# Graph of Verification: Structured Verification of LLM Reasoning with Directed Acyclic Graphs

arXiv: https://arxiv.org/abs/2506.12509 · HTML: https://mlsanity.com/paper/2506.12509/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 23 of its 24 references that are in the map.
- First posted on arXiv 14 Jun 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 23 of 23)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [ProcessBench: Identifying Process Errors in Mathematical Reasoning](https://mlsanity.com/paper/2412.06559/) (2024)
- [When Can LLMs Actually Correct Their Own Mistakes? A Critical Survey of Self-Correction of LLMs](https://mlsanity.com/paper/2406.01297/) (2024)
- [LLM Critics Help Catch LLM Bugs](https://mlsanity.com/paper/2407.00215/) (2024)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [Deductive Verification of Chain-of-Thought Reasoning](https://mlsanity.com/paper/2306.03872/) (2023)
- [Question Decomposition Improves the Faithfulness of Model-Generated Reasoning](https://mlsanity.com/paper/2307.11768/) (2023)
- [Enhancing Large Language Models in Coding Through Multi-Perspective Self-Consistency](https://mlsanity.com/paper/2309.17272/) (2023)
- [Can Large Language Models Detect Errors in Long Chain-of-Thought Reasoning?](https://mlsanity.com/paper/2502.19361/) (2025)
- [A Closer Look at the Self-Verification Abilities of Large Language Models in Logical Reasoning](https://mlsanity.com/paper/2311.07954/) (2023)
- [LLM Critics Help Catch Bugs in Mathematics: Towards a Better Mathematical Verifier with Natural Language Feedback](https://mlsanity.com/paper/2406.14024/) (2024)
- [Premise-Augmented Reasoning Chains Improve Error Identification in Math reasoning with LLMs](https://mlsanity.com/paper/2502.02362/) (2025)
- [Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures](https://mlsanity.com/paper/2502.05078/) (2025)

## Built on by (most cited first, 8 of 8)

- [SSR: Socratic Self-Refine for Large Language Model Reasoning](https://mlsanity.com/paper/2511.10621/) (2025)
- [Do We Need Frontier Models to Verify Mathematical Proofs?](https://mlsanity.com/paper/2604.02450/) (2026)
- [Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution](https://mlsanity.com/paper/2605.19228/) (2026)
- [Two Regimes of Chain-of-Thought Unfaithfulness: Metric-Based Detection Fails Where Models Are Wrong](https://mlsanity.com/paper/2607.23458/) (2026)
- [VeriGraph: Towards Verifiable Data-Analytic Agents](https://mlsanity.com/paper/2606.16603/) (2026)
- [Theoria: Rewrite-Acceptability Verification over Informal Reasoning States](https://mlsanity.com/paper/2607.01223/) (2026)
- [The Error You See Is Not the Error You Made: Progression-aware Reasoning Origin for Reasoning Error Localization](https://mlsanity.com/paper/2609.33297/) (2026)
- [Learning to Prove, Not Just to Answer: Reinforcement Learning from Formal Verification for Natural-Language Logical Reasoning](https://mlsanity.com/paper/2609.37203/) (2026)

## Abstract (arXiv)

Verifying the complex and multi-step reasoning of Large Language Models (LLMs) is a critical challenge, as holistic methods often overlook localized flaws. Step-by-step validation is a promising alternative, yet existing methods are often rigid. They struggle to adapt to diverse reasoning structures, from formal proofs to informal natural language narratives. To address this adaptability gap, we propose the Graph of Verification (GoV), a novel framework for adaptable and multi-granular verification. GoV's core innovation is its flexible "node block" architecture. This mechanism allows GoV to adaptively adjust its verification granularity--from atomic steps for formal tasks to entire paragraphs for natural language--to match the native structure of the reasoning process. This flexibility allows GoV to resolve the fundamental trade-off between verification precision and robustness. Experiments on both well-structured and loosely-structured benchmarks demonstrate GoV's versatility. The results show that GoV's adaptive approach significantly outperforms both holistic baselines and other state-of-the-art decomposition-based methods, establishing a new standard for training-free reasoning verification.