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

Jiwei Fang, Bin Zhang, Changwei Wang, Jin Wan, Zhiwei Xu

Abstract

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.

Introduction

Large Language Models (LLMs) are increasingly capable of multi-step reasoning, yet they remain notorious for "hallucinating" logical leaps. Even when an LLM arrives at the correct final answer, intermediate steps may contain subtle flaws. The standard approach to verification is holistic, requiring an LLM to judge the entire reasoning chain at once. However, this imposes a massive "cognitive load" on the verifier; as reasoning chains lengthen, the verifier often misses localized errors. While step-by-step verification is a promising alternative, existing methods are often too rigid, attempting to force every sentence into an "atomic" logical unit—a strategy that works for formal proofs but fails for loosely structured natural language.

The Graph of Verification (GoV) Framework

The authors propose the Graph of Verification (GoV), a training-free framework that treats a reasoning process as a structured flow of information. The framework operates in four distinct stages:

The four stages of the GoV framework: DAG Construction, Topological Sorting, Verification, and Verification Outcome.
  1. DAG Construction: The reasoning process is modeled as a Directed Acyclic Graph (DAG) where nodes are statements (premises, intermediate conclusions, or final answers) and edges represent logical dependencies.
  2. Topological Sorting: GoV ensures that premises are verified before the conclusions that rely on them, maintaining causal consistency.
  3. Sequential Verification: An LLM verifier checks each unit (node or block) one by one.
  4. Error Localization: The process halts at the first detected error, providing a precise "point of failure."

The core innovation is Multi-Granular Verification. Instead of checking only single sentences, GoV uses Node Blocks. For a math problem, a node might be a single equation (Atomic Granularity). For a natural language essay, a node might be a semantically coherent paragraph (Block Granularity). This allows GoV to navigate the fundamental trade-off between precision and robustness.

Experimental Results

GoV was evaluated on two primary fronts: the Number Triangle Summation task (a synthetic benchmark with deep dependencies) and ProcessBench (featuring GSM8K, MATH, and OlympiadBench).

Performance comparison between Holistic Verification and GoV across different Qwen2.5 model sizes as problem complexity (N) increases.

As shown in the results, GoV consistently outperformed both holistic baselines and state-of-the-art decomposition methods like PARC. On the Number Triangle task, as problem size (N) increased, the performance of holistic verification plummeted (e.g., from 99% to 49% F1 score), while GoV maintained significantly higher accuracy. On the challenging OlympiadBench, GoV boosted the F1 score of Qwen2.5-32B from 35.9% to 65.2%.

Conclusion

GoV establishes a new standard for training-free reasoning verification. By allowing practitioners to tune the granularity of verification, it provides a robust solution for both formal and informal reasoning tasks. Future work will explore automated graph-parsing methods and the transition from verification to interactive correction.

Summary updated

Abstract

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.
BibTeX
@misc{fang2025graph,
  author = {Jiwei Fang and Bin Zhang and Changwei Wang and Jin Wan and Zhiwei Xu},
  title = {{Graph of Verification: Structured Verification of LLM Reasoning with Directed Acyclic Graphs}},
  year = {2025},
  eprint = {2506.12509},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.12509},
}

Loading related content...

Figure