DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs

AI summary

Overview

Research area: evaluation and formal modeling of mathematical reasoning in large language models, specifically Chain-of-Thought (CoT).

Technical level: Advanced. The paper defines CoT as a rule-based stochastic process over directed acyclic graphs (DAGs), introduces formal definitions of "logical closeness" and "perfect reasoning," and derives metrics (PRR, AUC) that require comfort with graph theory and probability.

Scope (1 sentence): The paper proposes a DAG-based framework for modeling and evaluating LLM mathematical reasoning, releases a benchmark of 2,894 gold-standard DAGs in a new "DAG-MATH" CoT format, and evaluates five LLMs on three competition-math datasets.

What This Paper Is About

LLMs prompted with Chain-of-Thought score well on math problems, but it is unclear whether they are genuinely applying rule-consistent logical inference or simply searching through plausible alternatives until an answer appears. The authors build a graph-based framework in which each CoT step is a node (a conclusion) reached by an edge (a justification), letting them check not just whether the final answer is right but whether the whole derivation obeys the logical structure of the problem. They use this to define a new metric — the Perfect Reasoning Rate (PRR) — and to build the DAG-MATH benchmark and CoT format for evaluating models.

Key Contributions

1. A two-phase DAG framework for step-level CoT. Phase 1 constructs a task-specific DAG from the prompt, with source nodes (from the input), intermediate nodes, and sink nodes (final answers, one correct and possibly others incorrect), under Assumption 1 that the graph is acyclic. Phase 2 models the LLM's output as a node-level autoregressive stochastic process over that DAG, where a node becomes available only once all its parents have been visited, and the process is absorbing at sink nodes.

2. The notion of "logical closeness" and the Perfect Reasoning Rate (PRR). A generated trajectory-DAG is logically closed if every node except the final ones has out-degree at least 1; a trajectory is perfect reasoning if it is logically closed and its sink node is the correct answer. PRR is the expectation of the product of the closeness indicator and the correct-sink indicator, and overall mathematical reasoning ability is the expectation of PRR over a problem distribution. The authors also define AUC scores by relaxing the closeness requirement across a range of thresholds (0% to 100%).

3. The DAG-MATH CoT format and a gold-standard benchmark. DAG-MATH makes reasoning structure explicit in the order Edge → Parent(s) → Node, with step IDs serving as node identifiers. Using a three-stage prompting strategy in reverse order (Node → Parents → Edge), the authors construct a benchmark of 2,894 gold-standard DAGs from Omni-MATH problems, verified for format adherence, logical closeness, and correct final answers.

4. An empirical evaluation of five LLMs on three competition datasets. The paper compares Gemini-2.5-Flash, Gemini-2.5-Flash-Lite, GPT-4.1, GPT-4.1-mini, and Qwen3-30B-A3B-Instruct-2507 on AIME 2025, BRUMO 2025, and HMMT 2025, reporting PASS@1, PRR estimates, AUC curves, and graph-level statistics.

Main Findings

• Search inflates raw accuracy, while perfect reasoning ability stays roughly comparable across models. All evaluated models show a noticeable drop from PASS@1 to the estimated reasoning ability, but the endpoint of the AUC curve (the estimated reasoning ability under strict logical closeness) is "almost the same" across models, even though PASS@1 varies widely.

• Correct answers come with limited logical consistency. The AUC scores indicate that models with correct answers achieve at most 80% logic-closed nodes, and accuracy degrades markedly under stricter criteria.

• Harder problems produce larger, sparser, and more branchy DAGs. As problem difficulty increases from 0 to 6, the distributions of node count and edge count shift rightward with heavier tails; graph density drops; maximum in-degree grows slowly while maximum out-degree rises more sharply, suggesting logical complexity scales mainly through branching rather than aggregation. Average in-degree and out-degree remain around 1.3 across difficulty levels.

• Graph structure tracks reasoning quality, not just difficulty. Within each model, Perfect trajectories correspond to the smallest and densest graphs; Correct graphs are slightly larger and sparser, suggesting useful exploratory steps; Incorrect graphs exhibit strong branching, with maximum out-degree growing faster than maximum in-degree, indicating failure often comes from speculative expansion rather than insufficient aggregation. On AIME 2025, for example, Gemini-2.5-Flash's All class averages 32.8 nodes, 48.9 edges, 11.2% density, maximum in-degree 4.3, and maximum out-degree 7.0, while its Perfect class averages 23.3 nodes, 30.8 edges, 13.0% density, maximum in-degree 3.3, and maximum out-degree 3.6. The provided text is truncated mid-sentence in the discussion of Gemini's Correct cohort.

• PRR decays exponentially with depth in a controlled example. In a toy DAG of two linear chains of length L with uniform transitions over available nodes, PRR equals (1/2)^(L−1), even though final-answer accuracy stays at 1/2 — showing that logically closed trajectories become increasingly rare as derivations get longer.

• Benchmark reliability. Human evaluation on 50 random samples produced 49/50 in agreement with the automated gold-standard labeling.

• Error taxonomy richer than plain generalization. The framework draws an analogy to supervised learning: under-reasoning (the DAG omits necessary intermediate steps) and over-reasoning (the DAG is sound but contains redundant steps) both lower estimated reasoning ability, with perfect reasoning as the "sweet spot."

Methodology in Plain English

The authors start from an intuition: when an LLM solves a math problem, its reasoning has an underlying logical structure — certain conclusions must come before others. They represent that structure as a directed graph where each conclusion is a node and each inference connecting conclusions is an edge. One graph (Phase 1) describes all the valid reasoning routes for a given problem, with the problem statement feeding in at "source" nodes and final answers appearing as "sink" nodes.

Then they treat the model's written CoT as a walk through that graph (Phase 2): at each step the model may only move to a node whose parents have already been established, and it stops once it hits an answer. This gives a precise definition of what a "logically closed" chain of reasoning looks like.

To make this measurable in practice, they force the model to emit its reasoning in the DAG-MATH format: for each step, state the rule or justification (Edge), list which earlier steps it depends on (Parents), and then state the conclusion (Node). A small number of worked examples (few-shot prompting) teaches models the format. Because the parents are explicit, the resulting graph can be checked mechanically. For the benchmark, they prompt strong models to produce DAG-MATH chains for Omni-MATH problems, then run a three-stage process that fixes the conclusions first, then parents, then edges — a reverse order chosen so verification with SymPy or an LLM judge is easier and errors propagate less. Only chains that follow the format, are logically closed, and end at the correct answer become gold-standard entries. Finally, they test five LLMs on three competition datasets, generating 32 DAG-MATH trajectories per problem with 4-shot prompting, and compute PASS@1, the estimated reasoning ability, and graph statistics such as node count, edge count, density, and maximum in- and out-degree.

Why This Matters

Impact on research. The paper argues for an evaluation layer between free-form natural language CoT and full formal proof verification in LEAN. LEAN guarantees logical correctness but requires problems to be formalized in advance, which costs substantial expert effort for answer-based problems. The DAG-MATH framework is meant to be a middle ground — the authors call it a "Goldilocks principle" — that is rigorous enough to detect rule-inconsistent reasoning while remaining applicable to ordinary natural-language math problems. It also proposes a way to distinguish illegal paths, legal-but-wrong paths, and "imperfectly correct" trajectories, which standard accuracy-based evaluation collapses into a single error type.

Real-world applications

• AI tutoring and education: A system could flag a student-facing or AI-generated solution that reaches the right answer through a structurally incoherent argument, rather than marking it correct.
• Benchmarking and model selection: Organizations choosing between LLMs for quantitative work could compare perfect reasoning rates and AUC curves instead of relying only on PASS@k leaderboards.
• High-stakes automated reasoning pipelines: In domains where multi-step quantitative reasoning is used (for example financial analysis, engineering calculations, or research assistance), logical-closeness checks provide a diagnostic signal on whether the chain of steps hangs together.
• Agentic and multi-step systems: The decomposition into sub-tasks, long dependencies, and recombination mirrors planning problems in tool-using agents, where branching structure is a practical bottleneck.

Industry relevance. Model developers can use the format and metrics as diagnostics to see where added exploration helps versus where it merely branches; the paper notes models with strong math performance and lower token usage were chosen deliberately for efficiency reasons, which matters for cost-sensitive deployments.

Future Directions

• A formal theory of reasoning ability. The authors state they believe the framework can lay the foundation for a mathematical definition of reasoning in LLMs, paralleling memorization and generalization in supervised learning.
• Mitigating over-reasoning. They suggest regularization strategies such as the minimum description length principle could favor concise proofs conforming to a proof grammar or template, and leave this to future work.
• Extending to harder, proof-style problems. The framework is claimed to extend to IMO-level problems via lemma-level DAGs, with a concrete example based on problem 4 from IMO 2025 given in the appendix; scaling this up is an open direction.
• Algorithm design implications. The authors suggest the framework can inform algorithm design for improved reasoning performance of LLMs, and that this remains for further investigation.

Target Audience

This paper is best suited to researchers and engineers working on LLM reasoning and evaluation — particularly those interested in chain-of-thought analysis, formal or semi-formal verification of model outputs, and benchmark construction. It will also be useful to practitioners who need to distinguish genuinely coherent multi-step reasoning from answer-only correctness, and to graduate-level readers comfortable with graph theory, stochastic processes, and competition-level mathematics. Readers seeking a purely applied, implementation-focused guide may find the formal definitions and appendices the more relevant parts.

Authors’ 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 mathematical 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.