acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Large Language Model Reasoning, Process Verification, Dependency Graphs

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 2 reviews, above 9% of the others.
Reviewer_XJe3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors propose Adaptive Dependency Graph Verification, a training-free framework for process-level verification of LLM reasoning. This method incrementally decomposes a reasoning trajectory into atomic units, constructs a dependency DAG, and verifies each step using its recursively retrieved ancestor context. The conducted experiments on some math benchmarks with Qwen2.5 series models verifiers show improved first-error localization over GoV in many settings. The paper also reports GPT-4o and DeepSeek rationale audits, with approximately 2–11% reductions in verifier context length.

Critical strengths

ADGV addresses a meaningful problem that full-history verification can expose the verifier to irrelevant reasoning, while fixed decomposition may fail to reflect instance-specific dependencies. The proposed ancestor-based context construction is simple, intuitive, and compatible with existing verifier models without additional training. The evaluation covers multiple mathematical benchmarks and verifier scales.

Critical weaknesses

The core pipeline is under-specified and its efficiency claims are incomplete. The paper does not clearly identify the model used for decomposition and dependency analysis, the number of additional inference calls, parsing or invalid-output handling, graph-construction accuracy, or the total end-to-end token and latency cost. Therefore, the reported 2–11% context reduction does not account for the overhead introduced by ADGV itself. In addition, the mapping between newly created atomic-step indices and ProcessBench’s original annotated step indices is unclear, and PARC is mentioned as a baseline but is absent from the reported tables.

Questions for authors

Please refer to the weaknesses above for the concerns. Below are some additionals:

  1. The experimental setup states that PARC is included in the comparison, but no PARC results appear in the tables. Was PARC evaluated under the same setting?
  2. Is decomposition and dependency analysis performed by the same verifier model or by a separate model? Please specify the model, decoding settings, and total additional inference cost.
Reviewer_WEtdOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Adaptive Dependency Graph Verification (ADGV), a training-free framework for fine-grained verification of LLM reasoning. It decomposes reasoning trajectories into atomic steps, constructs dependency graphs, and retrieves relevant preceding steps to provide context for verification. Experiments on ProcessBench demonstrate improvements in error localization over existing baselines.

Critical strengths
  1. The paper is well-written and clearly structured, making the proposed approach easy to understand.
  2. The proposed method is training-free and demonstrates performance improvements over existing baselines across multiple benchmarks.
Critical weaknesses
  1. The proposed approach closely resembles existing methods, particularly GoV (Fang et al., 2026), PARC (Mukherjee et al., 2025), and Deductive Verification (Ling et al., 2023). These works have already explored decomposing reasoning into smaller units, modeling dependencies between steps, and selecting relevant premises for verification. In particular, GoV and PARC already employ dependency graphs for structured reasoning verification. The proposed adaptive ancestor retrieval appears to be an incremental extension rather than a fundamentally new technical contribution.
  2. The ablation results in Table 4 show relatively small improvements over the Split-only baseline, often less than one percentage point. Moreover, ADGV does not consistently outperform GoV across all settings in Table 1. These results raise concerns about the significance of the proposed dependency reconstruction mechanism.
  3. Although the paper reports reduced verification context length, it does not adequately account for the additional computational overhead of atomic decomposition and dependency graph construction. A comprehensive end-to-end inference cost comparison is needed to establish the practical benefits of the proposed method.
Questions for authors
  1. ADGV appears closely related to existing approaches such as GoV and PARC. Could the authors clarify the key technical novelty and explain how ADGV fundamentally differs from these prior works?
  2. The improvements reported in Table 4 are relatively small. Could the authors further clarify the respective contributions of dependency graph reconstruction and atomic decomposition to the overall performance gains?
  3. Constructing and maintaining dependency graphs may introduce substantial computational overhead. How does ADGV compare with existing methods under the same end-to-end computational budget, including the costs of decomposition, graph construction, and verification?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.