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

会议: AAAI 2026
arXiv: 2506.12509
代码: Frevor/Graph-of-Verification
领域: LLM推理
关键词: 推理验证, 有向无环图, 多粒度验证, 分解验证, 免训练方法

一句话总结¶

提出 Graph of Verification (GoV)，一种将 LLM 推理过程建模为有向无环图 (DAG) 的结构化验证框架，通过灵活的节点块(Node Block)架构实现多粒度验证——从形式化任务的原子步骤到自然语言叙述的段落级验证——在结构化和松散结构化推理基准上均显著优于整体验证和其他分解验证方法。

研究背景与动机¶

LLM 推理验证的关键挑战：LLM 经常产生看似合理但包含微妙逻辑缺陷的推理步骤，即使最终答案正确也可能过程有误，亟需严格评估推理过程的内在有效性。

整体验证的困境：将整个推理链一次性交给验证器 LLM 评估，认知负担过重，难以检测局部缺陷，且随推理链变长和复杂度增加，问题愈发严重。

训练式验证器的代价：基于过程的奖励模型(PRM)需要大量人工标注数据，训练成本高昂，且难以跟上前沿 LLM 快速迭代的步伐。

已有分解验证的局限：PARC 和 Deductive Verification 追求原子粒度+最小前提的验证策略，理论上最精确，但依赖脆弱的前提提取或声明步骤，在松散结构的自然语言推理中不可靠。

适应性缺口：从高度结构化的形式证明到高度非结构化的自然语言叙述，目前缺乏一个统一的框架来灵活应对不同推理结构——这是实现真正可靠推理验证的关键障碍。

核心洞察：受人类认知启发——面对复杂论证时，人们本能地将其分解为依赖序列逐步验证——这可以自然建模为 DAG。关键是验证粒度应该与推理结构匹配：结构化推理用原子粒度高精度验证，自然语言推理用块粒度保证鲁棒性。

方法详解¶

整体框架：四阶段验证流水线¶

DAG 建模：将推理过程建模为有向无环图 \(\mathcal{G} = (V, E)\)
拓扑排序：对 DAG 做拓扑排序，确保前提在结论之前被验证
顺序验证：LLM 按拓扑序逐个验证每个单元，基于已验证的前驱信息
早停错误定位：在首个检测到的错误处终止，实现精确的故障定位

关键设计 1：二维设计空间的形式化¶

作者首次将分解验证形式化为由验证粒度和上下文范围构成的二维设计空间，为验证策略的选择提供了原则性的理论框架：

维度一：验证粒度 - 原子粒度：推理分解为最小不可分逻辑单元（如单个加法运算 \(a + b = c\)），错误定位最精确，但要求推理结构高度清晰。 - 块粒度：多个相关原子步骤聚合为语义连贯的单元（如完整段落），更鲁棒且适应自然语言，但定位精度降低。

维度二：上下文范围 - 最小上下文：仅提供当前单元的直接前提，减少认知负担和干扰，但依赖可能出错的前提提取。 - 包含上下文：提供所有之前已验证的信息，更安全鲁棒但可能引入冗余。

关键洞察：最优配置取决于推理的固有结构——结构化推理适合"原子粒度+最小上下文"，自然语言推理宜采用"块粒度+包含上下文"。

关键设计 2：DAG 建模推理过程¶

节点 \(V = \{v_1, v_2, \dots, v_n\}\)：推理的基本验证单元，分为三类：
- 基础元素：前提、公理、事实（DAG 的根节点）
- 推导语句：从前驱节点通过逻辑规则或计算得出的中间结论
- 终止语句：推理过程的最终结论/目标
有向边 \(E \subseteq V \times V\)：\((v_i, v_j) \in E\) 表示 \(v_i\) 是 \(v_j\) 的直接前提，\(v_j\) 的有效性依赖于 \(v_i\)。
DAG 的理论优势：
- 有向性确保推理从前提到结论的方向性，消除歧义
- 无环性保证不存在循环依赖，防止"自证合理"

关键设计 3：多粒度拓扑单元¶

拓扑排序：对 DAG 求拓扑序 \(\sigma: V \to \{1, 2, \dots, n\}\)，使得 \(\sigma(v_i) < \sigma(v_j)\) 对所有边 \((v_i, v_j)\) 成立，得到验证序列 \(\mathcal{C}_{\text{verif}} = (c_1, c_2, \dots, c_n)\)。

原子节点：每个节点 \(v_k\) 作为独立验证单元，实现最细粒度的错误定位，适用于结构化推理。

节点块：将拓扑连续的节点分组为逻辑连贯的块 \(\mathcal{B} = (B_1, \dots, B_m)\)，满足两重约束： - 拓扑一致性：\(\max_{v \in B_j} \sigma(v) < \min_{v \in B_k} \sigma(v)\)，\(j < k\)，保持宏观依赖关系 - 语义连贯性：每个块对应完整的逻辑单元（如证明中的引理或叙述中的段落），禁止任意切分

退化情况：\(m = 1\) 时即为传统的整体验证。

关键设计 4：原子节点验证机制¶

验证函数 \(\text{Verify}(c_k, Pred_{\text{prov}}(c_k))\) 在拓扑序下对每个节点执行：

基础节点（\(Pred(c_k) = \emptyset\)）：直接验证其与问题陈述或领域知识的一致性。
推导节点（\(Pred(c_k) \neq \emptyset\)）：验证需同时满足两个条件：
所有直接前驱已被验证为 True
从前驱到当前节点的推理步骤本身是合理的

\[T(c_k) = (\forall c_i \in Pred(c_k), T(c_i) = \text{True}) \land \text{Verify}(c_k, Pred_{\text{prov}}(c_k))\]

关键设计 5：节点块验证机制¶

外部前提集：\(Pred_{\text{ext}}(B_j) = (\bigcup_{v \in V(B_j)} Pred(v)) \setminus V(B_j)\)，即所有内部节点的外部依赖。
实践中：对自然语言段落，\(Pred_{\text{prov}}(B_j)\) 通常包含所有之前已验证块的完整内容 \((B_1, \dots, B_{j-1})\)。
LLM 同时验证块的内部连贯性和块内所有语句基于外部前提的有效性。

早停与错误定位¶

验证沿拓扑序（或块序）进行，一旦发现某个单元为 False，即标记为最早失败点并停止验证。整个推理过程仅在所有单元均通过验证时才判定为有效。

实验与结果¶

实验一：Number Triangle Summation（结构化推理）¶

任务设计：从 \(N\) 个初始数出发，逐层对相邻数求和直到只剩一个数。每个推理过程有 50% 概率被引入单位错误。
配置：原子粒度 + 最小上下文（精确模式）
结果（Qwen2.5-72B-Instruct, F1 Score）：

问题规模 \(N\)	整体验证	GoV
\(N = 2\)	99.6	98.7
\(N = 4\)	93.3	97.9
\(N = 6\)	46.3	98.1
\(N = 8\)	49.5	98.1

随着问题复杂度增加，整体验证 F1 急剧下降（从 99.6 到 49.5），而 GoV 始终保持 97+ 的高水平。

实验二：ProcessBench（松散结构化推理）¶

数据集：GSM8K、MATH、OlympiadBench 上的推理过程验证
配置：块粒度 + 包含上下文（鲁棒模式）
结果（Qwen2.5-7B-Instruct, F1 Score）：

数据集	整体验证	PARC	GoV
GSM8K	47.3	47.0	58.0
MATH	34.6	43.3	55.0
OlympiadBench	32.7	-	42.9

GoV 在所有数据集上均显著超越整体验证和 PARC，尤其在 MATH 上 F1 提升超 20 个百分点。

关键发现¶

可扩展性：GoV 的优势随问题复杂度增加而愈发明显，解决了整体验证在长推理链上的致命弱点。
灵活性：同一框架通过配置不同粒度即可适应截然不同的任务类型。
模型泛化：从 7B 到 72B 不同规模的模型上 GoV 均有效。
免训练：无需任何标注数据或微调，开箱即用。

论文评价¶

优势¶

二维设计空间的形式化是重要的理论贡献，为分解验证提供了清晰的原则性指导。
Node Block 架构优雅地统一了原子验证和块验证，通过一个连续统涵盖了从精确到鲁棒的全谱系。
免训练设计使其具有高度灵活性和实用性。

局限¶

DAG 的构建本身依赖 LLM 的分解能力，在极松散的推理结构下可能不可靠。
Number Triangle Summation 是人工构造的基准，与真实推理场景有差距。
早停策略可能遗漏后续步骤中的独立错误。