用分层搜索提升代码验证成功率,突破大模型生成代码的正确性瓶颈。
Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification
- 分层分解验证目标,通过评分机制指导子任务拆解与证明顺序。
- 80亿参数模型在3个基准上达62.0%成功率,比最强基线高2.6个百分点。
- 适合研究形式化验证、自动化推理及大模型代码生成的开发者使用。
大型语言模型(LLMs)虽能生成看似合理的代码,但缺乏正确性保障。形式化验证需构建机器可检查的证明,当前自动化能力仍不足。本文提出面向Lean 4的分层证明搜索框架,将复杂验证目标分解为结构更简单的子目标,再进行战术级证明。核心是结合构造性理由与结构有效性设计的分解评分,该评分同时作为训练奖励和推理时的排序依据,实现优化与部署对齐。我们通过监督初始化加混合强化学习训练出统一策略模型Goedel Code Prover,其中连续分解奖励支持规划探索,监督回放则稳定证明生成。在包含427个任务的三个基于Lean的验证基准上,80亿参数模型达到62.0%的证明成功率,较报告设置下的最强基线提升2.6个百分点。进一步观察发现,推理时性能随搜索迭代次数和采样预算单调提升,而全证明基线在评估预算内已趋于饱和。
原文摘要 · Abstract (English)
Large language models (LLMs) can generate plausible code but offer limited guarantees of correctness. Formally verifying that implementations satisfy specifications requires constructing machine-checkable proofs, a task that remains beyond current automation. We propose a hierarchical proof search framework for automated code verification in Lean~4 that decomposes complex verification goals into structurally simpler subgoals before attempting tactic-level proving. Central to our approach is a principled decomposition score that combines constructive justification with structural effectiveness. The same score serves as both the training reward and the inference-time ranking criterion, aligning optimization and deployment. We train Goedel Code Prover, a single unified policy for both decomposition and completion, through supervised initialization followed by hybrid reinforcement learning, where a continuous decomposition reward supports planning exploration while supervised replay stabilizes proof generation. On three Lean-based code verification benchmarks comprising 427 tasks, our 8B-parameter model achieves a 62.0% prove success rate, a 2.6 improvement over the strongest baseline under the reported inference settings. We further observe consistent inference-time scaling: success rates improve monotonically with search iterations and sampling budget, while whole-proof baselines plateau within the evaluated budgets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。