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

Yuanhe Zhang, Ilja Kuzborskij, Jason D. Lee, Chenlei Leng, Fanghui Liu

TL;DR

While Large Language Models (LLMs) excel at solving math problems using Chain-of-Thought (CoT) prompting, standard metrics only evaluate the final answer, masking flawed or exploratory intermediate steps. This paper introduces DAG-Math, a framework that models reasoning as a stochastic process over Directed Acyclic Graphs (DAGs) and defines a new metric, logical closeness, to measure true reasoning fidelity. The authors reveal a massive gap between final-answer accuracy and mathematically sound derivation across leading LLM families.

What Problem Does This Paper Address?

When an LLM solves a complex mathematical problem using Chain-of-Thought (CoT), how do we know it actually reasoned its way to the answer? Current evaluation methods primarily rely on metrics like $\text{PASS}@k$, which only check if the final answer matches the ground truth.

However, a model might arrive at the correct answer through lucky guesses, brute-force search, or a messy mix of conflicting strategies that happen to cancel out errors. While formal proof systems like LEAN provide rigorous verification, they require immense expert effort to formalize natural language problems.

The authors bridge this gap by introducing a framework that evaluates the structural and logical coherence of the entire intermediate reasoning chain without losing the flexibility of natural language.

Methods

The authors formalize CoT reasoning by mapping it to a task-specific Directed Acyclic Graph (DAG).

  • Nodes (Conclusions): Represent intermediate states, facts, or derived assertions.
  • Edges (Justifications): Represent the logical rules or steps that connect parent nodes to a new conclusion.
Figure 1: Task-specific DAG via LLaMA-3.1-8B-Instruct.

Logical Closeness & Perfect Reasoning Rate (PRR)

A key contribution is the concept of logical closeness. A generated reasoning path is considered logically closed if every intermediate node is actively utilized to derive a subsequent step. If a model generates "dangling nodes"—ideas or calculations that lead nowhere—it fails logical closeness.

A trajectory achieves Perfect Reasoning (PRR) if it is both logically closed and terminates at the correct final answer (sink node).

To make this structure explicit and measurable, the authors introduce the DAG-MATH format, which forces LLMs to generate text in a structured format: Edge → Parent(s) → Node.

Datasets

The authors created a new gold-standard benchmark consisting of 2,894 verified DAG-MATH DAGs derived from Omni-MATH (focusing on difficulty levels 1 to 5 to ensure high baseline solvability).

For empirical evaluation of leading LLMs, they tested the models on three highly challenging, competition-level math datasets:

  • AIME 2025 (American Invitational Mathematics Examination)
  • BRUMO 2025 (Brown University Math Olympiad)
  • HMMT 2025 (Harvard-MIT Mathematics Tournament)

Key Insights and Ideas

  • Search Inflates Accuracy, Not Logic: Extensive exploration or test-time compute (like "thinking modes") significantly boosts raw final-answer accuracy ($\text{PASS}@1$). However, the underlying Perfect Reasoning Rate (PRR) remains low. Models are essentially getting better at searching, not necessarily at executing flawless, direct logical chains.
  • Complexity Scales via Branching, Not Aggregation: By analyzing the graph properties of harder math problems, the authors found that as difficulty increases, DAGs become larger and sparser, with a sharp increase in maximum out-degree. This means difficulty stems from branching into modular sub-reasoning paths rather than aggregating massive amounts of information into a single step.
  • The Strategy-Switching Phenomenon: Qualitative analysis revealed that models frequently switch problem-solving strategies mid-generation. For example, a model might start with a geometric reflection strategy, abandon it halfway through, switch to a coordinate-based "shoelace formula" strategy, and get the right answer. $\text{PASS}@1$ scores this as a perfect success, whereas DAG-Math flags it as structurally imperfect due to the abandoned, unclosed reasoning branch.
Figure 2: Toy DAG.

Key Results

The paper exposes a stark "reasoning gap" across all evaluated models (including Gemini 2.5 Flash, GPT-4.1, and Qwen3-30B).

On the AIME 2025 dataset:

  • Gemini-2.5-Flash achieved a strong 52.4% $\text{PASS}@1$ accuracy, but its PRR plummeted to just 17.0%.
  • Qwen3-30B posted a 43.1% $\text{PASS}@1$, but managed only a 15.8% PRR.
  • Even when activating Gemini's specialized "thinking mode," which boosted $\text{PASS}@1$ from 52.4% to 64.0%, the PRR only rose to 35.9%—leaving a massive 28.1% gap of "correct answers with flawed derivations."

Limitations and Future Work

The primary limitation acknowledged by the authors is their assumption of local step correctness. The framework focuses entirely on the structural logic of the graph, assuming that individual calculations within a node are accurate (relying on external tools like SymPy or Process Reward Models to catch basic arithmetic slips).

Future Directions

  1. Guiding Search Policies: Integrating logical closeness as a dense reward signal for Monte Carlo Tree Search (MCTS) or Tree-of-Thoughts algorithms to prune messy, speculative branches early.
  2. Reinforcement Learning Curriculum: Designing RL training loops that progressively demand higher logical closeness, guiding LLMs away from chaotic trial-and-error toward concise, elegant mathematical proofs.

Summary updated

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.
BibTeX
@inproceedings{zhang2026dag,
  author = {Yuanhe Zhang and Ilja Kuzborskij and Jason D. Lee and Chenlei Leng and Fanghui Liu},
  title = {{DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMs}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=ylr6WArKQN},
}
Figure