Research map / Large language models / Reasoning and chain of thought

DAG-Math: Graph-Guided Mathematical Reasoning in LLMs

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Chain-of-thought training and analysis

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Models chain-of-thought as rule-based stochastic processes over task-specific DAGs, introduces logical closeness and perfect reasoning rate (PRR) metrics, builds a 2,894-DAG DAG-MATH benchmark, and evaluates LLMs on AIME/BRUMO/HMMT 2025.

Problem

Final-answer metrics like PASS@k cannot tell whether an LLM's chain-of-thought reflects rule-consistent logical derivation or search/luck; a rigorous framework and metric for step-level reasoning fidelity are needed.

Approach

Formalize CoT as a rule-based stochastic process over a task-specific DAG of intermediate conclusions, define logical closeness (every non-sink node has a child) and perfect reasoning rate (closed DAG ending at the correct sink), and elicit DAG-MATH-formatted CoT via few-shot prompting to measure these.

Key results

• Gemini-2.5-Flash shows roughly a 36% gap between PASS@1 and PRR on AIME 2025 (PRR 17.0% without thinking vs PASS@1 52.4%).
• Perfect reasoning rates remain comparable across models while PASS@1 varies widely; e.g., GPT-4.1 PRR 16.8% in the cross-family check.
• Benchmark of 2,894 gold-standard DAGs built from Omni-MATH problems at difficulty below 6; human check on 50 samples gave 49/50 correct.

Surprising findings

• Search/exploration inflates PASS@1 substantially while perfect reasoning rate stays similar across model families.
• Thinking mode raises PRR for Gemini but a large PASS@1-PRR gap persists.

Limitations

• Assumes each step is execution-correct; step-level arithmetic errors are abstracted away.
• Benchmark restricted to Omni-MATH problems of difficulty below 6 and relies on LLM-generated gold DAGs with limited human verification.
• Evaluation relies on few-shot prompting to produce DAG format, so results depend on prompt and format compliance.

Experimental setup

Datasets: Omni-MATH AIME 2025 BRUMO 2025 HMMT 2025 MATH-500

Benchmarks: AIME 2025 BRUMO 2025 HMMT 2025 DAG-MATH benchmark

Metrics: PASS@1 perfect reasoning rate (PRR) AUC of accuracy vs logical closeness graph statistics (nodes, edges, density, max in/out-degree)

Baselines: PASS@1

Builds on: chain-of-thought pass@k

Closest papers by meaning

• Mind the Gap: Bridging Thought Leap for Improved Chain-of-Thought Tuning (NeurIPS 2025 · similarity 0.91)
• Premise-Augmented Reasoning Chains Improve Error Identification in Math reasoning with LLMs (ICML 2025 · similarity 0.90)
• Putnam-AXIOM: A Functional & Static Benchmark for Measuring Higher Level Mathematical Reasoning in LLMs (ICML 2025 · similarity 0.90)
• To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning (ICLR 2025 · similarity 0.90)
• Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.90)
• Understanding Chain-of-Thought in LLMs through Information Theory (ICML 2025 · similarity 0.90)