DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs
Authors: Yuanhe Zhang
Ilja Kuzborskij
Jason D. Lee
Chenlei Leng
Fanghui Liu
Venue: ICLR 2026 Poster (2026)
Keywords: LLMs
mathematical reasoning
directed acyclic graphs
Primary area: foundation or frontier models, including LLMs
TL;DR: We propose a new pipeline by modeling CoT on directed acyclic graphs (DAGs), introduce the concept of logic closeness, and then precisely evaluates the mathematical reasoning ability of LLMs via the proposed DAG-MATH format.

Abstract: Large Language Models (LLMs) demonstrate strong performance on mathematical problems when prompted with Chain-of-Thought (CoT), yet it remains unclear whether this success stems from search, rote procedures, or rule-consistent reasoning. To address this, we propose modeling CoT as a certain rule-based stochastic process over directed acyclic graphs (DAGs), where nodes represent intermediate derivation states and edges encode rule applications. Within this framework, we introduce \textbf{logical closeness}, a metric that quantifies how well a model’s CoT trajectory (i.e., the LLM's final output) adheres to the DAG structure, providing evaluation beyond classical PASS@$k$ metrics. Building on this, we introduce the \emph{DAG-MATH} CoT format and construct a benchmark that guides LLMs to generate CoT trajectories in this format, thereby enabling the evaluation of their reasoning ability under our framework. Across standard math reasoning datasets, our analysis uncovers statistically significant differences in reasoning fidelity among representative LLM families-even when PASS@$k$ is comparable-highlighting gaps between final-answer accuracy and rule-consistent derivation. Our framework provides a balance between free-form CoT and formal proofs systems, offering actionable diagnostics for LLMs reasoning evaluation. Our benchmark and code are available at https://github.com/YuanheZ/DAG-MATH.

Published as a conference paper at ICLR 2026
DAG-MATH: GRAPH-OF-THOUGH GUIDED MATHE-
MATICAL REASONING IN LLMs
Yuanhe Zhang
Ilja Kuzborskij'
University of Warwick yuanhe. zhang@warwicck.ac.
Google DeepMind, United Kingdom il iljak@google.coo
Jason D. Lee
Chenlei Leng
University of California, Berkeley basondlee@berkeeey.ccm edu
Hong Kong Polytechnic University chenlei. lengepolyu. edu hk
Fanghui Liu
Shanghai Jiao Tong University fanghui. liuus liuusjtu.... edu.cn
ABSTRACT
Large Language Models (LLMs) demonstrate strong performance on mathemati- cal problems when prompted with Chain-of-Thougee (CoT), yet it remains unclear whether this success stems from search, rote procedures, or rule-consistent reason- ing. To address this, we propose modeling CoT as certain aale-based stochastic process over directed acyclic graphs (DAGs), where nodes represent intermedi- ate derivation states and edges encode rule applications. Within this framework, we introduce logical closeness, metric that quantifies how well model's CoT trajectory (i.e., the L.LM's final output) adheres to the DAG structure, providing evaluation beyond classical PASS@: @ metries. Building this, we introduce the DAG-MATH CoT format and construct a benchmark that guides LLMs to generate CoT trajectories in this format, thereby enabling the evaluation of their reasoning ability under our framework. Across standard math reasoning datasets, our anal- ysis uncovers statistically significant differences in reasoning fidelity among rep- resentative LLM families-even when PASS @ is comparable-highhighttng gaps between final-answer accuracy and rule-consistent derivation. Our framework provides a balance between free-form CoT and formal proofs systems, offering actionable diagnostics for LLMs reasoning evaluation. Our benchmark and code are available at httpp::: /ttps::/giie thubbubbbuutttt//////...
thub. wwt.commcc/o....ooo Yuan/e/ httpa//c/o//aaae//////--aa-a DDAT MATH
INTRODUCTION
Large Language Models (LLMs) have demonstrated promising mathematical reasoning abilities on
answer/proof-basee based problems, e.g.. Gemini-2.5 (Gemini Team 2025) and GPT-5 (OpenAl 2025
DeepSeek-PE R1 (DeepSeek Team 2025). A key strategy underlying these successes is the Chain-of-
Thought (CoT) (Nye al. 202 Wei et al. 2022 Kojima et al.. 2022 Zhang al. 2022 which encourages models to produce intermediate reasoning steps prior to the final answer.
The black-box nature of CoT in LLMs raises key challenge: how to rigorously model and eval- uate LLMs' mathematical reasoning abilities. Prior works formalize reasoning in terms of search Shalev-Shwartz & Shashual 2025). probabilistic inference (Prystawski et al. 2023 Feng et al. 2023), and propositional logic (Merill & Sabharwal, 2023 Kim & Suzuki 2024 Yin et al. 2025). Intuitively. LLM reasoning needs identify all required premises (e.g., facts, constraints), and con-
PParticipated in advisory capacity only.
SShool of Mathematical Sciences. Institute of Natural Sciences and MOE-LSS LSC. Shanghai Jiao Tong Uni- versity, China. Work done Department of Computer Science, and Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, United Kingdom. (Corresponding author)

---

Published as a conference paper at ICLR 2026
duct correct logical inference from premises to reach the conclusion 1 These operations must be exact, in line with the exact learning requirements in György et al. (2025). To test whether LLMs achieve this through CoT, two elements are crucial:
A Rigorous Framework: It is necessary to establish a principled framework that charac- terizes the mechanisms by which CoT operates in mathematical problem solving. Such a framework should explicitly account for the roles of premises identification and logical inference. This in turn enables systematic analysis of reasoning behaviors.
An Appropriate Evaluation Metric: A reliable metric is required to assess whether model outputs reflect authentic reasoming processes rather than the application of heuristic or search-based strategies An effective metric should hence evaluate not only the final cor- rectness but also the logical coherence of intermediate reasoning steps.
Despite recent progress, existing approaches remain limited in both. In terms of frameworks, prior work has examined Boolean-cireuit analyses eL et. 2222), k k-aritty models (Kim & Suzuki [202]] Yin al. (025)) and graph- based representations (Dziri et al. 2023 Mukherjee et al. 2025). Graph- based strategies provide a natural way model CoT discrete, step-level abstractions where nodes correspond to intermediate assertions and edges encode inferential dependencies. However, existing graph-based formulations, whether modeling CoT as deterministic subgraph matching in a directed acyclic graph (DAG) (Dziri et al.) 2023), random walks reversible/recurrent Markov chains (Kim et al., 2025), or trees of linear solution paths (Shalev-Shwartz & Shashua 2025), ne- glect the improvement from diverse sampling (Wang et al. (003) and ability connect disparate knowledge (Yin Wang 2025). As a result, they fail to capture long-range and cross- boos-bbaach de- pendencies, well the goal-directed, absorbing-state nature of CoT.
In terms of evaluations, prior work (Dziri et al. 2023 Joshi et al. 2025 Kim et al. 2025 Xu
& Sato 2025 primarily relies annler metrics such PASS @ k while the entire output for inference is overlooked, which leaves it unclear whether it is solved by logical inference or by search. promising alternative is the LEAN programming language (De Moura al. 2015 Moura & Ullrich 2021) to formally verify solutions (Google DeepMind| [024]]
Roe Ren et al. 2025 Wang et al.) 2025| Lin et al., 2025). While LEAN-based verification ensures logical correctness, it presupposes that problems have been already formalized in proof-oriented form. For answer-based problems, the formalization into Lean must be carried out in advance, which requires substantial expert effort.
Building on empirical and theoretical insights (Ye et al. 2025 Kim et al., 2025), we address these limitations by formalizing CoT as a rule-based stochastic process on directed acyelic graphs (DAGs). This formalization provides unified and principled framework for both modeling and evaluation of LLM mathematical reasoning. The main contributions of this work are summarized as below:
Framework. In Section 2 we establish a rigorous graph-based framework that formalizes CoT (i.e., the LLM's entire output) in two phases. Phase I constructs a task-specific DAG as the search space for generating CoT trajectories. In Phase 2, the L.M generates CoT trajectories over this DAG under certain stochastic transition rules.
Logical Closeness and Metric. In Section we introduce the notion of logical closeness, which evaluates whether an LLM solves a problem by searching over possible choices or by applying rigorous logical inference. This yields new evaluation metric, the perfect reasoning rate (PRR) and the related AUC (area under curve) scores for ranking.
Benchmark Construction. In Section we propose the DAG-MATH format based on the above concepts, which makes the logical structure of CoT explicit through DAG rep- resentations. Using three-stage prompting method, we construct benchmark of 2,894 gold-standard DAG-MATH DAGS. Our graph-level statistical analysis shows that harder problems yield larger, sparser DAGs with higher branching complexity, emphasizing the need for LLMs to decompose tasks, track long dependencies, and recombine results effec- tively. We have released the benchmark in the supplemental materials.
Empirical Evaluation. In Section 5
employ few-shot prompting to guide LLMs (e.g., Gemini, GPT, Qwen3) to produce DAG-MATH formatted CoT trajectories as the final out-
Accurate calculation and symholic exccution are also required, see the discussion in Appendix A.1 Search--aaeed strategies may yield irrelevant information, undermining solution's 's consistency. I.LMs should be able to summarize the searched/thinking results ensure the final output logic coherence."
2

---

Published as a conference paper at ICLR 2026
put. We find that search can inflate PASS@ I through exploratory branching, while perfect reasoning ability remains comparable across models. Perfectly reasoning corresponds to easier problems; sully-oorrec--aswwee CoT reflects modest exploratory overhead; and incor- rect CoT typically arises from problems exceeding model capacity, where difficulty stems from branching rather than aggregation.
Our framework provides "Goldilocks principle" that balances the versatility of natural language with the rigor of LEAN in mathematical reasoning evaluation. Moreover, we believe the DAG- lay the foundation for mathematical definition of reasoning in LLMs (par- alleling in memorization and generalization in supervised learning), and inform future algorithm design for improved reasoning performance of LLMs.
MATH framework
Notations: We denote a random variable by capital letter (e.g.. V) and its realization by the corresponding lowercase letter (e.g., r). For shorthand,
for & 2 1. We denote a DAG by g = (E, V). where V is the node set and & is the edge set. For node v, we write pa(e) (v) as its parent set. Finally, we denote the input prompt by Xin E where P is the power set of the vocabulary.
write d1at (V1 12,....5 U2)
2 A DAG FRAMEWORK FOR STEP-LEVEL COT
Motivated by empirical observations in Bogdan al. 2025),
we study COT at the step level, rather
than the token level. This step-level perspective has been widely considered recent theoretical analyses (Dziri et al. 2023 Hu al. 2024 Kim et al. 2025 Shalev-Shwartz & Shashual 2025), as it better captures intermediate reasoning and the logical structure of solutions. We model step-level
CoT in a two-phase workflow as below. Phase defines task-specific DAG, where Phase samples CoT trajectories over this DAG under certain stochastic process. For better illustration, we take the
following problem, adapted from MATH-500 (Hendryeks al., 202T), as representative example.
Logarithmic Count Problem (LCP)
For how many integers k E [-300, 300] does the equation 2 log((x 1) = log A: have exactly one real solution x??
2.1 PHASE 1: TASK-SPECIFIC DAG FOR STEP-LEVEL. CoT
For mathematical problems, CoT step is natural- language derivation of new conclusion from prior information. Each step has two components: Edge (Justification): This captures the inference that leads to the step's conclusion. The edge ex- plicitly encodes the logical dependency on the problem statement or on previous steps, making the reasoning chain transparent. Node (Conclusion): The node represents the step's conclusion- state or value derived from the edge's 's logic and its parent nodes.
Edges and Nodes in Step-Level CoT:
Hence, single CoT step be viewed node/edge decomposition, pendix A.2]as as well as the nodes/edges in Fig. foor the logarithmic count problem. Note that such a decomposition is non-umique due to semantic variation, such synonyms equivalent phrasings. This ambiguity makes it challenging to develop a precise and principled definition of a CoTT step.
example in Ap-
Consequently, prior work (Dziri al. 2023 Hu et al. 2024 Kim al. 2025 Shalev-Shwartz &
Shashua 2025 BBgdan et al.] (2025) has typically defined steps heuristically either as text spans or task-specific annotations withhtt providing formal definition. As first attempt, we present an abstract mathematical formulation, with the technical details deferred to Appendix A.3 since they are not essential for understanding the main text. Within this formulation, although the node/edge decomposition for single step may still be non-unique, the task-specific DAG introduced later can be made unique, provided that each step is restricted to single conclusion.
Task-Specific DAG: Empirical studies (Ye et al.,
2025) demonstrate the existence of a latent di- rected dependency graph within LLMs, present as soon as a question/prompt is posted, before any output generated. Formally, given prompt Win, we define the directed graph as
(# (V(w1a) E(r.))
where E(xsa) C ((x.n) V(xin).
3

---

Published as a conference paper at ICLR 2026
where ((:ia) is the set of directed edges and (Z is the set of nodes divided into three classes:
(Tnn)) denotes the set of source nodes, i.e., nodes formulated solely from the input prompt. In Fig. the source nodes are V1, 02, and ug-
Pout(Zis) denotes the set of sink nodes, i.e., nodes with only incoming edges and out- going edges, corresponding to the final answer(s). The correct sink node represents the terminal object that matches the ground-truth answer. In Fig. T the sink nodes are vi0 (correct) and U11 (incorrect).
Vinter (Xin) == V(xin) (Vin( U Vou (xin) denotes the set intermediate nodes. In Fig. the intermediate nodes are Vy through 2g.
We make the following assumption on the acyclic structure of the graph for the absence of circular dependencies, ensuring that no CoT step depends on its own output either directly or indirectly.
Assumption 1. For any imput prompt Vin, the task-specific directed graph (araa) is acyclic.
If the correct sink node is included in ((via). the task-specific DAG can be always constructed by backtracking through its ancestors. Note that, the LLM may reason imperfectly during thinking process, e.g., dead-ends, self-correction, but is expected to output only the finalized, perfect, correct reasoning results to the user (with formal definition later). The reasoning evaluation this paper is based on the entire final output while PASS@ k just considers the final answer. More discussion can be found in Appendix A.4
Task specific DAG for the logarithmic count problem
U2
11
U3
1 "2log(x x - 1) = log k" (target equation);
U2 "k E [-300, 300 (range constraint);
U4
16
U3 "exactly one solution" (task requirement);
V4 "log(æ
requires 1" (constraint inferred from
the equation);
Us "loog requires le > (constraint inferred from the equation);
Us : "2 log(z 1) = log k + (xr - 1)2 k" (re-arranged equation);
1g
87 "I 1 VK" (solve the quadratic equation):
Us "1 + V is the only solution" (correct check);
V10
Ug "For any k, there are two solutions" (incorrect check);
Figure 1: Task-specific DAG via
U10 "There are 300 valid values for k² (the correct answer);
LLaMA-3, 1-8B-Innt
U1 "There are valid value for k. (the incorrect answer).
2.2 PHASE 2: STOCHASTIC PROCESS ON LOGIC DEPENDENCE
Based on the task-specific DAG, the LLM generates CoT trajectories over this DAG as the final output via certain sampling strategy. Given (xx,)) from Phase 1, we denote the node-level au- toregressive distribution of an LLM as P. A node-level CoT trajectory (Vi) with length-L, given the input prompt Xin. sequentially generates V, V (1 < S L), ultimately leading to the final answer Vr == Vout Specifically, the trajectory (Vi [VH, follows the stochastic process:
V1 7 P(. X.n) .... V/ P(. Vi...... Vi X..), Vout ~ P(. V..1. VI, X.n)
Next, we define a stochastic transition rule to generate the node-level trajectory over V(=io). We begin with the initial step, where P(V1 v Xia Iin) is nonzero only for E Vin(x.n) and zero for all other nodes. Given (w.))) and the previous (I - 1) steps Vi---1 = 01.--1 the transition probability for the next step is not based on all previous nodes but depends on certain nodes, i.e.
P(V: = v Vi--1 = 01a-1 X = TIn), Vo E V(11-11 Ian))
with ViViA-1 aii)) = {o V(con)) pa(v) C (mia-1), (un--1})

---

Published as a conference paper at ICLR 2026
and zero probability for Vu & V(V1a-11 Tia). The sampling process is absorbing upon reaching any node u E Vous (Iin), indicating that a final answer has been obtained. For non-thinking LLMs, the model directly outputs such types of CoT for the given problem. For thinking LLMs, e.g- DeepSeek-RI (DeepSeek Team 2025), the thinking process can be viewed as an exploration of the task-specific DAG with self-correction or backtracking, but its final output shown the users (excluding thinking tokens) is still consistent with our transition rule.
Applied to our logarithmic count problem, Eq. ① enforces valid transitions over the nodes. For instance, after collecting {21, 02 V3, U4, v.). the next admissible node should be vo; while nodes vy through U1 remain inaccessible until Vi has been visited. We use LLaMA-3. 1-88-Instt ruct (Grattafiori et al., (224)) to generate four CoT trajectories, where each trajectory consists of its own steps leading to correct/incorrect answers. The nodes and edges shown in Fig. are performed by the authors, but can also be carried out by LLMs through appropriate prompting (see Section Accordingly, the LLM's final CoT output can be split into three classes:
Perfect reasoning (U1, U2 V3, U4, Us LG, U7, Ug (1o): The trajectory only includes the correct sink node and its ancestors. We formally define this in the next section.
Imperfect reasoning, c.g., (V1, 02 13, U4, U5 V6, 27, 0g 0g, v10): The trajectory still reaches the correct answer but also includes the irrelevant node dg. which is not an ancestor of the correct node. Such case may occur when the LLM explores multiple directions and eventually arrives at the correct answer either by chance or through subsequent derivation. We give real example for this case in Appendix B where two solution paths are mixed.
Wrong reasoning, e.g., (v), 12, V3, 06, 17, Ug, v: The final answer is incorrect.
Comparison with previous work: Our framework integrates an instance-specific DAG with a rule- based stochastic process, directly addressing key limitations in prior work. We do not assume a fixed "universal" graph with deterministic matching Dziri et al. (2023). Instead, our DAG is logi- cal, acyclic, and features absorbing sink nodes, preserving the directional, goal-oriented nature of mathematical problem solving while allowing for long-range dependencies, Markov chain models (Kim et al. 2025). Furthermore, unlike the tree abstractions in Shale--Swwartz & Shashual (2025), our DAG captures shared sub-derivations and the true dependency structure rather than just linear solution paths, thereby supporting multiple valid routes to a solution.
contrast to reversible
3 FORMAL DEFINITION OF MATHEMATICAL REASONING ABILITY
Based our DAG framework, now present formal definition of mathematical reasoning ability. Given an input prompt Iin, we independently draw N CoT trajectories [ under the proposed sampling mechanism in Eq. For each trajectory (+),, we construct a trajectory-specing DAG:
gen (I..) - gen (n),,, e(a (m),)), 1 ISiSN,
where the subscript gen indicates that the object (DAG, node, edge) is extracted from the gen- crated CoT trajectory. Here, Vgen corresponds to the enumerated steps in the trajectory, and Egen contains edges explicitly defined by the parents of each step. Each trajectory-specinf DAG is sub- DAG of G (I.n). and the reasoning ability of each trajectory can be evaluated using a new metric, termed logical closeness, and the concept of perfect reasoning, introduced in framework.
Definition 1 (Logical closeness and perfect reasoning). Under Assumption ! consider an input prompt in and the DAG (3.) For each node v (Isa), define its out-degree as
(v Ggen (x)))) := (uu E &gen(( (v + u) E Egen (xm))
We say that Ggen (waa) is logically closed if
deg(u (gmn( 2 VU Vgen(ann))
i.e., only the final nodes have no outgoing edges. Furthermore, if the sink node corresponds to the correct answer, call the associated CoT trajectory case of perfect reasoning.
Any topological ordering of the ancestor nodes that terminates at the correct sink node is perfect reasoning. Compared with evaluating reasoning based solely on the correctness of the final answer,
5

---

Published as a conference paper at ICLR 2026
incorporating logical closeness allows assess whether an LLM engages in genuine logical inference rather than merely searching among possible solutions. Based on the definition logical closeness,
formally define the mathematical reasoning ability of LLMs follows.
Definition 2 (Mathematical reasoning ability). Under Assumption L inn E P. sampled from an underlying distribution D over mathematical problem prompts. define two indicator functions for a trajectory sppcecc DAG (gge(XXnn)
let LLM be given prompt
if geenen (Xin) is logically closed, 0, otherwise,
Sclose (geen (in)) =
8ginel (geen Xin)) 11, if the sink node of Ggen 1o) is correct,
otherwise.
Then, the Perfect Reasoning Rate (PRR) of LLM w.E.t. given prompt Xin is defined as
PRR(X... = Ee Oc2oze (geen (X ) x dgimal (geen Xin))
The overall mathematical reasoning ability of an LLM over the distribution 'D is then measured
R. = EX (PXX,, (PR((X.)))) = Ep, x dctosa (ggen (2n)) x deinal (gon x=n))]-
AUC socres: By relaxing Selose to permit a certain proportion of nodes that do not satisfy logical closeness, we obtain the corresponding AUC scores (with proportion of logic closeness from 0% to 100%), which serves
comprehensive measure of mathematical reasoning performance.
This metric can be regarded as combination the final-answer correctness reflected by PASS @1 and logical closeness. To illustrate Definition 2 con- sider toy DAG example Fig- 2 consisting of two linear chains of length L emanating from common source node. We denote the correct sink node as L and the incorrect sink node as L'. At each step, the transition distribution P is uniform over all available nodes according to Eq. (T. i.e..
Vu E V(eia-1 pin), P(V = Via- = U1--1, X = Rin) =
To remain logically closed, a trajectory must stay on the same chain across the remaining transitions, each occurring with probability 1/2. Hence, we have PRR = L-1 This illustrates that PRR decays exponentially with depth: although the final-answer accuracy (1/2) may appear stable, logically closed trajectories become increasingly rare. Furthermore, Appendix [B.] presents a geometry example from AIME 2025 (Art of Problem Solving 2025a) where the final answer is correct, but logic-closeness fails due mix-
Figure 2: Toy DAG.
ing two solution paths. Consequently, lacking logic closeness risks producing answers correct only by chance, obscuring flawed reasoning, reducing reliability, and undermining interpretability. Fur- thermore, our framework also can be extended to analyze IMO-level problems via lemma-level DAG, which can reveal the key structural distinction. A concrete example based on the problem from IMO 2025 (IMO Foundation 2025) is presented in Appendix B.2
practice, given a dataset with M problems and N independent CoT trajectories per problem, one can approximate PRR (x)..) and R by
M
PRR (11))
close (I d (IIn),
R
PRR
( x
M
==1
By Hoeffding's inequality, taking M 2(1/22) is sufficient for R R| < E with high probability.
Comparison with generalization in supervised learning: Analogous to underfitting and over- fitting in supervised learning. we can define under-reatt weasoning-whern the DAG omits necessary intermediate steps-and over-reasooing-wheee the DAG is logically sound but contains redundant

---

Published as a conference paper at ICLR 2026
irrelevant steps. In both cases, the estimated reasoning ability R is low, and perfect reasoning can be regarded as the "sweet spot" in this baasoning-generalizn analogy.
Importantly, R offers richer enror taxonomy, distinguishing structurally illegal paths, legal-but- wrong paths, and "imperfectly correct" trajectories, whereas standard generalization theory typi- cally treats all errors uniformly. Regularization strategies, such the minimum description length principle (Grünwald] 2007). could potentially mitigate over-reasoning by favoring concise proofs that conform to proof grammar or template. We leave exploration of this direction future work.
4 DAG-MATH FORMATTED COT AND BENCHMARK
In practice, standard CoT trajectories generated by LLMs are unstructured, autoregressive sequences of tokens. Within such free-form text, the logical steps (nodes) and their dependencies (edges) are often entangled, which complicates the evaluation of our step-level reasoning framework. To address this issue, we introduce structured CoT format via prompting, described in Section 4.1 which term the DAG-MATH format. This format facilitates the construction of the corresponding DAG, enabling the creation of DAG benchmark, presented in Section 4.2
4.1 DAG-MATH FORMATTED CoT
As structured, step-by-step format, DAG-MATH explicitly specifies each reasoning step in forward generation order: Edge - Parent(s) -> Node. This ordering is designed for evaluation-oriented sampling: first, declare the logical link to prior knowledge (Edge): next, cite the necessary tecedents (Parents); and finally, assert the derived conclusion (Node). The DAG-MATH format can be produced by LLMs through prompt engineering. For illustration, below is one step from the DAG-MATH formatted COT for the logarithmic count problem (all steps in DAG-MATH format are presented in Appendix Cp.
Step 4
Edge: Since the left-hand side of the equation in Step I contains log(r - 1), the domain restriction for logarithm requires 1 > 0, i.e., x >> 1.
Parents: Step 1. log(x- 1) requires x > 1.
Node:
Step IDs also serve as node identifiers, which allows for a straightforward evaluation of DAG close- ness. Based on the DAG-MATH format, gold-standard CoT trajectory is defined by three criteria: (1) it adheres to the DAG-MATH format; (2) its corresponding DAG is logically closed; and (3) the final answer is correct.
4.2 GOLD-STANDARD DAG-MATH BENCHMARK
We prompt L.MMs generate CoT trajectories in the DAG-MATH format for existing mathematical datasets, such as Omni-MATH (Gao et al.) 2024), and construct the corresponding DAGs. By ver- ifying both logical closeness (Definition and the correctness of the final answers, we compile benchmark consisting of 2,894 gold-standard DAGs. The primary purpose of this benchmark is to characterize the statistical properties of these gold-standard DAGS across different problem difficulty levels, providing valuable insights for evaluating and enhancing LLM mathematical reasoning.
The benchmark comprises problems from Omni-MATH (Gao al. 2024). which are categorized into difficulty levels ranging from 1 (casiest) to 10 (hardest). To ensure high solvability by LLMs, we only consider problems with difficulty levels below For generating DAG-MATH format- and Qwen3 - wonnkinng--e 1n2-2 both recog-
ted CoT's, we employ GPT-o4-m nized as leading models in mathematical problem solving (LMArena 2025). Gold-standard CoTs are constructed using a three-stage prompting strategy (see Appendix D) in reverse order (Node -> Parents + Edge). This approach fixes the node set first, making verification easier with SymPy or Judee and minimizing error propagation, thereby ensuring high-quality trajectories. Fur- thermore, we perform human evaluation on 50 random samples and the results (49/50) confirm the reliability of benchmark, more details in Appendix B

---

Published as a conference paper at ICLR 2026
#hades ou butten Bi
Podges tim betin oofeeyy
Gragt ceedly Dastiuate die Hiaat
0.39
Madmum Dn
Dbrytuutonn Officull Oreap
Mommma OukGayee Dowiltee Oificity Croup
3,20
805
10
Figure 3: Empirical distributions of DAG statistics across problem difficulty groups, where group k: corresponds to problems with difficulty (k-1, Shown are the distributions of #Nodes, #Edges, graph density
(i.e.,
Edgd #Nodos Nodess maximum in-degree, and maximum out-degree.
We consider five representative graph-level statistics: (1) the total number of nodes (#Nodes); (2) the total number of edges (#Edges); (3) graph density, defined as the ratio of #Edges to the maximum
2#Eddes possible number of edges in an acyelic graph, i.e., NNddes #Nodes (4) the maximum in-degree,
denoted d dmax, and (5) the maximum out-degree, denoted d Fig. 3 shows the distributions of
these five statistics across problem difficulty levels. Our key observations as problem difficulty increases from 0 to 6 are as follows:
More nodes and edges with heavier tails: The distributions of #Nodes and #Edges shift no- ticeably to the right and develop heavier tails, indicating that harder problems produce larger graphs, while simpler problems yield much smaller ones.
Sparser structure: The graph becomes sparse when problem difficulty increases. Harder rea- soning produces broader, less connected structures, reflecting modular sub-reasoning where semi-independent chains (e.g., sub-tasks or lemmas) are later combined.
Logic complexity reflected in maximum out-degree: As difficulty increases, the distributions of maximum in-degree and out-degree shift rightward with heavier tails. Maximum in-degree grows slowly, suggesting most steps rely on few inputs, whereas maximum out-degree rises more sharply, indicating that certain key steps support multiple inferences. This implies that logical complexity scales primarily through branching rather than aggregation. The average in- and deg-ee remains around 1.3 across difficulty levels, most nodes have small degrees while few pivotal steps exhibit large connectivity.
Accordingly, problems become harder, their DAGs grow larger and sparser, with complexity arising primarily from branching into modular sub-reasoning chains. This underscores the impor- tance of LLMs being able to decompose problems into sub-tasks, track longer dependencies, and recombine intermediate results to solve challenging problems effectively.
EVALUATION OF MATHEMATICAL REASONING ABILITY
To evaluate mathematical reasoning performance, we employ few-shot prompting (using demonstra- tions from the benchmark in Section 4.2, see Appendix [F for details) to guide LLMs in generating DAG-MATH formatted CoTs/DAGs for test problems, without providing the final solutions.
Models and datasets: We evaluate five LLMs: Gemini -2.5 2-5-lhash (Gemini-2.5-F), 300-----0-ABB-InSS (Gemini-2.5-F-L), 2PT-4.1, GPT-4. 1-mini (GPT-4.1-M), and (Qwen3-30B). These models demonstrate strong mathe- matical performance even without long thinking (White et al. (025), also are more efficient and economical than other thinking-focused models due to lower token usage. We evaluate these models
8

---

Published as a conference paper at ICLR 2026
AIME 2025
BRUMO 2025
HMMT 2025
10
Gemini 2.5 (AUC-0.484 4844
Gemini 2.5 (AUC-0.579)
Gemini 2.5 (AUC-0
Owen3-308 (95)
G (AUC-0.437)
S0enn-3388 (AUC-0.239)
18
Gemini-2.5444 JAUC-0
Gemini22.5.--1 (AUC=O
Gemmi-2.5-F-L (AUC=0.232)
(AUC-0.296)
(AUC-0.332)
GPT4.1 (AUC-6.134)
GPT (AUC-0:255)
GPT-4.1 (AUC-0.329)
GPT4.11 (AUC-0.108)
Accuracy
3.6
2.4
122
66
0..
0.6
0.
66
Logical Closeness Rate
Logical Closeness Rate
Logical Closeness Rate
Figure 4: The AUC curves of averaged accuracy under the logical closeness rate three datasets for five selected LLMs. The curve is a direct plot of the computed accuracies at a fine-grained grids of threshold (0.01 increment from 0 to 1).
on three recently adopted datasets for high-difficulty, answer-based problems: AIME 2025 (Art of Problem Solving 2025a b). BRUMO 2025 (BRUMO) 2025), and HMMT 2025 (HMMT 2025).
For each model, we use a 4-shot prompting strategy to generate 32 DAG- MATH formatted CoT trajectories per problem across all datasets. Next, we extract the correspond- ing DAGs and evaluate the five graph-level statistics introduced in Section 4.2 as well as model performance metrics (e.g., PASS@1 and R). The sampled DAGS are then partitioned into four classes: All (no filtering), Incorrect (ending at an incorrect sink), Correct (ending at the correct sink), and Perfect (logically closed and ending at the correct sink).
Experimental Settings:
5.1 RESULTS
Fig. reports AUC scores across three datasets, with PASS@1 the starting point and R as the end point (see more details in Table Appendix []. as the logic closeness rate increases. Besides,
we also report averaged graph-level statisties for ATME 2025 in Table with additional results for BRUMO 2025 and HMMT 2025 in Appendix |
We have the following observations:
Search improves raw accuracy while perfect reasoning ability remains similar. All models exhibit a noticeable drop from PASS@1 to R; while PASS@I I varies widely across models, R
remains relatively stable (i.e., the end point is almost the same). This suggests that additional exploration or search can inflate raw accuracy, while the models' inherent perfect reasoning ability is broadly comparable. We conduct statistical test in Appendix K. to show statistical significance of those gaps. The AUC scores indicate that models with correct answers achieve at most 80% logic-closed nodes, but accuracy degrades markedly under stricter criteria. This suggests that outputs, while correct, are superficially consistent at some point, which aligns with users' impressions when using these LLMs.
Graph structure reflects problem difficulty and reasoning quality. Harder problems induce larger, sparser, and more branchy DAGs (see (..2. Within each model, Perfect reasoning trajectories correspond to the smallest, densest graphs, reflecting concentrated reasoning on solvable items. Correct graphs are slightly larger and sparser, suggesting the inclusion of useful exploratory steps. In contrast, Incorrect graphs exhibit strong branching (with dmax growing faster than Jaaa)) indicating that failure often arises from speculative expansions rather than from aggregating insufficient inputs. For example, Gemini's Correct cohort exhibits larger but sparser graphs with slightly higher branching when compared to the GPT family, indicating that effective exploration and task planning can increase the likelihood of reaching correct answers without fully closed, deeper reasoning.
Identifying the "difficulty boundary"". Within each model, the Incorrect cohorts resemble ababaaiitaa graphs (see Section 4.2 larger, sparser, heavy-tailed, and with notably higher d In contrast, the Perfect cohorts converge to smaller, relatively dense DAGs with low branching. This indicates that each model's effective difficulty ceiling corresponds to the regime where it can maintain compact, low-branching DAGs; beyond this point point-when branch- ing explodes and density accuracy sharply declines.
9

---

Published as a conference paper at ICLR 2026
These insightful findings from our proposed metrics can provide principled foundation for future work aimed at improvement, see a detailed discussion in Appendix
5.2
MORE EXPERIMENTS AND DISCUSSIONS
Here we discuss several additional experiments to validate claims and findings.
We expand evaluation sample size from 32 to 128 trajectories per problem and calculate 95% confidence intervals for the gap between PASS @ and PRR. The resulting intervals were tight and consistently excluded zero (c.g., confirming a 36% gap for Gemini-2 1imii-2.. Flassh, statistically demonstrating that the difference between finding the correct answer and generating perfectly valid derivation significant and substantial across all tested models. More details are presented in Appendix K.T.
Reasoning Gap:
We employ Two One-Sided Tests (TOST) to verify that DAG-MATH evalua- tions robust variations prompt. By perturbing the few-shot prompts through re-formatting (changing nested bullets to tables) and re-phrasing (using synonyms and alternative grammar), then generate new sets of DAGs. The analysis shows statistical equivalence across five key graph-level statistics and performance metrics, see more details in Appendix K.2
Prompt Sensitivity:
Parsing Consistency and -on-Circularity: We validate the objectivity of PRR/AUC metric by examining the consistency of DAG construction across different parsing methods, including self- parsing and external parsing by Thinking LLMs. The AUC scores for logical closeness remained remarkably stable across all models (ranging from 23.8% to 25.5%) with statistically equivalent DAG structures tested by TOST, demonstrating that logical closeness is an intrinsic property of the solution rather than an artifact of the parser. More details are reported in Appendix K.3
Formatting Constraints: By employing external models to parse natural CoT into dependency graphs, the analysis revealed that the metrics effectively capture fundamental reasoning patterns, with Natural CoT achieving AUC scores comparable to the structured format and over 70% logical closeness. This confirms that the evaluation framework is not limited the benchmark but serves as a robust, objective method for diagnosing the logical coherence and reasoning fidelity of freeform LLM generations. More details are presented in Appendix K.3
Cross-Family Few-Shot Demonstrations: We investigate potential biases introduced by the model source of few-shot demonstrations. While using cross-family examples resulted in slight perfor- mance decrease (GPT-4. 4. 1 PRR drops from 16.8% to 15.9%), the DAG structures are statistically equivalent and the relative rankings of the models remained unchanged. This indicates that while same-family demonstrations are optimal, our framework's 's evaluations remain valid even when cross- family prompting is employed. More details are presented Appendix K.4
Role of Thinking: We perform experi- ments with thinking modes for Gemini models om AIME 2025. The results in Ta- conffrr that while thinking mode sig- nificantly boosts both PASS@I and PRR, the substantial performance gap between two metries persist. The continued gap in- dicates that thinking enhances the model's exploration of the task-specific DAG, yield- ing more correct and logically closed trajec- tories, but does not eliminate the tendency search over logical coherence.
Table 1: Results of PASS@ and PRR for Gemini
models w/wo thinking on AIME 2025.
PASS@ @1
PRR
Thinking
w/o
w/o
Flash Flash-Lite
52.4%
64.0%
17.0% 15.9%
35.9%
37.4%
49.2%
24.5%
6 CONCLUSION
This paper proposes novel DAG-MATH framework for modeling and evaluating mathematical rea- soning, introducing the concepts of logical closeness and perfect reasoning over DAGs, We demon- strate how DAG graph statistics vary with problem difficulty and how models' perfect-reasoning ability and AUC curve behaves across these tasks. The framework provides accessible mathe- matical formalization reasoning and memorization in LLMs, paving the way for future work on reasoning guarantees, analogous to generalization guarantees in supervised learning.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
Y. Z. was supported by Warwick Chancellor's International Scholarship. JDL acknowledges support of Open Philanthropy. NSF IIS 2107304, NSF CCF 2212262, ONR Young Investigator Award, NSF CAREER Award 21 2144994, and NSF CCF 2019844. F. L. was supported by Royal Society KTP R1 241011 Kan Tong Po Visiting Fellowships and Warwick-SITU seed fund. We thank Zulip for project organization tool and Suli for GPU computation resources.
REFERENCES
Art of Problem Solving. 2025 AIME httpes///Arteppoolllaaoolr/roao.
index. 2025 AIME I 2025a. Accessed: 2025.
Art of Problem Solving. 2025 AIME II. bttee:://Arrtffooooooesssrrrrrra
index. php/2025 AIME II 2025b. Accessed: 2025.
Paul C Bogdan, Uzay Macar, Neel Nanda, and Arthur Conmy, Thought anchors: Which Ilm reason- ing steps matter? arXiv preprint arXiv:2506. (00i:2500..1144,, 2025.
BRUMO. Brown University Math Olympiad 2025. https: http:/wwwwu.......//. org/ 2025. Ac-
cessed: 2025.
Leonardo De Moura, Soonho Kong, Jeremy Avigad, Floris Van Doomn, and Jakob von Raumer. The lean theorem prover (system description). In International Conference on Automated Deduction, pp. 378-388. Springer, 2015.
DeepSeek DeepSeek Team. Deepseck-rl: Incentivizing reasoning capability in llms via reinforce- ment learning. arXiv preprint arXiv:2501. 12948, 2025.
Nouha Dziri. Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Scan Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, al. Faith and fate: Limits of trans- formers on compositionality. Advances in Neural Information Processing Systems, 36:70293- 70332, 2023.
Guhao Feng. Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36:70757-70798, 2023.
Bofei Gao, Feifan Song, Zhe Yang. Zefan Cai, Yibo Miao, Qingxiu Dong, Lei Li, Chenghao Ma, Liang Chen, Runxin Xu, Zhengyang Tang, Benyou Wang, Daoguang Zan, Shanghaoran Quan, Ge Zhang, Lei Sha, Yichang Zhang, Xuancheng Ren, Tianyu Liu, and Baobao Chang. Omni- math: A universal olympiad level mathematic benchmark for large language models, 2024. URL https: /ttp:///axivvv./ org/ wtw//bs///aa/oooooooo.o/e..eeaet 24100.79115
Google Gemini Team. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality,
long context, and next generation agentic capabilities, 2025. URL bttps://axxiv.orr abs abs/2507.0626.
Google DeepMind. matical olympiad problems. httpa://deepmins/ wtwp://...oooooogooooooooeeeeeee sttp////covee/boo//////ooooo a ai-sol ves mommo-rre moo-rroble ems at -t---a-ssill sidessiremaamdlleeeee 2024. Accessed: 2025-09-
Ai achieves silver-medal standard solving international mathe-
03.
Aaron Grattafiori, Abhimanyu Dubey, Abhinay Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, al. The llama 3 herd of models. arXiv preprint arXiv:2407.21788. 2024.
Peter D Grünwald. The minimum description length principle. MIT press, 2007.
https://zulip.com

---

Published as a conference paper at ICLR 2026
András György, Tor Lattimore, Nevena Lazié, and Csaba Szepesvári. Beyond statistical learning: Exact learning is essential for general intelligence, 2025. URL https: https::/aaxiv. org/ abs
2306.23908)
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring Mathematical Problem Solving With the MATH Dataset. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks
Track (Round 2), 2021. URL wttpt:tp////cmm http://.....tp/////eeeeooo..o.e.
HMMT. HMMT 2025. https: www. hmmt. org/ 2025, Accessed: 2025.
Xinyang Hu, Fengzhuo Zhang, Siyu Chen, and Zhuoran Yang. Unveiling the statistical foundations of thain-tf- prompting methods. arXiv preprint 14511 2024.
IMO Foundation. International Mathematical Olympiad. https:/ www. imo officiall
org/ 2025. Accessed: 2025.
Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought. arXiv preprint arXiv:2503.07932, 2025.
Koray Kavukcuoglu.
Gemini 2.5:
Our most intelligent
model.
https: og. www.goooolllooooo http:///oo...oooeeeee////c/oooo/ http:///ooooo/ooooooeeeeeeeeee
gemi ni www.oooll-oooiiinnnoeeeeeeeeeeee sactaattte---rr-ee-eee march- March 2025. Blog post on
*The Keyword
Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. arXiv preprint arXiv:2410.0863: 2024.
Juno Kim, Denny Wu, Jason Lee, and Taiji Suzuki. Metastable dynamics of chain-of-thought rea- soning: Provable benefits of search, and distillation. arXiv preprint arXiv:2502.01694 2025.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 15522199-222133 2022.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of Thought Empowers Transform- to Solve Inherently Serial Problems. In The Twelfth International Conference Learning Representations, 2024. httpss//::// bettps::/opeerrveee www.eeeeeeeeeeee htt.:/eee/fouuuteeee/o/ 1onim?iid=-.T.... 9MTM
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, 2023.
Yong Lin, Shange Tang, Bohan Lyu, Ziran Yang, Jui-Hui Chung, Haoyu Zhao, Lai Jiang, Yihan Geng, Jiawei Ge, Jingruo Sun, et al. Goedel-Prover-V22 Scaling formal theorem proving with scaffolded data synthesis and self-correction. arXiv preprint arXiv:2508.0300 2025.
LMArena. Leaderboard. httppp///iaarraaaaaaeeeeeooooooo
2025. Accessed: 2025.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023.
Leonardo de Moura and Sebastian Ulirich. The Ican 4 theorem prover and programming language. In International Conference on Automated Deduction, pp. 625-633 Springer, 2021.
Sagnik Mukherjee, Abhinav Chinta, Takyoung Kim. Tarun Anoop Sharma, and Dilek Hakkani- Premise-augmenter reasoning chains improve emror identification in math reasoning with llms. arXiv preprint orXiv:2502.003622 2025.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Au- gustus Odena. Show your work: Scratchpads for intermediate computation with language models, 2021. URL httpss/tt: wttp:///o/////aa//../// 00114
12

---

Published as a conference paper at ICLR 2026
OpenAI. GPT-5 System Card. httpss//ppeaa..cm///aaa///gggg//
August 2025. System Card published by OpenAl.
Jianfeng Pan, Senyou Deng, and Shaomang Huang. Coat: Chain-o--asscciacc--toooghg framework for enhancing large language models reasoning. arXiv preprint arXiv:2502.022990 2025.
Ben Prystawski, Michael Li, and Noah Goodman. Why think step by step? reasoning emerges from the locality of experience. Advances in Neural Information Processing 36110m6776677
2023.
ZZ Ren, Zhihong Shao, Junxiao Song, Huajian Xin. Haocheng Wang, Wanjia Zhao, Liyue Zhang, Zhe Fu, Qihao Zhu, Dejian Yang, al. Deepseck-Prover-Ve. Advancing formal mathematical reasoning via reinforcement learning for subgoal decomposition. arXiv preprint arXiv:2504.21801, 2025.
Shai Shalev-Shwartz and Amnon Shashua. From reasoning to super-ntelligeece: A search-theoretic perspective, 2025. https: http:////wwwwwwoo////oa////a////
org/ hwtp://b///te http://b/////2//
15865
Haiming Wang. Mert Unsal, Xiaohan Lin, Mantas Baksys, Junqi Liu, Marco Dos Santos, Flood Sung, Marina Vinyes, Zhenzhe Ying, Zekai Zhu, et al. Kimina-Prover preview: Towards large formal reasoning models with reinforcement learning. arXiv preprint arXiv:2504. 11354, 2025.
Peiyi Wang. Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce lims step-by-step without human annotations. In Pro- ceedings of the 62nd Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 9426-9439, 2024.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, al. Chain-of- Prompting Elicits Reasoning in Large Language Models. Advances in neural information processing systems, 35:24824-24837, 2022.
Colin White, Samuel Dooley, Manley Roberts, Arka Pal, Benjamin Feuer, Siddhartha Jain, Ravid Shwartz-Ziv, Neel Jain, Khalid Saifullah, Sreemanti Dey, Shubh-Agrawal, Sandeep Singh Sandha, Siddartha Venkat Naidu, Chinmay Hegde, Yann LeCun, Tom Goldstein, Willie Neiswanger, and Micah Goldblum. Livebench: A challenging, contamination-limite LLM benchmark. In The Thirteenth International Conference on Learning Representations, 2025. URL https:://penrev/// wtw.:eewwwweeeetteetteeeee
net forum? w
Kevin Xu and Issei Sato. To cot or to loop? a formal comparison between chain-of-thought and looped transformers. arXiv preprint arXiv:2505. 19245, 2025.
An Yang, Anfeng Li, Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. 2025.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36:1 16:91809-00 1809-11822, 2023.
Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physies of language models: Part 2.1, grade-school math and the hidden reasoning process. In The Thirteenth International Confer- Learning Representations, 2025. https:/ /wppnrevieeeeeeeee/oeeeeee /
net. wtr.mmirrmmm
Tn5B6Udq3E.
Lang Yin, Debangshu Banerjee, and Gagandeep Singh. Data Shifts Hurt CoT: A Theoretical Study. arXiv preprint arXiv:2506. 10647, 2025.
Yutong Yin and Zhaoran Wang. Are transformers able to reason by connecting separated knowledge in training data? arXiv preprint arXiv:2501. 2025.
13

---

Published as a conference paper at ICLR 2026
Zhenru Zhang, Chujie Zheng, Yangzhen Wu, Beichen Zhang, Runji Lin, Bowen Yu, Dayiheng Liu, Jingren Zhou, and Junyang Lin. The lessons developing process reward models in mathematical reasoning. arXiv preprint arXiv:2501.07301, 2025.
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.03499, 2022.
14

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
2 DAG Framework for Step-I.evel CoT
2.1 Phase I: Task-specitic DAG for Step-Level Col
2.2 Phase 2: Stochastic Process on Logic Dependence
3
Formal Definition of Mathematical Reasoning Ability
4
DAG-MATH Formatted Formattee CoT and Benchmark
DAG-MATH Formatted CoT
4.2
Gold-Standard DAG-MATH Benchmark
7
Evaluation Mathematical Reasoning Ability
5.1
Results
5.2
More experiments and discussions
10
6
Conclusion
10
Illustration and Definition of Co'l Step
17
Remark on Execution Correctness
17
A.2
Intuitive Understanding of Steps in CoT
17
A.3
Mathematical Definition of Steps CoT
17
A.4
Discussions on Acyclicity
19
Examples of Logical Closeness
19
B.1
A High-School Competition-Leve Level Example DAG
19
B.2 An IMO-Level Example DAG
22
Example DAG-MATHH Formatted CoT
24
Benchmark Construction and Validation
24
D.I Prompt for Stage
25
D.2 Prompt for Stage
25
D.3 Prompt for Stage 3
27
Human Evaluation of Gold-Standard Benchmark
29
E.1 Human Evaluation Example
29
Few-Shot Prompt for DAG-MATH Formatted CoT
31
Prompts for Sensitivity Analysis
32
G.1 Prompt with Different Format
32
15

---

Published as a conference paper at ICLR 2026
G.2 Prompt with Rephrasing
34
Prompts for DAG Parsing
35
H.1 Prompt for Thinking LLMS
35
H.2 Prompt for Non-Thinking LLMS
36
Additional Results for Evaluation
36
Discussion on Future Improvements
37
K
Extended Experimental Studies
39
K.
Statistical Tests for PASS@ and PRR under Large Sample
................................
39
K.2
Ablation Studies on the Sensitivity of Prompts]
39
K.3
Ablation Studies Formatting Constraint and Circularity
40
4
Ablation Studies on Cross-Family Few-Shot Examples
42
The Use of Large Language Models (LLMs) Statement
43
16

---

Published as a conference paper at ICLR 2026
A ILLUSTRATION AND DEFINITION OF COT STEP
In this section, we first discuss execution correctness as a measure of LLM reasoning performance and emphasize that our framework addresses the key challenge of tracking logical dependencies. To facilitate understanding, we first provide an intuitive illustration of a CoT step using the logarithmic count problem, followed by formal mathematical definition of a CoT step.
A.1 REMARK ON EXECUTION CORRECTNESS
We note that accurate calculation and symbolic execution remain essential for evaluating an LLM's mathematical reasoning. practice, LLMs may make stepwise errors, such as computational slips or misreading problem statements. Our framework, however, assumes that each step is correct. This simplification justified because step-level errors can be automatically detected using Process Reward Models (Lightman et al. 2023 Wang et al. 2024 Zhang et al. 2025) SymPy validation.
Focusing on correct steps allows us to capture the trajectory of model capabilities: with recent advances (Kavukcuoglu 2025 OpenAl 2025 Yang et al., 2025 DeepSeek Team 2025), the main bottleneck in complex mathematical reasoning lies less in local step fidelity and more the higher- level logical structure. Our framework addresses this challenge by: (1) perceiving the full logical structure of a problem, and (2) navigating it to construct a coherent solution path. By abstracting away from local step errors, isolate and analyze the structural core of CoT reasoning.
A.2 INTUITIVE UNDERSTANDING OF STEPS CoT
We illustrate a single step in the logarithmic count problem (LCP) below.
One CoTI Step in the Logarithmic Count Problem (LCP)
If two logarithmic expressions equal, then their arguments must also be equal.
Hence, from 2 log(x= 1) = log k we can conclude (æ: - 1) 2
In this illustration, the blue part corresponds to the previous conclusion (parent node), the green part represents the new conclusion for the current node, and the orange part highlights the logical reasoning (Edge) that connects the parent to the current node. Note that the edge may be latent when the model only outputs the conclusion without explicitly stating the reasoning.
A.3 MATHEMATICAL DEFINITION OF STEPS IN COT
We now formalize the definition of single CoT step. Let V denote the semantic domain of math- ematical objects in semantic normal form (SNF), raw CoT step sequence of tokens, i.e., string e E P. We introduce a canonicalization map
P - V
that maps any textual span its SNF representation:
_ <(c) EV.
The canonicalization map satisfies the following properties:
Idempotent: k(к(с)) k(c).
Presentation-invariant:: It does not perform substantive algebraic manipulations (e.g., ex- panding factoring), which treated separate reasoning steps.
Canonicalization removes superficial variations such as synonyms, spacing differences, commuta- tivity, and a-equivalent variable names, ensuring semantic consistency.
Intuitively, a CoT step can be mapped to a normalized SymPy object that captures its underlying mathematical semanties. A concrete example of this canonicalization is provided below.
17

---

Published as a conference paper at ICLR 2026
Imput: Raw CoT step text tokens (e.g.. "The value of our target is x + y." or "The target value is (y z).").
Canonicalization (k): Maps the input normalized form by removing superficial varia- tions such as synonyms, spacing, commutativity, and a-equivalent variable names.
Output: A semantic object (e.g., SymPy object Add(x.y)) that consistently encodes the meaning.
Accordingly, let denote a signature of primitive inference rules/operations. Each f J is associated with an arity ar(f) N (i.e., the number of inputs the rule operation takes) and (partial) semantic operator [f] Var(f) - V. Intuitively, F represents the atomic reasoning steps allowed at the CoTT level, such as a single algebraic operation, one application of a named lemma, single substitution. We now formally define a CoT' step.
Definition (Atomic Step of CoT), Given an input prompt Vin E a CoT trajectory of length i is sequence of steps C (C1,-.., Ct)- Suppose P V is canonicalization map. Then, step C₁ can be formulated triple (T Ji, vi) denoted by r; St Us where:
Canonicalization: Each string C₁ E P producee in the CoT trajectory is mapped by k to the corresponding SNF object U k((;) E
2. Premises: I₁ S. fei, ..,,.., U.-1) is the finite set of previously established SNF objects (from the prompt or earlier steps) directly used to infer the current step.
3. Primitive operation: fi E F and v; = [T)](T)), ie., 02 is obtained by exactly one applica- tion of a primitive operator the premises.
Accordingly, each step in a CoT can viewed as the reasoning pattern:
(Premises used) + (inference rule applied) - (new result).
Next, we provide concrete algehra example expanding (x y)² for better intuition.
Step c:: Expand the square
r ((x + )) Si = "expand square",
() + + v; = [/]((T])) = (x
So we have:
{(x + 8) expand square
(a + 5) y))
Step c+11 Distribute the product
T = {()+t) fi11 "distributive law",
1/+1 = [[++a((T = =2 +2 +zy+yr+y²
So we have:
( + x)}
distribute
x² + xy + yy +
Step C422 Simplify like terms
Fi+2 22² + ry + ye + y²
f- = "commutativity + combine like terms",
Us+2 = [[+a](TTa2] = =x + 2xy +
So we have:
{x² + ry + yæ + y²}
simplity, x² + 2xy + y²
Combining the above steps, the CoT trajectory is
(x (c+g) 2
expand square
(x ( (x +
distribute
2² xy ye simplify
x² + 2xy + y²²
This example follows Definition precisely characterizes a CoT trajectory at the step level. Note that this step-level formalization is not essential for understanding the main text, which primarily fo- cuses on DeG-level reasoning rather than the specifics of individual nodes and edges. Nonetheless, for readers interested in how nodes and edges are defined or how they influence a CoT trajectory, this definition and the accompanying example provide useful reference.
18

---

Published as a conference paper at ICLR 2026
A.4 DISCUSSIONS ACYCLICITY
The acyclic assumption in Assumption is sufficient to characterize both groblem-solvingg and the- orem proving. A mathematical derivation/prooff is finite sequence well-formed formulas where each formula is either an axiom or is derived from earlier formulas by rule of inference. If we treat each formula occurrence as a node and draw directed edge from each premise inferred from it, the dependency graph we obtained is indeed directed acyclic graph. This is also supported by formal finitary system such as Zernelo-Fraenkel set theory or type theory. Strategies like proof-by- contradiction are rules of inference (e.g.. -P - P), which creates clear, acyclic dependency: the conclusion P depends on the sub-derivation that starts with the assumption -P and ends with a contradiction I. This is not cycle but conditional branch that is closed, which can be covered by our assumption.
B EXAMPLES OF LOGICAL CLOSENESS
B. A HIGH-SCHOOL COMPETITION-LEVE EXAMPLE DAG
There are several reasons why LLMs may generate unclosed nodes even though the final answer is correct:
Assertions stemming from an alternative strategy that is not one leading to the final answer in the trajectory.
Qualitative axioms that are implicitly used. When forming edges, the model tends link parents that provide numerical values from earlier calculations, since quantitative conclu- sions are casier to cite than qualitative ones.
Irrelevant information drawn from the problem statement.
Additional commentary based on previous conclusions but not required for the solution.
We aim to analyze specific DAG-MATH formatted CoT trajectory which has the correct final answer but unclosed DAG. To justify the rationale, take the following geometry problem from AIME 2025 (Art of Problem Solving 2025a) as an example.
Area of Heptagon Problem
On AABC points A, D, E, and B lie in that order on side AB with AD = 4, DE = 16,
EB = 8. Points A, F, G and C' lie that order on side AC with AF = 13, FG = 52, and GC 26. Let M be the reflection of D through F, and let N be the reflection of G through E. Quadrilateral DEGF has area 288. Find the area of heptagon AFN
We have 4 correct CoT trajectories 32 total trajectories generated by Gemi ni 5-.5-FF ash. We provide a detailed analysis one trajectory that contains multiple unclosed patterns and has a moderate graph size. There are trajectories that exhibit similar characteristics, while the last trajectory consists of 121 nodes.
F
E
N
G
B
C
Figure 5: Visualization of the heptagon problem.
19

---

Published as a conference paper at ICLR 2026
1
19
25
24
31
30
Figure 6: A trajectory-specifi DAG for the Area of Heptagon problem, whose DAG- MATH--formated COT trajectory is generated by Gemini- in-iiii-2... 3-Flash and has the correct final node. Nodes without any children are highlighted in orange.
We plot Fig. 5 for better illustration and present the first trajectory-specific DAG shown Fig. We summarize each node's conclusion below.
1. States the ordering/collinearity A, D. E, B on AB.
2. States AD 4.
3. States DE 16.
4. States EB 8.
5. Computes AE = AD + DE = 20.
6. Computes DB DE + EB = 24.
7. Computes AB AD DE EB 28.
8. States the ordering/collinearity A F F - C on AC (global setup).
9. States AF 13.
10. States FG = 52.
States GC 26.
12. Computes AG AF + FG 65.
13. Computes FC = FG + GC 78.
14. Computes AC = AF + FG - GC' = 91.
15. Defines M as the reflection D across F (so midpoint of DM).
16. Elaborates reflection F; observes F midpoint of DM Area(AFFM Area(ADF).
17. Defines N as the reflection of G across E (so E is midpoint of GN).
18. Notes explicitly that E is the midpoint of GN.
19. States Area( D DEFF) = 288.
20. Sets Area(ADF)
AD
AF AC Area(ABC)
AB
39
21. Sets Area (AFG)-
AE
AG S
258
AC
20

---

Published as a conference paper at ICLR 2026
22. Relates Area(DEGF) Area (AEG) - Area(ADF) 245
23. Solves 245 288 = = Area( Area(ABCC = 588.
49
24. Computes Area( (ADF) = 5/49 = 12.
25. Uses reflection at F = Area(AFM = ArDF(ADF).
26. Concludes Area
Area(AFM) (AFM) = 12.
27. Computes Area Area(ABG)) AG
.S 420.
AC
28. Computes Area BBGG) -Are(AAB)) Area Area(AEG) 420 300 = 120.
29. Uses reflection at E = Area(BEN) = Are((BEG).
30. Concludes Area( BEN) 120.
31. Chooses coordinates = (0, = (28,0), C = (0,42); derives D, D,F.F,G,M,
coordinates.
32. Applies the shoelace formula the heptagon BCFM and gets area 588.
33. States the final result: 588
We can observe that the DAG has 8 non-closed nodes. We diagnose the reasons of uncloseness for each node:
Nodes 1 & 8: These two nodes state the global setup collinearity/ordering which are directly provided by the problem statement. The later steps implicitly use collinearity to add segment lengths AB and AC, but the LLM does not recognize that it has used these two nodes in its subsequent reasoning.
Nodes 6 & 13 16 & 18: These nodes derive or state extra commentary their previous step, which not needed in the subsequent steps.
Then, the message conveyed by Nodes 26 & 30 is crucial. In this problem, the area of the heptagon AFNBCEB can be computed via two distinct strategies:
Reflection-swap strategy: The core idea is replace two interior triangles (AADF, ABEG) of AABC with their exterior reflected counterparts (AAFM, ABEN), show- ing that the net area change is zero. Consequently, the heptagon's 's area obtained by straightforward "remove add" bookkeeping.
Shoelace strategy: This coordinate-based algebraic method requires only listing the ver- tices A, F, N, B, C, E, M order and then applying the determinant sums to compute the area.
Nodes 20 through 30 derive the areas required for the final "remove + add" computation in the reflection-swap strategy, namely
Area(APN Area(ABC)
Area(ADF) Area(BEG)
Node
Node 24
Node 28
Area(AFM + Area(BEN)
Node
26
Node 30
If the model had continued with this strategy, Node 31 would correspond to the above equation, with Nodes 26 & 30 as its parents. However, the model instead switches to the shoclace strategy at Node 31 and successfully obtains the correct answer, leaving Nodes 26 & 30 unclosed.
This provides evidence that the model generates elements an alternative strategy that remain unused in the current trajectory and switches strategies during the generation process.
Next, the second and third trajectories exhibit node structures similar to the first. They also contain nodes such as Nodes 1 & 8 in the first trajectory, which not recognized being used. However, unlike the first trajectory, they rely solely on the reflection-swaz strategy to obtain the final answer without switching strategy.
21

---

Published as a conference paper at ICLR 2026
The final trajectory consists of 121 nodes in total. We provide comprehensive review of its reasoning process: it begins by copying the givens, constructing segment sums, and recording the reflection, analogous to Nodes 1-19 in the first trajectory. It then attempts parametric area strategy via trigonometric parametrization but halts after approximately 20 steps. Subsequently, searches over many polygon decompositions of heptagon AFN BCF. repeatedly proposing and discarding formulas clear evidence of exploratory
search-untee it identifies the structural invariant AD: DE EB AF FG: GC' = 1: 4 2, from which it correctly infers DF || EG BC. At this stage, the strategy shifts to similarity/area-ratii approach for triangles sharing angle A and suc- cessfully derives the area of AABC. Finally, the strategy switches once more to the reflection-swap method, yielding the correct answer.
B.2 AN IMO-LEVEL EXAMPLE DAG
There are several ways in which an IMO-level proof can fail the logical-closeness test even when substantial portions of the argument correct:
a model may solve the fixed-poing subproblem and mistake fixed points for all valid starting values;
a model may prove the forward dynamics for N E S but omit the complementary necessity argument for N & S:
model may derive both macro-branches but never fuse them into single final characterization.
For such problems, lemma-level DAG is more informative than a step-level DAG. We illustrate this with the following problem from IMO 2025.
IMO 2025 Q4 Problem
A proper divisor of positive integer N a positive divisor of N other than N itself.
The infinite sequence 01, a2 consists of positive integers, each of which has at least three proper divisors. For each 2 1, the integer an+1 is the sum of the three largest proper divisors of On,.
Determine all possible values a1-
The rigorous solution shows that the valid starting values are exactly
S = {N: (2
(N)aa is odd, ua(NN 2 [2(N++1 NY.
The resulting lemma-level task-specific DAG drawn from C1 Claude Opndee-Opus444 is shown in Fig.
We summarize each node's conclusion below.
1 Defines the dynamical map f(N), validity of starting value, and the candidate set S.
2 Proves the divisor-pairing identity f(N) N 1 53
3 Solves 1 + 1 + = in strictly increasing integers and obtains the unique triple 3,63.6).
4 Characterizes the fixed points: S(N) N if and only if N 2 36. m with b 2 and ged(m, 30) = 1.
5 Shows that odd inputs stay odd and strictly decrease under f.
Shows that when 12 N and
one has f(N)
13N and (02, Uz) (v2 2, U3 1).
12
7 Proves sufficiency: every N S is valid.
8 Proves forward invariance of the complement: N S f(N) $ S.
9 Proves necessity: every N & S eventually becomes invalid.
Correct sink: the valid starting values are exactly the elements of S.
L' Incorrect sink: the valid starting values exactly the fixed points of f.
22

---

Published as a conference paper at ICLR 2026
1
2
3
5
4
L'
8
Figure 7: Lemma-level task-specific DAG for IMO 2025 Q4. The green sink is the correct theorem, while the red sink is a plausible but incorrect premature termination.
The green sink requires both macro-branches of the proof. On the left, Nodes 2-4-6-7 show that numbers in S are not necessarily fixed at time O, but repeated use of Node decreases U2 by 2 and uy by 1 until the orbit reaches the fixed-pe -point family from Node 4. Concretely, if
N 2 3 E S
(b + 1, ged(m, 30) 1).
then after applications one obtains
13
(*(N)= =
N 2 3
13*m,, .1
12
which lies in the fixed-point family and therefore generates an infinite valid orbit.
On the right, Nodes 5, 6, 8, and 9 show that the complement of S cannot support an infinite orbit. Node keeps every iterate outside S. Then Node 9 selects the minimum element of the orbit and proves that any local growth pattern must fall into either the short-lived (2, 3, 5) regime or the (2, 3, 4) regime; both eventually force strict descent, contradicting fell-foundedness of N.
The incorrect sink L' models natural but wrong termination. After Nodes 2, 3, and 4, a model might conclude that the only infinite sequences are the fixed points of f. This is coherent subproof, but it misses the genuinely valid preperiodic starting values in S with 22 (N) 2 3, which are not fixed at time 0 and only flow to a fixed point after finitely many applications of Node
This failure mode is especially useful for evaluating logical closeness. A trajectory ending at T'' has solved substantial subproblem-the complete classification of fixed points-yet it omits lemmas that distinguish fixed points from all valid starting values. In other words, L' is not random wrong answer; it is mathematically polished but globally incomplete termination.
At the DAG level, the proof therefore separates into a left sufficiency branch and right necessity branch, both which are indispensable for the correct sink. logically closed trajectory must collect enough ancestors to justify Node L, rather than stopping soon as Node 4 is established. For IMO-level arguments of this type, the lemma-level DAG exposes the key structural distinction much more elearly than long list of atomic algebraic steps.
23

---

Published as a conference paper at ICLR 2026
C
EXAMPLE DAG-MATH FORMATTED CoT
Example DAG-MATH Formatted CoT for the logarithmic count problem
Step 1
Edge: Restate the target equation from the problem statement, 2 log(2 1) log k, which the central equation to solve for x in terms of k.
Parents: Null
Node: 2 log(2 1) log k.
Step 4
Edge: Since the left-hand side of the equation in Step 1 contains log(æ - 1), the domain restriction for logarithm requires 1 0, i.e., x >> 1.
Parents: Step
Node: log(x 1) requires æ >>
Step 8
Edge: Using Step 7, the candidate solutions are + vl; Step 4 requires æ > 1, and Step ensures 0, so Vk > 0, making Vk invalid. Therefore, + vk is the only admissible solution.
Parents: Step 4,5,7
Node: 1 1+ vk is the only admissible solution.
Step 9
Edge: From Step each positive integer yields exactly one solution x + Vk. Step requires k 0, and Step restricts & to integers in [1, [003. Therefore, there are 300 valid k values, satisfying Step 3's requirement exactly one solution.
Parents: Step 2,3,5,8
Sink Node: There are 300 valid values for
D BENCHMARK CONSTRUCTION AND VALIDATION
In this section, we detail our three-stage strategy for benchmark construction with stage-wise vali- dation method.
We prompt GPT-o4-mini to generate only the Node set, one step at time, using the in- structions in Appendix D.I] To enhance correctness, we adopt supervised setup that provides both the problem and its correct solution. Because standard CoT can skip arithmetic or combine multiple results in single step, we require that each Node consist of exactly one sentence containing single mathematical or logical assertion (i.e., one primitive action per step) normalize granularity.
Stage 1:
The intermediate stepwise correctness and final answer correctness are validated using both SymPy and LLM-as-Judge (via GPT-4o; if the final answer or any intermediate assertion is incorrect, the complete Node set rejected and resampled. We iteratively repeat this procedure until passing all checks.
Validation
Stage 2: Given the verified Node set from Stage we prompt GPT-o4-miie (per Appendix D.2 to assign, for each Node, minimal set of direct Parents sufficient to derive it via primitive opera- tion. We enforce acyclicity and well-typed arity constraints, then assemble the full DAG.
Validation 2 The resulting DAG is checked for logical closeness relative to the sink node; checks fail, all dependencies are resampled. We repeat this procedure for times. If the DAG is still not closed, then go back to Stage 1 to regenerate Node
24

---

Published as a conference paper at ICLR 2026
set. If the Node set of second turn still fails to close for 5 times, filter out the problem. Next, we employ GPT-o3 to evaluate the correctness dependency structure. Stage 3: Conditioned ated [Parent(s), Node] pairs, we prompt gen-
the gener-
Table 2: Benchmark Construction Success Rate by Problem Difficulty
3 ( Appendix(D.3) crate the Edge content that justifies how each Node is inferred from its Parents. The justification must introduce no new facts be- yond the problem statement and the cited Parents. After this step, the triplets are merged into gold-standard DAG-MATH formatted CoT in forward order.
Difficulty
Total
Success
Rate
(0, 1]
124
119
96.0%
(1, 2]
363
343
94.5%
(2, 3]
197
182
92.4%
(3,4)
746
665
89.1%
(4
1304
1072
82.2%
Table reports the success rate over prob- lem difficulty after three-stage construction with validation on Omni-MATH. We limit the problem difficulty within 6 to ensure the reliability of benchmark (IMO-Ievel problem beyond 6).
65.
649
498
76.7%
D.1
PROMPT FOR STAGE
Stage Instructions for Refined Step-by-Step Answer
Task:
You expert in mathematical logic and reasoning. Your job is to take rough multi-step step math solutions and rewrite them in a detailed, structured, and logical step-by-step format. Follow these guidelines:
Each step must be exactly one sentence, and that sentence may contain only one mathematical or logical assertion.
Do not combine multiple assertions in one step.
Show every tiny inference- setting up equations, solving for variables, converting units, etc.-cach in its own step.
Any fact, formula, problem detail, or intermediate result must itself be stated in its own individual step.
Avoid including irrelevant steps that do contribute the solution.
The final step should be the answer statement in the form: The final answer is \boxed(xxx [xxx].
Use LaTeX format enclosed in dollar signs for all mathematical expressions.
Problem: (problem statement]
Solution: foriginal step-by-step solution]
Refined Step-by-Step Answer:
D.2
PROMPT FOR STAGE 2
Stage Instructions for Step Dependency Analysis
Role and Objective
You are expert in mathematical logic and stepwise reasoning. Your primary role is to analyze the detailed solution steps for a mathematical problem and annotate each step with its minimal set of direct dependencies. Instructions
*GPT-o3 is a stronger model than GPT'-04-m" 101--44-minn mi
WWe choose Qwen3 provides clearer description of the inference from Parents Nodes than GPT-04.
25

---

Published as a conference paper at ICLR 2026
1. Input Structure:
Each problem appears JSON object with fields:
problem.text (string): Problem description. final.answer (string): The solution.
steps (array): Each is object containing:
step_id (integer): Unique step identifier.
text (string): Reasoning or mathematical operation.
2. Dependency Annotation:
Add a di rec.reett.eeee werpttddeeedentttttepeee field for every step.
For each step:
If stated directly from the problem statement, assign null.
Otherwise, list the minimal, directly required prior step_id values in ascending
order, e.g., [2, 31.
Dependency Rules:
1. Every dependency ID in direct wwwendent. steps MUST exist in the origi- nal set of step-id values of the input.
2. Every listed dependency must be prior step its step_id must be strictly less than the current step (i.e., no self- or future-dependency is allowed).
3. Self- Validation for Step Closure:
After assigning dependencies, check for unclosed intermediate steps:
An unclosed step is any non-final step not referenced in
d. cer.tt.deendent.stte
by any subsequent step.
If any exist, refine dependencies until all intermediate steps are "closed" (each is used at least once by a later step).
4. Post-action Validation:
After annotating dependencies and closing all steps, validate that each intermediate step is referenced at least once by a subsequent step before finalizing the output. If any issues are found, self-correct and repeat the closure process.
5. Structured Output and Consistency:
The number of steps in the structured output MUST match exactly the number of steps in the original input.
Application Process
When presented with new problem in valid JSON:
1. Iterate through steps in order of step-id.
2. For each step, determine
relies on previous steps or the problem statement and as specified.
annotate di direct_depen wta.reetddeenddnt.stttee
3. Validate dependencies (all dependency IDs exist; all point a prior step).
4. Check for unclosed steps and adjust as necessary.
5. Validate closure and present the final modified problem.
Error Handling
If the input is malformed (e.g., required fields missing, step id missing, step id values not strictly ascending):
Return only JSON object with error field and concise message. For ample: "error": "Input data malformed: missing step.id in step 3."
Output Format
Output the structured response with all steps mirroring the original order and count, each annotated with di diett.ddeeeeeeeeeeee www.re.dppedddttsseppe If there is an error, output only the error object as described.
(JSON text of refined step-by-step answer with problem statement from Stage 1}
26

---

Published as a conference paper at ICLR 2026
D.3
PROMPT FOR STAGE 3
Stage Instructions for Constructing Edge Inference
Role and Objective
You serve as a mathematics solution explainer. For each step solved mathematics problem (provided structured JSON), generate detailed and explanatory justification paragraph (edge string) clarifying the correctness and logical progression.
Instructions
For each step in the provided "steps" " array within the problem JSON, write edge string that satisfies the rules below.
directt.com wewprttdededdeeettdteeeeee
is not null, explicitly justify how
support the current one, citing their IDs. If null, note that the step is given by the problem statement or background knowledge (definition, the- orem, lemma, fact, general knowledge not originally in the problem statement).
di drrecttcce rreec..dppedeet.steeee.
Clearly explain the mathematical logical principle, operation, or procedure used (e.g., counting rule, algebraic manipulation, definition, theorem, arithmetic operation) applied in the step.
Strict Rule: Do not omit any referenced dependency, the edge MUST include every step di rect wtw.rreecceeedeeeeee hependent..seege
Clearly illustrate why we need do this step and how we arrive at this step (acts like planning).
For numeric calculations, perform the arithmetic clearly and include brief sanity check appropriate.
Use neutral, present-tense, explanatory sentences with active voice.
Ensure each justification is self-contained needing only the current step and referenced prior steps to be understandable.
Context
Input:
JSON object representing solved math problem with array of steps, each with step-id, text, and di www.eeedppeedeet.ste....mm
Output: Return only the edge for each step, ordered match the original steps array.
Do NOT include internal model reasoning or any execution commentary in the output.
Demonstration Example
Here is a demonstration of the style and format of the edge field. You need to follow this style and format.
"We plan to exclude numbers divisible by 2, 3, or 5. To do that systematically express the count of multiples of each relevant divisor in the domain. The number of multiples of up is | Applying that with 999 (from Step 1) and & = 2 gives [999/2]. Writing it floor expression is precise and handles the non-divisible endpoint gracefully.""
first
"Since numbers divisible by 3, and 5 are overlapping, we need subtract the count of numbers divisible by pairwise combinations of 2, 3, and 5 then add back the count of numbers divisible by all three, i.e., inclusion-exclusion The least common multiple and is 6, so count multiples of 6. Recall we have 999 integers in the domain from Step up to 999 via [999/6]. This uses the same floor-division approach but applied to the least common multiple of the pair."
count multiples
"ee convert the expression in Step 8 into concrete number to use in later arithmetic. Compute 999/6- = 166.5; taking the floor yields 166. Quick cross-check: 166 x 996, so the last multiple is exactly 996."
"We now have all the building blocks: counts of singles, pairwise intersections, and the triple intersection. The immediate plan is to apply the inclusion-exctusion formula for
27

---

Published as a conference paper at ICLR 2026
three sets compute the size of the union A U U C. where A multiples of 2, B multiples of 3, C = multiples of 5. Inclusion-excluson avoids overcounting and is the rig-
orous combinatorial tool for unions of overlapping sets. The three-set inclusion-xxxlusiion identity is UAU BUC)
|A] + B + [C] - (lAn B| |ANC] | Substitute the numerical values computed from Steps 3, 5, 9, 11, 13, 15.: 499 333 + 199 - (166 + 99 66) + 33. Writing it explicitly 499 - -33 + 199 166 -99 - 1899-6644 +3--3 lays out the arithmetic to performed next."
"Cite the standard definition: has exactly one positive divisor (1 itself), is neither prime (requires two distinct divisors) nor composite (requires more than two). In parti- tioning the 266 numbers not divisible by 2,3,5 into primes and composites, we must also handle the special case I, which is counted among the 266 but is neither prime nor com- posite; failing to account for would misclassify one element."
"We simplify the complex expression from Step 12, which is (48 x 15) (320 + 8) + 27. The order of operations dictates multiplication and division before addition or subtraction. First compute 48 15 720. Next compute 320 8 40. Substituting these back into the expression gives 720 - 40 + 27. This reduction preserves equivalence while making the next hiep-performing the remaining subtraction and addition-more straightforward."
Core Language Style Requirements
Match the tone, sentence flow, and level of detail in the demonstration examples provided below.
Write way that reads naturally to human reasoner, not like a formal audit log.
Self- Velf-Valiittio
After each edge is generated, validate that whether it includes every step in direett deoee.deeeneentt stredenttssess.....e not, you need to re- re-generate the edge for the step. Notice that you need to check for all steps, not just a subset of steps.
IMPORTANT:
For each step, internally determine the applicable mathematical principle, identify depen- dencies, clarify evaluation logic, and succinetly state both justification and role in the broader problem.
Clearly state mathematical justifications, and follow the required language style. numeric evaluation is performed, confirm a brief sanity check is present.
Verbosity
edge should be detailed, allowing for expansion if the step complex or multi-pan part.
Stop Conditions
Complete when every step has a well-justified edge field, following all style and content rules. Escalate for ambiguous incomplete input only.
Output Format
Return only a edge field for each step populated as described. Do not include extra fields, wrappers, commentary.
EXAMPLE ISON OUTPUT:
"edges":
" "step_i id"; 1, "edge": "We define ....
"step_ic" 2, "edge": "Building on the definition of ..."
"step_id": 3,
28

---

Published as a conference paper at ICLR 2026
"edge": "Using the expression for
{JSON text of refined step-by-step answer with problem statement from Stage 1 and dependencies from Stage 2}
E HUMAN EVALUATION OF GOLD-STANDARD BENCHMARK
To validate the reliability of the DAG-MATH benchmark and address potential concerns regarding the subjectivity of human or LLM-annotated dependencies, we designed an algorithmic human eval- uation pipeline. This approach treats the logical structure of mathematical solution as isomorphic computational graph, where "dependencies" correspond the flow of variables in executable program.
Pipeline We formalize the validation process through the following four-step pipeline, applied to random sample of 50 problems from the benchmark:
1. check basic stepwise correctness and final answer correctness by human,
2. map each natural language step (node) to functional line(s) of SymPy code by human,
3. execute the complete code to test validity then extract the computational graph of code. the code for step_k referenced the variable step-j, record computational depen- dency.
4. compare the set of computational dependencies extracted from the code against the direet.deperdent.ster..
For steps which cannot be converted to SymPy code such declarative constraint (e.g.. "an arrange- ment of hats corresponds to permutation of the three people"), or strategy (e.g., "we propose to count the total arrangements and subtract the invalid ones"), validate the dependencies by human knowledge. We provide a complete human-evaluated example for illustration in Appendix F.
Results All samples pass the correctness check in Step and 49/50 samples pass dependency check. The sample that not pass contains one irrelevant node, i.e. "Lauren plays basketball with her friends", which is closed but has very weak connection its child ("Lauren makes 10 baskets"), Our human evaluation confirms the benchmark's s high reliability, achieving 100% execution correct- ness and 98% dependency accuracy. with the sole outlier attributable weak semantic link in narrative context step rather than a structural reasoning failure.
E.1 HUMAN EVALUATION EXAMPLE
Rato of Distance Problem
Natascha cycles times as fast as she runs. She spends 4 hours cycling and hour running. What is the ratio of the distance that she cycles to the distance that she runs?
from sympy import symbols, simplify, Rational
def solve_problem_4200
Step 1: "Natascha cycles times as fast as she runs. Dependencies: [mull]
step_1 =
Step 2: "Natascha spends hours cycling." Dependencies: [null]
10
II
step_2 =
13
Step "Natascha spend's hour running."
29

---

Published as a conference paper at ICLR 2026
Dependencies: [nall]
15
step_3
16
17
step 4: "Let represent Natascha's running speed in km/h." Dependencies: [null] We initialize the symbolic variable. step_4 synbols('r))
20
21
22
step 5: "Cyeling speed is 3r km/h." Dependencies: [1, 4 Muitiplier (step_1) Running Speed (step_4) step_5 step_1 step_4
25
26
Step 6: "The formula for distance... is d=vt." Dependencies: [null]
29
We define the distance function here. stop_6 lambda V, V
30
31
step 7: "Running distance... yields = = Dependencies: [3, 4, 6]
34
Apply Formula (step_6) 6) to Speed (step_4) 4) and Time (step_3) step_7 step_6(v=step_4, t=step_3)
35
36
Step 8: "Simplitying... running distance Dependencies: 17]
38
39
simplify previous result step_ simplify(step__)
40
Step "Cycling distance... yields 3r 4." Dependencies: (2, 5, 6]
43
44
Apply Formula (step_6) 6) to Speed (step_5) 5) and Time (step_2)
45
step_ stop_6(v=step_5, t=step_2)
47
step 10: "Simplifying... cyeling distance as 12r. Cependencies: [9] Simplify previous result
48
49
step_10 simplify(step__)
52
Step 11: "Ratio... is 12r : r." Dependencies: 18, 10]
53
Construct the fraction (Ratio) using Running (step_ 8) and Cycling ( step_10) step_11 (step_10, step_8)
55
36
57
Step 12: "Simplifying... gives 12:1." Dependencies: [11] in the ratio
Divide the ratio_val step_1l101 stlp_ step 12 = simplify (ratio_val)
60
61
62
Step 13: "The final answer is (boxed(12:1). Dependencies: [12] Pormat the result from step_12 12 step 13 = E"The final answer is \booxed| | [[step_12]:]]] 12/:111.>
65
66
return step 13
30

---

Published as a conference paper at ICLR 2026
F FEW-SHOT PROMPT FOR DAG-MATH FORMATTED CoT
Instructions for DAG-MATH Formatted CoT Generation
Role and Objective
You are an expert mathematical reasoner and logician. For the given problem, you produce single, valid JSON object containing list of solution steps. Each step in the list must be an object with the following four fields: step-id, edge, direct_dest beacctddppedeet.steege Requirements
and node.
Each step has exactly:
step_id (int; unique; strictly increasing)
edge (sentences; describe why/how this step follows; reference prior steps with Step's step_id tags, e.g., Step 1, Step 3)
State the goal of the current step.
Cite the minimal direct dependent previous steps used, with how these steps are used for the current step. IMPORTANT: every direct dependent step must be cited in the form Step's step-id.
State clearly the mathematical principle being applied (e.g.. inclusion- exclusion, algebraic manipulation, definition), which turns those inputs into the asserted output.
di direct__eeeeddentssttee
(array of ints or null)
This field must contain list of step_ids representing the minimal set of prior steps directly used to derive the current step in edge.
The list must be in ascending order (e.g., [2, 51).
If step is fact taken directly from the problem statement, this field should
be null.
Topological order: every dependency ID < current step-id.
Closure: every nonfinal step's step_id must appear in some later step's direct dependent steps.
node (one execution sentence)
Each step's node field must contain single, atomic sentence making exactly one logical assertion (e.g., stating an equation, defining variable, presenting calculation result) which acts the results inferred from edge.
All information, including facts from the problem statement and intermediate results, must be broken down into these atomic steps.
Avoid including irrelevant steps that do not contribute to the solution.
The final step must be the answer statement in the form: "The final answer is
Global Constraints
Use LaTeX format enclosed in dollar signs for all mathematical expressions.
Your entire output must be a single, valid JSON object. Do not include any text or commentary outside of the JSON structure. You will be provided with high-quality examples to demonstrate the required format and reasoning style.
Demonstration Examples
(Gold-standal demonst examples]
Bad Examples
1. The example below is bad since Step's step_id are missing in edge.
" "steps":
31

---

Published as a conference paper at ICLR 2026
"s "step_id" = 36,
"edge": "Using the confirmed digit values...", Sbirect_dependent__e 8, 15, 26, 32, 35
"node": "The sum of the digits sK + L + M + N$ 1,
is $0 + 5 9$."
2. The example below is bad since plural "Steps 8, 9, and 10" is used in edge instead singular "Step 8, Step 9, and Step 10".
"steps":
"step_id" 11,
"edge": "From Steps 8, 9, and 10, we have...", "earer__deeendet_sttpp"""" 8, 9, 10
}, "node": "Define d = b and
Then
the equations become: (a + e)
+ 2k,
(a d) -3 6k, a * (e d) -4 + 4k.
Problem:
[Test problem statement]
Solution:
G PROMPTS FOR SENSITIVITY ANALYSIS
G.1 PROMPT WITH DIFFERENT FORMAT
Instructions for DAG-MATH Solution Generation
Role and Objective: You are an expert mathematical reasoner and logician. For any given problem, you must produce single, valid JSON object containing list of solution steps.
Requirements:
Output one JSON object: { "steps": [ ...]
Each step specification:
32

---

Published as a conference paper at ICLR 2026
Field Name
Data Type
Requirements
Description
step id
Integer
Unique identifier for each step in ascending order
Must be unique
Must be strictly increasing
thinking
String
Reasoning that explains the logical derivation of this step
Describe why/hww this step follows
Reference prior steps as Step step_id se (e.g., Step 1,
Step 3)
Must include:
Goal of current step
Citation of minimal di-
rect dependent steps with how they're used Mathematical principle being applied
direct
List OR
dependent.
Minimal set of immedi- ate prior steps required for current step
List step.id values
steps
null
Must be in ascending order
(e.g., [2, 5])
Use null if fact from prob- lem statement
Every dependency ID < cur-
rent step -i
Every non-final step must
appear in some later step's
text
String
Execution statement pre- senting the conclusion of this step
Single, atomic sentence Makes exactly one logical assertion
Acts as result inferred from thinking
Final step format: "The final answer is ...."
Every non-final step's step_id must appear in at least one subse- quent step's di direct.dependent.ster.. array.
Closure Constraint:
Global Constraints:
Use LaTeX format enclosed in dollar signs for all mathematical expressions
Output must be single, valid JSON object only
No text or commentary outside the JSON structure
High-quality examples will be provided demonstrate the required format and reasoning style
Demonstration Examples
(Gold-standard demonstration examples]
Bad Examples
[Bad demonstration examples]
33

---

Published as a conference paper at ICLR 2026
G.2 PROMPT WITH REPHRASING
Instructions for DAG-MATH Solution Generation
Role and Objective: Your function is that of specialist in mathematical reasoning and logical analysis. When presented with any problem, your task is to generate a single, properly-formed JSON object that contains array of solution steps. Within this array, every step must be represented as an object containing these four specific fields: step_id, thinking, direct..ependent.stee.
and text.
Requirements: Generate a JSON object with this structure: "steps": [ [...] }. The specifications for each step as follows:
step (integer value; no duplicates; monotonically increasing sequence)
thinking (prose description; articulate the reasoning and methodology behind this step; make references to previous steps using Step step id notation, such as Step 1 or Step 3)
Articulate the objective that this particular step accomplishes.
Identify the smallest of immediately preceding steps that are utilized, explaining the manner in which these steps contribute to the current one. CRITICAL: each immediately preceding step must be mentioned using the Step step_id format.
Explicitly state the mathematical concept or operation being employed (e.g.. the prin- ciple of inclusion-exclusion, manipulation of algebraic expressions, application of definition), which transforms the referenced inputs into claimed result.
gireet..ependent.sstt.
(list of integers or null value)
This field is required hold array of step_id values that represent the smallest collection of prior steps that must be available to derive the present step.
The array must maintain ascending numerical order (for instance, [2, 5]).
When step represents information extracted directly from the problem description, this field should contain null.
Topological ordering requirement: each dependency identifier < the current step-id.
Closure property: each non-terminal step's step_id is required to be listed within the direct wwwpeeddddeeddetttseeee _steps of at least one subsequent step.
text (single sentence for execution)
The text field of each step is required to contain a single, indivisible sentence that logical claim (such as declaring equation, introducing vari- able definition, or stating a computational outcome) which serves as the conclusion derived from thinking.
makes precisely
Every piece of information, encompassing facts extracted from the problem descrip- tion and intermediate computational results, is required to be decomposed into these indivisible steps.
Exclude any irrelevant steps that fail to advance the solution.
The terminal step is required to take the form of an answer declaration: "The final answer
Global constraints: Employ LaTeX notation surrounded by dollar signs for every mathe- matical expression.
The entirety of your output required to be single, well-formed JSON object. Exclude any textual content or explanatory remarks beyond the JSON structure. High-quality exemplars will be supplied to illustrate the expected format and reasoning approach.
Demonstration Examples
(Gold-standard demonstrraion examples]
34

---

Published as a conference paper at ICLR 2026
Bad Examples
{Bad demonstration examples]
H PROMPTS FOR DAG PARSING
H.1 PROMPT FOR THINKING LLMS
Instructions for Step Dependency Analysis
Role and Objective
You are an expert in mathematical logic and stepwise reasoning. Your primary role to analyze the detailed solution steps for a mathematical problem and annotate each step with its minimal set of direct dependencies.
Begin with concise planning checklist (3-7 bullets) of what you will do; keep items con- ceptual, not implementation-leve. Instructions
1. Input Structure: Each problem appears JSON object with fields:
problem.tex: (string): Problem description.
steps (array): Each is an object containing:
-stepiid (integer): Unique step identifier.
text (string): Mathematical operation/action of this step-
2. Dependency Annotation:
Add direct dependent steps for every step.
For each step:
If derived only from the problem statement, assign 'null'.
Otherwise, list the minimal, immediately required prior step-id idd values ascending order, e.g.. '1, 31
3. Dependency Rules:
Every dependency ID in direct _dependent.steps MUST exist in the original set of step-id values of the input.
Every listed dependency must be a prior step-its step_id must be strictly less than the current step (i.e., no self- or future-dependency is allowed).
4. Structured Output and Consistency:
The number of steps in the structured output MUST match exactly the number of steps the original input.
The output must strictly follow the schema DependencyyGraph.
Error Handling
1. If the input is malformed (c.g., required fields missing, step id missing, or s step.id values not strictly ascending):
2. Return only a JSON object with an error field and a concise message. For exam- ple:
{ ("error": "Input data malformed: missing step_id in step 3.")
Output Format
Output the structured response with all steps mirroring the original order and count, each annotated with direct wiirect.dpeeddnt.steee... If there is an error, output only the error object described.
35

---

Published as a conference paper at ICLR 2026
H.2
PROMPT FOR NON-THINKING LLMs
Instructions for Step Dependency Analysis
Role and Objective
You are an expert in mathematical logic and stepwise reasoning. Provide a reason for each step explain its minimal set of direct dependencies then annotate each step with its depen- dencies.
Begin with concise planning checklist (3-7 bullets) of what you will do; keep items con- ceptual, not implevlntation-levell Instructions
1. Input Structure: Each problem appears JSON object with fields:
problem.text (string): Problem description.
steps (array): Each is an object containing:
step_id (integer): Unique step identifier.
text (string): Mathematical operation/action of this step.
2. Dependency Annotation: For each step, produce:
reason: An explanation justifying the direct dependencies, referencing step
IDs or the problem statement.
di recreeet_eeeee wtwpctddeeeeedeetssteep.
If derived only from the problem statement, assign 'null'.
Otherwise, list the minimal, immediately required prior step.id values ascending order, e.g.. '1, 3]".
3. Dependency Rules:
Every dependency ID in direct direct_dependent _dependent_steps MUST exist in the original set of step-id values of the input.
Every listed dependency must be a prior step-its step-id idd must be strictly less than the current step (i.e., self- future-dependency is allowed).
4. Structured Output and Consistency:
The number of steps in the structured output MUST match exactly the number of steps the original input.
The output must strictly follow the schema Dependencyyrrphh.
Error Handling
1. If the input is malformed (e.g., required fields missing, step_id missing, or step.id values not strictly ascending):
2. Return only a JSON object with an error field and a concise message. For exam- ple:
("error": "Input data ma halforeed: missing step_id id in step 3.")
Output Format
Output the structured response with all steps mirroring the original order and count, each annotated with direct weweeccdddeeddettstteee If there is an error, output only the error object as described.
Demonstration Example
(Human-wris tten demonstration example)
I ADDITIONAL RESULTS FOR EVALUATION
The results for final-and insler accuracy (PASS@) 1) and empirical mathematical reasoning ability ( three benchmarks across five LLMSs are reported in Table The averaged graph-level statistics
36

---

Published as a conference paper at ICLR 2026
Table 3: Final-answer accuracy (PASS @ 1) and empirical mathematical reasoning ability (R) across three math benchmarks. Parentheses show the gap (A PASS@1 -R)-
Model
AIME 2025
BRUMO 2025
HMMT 2025
PASS@1 @1 1
R. 4)
PASS@
R (4 4)
PASS@1
R. 4)
Gemini-2.5-F
52.4
17.0 (35.4.)
63.4
20.7 (42.74)
38.5
5.7 (32.8.)
Gemini-2.5-F-L
37.4
15.9 (21.5L)
43.2
17.8 (25.4L)
28.8
7.5 (21.3))
GPT-4.1
26.5
16.8 (9.7.)
33.3
22.8 (10.5L)
11.8
(5.30)
GPT-4.1-M
30.5
20.9 (9.6.)
34.4
24.6 (9.81)
14.3
7.4 (6.9L)
Qwen3-30B
43.1
15.8 (27.3L)
46.8
21.8 (25.0L)
27.3
5.6 (21.74)
Std
10.3
2.1
12.2
2.5
11.0
0.9
Table 4: Averaged graph-level statistics of sampled DAGs across selected LLMs on AIME 2025.
Model
Class
#nodes
#edges
density
in
out
All
32.8
48.9
11.2%
4.3
7.0
Gemini-2.5-F
Incorrect
35.6
53.3
10.6%
4.6
8.6
Correct
30.2
45.1
11.6%
4.1
5.5
Perfect
23.3
30.8
13.0%
3.3
3.6
All
33.0
54.0
13.4%
3.6
9.7
Gemini-2.5-F.
Incorrect
40.5
68.6
11.9%
3.9
12.8
Correct
21.5
31.6
15.7%
3.2
4.8
Perfect
16.1
21.4
18.4%
3.0
3.2
All
17.8
21.4
16.2%
2.6
3.0
GPT-4.1
Incorrect
18.4
22.2
15.6%
2.6
3.1
Correct
15.9
19.3
17.5%
2.7
2.9
Perfect
14.1
16.8
19.0%
2.5
2.4
All
22.8
31.3
14.2%
3.2
4.0
GPT-4.1-M
Incorrect
25.0
34.7
13.3%
3.3
4.3
Correct
17.9
23.6
16.6%
3.0
3.4
Perfect
16.5
21.5
17.4%
3.0
3.1
All
21.4
31.1
16.0%
3.3
4.9
Qwen3-30B
Incorrect
23.4
34.3
14.9%
3.4
5.5
Correct 18.9
27.2
17.2%
3.1
4.1
Perfect
14.7
19.6
20.2%
2.9
3.0
for BRUMO 2025 and HMMT 2025 are reported in Tables 5ndd respectively. The overall trend similar the analysis Section Additionally, we can obtain the following findings:
The change graph-level statistics monotonic A. The variations in the #nodes, Hedges, density, and maximum out-degree from Correct to Perfect increase monotonically with the gap A between PASS@) and R. When A is small, the statistics of these two classes are nearly identical.
Graph-level statistics remain similar across the four classes when raw accuracy is low. In particular, when PASS@ is low, their variations across classes minimal.
J DISCUSSION ON FUTURE IMPROVEMENTS
Our proposed metrics can provide a principled foundation for future work aimed improving both search-based inference and L.LM's post-training.
37

---

Published as a conference paper at ICLR 2026
Table Averaged graph-level statistics sampled DAGs across selected LLMs on BRUMO 2025.
Model
Class
#nodes
#edges
density
dmax
26.6
39.8
13.0%
4.1
5.3
Gemini-2.5-F
Incorrect
29.2
47.4
13.0%
4.8
6.2
Correct
25.1
35.9
13.1%
3.8
4.8
Perfect
20.5
26.1
14.1%
3.0
3.2
All
27.9
47.7
15.5%
3.8
8.3
Gemini-2.5-F-L
Incorrect
33.2
61.5
14.5%
4.0
11.1
Correct
21.2
30.4
16.7%
3.4
4.8
Perfect
14.1
17.4
20.1%
2.6
2.9
All 14.9
18.1
19.4%
2.4
2.9
GPT-4.1
Incorrect
15.9
19.6
18.4%
2.5
3.0
Correct
13.0
15.1
21.4%
2.3
2.5
Perfect
12.0
13.8
23.0%
2.3
2.3
All
17.1
24.1
18.7%
3,0
3.7
GPT-4.I-M
Incorrect
18.6
27.2
17.7%
3.1
4.1
Correct
14.3
18.3
20.6&
2.7
3.1
Perfect
13.1
16.6
22.1%
2.7
2.9
18.4
27.7
19.8%
3.4
4.7
Qwen3-30B
Incorrect
21.7
34.4
17.8%
3.7
5.7
Correct
14.7
20.1
22.1%
3.1
3.6
Perfect
12.1
15.4
25.3%
2.8
3.0
Table 6: Averaged graph-level statistics of sampled DAGs across selected LLMs on HMMT 2025.
Model
Class
#nodes
#edges
density
max in
max
All
36.8
60.4
10.9%
4.7
7.9
Gemini-2.5-F
Incorrect
36.6
61.4
11.4%
4.7
8.4
Correct
37.4
59.8
10.1%
4.9
7.1
Perfect
30.1
48.4
12.0%
6.1
All 35.8
63.0
14.0%
4.1
11.2
Gemini-2.5-F-LL
Incorrect
40.4
73.3
13.4%
4.1
13.1
Correct
26.5
42.7
15.2%
4.0
7.1
Perfect
16.8
25.9
20.6%
3.9
4.2
All
17.0
20.7
17.8%
2.5
3.2
GPT-4.1
Incorrect
16.9
20.8
17.8%
2.5
3.1
Correct
17.5
20.6
17.4%
2.6
3.5
Perfect
14.7
17.3
19.8%
2.5
2.7
All
21.1
30.2
16.0%
3.0
4.2
GPT-4.1-M
Incorrect
21.1
30.2
15.9%
3.0
4.1
Correct
21.1
30.5
16.6%
3.0
4.4
Perfect
17.2
24.3
19.4%
2.9
3.6
All
22.8
34.6
16.1%
3.6
5.6
Qwen3-30B
Incorrect
22.8
34.5
16.4%
3.6
5.7
Correct 22.8
35.0
15.2%
3.7
5.5
Perfect
18.7
28.5
18.8%
4.6
5.0
1. Guiding Search Policies: Our framework suggests that logical closeness can serve as a reward to guide graph- based search algorithms like Monte Carlo Tree Search (Pan et al.) (225)) or Tree-of- Thhuuhhss Yao et al. 2023). Instead of relying solely on random branch- ing value function, search policies could prioritize reasoning paths that maintain high
38

---

Published as a conference paper at ICLR 2026
logical coherence. For instance, by favoring branches that close open dependencies or by pruning highly speculative trajectories early. This offers promising avenue to make search more efficient and goal-directed, steering it toward not just correct but also well-structured solutions.
2. Informing Reward Design for RL: The AUC curves inspire a curriculum learning strategy for training reasoning models via RL. One could progressively increase the required level of logical closeness during training, starting from a regime that rewards basic correctness and gradually guiding the model toward the "sweet spot" of perfect reasoning identified by our framework.
K EXTENDED EXPERIMENTAL STUDIES
K.1 STATISTICAL TESTS FOR PASS @ AND PRR UNDER LARGE SAMPLE
In this section, we aim to establish statistical test for the difference between PASS @1 I and PRR. We extend the sample size from 32 to 128 for Gemini-2.55 ash, Gemini-2 Gemini-2.5-Flase 5-Flash-Iite, GPT-4. 4.4. 1, and GPT-4. 1-mnnn on AIME 2025. For mean gap A 1-PRR, we compute the 95% confidence interval for a binomial proportion using the Wilson score method for each model.
The results are reported Table All confidence intervals for A exclude zero with tight bounds, confirming with high confidence that the observed gaps between PASS @ I and PRR are statistically significant and substantial in magnitude. Additionally, we note that the statisties from this extended sample align closely with our original results in Table
Table 7: Results of PASS@1, PRR, A, and associated confidence interval as CI(A) across four selected models on AIME 2025.
Model
PASS @1 1
PRR
A
CI(A)
Gemini-2.5-P
53.3%
17.1%
36.3%
[34.7%,3778%%
Gemini-2.5-F-L
38.5%
15.5%
22.9%
(21.6%,2443%%)
GPT-4.1
25.1%
16.1%
9.0%
[8.2%,10.0%)
GPT-4.1-M
30.3%
20.4%
9.9%
19.0%,10.9%)
K.2 ABLATION STUDIES ON THE SENSITIVITY OF PROMPTS
In this section, we aim to test the sensitivity of few-shot prompt in Appendix F via perturbing the prompts in the following two ways:
Convert nested bullet points into structured table format, see details in Appendix G.I
Rephrase every sentence with synonyms and alternative grammatical structures, see details in Appendix G.2
We select GPT-4. 1 as test model and AIME 2025 test dataset. To rigorously assess prompt sensitivity, we employ the TOST (Two One-Sided Tests) procedure for statistical equivalence testing on five graph statistics introduced Section 4.2 We consider wwo-sample mean difference per- problem then set the significance level to 0.05 and equivalence margin to 0.10. The testing results are reported in Table 8 for re-format and Table for rephrase. Fig. 8 reports AUC scores on DAG- MATH formatted CoT with original and two perturbed prompts, see Table [0 more details. We have the following observations:
Structural Consistency: From Table g and Table 9 our equivalence testing demonstrates that the DAG structures generated under different prompt variations are statistically equiv- alent across all five graph-level statistics.
Robust Evaluation: In Fig. and Table I0 we can observe that the variation in PRR/AUC is minimal, suggesting metrics capture inherent model reasoning capabilities rather than artifacts of specific prompting strategies.
39

---

Published as a conference paper at ICLR 2026
Table TOST equivalence testing between original and re-format prompts across 30 problems (per- problem paired mean aggregation). CI denotes 90% confidence interval. Plen and Pright are the two one-sided p-values one for lower and upper bound test.
Stat.
Mean Difr.
CI
Plett
Pright
Equivalent
#nodes 0.56
[0.18, 0.95]
2.59 x 10 11
7.76 x 10
YES
#edges
0.44
[-0.11, 0.99]
5.01 10-9
7.49 10
YES
density
-0.23%
[-0.37% -0.09%]
7.99 x 10-8
2.22 x 10
YES
d max
0.03
[-0.04, 0.
5.64 x 10-8
2.81 x 10-6
YES
mmxx
0.01
[-0.09, 0.12]
1.16 10-5
4.18
10-5
YES
Table 9: TOST equivalence testing between original and re-phrase prompts across 30 problems (per- problem paired mean aggregation). CI denotes 90% confidence interval. Plef and Pright are the two one-sided p-values one for lower and upper bound test.
Stat.
Mean Difr.
CI
Plett
Pright
Equivalent
#nodes
0.89
[0.52, 1.26]
3.83 x 10 13
2.82 x 10
YES
#edges
0.82
[0.30, 1.35]
9.80 10-11
1.29 10-4
YES
density
-0.3%
[-0.49% -0.17%]
5.30 x 10
2.34 x 10 10-13
YES
max
0.03
[-0.04, 0.10]
2.58 x 10-8
1.89 x 10 10-6
YES
d qmax 0.007
[-0.10, 0.11]
1.40 10-5
2.67
10-5
YES
K.3 ABLATION STUDIES ON FORMATTING CONSTRAINT AND CIRCULARITY
In this section, we conduct ablation studies in two aspects:
analyze the impact of formatting constraint comparing to natural CoT;
examine the consistency of DAG constructions by different model families for evaluation.
We design two prompting methods to enable DAG parsing by external thinking/non-thinkingg model, which makes our PPR/AUC metric apply to any step-by-step CoT without formatting. We select GPT-4.1 1 as test model and AIME 2025 test dataset.
Natural CoT Generation: We compare DAG-MATH formatted CoT with natural CoT to check whether the formatting constraint degrades the reasoning ability in natural form not. We design a minimal zero-shot prompt for natural CoT which only requires the model to generate step-by- step solution and write the final answer in boxed format for convenience of evaluation. Then, independently draw 32 natural CoT samples for each problem.
Since the prompting evaluation in Section Section requires self-parsing for the dependency structure, we aim to show there are no circular dependency by adding dependencies for both format- ted and natural CoT via external LLMs. Besides, the corresponding parsing method can annotate DAG for natural CoT, which generalizes the utility of our PRR/AUC metric. We evaluate three modes:
DAG Parsing:
parsing DAG Cem
parsing DAG by GPT-o4-mini,
self-parsing.
For thinking LLMs, since the construction of dependencies can be performed within thinking pro- cess, we design a zero-shot prompting method to provide instructions for model to annotate DAGs, see Appendix H.I for details. Since GPT-4. 4.1 1 is a non-thinking LLM (instant answer), we add a reason field to analyze dependencies before generating di direct bee.c..dpeeddet.stee. order to enable self self--prsing for natural CoT. Additionally, we add one human-written demonstration example for better instruction following. See Appendix H.2 for more details.
field, in
40

---

Published as a conference paper at ICLR 2026
AIME 2025
0.35
Original (AUC=0. 255)
0.30
Re-phrase (AUC=0.252)
Re-format (AUC=0.235)
0.25
Accuracy
0.20
0.15
0.10
0.05
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Logical Closeness
Figure 8: The AUC curves of averaged accuracy under the logical closeness rate for DAG-MATH formatted CoT under original, re-format, and re-phrase prompts.
Table 10: The results of PASS@1. PRR, and AUC values for DAG-MATH formatted CoT under original, re-format, and re-phrase prompts.
Original
Re-format
Re-frame
PASS@ 26.5%
24.3%
26.1%
PRR
16.8%
16.5%
15.8%
AUC
25.5%
23.5%
25.2%
Results Fig. reports AUC scores natural CoT and DAG-MATH across different parsing models (see more details in Table 11]. We perform the same TOST as Appendix K.2 with margin 0.25 and all statistics are tested as equivalent between self-parsing and external parsing. We have the following findings.
Utility on Natural CoT Format Dependency: Our PRR/AUC metrics remain highly infor- mative even when applied to free-form natural COT. From Fig. 9 the AUC metric clearly shows that the natural CoT can achieve more than 70% logic-closed nodes, which consistent across different LLMs. The AUC values for natural CoT are comparable to those for DAG-MATH, demonstrating that the metrics capture fundamental reasoning patterns regardless output for- mat. In Table II the consistently higher PRR for DAG-MATH indicates that the structured format enhances logical coherence by encouraging more dependency-awenr reasoning. This confirms that the DAG-MATH format amplifies rather than creates the signal of logical coher- ence.
No Circular Dependency: The consistency of AUC scores across different parsing methods- ranging from 23.8% 24.7% for natural CoT and 24.9% to 25.5% for DAG-MATT-dirrclle addresses circularity concerns. This consistency is further enhanced by our TOST which all achieve statistical equivalence. This shows that logical closeness is objective property that can be reliably measured by independent models, validating the robustness of our evaluation framework. We randomly draw 10 samples which closed by self self-parsing but unclosed by others then evaluate the dependency structure manually by human. Surprisingly, we find that self-parsing works better than external parsing, which matches the fact that LLM generates CoT following the internal dependency studied in Ye et al. (2025). There might be an extra understanding stage needed when parsing with external models.
Format Constraint Impact: The DAG-MATH format does not degrade natural reasoning flex- ibility, as evidenced by better PASS@ scores (26.5% for DAG-MATH vs. 25.7% for natural CoT). The significantly lower average node count and standard deviation in DAG-MATH indi-
41

---

Published as a conference paper at ICLR 2026
Natural
DAG-MATH
0.35
0.35
Self (AUC=0.247)
Self (AUC=0.255)
0.30
Gemini (AUC=0.241)
0.30
Gemini (AUC=0.253)
(AUC=0.238)
GPT (UUC)
0.25
0.25
Accuracy
Accuracy
0.20
0.20
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
1.0
Logical Closeness
Logical Closeness
Figure 9: The AUC curves of averaged accuracy under the logical closeness for natural CoT and DAG-MATH across self-parsing, parsing by Gemini-i 2.11225--55 5.Fashshhh S---aaah-Thiiikee (Gemini for short), and parsing by GPT-04-mint (GPT for short).
Table 11: The results of average number of nodes (#Nodes), PASS@1, PRR, AUC scores for natural CoT and DAG-MATH across self-parsing, parsing by Gemini wai-2.5-Flash--Thaaeee (Gem- ini for short), and parsing by GPT-o4-mini (GPT for short).
Metric
Natural
DAG-MATH
#Nodes
40.3426.6
17.8+7.0
PASS@1
25.7%
26.5%
Self
Gemini
GPT
Self
Gemini
GPT
PRR
10.4%
7.8%
4.7%
16.8%
14.7%
11.4%
AUC
24.7%
24.1%
23.8%
25.5%
25.3%
24.9%
cates the format encourages focused reasoning without sacrificing accuracy. The higher PRR across all parsing methods for DAG-MATH suggests ing quality by promoting logically closed derivations, while natural CoT causes extra verifica- tion burden due to a large amount of irrelevant information.
the format actually enhances reason-
K.4 ABLATION STUDIES ON
PEW-SHOT EXAMPLES
In this section, we conduct ablation studies regarding model bias in few-shot examples. We fix the same few-shot example problems and repeat the standata DAG construction procedure intro- duced in Appendix by Gemini-2.55 5-r different to GPT-o4 2ET-o4--ini used in benchmark con- struction. Next, we select GPT-4. and Gem ni-2. 5-Flash to generate DAG-MATH samples under prompts with few-shot examples from two different model families, which forms cross- family comparison. Fig. shows the AUC curves with more details in Table I2 The results show that while there is slight performance drop when using examples from different family, the ef- fect is modest and does not fundamentally alter the relative rankings or conclusions drawn from our metrics. Furthermore, structures under family examples. GPT-4. achieves statistical equivalence at a margin of 0.1 and Gemi ni -2, 5-Pro at 0.25, which is strong evidence.
perform same TOST Appendix K.2 test the equivalence of DAG
42

---

Published as a conference paper at ICLR 2026
Gemini-2.5-Flast on AIME 2025
Semini-2.5-Flaae on AIME 2025
0.6
0.26
0.5
0.24
Accuracy
Accuracy
0.4
0.22
0.20
0.18-
Same (AUC=0. 255)
Different (AUC=0.501)
0.16
Different (AUC=0.220)
Same (AUC=0.484)
0.1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Logical Closeness Rate
Logical Closeness Rate
Figure 10: The AUC curves of averaged accuracy under the logical closeness for DAG-MATH formatted CoT under prompts with few-shot examples from same vs different model family.
Table 12:
Results of PASS@1 and PRR for two test models with few-shot examples from same/dif-
ferent model family on AIME 2025.
PASS@1
PRR
Family
same
diff.
same
diff.
GPT-4.1 2.5
26.5% 54.4%
22.7% 52.4%
16.8%
15.9%
19.6%
17.0%
L THE USE OF LARGE LANGUAGE MODELS (LLMs) STATEMENT
We claim that LLMs were used minimally for language polishing. For example, we use ChatGPT to make the abstract more precise and concise, which has no effect the technical contribution of this paper.
43


Reviews:
[{"review_id": "LVOje2f8ST", "reviewer": "Reviewer_wXKz", "summary": "This paper introduces DAG-MATH, a framework designed to formalize and evaluate the Chain-of-Thought (CoT) trajectories generated by Large Language Models (LLMs) in mathematical reasoning. The CoT is modeled as a rule-based stochastic process over a Directed Acyclic Graph (DAG), where nodes are intermediate states. The core proposal is the Logical Closeness metric, which quantifies the fidelity of an LLM's path against a \"gold standard\" DAG, yielding the Perfect Reasoning Rate (PRR) and AUC scores. The authors claim this provides a superior diagnostic tool compared to simple final-answer metrics like PASS@k. The resulting DAG-MATH benchmark is built using LLM-generated structured outputs.", "questions": "1. Can you demonstrate the utility of PRR/AUC by heuristically parsing DAGs from unconstrained, free-form CoT outputs (without the DAG-MATH template) on a subset of problems? If the metric collapses here, it confirms the dependency on the template is too strong.\n2. Please elaborate on the relationship between DAG-MATH's diagnostic insights and existing MCTS/Tree-of-Thought techniques. How can the PRR/AUC scores be used to guide the search policies or reward functions in such systems?\n3. Given the reliance on LLM-generated ground truth, what specific human review or verification process was applied to the 2,894 gold-standard DAGs to ensure their canonical logical structure? What were the human agreement statistics on the logical decomposition?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The underlying idea of treating CoT as a DAG traversal is fundamentally sound and offers a pathway for structured reasoning analysis beyond token-level checks. This is the paper's primary and most important strength.\n2. The authors have created impressive few-shot prompts to enforce their complex output format, which is a valuable demonstration of structured generation control in LLMs. The visual examples of the DAGs are convincing.\n3. The metric correctly isolates failure modes like speculative branching and imperfect reasoning, which are invisible to simple PASS@k.", "weaknesses": "1. The PRR/AUC metric confuses adherence to the authors' custom template with true logical reasoning ability. The paper must provide evidence that this metric holds up when applied to non-formatted, naturally generated CoT.\n2. A critical omission is the lack of comparison with or contextualization against MCTS or similar graph-based search methods. If the goal is to improve reasoning, how does the DAG-MATH diagnosis inform or relate to these established LLM search strategies?\n3. The use of LLMs to generate the ground truth DAGs for their own evaluation introduces a circular dependency. This casts significant doubt on the objectivity and reliability of the Logical Closeness scores.\n4. The Acyclicity Assumption restricts the framework to simple forward derivation, excluding crucial reasoning patterns like planning, iterative refinement, or proof by contradiction, thereby limiting its general applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gWqKiSfTN2", "reviewer": "Reviewer_utCQ", "summary": "This paper introduces DAG-MATH, which is a framework to evaluate mathematical reasoning of LLMs through modeling Chain-of-Thought as stochastic process over directed acyclic graphs. The authors propose metric called \"logical closeness\" for distinguishing between when model solves problem by search versus real logical inference. They make benchmark with 2,894 gold-standard DAGs and test five LLMs, discovering that although PASS@1 scores vary much between models, their perfect reasoning rates stay quite similar, which suggests search is inflating the accuracy metrics.", "questions": "How did you validate that the DAGs generated by GPT and Qwen actually represent correct reasoning structures? It seems crucial to have human experts verify at least subset of these DAGs to ensure the benchmark quality. Many mathematical problems have multiple valid solution approaches - how does the logical closeness metric handle cases where completely different but valid DAG structures could exist for same problem?\n\nCould you provide proper statistical significance tests for the differences you claim between PASS@1 and PRR? How sensitive are all these results to the specific prompting strategies you used? If you changed the prompts slightly, would the DAG structures and evaluation results change significantly?\n\nWhat is the practical path from these evaluation insights to actually improving LLM reasoning capabilities? The paper identifies interesting patterns but doesn't suggest how to use this knowledge for making better models. How does this framework compare empirically with recent work on process reward models from OpenAI and others that also try to verify reasoning at step level?\n\nWhy did you choose to require exactly one assertion per node - this seems quite restrictive and arbitrary? And why make logical closeness binary measure instead of having gradient that could capture partial correctness better? Finally, have you considered that the models might be following completely different internal reasoning process and the DAG structure is just post-hoc rationalization that we impose on their outputs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper tackles really important problem about understanding whether LLMs achieve correct answers through systematic search or through genuine logical reasoning, which is fundamental question for the field. The DAG-based formalization is quite novel approach that sits nicely between completely free-form CoT and very formal systems like LEAN verification, making it more practical to use. The logical closeness metric gives us insights that go beyond simple PASS@k metrics that everyone uses.\n\nThe empirical analysis is quite comprehensive, showing interesting patterns about how DAG statistics like number of nodes, edges, density and branching correlate with problem difficulty. It reveals that harder problems create larger and more sparse graphs with higher branching, which makes sense intuitively. The finding that search and exploration inflate PASS@1 while actual reasoning ability measured by PRR stays comparable across different models is really actionable insight that changes how we should think about evaluating these systems. Also good that authors released the benchmark and code for others to use.", "weaknesses": "There is concerning circularity in how the benchmark was constructed - using GPT-4 and Qwen to create the \"gold standard\" DAGs means the benchmark is essentially created by same type of models that are being evaluated, which introduces obvious biases. The theoretical justification feels not enough developed. Why should we believe this specific DAG formalization captures what \"true\" reasoning means? The stochastic process described in Equation 1 seems somewhat arbitrary choice without proper justification.\n\nThe statistical analysis lacks rigor with only 32 samples per problem and no significance testing provided for the differences claimed between PASS@1 and PRR. There is no analysis about robustness - what happens when same problem can be formulated with different but equivalent DAG structures? The scope is quite limited, restricting to mathematics problems with difficulty below 6, and missing comparisons with other approaches like process reward models that also try to do step-level verification. The three-stage prompting methodology might be imposing particular reasoning patterns that are not universal. Most importantly, there is no human validation beyond what the models themselves produce, which is problematic for claiming these are \"gold standard\" solutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jCMw85o5vc", "reviewer": "Reviewer_61B1", "summary": "The paper proposes to model mathematical reasoning’s CoT traces as a rule-based stochastic process over task-specific DAGs, where nodes represent reasoning states and edges encode inference rules or justifications. Building on this formulation, the paper introduces logical closeness as a new metric to evaluate the model's reasoning trajectory. It also presents a benchmark of gold-standard DAG-MATH graphs with verified logical structures and statistical analyses relating graph properties to problem difficulty. Finally, the paper evaluates several large language models by prompting them to produce formatted CoT reasoning on mathematical benchmarks and examines how their reasoning abilities correlate with the proposed DAG-MATH framework.", "questions": "- How exactly is the branching of reasoning paths determined?\n- Since the canonicalization turns reasoning steps into SNF, does it limit the type of mathematical questions that DAG-MATH can apply to? \n- In lines 63-64, what does it mean that the other works “fail to capture long-range and cross-branch dependencies, as well as the goal-directed, absorbing-state nature of CoT”?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written and well-organized. \n- The idea of representing CoT reasoning with DAG-MATH is interesting and novel. The proposed metrics are also new and conceptually sound. \n- The empirical results are informative, showing how graph structures reflect problem difficulty and reasoning quality.", "weaknesses": "- Enforcing the DAG-MATH format may degrade the natural reasoning flexibility of LLMs. It would help to include an analysis or ablation comparing performance with and without this formatting constraint. Furthermore, if the few-shot examples are drawn from a specific model family, models of the same family might have an advantage because their reasoning patterns are similar.\n- The analysis is primarily quantitative. Some qualitative examples or case studies of the generated DAG-MATH graphs, especially highlighting common reasoning errors or structural failures, would strengthen the insights.\n- In Section 2.2, the paper mentions that thinking LLMs can be viewed as “an exploration of the task-specific DAG with self-correction or backtracking, but its final output … is still consistent with our transition rule.”, but empirical results did not include reasoning models, which could strengthen the value of the paper. \n- DAG-MATH has limited scalability. Complex problems with very long and multiple reasoning traces are computationally expensive to construct. Those with cyclic reasoning or backtracking are hard to capture in a strictly acyclic form.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3qoCulNMAJ", "reviewer": "Reviewer_GdSj", "summary": "This paper proposes a DAG-based framework for representing CoT reasoning and introduces the concept of logical closeness, enabling fine-grained evaluation of LLM mathematical reasoning beyond final-answer accuracy. Its approach assesses the coherence and consistency of logical dependencies along a CoT trajectory, rather than focusing solely on whether the solution is correct. Furthermore, the authors construct a benchmark of DAG-formatted mathematical problems derived from existing datasets and provide empirical analyses linking graph-level characteristics—such as size, density, and branching complexity—to problem difficulty.", "questions": "- How can we trust an LLM-as-Judge to reliably evaluate the logical coherence of DAG constructions, particularly when edges are intended to represent valid inference paths? Have the authors conducted any analyses or validation studies to assess the consistency or accuracy of these judgments?\n- At first glance, Figure 4 being a line plot was somewhat confusing. Do the authors plot accuracy against varying levels of logical correctness rates and then smooth the resulting curve? A brief clarification in the caption or text might help.\n- I also wonder whether different node segmentation choices could exist for the same reasoning trajectory. If so, how sensitive are the proposed approach and the PRR metric to such segmentation differences?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This work formalizes the notion of logical closeness and proposes a metric, the perfect reasoning rate, based on this notion to measure LLMs' logical consistency beyond the final output. This indeed addresses an important question of whether an LLM arrives at a correct answer through genuine logical reasoning or mere pattern matching.\n- The formalization in Sections 2 and 3 is clearly presented and easy to follow.\n- Section 5 and Appendix B offer several interesting insights, such as the correlation between graph structure and problem difficulty, and how a correct final answer may still arise from unclosed or flawed reasoning.", "weaknesses": "- The DAG-MATH benchmark presented in the paper is validated using symbolic correctness and an LLM-as-Judge approach. I assume that SymPy is employed to verify mathematical equivalence, while the logical dependencies between nodes (i.e., whether an edge should exist) are assessed by the LLM-as-Judge. However, as the paper itself demonstrates, LLMs can often produce superficially consistent but logically inconsistent reasoning. While using LLMs for judgment is a practical solution, it would be helpful for the authors to further justify the reliability of this dataset construction and evaluation methodology. \n- Building on this point, reliable automation of the logical closeness check appears challenging, if not infeasible, since formalizing a DAG from natural-language CoT inherently involves subjective interpretation, particularly for more complex problems. For instance, reasonable disagreement could arise over whether a given edge should connect two specific nodes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)