🤖 AI

Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification

本文提出了名为 Goedel-Code-Prover 的层次化证明搜索框架，通过结合构造性理由与结构有效性的分解评分机制，训练了一个统一的 8B 参数模型，在 Lean 4 代码验证任务中以显著优于更大规模基线的成功率实现了高效的自动化形式化验证。

原作者： Zenan Li (Mike), Ziran Yang (Mike), Deyuan (Mike), He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin

发布于 2026-03-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Zenan Li (Mike), Ziran Yang (Mike), Deyuan (Mike), He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一个名为 Goedel-Code-Prover 的新系统，它的核心任务是教人工智能如何像人类专家一样，用数学证明的方式去“严格检查”电脑代码是否正确。

为了让你更容易理解，我们可以把这件事想象成建造一座摩天大楼，而 AI 就是那个负责检查大楼是否安全的“超级工程师”。

1. 为什么需要这个系统？（背景）

现在的 AI（大语言模型）写代码很厉害，就像是一个才华横溢但有点粗心的建筑设计师。它能画出很漂亮的图纸，也能写出能跑通的代码。

问题：AI 写的代码通常只能“看起来能跑”，但无法保证在极端情况下（比如输入了奇怪的数据）不会崩溃或出错。就像设计师画了图，但没经过严格的力学计算，万一遇到地震怎么办？
传统方法：以前，要证明代码绝对安全，需要人类专家手写“数学证明”。这就像让一位老工匠拿着尺子和计算器，花几个月时间去计算每一根梁的承重，非常累，而且很难普及。
AI 的尝试：最近，AI 开始尝试自己写这些“数学证明”。但在数学题上 AI 表现很好，一旦到了写代码这个领域，AI 就经常“翻车”。

2. AI 为什么在代码验证上会“翻车”？（核心难点）

论文指出了两个主要“水土不服”的原因：

原因一：没有“教科书”可以抄（无根基的分解）
- 数学界：AI 在训练时读过无数本数学书、竞赛题解。当遇到难题时，它知道怎么把大问题拆成小问题（比如“先证明 A，再证明 B，最后得出 C"），因为它见过类似的套路。
- 代码界：代码世界没有这种“通用套路”。每个程序都是独特的，就像每栋大楼的结构都不同。AI 以前没见过这种特定的“大楼结构”，所以它瞎拆出来的“小问题”往往是错的，或者拆了个寂寞（并没有变简单）。
原因二：工具包不匹配（战术错位）
- 数学证明：主要靠代数运算、公式推导。
- 代码证明：需要处理具体的逻辑，比如“列表里有没有重复元素”、“循环会不会死锁”。这需要完全不同的“工具”（就像修水管和修电路用的工具不一样）。AI 如果只学过数学，拿到代码题就会拿着“数学尺子”去量“电路”，怎么量都不对。

3. Goedel-Code-Prover 是怎么解决的？（核心创新）

为了解决这个问题，作者设计了一个**“分层级”的搜索框架**，就像是一个**“总指挥 + 特种部队”**的协作模式。

第一步：聪明的“总指挥”（分层分解）

系统不再让 AI 直接去证明整个大定理（就像不让新手直接去盖整栋楼）。

策略：AI 先当“总指挥”，把那个巨大的、复杂的验证目标，拆解成一系列更小、更简单的“子任务”（子引理）。
比喻：就像盖大楼，总指挥先说：“我们要先打地基，再建框架，最后装修。”它把“盖大楼”这个大目标，拆成了“打地基”、“建框架”等小目标。
关键创新（打分机制）：怎么知道拆得对不对呢？系统发明了一个**“智能打分器”**。
- 如果拆出来的小任务逻辑不通（比如“证明 1+1=3"），直接打 0 分扔掉。
- 如果拆出来的小任务虽然对，但比原题还难，也打低分。
- 只有那些逻辑通顺且明显变简单的拆解，才会得到高分。这个分数既是训练时的“奖励”，也是搜索时的“导航仪”。

第二步：专业的“特种部队”（逐个击破）

一旦“总指挥”把大任务拆好了，剩下的就是“特种部队”（AI 模型）的工作了。

策略：针对每一个小任务，AI 利用 Lean 4（一种像编译器一样的数学工具）提供的实时反馈，一步步写出证明代码。
比喻：就像建筑工人拿着图纸，每砌一块砖，系统就检查一次：“这块砖稳不稳？”如果不稳，系统会报错，工人就马上修改，直到这块砖完美为止。

4. 训练方法：怎么教 AI 学会这一套？

作者没有让 AI 从头学，而是用了**“先模仿，后实战”**的混合训练法：

模仿学习（SFT）：先用顶级 AI 生成的“完美拆解案例”教它，让它学会基本的拆解思路。
强化学习（RL）：让 AI 自己去尝试拆解。
- 如果它拆得好（得分高），就给它奖励。
- 如果它拆得不好，就让它重来。
- 关键点：为了解决“拆解”和“证明”奖励不一致的问题（拆解有连续分数，证明只有成功/失败），作者设计了一种混合机制，既鼓励它去探索新的拆解方式，又保证它能把证明写对。

5. 结果如何？（战绩）

以小博大：作者训练了一个只有 80 亿参数（8B）的模型。
吊打对手：这个“小个子”模型在三个代码验证测试集上，成功证明了 62% 的代码任务。
对比：这个成绩比目前最强的其他 AI 模型（有些甚至大了 84 倍，有几百亿参数）还要好 2.6 倍！
越练越强：给这个模型更多的计算时间和尝试次数，它的成功率还会稳步上升，说明它真的学会了“思考”和“规划”，而不是死记硬背。

总结

这篇论文的核心思想就是：不要指望 AI 一下子就能解决所有复杂的代码安全问题。

我们要教 AI 像人类专家一样，先学会“拆解问题”（把大象装进冰箱分几步），再学会“逐个解决”。通过一个聪明的**“打分机制”**来指导 AI 如何拆解，最终让一个小小的 AI 模型，也能完成以前只有超级计算机或人类专家才能完成的代码安全验证工作。

这就好比，以前我们以为只有大力士（超大模型）才能搬动巨石，现在发现，只要给小个子（8B 模型）配上一套聪明的杠杆和滑轮组（分层分解 + 打分机制），它也能轻松把巨石搬走。

这篇论文提出了一种名为 Goedel-Code-Prover 的框架，旨在解决大型语言模型（LLM）在形式化代码验证（Formal Code Verification）中的核心难题。该框架基于 Lean 4 定理证明器，采用**分层证明搜索（Hierarchical Proof Search）**策略，将复杂的验证目标分解为结构更简单的子目标，从而显著提升了自动化代码验证的成功率。

以下是该论文的详细技术总结：

1. 研究背景与问题定义 (Problem)

核心挑战：虽然 LLM 在代码生成方面表现优异，但生成的代码往往缺乏严格的正确性保证。传统的测试无法覆盖所有边界情况和逻辑错误。形式化验证（如使用 Lean 4）可以提供机器可检查的证明，但手动编写证明极其耗时且需要专家知识，而现有的自动化方法难以处理。
现有方法的局限性：
- 数学与代码的鸿沟：现有的 LLM 证明器（如 DeepSeek-Prover, Goedel-Prover）主要在数学领域取得成功。数学证明依赖于共享的库（如 Mathlib）和通用的推理直觉，而代码验证面临**概念增殖（Concept Proliferation）**问题：每个新程序都引入独特的控制流、数据结构和不变量，缺乏现成的库支持。
- 无根基的分解（Ungrounded Decomposition）：LLM 缺乏关于“如何证明程序正确性”的自然语言语料库，导致其生成的子目标往往语义无效、不简化原问题，甚至无法证明。
- 策略分布偏移（Tactic Distribution Shift）：代码验证需要特定的自动化策略（如 grind, native_decide 处理离散和递归域），而数学证明多依赖代数策略（如 linarith）。在数学语料上训练的模型难以正确调用代码验证所需的工具。
任务定义：给定一个 Lean 4 程序 $C$ 、前置条件 $P$ 和后置条件 $Q$ ，目标是自动生成机器可验证的证明项 $\tau$ ，证明 $\forall x, P(x) \to Q(x, C(x))$ 。

2. 方法论 (Methodology)

论文提出了一种分层证明搜索框架，核心思想是“先分解，后证明”，并引入了一个统一的策略模型和评分机制。

2.1 分层证明搜索框架

框架分为两个阶段，由同一个 LLM 策略 $\pi$ 驱动：

递归引理分解（Recursive Lemma Decomposition）：
- 将顶层验证目标 $G$ 递归分解为一系列结构更简单的子引理（Sub-lemmas）。
- 每个分解步骤需经过**证明重构（Proof Reconstruction）和Quickcheck（自动反例搜索）**的验证，确保子目标在逻辑上蕴含父目标且语义有效。
引理完成（Lemma Completion）：
- 对分解后的叶子引理，通过迭代生成策略（Tactics）和编译器反馈进行证明，直到所有子目标被消除。

2.2 核心创新：分解评分机制 (Decomposition Score)

为了解决奖励稀疏和分解质量评估难的问题，作者设计了一个原则性的分解评分 $S$ ，该分数同时作为训练奖励和推理时的排序标准，确保训练与部署的一致性。
评分 $S$ 由两部分组成：

构建性证明（Constructive Justification, $v$ ）：
- 逻辑有效性：子引理必须能通过证明重构推导出父目标。
- 语义有效性：通过 Quickcheck 进行随机输入采样，若发现反例则直接丢弃该分解。
结构有效性（Structural Effectiveness, $r$ ）：
- 衡量分解是否真正降低了问题难度。定义算子足迹（Operator Footprint） $d(\cdot)$ 为验证目标 AST 中逻辑算子和程序算子的总数。
- 计算子目标相对于原目标的复杂度降低比率。使用 LogSumExp 近似最大值，确保对任何子目标的简化都能获得奖励。
最终公式： $S = r \cdot v$ 。

2.3 混合强化学习训练流程 (Hybrid RL)

由于分解任务有稠密的连续奖励（评分 $S$ ），而完成任务只有稀疏的二元奖励（证明成功/失败），直接联合训练会导致梯度失衡。作者采用了两阶段混合训练：

监督微调（SFT）：利用前沿模型（GPT-5.2, Gemini-3-Flash）生成的分解和完成轨迹，对 Qwen-3-8B 基座模型进行初始化，使其具备双重能力。
混合强化学习（Hybrid RL）：
- 分解优化：使用 GRPO (Group Relative Policy Optimization)，利用连续评分 $S$ 驱动探索，优化分解策略。
- 完成稳定：通过**监督回放（Supervised Replay）**高质量证明轨迹来稳定完成策略，避免二元奖励导致的训练不稳定。
- 课程学习：成功分解出的子引理会被反馈到问题集中，形成不断扩展的、难度递进的课程。

3. 主要贡献 (Key Contributions)

分层证明搜索框架：首个专门针对 Lean 4 代码验证设计的框架，通过“分解 - 完成”循环将复杂验证任务转化为可管理的子任务。
原则性分解评分：提出结合“构建性证明”与“结构简化”的评分机制，统一了训练奖励和推理搜索标准，有效解决了代码验证中缺乏分解直觉的问题。
统一策略与混合 RL：训练了一个 8B 参数的统一策略模型（Goedel-Code-Prover-8B），通过混合 RL 解决了分解（稠密奖励）与完成（稀疏奖励）的联合优化难题。
性能突破：在三个基准测试上，以 8B 模型超越了此前最大的 671B 参数模型及多个前沿闭源模型。

4. 实验结果 (Results)

数据集：在 Verina (189 题), Clever (161 题), AlgoVeri (77 题) 三个 Lean 4 代码验证基准上共 427 个任务进行测试。
整体表现：
- Goedel-Code-Prover-8B 取得了 62.0% 的整体证明成功率。
- 相比最强的基线模型（BFS-Prover-V2-32B，23.8%），提升了 2.6 倍。
- 超越了参数量高达 84 倍（671B）的神经证明器。
- 显著优于单步生成的前沿模型（如 GPT-5.3-Codex, Claude-Opus-4.6 等，成功率普遍低于 25%）。
推理扩展性（Inference-Time Scaling）：
- 证明成功率随着搜索迭代次数和并行采样预算（pass@k）的增加而单调提升，显示出未饱和的扩展潜力。
- 分解评分与最终证明成功率高度相关（AUROC = 0.903），证明评分机制能有效指导搜索方向。
消融实验：
- 分层分解是提升性能的最关键因素（无分解时成功率仅 26.4%）。
- 分解模块和完成模块经过联合训练后产生了协同效应，组合效果优于单独替换为基线模型。
证明复杂度：平均每个验证任务需要 8-17 个辅助引理，证明代码平均长度超过 130 行，最复杂的证明超过 680 行，证明了框架处理深度结构化推理的能力。

5. 意义与结论 (Significance)

填补了数学与代码验证的鸿沟：论文证明了通过特定的架构设计（分层分解）和训练策略（混合 RL + 连续评分），LLM 可以克服代码验证中“概念增殖”和“策略分布偏移”的困难，不再单纯依赖数学语料库的迁移。
小模型超越大模型：展示了 8B 参数量的专用模型，通过高效的搜索策略和领域适应，可以超越参数量大得多的通用或数学专用模型，为资源受限场景下的形式化验证提供了新路径。
自动化验证的新范式：该框架将形式化验证从“一次性生成”转变为“规划 - 搜索 - 迭代”的过程，使得验证非平凡（Non-trivial）的算法和程序成为可能，推动了形式化方法在软件工程中的实际应用。

局限性：目前假设程序和规范已形式化为 Lean 代码，未来工作将致力于从自然语言规范到 Lean 的自动翻译，以及处理更复杂的跨过程依赖和大型代码库。