VeriBound：使用正式验证工具训练的过程奖励模型的 PAC-贝叶斯泛化界限

过程奖励模型 (PRM) 为 大语言模型 (LLM) 推理提供步骤级验证，但其训练数据获取仍然是一个瓶颈：人工注释成本高昂，蒙特卡罗推出估计存在噪音。最近的一种方法 FOVER 在由 Z3 和 Isabelle 等形式验证工具自动注释的步骤级错误标签上训练 PRM，并凭经验观察从符号任务到不同推理基准的跨任务泛化。然而，这种泛化现象缺乏任何理论解释，并且此类 PRM 的泛化误差、样本复杂性、收敛速度或下游 Best-of-K 性能不存在正式界限。我们提出了 VeriBound，一个理论框架，为使用形式验证工具训练的 PRM 提供 PAC-贝叶斯泛化界限。我们建立了四个主要结果：（i）PAC-贝叶斯泛化界限，它将形式验证注释训练数据的经验验证误差与未见推理任务的预期误差联系起来，该界限取决于形式验证的准确性以及训练和测试任务分布之间的差异； (ii) 样本复杂度结果表明 $O(d \log(d/δ) / ε^2)$ 形式验证注释示例足以以 $1-δ$ 概率实现泛化误差 $ε$，其中 $d$ 是 PRM 假设类的复杂度； (iii) 收敛分析，证明带有正式验证标签的 PRM 训练在 $L$ 平滑度和有界方差条件下以线性速率收敛； (iv) 将步骤级验证错误与 Best-of-K 性能下降联系起来的错误传播界限。