Adaptive Dependency Graph Verification: Fine-Grained Verification of LLM Reasoning via Adaptive Dependency Reconstruction

Process-level verification of large language model reasoning requires sufficient context to judge each step, yet determining which preceding reasoning is relevant remains challenging in long reasoning traces. Existing structured verification methods typically rely on predefined reasoning units or fixed context construction strategies, which may fail to capture instance-specific dependencies. We introduce Adaptive Dependency Graph Verification (ADGV), a training-free framework that adaptively reconstructs verification contexts according to the dependency structure of each reasoning trace. ADGV first decomposes a solution into atomic reasoning units and constructs a directed graph capturing their prerequisite relations. For each target unit, it recursively traverses the dependency graph to reconstruct an ancestor-based context containing the relevant antecedent reasoning. This procedure preserves dependency-relevant information while excluding unrelated portions of the trace. We evaluate ADGV on ProcessBench across diverse mathematical reasoning tasks and multiple verifier scales. ADGV consistently improves first-error localization and step-level error attribution over existing graph-based verification, demonstrating that adaptive dependency reconstruction provides more effective verification contexts than predefined reasoning structures. These results establish ADGV as a practical approach to fine-grained reasoning verification without additional training or parameter updates.