On Learning Verifiers and Implications to Chain-of-Thought Reasoning

会议: NeurIPS 2025
arXiv: 2505.22650
代码: 无
领域: LLM推理验证与理论学习
关键词: PAC学习, 验证器, CoT推理, 可验证性, 样本复杂度

一句话总结

从PAC学习角度系统研究CoT验证器的可学习性，在不同验证目标下给出样本复杂度的上下界，并揭示验证与生成之间的有趣计算关系。

研究背景与动机

1. 问题: CoT推理容易出现错误，需要可靠的验证器检查推理步骤正确性
2. 传统思路: 形式化验证方法对自然语言无效，需要学习方法
3. 关键挑战: 如何将随机步骤序列推理分解为可验证的步骤验证
4. 研究价值: 从统计学习角度理解验证器的基本限制和可能性

方法详解

整体框架

论文提出三种递进式的验证概念：

1. 简单PAC验证 (SVPAC): 给定包含正确步骤标签的推理序列，学习验证每一步是否正确

2. 可信PAC验证 (TVPAC): 给定黄金标准推理器g(x)，学习验证器在大多数问题上都拒绝错误推理

3. γ-TVPAC: 黄金标准追踪数量可任意多时，学习验证器保证完备性和可靠性

关键理论结果

定理3.1-3.3: SVPAC可学习性与VC维 - 有限验证类：样本复杂度 O(log|H|/ε) - 有限VC维：样本复杂度 O(VCDim(H)logT/ε) - T为最大推理长度

定理4.4-4.5: TVPAC可学习性
- 有限验证类：O(log|H|/ε) - 有限VC维：O(VCDim(H)·log(kT|Σ|)/ε)
- k为每问题的正确推理数量

定理4.9-4.11: γ-TVPAC的线性下界 - 当访问有限正确示例时，需要Ω(|H|)样本 - 即使进行非参监督学习，完备性要求也导致不可避免的线性依赖

实验关键数据

核心理论对比表

验证目标	训练数据格式	学习算法	VC样本复杂度上界
SVPAC	随机序列+标签	ERM	O(VCDim logT)
TVPAC	黄金标准集合	ERM	O(VCDim·log(kT|Σ|))
γ-TVPAC	随机正确序列	算法1(交集)	Ω(|H|)下界

关键发现与启示

研究维度	主要发现
生成vs验证等价性	k=1时，TVPAC验证等价于CoT生成（
计算分离	USAT问题上存在高效验证但生成困难的例子
可靠性要求	soundness+completeness导致线性样本复杂度
分布鲁棒性	TVPAC相比SVPAC提供更强的分布外保证

亮点与洞察

1. 理论完整性: 系统地给出了三种验证强度的样本复杂度界，上下界都有
2. 验证-生成等价性: 揭示了验证和生成在特定条件下的深刻联系
3. 计算复杂性: 构造例子说明验证虽然通常比生成简单，但在某些情况下两者复杂度相当
4. 实用启示: 指导如何设计可学习的验证系统

局限性

1. 假设条件: 要求gold标准推理的代数性（有限步规模）
2. 自然语言: 现有框架主要针对formal reasoning，自然语言的适用性有限
3. 实验验证: 论文为纯理论，缺乏实验验证
4. 实时性: 没有考虑在线学习或增量更新场景

相关工作

• PAC学习: 经典的SVM、decision trees、VC理论
• 形式化验证: Lean证明检查、Z3求解器
• CoT生成: o1、DeepSeek-R1等长思维模型
• 学习论文: JVB+对CoT生成的样本复杂度分析

评分

⭐⭐⭐⭐⭐

---