Are Language Models Efficient Reasoners? A Perspective from Logic Programming
Authors: Andreas Opedal
Yanick Zengaffinen
Haruki Shirakami
Clemente Pasti
Mrinmaya Sachan
Abulhair Saparov
Ryan Cotterell
Bernhard Schölkopf
Venue: NeurIPS 2025 poster ()
Keywords: language model
logic programming
proof
arithmetic reasoning
math word problem
search
reasoning
efficiency
Primary area: deep_learning

Abstract: Modern language models (LMs) exhibit strong deductive reasoning capabilities, yet standard evaluations emphasize correctness while overlooking a key aspect of reasoning: *efficiency*. In real-world reasoning scenarios, much of the available information is irrelevant, and effective deductive inference requires identifying and ignoring such distractions. We propose a framework for assessing LM reasoning efficiency through the lens of logic programming, introducing a simple method to align proofs written in natural language---as generated by an LM---with shortest proofs found by executing the logic program. Efficiency is quantified by measuring how well a model avoids unnecessary inference. Empirically, we construct a dataset of math word problems injected with various number of irrelevant axioms that vary in semantic overlap with the goal theorem. We find that current LMs show marked accuracy declines under such conditions---even with minimal, domain-consistent distractions---and the proofs they generate frequently exhibit detours through irrelevant inferences.

Are Language Models Efficient Reasoners? A Perspective from Logic Programming
Andreas Opedal
Yanick Zengaffinen"
Haruki Shirakami
Clemente Pasti Bernhard Schölkopf
Mrinmaya Sachan
Abulhair Saparov'
Ryan Cotterell
EETH Zürich
MPP for Intelligent Systems, Tübingen
EPFL
'diap Research Institute
'Purdue University
Abstract
Modern language models (LMs) exhibit strong deductive reasoning capabilities, yet standard evaluations emphasize correctness while overlooking key aspect of reasoning: efficiency. In real-world reasoning scenarios, much of the available information is irrelevant, and effective deductive inference requires identifying and ignoring such distractions, We propose framework for assessing LM reasoning efficiency through the lens of logic programming, introducing a simple method align proofs written in natural language as generated by an LM--wthh shortest proofs found by executing the logic program. Efficiency quantified by measuring how well a model avoids unnecessary inference. Empirically, we construct dataset of math word problems injected with various number of irrelevant axioms that vary in semantic overlap with the goal theorem. We find that current LMs show marked accuracy declines under such conditions with minimal, domain- consistent distractions- and the proofs they generate frequently exhibit detours through irrelevant inferences.
Introduction
Large language models (LMs) appear capable of solving a wide range of tasks that rely on deduc- tive reasoning, particularly when post-trained with reinforcement learning (Lightman et al., 2024; DeepSeek-Al, 2025) and scaled to use more compute at test time (Wang et al., 2024; Muennighoff et al., 2025; Snell et al., 2025). However, emerging findings suggest recent reasoning models often gen- erate more tokens than necessary to solve problems, even for simple deductive tasks (Chen et al., 2025; Pu et al., 2025). Such findings point towards a key dimension of deductive reasoning that standard eval- uations of LMs' reasoning abilities fail to systematically assess efficiency. Indeed, more abstractly, in most real-world reasoning tasks, more information is available than is necessary solve the prob- lem. This spurious information is not random: it often interacts with relevant information, enabling the derivation of true but irrelevant conclusions. Crucially, it is unknown priori which pieces of in- formation will be relevant for determining whether a desired conclusion is supported by the evidence. An efficient solution to a problem uses only necessary information and takes few steps possible.
To characterize efficiency, we adopt a formalization of deductive reasoning based on logic programming (Kowalski, 1974). Our perspective is that logic programming provides clean and flexible framework for reasoning within a understodd proof system. Given logic program that is, a set of inference rules and axioms proof of some goal theorem can be viewed as path in a hypergraph induced by the inference rules, starting from vertices corresponding to axioms and terminating vertex corresponding the goal theorem. Then, the most efficient proof is simply a shortest such path. Using this machinery. the goal of this paper is to evaluate a language model's reasoning efficiency. Thus, we require an additional mechanism bridge the gap between reasoning
Pleasse direct correspondence to andreas... caciaas.peedeeiii ethz. ch, ryan www.erellteeeennn.o ethz. ch, and asaparov@purdue. edu. "Code for this project is available at http:://ggghhbbccoooooooaaa/rrra eff.ciiincc.cc.cc...c..cooo
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in logic programming and reasoning in natural language. To this end, we introduce the notion of a verbalized logic program, in which each theorem in the logic program is associated with a set of natural language strings. Verbalized logic programs allow us to map the deductions performed by an expressedd as a natural language proof-onte onto deductions performed during the execution of a logic program. While numerous recent papers use number of generated tokens as proxy for efficiency (Arora & Zanette, 2025; Han et al., 2025; Ma et al., 2025), doing so conflates inefficiency stemming from two separate sources: (1) unnecessary deduction steps and (2) verbosity in the natural language strings expressing those deduction steps. In contrast, our framework disentangles these two factors, with our paper's experiments emphasizing the former.
Empirically, we construct verbalized logic programs for grade school math word problems (GSM problems; Cobbe et al., 2021; Li et al., 2024; Zhang et al., 2024), adopting methods from Opedal et al. (2025). Our primary experimental manipulative is the injection of irrelevant axioms into these GSM programs, which yields many possible implications that are irrelevant to goal theorem of interest. We experiment on problems that vary both how much the information in the irrelevant axioms overlap with the goal theorem, well as in how many such axioms are injected, generalizing existing datasets that only include a single irrelevant axiom (Shi et al., 2023; Mirzadeh et al., 2025). We first measure accuracy, showing that current LMs are less accurate problems containing irrelevant axioms than on equivalent problems without them. This performance gap often persists even in the simplest cases, where a single irrelevant axiom from the same domain is introduced, and grows larger as more irrelevant axioms are added. We confirm that this reduction in accuracy is not due to longer inputs alone: LMs usually perform better control problems of equal length but without irrelevant content.
Next, we map the reasoning performed by the LM onto theorems they correspond to when executing the logic program. We find that while the LMs predict most of the correct intermediate theorems for the problems where they correctly generate the goal, they are often inefficient. In particular, for GSM problems where about half of the axioms are irrelevant, more than half of the LM's predicted theorems are irrelevant too, i.e., not needed for proving the goal. The LMs are particularly inefficient when the ir- relevant axioms overlap semantically with the query for instance, when the question asks "how many cats does Ryan have?" and the irrelevant axioms also mention "Ryan" " or "cats". On the other hand, these results also suggest that the LMs' search procedure sometimes employ useful heuristic based on such overlap. Our results shed some light on how LMs, albeit in natural language, perform inference.
Outline. The remainder of the paper is structured as follows: $2 situates our contributions among related work. $3 provides relevant background on logic programming and discusses how reasoning efficiency is measured relative to shortest proofs. $4 introduces verbalized logic programs and the specifics of our GSM programs. $5 presents experiments and results on how LMs reason on verbalized GSM programs with irrelevant axioms. Apps. A-D give further technical details and empirical results.
2 Related Work
Evaluating Reasoning. Most studies and benchmarks on LM reasoning evaluate correctness based on the LM's final answer (Hendrycks et al., 2021; Patel et al., 2021: Rein et al., 2024; Yu et al., 2024, inter alia). However, correctness of the final answer does not guarantee correctness of the proof (Lyu et al., 2023: Turpin al., 2023). Some studies include more fine-grained reasoning evaluations by verifying LM-generated proofs (Gontier et al., 2020; Frieder et al., 2023; Nguyen et al., 2024; Wang et al., 2024; Petrov et al., 2025). While useful, many such evaluations rely either on manual scrutiny or heuristic measures of the proof's ' correctness. An alternative approach is to use proof assistants, e.g., Lean (de Moura& & Ullrich, 2021), for formal verification (First et al., 2023; Tsoukalas al., 2024); however, LMs may have been trained on less amounts of such data as compared to natural language. We perform an automatic evaluation by parsing the L.M-genratted output into proofs in logic programs.
Irrelevant Information in Reasoning Tasks. Our work relates to papers that evaluate LMs' ability correctly solve problems with irrelevant information (or missing information; Li et al., 2025). Shi et al. (2023) create such dataset by appending single irrelevant statement to problems taken from GSM8k (Cobbe et al., 2021). Mirzadeh et al. (2025) seem to take a similar, albeit more manual ap- proach; however, details presented are scarce and their dataset has not yet been made publicly available. Xu et al. (2025) incorporate irrelevant statements as part of a pipeline for generating problem varia- tions. Anantheswaran et al. (2025) use prompting-basee method for augmenting problems with sev-
'Previous work have made implicit use of similar notions (e.g., Betz et al., 2021; Clark et al., 2021; Saparov & He, 2023; Morishita et al., 2023; Han al., 2024).
2

---

eral irrelevant statements. We formalize the notion of irrelevance through logic programming and gen- eralize previous approaches by generating problems that may have several, arbitrarily placed irrelevant axioms, which can be used together in further inference. Thus, there are many implications that are ir- relevant to the goal theorem and the challenge becomes not only to generate correct proofs, but proofs that only contain steps that are necessary. By generating new problems from scratch, our approach avoids bias from memorizing the efficient solution seen during training (see, c.g., Zhang et al., 2024).
Search and Efficiency. Other studies have investigated whether and how transformers can learn search tasks (Gandhi et al., 2023. 2024; Kazemi al., 2023; Lehnert al., 2024; Sanford al., 2024; Sel et al., 2024; Shah et al., 2024; Saparov et al., 2025). We are interested not only in whether a transformer-based LM can perform accurate search, but in how efficient is. Efficiency of large (reasoning-basse LMs is a rapidly growing area of research (Sui et al., 2025), due to their often lavish use of compute (Chen et al., 2025; Pu et al., 2025). Several methods have been proposed to make reasoning more efficient (Han et al., 2025; Ma et al., 2025), e.g., by incorporating length rewards in training (Arora & Zanette, 2025; Luo et al., 2025; Team et al., 2025). While these papers focus solely on the number of tokens, we argue that it is more informative to measure efficiency based on the natural language proof, since a long output can be explained either by unnecessary inference steps or by "verbose" verbalizations of the proof. Moreover, an LM should avoid generating redundant tokens (Xia et al., 2025), but it should also not skip necessary inference steps in favor of a shorter output.
3 Logic Programming and Deductive Reasoning
This section provides relevant background on logic programming (Kowalski, 1974). It also introduces the metric we propose for scoring proof's efficiency in $3.2.
3.1 Typed Logic Programs with Built-ins
Basic Notions. A signature is a 3-tuple Σ = (Ep. Ez, Ex). where Ep is set of predicate (or relation) symbols, denoted p. q. r..; Σg set of constants, denoted æ, y, 2, ..:; Σy is a set of variables, denoted X, Y, Z, Every predicate is associated with arity, which we denote using the function arity ar: Σp + N. specifying how many arguments takes, Arguments to predicates are called terms; they can be either constants (ground terms) or variables (non-ground terms). An atomic formula, called an atom, for short, is an expression of the form p(42,... (x). where p E Σxp is predicate symbol of arity ar(p) = N and t1. $i,...ty for signature Σ is the set of all atoms that can be formed by terms in D,, i... H = {p(t1, .... tN) p e sp.ar(p) N1, ..., tN E.).3 Subsets of the Herbrand base 1 S H are called interpretations.
Σg Uy,
all terms. The Herbrand base H
Logic Programming. An inference rule an expression of the form bi.... by + h, where bi,..., bk, h are atoms; b1, (1..,bp bx is the body (or premises) and h is the head (or conclusion). For example,
parent [ Y), ancestor (,, Z) + ancestor(
is an inference rule that allows us to conclude that if X is a parent of y and Yis an ancestor of Z, then is ancestor of Z. An inference rule is called range restricted if each variable appearing in the conclusion h also appears in at least one atom by in the premise. For example, p(x) I- q(X) is range restricted, while p(x) H q(x, Y) is not. In this paper, we require all inference rules to be range re- stricted. 6 Inference rules with a null premise, i.e., where K O, and a ground conclusion, i.e., where h E H. are called axioms. A set of axioms is denoted A. For example, F parent( abraham, isaac). also written parent over a signature Σ is set of inference rules in which all atoms formed by symbols in Σ. The following is an example logic program, adapted from Sterling & Shapiro (1994, $5):
parent(abrahan, aabraham, d'saac), omitting the - symbol, is an axiom. A logic program P
parent terah, abraham)
parent(abrohant abbrhamm, ishmaell
parent(abraham, aabraham, isaac)
parent(X, r) F ancestor(x, r) parent(X, X, r), ancestor( Y, 2) T ancestor(I, (x, 2)
*Many logic programming languages, e.g., Prolog (Colmerauer & Roussel, 1993; Körner al., 2022). additionally have the notion function. Constants are then just nullary functions. Our notion of logic programming is most similar to Datalog ( (Vardi, 1982; Maier et al., 1984; Ceri et al., 1989), which does not. In the case that the signature additionally contains set of function symbols 2,, the Herbrand base is defined as the set of atoms that can formed by all terms in the Herbrand universe, which is the smallest set that satisfies the equation = F. U (f, I E E,,, af( = N, f1, ty E U).
'Rngee restriction ensures that applying the fixpoint operator (Eq. (1)) does not create goo-ground atoms.
3

---

Types and Built-ins. Our notion of logic programming additionally includes types (Abiteboul et al., 1995, $21) and built-ins (Kaminski et al., 2017). which we define here. We partition Σ, and Σ, into T disjoint subsets, i.e., Σn 22 ......I.gg LI and Σ, II.. ET respectively, and associate each subset with a type. These subsets are paired index-wise i.e., (E), Σ constant and variable types match. In this paper, we consider three types: (i) natural numbers, denoted (N,, N2), (ii) strings, (A A7), and (iii) sets of strings, (2 2 ). Our introduction of types is neces- sitated by our desire to add additional power to our notion of logic programming that is external the language itself. Specifically, we will introduce built-in predicates. simply called built-ins through the exposition, that add various arithmetic and set-theoretic operations. We enumerate these operations:
(
=: Σイ ), ensuring that the
xz Vz=Zz Zz
(Integer Addition), (Integer Subtraction),
Xza= U U225= = Zza
(Set Union), (Set Intersection).
Xg-Y2 Yz=2z
Xzs+ 0g, Nx20= = Z200
Xzx Yg- - Zz
(Integer Multiplication),
|Zza> | -Xg
(Set Cardinality),
xz=Yzz
(Integer Equality),
Iza- = Yz
(Set Equality),
Xz Yg
(Integer Comparison),
Igg0r XXg
(Set Cardinality Comparison).
The truth value of grounded atoms constructed from built-in predicates is evaluated externally to the logic program. To do so, we define the built-in evaluator eval: H - (T,F}, that maps all ground built-ins that evaluate to true to and all ground built-ins that evaluate to false to Additionally, any element of H that is not a built-in evaluates to F. For example, eval( 4- = T, eval( 6+ 30-+4-10 10) = F. and eval( abraham, isaac)) built-ins in a logic program, we can extend the inference rules from the earlier example to measure the depth of the ancestor relation (e.g., parent, grandparent, greaatgrandpareet etc):
For example, to illustrate the use of
parent Yx-) ancestor Yx=, 1)
parent (Xar, Ya=), ancestor( (Ya-, Z x-+11 Y/2 |- ancestor(Ax: Zar, Yz)
Substitutions and Semantics. To assign semantics to logic program, we require bit more machinery. A substitution 0 is a finite set of pairs {(Xm, m= where Im E Σx. tm E Eg 12 Xm * Xm for all m # m', and Xm & tm for all m (Sterling & Shapiro, 1994, p. 14). Additionally, a typed substitution is a substitution where, if Xm E Et, then lm E E U Et. We can apply a substitution 0 to an atom b, denoted b/0, e.g., parent iisacc/(((x abraham)) = parent (abraham, issaae.. Let (P)) be the set of all typed substitutions under P. We say that b',,..,b%, 6/x + h is instantiation of bi.... bx + h if there exists substitution @ E O(P) such 66x | h²' = b1/0, ..., bx/ /0 H h/0. If an instantiation has no variables, we call a ground instantiation. In addition, we say that an atom b unifies with b' if 30 E O(P): b//0 = 6//0. If b unifies with b/ we write b = V. We define a logic program P's fixpoint operator Tp: 2 + 2 as
that bg....b'%
(1) = 1 (th/ (61...,,xx + 1) E P, AK (ba// E I V (0)). OE ((P)) (1)
where 1 C H is an interpretation. The fixpoint operator Tp is inflationary, i.e., for every interpretation I S H. we have b E -- (I).). and monotone, i.c.. for every pair of interpretations 41, 12 C H, we have 11 us to employ least fixpoint semantics. To that end, we define the minimal Herbrand model as M = MTT;(A) def U (A),, where T denotes the n-fold application of the fixpoint operator Tp, i.e. M is Tp's 's least fixpoint.? Thus, M is the subset of the Herbrand base that is true given the axioms and inference rules in the program; we call elements of M theorems. Due to our inclusion of built-ins that encompass basic arithmetic operations, it is undecidable to compute M (Dantsin et al., 2001), i.e., in general, we cannot decide whether h (A) for an arbitrary h e H.
C
(
That Tp is monotone allows
Queries. Given a logic program P. we are often interested in determining whether there exists a theorem in P that is an instantiation of specific (possibly non-ground) atom. We refer to such atoms as queries.* 8 For example, building on the running example drawn from Sterling & Shapiro (1994, $5), we may wish to ask whether there exists theorem that instantiates the atom ancestor X, ishmmell.
IInflationarity is not needed to prove that the minimal Herbrand model M exists. Indeed, monotonicity and the fact that interpretations of the Herbrand base form a complete lattice suffice to apply Tarski's (1955) theorem, which guarantees the existence of the least fixpoint. However, inflationarity does guarantee that, as we iteratively apply Tr, convergence to the least fixpoint is monotone.
'n principle. queries may also be ground; however, only the non-grov non-ground case is of theoretical interest here. as it extends beyond what can be handled by the machinery introduced so far.

---

contifd),,.oo 3.spple,2)
(on)((())/ 2..gpl.. "a Ius aupks"
"c, b. and together have 25 appless
cont ((a ,b,o),,2,,,p. apple,,
Goal theorem
comp (1m), 1.di,,,,, Appla, 2) not more opples "oon
contifbb), , aapple, "b hos 8 opp os
Query
cont cont(Ic),,,.ol 9.aple,, hos apples"
cont le "b lida apaliss
oon't ([a,b, X. appple. 2) "How many upples do 5, and hove regerhar?
transfer (Ib), fel 22apppe.1)) "e gove 2 Zopples to
Relevant Theorems
Irrelevant Theorems
cont((() 2) "oos
((g) apple, apples"
con't [(h) .1, 19,apple,,2) Th JP aspies
((nt ,3 apple,, "ohos 23 soples
comp (g)), apple, "I has more agoles than
comp (g). apple, in hos more apples
coot ((E) ,19, apple,1) 'I hhss appless
txansfor ((A), (1))),1),44,00 4,4911o.1) 1)
"oooro opplis
Figure I: Example of a proof of a goal theorem for the logic program presented in Table with a shortest proof PP' in blue and irrelevant theorems in red. We propose measuring efficiency as the size the proof [P] relative to the size of the shortest proof [ penalizing the LM's proof for containing irrelevant theorems. We have omitted built-in predicates from this diagram for brevity.
Answering such a query amounts to finding all substitutions for that make the atom provable from P. When X can take on infinitely many instantiations, more sophisticated inference mechanisms most notably, unification (Robinson, 1965)-an are required to perform this kind of non-ground reasoning effectively. In this paper, however, we restrict attention to queries in which each variable is known priori to range over a fixed, finite domain, which allows us to avoid additional complexities.
3.2 Deductive Reasoning
Hypergraphs. A hypergraph 9 (B- (B-hypergraph: Gallo et al., 1993) is a tuple E). where V is
a set of vertices, and E C 2 x V is a set of hyperedges, where a hyperedge = T - 2h2 consists of tail T C V. with T > O, and head Up V. We define the size of hypergraph as |9 del V where 9 = E). A subhypergraph of a hypergraph 9 = (V. E) is hypergraph 9 = (V' E
where V C V and E' S E. Given S C V and E V. an (S,,))-yperppe
in a hypergraph Uh, such that uh,, = and for every j E [J]: T₁ SUU {Uhys-.. --. "a,,,-,,,,, Uh, J.. i.e., each hyperedge's 's tail consists only of nodes that are either in the source set S or are heads of previous hyperedges in the sequence. A hyperpath generalizes the notion of a directed path in a graph. but allows each hyperedge to have multiple tail nodes that jointly produce a head node. Finding the shortest (S, v) -)-hpeerpath in hypergraph is analogous context-free parsing (Klein & Manning, 2001) and can be executed in polynomial time.
9 9= (V, is a finite sequence of distinct hyperedges Ti - UA "h, TT -
Proof Forests, Proofs and Proof Efficiency. Let P be a logic program. A proof forest (F, e) in P is a pair where F (E, V) is a hypergraph and f: V + H where H is P's Herbrand base (Heijltjes, 2010). Additionally, we require that, for every hyperedge e = (t......ta tx] - en. E E, there exists rule (bi,..., (b., bx | h) R and a substitution 0 E ( such that b1/0= E(41), bx /0 = {((x) and h/0 = ((vx). We call a proof forest (F, E) an (A, hig) )-proff if there exists (e- 8
in (F, E). 10 In Fig. 1, we show an example of a proof in which hg c {a, b, c), 25, app 2) in custom logic program for math word problems ($4), together with some axioms in the program that do not contribute to the proof of the goal theorem hg. We call an (A, -prof a shortest proof if has the least number of vertices of all (A, hg) -proofs in discussed in the subsequent paragraph. Now
P. A shortest proof can be found by forward-chainee we turn to measuring proof efficiency. Consider an (A, h,, h-rooo P in P. We define the efficiency of P as EFFICIENCY (P) def |IP I/[P] where |3P*| is the number of vertices the remainder of the paper, we will refer to an axiom a as irrelevant if there does not exist a shortest proof D that contains a vertex U such that {(v)= a.
shortest (A, -proff In
We note that this is non-standard; the size of a hypergraph is more often defined as its number hyperedges or the sum of the cardinalities of its hyperedges (Gallo et al., 1993). We use this definition to sync with the exper- imental setup, which we explain in $5. Future work could easily adapt our efficiency metric to other definitions.
We note that the expression (A, hgghhhghghhh -hyperpptth is a slight abuse of notation in the case that not injective adopted for convenience: A and hy are a subset and an element, respectively, of P's Herbrand base not of Rp's is V. In this context, by A. we refer to a set X C ((A() where {(X) = A, and by h2 we refer to set Y C (hgg where {(Y) lgg
5

---

id
Inference Rule
cont(AA A. his far fg).compp) RA. A.t NNe Fas: Tic), he Ay (ont(RA Prg, Fgg [44]
(bb)
c des 6a [s).comp(P2 (PA da Thi Ear Te). in 2 thi Ru- Iy F cont(AA: AN. E.g TT]
(1c)
cont(AA, Ag. Far R8). cons (5A. 2t,, Ear. Tprl, T42 Ag. Ag AA A.A. Ag,. Fgr.
(2a)
co Ax- Far Ix). transseeee 8... Tn. FAr Re). Iyt In I I- cont
Eg. 91))
(2b)
cont( 4e. P2r transterr LA A.. Ar PA 16). 242 To in fy Tar I= cont(R Ape Sar, 91)
cont(AA, 0x. Far To). co..(4A, 0%gy Fgr Te). 4A, U4A, =. 04, + 0% Phi cont Nr. Far.
for S & K
(4)
cont(AA. As. Far P5)) rate 3p. Exy Far 1y). 4y fp- By+ cont (4 By. Fan. Fn0
(5a)
cont(dA, As. Ear F.). compp(AA CA. Fat. Ty). compouul 9.. CA. Far Is) An cont By. Far. Tu)
(5b)
compleA. AA, Au, Ege. TR.). comp(RA. Ca. Nu. Eae, J1), Au Fy compon RA. Ca. Ea. 7N)
pllA. ....... -transfer(1 RA. Ty. Far. J8), -transfor 4a. ip. Far. 3t). T = By p(Aa. Fax. Rt. for P. E [cont, comp, rate, compon))
Table I: Inference rules in Pw. The symbols cont, comp, transfer, rate, comped are predicates and we use variables A,A. AA CA. CA 2 for agents, Exr, Fx- E E,, for entities, Xn, Yv, Ze E NN for quantities, and IN E N; for timestamps. We refer to Fig. for ground instantiations the atoms shown here with corresponding example verbalizations. The symbol p in Rule (6) is a placcholder for any predicate other than transfer; because the predicates have different arities, we use "..." to denote other arguments that may be present. Rule (6) is special since it has negation (App. A) it is included to treat complications resulting from the timestamp in Rules (2a) and (2b) see footnote 11 and not used when generating shortest proofs for our experiments (App. C).
Forward Chaining. Forward chaining Playes-Roth al., 1983; Poole & Mackworth. 2017) is meta-strategy for theorem proving in logic programming that proceeds from the axioms toward the goal theorem. The process terminates once the goal theorem is proved. Pseudocode for the forward- chaining is given in Alg. 1 in A.2. As a meta-strategy. each instance of forward chaining defines an ordering over proof steps. Different orderings give rise to familiar search algorithms, such as depth- first search (DFS; Tarjan, 1972), breadth- first search (BFS; Moore, 1959), Dijkstra's 's (1959) algorithm, and heuristic-basst search (Pearl, 1984) like A* (Hart al., 1968). While DFS and BFS ignore infor- mation about the goal theorem, such information can guide search more efficiently, as exemplified by goal-aware strategies like Earley's (1970) algorithm for context-free parsing or its more general equiv- alent in logic programming- magic templates (Bancilhon et al., 1986; Ramakrishnan, 1991; Eisner & Blatz, 2007). In the spirit of using top-down information in proof search. in $5, we examine whether LMs make use of lexical overlap with the goal theorem as part of their internal search heuristic.
4 Evaluating Language Models on Grade School Math Word Problems
We are interested in reasoning that takes places in natural language, particularly performed by LMs. To this end, we consider grade school math (GSM) word problems as empirical test domain. Such problems are commonly used for training and evaluating LMs on reasoning tasks (Cobbe et al., 2021; Patel et al., 2021). In $4.1, we introduce a family of logic programs, using the technical notions intro- duced in $3, that correspond to natural class of such math word problems. We also describe simple manner to convert text generated by an LM to a proof in such logic programs in $4.2. Finally, in $4.3 we explain how we generate problem descriptions in natural language that contain irrelevant axioms.
4.1 Modeling Math Word Problems with Verbalized Logic Programs
Logic Programming for Grade School Math Word Problems. We consider a particular family of logic programs to represent GSM problems, adapted from Opedal et al. (2023, 2025). All of the logic programs have the signature Σ = (IW M ) The set of predicate symbols M = {cont, comp, transfer, rate, compeq) corresponds to arithmetic concepts that occur in GSM word problems (Riley et al., 1983), e.g., cont for denoting how many entities an agent contains, comp for comparing the number of entities across multiple agents, or transfer for expressing one agent transfering entities to another. We partition WW 24 L E. Li Ng U UN; and ΣΦ = 2 U Er U' L U into the following pairs: sets of strings (2 24) called sets of agents (who possesses), strings (Ea, Ex) called entities (what is possessed), natural numbers (Ng. g, N2) called quantities (how much is possessed), and natural numbers (Ng, N)) called timestamps (time of possession). We note that 2 is a power set of the set of agent strings Ag. which enables us to code a state where multiple agents possess the same entity jointly. The family of logic programs all share the same inference rules, which are given in Table 1. Fig. 1 shows an example proof using these inference rules, omitting built-ins. We note that possession may change over time and is governed by the transfer predicate in Rule (2)." "I
"Teee time component requires the addition of Rule (6), which expresses that all theorems with time Tx that are not affected by a proof step using Rule (2) maintain their truth value at Is+ 1. This is an instance of the

---

Axioms. The rules given in Table I are held constant across all logic programs in our family. Indeed, what distinguishes one program from another, then, the choice of axioms. For example, consider the axiom cont( (ryan), 5, cat, 2) which expresses that "Ryan has 5 cats at time step 2": the predicate cont. represents the semanties of possession, and (ryan) E 24 cat E Egg, and 2 E N2 are all ground atoms of different types. Additionally, we only consider axiom sets Aw C H that have the following property: We call an interpretation I S H of a logic program in our family (Table 1) numerically consistent if there do not exist two substitutions 0 = [(AA, La); (Xz, 1), (Exr, Le), (Tee,4) and 0' = [{(AA,a)) (Xz, L'), (Esr, Le), ( (5) such that t * l' and both cont (AA: Xy, Exr; O0) (4., IN; Exr; Tx)/0' E T (T). This ensures that the minimal Herbrand model does not contain contradietory pairs such as cont (ryan), 5, cat, 2) and cont( fryan), 4, cat, 2). For example, the following set of axioms is numerically consistent: Aw = {cont( (ryan), 5, cat, 2), compl (fleenor), (ryan), 3, cat, 2)}, expressing that "Ryan has 5 cctts" and that "Eleanor has 3 more cats than Ryan". If we were to, e.g., include the two axioms {cont( (andreas), 7, cat, 2), comp( fe leaaor)) (andreas), 3, cat, 2)}. we would obtain numerically inconsistent axiom set. Inference in our family of logic programs is decidable under numerically consistent axiom sets. See App. B for details.
E Ny,
4.2 Language Modeling and Proofs in Natural Language
Language Modeling, We give brief formal introduction to language modeling. Let I be an alphabet of tokens and I be the set of all strings over r, its Kleene closure. We write w E I for a string, w, for the token at the ht position in w = Ww ... WT, and |w| = T for the number of tokens in un i.e., its length. language model (LM) p is a probability distribution on r. Let EOS & r be distinguished symbol denoting the end of a token string. The probability of a string w can be written autoregressively as p(w) 7 (EOS w) [1 7
w<:)., where 7. c) is probability distribution over r def T [FOS) conditioned on the context c E T
Verbalized Logic Programs. To bridge reasoning in formal proof systems to rea- soning in natural language, we
introduce the idea of verbalized logic program.
Given a logic program P with nega- tion (App. A.1), let H be its extended Herbrand base We associate each atom E H with a set of natural lan- guage strings. To that end, we define a verbalizer up: H - 2T,,, where each up (b) is a disjoint set. For every b E H, the set ub) represents the various ways in which the meaning of b can be expressed in natural language. In this paper, we take straightfor- ward approach. For each b E H, we construct finite set G2 C l" Moreover, we enforce disjointness, i.e., Gb, nG., = Ø for and that, for all b E H, each string in G, ends in a distinguished separator symbol-in our case period " that appears nowhere else in the string. These assumptions allow for trivial lincar-time parsing of natural language text into a sequence of atoms in the verbalized logic programs. In practice, we generate the strings in each G2 with a series of wand-written templates. We give examples in Fig. 2.
Grounded Atom
Verhalization
cont( (anticce))) 3, appte, 1)
"Alice has 3 apples."
cout( falice, bob), 8, f) comp( (( bob), (alice). 2, apple, f)
"Alice and have apples combined."
"Bob has 2 more upples than Alice."
transfor(( (alice). (bob), 2, apple, f)
"Bob gave 2 apples Abice."
rato((alice), 4. basket, apple. f)
"Each of Alice's 's baskets comtains apples."
3+2=5
Not verbalized
Figure 2: Examples of verbalized grounded atoms, i.c., elements of VPw (b) for some b E H. Built-ins are not verbalized other than as part of the conclusion; App. D.2 shows how this was done in our prompt. We additionally note that time is not verbalized directly but implicitly through the use a past form depending on context.
bi, b2 E H,
4.3 Generating Problems with Irrelevant Axioms
Sampling Axiom Sets. We introduce simple sampling algorithm, presented and analyzed in App. C. that samples a ground goal theorem h2 = (A Xy, Ex,, Tx) and a shortest proof of hg under the rules Rw from Table 1. By construction, the axioms Aw in the shortest proof are numerically consistent (64.1) ) and all axioms in Aw will be used in the proof of hy in the program
Pw = Rw L Aw; we denote this dependency by Aw (hy). 12 That is, Aw (hg) contains no irrelevant
frame problem (McCarthy& & Hayes, 1969; Sandewall, 1972; Hanks & McDermott, 1987). To express this rule, we introduce negation into the logic program; see App. A. for background on negation in logic programming. The only negated predicate in Table is -transfer; because -transfer only appears in the body of an inference rule, the program is trivially stratified (App. A.I). That is -transfer atoms can not be proved true, but we assume -transfer atoms if the corresponding transfer atom is not known to he true from the axioms.
(hg)) is the unique smallest set of axioms (Lemma 1) needed prove hgg justifying the function notation.
7

---

w/ Axiom
w/ Tree
w/ Multiple Trees
Model
Irrelevant
Control
Irrelevant
Control
Irrelevant
Control
Llama-3.1-
65.0
60.8
54.0
52.6
58.6
41.0
52.4
8B
(- 4.1)
(-2.2, 2.1)
(-4.4, 1.3)
(-2.2, 2.2)
(-4.4,44 4.2)
(-2.2, 2.2)
(-1.4, 1.3)
Qwen2.5.
$2.8
43.4
48.4
35.6
40.2
23.5
30.6
Math-7B
(-4. 4.34
(-2.2,
(-4.4,4.0)
2-2.1,
(-4.2,4.4)
(-1.8, 1.9)
(-3.9, 4.2)
63.4
62.2
76.2
58.7
72.2
50.1
65.4
QwQ-32B
(- 1.3, 4.1)
2.11,
(-3.9, 3.5)
2-11
(-7.1,3.7)
(-2.2, 2.2)
(-4.3, 4.0)
DeepSeek-
98.2
98.4
98.0
98.6
97.6
(-1.1,0.4)
(-0.7.0.5)
(-1.5,0.8) 0.8)
(-1.1,0.9)
(-0.8,0.6)
(-1.1,0.9)
(-1.5,0.7)
Table 2: Average answer accuracy (%) with 95% confidence interval (CI) for hase problems augmented with different degrees of irrelevance (one irrelevant axiom, one irrelevant tree, and multiple irrelevant trees; $4.3). The control problems are of the same length as the corresponding problems that have irrelevant axioms, with the difference being that all axioms are relevant. The CIs are Wilson (1927) score intervals. Note that adding irrelevant axioms degrades performance across all models.
axioms. However, to produce logic programs that do contain irrelevant axioms, we do the following. We sample an additional M distinet distractor theorems (hm M m=1- For each distractor theorem hm- we again apply our axiom sampling procedure to generate distractor axioms Am (hmm). Importantly, we are able to show that Aw(hg) remain on shortest proof of hig even in the case that we consider the augmented logic program Pw Rw LI Aw (h.)) LJ Āι (I.) LI Aas (har): see App. C.4.
Structural Overlap. In experiments, we vary the size of the irrelevant axiom sets Ā = Ā (T(T)) A (has) follows: (i) single irrelevant axiom (w/ axiom). where M = [ (h,) = 1, and A, (hg) } (i.e., the distractor theorem is trivial); (ii) a single irrelevant tree (w/ tree), where M 1. A1 (h1) > 1, and hy has a non-trivial proof: (iii) multiple irrelevant trees (w/ multiple trees), where we set M 3. |Am (hm)) > for m (1,2,3). and h1, f2 ha all have non-trivial proofs.
Agent and Entity Overlap. We additionally control for overlap between the set of agents, i.e., elements of 22 and the entities, i.e., elements of E., of the goal theorem hy (A Xx, Es,, Ts). and those present in A. Intuitively, for a query asking how many telescopes "Bernhard" has, we should make use of the information in "telescope" and "Bernhard" when deciding whether to take a certain deduction step. By constructing irrelevant axioms that also mention "telescope" " and/or "Bernhard", it becomes harder to distinguish what is relevant and what is not. We distinguish four cases: (i) neither the set of agents nor the entity occur in À (no overlap), (ii) the agent does not occur in Ā but the entity does (entity overlap), (iii) the entity does not occur in Ā but the set of agents does (agent overlap), and (iv) entity overlap in which the agents occurring in Ā have lexical overlap with the set of agents (agent and entity overlap), e.g., if bernhard is in hg then À contains agents like bernhard' ss_ student or bernhard's s__ son. Entities that do not overlap are always made topically related, e.g., if Aw contains axioms with telescope, then À may contain dinocular.
5 Experiments
We use proofs generated from the family of verbalized logic programs introduced in $4 to help un- derstand how LMs reason about GSM problems. Our primary experimental manipulative is irrelevant axioms with respect LMS fare in the face of irrelevant axioms. We generate 500 problems with varying structural, agent and entity overlap, as discussed above. See App. D. for more details on the make-up of the dataset. We refer to the problems without any irrelevant axioms as base problems. We additionally generate control problems that have the same number of axioms as the problems with irrelevant axioms, except that all axioms are relevant. Their shortest proofs contain the base problem's 's shortest proof as a subproof. This controls for the possible confounder of problem length (see, e.g., Leeb et al., 2025). We consider both non- non-ground queries, corresponding to questions like "How many drones does Yanick have?" " 13 and ground queries, corresponding to questions like "Show that Yanick has 5 drones." "
goal theorem introduced into logic program, which allows to analyze how
AAssummng numerical consistency ensures there exists at most one ground atom in the minimal Herbrand model that unifies with the non gonnggound query. This ensures that forward chaining would halt in finite time.
8

---

Qwom25-Matl-The
QwQ-32R
DeepSel-RRI
00055
model
0.015
annotated tokens
Denityy
0004
0001
0001
0000
2006 1000
4000
1000
1000
.000
1000
2000
1000
1000
1000
1000
Number tolens
Number tokenss
Number tolcens
Numsher of tokens
Figure 3: Number of tokens in the natural language annotation of the shortest proof as compared to model outputs for problems with three irrelevant trees (Á, u Az L Az). The plot includes problems for which the model gave the correct final answer; this is why the density for annotated tokens differs between the models. We observe that LMs often use more tokens than necessary.
Language Models. We use one "vanilla" LM and three reasoning LMs in our experiments: 1-ama-3.1-BB-Instiii (Llama Team, 2024), Bwenn.5-Matth77--nnntee (Yang et al., 2024). Qwen's reasoning model QwQ-32B, and DeepSeek-RI (DeepSeek-Al, 2025). We generate strings using ancestral sampling, restricting the context length to 4000 tokens.
Prompting. Our experimental design is based on in-context learning (Brown et al., 2020). Specifically, we use five fixed in-context examples of shortest proofs to expose the LM to proofs in our verbalized logic programs. The verbalized proofs are ordered under a DFS traversal of the theorems in the proof, such that the axioms are popped in the same order they occur the verbalized text. See App. D.2 for the prompt.
5.1 Addition of Irrelevant Axioms and Answer Accuracy
We begin by analyzing how irrelevant axioms influence LM's ability generate the correct goal theorem for non-ground queries. We employ the two-step prompting strategy given by Kojima et al. (2022). In the first step, the model is prompted to produce natural- satural-language proof outlining its reason- ing process. This natural-language process is then mapped to a proof in the verbalized logic program. In the second step, we prompted the LM second condiionnit on the proof generated-to produce the goal theorem. In Table 2, we report model accuracy in generating the correct goal theorem. We observe that even single irrelevant axiom reduces model performance, particularly for Llama-3.1 and Qwen2.5. Performance degrades further as additional irrelevant axioms are introduced. The performance the most capable model, DeepSeck-R1, is nearly saturated at perfect accuracy, though slight decreases are still observed when irrelevant axioms are included. Across models, accuracy on problems containing irrelevant axioms is almost always lower than on the corresponding control exam- ples, suggesting that irrelevance has a substantial effect on accuracy beyond what can be explained by longer problem statements. The only exception is Llama-3.1, whose performance on problems with one irrelevant axiom exceeds that of the corresponding control. QwQ-32B stands out an outlier: for this model, performance on the control problems is significantly higher than on the original base problems. In Fig. 7 (App. D.4), we present results stratified by agent and entity overlap ($4.3). A consistent pattern emerges: such overlap between the goal and irrelevant axioms makes solving the problem more difficult. Compared to no overlap, performance drops with both kinds of overlap, sug- gesting both serve as heuristics during search. While drops are typically larger for agent overlap than for entity overlap, note that this could be partially due to the entities being topically related ($4.3). In the following subsection, we analyze the proofs in greater detail to further illuminate these effects.
5.2 Addition of Irrelevant Axioms and Efficiency
In Fig. we plot the empirical distribution over the number of tokens in the model's output and com- pare the number of tokens in the natural language annotation of the shortest proof, taking only the proofs that concluded at the correct goal theorem. This analysis, as well as those in the remainder of this section, are done on the problems with multiple irrelevant trees (i.e.. the kind of structural overlap with the most axioms; $4.3). We observe that all models often use more tokens than are in the annota- tions, suggesting that they use more compute than necessary to prove goal theorems. This is consistent with findings on reasoning models ($2), but holds also for the Llama model. However, these results do not confirm that the models generate irrelevant theorems- they might just be more verbose than our annotations. This leads us into our efficiency analysis in line with the technical exposition in $3.2.

---

Non-ground Queries
Ground Queries
None
Entily
Agent
Both
None
Entity
Agent
Both
Efficiency
60.2
43.5
47.5
34.0
45.3
34.9
29.9
23.6
Llama-
Exact matches
15
3
4
0
11
11
3,1-8B
Efficiency (non-axioms)
71.8
50.3
63.0
44.2
57.6
41.3
42.9
37.1
Correct Theorems
84.5
82.9
86.0
85.4
76.0
77.8
72.1
69.8
Efficiency
43.7
32.4
34.4
31.1
36.8
30,6
29.3
25.3
Qwen2.5.
Exact matches
8
0
1
0
10
2
1
Math
Efficiency (non-axioms)
57.3
40.1
51.5
16.2
50.5
38.1
41.1
36.0
Correct Theorems
75.1
73.7
74.3
73.6
62.5
63.4
57.4
56.6
Table 3: We report efficiency, number of exact matches (out of 500), and efficiency restricted to non-axioms between the theorems parsed from the output generated by LMs and the shortest, most-efficient proof. Results are stratified by type of query and type of overlap between agents and entities present the query and the irrelevant axioms. The numbers are computed based on the problems for which the model got the correct final answer. The low efficiency scores show that LMs often produce irrelevant theorems when successfully proving goal theorem. The differences in efficiency scores across datasets of different overlaps are significant (p < 0.001) according mne-way ANOVA analyses. Lastly, "Correct Theorems" shows the proportion of the theorems in the shortest proof that the LM predicted.
Efficiency Evaluation. This analysis performed for Llama-3. 1-8-tnnttttt and Qwen2.5 5-Math- BB-Instruct since only those models followed the required formatting ($4.2)); however. we perform a more crude analysis based on only the arithmetic expressions for the other two models in App. D.4. We report the efficiency metric presented in $3.2 for the problems where the LM generated the correct goal theorem, comparing against the shortest proof generated with our method (App. C). 15 We omit built-ins from the efficiency analysis since those are not verbalized. Additionally, we note that it might be the case that all irrelevant steps the models take are axioms; the LMs may simply be stating that some axioms are irrelevant to the query. We therefore also consider a metric in which only non-axiom theorems are counted. App. D.4 we provide an additional analysis on search order.
Efficiency for Non-ground Queries. The main results are shown in 55.2 (non- mion-ground queries), with scores stratified by agent and entity overlap. The efficiency scores are far from 100%, meaning that the models predict several theorems beyond the required ones present in the shortest proof. Additionally, observe that the efficiency scores vary significantly across the type of overlap (p < 0.001), conclude that lexical information in the query has a substantial effect on proof planning. We finally comment on the results that only consider non-axioms, presented the last row in $5.2. We again observe efficiency scores that are considerably below 100%, showing that the LMs prove theorems that are irrelevant to the query. App. D.3 gives an example where Llama-3. 1-BB proves irrelevant theorems.
Comparison to Ground Queries. We compare the performance to the same problems when presented with ground queries. Queries tend to be non-ground in the GSM domain (Riley et al., 1983; Cobbe et al., 2021). Since LMs are heavily influenced by training data, we therefore expect them to perform better on non-ground queries. Our results on the same verbalized logic programs as before, but with ground queries, are presented on the right-hand side of $5.2. We observe lower efficiency scores, suggesting that LMs are indeed worse at proving ground theorems in this domain.
6 Conclusion
This paper provided a framework based on logic programming for studying deductive reasoning in language models, with a particular emphasis on efficiency. This framework enables us to disentangle efficiency due to generating irrelevant theorems from efficiency due to verbose natural language verbal- izations of those theorems. We applied this framework to empirically investigate how language models perform reasoning on math word problems that have many irrelevant axioms. We found that introduc- ing irrelevant axioms into reasoning problems leads to significantly lower answer accuracies for most models-ewe when controlling for problem length- and proofs that exhibit frequent detours through irrelevant theorems. Our work highlights the need to improve models in terms of reasoning efficiency, as well as the advantages to viewing deductive reasoning through the lens of logic programming.
Wee manually verified parsing accuracy on the theorems generated by the models for a subset of 20 randomly sampled examples. An additional class representing that there is match with any annotated theorem in the proof included as well. The parser predicted the correct (or correctly predicted no) match in 394/397 99.2% of the theorems for 3.ama-3.1 1-1.3..-------- Ins-truttt and 381 381/38t /384 = 99.2% the thcorems for Qwen2.5-Math- BB-h777--tsttt
LMS often generated the same theorems multiple times. We chose ignore such duplicates in the evaluation.
10

---

Acknowledgments and Disclosure of Funding
We thank Juan Luis Gastaldi for useful discussion and criticisms. Andreas Opedal acknowledges funding from the Max Planck ETH Center for Learning Systems.
References
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases: The Logical Level. Addison- Longman Publishing Co., Inc., USA, 1st edition, 1995, ISBN 0201537710. URL https://dl acm. org/ toi/10.../ 005///11.5555551111 5555/551350.
Ujjwala Anantheswaran, Himanshu Gupta, Kevin Scaria, Shreyas Verma, Chitta Baral, and Swaroop Mishra. Cutting through the noise: Boosting LLM performance on math word problems. In Proceedings of the ICLR 2025 Workshop on Reasoning and Planning for Large Language Models, 2025. URL https: /ttp///pppeeeeeeeeeeeeeeee www.teetuuuneeeee iitrrmmmiidV//PPiiiiii
Daman Arora and Andrea Zanette. Training language models to reason efficiently. In Proceedings of the ICML Workshop ES- FoMo IlI: 3rd Workshop on Efficient Systems Foundation Models, 2025. URL htw.::tpp///// https:://pperreiieee wwt.:ee//ffe.ee nett/forum?id-tCUGSSS.
François Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. Proceedings of the 5th ACM SICACT-SIGMOD Symposium on Principles of Database Systems (PODS), pp. 1-15, 1986. URL https://doi. org/10. /1144//612..15
Gregor Betz, Christian Voigt, and Kyle Richardson. Critical thinking for language models. In Sina Zarrieß, Johan Bos, Rik van Noord, and Lasha Abzianidze (eds.). Proceedings of the 14th International Conference on Computational Semantics (/WCS), pp. 63-75, Gronin gen, The Netherlands (online), June 2021. Association for Computational Linguistics. URL atttss//accanntooloe org 202g/ www.scs../....
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Hossbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33. pp. 1877-1901, 2020. URL httptttt/////cocddeeiiii / http::/aeeeeeapppe////////////// c0dd0 htt.:///0..0.44AA111111/1..A2222 Pdf.
neurips.
Stefano Ceri, Georg Gottlob, and Letizia Tanca. What you always wanted to know about Datalog (and never dared ask). IEEE Tramsactions on Knowledge and Data Engingeering. 1(1):146-166. March 1989. URL https://doi. wwt.////////// 1ttg//....///.9.99.11 43410.
Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang, Rui Wang, Zhaopeng Tu, Haitao Mi, and Dong Yu. Do NOT think that much for 2+3=? On the overthinking of long reasoning models. In Forty-second International Conference on Machine Learning, 2025. URL httpttt//ppperreiiiee net/forum? id=MSbU3L7V00.
Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers soft reasoners over language. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAF'2,, 2021. ISBN 9780999241165. URL https: //dl. acm. acm.org////................oo ort//oii////oooooooooooooooooooo do// /abi//////// / 100. 5555/ 3491440. 3491977.
3491440.3491977.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. URL htttps://aaxiiis org/ abs /2100.210..2 14168.
Alain Colmerauer and Philippe Roussel. The birth Prolog. SIGPIAN Not, 28(3):3755, March 1993. doi: 10. 0015/155360.153366 URL https://doi. org/ atg/10.11 1145/ 155360.63.0 155362.
11

---

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374 425, 2001. URL https: //doi.org//aiii... 1ee.11115550000 0000//0000077.88800.. 502810.
Leonardo de Moura and Sebastian Ullrich. The lean 4 theorem prover and programming lan- guage. In Automated Deduction CADE 28, volume 12699 of Lecture Notes in Computer Sci- ence, pp. 625-635. Springer, 2021. URL https://linn springer... com/ chapter/10.1007/ 978-3-030 79876-5_38
DeepSeck-Al. DeepSeek-RI:
Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprini arXiv:2501.12945. 2025. URL httts:///axii: herrg/aba22001.. 12948.
Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1
(1):269 11,, 1959. URL https:///oi...... /tL.:ttpes///oo..or//0000//////2 1ttp:///000.00///8133333300
Jay Farley. An efficient context-free parsing algorithm. Communicationn of the ACM, 13(2):94 1970. doi: 10. 1.11144//798003580000 URL https:t////o.oi http://iii.rgo/...1111..1 wttpg//....1/33200000000 .62.23 362035.
Jason Eisner and John Blatz. Program transformations for optimization of parsing algorithms and other weighted logic programs. In Proceedings of the Conference Formal Grammar, 2007.
URL http://cs. juu.edu// htap:jjjannnappppa hapappassteisneeeeeeer http:/eeiieeerbreeeeeeee b1a7z-2007.
Emily First, Markus N. Rabe, Talia Ringer, and Yuriy Brun. Baldur: Whole-proof generation and repair with large language models. In Proceedings of the 3 ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ESEC/FSE 2023, pp. 1229-1241, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400703270. doi: 10.1145/361 16433361666 URL httpp://dot org/10. 10. 1114/36111114.. 3616243.
Simon Frieder, Luca Pinchetti, Chevalier Chevalier, Ryan-Rhys Griffiths, Tommaso Salvatori, Thomas Lukasiewicz, Philipp Petersen, and Julius Berner. Mathematical capabilities of Chat- GPT. In A. Oh, T. Naumann, Globerson, Saenko, M. Hardt, and S. Levine (eds.), Ad- vances in Neural Information
ciates, Inc., 2023. URL Processing Systems, volume 36, pp. 27699-27744, Curran Asso- http://perppppppppppppaea//////p files//apee//////3// ftae5558862255666aa333rccccrrre2
Giorgio Gallo, Giustino Longo, Stefano Pallottino, and Sang Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics, 12(2): 1993. ISSN 0166-218X. doi: https://
0oo.oo//00.006600066288888999999 art.icle/pp1/001622281999955
URL hwtps:ttp/::/t: reeteeed.......ieeenerree...... wwt.e/eeeettttccooeeeeeeeeeeeeee conmsciennee/
Kanishk Gandhi. Dorsa Sadigh, and Noah Goodman. Strategic reasoning with language models. In NeurlPS 2023 Foundation Models for Decision Making Workshop, 2023, URL https:// openreview net/ wowoorrimmmmuuueeee
Kanishk Gandhi, Denise H Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah Goodman. Stream of search (SoS): Learning to search language. First Conference on Language Modeling, 2024. URL https: /ttp///eeeeeeeeeeee/ee/eeeeeeeee mett/forumiid=2coppjiee
Nicolas Gontier, Koustuv Sinha. Siva Reddy, and Chris Pal. Mcasuring systematic generalization in neural proof generation with transformers. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 22231-22242. Curran Associates, Inc., 2020. URL http:ttc////roceeddingg neurips. cc/ pdf.
paper
Christoph Haase. A survival guide to Presburger arithmetic. ACM SIGLOG News, 5(4):4221, 2018. URL https: //11. acm. org/ otg//oi//a /doi/10. 1145/3242963... (t55/3322295333222666623 A concise tutorial overview on decision procedures and complexity of Presburger arithmetic.
Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng. Yujie Qiao, Luke Benson, Lucy Sun, Alexander Wardle-Solano, Hannah Szabó, Ekaterina Zubova, Matthew Burtell, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Alexander Fabbri, Wojciech Maciej
12

---

Kryscinski, Semih Yavuz, Ye Liu, Xi Victoria Lin, Shafiq Joty, Yingbo Zhou, Caiming Xiong, Rex Ying, Arman Cohan, and Dragomir Radev. FOLIO: Natural language reasoning with first-order logic. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 22017-22031, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10. 18 2024.emnlp- mainn. 1229. URL https: : / aclanthoonntooy org/2024. 2024. emnlp-maiiee ma...mn2n/.............
Tingxu Han, Zhenting Wang, Chunrong Fang, Shiyu Zhao, Shiqing Ma, and Zhenyu Chen. bokee-budget-aware LLM reasoning. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Findings of the Association for Computational Lin- guistics: ACL 2025, pp. 24842-24855 Vienna, Austria, July 2025. Association for Compu- tational Linguistics. ISBN 979- 779-8-89176-2566 doi: 10.18653/v1/2025 http:///12222...1nnn-1o-aa 127.1 URL https://accaanthologg.. .rg. org/2025. findings-acll. act.94///
Steve Hanks and Drew McDermott. Nonmonotonic logic and temporal projection. Artifi- cial Intelligence, 33(3):379-412, 1987. ISSN 0004-3702. doi: https://oii.or//11. 1016/ http://www..iiieeeeeeeetttt wwwc htt/:/iiennc/arriee/ppp..
N004-37702087990043-99 URL 0004370287900439.
Peter E. Hart, Nils Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE Transactions Systems Science and Cybernetics, 4(2): 120:100-107, 1968. doi: 10. N0.1109/TSSC.196... 19011660......... URL hattps://dot org/10 10. 1109/TSSC. 1968. 300136.
Frederick Roth,-Roth, Donald A. Waterman, and Douglas B. Lenat. Building expert systems. Addison- Wesley Longman Publishing Co., Inc., 1983. URL https: ort/oogg///ooo 11090........ 1985. 13159.
Willem Heijltjes. Classical proof forestry. Annals of Pure and Applied Logic, 161(11):1346-336, 2010. ISSN 0168-0072. doi: http://lo..og///..o00////aaa0200 URL hatpps:/ww/ sciencedirect. httpa////rrraeee////////00/00000 Special Issue: Classical Logic and Computation (2008).
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Representations, 2021. URL https:t///// httpa/:///pppeeeeeeeeeeeeee net/ffrum? wtt.edKKBjmma0.
Mark Kaminski, Bernardo Cuenca Grau, Egor V. Kostylev, Boris Motik, and Ian Horrocks. Founda- tions of declarative data analysis using limit Datalog programs. In Proceedings of the 26th Interna- fional Joint Conference on Artificial Intelligence, IJCAI'17, pp. 1 1123-1130, AAAI Press, 2017. ISBN 9780999241 103. URL https: / /w/p///wwww/ ijcai. org/ pwtp///rocennn....///////. 2217/0155 0156..df.................f...111
Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. LAMBADA: Backward chaining for automated reasoning in natural language. In Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Lingwistics (Volume 1: Long Papers), pp. 6547-6568, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 10.18653/v1/200 10t.5////12222..o 1/20:/0.../2.....ooogg..... lon-..g.336. URL https: hatp///cacanoooogyoooooooo org/2022 acl cong.ong..o 361/
Dan Klein and Christopher D. Manning. Parsing and hypergraphs. In Proceedings of the Seventh International Workshop on Parsing Technologies, pp. 123-134, Beijing, China, October 2001.
URL https: httpee://aaaaatta hatp//accaantoooo....ooo org/W01-18111
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwa- sawa. Large language models are zero-shot reasoners. In S. Koyejo, S. Mo- hamed, Agarwal, D. Belgrave. K. Cho, and A. Oh (eds.). Advances in Neu- Curran Associates,
ral Information Processing Systems, volume 35. pp. 22199-22211 Inc.. 2022. URL https://proceedinn newrips.........r... cc/paper.......e.epppe ppapr_files] sll.ffllesppppeee httpe///pppr//0///11ee. 8bb0d291acdes 1abo0229lacdaaff06661112222881
Confereeceeee pdf.
Robert Kowalski. Predicate logic as programming language. IFIP congress, volume 74, pp- 569-544, 1974. URL httph:://///t httpps:///www.eee doc. ic. ac. ac.uk/""....... wtt.aaa..aaaaaapapsssaaa///// Tatk/ppprrs//FPP/2777,,, pdf.
13

---

Keito Kudo, Yoichi Aoki, Tatsuki Kuribayashi, Shusaku Sone, Masaya Taniguchi, Ana Brassard, Keisuke Sakaguchi, and Kentaro Inui. Think-to-talk or talk-to- thinkk? When LLMs come up with an answer in step reasoning. arXiv preprint arXiv:2412.0111 2024. URL https: //arxiv..o www.vv...ggaooooo httggabb/2412....
Philipp Körner, Michael Leuschel, João Barbosa, Vitor Santos Costa, Veronica Dahl, Manuel V. Hermenegildo, Jose F. Morales, Jan Wielemaker, Daniel Diaz, Salvador Abreu, and Giovanni. Ciatto. Fifty years of Prolog and beyond. Theory and Practice of Logic Programming, 22(6):
776-858, 2022. URL https:://// http:////.....00...0000777772220 10011007//111108422000222
Felix Leeb, Zhijing Jin, and Bernhard Schölkopf. Causality systematically address the monsters under the benchsmarks). arXiv preprint arXiv:2502.05085, 2025. URL hhttps:://art org/
abs/2502. 05085.
Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mcyay, Michael Rabbat, and Yuandong Tian. Beyond * Better planning with transformers via search dynamics bootstrapping. In First Conference on Language Modeling, 2024. URL SE=SGoVICCoOf.
Belinda Z. Li, Been Kim, and Zi Wang. QuestBench: Can LLMs ask the right question to acquire information in reasoning tasks? arXiv preprint arXiv:2503.22674 2025. URL https: /tttps://ariv.. arxiv. org/abs/2500 22674.
Qintong Li, Leyang Cui, Xueliang Zhao, Lingpeng Kong, and Wei Bi. GSM-plus: A comprehensive benchmark for evaluating the robustness of LLMs mathematical problem solvers In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (cds.), Proceedings of the 62nd Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.18653/v1/2024. acl-long. 163. URL https: htcp//acclaaaa aclooolllo org/ 2024. acl- 163/.
Bangkok,
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024. URL forum?2d==x8L.00N6E00
net/
Llama Team. The llama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024. URL https: //arxiv. org/ abs///40 21783.
Haotian Luo, Li Shen, Haiying He. Yibo Wang, Shiwei Liu, Wei Li, Naiqiang Tan, Xiaochun Cao, and Dacheng Tao. O1-pruner: Length-harmonizing fine-tuning for ol-like reasoning pruning. In 2nd AI for Math Workshop @ ICML 2025, 2025. URL https: httpps://opeeeee /pwp/eeveeeeeeeee////ee/ee nww/forummic.... ioYybCReyW.
Qing Lyu. Shreya Havaldar, Adam Stein, Li Zhang. Delip Rao, Eric Wong, Marianna Apidianaki. and Chris Bellison-Burchh Faithful chain-of of-thought reasoming. In Jong C. Park, Yuki Arase, Baotian Hu, Wei Lu, Derry Wijaya, Ayu Purwarianti. and Adila Alfa Krisnadhi (eds.), Proceedings of the 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Chapter of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 305-329, Nusa Dua, Bali, November 2023. Association for Computational Linguistics. doi: 10. 20. URL https: /all haa///llalltttt anthology org. 222g/2223..00 ij jecnpmmainn 20/.
Xinyin Ma. Guangnian Wan, Runpeng Yu, Gongfan Fang, and Xinchao Wang. -oT-valve: Length- compressible chain-of-thought tuning. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pp. 6025 6025-6035, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-88 1916--55--00 doi: 10.18653/v1/2025 acl-long.300 URL https://accaattholgg.
org 2025 acl- 1an1-loog.3000 300/.
David Maier, Jeffrey D. Ullman, and Moshe Y. Vardi. On the foundations of the universal relation model. ACM Trans. Database Syst., 92))2833338 June 1984. ISSN 0362-5915. doi: 10. 145/329. 318580. URL https: /ttps://doi.. org/ 10. (1.//////...18888//
14

---

John McCarthy and Patrick Hayes. Some philosophical problems from the standpoint of artificial intelligence. In Meltzer and Donald Michie (eds.), Machine Intelligence 4, pp. 463-502.
Edinburgh University Press, 1969. URL. htt.:httpp:/hhhie wptpspppppee.oorrreeeeee/eeeeeee
Seyed Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar: GSM-symbolic: Understanding the limitations of mathematical reasoning in large language models. In The Thirteenth International Conference Learning Representations, 2025. URL https: / //ppnreeeeeeeeeeee/eeeeeeeeeeeee pet//forum?.d=AAjAAZZy
Edward F. Moore.
The shortest path through maze. Proceedings of an International Symposium on the Theory of Switching, pp. 285-292, 1959. URL settps//bboole woweelgooooo..o.... ch/bookssidd IVZBHAAACAAJ.
Terufumi Morishita, Gaku Morio, Atsuki Yamaguchi, and Yasuhiro Sogawa. Learning deductive reasoning from synthetic corpus based on formal logic. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt. Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 25254-25274. PMLR, 23-29 Jul 2023. URL https: //tps/////occ..........m mlr. httpss///222/mmmosssitaeea
html.
Niklas Muennighoff, Zitong Yang. Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candes, and Tatsunori Hashimoto. sl: Simple test-time scaling. In Workshop Reasoning and Planming for Large Language Models, 2025. URL https://openreviice wwwprreiiiiinneeefeoeeeeeeeeeeee hett///orumm.dd...Hovrr...
Minh- Vuong Nguyen, Linhao Luo, Fatemeh Shiri, Dinh Phung, Yuan-Fang Li, Thuy-Trang Vu, and Gholamreza Haffari. Direct evaluation of chain-of-thouue knowledge graphs. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguistics: ACL 2024, pp. 2862-2883, Bangkok, Thailand, August 2024. Association for Computational Linguistics. URL https :/aa://aallla htt////aaaaaaloooeee org/2024. findings acl. 168/.
in multi-hop reasoning with
Andreas Opedal, Niklas Stoehr, Abulhair Saparov, and Mrinmaya Sachan. World models for math story problems. In Anna Rogers, Jordan Boyd-Graber, Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics; ACL 2023, pp. 9088-911 1888-1155, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 18653/v1/2023 18033//n/ acI.579. URL https: aaath/oooay 2r23/223..22 aindings-ac1.599
Andreas Opedal, Haruki Shirakami, Bernhard Schölkopf, Abulhair Saparov, and Mrinmaya Sachan. MathGAP: Out-of-distribution evaluation on problems with arbitrarily complex proofs. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are NLP models really able to solve simple math word problems? In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceed- ings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2080-2094, Online, June 2021. Association for Computational Linguistics. URL https: :ttpp:///accaae http://aaaaaanaocyoooooo ww.oorg/22022 www.caaclllaaa maianl-mann.... 168.
Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison- Wesley, Reading, MA, 1984. ISBN 0-201-05594-5. URL https: org. http:////...ccc..rrr//////////. 5555/525.
Ivo Petrov, Jasper Dekoninck, Lyuben Baltadzhiev, Maria Drencheva, Kristian Minchev, Mislav Balunovic, Nikola Jovanović, and Martin Vechev. Proof or bluff? Evaluating LLLMs on 2025 USA math olympiad. In 2nd Al for Math Workshop @ ICMI. 2025, 2025. URL wtttthtss///pereeeeeee het/fforum?2d+33855HHH0III
David L.. Poole and Alan K. Mackworth. Artificial Intelligence: Foundations of Computational Agents. Cambridge University Press, USA, 2nd edition, 2017. ISBN 110719539X. URL https: // oooii.org/1..110 1000//0...17/7981100025522
15

---

Mojžesz Presburger. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du 1e congrés de Mathématiciens des pays Slaves, Varsovie 1929, pp. 92-101, 1929. URL https://boook... google http//ooksss.d-7ggggAAAAAAAAAA In German.
Xiao Pu, Michael Saxon, Wenyue Hua, and William Yang Wang. ThoughtTerminntor: Benchmarking, calibrating, and mitigating overthinking in reasoning models. In Second Conference Language Modeling, 2025. URL https: / /ttp///epeeeeeeeeee/eeeeeeeeeeee
Raghu Ramakrishnan. Magic templates: A spellbinding approach to logic programs. The Journal of Logic Programming, 113344):88-2166 1991. URL https://doi. otg/10.10100 0743-1066 (91) 90026-L.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang. Julien Dirani, Julian Michael, and Samuel Bowman. GPQA: A graduate- google-pre proof q&a benchmark. In First Conference on Language Modeling, 2024. URL https: /ttp:::://////ii///eeeee www.ereweeewweeeeeeeeeee net/forum? id-Ti67584b98.
Mary Riley, James Greeno, and Joan Heller. Development of Children's 's Problem-Solving Ability in Arithmetic, pp. 153-196. Learning Research and Development Center, University of Pittsburgh, 01 1983. ISBN 978-0122847806. URL https: //trir/erieeeee ed. gov/?id=ED252410.
John Alan Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23-41, 1965. doi: 10.1 00.1145/21220.:22253. URL https://doi.... orgi:.....rroooo www.org................. 1145/
321250. 221250.321255 321253.
Erik Sandewall. An approach to the frame problem and its implementation. Machine intelligence, 7 (195-204):11-19, 1972. URL https://wwwt ida. wew.lll...eeeeeeeee www.sseeet/caaeeeeeeeeeeeeeeeeee /Bt////t//aiiserrraccee///////// caisor-1922-000 pdf.
Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In The eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: http//ppeeeeeeeeeeeeeeeeeeeeeeee www/teruuurr.... http://rruum/dd-f//abb0oo0o
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thouuht. In The Eleventh International Conference Learning Representations, 2023.
URL h aaee/fforum?.tttqFVVV2z2222
Abulhair Saparov, Srushti Ajay Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Mehran Kazemi, Najoung Kim, and He He. Transformers struggle to learn to search. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openrey www.:/eeeonnmiiimmem (t
.nt/
Bilgehan Sel, Ahmad Tawaha, Vanshaj Khattar, Ruoxi Jia, and Ming Jin. Algorithm of thoughts: Enhancing exploration of ideas in large language models. In Proceedings of the 41st Inter- national Conference on Machine Learning, 2024. URL httph::////ppt https:://proceedings mlr.press v235/ se124a. htmll................m..m......m
Kulin Shah, Nishanth Dikkala, Xin Wang. and Rina Panigrahy. Causal language modeling can elicit search and reasoning capabilities on logic puzzles. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:://ppereeviee.nttt wtt.:/wwwwwewewt/.eeeee..ee i5PoejjMoC.
Freda Shi, Xinyun Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed Huai hsin Chi, Nathanael Scharli, and Denny Zhou. Large language models can be easily distracted by irrelevant context. In International Conference on Machine Learning, 2023. URL https: //tp://eiieeeeeeee/e net/ forun?id:=s2mooN033
Charlie Victor Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning. In The Thirleenth In- ternational Conference on Learning Representations, 2025. URL httph:ttp//// htttapss///peereveeee net/ Forum?id=44WA:2toa
16

---

Leon Sterling and Ehud Shapiro. The Art of Prolog: advanced programming techniques. MIT Press, Cambridge, MA. USA. 2nd edition, 1994. ISBN 0262193388. URL https:///cclppaaa org/ Bogall//occThee _rt__rrr_fff Prolog.pdi pdf.
Yang Sui, Yu-Neng Chuang, Guanchu Wang. Jiamu Zhang. Tianyi Zhang, Jiayi Yuan, Hongyi Liu, Andrew Wen, Shaochen Zhong, Na Zou, Hanjie Chen, and Xia Hu. Stop overthinking: A survey on efficient reasoning for large language models. Transactions on Machine Learning Research, 2025. ISSN 2835-8856
URL https:// wwwpa/reiew..neefooireeeeeeeeeee http:/oorrmmdddftooSSsseee
Hisao Tamaki and Taisuke Sato. Unfold/Fold transformation of logic programs. In Proceedings of the International Conference on Logic Programming, 1984. URL https: http::///i.iiii ac. jp/naid/ 10000035006/.
Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2): 146-160, 1972. doi: 10. 137100000000 URL https: / /ttp://.....rg.....1///0/0011100 1137/0201010.
Alfred Tarski. A tatocce-heoorttcal fixpoint theorem and its applications. Pacific Journal of Mathemat- ics, 5(2): --99 1955. URL https:t///// /msp..ppp.. wwwpp.rggpppp.... http:///6//////jmm--5//5/5
http//5nn--------- p11-spp1sss. p.d.f
Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, Chuning Tang, Congcong Wang, Dehao Zhang, Enming Yuan, Enzhe Lu, Fengxiang Tang, Flood Sung, Guangda Wei, Guokun Lai, Haiqing Guo, Han Zhu, Hao Ding, Hao Hu, Hao Yang, Hao Zhang, Haotian Yao, Haotian Zhao, Haoyu Lu, Haoze Li, Haozhen Yu, Hongcheng Gao. Huabin Zheng, Huan Yuan, Jia Chen, Jianhang Guo, Jianlin Su, Jianzhou Wang, Jie Zhao, Jin Zhang, Jingyuan Liu, Junjie Yan, Junyan Wu, Lidong Shi, Ling Ye, Longhui Yu, Mengnan Dong. Neo Zhang, Ningchen Ma, Qiwei Pan, Qucheng Gong, Shaowei Liu, Shengling Ma. Shupeng Wei, Sihan Cao, Siying Huang. Tao Jiang, Weihao Gao. Weimin Xiong, Weiran He, Weixiao Huang. Wenhao Wu, Wenyang He. Xianghui Wei, Xianqing Jia, Xingzhe Wu, Xinran Xu, Xinxing Zu, Xinyu Zhou, Xuehai Pan, Y. Charles, Yang Li, Yangyang Hu, Yangyang Liu, Yanru Chen, Yejie Wang. Yibo Liu, Yidao Qin, Yifeng Liu, Ying Yang. Yiping Bao, Yulun Du, Yuxin Wu, Yuzhi Wang, Zaida Zhou, Zhaoji Wang. Zhaowei Li, Zhen Zhu, Zheng Zhang, Zhexu Wang, Zhilin Yang, Zhiqi Huang, Zihao Huang, Ziyao Xu, and Zonghan Yang. Kimi k1.5: Scaling reinforcement learning with LLMs. arXiv preprint arXiv: January 2025. URL https:://oi. org/10 10. 48550/ arxiv 2501 12599.
George Tsoukalas, Jasper Lee, John Jennings. Jimmy Xin, Michelle Ding, Michael Jennings, Ami- tayush Thakur, and Swarat Chaudhuri. PutnamBench: Evaluating neural georee--provers on the Putnam Mathematical Competition. In The Thirty-eight Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL forum?id=CaKCF700
net/
Miles Turpin, Julian Michael, Ethan Perez, and Samuel R. Bowman. Language models don't always say what they think: Unfaithful explanations in chain-of-thouge prompting. In T'hirty-eventth Conference on Neural Information Processing Systems, 2023. URL https:/ //pp///eee/eeeeeeeeeeeee/eeeeeee net/ forum?id-bzsAuPLX.
Moshe Y. Vardi. The complexity of relational query languages. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC '82, pp. 137-146. Association for Computing Machinery, 1982 ISBN 0897910702. doi: 10. 00,1145/800070.822158 URL https: //doi.oor/// 10. 1145/800070.8022
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math- Shth-Shepherd: Verify and reinforce LLMs step-by-step without human annotations. In Lei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 9426 9939,,39, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/ 2024.acl-long URL. https:: htt.tttss://allanttoot /awcaaaaaanntoyyc..aaoao org/2024 acl long.
Edwin B. Wilson. Probable inference, the law of succession, and statistical inference. Journal of the
American Statistical Association, 22(158):209-12,, 1927. doi: 10. 499800006614.119927000033333 URL https: / //www/wwwwooooo// tandfonling
11w.:...1100000111..011110001110 1927 10502953.
17

---

Wilson Wu, John Xavier Morris, and Lionel Levine. Do language models plan ahead for future tokens? First Conference on Language Modeling. 2024. URL https: attps://openrrevew net/
Shijie Xia, Xuefeng Li, Yixin Liu, Tongshuang Wu, and Pengfei Liu. Evaluating mathematical reasoning beyond accuracy. Proceedings of the AAAI Conference on Artificial Intelligence, 39: 27723-27730, 04 2025. doi: ww.1////ai..3399263.....
URL https: //js::////jss//// aaai oeaal.orgiinnne //iinddd..
Xinnuo Xu, Rachel Lawrence, Kshitij Dubey, Atharva Pandey, Risa Ueno, Fabian Falck, Aditya V. Nori, Rahul Sharma, Amit Sharma, and Javier Gonzalez. RE-IMAGINE: Symbolic benchmark synthesis for reasoning evaluation. In Forly-second International Conference on Machine Learning, 2025. URL
net//forumiiddqpP000la
An Yang. Beichen Zhang, Binyuan Hui, Bofei Gao, Bowen Yu, Chengpeng Li, Dayiheng Liu, Jianhong Tu, Jingren Zhou, Junyang Lin, Keming Lu, Mingfeng Xue, Runji Lin, Tianyu Liu, Xingzhang Ren, and Zhenru Zhang- Qwen2.5-Math technical report: Toward mathematical expert model via seff-improvement. arXiv preprint urXiv:2409.12122 12122, 2024. URL. https:
//arxiv..o baaxiv..rg/abaee wrgg/bs//4000 12122.
Longhui Yu, Weisen Jiang, Han Shi, Jincheng YU, Zhengying Liu, Yu Zhang, James Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. MetaMath: Bootstrap your own mathematical questions for large language models. In The Twelfth International Conference on Learning Representations, 2024. URL https: http///pppeeeiiieeeeee peee//torum/ddd-BBoghgun
Hugh Zhang, Jeff Da. Dean Lee, Vaughn Robinson, Catherine Wu, William Song, Tiffany Zhao, Pranav Vishnu Raja, Charlotte Zhuang, Dylan Z Slack, Qin Lyu, Sean M. Hendryx, Russell Kaplan, Michele Lunati, and Summer Yue. A careful examination of large language model performance on grade school arithmetic. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL https: httpe////pppevveeeeeeeee RJZRhMzZzH.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Compare the claims with the results presented in $5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in an ad-hoc manner throughout the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
See App. B and App. C.4 for proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have included as much relevant details the main text as possible. Further details on data generation can be found in App. C and details on the experiments in App. D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer:
[Yes]
Justification:
All code is available on our GitHub repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. wwtppcccpcc/cceecccccccccccccctt httpei/ggieeee/eeeumaimieeeeee
/Cc////oodbssssseeeeee wwmiisssioooicyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We have specified everything we believe to be relevant, along with details reviewers identified missing.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please refer to the tables and figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The compute required to reproduce our experiments is not outside of the ordinary typically accessed by academic labs. Inference on all models we consider is also available through APIs.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attps://neuns http:///wwurrppcccppbbbeeaa Ctublicc/thicSuuieeee
Answer: [Yes]
Justification:
We foresee no ethical concerns about our work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Foundational research that is not tied to particular applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets properly cited and used according to license.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the data and code that generated it GitHub.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https //tp:///eeuppppeeeeee / for what should or should not be described.
25

---

A Further Background
A.1 Negation in Logic Programming
It is also useful to introduce notion of negation into logic programming We denote negation by To accommodate negation, introduce the extended Herbrand base H del H U {-h h H). We call an interpretation 1 C H. consistent iff E = -b & I. Furthermore, a logic program P is called guusistency-preserving if is consistent implies Tp is consistent. One simple way to check whether a logic program is consistency prrseernncy-reservving is inspect the program's 's dependency structure. Construct the predicate dependency graph G as follows. Create a vertex (D) for every distinct predicate symbol p appearing in P. For each rule predicate p appearing among r's premises, add directed edge + (q) where q is h's predicate symbol. Then, label the edge if p is negated and + otherwise. We say that G has negative eycle there exists a directed cycle that contains at least one negatively labeled edge. Logic programs that do not have negative cycles are called stratified (Abiteboul al., 1995, $15.2). It is easy see that any stratified logic program has a consistency-presers fixpoint operator.
(b,,-,, by + h) P and each
A.2 Forward Chaining
We give background details and pscudocode for the forward chaining algorithm: see Alg. 1. The algorithm takes logic program =
with a set of ground goal theorems Hy and returns (true) if all goal theorems in Mg can be proved. It uses a priority queue Q and a set C. The priority queue Q is called the agenda. It keeps track of theorems that are to be used to prove new theorems. The order in which the axioms are pushed to Q will determine the order in which they are popped and Q may implement any arbitrary priority policy. For example, a last-in first-out (LIFO) policy yields depth-first search (DFS) order, while first-in first-out (FIFO) policy yields a breadth-fisst search (BFS) order. The set C' is called a chart. The chart keeps track of theorems that have been proved. Theorems are added to C after they have been popped from Q.
When a theorem is popped, is used prove new theorems if applicable. The algorithm iterates over all rules in the program and proves all conclusions that can be proved from the popped premise together with theorems that have previously been added C. For conclusion to be proved, there must exist an instantiation of the rule for which the premises in the instantiated ground rule are in C. The algorithm iteratively removes theorems from Hg as they are proved, and terminates with the result T when Hg has been emptied. If all theorems that could be proved have been popped and Hy remains non-empty, the algorithm returns (false). The algorithm may not terminate, however, if the minimal Herbrand model is infinitely large.
B Decidability of GSM Programs
Proposition (Decidability). Pet = Rw be a logic program where Rw is specified in Table I and Aw a numerically consistent subset Rw's 's extended Herbrand base H. Then, inference in Pw is decidable, i.e., it is decidable to determine whether h E (A((A) for arbitrary h E H.
Proof sketch. First, observe that the extended Herbrand base H of Pw is countably infinite due to the unbounded sets of quantity constants Ng and timestamp constants No. However, since the axioms Aw were chosen to be numerically consistent and the sets MW 2AA and Eg are all finite, it follows that (AA) ([A))orr or equivalently conootains only finitely many theorems for each element of N Consequently, reasoning in Pw reduces to Presburger arithmetic, as the only built-in predicate that applies to timestamps is T 1. present in Rule (2) in Table 1. Since Presburger arithmetic is famously decidable (Presburger, 1929; Haase, 2018), it follows that inference Pw is decidable.
C Data Generation
We adapt and apply Opedal et al.'s (2025) method for generating shortest proofs with axioms that are numerically consistent. App. C.2 introduces and discusses pseudocode (Alg. 2), App. C.3 explains how we use the algorithm to generate a proof along with irrelevant axioms, and App. C.4 shows that the algorithm indeed returns shortes! proof. To do so, we define a class of logic programs of which Pw is member, and we will present a generalization of Opedal et al.'s 's (2025) method
26

---

Algorithm Generic forward chaining
function FORWARDCHANINGGP = R U A, Hg)
2.
Pprogrrm R. U A, set of ground goal theorems Hg
3.
Q
Dinitialize agenda
4.
C+Ø
Dinitialize chart set of known atoms ppuuh axioms to agenda
5.
for A:: QPPUSH(V)
6.
7.
while + + 2::
bpop premises while available Dpop highest priority premise Dmmar as proved by adding to chart Diterate over all rules program 30 E ((P): b1/0, b2/0 h/0 and b1/ 61/0, bx/0 /0 E C:
V' Q.POP()
C- CU
9.
10.
for (61, .... bN J R:
11.
12.
Dthere is new inference rule available for which all premises have been previously proved h' < h/8 if H' & C: Q.PUSH(h')
Iground conclusion to the rule bwe proved a new theorem >ppuh to agenda bwee proved a new goal theorem Dmark proved by removing from goal set othe goal set is empty so we have proved all goal theorems
14.
16.
if h Hg:
Hg - Hg \ {
18
if Hg Ø:
return T
20. ball goal theorems could not be proved
return
that generates shortest proofs under any program this class. We start by defining this class of logic programs in App. C.I below.
C.1 Additional Definitions
We define the expanded Herbrand base containing all ground and non-ground atoms-innludinn negation (App. A.1) H ip,ti....,ty [N) E Ep, ar(p) = N,t1, &N E Dg U Σx} U E ar() = N, N,4,,.,, .i,,. Ix E Σg U Σx). We let C + 2 be a function that selects set of terms from an input atom. We refer to C((b) the C-terms of b. One example of such a function in Ra is to return the set of agent terms from given atom, e.g., C'cont(A A, 5, boat, 2)) {4} and C(comp(A, (horuks), 2, boat, 1)) {A, (haruki)). In the following, we will also define C of an inference rule. Indeed, = bi...., bx + h, we define C(r) def U C(by) the union of the C'terms in the premises of the inference rule We similarly define of hyperedge: Given a hyperedge
(=p((),..,,N) (N)
(bi...,bkl - h, C(e) der U C(bb).
Definition We say a set of inference rules C-conserving if. for every inference rule .i...... bx h, we have C(by) # O for all k, C(h) + ( and one of the following conditions holds:
1. The rule is an introduction rule for a predicate p. and can be written as
b.....b H (N).....)...
(2)
Here, we require the premises to be non-p atoms. We require the C-terms in the conclusion appear in the premises: C(p(t,.... IN U of the premises are disjoint: C(bb) CCb,) Ø for all le + j. We require that R have at most one introduction rule for each predicate.
k= C(bx). We also require that the C-terms
2. The rule is an elimination rule for a predicate p. and can be written
b m.y bx- p(t,,,,,,..... .... tN) h.
Here, we require that the C-term of the conclusion is distinct from that of the premises: by,... b1- C(h) n C(bx)) for all i = 1, 1,.... K 1. We also require that the C-term of the premise p(t "i,,,.., (x) contains the C-terms of all other premises and the conclusion:
C(h) U C(bx) C C(p(t,,.., (N)). Finally, we require the C-terms of the other premises are disjoint: C(bu) C(b,) Ø for all 0 < k.j < K and l + j.
27

---

3. The rule is a union rule, where there is a built-in in premise requiring the C-terms of the conclusion be equal to the union of the C-terms of the premises: C(h) = =U C(bu). This rule must be unique in R.
4. The rule is an unused rule: contains premises that do not unify with the conclusion of any rule.
Finally, if R has multiple elimination rules for a predicate p. we require that those rules be dis- tinct in the following way: For any two such rules, written b1,-.. bk -1. p -,.-.-.00 (2) T h and
[x))),,'')) for any such that h/0 = Ii' p(t,,-., (x) { # p(t (.,..-,,)) F,))
Given C-conserving set of inference rules R, we will use the following short-hand notation refer to specific subsets of rules:
R, the set of introduction rules in R.
Rg is the set of climination rules in R.
Ry is the set of union rules in R.
Definition 2. Let E: H + 2 be function. We say set of inference rules R is E-monotonic if. for every inference rule b ..., bg h, we have F((ba) # O for all k, E(hh) # O. and one of the following conditions holds:
1. The rule is an introduction rule; see above.
2. The rule is an elimination rule; see above.
3. The rule preserves E-terms: =(bi))....e E((b)=))..E((()))
)+x= = E(h).
To prove the optimality of our generated proofs, need additional constraints the relationship between introduction and elimination rules. Let C:: + 2 be a function. Consider each elim- ination rule 61, .... by 1, p(t,,((.,,,)) (x) + h, and let C. a hypergraph using the following procedure: Start by mapping the atom p(t,,..,,ty to a vertex Vo. i.e. we {(va) = (p(( IN)). Repeat the following: For any vertex that contains C-terms in both C. and Cn (i.e., (v) C. * Ø and (v) ( C + 2), and for any introduction rule B,,,.., b/x | h E R, add vertex for each unified premise by/0 where E(h' /0) = and hyperedge from (bxb/0) (bx/0)} to (v). We say the climination rule is C-Iocally reducible if either: (1) the hypergraph contains no edges, or (2) there exists a vertex in this hypergraph that identifies with the conclusion of the climination rule h. If all climination rules in R are locally reducible, we say R in harmony. One consequence of harmony is that, in any proof containing a proof step with an elimination rule, if the subproof of the premise p(t1,... .... &x) does not contain any axioms with C-terms from both C, and Ch. which is true of any proof generated by the procedure in App. C, then the conclusion of the elimination rule must be an axiom of the subproof. Therefore, P is not optimal.
def U C(bb) and C₁ _ C(h). Construct
We note that Rw is agent-conserving, i.e., Rw is C-conserving where C is the function that returns the agents of any atom. In particular, if we inspect the rules in Table 1, we observe that (la) and (Ib) are elimination rules for comp, and (Ic) is the corresponding introduction rule. Rules (2a) and (2b) are climination rules for transfer. Rule (4) is an elimination rule for rate. There are no corresponding introduction rules for transfer and rate, (5a) is an elimination rule for compeq and (5b) is the corresponding introduction rule. Rule (3) is a union rule. Rule (6) is an unused rule. Ro also entity-monotonic with (4) being the elimination rule for rate. Rw is also in harmony, with respect to both agents and entities: (la) and (Ib) are each locally reducible with (1c). (5a) is locally reducible with combination of (5b) and (Ic).
A ground substitution {(xm, (mm ) is a typed substitution where Im E Eg. for all m E [M]. We define (P) to be the set of all ground substitutions under the logic program P.
C.2 Applying Opedal et al.'s (2025) Method
Opedal et al. (2025) provide method to generate the shortest proof for a goal hg. i.e., the shortest (Aw), -hyp))aatttpttthh that exists in proof forest over the Herbrand base; see $3.2. We present the pseudocode in Alg. The method takes any logic program with C-conserving rules, e.g., Pw described in Table goal theorem hgg set of forbidden ground theorems Ax. and
28

---

Algorithm 2
function SAMPLESHOORTESTPPPOPP bgg Ax, D)
2. >-logic program P (e.g. Table 1), gool theorem hgg forbidden ground theorems Ax, max depth D
3. let R. be the inference rules in P
4. E
Dinitialize an empty hyperpath Dinitialize queue for conclusions to expand and their depth
5. QUEUE t []
QUEUE.PUSH((O) hg))
Dhy is distance O from hig
SET < (hy) Ax
while QUEUE # Ø:
hd, < QUEUE.POP()
10.
if > D:
Dexit if stopping criterion has been met
break
12.
Sirst, sample the inference rule for the next proof step
R' t 1 (6 (b....., 8 + h²) R, U. U Ru, 30 0c(P) : ://0 h}
r == =(b,, "....,''x (b1,...,
R/) SAMPLE(R')
14.
>next, sample the substitution
O' + (0 O (o)),, h//h//00- 1/0 = h, / & SET}
16.
17.
Ssample novel and distinct C-terms whenever possible let CSE USESET C(x)
18.
e' o' o'n 1 11 C(6)) C(h)) = -IU C(b//0) Cserl
19.
20.
r Ry:
Dsample widest possible union rules
e' e n [0) ((K/8)) C(b)/0) Ø for le + jt
21.
8~ SAMPLE(O')
23.
for k = up to K:
SET SET (6 /0 if r E RS and k + K: QUBUE.PUSH (,11,
Dthe last premise of elimination rules are axioms
27.
Sconstruct the hyperedge for this new proof step, and prepend it to the hyperpath x (tb1,-. .. bk) h) o
29. return P
maximum depth D. The set Ax becomes relevant when generating irrelevant axioms, which will be discussed in App. C.3. For now, we assume that Ax Ø. The algorithm will terminate and return a proof of depth D. our experiments with Pw, we use the following arguments: We sample the goal hg to be ground atom of the form cont (4, E, T)/0 0 for some 0 E ((P)). For the agent set we make an arbitrary choice, sampling an agent set with cardinality (1, 2, 3, 4} with probabilities {1+1//2 2 + 1/6, 3 - 1/6, 4 1/6.. We restrict the cardinality to 4 in order avoid generating GSM problems that are too large; see App. D. for dataset statistics. The timestamp is set to an arbitrary value larger than the value of D, which ensures that the timestamps remain in N throughout the generation procedure. We sample D uniformly at random from {1,2, 2, for every generated proof.
Sampling proceeds recursively in top-down manner. We then sample an inference rule b,, bx + h, ie., where is the conclusion. This yields a tree. We then repeat the procedure recursively for each leaf node until the stopping criterion, i.e., required depth, has been reached. Importantly, all premises are sampled without replacement; this ensures that any individual theorem will not be used more than once in the generated proof, i.e., the proof is acyclic. For example, suppose we have cont( (haruki), 5, boot, 1) and sample an instantiation of Rule (la) in Table 1. We generate two new premises, cont( {abu), 3, boat, 1) and comp( {haraki), {abu), 2, boat, 1), where the agent (abu) is new agent that does not appear elsewhere in the proof. In Alg. 2, this is handled by maintaining set SET of generated non-ground atoms, and by restricting the substitutions such that new C-terms are mapped to new objects. We only sample atoms that are not in SET.
We comment on two more details of Alg. 2. First, whenever we sample an elimination rule bi,...bb 6b- p(,,,..,4x) h, we require the last premise, p((,,..,/Ny (N), to be an axiom, i.e., we do not recursively apply the algorithm on this premise. This is due to the fact that the rules in P are in harmony, and so the addition of introduction rules preceding elimination rules could result in reccule-e regions in the output proof, and so the proof would not be shortest. Second, if
29

---

sample a union rule, we always require the C-terms of the premises to be singleton sets. Otherwise, a shorter proof could have been obtained by several instantiations of the union rule.
Throughout the algorithm, we sample substitutions from (a(P). By substituting under the constraints laid out by the arithmetic built-ins ensure numerical consistency. However, numerical substitutions may fail due to unsatisfiable constraints, i.c., O' in Alg. 2 may become empty before we sample from it. We therefore perform rejection sampling until a successful substitution has been found. In a few cases, this may run prohibitively long. We therefore retry a maximum of 1000 times before rejecting the candidate proof and sampling a new one.
C.3 Generating Math Word Programs with Irrelevant Axioms
We apply Alg. 2 described in the previous subsection to generate irrelevant axioms. As mentioned in $4.3, we augment a logic program Pw = Rw LJ Aw as sampled by the method described above with M additional sets of irrelevant axioms A Li... 11 A AMr. In simple terms, we do so by applying the sampling procedure again, once for every Am, with additional restrictions to not generate duplicate axioms. As will show later, this procedure for generating irrelevant axioms requires the additional constraint that the inference rules R in the logic program P be E-monotonic. With each application of the sampling procedure, we provide a perturbed goal argument hy. At least one C-term or E-term of the original goal will be replaced with new value (e.g.. in Pw. either the agent, the entity, or both will be perturbed). Precisely which term is perturbed depends the experimental setting (see $4.3). The set of forbidden theorems Ax is initialized to be the theorems in the shortest proof (including the axioms) from Pw Rw LI Aw. thus, avoiding generating those theorems. The same is done incrementally for the irrelevant axioms as they are generated, guaranteeing disjoint sets.
Moreover, for practical reasons, the distribution from which we sample is slightly modified. In particular, we restrict cont predicates to have singleton agent sets; otherwise, the number of irrel- evant axioms could get very large. Furthermore, overlapping agents and entities could sometimes be hard to instantiate with a rate atom, since it requires particular semantic relationship between the two entity terms in the atom, e.g., "apples" " per "basket". " Enforcing these restrictions led to substantially more efficient rejection sampling during the substitution part of Alg. 2.
exclude the rate predicate,
we found that
When ordering the axioms in natural language, it is undesirable to have a predictable ordering of relevant and irrelevant axioms, e.g., appending all irrelevant axioms to follow the relevant ones. We therefore randomly reorder them in a manner that respects the ordering of the values of the timestamp.
C.4 Uniqueness and Optimality of Generated Proofs
Here, we will show that the above procedure for generating proofs produces a shortest proof-a proof from axioms A to goal fy for which there does not exist a shorter proof of hy from A. Furthermore, we will show that each generated proof is unique: There are no other shortest proofs with the same axioms and goal theorem.
C-conservation, monotonicity, and harmony of the inference rules alone insufficient to guarantee that the proofs generated by the procedure described in App. C are shortest. We need additional properties of the generated proofs, as well as few additional definitions.
A linear chain is sequence of hyperedges ei, eM where the head of every edge is in the tail of the next edge (except for the last edge). More precisely, for all m, we have em = (bm,1 m.y bm, + hmm and for all 0 < m < M, Am E (1b++1,1, 1.2.22.....
Given an (A, hg -proof p = ((V, E), and an atom x E H in the extended Herbrand base H (App. A) where (x) E V. subproof of x is an (A, prrooff = Ez), where V2 S V and E. C E. Using this, we can define the subproof relation: If is subproof of some atom in P, we write Pr 3 P. We say a subproof P2 of x contains an atom y, or similarly, y is in Pa, if there is an (A, x hypeprpttt where (v) is in the head or tail of any edge in the hyperpath. Similarly, say a subproof P, of x contains a C-term t, or t in Pz, if there is some such that Pa contains and E C(y).
16This is analogous to folding and unfolding (Tamaki & Sato, 1984).
30

---

Theorem 1 (Generated proofs are shortest and unique). Let R be a set of inference rules that are C-conserving, E-monotonic, and in harmony." 17 let P be an (A, -y)roof in R generated by the procedure in App. C.3, and let Á be the set of irrelevant axioms generated by App. C.3. There does not exist (A', -proo y in R LUAUA A such that 13'| S [P].
To prove Thm. we introduce two lemmas. First, in Lemma 1, we show that the shortest proofs (without irrelevant axioms) are unique. That is, for given goal theorem and set of axioms, there is no shortest proof that is different than the one we generate. Then, we show that the irrelevant axioms generated in App. C.3 generated through Alg. 2 can not be used yield another shortest proof of the goal theorem; this is done in Lemma 2. Taken together, these lemmas imply Thm. 1.
Lemma 1. Let R. be a C-conserving set of inference rules, and let A be a set of axioms. Then, for all theorems bg in R.U. A such that (A,hg)-pro)) P could be generated by Alg. we have that P is hg 's unique shortest proof in R A.
Proof. We perform structural induction on the subproof relation 3.
We first observe that d can not have cycles: By definition, cycle contains several vertices labeled with the same theorem. This is not possible since Alg. 2 maintains a set of already sampled theorems SET that can never be sampled again: Specifically, line 16 excludes theorems in SET from being sampled and line 24 adds generated theorems to SET.
Base Case. The base case is the smallest possible proof containing single axiom that is also the goal theorem, i..., an hg) (ogoo of hg with [P] = 1. This is clearly the unique shortest proof in this case.
(h)),, i.e., the hyperedge for which the head is labeled with the goal theorem h of the subproof. The inductive hypothesis states that for any atom x * h in P, the subproof of x in R A. We consider the various cases of inference rules in the logic program for the last hyperedge and show that the unique shortest proof of the conclusion is obtained by combining the unique shortest proofss of the premises under the inference rule corresponding to that hyperedge.
Inductive Case. Consider the last hyperedge (e-1 (bx)))()))) -
the unique shortest (A, x) -))-roof in
We now consider four cases.
Case 1: (Introduction). The inference rule corresponding to the last hyperedge is an instantiation of introduction rule:
b b1,..,bK bx + p(,,,..,,
Because there are no other introduction rules for C(p(ta...,,t)) = - C(b)). and the atoms in the subproofs of the premises are disjoint, the above introduction rule the only way to prove p(t1...,tty t.). Thus, we conclude that d is the unique shortest proof of p(t1....,tx)
Case 2: (Elimination). The inference rule corresponding the last hyperedge is instantiation of an elimination rule: b,,... bx-1, P(11, .... (x) ) + h. Due to the restriction in the generative process- App. the-the premise p(f1,-.. tN) is not expanded when generating P because it is axiom. Furthermore, since (hh) n Cba) = Ø for all premises by. it is impossible to prove h using only the atoms in the subproofs of the premises b.,... bk-1- .. In fact, since C(h) C C(((1, (N)... (N)), the axiom p(,,,.., IN) musl appear in any proof of h. The logic program may have other elimination rules for the same predicate p. but since such rules are distinct due to C-conservation, those other rules cannot be used to derive h from bj. -1, p(t1..., t.). Therefore, we conclude that P is the unique shortest proof of h.
Case 3: (Union). The inference rule corresponding to the last hyperedge is an instantiation of a union rule: b,,.., ..., bx + h. Since the generation procedure in App. C.2 only generates hyperedges corresponding to union rules where the premises have disjoint C-terms, i.e., C(b (bb))))(), = Ø for all k f and there is no way to prove h other than the union rule, this case is identical to Case / above.
Case 4: (Unused). The inference rule corresponding to the last hyperedge is an instantiation of an unused rule. But the procedure in App. C.2 never includes such inference rules, so this is impossible.
With respect to both C' and E.
31

---

Lemma 2. Let R be set of inference rules that is C-conserving, E-monotonic, and in harmony, let (A, hg) - be the proof in R generated by App. C.3, and let A be the set of irrelevant axioms generated by App. C.3. Then, there does not exist an (A', hgggggg) poropooof 3 in R L A U A such that A' + A and [P|| S (P).
Proof. We offer a proof by contradiction. By way of contradiction, assume there exists an (A', hg)) proof P' in RUAUA A such that A' * A and | = |p]. Take T to be the shortest such proof. Because, by construction of the algorithm, the proof P consists of single hyperpath starting from A. Thus, A' + A implies there exists an a E A' where a & A. Recall that P = [VV,E), () is itself a proof forest. Let ((P) d USEE C(e) be the set of C-terms in P. i.c., the relevant C-terms. Similarly, let Ve E(e) be set of E-terms in P, i.e., the relevant E-terms. We now consider two cases.
E(P) del
Case 1: C(a) & C(P) (The irrelevant axiom only has relevant C-terms). The generation procedure described in App. C.3 can only generate an irrelevant atom with relevant C-terms when generating proof trees that have F-terms that are distinct from those the relevant proof. Therefore, the E-terms in P.', i.e., the irrelevant E-terms, are disjoint from those in PP i.e., the relevant F-terms. Take the linear chain e1, EM E 3 such that is in the tail of e and hg is the head of eM. Let h. be the head of edge Em Select the first Em such that (hmm) contains E(hm+1) 1) has only relevant E-terms. There must be at least one such edge since hg has only relevant E-terms but does not. Because R is E-monotonic, only elimination rules allow an E-term from premise to be absent from the conclusion, and so cm+1 must be an instantiation of an elimination rule
E-term that is not relevant and
b ... by- 1: p(t1, ..., tN) H h,
(5)
and E(h) U E(bb) E(p(ti,...,tN for any k. The E-terms of hm and hm+1 included in E(p(t1. ... fy)). Thus, the premise p(t1. t.. must contain both relevant and irrelevant E-terms. Note that in the generation procedure described in App. C.3, no axiom is generated that contains both relevant and irrelevant E-terms. Therefore, p(4 IN) must be derived from axioms other than a. However, because R. is in harmony, the subproof of this premise must contain h, and so the proof J' is not shortest, which is a contradiction.
Case 2 C(a) & C(P) (The irrelevant axiom has irrelevant C-term). Take the linear chain C1,,,EM E P such that a is in the tail of ej and hg is the head of eM. Let him be the head of edge Cm- Select the first em such that Chhm) E C(P) and 11 C C(P). There must be at least one such edge since hg has only relevant C-terms but a does not. Since the R is C-conserving, only elimination rules allow a C-term from premise to be absent from the conclusion, and so cm+1 must be an instantiation of an elimination rule
bi, ... by- p(11, ..., (r) H h,
and C(h) O(b,) S C(p(t)..... Nn).. That is, the C-terms of f. and hm+1 are included in C(p(t1, ..., (N)). Thus, the premise p(t1, (x) must contain both relevant and irrelevant C-terms. Note that in the generation procedure described App. C.3, no axiom is generated that contains both relevant and irrelevant C-terms. Therefore, p(t1, ... tr) must be derived from other axioms. However, since R is in harmony, the subproof of this premise must contain h, and so the proof P is not shortest, which is contradiction.
We can now prove Thm. using the above lemmas.
Theorem (Generated proofs are shortest and unique). Let R be a set of inference rules that are C-conserving, E-monotonic, and in harmony, 18 let P be an (A, hp)oof in R L A generated by the procedure in App. C.3, and let A be the set of irrelevant axioms generated by App. C.3. There does not exist an (A', -frroof 3a in R U A L À such that |P' <<> [P.
Proof. By Lemma 1, there exists one unique shortest proof P of a goal theorem from set of relevant axioms and this is the proof we generate as the ground-truth proof. By Lemma 2, there will be no additional proofs P' where |PP| < |PP when generating irrelevant axioms through our procedure. Therefore, all our generated proof systems have a unique shortest proof, which is identical to the ground-truth proof that is generated through our procedure.
With respect to both C' and E.
32

---

Base Problem Length
120
100
Problems
80
# Steps
Figure 4: Histogram of the number of hyperedges (i.e., inference rule applications) present in the shortest proof for the GSM programs our dataset.
Number of Axioms
Complexity
Hase
70
Tree
w/ Maltiple Tress
Problens
40
40
30
20
10
15
Axtions
Figure 5: Histogram of the total number of axioms, including irrelevant ones, per type of complexity of the GSM programs in our dataset.
D
More Details on Experiments
D.1 Dataset Statisties
Here, we present more statistics on the datasets used in our experiments ($5). Fig. 4 shows the distribution of the number of edges in the proofs in the base problems, which equivalent the number of non-axiom theorems. The numbers range from 2 to 13." The distribution is skewed towards shorter problems. This done by design order to prevent saturation when evaluating models with different levels of capabilities.
Fig. 5 shows the number of axioms the GSM problems contain, including irrelevant ones. As expected, adding one irrelevant axiom (w/ axiom) yields a distribution that is shifted by exactly one additional axiom as compared to the base distribution. When adding single irrelevant tree (w/ tree), the distribution shifts further and spreads out. This trend is further amplified when adding multiple irrelevant trees (w/ multiple trees).
D.2 Prompt
See Fig. for the prompt used our experiments.
For reference, GSMSK (Cobbe al., 2021) includes problems with to steps.
33

---

[PROMPT 11
You helpful assistant tasked with solving math word problems. You follow the formatting of the problems and the solutions as given in examples below.
Q: Lib possesses 20 puzzles. Shanna has puzzles more than Lib. Shanna then donates 5 puzzles to Costa. Shanna has 6 puzzles more than Valeria. Valeria has 11 puzzles more than Clementius. How many puzzles does Clementius have totaled?
A: Let's think step by step.
1. Lib possesses 20 puzzles.
2. Shanna has 4 puzzles more than Lib.
So Shanna has 20 4 24 puzzles.
Shanna then donates puzzles to Costa.
5. So Shanna has 24 = 19 puzzles.
6. Shanna has 6 puzzles more than Valeria.
So Valeria has 19 6 13 puzzles.
Valeria has puzzles more than Clementius.
9. So Clementius has 11 puzzles. Therefore, the answer (arabic numerals) is 2.
[...reeeat...
Q: Stacee owns 18 necklaces. Stacce then gets 14 more necklaces from Felic. Valencia has necklaces less than Stacee. How many necklaces does Valencia have?
A: Let's think step by step.
[GENERATION 1]
1. Stacee owns 18 necklaces.
2. Stacee then gets 14 more necklaces from Felic.
So Stacee has 18 14 32 necklaces.
Valencia has necklaces less than Stacee.
5. So Valencia has 32 11 21 necklaces.
[PROMPT 2]
Therefore, the answer (arabic numerals) [GENERATION 2]
2/
Figure 6: Two-stage prompting method used in our experiments. We first prompt the model with in context examples (5-shot) and the test problem. After generation, re-prompt the model to generate the final numerical answer.
D.3 Example Proof
In this section we give an example proof in natural language. Consider the following problem, with the irrelevant axioms marked in bold:
Anatola has 67 keys. Ichabod has 23 packets. Clayborne has 55 crayons. Pieter has 20 parrots. Ichabod has 30 packets less than Winnah. Pieter then gives Yorgos parrots. Clayborne has 96 crayons less than Imogene. Anatola has 55 keys less than Rahel. Dennie has 19 parrots. Dianna owns 4 parrots. The number of parrots that Edgar has more than Pieter is the same as the difference between the number of parrots that Dennie has compared Dianna. Edgar has 3 parrots than Eddie. How many parrots does Eddie have all?
Note that the only axioms that are relevant are the ones containing information about parrots. The shortest proof for this problem requires the application of four inference rules and can be written in natural language as follows:
1. Pieter has 20 parrots.
2. Pieter then gives Yorgos 6 parrots.
3. So Pieter has 20 6 = 14 parrots.
4. Dennie has 19 parrots.
5. Dianna owns 4 parrots.
34

---

6. So the difference between the number of parrots Dennie and Dianna have is
19 4 15.
The number of parrots that Edgar has more than Pieter is the same as the difference between the number of parrots that Dennie has compared to Dianna.
8. So Edgar has 14 + 15 = 29 parrots.
9. Edgar has 3 parrots more than Eddie.
10. So Eddie has 29
26 parrots.
In this case, employing a best-first search heuristic based on lexical overlap with the query (i.e., prioritizing theorems that contain information about parrots) will yield the above shortest proof. Llama-3.1-8B5 188--nnrrutt did not opt for that strategy. Instead, generated the following, inefficient solution to this problem:
Anatola has 67 keys.
Anatola has 55 keys less than Rahel.
So Rahel has 67 + 55 122 keys.
4. Ichabod has 30 packets less than Winnah.
5. So Winnah has 23 30 = 53 packets.
6. Clayborne has 96 crayons less than Imogene.
7. So Imogene has 55 + 96 151 crayons.
8. Pieter has 20 parrots.
9. Pieter then gives Yorgos 6 parrots.
10. So Pieter has 20 6 = 14 parrots.
11. The number of parrots that Edgar has more than Pieter is the same as the difference between the number of parrots that Dennie has compared to Dianna.
12. Dennie has 19 parrots and Dianna has 4 parrots.
13. The difference between Dennie and Dianna is - 15.
14. So Edgar has 15 more parrots than Pieter.
15. Edgar has 15 + 14 = 29 parrots.
16. Edgar has 3 parrots more than Eddie.
17. So Eddie has 29 26 parrots.
Therefore, the answer (arabic numerals) is 26.
D.4 Further Empirical Results
Accuracy Stratified by Agent and Entity Overlap. Fig. 7 shows further stratified results that were mentioned 1. We briefly note that these results suggest that the models might make use of a heuristic based on such overlap. (Recall that the problem sets are otherwise identical.) One could reasonably expect that model could learn such heuristic, based on previous work suggesting that models may derive the conclusion to proof step greedily within forward pass before initiating the step the output tokens (Kudo et al., 2024; Wu et al., 2024).
Parsing Reasoning Model Outputs. Since QwQ-32B and DeepSeek-RI did not generate output corresponding to strings in verbalized program, performed separate, more crude analysis for those two models. Rather than matching the full generated token sequence, we match only the arithmetic expressions. They matched with the ground-tree truth expressions from the built-ins of the corresponding inference rules. This can only be done for theorems that are not axioms, since only those require arithmetic built-in (i.e, arithmetic expression) to prove. Arithmetic expressions ex- tracted flexibly, accounting for formatting irregularities and natural language that may be interleaved. The parser may also prediet match for particular model output if no matches found.
We manually verified parsing accuracy (macro-average) on model outputs over 20 randomly selected example problems. The parser predicted the correct match (or correctly predicted no match) in 94.4% of cases for QwQ-32B and 94.8% of cases for DeepSeck-R...
Table 4 displays the results. We observe results that are overall consistent with the main conclusions of the paper; even state-of-the-art models like PeepSeck-RI-desee accuracy (Table 2) appear to generate theorems that are irrelevant to the goal theorem. As with the two models discussed in the main text, the efficiency scores decrease when there agent and/or entity overlap between the irrelevant axioms and the goal theorem.
performing well in terms of
35

---

Max-Llame 1-8--18---88-- Anstrett
Qrent 5- Saath bustract
Q+1--20
Deplakkit
wifire Compleuty
o/ M'Mallle Times
who0 Complexity
Complouty
Compleniy excry weelup
overlp
agedt
Agenr codiy ovedap
Figure Results on problems with irrelevant axioms from Table as average answer accuracy (%) when stratified by different kinds of lexical overlap between the irrelevant axioms and the query. The error bars show the 95% confidence interval using Wilson (1927) score intervals.
Non-ground Queries
None
Entity
Agent
Both
QwQ-32B
Efficiency (non-axioms)
77.1
63.8
72.2
63.1
DeepSeek-R1
Efficiency (non-axioms)
89.4
67.7
77.3
67.8
Table Additional efficiency analysis QwQ-32B and DeepSeek-R1, using more crude parser that only extracts arithmetic expressions corresponding the arithmetic huilt-ins in Table 1. The efficiency score can therefore only he presented for theorems that are not axioms. Results are stratified and computed in the same way $5.2. The differences in efficiency scores across datasets of different lexical overlaps significant (p < 0.001) according one-way ANOVA analyses.
Search Order. While our results in $5.2 suggest that LMs make use of information in the query to prove goals, they also reveal that LMs generate irrelevant theorems. Thus, LMs appear to use some heuristic, albeit an imperfect one, in their reasoning. Here, present a limited analysis whether this heuristic could in combination with either DFS or BFS. We do so by examining the order in which intermediate theorems, both relevant and irrelevant, comparing this order to the respective reference orders. Furthermore, we compare the LM's ordering to the theorems in the shortest proof as visited in DFS order control.
generated by the LM, and
Before presenting the results, we make note of few limitations of this analysis. First, the only irrelevant theorems consider in the DFS and BFS orderings are those that are generated by Alg. when sampling the axioms for the irrelevant goal theorems hi...uu ($4.3). In addition, we note that in-context examples were ordered according to DFS; see $5. However, the examples were chosen so that the ordering of theorems that are not axioms would be the same under both DFS and BFS. We therefore ignore the axioms as we compare the orderings.
Concretely, the DFS and BFS orderings correspond to the order in which atoms are popped from the chart in Alg. 1, where: (i) C is implemented as a stack for DFS and queue for BFS, (ii) the axioms are popped from the agenda Q in the order in which they are presented (i.e., pushed) to the model in natural language (as described $5), and (iii) we do not include pops of axioms.
As our metric, we compute the Levenshtein distance between the sequence of indices produced by the LM and the ground truth reference ordering under the different search orders, normalized by the longest of the two sequences. The results are shown Fig. 8. We observe that the models' search orders closer to DFS than to BFS across all types of query overlap. Furthermore, for Llama-3.1, 1, they are closer to the DFSe- ordering required for the shortest proof than DFS when there is no agent entity overlap between the goal and the irrelevant axioms. Qwen2.5-Math appears to be less efficient however, consistent with the results in $5.2. These findings suggest that LMs tend to follow a depth-first exploration of the proof space in combination with the superficial heuristic. However, future work should perform more rigorous analysis to confirm these preliminary findings.
36

---

Meta Lluma Instret
Quen15-Math D--ustruct
0.
and antly
ently
Overlag
Ovalla
DFS
RFS
Efficion DPS
Figure 8: Average Levenshtein distance between Llama-3. 3.1 (DFS), breadth-firs first search (BFS), and an efficient DFS which only visits relevant theorems. The plot based on problems which model gave correct answer. Levenshtein distances are normalized by the length of the longest string to take values in [0, 1]: lower values mean shorter distances.
search order and depth- search
37


Reviews:
[{"review_id": "cf2J3OA7WQ", "reviewer": "Reviewer_Bqyz", "summary": "The paper evaluates how efficiently language models perform arithmetic proof search when faced with irrelevant information. Using a formal proof system and uniquely defined efficient proofs, the authors show that even strong LMs often include unnecessary steps, especially when irrelevant facts overlap with the query. The models tend to follow depth-first-like search guided by imperfect heuristics, revealing a gap between getting correct answers and reasoning efficiently.", "questions": "- In Table 2, for Llama-3.1-8B under “w/ Axiom”, why is the accuracy with irrelevant axioms (60.8%) higher than the control (54.0%)? Does this suggest that irrelevant information improves performance, or is it a typo?\n- Could you clarify the results in Table 3? It’s unclear how the experiments demonstrate that LMs are empirically worse at proving ground theorems.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- Well-controlled experiments using a clearly defined proof system.\n\nWeaknesses\n- While the controlled setup is appreciated, it may be overly simplistic and may not generalise well to real-world reasoning tasks.\n- The negative impact of irrelevant premises is a known issue, even outside rigorously defined proof systems, which may limit the novelty of the conclusions.\n- The claim that LLM proof search follows a DFS-like ordering is interesting, but the experimental evidence supporting it is not entirely convincing.", "was_revised": true, "final_justification": "Most of concerns have been addressed except for that I am still a bit worried the applicability of the theoretical framework to more complex problems.", "rebuttal": "Thank you for your review and feedback. We respond to your questions and reservations below.\n\n> While the controlled setup is appreciated, it may be overly simplistic and may not generalise well to real-world reasoning tasks.\n\nThanks for raising this point. We believe there is a natural trade-off between higher ecological validity on the one hand and a more principled/formal understanding on the other; we chose to prioritize the latter in this study. Besides, our approach has additional advantages such as mitigating data leakage, and the problems, while synthetic, are reminiscent of  those found in popular datasets such as GSM8K (Cobbe et al., 2021). We take your point and will rewrite the introduction to better motivate our study.\n\n\n> The negative impact of irrelevant premises is a known issue, even outside rigorously defined proof systems, which may limit the novelty of the conclusions.\n\nWe agree that previous papers (Shi et al., 2023,  Mirzadeh et al., 2025) have reported that irrelevant information has a negative effect on LM reasoning. Note that we make several contributions beyond these papers: (i) while previous papers analyzed problems with *one* irrelevant premise, often placed at the same position in the text, we provide more complex problems where there are irrelevant premises at various positions in text that can be used in further deduction; (ii) our study considers not only answer accuracy, but also proof efficiency; (iii) we have a method to automatically generate problems with irrelevant premises of various kinds, which is more scalable; (iv) we formally characterize the notion of irrelevance, which enables a more principled understanding of the findings. Thus, our study can be viewed as refining and extending findings from previous papers, which we acknowledge in the paper, e.g., at l85-7 and and l300-1. With that said, we agree that we can do a better job at this and will incorporate the above discussion into the related work section. Moreover, we would be grateful for any pointers to other related literature we may have missed that made similar contributions!\n\n\n> The claim that LLM proof search follows a DFS-like ordering is interesting, but the experimental evidence supporting it is not entirely convincing.\n\nWe are pleased that the reviewer also sees the value in studying search order. We do indeed find that the LM’s search order is closer to DFS than to BFS, but, for the sake of clarity, we would like to add that we additionally find evidence that LMs use a heuristic based on lexical overlap with the query, which yields a more efficient algorithm than basic DFS. That is, we did not intend to claim that they follow DFS and will revise any claims that can be perceived that way.\n\n> In Table 2, for Llama-3.1-8B under “w/ Axiom”, why is the accuracy with irrelevant axioms (60.8%) higher than the control (54.0%)? Does this suggest that irrelevant information improves performance, or is it a typo?\n\nThanks for this question; these numbers deserve a note in section 5.1. It does *not* suggest that irrelevant information improves performance, since the performance on the dataset with irrelevance is still lower than the performance on the base problems (see leftmost column). (As a reminder, the control problems have the same number of axioms as the corresponding problems with irrelevance, except with all axioms being relevant.) It appears to be an outlier; for all other models and datasets, the control accuracy is higher than the non-control one. We did not find a clear explanation for these numbers after manually looking at some of the model responses. We will clarify this point in the paper.\n\n> Could you clarify the results in Table 3? It’s unclear how the experiments demonstrate that LMs are empirically worse at proving ground theorems.\n\nPrecision gives the size of the overlap between the LM's reasoning steps and the steps in the efficient ground truth divided by the number of LM steps, while recall gives the overlap divided by the number of steps in the efficient ground truth. Precision therefore gives a score for efficiency, and recall gives a score for correctness in the steps taken. We observe generally lower scores for both precision and recall when the LMs are given ground queries. Therefore, we conclude that they are less efficient and less correct for ground queries as compared to nonground queries. We will spell this out more clearly in the paper."}, {"review_id": "kpLxjMo9T3", "reviewer": "Reviewer_6aPK", "summary": "The work \"Language Models Are Inefficient Reasoners\" investigates how current large language models handle reasoning in the presence of many irrelevant axioms within grade‑school arithmetic word problems. The paper argues that language models are inefficient reasoners when tasks contain many distractor facts, with the example of achieving normal form efficiency in formal proof systems. The authors adapt the GSM arithmetic generator to insert irrelevant axioms while preserving consistency, varying the complexity (single axiom / single tree / three trees) and lexical overlap (none/entity/agent/both).\n\nThe paper finds that the answer accuracy falls sharply with irrelevance (e.g. Llama‑3 drops from 65% to 41% when three irrelevant trees are added). Parsed proof steps reveal high recall but low precision, indicating many superfluous inferences, while search‑order distance analysis shows traces are closer to DFS than BFS. The authors conclude that LMs employ a depth‑first style strategy guided by a weak lexical heuristic.", "questions": "1. Significance: can you add statistical tests (confidence intervals or McNemar/paired bootstrap tests) for accuracy and precision to support claims of significant degradation?\n2. Model diversity: can you include at least one closed‑weight frontier model (e.g. GPT‑4o) via API to check whether scaling or RLHF reduces inefficiency?\n3. Semantic parser reliability: please provide an error analysis of the 5–6% unmatched proof steps; could systematic misses from the parser distort the results?", "limitations": "Mostly adequately addressed in the paper. Some additional points:\n* reliance on template parsing restricts coverage;\n* proofs are limited to depth ≤ 3.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* [*originality*] as far as I know, this is the first systematic study of irrelevant‑fact noise on LM proof search; the work introduces a novel confluence‑based efficiency metric;\n* [*quality*] the formal proofs are correct, and dataset construction algorithms are clear;\n* [*structure*] the paper is easy to read and understand, and illustrative examples are helpful;\n* [*significance*] dataset and metrics may be introduced into standard benchmarking for researchers working on reasoning, search and CoT evaluation; the paper also promises to release the code for data generation which is always helpful.\n\nWeaknesses:\n* [*originality*] the work deals with arithmetic domain only and relies on an existing GSM generator;\n* [*quality*] there are only four models in the comparison, and 500 samples per condition may be insufficient; \n* [*quality*] the semantic parser is imperfect (94-95% accuracy) which could bias precision/recall;\n* [*significance*] the work is limited to short arithmetic proofs, so it is unclear whether the conclusions transfer to other domains (e.g., logical or commonsense reasoning).", "was_revised": true, "final_justification": "The responses were adequate but did not raise my evaluation which is already at \"borderline accept\".", "rebuttal": "Thank you for the review and useful feedback, and for acclaiming the paper for its novel metric, correctness, and clarity. We respond to your questions below and have made several improvements to the paper based on your feedback.\n\n> Significance: can you add statistical tests (confidence intervals or McNemar/paired bootstrap tests) for accuracy and precision to support claims of significant degradation?\n\nThanks, this is a great suggestion. We performed one-way ANOVA tests for the precision, recall and \"precision for non-axioms\" scores and found statistically significant F-scores (p < 0.001) for precision and precision for non-axioms, both for data with ground and nonground queries. Thus, we conclude that the means of these scores are different across the types of lexical overlap between irrelevant facts and the query, supporting our claim on degradation in terms of efficiency with more lexical overlap (as measured by precision). We will add this analysis to the paper.\n\n> Model diversity: can you include at least one closed‑weight frontier model (e.g. GPT‑4o) via API to check whether scaling or RLHF reduces inefficiency?\n\nWe wanted to use open-weight models in this study in order to ensure replicability, improve understanding of the results in relation to, e.g., architectural choices and training, and overall promote a culture of open science. Our frontier model of choice is DeepSeek-R1, which turns out to be less efficient in terms of tokens generated than Llama-3.1-8B-Instruct and Qwen2.5-Math-7B-Instruct (Figure 2). With that said, if you still feel that including a model like GPT-4o to the analysis is worthwhile, we will be happy to do so even if it means paying OpenAI for API access. \n\n> Semantic parser reliability: please provide an error analysis of the 5–6% unmatched proof steps; could systematic misses from the parser distort the results?\n\nThanks, this was a useful suggestion. We performed an analysis on the unmatched proof steps and found that most of them were on container-type predicates (i.e., statements about possession), especially for the Llama model. The majority of them were misclassified because the model gave the correct intermediate numerical answer without the arithmetic equation that implies that answer. We incorporated such cases into the parser which boosted the parsing accuracy to 99.2% for the Llama model and 97.7% for the Qwen model.\n\n> [originality] the work deals with arithmetic domain only and relies on an existing GSM generator;\n\nWhile it is true that we rely on an existing GSM generator (Opedal et al., 2025), we would like to add that adapting their method to our study required some nontrivial extensions. For instance, we need to ensure that the irrelevant axioms can be used in inference rules with each other but not with the relevant ones, which is non-trivial. We have detailed some of these innovations in 4.2 and App. B, but we will make sure to better clarify these technical nuances in the final version.\n\n> [significance] the work is limited to short arithmetic proofs\n\nTo clarify, the base problems (i.e., excluding irrelevant axioms) may have up to 12 proof steps, i.e., a lot more than 3. (Note that depth is different from the number of proof steps.) Compare, for instance, to GSM8K (Cobbe et al., 2021), which includes problems with 2-8 proof steps. Moreover, the dataset can easily be extended to even longer problems if desired in future studies. To make this clearer, we created a histogram over the number of proof steps which we will add to the appendix and reference in 4.2. We will also make sure to improve the clarity regarding the data distribution more generally in that section.\n\nLastly, we would like to thank the reviewer for mentioning additional limitations. We have included a Limitations section at the end of the paper and will add these points in the discussion there."}, {"review_id": "fqt1YJRUtN", "reviewer": "Reviewer_WAXh", "summary": "This paper explores the efficiency of large language models (LLMs) when solving arithmetic reasoning problems, particularly when faced with irrelevant information. The authors introduce a formal proof system for grade-school math problems, allowing for precise definitions of efficiency and irrelevance through the concept of a \"normal form\" for proofs. Their experiments reveal that LLMs' answer accuracy significantly drops when problems include irrelevant facts, even if seemingly related, and that these models often generate inefficient proofs by taking unnecessary steps. The analysis suggests that LLMs tend to employ a depth-first search strategy, partially guided by lexical overlap with the query, but this heuristic isn't always effective in filtering out noise.", "questions": "1.  Clarify the \"Distraction\" Conclusion for Advanced Models:\n    *   Question/Suggestion: The paper's conclusion states that irrelevant axioms lead to \"significantly lower answer accuracies\". However, for the most capable model, DeepSeek-R1, Table 2 indicates performance is \"nearly saturated\" with only \"slight decreases\" in accuracy. While Figure 2 shows LMs, including DeepSeek-R1, use more tokens (indicating efficiency loss), this may be an expected behavior for complex models. Could the authors refine their conclusion to clearly differentiate between the impact on *accuracy* vs. *efficiency*, particularly for advanced reasoning models, and provide a more nuanced discussion of what \"distraction\" entails in this context for state-of-the-art LLMs?\n    *   Criteria for Score Change: A revised or more detailed analysis that precisely delineates how irrelevance affects accuracy versus efficiency across different model capabilities would significantly enhance the paper's clarity and the empirical robustness of its claims, positively impacting the evaluation of its significance and quality.\n\n2.  Distinguish Novelty from Prior Work (e.g., GSM-Logic/GSM-NoOp):\n    *   Question/Suggestion: The paper states it \"extends their method to generate proofs with irrelevant axioms\" and creates \"problems with many irrelevant axioms\". Please explicitly clarify the significant differences and novelties of your irrelevant fact generation methodology and proof evaluation approach compared to existing benchmarks that incorporate irrelevant information or provide programmatic/proof-based evaluation, specifically addressing works such as \"GSM-Logic\" (e.g., GSM-NoOp), which might also specify programs as proofs. Does your generation of irrelevant axioms from other *normal-form proofs* and control over \"complexity\" and \"lexical overlap\" offer distinct advantages?\n    *   Criteria for Score Change: A clear articulation of the methodological advancements and empirical distinctions from relevant prior work (like GSM-Logic's approach to irrelevant information or structured proofs) would greatly enhance the paper's perceived originality and contribution, leading to a higher evaluation of its significance.\n\n3.  Formalize \"Complexity\" and \"Lexical Overlap\" Definitions:\n    *   Question/Suggestion: While the paper provides a robust theoretical framework for proof systems, the \"Complexity\" (Axiom, Tree, Multiple Trees) and \"Lexical overlap\" (entity, agent) properties used to generate irrelevant facts are described conceptually. To align with the paper's formal emphasis, could the authors provide more formal definitions or cite specific references for these terms and their quantification?\n    *   Criteria for Score Change: Introducing more formal definitions or appropriate academic references for \"Complexity\" and \"Lexical Overlap\" would enhance the paper's rigor and clarity in its experimental design, improving its overall quality.\n\n4.  Provide a Complete Natural Language Problem Example:\n    *   Question/Suggestion: The paper describes generating natural language annotations for problems with irrelevant axioms but does not show a complete example of such an augmented problem (i.e., the actual input given to the LLM). Table 1 only provides templates for inference rules. To help readers intuitively assess task complexity and the reasonableness of the generated questions, could the authors include at least one full natural language example of a problem augmented with interleaved irrelevant axioms?\n    *   Criteria for Score Change: Presenting a concrete, end-to-end natural language example of an augmented problem would significantly improve the clarity and practical understanding of the experimental setup, positively impacting the evaluation of the paper's clarity and quality.\n\n5.  Discuss Scalability of \"Most Efficient Proof\" for Harder Reasoning:\n    *   Question/Suggestion: The paper's evaluation relies on comparing LM outputs to a \"provably unique normal form\" of the \"most efficient ground-truth proof\". While this is a strength for the arithmetic proof system studied due to its confluence, the paper also notes that \"Proving all possible facts... is computationally intractable in general\". Could the authors discuss the generalizability and scalability of this \"most efficient proof\" concept and evaluation methodology to more complex or open-ended reasoning problems where a unique normal form might not exist, finding it is intractable, or where trial-and-error is an inherent and normal part of the problem-solving process? How might this framework adapt or be limited in such scenarios?\n    *   Criteria for Score Change: A thoughtful discussion acknowledging the limitations of the \"most efficient proof\" concept for more challenging and open-ended reasoning domains, and exploring how their methodology might need to be adapted or its claims re-contextualized for such scenarios, would strengthen the paper's overall significance and provide a more comprehensive assessment of its applicability.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n*   Strong Theoretical Framing and Formalization: The paper establishes a well-defined theoretical framework for reasoning and introducing irrelevant axioms. It formally defines a proof system as a 3-tuple (L, A, R) and provides precise characterizations of concepts like efficiency and irrelevance. This formalization, including the property of confluence that ensures a unique, most efficient normal form for proofs, is a key strength that allows for rigorous evaluation.\n*   Novel Evaluation Methodology: The study introduces a new dataset specifically designed to evaluate Language Models (LMs) in the presence of many irrelevant facts, a setting that more closely mirrors real-world reasoning challenges than typical evaluation paradigms. The method for generating problems with irrelevant axioms, sourced from other normal-form proofs and controlling for complexity and lexical overlap, is a new perspective to me.\n*   Comprehensive Proof Verification: Unlike many studies that only verify the final answer, this paper evaluates the full proof generated by the LM, comparing it to the most efficient ground-truth proof. This is done via an automatic evaluation based on semantic parsing, which is a more fine-grained approach to assessing reasoning.\n\n### Weaknesses\n\n*   Limited Impact of Irrelevance on Advanced Models' Accuracy: While the paper concludes that irrelevant axioms lead to significantly lower answer accuracies, this finding appears less pronounced for the most capable models like DeepSeek-R1, where performance is \"nearly saturated\" with only \"slight decreases\". The observation that LMs use more test-time compute than necessary might be an expected behavior for complex models, and similar overthinking has been noted in other models. This slightly weakens the claim that these LMs are easily \"distracted\" in terms of *accuracy*, though their *efficiency* is clearly impacted.\n*   Informal Definitions for Problem Generation Properties: Despite a strong theoretical framework for proof systems, the definitions of \"complexity\" (Axiom, Tree, Multiple Trees) and \"lexical overlap\" (entity, agent) in the irrelevant fact generation process are described conceptually rather than with the same level of formal rigor. More formal definitions or references would enhance the clarity and robustness of these experimental parameters.\n*   Lack of Concrete Natural Language Examples: The paper describes the generation of natural language annotations for problems and proofs. However, it does not provide full natural language examples of the augmented problems given to the LMs. This makes it difficult for readers to intuitively grasp the actual complexity and reasonableness of the tasks from an LM's perspective (Table 1 shows only templates).\n*   Potential Scalability and Generalizability Concerns of \"Most Efficient Proof\": The reliance on a \"provably unique normal form\" for the \"most efficient ground-truth proof\" is a strength for the specific arithmetic proof system studied. However, this concept of a single \"most efficient proof\" might not generalize well to more complex or open-ended reasoning problems where multiple valid proofs exist, or where trial-and-error is an inherent part of the problem-solving process, and an \"efficient\" path is not always guaranteed or even discoverable upfront.", "was_revised": true, "final_justification": "The author's response has addressed my concerns about the formality of some definitions and the significance of the work, though I am not sure if the revised version will fully reflect my suggestions and concerns. Anyway, I would like to raise my score.", "rebuttal": "Thank you for the thorough review and for the structured, concrete feedback. We are happy that you appreciate the formal treatment of proof systems and the novelty and comprehensiveness of the evaluation methodology. We have incorporated most of the feedback, which definitely strengthens the paper, and respond to each of your questions below. \n\n1. Clarify the \"Distraction\" Conclusion for Advanced Models:\n* Thanks for noticing this. We will weaken the claim about irrelevance leading to significantly lower accuracies in the conclusion and throughout the paper, since there is only a small, nonsignificant effect for DeepSeek-R1. Regarding accuracy vs. efficiency: As you allude to, it seems like more capable models such as DeepSeek-R1 are not affected much in terms of accuracy, but they still use more tokens than they do for the corresponding base problems (i.e., those without irrelevant axioms). We created a new plot to show that this is indeed the case, which we will add to the appendix and discuss in 5.2. Thus, our findings suggest that more capable models are “distracted” only in the sense that it takes them more tokens to find the answer, but they still do, generally, find the correct answer. These findings are complementary to recent findings on “overthinking” of reasoning models. This was a helpful suggestion; we will add more discussion in the paper. \n\n2. Distinguish Novelty from Prior Work (e.g., GSM-Logic/GSM-NoOp):\n* We agree that we can improve the clarity of the methodological contributions as compared to prior work, in particular in relation to Mirzadeh et al. (2025) and Shi et al. (2023). The main innovation in our work as compared to theirs is in our method that generates problems with irrelevance *automatically*, whereas these papers seem to have added irrelevant statements manually. In addition, while they augmented problems from existing datasets, we created new problems from scratch. Our method thus avoids a potential bias from memorizing the efficient solution seen during training. In addition, we note the following differences to GSM-Symbolic’s No-Op dataset: (i) they seem to only include *one* irrelevant statement, whereas we may have multiple that could be simultaneously included as premises in the same proof; (ii) they describe irrelevance in an informal manner so the semantics of these irrelevant statements are unclear; (iii) it is hard to know further details about their setup since the details  in the paper are scarce and the dataset is still not available (there is currently an open issue about this in their github repo); we will release our datasets and generation code with the final version of the paper.\n\n* We will incorporate the above discussion into the Related Work section. \n\n3. Formalize \"Complexity\" and \"Lexical Overlap\" Definitions:\n* Thanks, this is a good point. We will revise that section to be more formal and precise. As for the two specific terms you mention, we propose the following: “Lexical overlap” between two atomic formulas can be defined as the type(s) of atom(s), if any, for which the same atom value is present in both atomic formulas. “Complexity” of the irrelevance is about hypergraph connectivity; an irrelevant axiom is one disconnected vertex in the proof, a tree is a component with multiple vertices, and “Multiple Trees” refers to multiple mutually disconnected components, each having multiple vertices. (Recall that a component is a connected subgraph that is not part of any larger connected subgraph.)\n\n4. Provide a Complete Natural Language Problem Example:\n* This is a great suggestion.  We have actually already added (1) a figure in the introduction which illustrates a proof and a corresponding natural language annotation as well as (2) an example problem in natural language with the ground-truth normal-form proof and a model-generated proof to a new Appendix C. \n\n5. Discuss Scalability of \"Most Efficient Proof\" for Harder Reasoning:\n* It is true that the exact type of analysis we propose is restricted to settings with confluent proof systems where there exists a unique most efficient proof. With that said, many of the notions we discuss do actually carry over to more general settings. We are not sure what you mean by “open-ended reasoning” but if we think of it as a non-confluent proof system where there exist several normal forms, we could evaluate efficiency of solutions to such problems simply by the merit of being in (or close to) *some* normal form (i.e., a non-reducible proof). Moreover, we could still compare the number of proof steps in the different normal forms and we may be specifically interested in the proof that has the fewest, which could be checked. Indeed, math word problems may not have unique normal forms in general and we agree that it is important to make note of this limitation. \n\n* In cases where there does not exist any normal form proof at all, it is not possible to adapt our evaluation method. In such cases you might have to resort to more crude metrics such as the number of repeated/redundant proof steps or the number of generated tokens.\n\n* Finally, we note that our statement from the introduction that proving all possible facts could be intractable is not contradictory to there being a unique, most-efficient normal form. This statement is about proving *all* facts implied by the proof system, i.e., not only those relevant to a specific query.\n\n* Thank you for raising these points; we have added a limitations section to the end of the paper and will incorporate the above discussion into that section."}, {"review_id": "zJHGS05K74", "reviewer": "Reviewer_XHVw", "summary": "The paper studies a very basic question: \"Is it true that LLM performance degrades when irrelevant facts are provided\". In particular, the paper investigates the question whether the reasoning gets worse (unnecessary steps are performed). \n\nIn order to do this, the paper uses word problems since smallest proofs for them are unique (this allows measuring non-optimality of the proof generated by LLM). It compares proofs generated by three open-source models with different amount of irrelevant facts and showed that with the amount of irrelevant information increasing the performance is decreasing.", "questions": "1. It would be good to add variance to the plots on Figure 1. \n2. line 231: It would be good to explain why smallest proof is a tree-like proof; for many proof systems the difference between tree- and proof-like proofs is big.\n3. line 164: it would be good to mention algorithms such as A* here.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is interesting and written well; however, the answer that the paper shows is expected and the paper doesn't give any guidance on how this result could be applied in practice. In addition, the problem studied is very far from real-life examples.", "was_revised": true, "final_justification": "I reviewed the response from the authors and other concerns from the other reviewers, and my opinion hasn't changed:\nwhile I agree that the example is somewhat artificial, proving that at least this settign LLM \"think\" as we expect them to think is important step in better understanding LLM capabilities.", "rebuttal": "Thank you for the overall positive review and helpful feedback. \n\nWe can definitely include some discussion on practical implications of the results. While we did not spell this out in the paper, our findings that LMs are generally unable to distinguish relevant from irrelevant information signifies that there is room for improvement in this regard in the training paradigm of current LMs. For instance, efficiency might be improved by penalizing inefficient proofs through the reward function used for finetuning LMs with RL techniques and this could be studied in future work. We will add a discussion to the conclusion.\n\nIn response to your questions:\n1. This is a great suggestion; we will make sure to include it in the final version of the paper.\n2. The smallest proof is always tree-shaped because it does not contain cycles, all vertices are connected, and each premise is used at most once (by construction). We will add this clarification to the paper. \n3. We actually mentioned A* in a previous draft, but decided to omit it since, in our setting, the costs of the hyperedges (or proof steps) are uniform. But we agree that it is a good idea to add it back in for the sake of contextualization in the final version of the paper, and will do so."}]

Author rebuttal:

Meta-review: The paper Language Models Are Inefficient Reasoners: An Analysis on Arithmetic Proof Search investigates whether large language models (LMs) can reason efficiently when faced with irrelevant information in arithmetic proof tasks. It introduces a formal proof system with unique normal forms to define proof efficiency, generates problems with irrelevant axioms of varying complexity and lexical overlap, and evaluates several LMs (Llama-3.1-8B, Qwen2.5-Math-7B, QwQ-32B, DeepSeek-R1). The key findings are that irrelevant information reduces accuracy (especially for smaller models), models often include superfluous proof steps even when correct, and their search strategy resembles depth-first search guided by weak lexical heuristics.

### Strengths of the paper:

- It provides a rigorous formalization of proof systems, irrelevance, and efficiency, including a confluence property guaranteeing a unique efficient proof.

- It introduces a scalable dataset with irrelevant axioms (from other proofs), controlling for complexity and lexical overlap, going beyond prior single-noise setups.

- It goes beyond final answer checking, comparing full LM proofs against efficient ground truth using semantic parsing.

- It shows that LMs use more test-time compute than necessary, often proving irrelevant facts, with clear patterns of depth-first-like search.

- Paper is well structured, examples are provided, and code/dataset release is promised.

### Weaknesses of the paper:

- Experiments focus only on short arithmetic proofs; generalization to broader reasoning tasks remains unclear.

- It relies on a limited set of models (no closed-weight frontier models like GPT-4o) and ~500 examples per condition.

- Semantic parser has ~94–95% accuracy, raising small risks of bias in precision/recall estimates.

- Core finding (irrelevant info harms LMs) is expected and has been noted in prior works; contributions are more incremental than groundbreaking.

- Framework’s assumption of unique most-efficient proofs may not extend to domains where multiple valid proofs exist.

### Primary reasons for Accept (Poster)

The paper is technically solid and makes a careful, principled contribution by formalizing proof efficiency and irrelevance in LM reasoning. While not a major breakthrough, it advances the evaluation of LMs by introducing proof-level metrics and a systematic dataset that stress-tests efficiency under distraction. Its findings about DFS-like search and heuristic use are insightful for understanding LM reasoning. The limitations in domain scope and novelty prevent a spotlight, but the work is strong enough for poster acceptance.

### Summary of the discussion and rebuttal

During rebuttal, the authors addressed reviewers’ concerns by 1) Differentiated their automatic irrelevant-axiom generation from prior manual/no-op approaches, emphasizing scalability and avoidance of data leakage. 2) Added statistical tests (ANOVA, p < 0.001) for degradation claims, more formal definitions of “complexity” and “lexical overlap,” and example augmented problems. 3) Conducted error analysis, boosting parsing accuracy to >97% by incorporating systematic misses. 4) Weakened statements about accuracy drops for advanced models like DeepSeek-R1, instead framing the issue as inefficiency (more tokens used). 5) Added discussion on the restricted applicability of unique-proof evaluation and how methods could adapt to non-confluent systems. Overall, the rebuttal strengthened the paper’s clarity, empirical support, and positioning relative to prior work, leaving consensus around a Poster acceptance.
Decision: Accept (poster)