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:
- 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.
- Topological Sorting: GoV ensures that premises are verified before the conclusions that rely on them, maintaining causal consistency.
- Sequential Verification: An LLM verifier checks each unit (node or block) one by one.
- 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).
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