关于验证器的学习及其对思维链推理的影响
On Learning Verifiers and Implications to Chain-of-Thought Reasoning
Maria-Florina Balcan, Avrim L. Blum, Zhiyuan Li, Dravyansh Sharma
neural information processing systems · 2025-01-01
开放获取大模型与语言推理与思维链被引前 10%影响因子 ≈3.9
摘要
思维链推理已成为解决复杂数学与逻辑问题的有效方法，但该方法常常因错误或无根据的推理而偏离正轨。形式化数学推理可通过正式验证器加以检验，是应对这一问题的途径之一。然而，当前大语言模型尚不足以以形式化方式解决复杂问题，甚至将非正式的问题表述转化为形式化语言也颇具挑战性。基于这一现实，本研究聚焦于自然语言思维链推理中可靠验证器的学习问题：给定问题描述及自然语言形式的逐步解决方案，验证器的目标是若方案中的推理步骤均合理则输出“是”，否则输出“否”。本研究构建了用于探讨该问题的正式PAC学习框架，提出并分析了该框架下不同强度的多种自然验证目标，给出了满足这些目标的验证器学习的样本复杂度上界，同时也针对缺乏额外假设时其他自然验证目标的学习问题得出了下界与不可行性结论。
本摘要由 AI（Hy-MT2-Pro）翻译生成，仅供参考，请以原文为准。
AI 综述
基于全文生成- 主要观点
- 论文针对自然语言Chain-of-Thought推理中错误或缺乏依据的推理步骤难以检测的问题，提出学习验证器：给定问题陈述与逐步解答，验证器输出[Yes]或[No]，并在错误时定位首个错误步骤。核心论点是可在PAC学习框架下刻画不同强度的验证目标：简单验证器（SVPAC）只需在训练分布内匹配理想验证器h*；可信验证器（TVPAC与γ-TVPAC）要求对大多数问题拒绝一切错误推理轨迹（可靠性），并接受金标准推理器g产生的全部或大部分正确轨迹（完备性）。论文进一步论证简单验证目标不能抵御因验证器反馈导致的分布偏移，而可信验证目标对推理轨迹的分布偏移更稳健。材料将验证问题与形式数学推理对比，指出形式化非形式问题陈述的困难及当前LLM形式求解能力不足，因而转向自然语言CoT验证器的可学习性。
- 研究方法
- 采用形式化PAC学习框架，定义验证器h: X×Σ*→{YES,NO}，并给出SVPAC、TVPAC、γ-TVPAC等学习目标及对应的样本复杂度定义。对有限验证器类用union bound和ERM得到O(log|H|)样本上界；对有限VC维类通过Sauer引理与ERM得到O(VCdim(H) log T)上界，并分析下界与不可能性结果。可信验证部分引入金标准推理器g与有限推理步骤集Σ，通过构造偏离金标准证明树的负例、取一致验证器交集（closure算法）等分析学习算法。论文还讨论与多类分类、单边错误学习、交互式证明者的关系，并给出生成与验证之间的计算差距及特例等价（Remark 4.6）。
- 学术贡献
- 理论建构层面，论文为自然语言CoT验证器建立PAC学习框架，区分简单验证与可信验证两类目标，并给出可靠性/完备性的形式定义（stepwise与overall soundness、γ-completeness）。方法上给出基于ERM、VC维和closure算法的样本复杂度上界，以及下界和不可能性结果，揭示不同验证目标的可学习性边界。领域拓展方面，将验证器学习与单边错误学习、选择性分类、交互式证明者、精确学习等线索连接，并指出生成与验证之间的计算差距，对CoT推理可靠性与验证器设计这一子议题有理论价值。
- 存在局限
- 论文主要为理论分析，材料中未明确提及在真实LLM生成的CoT轨迹上的实验验证或基准测试。可信验证结论依赖较强假设：推理步骤集合Σ有限、可获得金标准推理器g及其正确轨迹，且正确性以h*或g为参照而非独立真值。简单验证仅保证同分布D上的误差，作者自己也指出其对验证器反馈引发的分布偏移不稳健；TVPAC虽对推理轨迹分布偏移稳健，但不保证验证g之外的合法轨迹。样本复杂度结果主要关注样本量，材料中未明确提及学习算法的计算复杂度或对无限Σ、任意长轨迹的完整处理（后者被列为开放问题）。
- 进一步研究方向
- 可在真实CoT数据上比较SVPAC与TVPAC验证器的训练样本需求与错误定位准确率，检验理论界与实际样本量的差距。可研究Σ无限或轨迹长度T无界时的验证器学习，结合多类分类的无限类规模结果给出样本复杂度或不可能性刻画。可引入主动学习或交互式证明者设定，分析在prover提供逐实例保证时能否降低验证器学习样本复杂度。可探索仅用正例（gold标准轨迹）学习可靠验证器的算法，并分析其与closure算法、单边错误学习的联系。还可将框架扩展到规划、SAT、数独等序列推理任务，检验跨任务的可迁移性；材料中未明确提及这些实证方向，但可由其形式化设定直接推出。
本综述由 AI（deepseek-flash）阅读开放获取全文自动生成，仅供参考，不代表原文作者观点，请以原文为准。
参考文献
相关论文
话题：Machine Learning and Algorithms