Papers for

automated reasoning engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Modal style dependence logics extended and shown undecidable by reductions

Connecting Extended Modal Dependence Logics

Abstract: We consider three natural extensions of the basic decidable dependence logic LFD, adding, respectively, conditional dependence atoms, independence atoms, and identity atoms between variables. We show that these systems are all connected to first-order logic with identity by SAT reductions and in several cases also faithful translations. In particular, this implies that all these extended modal-style dependence logics are undecidable. This solves a number of problems left open in the original publication [1] introducing the LFD framework. The definitions and proofs presented here were found by ChatGPT and checked and streamlined as needed by the authors. At the end, we provide some discussion of what new things we learnt about dependence logics and about the methodology of using AI in logical research.

Mon 16 NovLogic in Computer Science
The gist
This paper studies logical systems that describe how variables depend on each other, which are important for reasoning in computer science. The authors look at three versions that add new types of dependence, like conditional dependence, independence, and identity between variables. They find connections between these logic systems and a well-known type of logic that includes equality, and show that these extended systems are undecidable—meaning there is no general algorithm to always decide their truth. They also discuss how AI tools helped discover and check their proofs.
Open → 2611.21287v1

New efficient method tests satisfiability of bounded formulas

A One-Sided Sublinear-Query Tester for Bounded-Degree 2SAT

Abstract: We give a one-sided tester for satisfiability of 2CNF formulas in the bounded-degree model. For every degree bound $Δ$, distance parameter $\varepsilon>0$, and $ν\in(0,1/2)$, its query complexity on $n$-variable formulas is $\widetilde O_{\varepsilon,Δ,ν}(n^{1/2+ν})$.

Thu 12 NovData Structures and Algorithms
The gist
The paper deals with checking if certain logical statements called 2CNF formulas can be true or are satisfiable. It focuses on formulas where each variable appears only a limited number of times, known as bounded-degree formulas. The authors present a method that tests these formulas quickly by looking at just a small part of them, rather than the whole. This approach guarantees it won’t incorrectly claim a satisfiable formula is unsatisfiable.
Open → 2611.16176v1

Horn clause max satisfiable subsets enumeration is computationally hard

A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression

Abstract: We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.

Tue 10 NovDiscrete MathematicsData Structures and Algorithms
The gist
This paper shows that figuring out whether there is another largest group of conditions that can all be true at the same time in a special kind of logic problem called a Horn expression is very hard. The authors demonstrate that this task is as difficult as the hardest problems in a class called NP-complete. Because of this, there is no fast method that can efficiently list all such largest groups unless a widely believed assumption about computational difficulty is wrong.
Open → 2611.14471v1

Strong backdoors to forests found efficiently in general sat problems

Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT

Abstract: In a seminal work, Gaspers and Szeider [FOCS 2013] gave a fixed-parameter tractable (FPT) approximate algorithm for finding a strong backdoor of size at most $k$ to incidence treewidth at most $t$, for a given CNF-formula $φ$. In particular, their algorithm runs in $f(k,t) |φ|^3$ time, and finds a strong backdoor to treewidth at most $t$, of $φ$, of size at most $2^k$ whenever there exists one of size at most $k$. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by $k+t$ was left open in their work and this has been repeatedly posed as an open question by Gaspers and Szeider, for example in [The Multivariate Algorithmic Revolution and Beyond 2012] and more recently in [Computer Science Reviews 2025], even for incidence forests and when the input is a $3$-CNF formula. We answer this question affirmatively. We show that strong backdoors to forests can be found in linear-FPT time on arbitrary non-tautological CNF formulas (not just on 3-CNF formulas). Given such a formula $φ$ and a budget $k$, our algorithm finds a strong backdoor to the class of forests, of size at most $k$, or correctly reports that none exists, in $2^{2^{O(k)}} |φ|$ time. Moreover, we show that our result is as tight as it can get. First, we show that finding strong backdoors to treewidth $t$ for any $t \geq 2$ is W[1]-hard, even on non-tautological 3-CNF formulas. Second, the running time of our algorithm is tight: it is linear in the input size and a better than double-exponential dependence on $k$ in the running time would imply a $2^{o(N/\log N)}$-time algorithm for solving 3-SAT on $N$ variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.

Mon 9 NovData Structures and AlgorithmsComputational Complexity
The gist
Finding small sets of variables that simplify complicated logic problems is very useful but often hard to do quickly. The authors answered a long-standing question by showing it is possible to find these sets, called strong backdoors to forests, in linear time with respect to the input size, even for very general formulas. They also proved that this speed is about as good as anyone can hope for unless a major breakthrough happens in solving 3-SAT problems. The work advances our understanding of which logical structures can be detected efficiently.
Open → 2611.12321v1

AI improves precise mathematical constants with interpretable proof refinements

Improving Analytic Constants via Interpretable AI-Guided Lean Proof Refinement

Abstract: AI agents are increasingly capable of discovering new mathematical results, yet their reasoning and generated proofs can be difficult to understand and verify. We introduce an interpretable framework for AI-guided mathematical discovery, focused on improving quantitative bounds on analytic constants. Our key insight is that existing proofs often contain slack in intermediate lemmas, which can be tightened without reconstructing the entire argument. To exploit this structure, we represent proofs as partially-formalized Lean blueprints: human-interpretable dependency graphs of definitions, lemmas, and theorems. An AI agent then iteratively refines the Lean code while preserving the blueprint's dependency structure, allowing local improvements to automatically propagate to a verified final bound. This interpretable structure allows humans to inspect the agent's refinements and understand how local improvements propagate to the final theorem. For Grothendieck's constant ($\mathcal{K}_G$), we obtain $$ \mathcal{K}_G \leq \fracπ{2\log(1+\sqrt{2})} - 10^{-17}, $$ an explicit numerical improvement over Krivine's 1977 bound. For Korenblum's constant ($\mathcal{K}_K$), we obtain $$ \mathcal{K}_K \geq 0.356565, $$ improving Wang's 2025 bound of $0.3554$. Our experiments demonstrate the potential of both partial formalization and iterative agentic refinement for interpretable mathematical discovery.

Sat 7 NovArtificial IntelligenceMachine Learning
The gist
Some important numbers in math come from complicated proofs that are hard to improve. The authors use AI to carefully revise parts of these proofs without changing the big picture, making the final numbers more accurate. They represent the proofs in a way that people can follow and check, allowing AI updates to show exactly how improvements happen step by step. Their method improved two well-known constants, showing that AI can help discover better math results while keeping them understandable.
Open → 2611.10961v1

Majority-vote pseudo-labels improve test-time reinforcement learning reliability

On the Reliability of Majority-Vote Pseudo-Labels in Test-Time Reinforcement Learning

Abstract: Test-time reinforcement learning (TTRL) adapts pretrained language models to unlabeled target-domain data using self-generated pseudo-labels, whose reliability remains poorly understood. We analyze majority-vote supervision for TTRL with online Direct Preference Optimization (DPO) and decompose its error into population-majority bias and prompt-dependent finite-rollout variation. Because population-majority bias is generally unidentifiable without external supervision, we focus on mitigating the downstream effects of finite-rollout variation. We propose \emph{Prompt-Conditional Distributionally Robust DPO (PC-Dr.DPO)}, which conditions within-prompt robust reweighting on observed vote reliability to make updates from sampling-sensitive prompts more conservative. We further introduce a cache-based mechanism to reduce self-supervised forgetting during online adaptation. Across six mathematical and knowledge-intensive reasoning benchmarks and five model backbones, PC-Dr.DPO matches or outperforms the strongest TTRL baseline in 24 of 30 settings.

Fri 6 NovArtificial Intelligence
The gist
People often try to teach AI models new tasks without giving them labeled examples, by letting the AI guess the answers itself and learn from those guesses. This paper looks at how reliable these self-generated guesses are when many guesses are combined by majority vote. The authors found that some errors come from differences in how prompts work and introduced a new method to make learning more cautious with less reliable guesses. Their method also keeps older knowledge from being forgotten. Tests showed their approach works better or as well as previous methods on several reasoning tasks.
Open → 2611.09872v1

Large language models often solve problems before formalizing programs

Solver-Like Behavior in Large Language Models as Formalizers

Abstract: In the LLM-as-formalizer paradigm, a large language model translates a problem into a formal program and leaves the search to a solver, gaining the solver's guarantees. Formalizers are now often reasoning models that write a long reasoning trace before the program, yet they are judged only by the program's output. We find that the trace routinely does the solver's job, assigning, testing and ruling out values until it often reaches the full answer; we call this solver-like behavior (SLB). We define an ontology of SLB over the trace, the program and its output, and use LLM judges, checked against human labels, to label 2,000 generations from three reasoning models on four constraint satisfaction datasets, each formalized in a declarative and an imperative formal language. SLB appears in 85% of traces and takes 24% of reasoning tokens, yet the program usually recomputes the answer, so the effort is redundant. The 9% of programs that inherit the trace's answer also inherit its errors, and pass output-based evaluation whenever that answer is correct. The amount of SLB is not associated with accuracy, and SLB is more common in imperative Python than in declarative Z3 or PDDL. Cautionary prompts reduce it by only a quarter, but hiding the problem's values behind placeholders, which the program receives only at run time, removes 97% of it without loss of accuracy. Formalizers should therefore be evaluated by how their programs are reached, not only by what they output.

Mon 2 NovComputation and LanguageArtificial Intelligence
The gist
Sometimes large language models write out detailed steps to solve a problem even before turning that problem into a formal computer program. The researchers found that these models often do the hard work of testing and ruling out possibilities in their reasoning text, which they call solver-like behavior. However, the final program they write usually repeats this work, making the reasoning redundant. They also found that this behavior is more common when the program is written in certain languages, and simple changes in how the problem is presented can reduce it a lot without hurting accuracy.
Open → 2611.02395v1

Three paraclassical logics combine two negations for classical logic insights

Paraclassical Logics with Two Negations

Abstract: We study three paraclassical propositional logics with two negations, CLoaN, CLouN, and CLauN, obtained by pairwise combining the one-negation systems CLuN, CLaN, and CLoN. CLuN's negation is glut-tolerant and paraconsistent, CLaN's negationis gap-tolerant and paracomplete, and CLoN's negation is both paraconsistent and paracomplete. We provide sound and complete two-valued non-deterministic semantics for each of the two-negations systems. We then focus on CLauN, the system containing the primitive dual pair of CLaN and CLuN negations. In this setting, we show deductive relationships between different negations expressible in CLauN; we show two diferent ways to recapture classical logic by means of translations, locally and globally; and we show a duality results for the multiple conclusion consequence relation of the logic.

Thu 29 OctLogic in Computer Science
The gist
This paper looks at three logical systems that use two types of negation rather than one. The authors study how combining these negations can represent different logical ideas, like tolerating contradictions or gaps in information. They describe how these systems work with special two-valued semantics and show how classical logic can be recreated within these frameworks. They also explore relationships between the different negations and logical consequences in these systems.
Open → 2610.40814v1

Connecting semantics for intuitionistic and classical logic operators

Connecting Base-Extension Semantics, Beth Semantics, and Ecumenical Logic

Abstract: We investigate the relationship between base-extension semantics, Beth semantics, and Prawitz's ecumenical logic. We first present a base-extension semantics for the propositional fragment of Prawitz's system and prove that it is sound and complete. The semantics interprets intuitionistic and classical operators directly within a common proof-theoretic framework, without reducing the classical operators to their intuitionistic counterparts by means of a translation. We then analyse the effect of incorporating Beth-style clauses into base-extension semantics. When arbitrary bases are admitted and $\bot$ is governed by atomic explosion, these clauses trivialise. By contrast, when $\bot$ is treated as a basic sentence and attention is restricted to consistent bases, the Beth-style clauses for atoms and disjunction characterise, respectively, classical atoms and classical disjunction in Prawitz's system. We also obtain equivalent, path-independent formulations of the classical clauses for atoms, disjunction, and implication. These results reveal that the consistency constraint is not merely a technical restriction: within base-extension semantics, it transforms clauses originally associated with intuitionistic semantics into semantic characterisations of classical operators.

Wed 28 OctLogic in Computer Science
The gist
This paper explores how different ways of understanding logical statements relate to each other, particularly intuitionistic and classical logic. The authors show a way to interpret both types of logic operators within a single framework without converting one into the other. They also find conditions under which certain semantic rules identify classical logic features. Their work clarifies how adding certain rules changes the meaning of logical operators when interpretations are restricted to consistent scenarios.
Open → 2610.38871v1

Conference shares advances in non-classical logics and applications

Proceedings Twelfth International Conference on Non-Classical Logics. Theory and Applications

Abstract: Non-Classical Logics. Theory and Applications (NCL) is an international conference aimed at presenting novel results and survey papers in the broad field of non-classical logics and their applications. The first two editions were held in Ł{ó}d{ź}, Poland, in September 2008 and 2009. Subsequent editions were organised in Toru{ń} (2010, 2012, 2015, 2018) and Ł{ó}d{ź} (2011, 2013, 2016, 2022, 2024). The tenth edition of the conference, organised by the University of Ł{ó}d{ź} in 2022, was the first to have its proceedings published in EPTCS. We are honoured and pleased to continue this practice and, for the third time, include all accepted long papers in an EPTCS volume. Furthermore, for the first time, we have also included all accepted extended abstracts in the volume.

Sun 25 OctLogic in Computer ScienceSymbolic Computation
The gist
Non-classical logics are systems of reasoning that go beyond traditional true-or-false logic, and they have many uses in computer science and mathematics. The conference gathers experts who present new discoveries and review existing knowledge about these logics. This volume includes not only full research papers but also extended summaries, making the shared information broader than before. The event has been held regularly in Poland since 2008 and this edition continues the trend of publishing all accepted works for wider access.
Open → 2610.34489v1

Model theoretic formalization clarifies alkhwarizmi inheritance rules

A Model-Theoretic Formalization of AlKhwaremis ilm alfaraid

Abstract: This paper presents a model theoretic and computational formalization of AlKhwarizmis treatment of inheritance within the framework of Computational Fiqh. We first show that every inheritance configuration in a specified class is representable as a finite system of rational linear equalities and inequalities, and that such systems are decided exactly by Fourier Motzkin elimination over Q. We then define the fixed dimensional inheritance structure Vd with distinguished claimant coordinates, and prove that every admissible rational linear coordinate realization is isomorphic to Vd, this establishes the algebraic representation as canonical within that class. The complete first order theory Td of Vd is shown to be complete by construction and is explicitly distinguished from the decidability of the inheritance relevant fragment. The methodological principle is then related to a broader formalization of closed Fiqh domains via exhaustive case generation, Horn clause axiomatization, and terminating deduction, yielding domain relative computational completeness.

Sat 24 OctLogic in Computer ScienceComputation and Language
The gist
The paper translates ancient Islamic inheritance rules into precise mathematical language, showing that these rules can be represented and solved using known mathematical techniques. The authors prove that all valid inheritance divisions in their framework fit a standard structure, making the representation unique and consistent. They also connect this approach to broader methods for automating legal reasoning in Islamic law. This work helps computers understand and apply historic inheritance rules exactly.
Open → 2610.33629v1

Arbor tracks reasoning states to pinpoint errors in long problem solving

ARBOR: Locating Reasoning Failures in Long Chains of Thought through Reasoning State Tracking

Abstract: Large reasoning models solve complex problems through long chains of thought, in which prior work has documented failure modes such as overthinking, underthinking, and unsupported deductions. Existing methods detect these failures from local signals: textual similarity to nearby steps, switch tokens, or an LLM's judgment of a step's correctness. However, what a step contributes to the solution depends on the state that earlier steps have established, so identifying failures requires a global view that tracks that state across the trajectory. Therefore, we propose ARBOR, a reasoning-failure attribution framework that represents each trajectory as a tree of reasoning states, built as each step creates, verifies, prunes, or revisits a state, and attributes each failure to a relation between a step and the state preceding it. Using ARBOR, we refine the three failure modes into distinct subtypes that harm reasoning through different mechanisms and at different costs. We find that the tree state ARBOR maintains before a step separates failure steps from the at-risk steps at which the failure did not occur. We discuss how ARBOR integrates with existing mitigations at inference time and in training data. Code, data and interactive examples are available at https://inklab.usc.edu/ARBOR.

Thu 15 OctComputation and LanguageArtificial Intelligence
The gist
Many large AI reasoning models solve problems by thinking through many steps, but sometimes they make mistakes due to thinking too much, too little, or making unsupported jumps. The authors introduce ARBOR, a new way to watch what each step adds to the ongoing reasoning and see where mistakes happen by tracking how the reasoning changes over time. This method helps break down failures into clearer types and tells which steps are truly wrong versus ones likely to fail. This tracking can improve how AI systems fix or avoid errors while solving hard problems.
Open → 2610.22717v1

Compact SAT methods improve geometric graph dimension finding

Geometric Graph Representations via Compact SAT Encodings

Abstract: We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of axis-aligned boxes; cubicity is defined analogously using unit cubes. Grid-based formulations face a geometric discretization bottleneck, growing rapidly with the target dimension. We avoid this bottleneck by encoding the total order of interval endpoints in each coordinate. For an $n$-vertex graph and target dimension $d$, our boxicity encoding uses $O(n^2d)$ variables and $O(n^3d)$ clauses, both linear in $d$. Requiring the left- and right-endpoint orders to agree yields a cubicity encoding of the same asymptotic size. Satisfying models are decoded into independently checked geometric representations, while unsatisfiable instances used as lower-bound evidence carry mechanically verified DRAT certificates. In a controlled evaluation with 186 trials per encoding on standard and structured graph families, the order encoding solves 96.8% of trials, compared with 71.0% for the known grid formulation, and reduces mean PAR-2 time from 178.21 to 21.70 seconds. The pipeline also certifies exact values for several named graphs. We turn one such value into a reusable obstruction by proving that every Kneser graph $K(n,k)$ with $k\ge3$ and $n\ge2k+1$ contains an induced Desargues graph. The resulting lower bound, together with an explicit three-dimensional representation of $K(7,3)$, establishes $\operatorname{boxicity}(K(7,3))=3$. This disproves the conjecture of Caoduro and Sebo that $\operatorname{boxicity}(K(n,k))=n-k$ for all $k\ge3$ and $n\ge2k+1$.

Thu 15 OctComputational GeometryDiscrete MathematicsData Structures and Algorithms
The gist
Determining the geometric dimension in which a graph can be represented by simple shapes like boxes or cubes is a challenging problem. The authors introduce a new way to encode this problem into SAT (logic puzzles that computers solve) much more efficiently than before. Their approach can prove exact answers faster and with certificates that ensure correctness. They also disprove a previous guess about a family of graphs called Kneser graphs, showing one example requires fewer dimensions than expected.
Open → 2610.22241v1

Complexity boundaries identified for reasoning in infinite argument systems

Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

Abstract: Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy ($Σ_1^1$ or $Π_1^1$), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non-empty existence ($\NE$). For grounded semantics, credulous and skeptical acceptance are already known to be $Σ_1^0$-complete. We show that non-empty existence is also $Σ_1^0$-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, $\Cred_{\pref}$ is shown to be in $Π_1^0$-c and $\NE_{\pref}$ is $Σ_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $Π_1^1$ and $\UniPref$ in $Σ_2^1$-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.

Thu 8 OctArtificial IntelligenceLogic in Computer Science
The gist
Argumentation frameworks help computers reason when information is complicated or conflicting. The researchers studied how hard it is to decide various questions about these frameworks when the structures are infinite but follow certain computability rules. They discovered exactly which problems become simpler and which remain very complex depending on the type of reasoning used. This helps clarify when infinite argument systems can be managed more easily by computers and when complex logic still makes reasoning difficult.
Open → 2610.12008v1

Loop-native residuals enable transformers to handle tens of thousands of steps

Scaling to Tens of Thousands of Test-Time Iterations with Loop-Native Attention Residuals

Abstract: In this paper, we argue that looped Transformers need their own residual connections to prevent performance degradation as the number of iterations grows. We observe that increasing loop iterations can reduce reasoning accuracy: noisy state updates overwrite correct intermediate deductions and even undo completed solutions. This leaves subsequent iterations to recover lost information from an already degraded representation: once an error arises in an earlier loop, often as a result of long-range propagation through the recurrence, later loops find it difficult to correct. In this paper, we introduce InfiLoop, a loop-native residual connection that learns which past computations to retain and how much to accept from each new update. InfiLoop combines content-based weighting with learned temporal decay to maintain a running summary of recurrent states. An exact streaming recurrence keeps its persistent aggregation memory constant as the loop count grows. The resulting adaptive update suppresses unreliable proposals and preserves useful intermediate states. Across extensive reasoning tasks, a 7M-parameter InfiLoop model outperforms existing recursive architectures, reaching 97.9% exact accuracy on Sudoku-Extreme, and 13.6% pass@2 on ARC-AGI-2. Notably, on Sudoku-Extreme, InfiLoop continues to improve with test-time looping beyond 20,000 effective steps, showing that added depth translates directly into stronger reasoning. Our code is available at https://github.com/pixeli99/InfiLoop.

Thu 8 OctArtificial Intelligence
The gist
Transformers that repeatedly process information can lose accuracy over many cycles because new, noisy updates overwrite earlier correct steps. The authors introduce InfiLoop, a new way to connect these cycles so that useful information sticks around while unreliable updates get ignored. This allows the system to improve reasoning steadily, even after tens of thousands of repetitions. Their method performs better than previous approaches on challenging tasks like extreme Sudoku puzzles.
Open → 2610.11570v1

Mathematical agents need mandatory checks to catch fake tool answers

When Tools Lie: Reliability of Mathematical Agents Under Corrupted Tool Feedback

Abstract: Mathematical problem solving often requires deterministic computational steps that agents delegate to tools and implicitly trust. Yet tools can fail silently, returning plausible but incorrect results. How well can agents detect and correct corrupted tool call outputs? We study this through a controlled corruption framework where a hidden interceptor replaces tool call results with plausible incorrect information on targeted problems. We evaluate agents across 31 problems under four verification designs including no verification (baseline), mandatory same-context reflection, optional fresh-context verification, and optional structural verification. Without verification, corruption causes dramatic accuracy loss, from 100% down to 72.4%. Mandatory reflection fully recovers this performance to 100%. Optional verification improves accuracy only when models actively invoke it. Our results show that checking frequency is strongly associated with robustness differences, while unequal invocation prevents a controlled comparison of verifier quality. A supporting recovery experiment shows that full problem restart succeeds in 100% of cases after explicit detection. These findings demonstrate that verifier availability and verification policy are separate components of mathematical-agent reliability. Mandatory policies enforce verification while optional policies depend on the model's own choice to invoke it.

Tue 6 OctCryptography and SecurityArtificial IntelligenceSoftware Engineering
The gist
Mathematical problem-solving often relies on computer tools, but these tools can sometimes give wrong answers that look believable. The authors studied how well agents detect and fix these false answers by intentionally changing tool results in tests. They found that without double-checking, accuracy drops significantly, but requiring agents to always reflect on the tool’s answer brings accuracy back to perfect. Optional checks helped only if the agent chose to do them. This shows that making verification mandatory is important for reliable math problem-solving with tools.
Open → 2610.08097v1

Search method improves math reasoning in language models

Improving Math Reasoning through Value-guided Informative Search

Abstract: Reinforcement learning with verifiable rewards (RLVR) has substantially improved the mathematical reasoning capabilities of large language models. Recent work introduces search into RLVR rollouts to increase trajectory diversity, but diversity alone does not ensure that the search-induced rollout policy improves upon the current policy. To address this gap, we propose APIVIS, a training-time framework that adapts finite-budget Gumbel search to chunk-level mathematical reasoning. APIVIS combines direct and searched responses within each rollout group, allowing improvements found by search to produce informative relative rewards. It further applies selective supervision to search-improved tokens, preserving a learning signal when uniform group rewards render GRPO ineffective. We show that exact value-guided selection improves the expected verifier reward at each searched state and that this guarantee extends to the complete rollout policy, with a corresponding approximate guarantee under bounded value-estimation error. Experiments on widely recognized mathematical reasoning benchmarks and different model scales demonstrate substantial improvements over competitive search-based methods, validating the effectiveness of APIVIS.

Thu 1 OctArtificial Intelligence
The gist
Solving math problems with AI models is tricky because they need to find the best steps to get the right answer. The authors noticed that just trying lots of different ways doesn’t always help. They created a new method called APIVIS that carefully picks better steps during the search and uses those improvements to teach the model. This makes the AI better at solving math problems. They tested it on common math benchmarks, and it worked better than earlier methods.
Open → 2610.01080v1

Cogentic orchestrates multiple agents to discover new mathematical proofs

Cogentic: Multi-Agent Orchestration for Automated Proof Discovery

Abstract: We present Cogentic, a multi-agent harness for automated proof discovery on open research problems. While frontier language models can generate strong mathematical ideas in a single shot, single-shot generation is often insufficient for open problems that require exploring multiple competing conjectures, overcoming subtle technical obstructions, and retaining intermediate progress over a long horizon. Cogentic addresses these challenges through an iterative prove--verify loop in which an orchestrator allocates a population of independent provers across distinct proof directions, subjects their output to adversarial verification by several specialized components, and promotes confirmed intermediate results into a persistent verified ledger that later rounds build on. The harness is designed to be able to solve research-level math and theoretical computer science problems. Using Gemini as the base model, Cogentic produced novel results on five open problems across online learning, auction theory, and mechanism design. Each result was independently verified by domain experts and is developed in full in companion papers. We list these results, and new ones as they are verified, at https://sites.google.com/view/cogentic .

Wed 30 SeptArtificial IntelligenceComputer Science and Game Theory
The gist
Mathematical problems often need many ideas and long reasoning steps that simple AI tries only once can’t handle. The authors created Cogentic, a system that uses many AI agents working together to try different proof ideas, check each other’s work, and keep track of important progress. This back-and-forth process helps tackle really hard math and computer science problems. Using this system, the authors found new solutions to five open problems in fields like online learning and auction design, verified by experts.
Open → 2609.40324v1

Cheq logic cannot be captured finitely and is undecidable

Non-finite Axiomatizability and Undecidability of $\mathsf{Cheq}$

Abstract: We prove that $\mathsf{Cheq}$ is not finitely axiomatizable, resolving a longstanding open problem in intermediate and modal logics. We further prove that the undecidability of Medvedev logic implies the undecidability of $\mathsf{Cheq}$.

Wed 30 SeptLogic in Computer Science
The gist
Some parts of logic are tricky to fully describe with a small set of rules. The authors showed that the system called Cheq cannot be captured with a finite list of axioms, which solves a question that has been open for a long time. They also found that if a related logic called Medvedev logic is impossible to decide automatically, then Cheq is also undecidable. This means certain logical problems in Cheq have no algorithm that always gives an answer.
Open → 2609.39577v1

Agentic meta reasoning improves long task control in large ai agents

Thinking Before Thinking: Scaling Agentic Inference Through Meta-Reasoning

Abstract: As agents take on longer and more complex problems, controlling the execution becomes a task in its own right. Each step in the run brings new control choices, like which partial work to build on, whether to start fresh, or when to stop. We introduce agentic meta-reasoning, an inference-time harness that makes these choices an explicit and structured reasoning process. Workers carry out the task-level computation, while a controller consolidates what the run has established, explores next options, assesses what each option is worth under the remaining budget, and dispatches the chosen work with context drawn from persistent memory. Between decisions the controller carries only a compact account of the run rather than replaying its full history. Our baselines span production coding agents and research harnesses, together with a Direct Control Agent using the same workers and compute budget allowance. On ProgramBench, which tests long-horizon agentic capability through program reconstruction, meta-reasoning achieves 71.5% with GPT-5.5 against 58.0% for Codex; with Opus 4.8 it achieves 67.2% against 65.5% for Claude Code. On the other benchmarks, spanning abstract reasoning, multi-domain long-horizon reasoning, and proof generation, it gains between 3.6 and 4.2 points over direct control, averaged across three frontier models. It keeps improving over the tested budget ranges where direct control plateaus, though its overhead can hurt at small budgets. Artifact-graph analysis reveals more reuse of earlier work, higher coverage of correct solutions in most settings, and nonuniform gains in final selection. These results indicate that spending computation on structured control becomes more important as agents scale to longer runs.

Tue 29 SeptArtificial Intelligence
The gist
Large AI agents solving complicated problems need to decide how to work step-by-step, like picking what to build on next or when to stop. The authors introduce agentic meta-reasoning, which adds a smart controller that manages these decisions instead of just following fixed steps. This controller summarizes progress, explores options, evaluates their value, and chooses the best next move without rereading everything done before. Their tests show this approach helps AI perform better on complex programming, reasoning, and proof tasks by reusing earlier work and making better choices.
Open → 2609.38147v1

Language models trained to prove reasoning steps for better answers

Learning to Prove, Not Just to Answer: Reinforcement Learning from Formal Verification for Natural-Language Logical Reasoning

Abstract: Large language models (LLMs) are increasingly deployed for natural-language logical reasoning, where the final answer is easy to check but the proof behind it is not. In natural-language logical reasoning, an intermediate conclusion should follow from its premises, and the resulting derivation should support the final answer. Existing methods lack machine-checkable verification of intermediate conclusions and answer-supporting proof dependencies, so they may assign credit to invalid or answer-irrelevant steps. We propose Proof-R1, an RL framework from formal verification that trains LLMs to construct verifiable proofs for natural-language logical reasoning. Proof-R1 admits a generated conclusion into the verified proof state only when the corresponding reasoning action satisfies the proof obligations through UNSAT-based machine-checkable formal verification. Proof-R1 also recovers the answer-supporting dependency closure to trace the proof structure of the final answer and align outcome credit with the proof dependencies. Experiments demonstrate that Proof-R1 improves answer accuracy across three logical reasoning benchmarks and four backbone models and outperforms training-free agents and training-based methods in terms of reasoning-process verifiability.

Tue 29 SeptArtificial Intelligence
The gist
Some computer programs can answer tricky questions, but the way they explain their answers is not always clear or trustworthy. The authors created a new way to teach language models to provide proofs that can be checked by a computer, making sure every step in the reasoning is valid. This helps the programs give more accurate answers and clearer explanations. Their approach was tested on several challenges and improved performance compared to previous methods.
Open → 2609.37203v1

Counterfactual memory improves language agent task performance consistently

COUNTERMEM: World-Model Verified Counter-Factual Memory for Language Agents

Abstract: Existing agent memory frameworks mainly create memory through an agent's interaction with the factual world, e.g., remembering feedback from actions taken to improve performance on future tasks. However, these frameworks seldom ask the "what if" question during memory construction: what if a different action had been taken, would the feedback have changed, and how could this feedback become useful memory? Obtaining such feedback directly in an active environment can be expensive and can alter the state needed for comparison. In this work, we introduce COUNTERMEM, a reinforcement-learning framework for constructing and using verified counterfactual memory across tasks. After a failed action, COUNTERMEM evaluates local alternatives from a copy or reset of the original state using executable world models, such as tests, proof checkers, and solvers. It stores improvements with the original and corrected actions, checked outcomes, and conditions for reuse. A learned memory-use policy selects a retrieved record or skips memory to balance task success and interaction cost, while the base LLM remains fixed. Both memory and policy are frozen during held-out evaluation. We evaluate COUNTERMEM on 12 benchmark settings across six domains. With gpt-oss-120b, COUNTERMEM improves both ReAct and Reflexion on all 12 benchmarks across six domains, averaging a gain of 12.6 percentage points over their unaugmented versions. In the four-domain comparison across two backbones, task-run tokens decrease by 7.7-42.0%, excluding offline selector-training costs. Further analyses show that removing verification or persistent storage weakens the gains, while applying verified corrections to unsuitable decisions can reverse them. Code will be released upon acceptance.

Fri 25 SeptArtificial Intelligence
The gist
Memory systems in language agents usually learn from what actually happened, but don’t imagine what could have been. The authors introduce COUNTERMEM, a framework that lets an agent consider alternative actions after a failure by simulating and verifying outcomes. This approach helps the agent remember better and choose smarter next steps without changing its core language model. Tested across various tasks and language models, COUNTERMEM shows clear improvements in success rates and efficiency.
Open → 2609.31874v1

Exponential complexity lower bound proved for bit pigeonhole principle proofs

An exponential lower bound for the bit pigeonhole principle in resolution over parities

Abstract: Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{Ω(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

Sat 19 SeptComputational ComplexityLogic in Computer Science
The gist
The authors showed that any logical proof method called resolution over parities needs an extremely large number of steps to prove a basic counting puzzle known as the bit pigeonhole principle. This means these proofs cannot be made efficient by restricting their structure. The finding uses advanced math and computer-assisted verification to confirm the result rigorously. Such limits help us understand why some logic puzzles are inherently hard for certain automated reasoning methods.
Open → 2609.23015v1

Quantum computers prove geometry theorems from olympiad problems

Proving olympiad geometry theorems on a superconducting quantum processor

Abstract: Automated theorem proving seeks to use computational systems to prove or disprove mathematical and logical statements [1, 2]. It underpins a wide range of applications, and enhancing theorem-proving capabilities remains a central objective in artificial intelligence [3]. Although recent neuro-symbolic systems have achieved remarkable progress [4-7], their operation is ultimately constrained by classical computational architectures. Quantum computing [8], by contrast, enables information encoding and coherent parallelism beyond classical limits [9-14], raising the possibility of accelerating structured symbolic deduction [15]. Here we report the experimental realization of automated geometry theorem proving on a fully programmable superconducting quantum processor. We develop two complementary quantum proving frameworks. The first implements Wu's algebraic elimination method using quantum pseudo-division, with multivariate polynomials represented in superposition states, enabling quantum algebraic theorem proving. The second implements the full-angle method as backward symbolic reasoning through a hybrid quantum strategy-guided architecture, demonstrating a general route toward quantum symbolic proof search. As illustrative examples, we prove two theorems on a superconducting quantum processor: the perpendicularity of the diagonals of a square and a 1978 International Mathematical Olympiad geometry problem. Our results establish, at the experimental level, automated logical reasoning as a viable task for near-term quantum processors and provide a concrete pathway toward quantum-enhanced symbolic intelligence.

Sun 13 SeptArtificial Intelligence
The gist
Proving mathematical theorems automatically is a challenge that usually relies on classical computers. The authors demonstrate that a quantum computer can carry out such proofs in geometry by encoding mathematical expressions as quantum states and performing symbolic reasoning. They used a superconducting quantum processor to prove the diagonals of a square are perpendicular and to solve a geometry problem from the International Mathematical Olympiad. This shows quantum machines can support logical reasoning tasks in new ways.
Open → 2609.14533v1