[Paper] 关于以推理为中心的 LLM 自动定理证明

Source: arXiv - 2604.19558v1

Overview

本文提出了 ReCent‑Prover，一种将大型语言模型（LLM）与 Coq 定理证明器相结合的新型证明助理代理。通过让 LLM 扮演更“以推理为中心”的角色——显式规划证明步骤并批评自己的输出——该系统在 CoqStoq 基准上显著提升了自动定理证明的性能，同时保持相同的 LLM 调用预算。

关键贡献

• 使用反射进行验证 – 一个反馈回路，LLM 检查其生成的策略，当策略可能错误时生成简洁的失败摘要，并在其到达 Coq 之前将其丢弃。
• 使用规划进行检索 – 不再仅通过子目标相似性检索引理，LLM 首先草拟高层次的证明计划，然后获取符合该计划的引理，使检索与策略意图对齐。
• 预算感知设计 – 两个新组件都会增加 LLM 调用次数，但作者保持总体推理预算不变，展示了更聪明的调用使用方式胜过暴力生成。
• 实证收益 – 在 CoqStoq 基准上，ReCent‑Prover 将已证明定理的数量提升了 22.58 % 相对 于之前的最佳系统。

Source: …

方法论

1. 计划的提示工程 – LLM 接收定理的描述，并被要求输出一个简短的、高层次的证明大纲（例如，apply induction on n, then use lemma X）。
2. 基于计划的检索 – 将大纲用作对引理数据库的查询。仅检索与预期策略匹配的引理（例如，归纳引理、算术引理），从而降低噪声。
3. 策略生成 – LLM 根据检索到的引理和计划合成具体的 Coq 策略。
4. 反思循环 – 在将策略发送给 Coq 之前，系统运行轻量级的静态检查（类型检查、目标匹配），并让 LLM 反思 任何不匹配之处。LLM 返回一个简短的“失败摘要”，解释策略可能失败的原因，使系统能够在不进行昂贵的 Coq 调用的情况下丢弃或修改该策略。
5. 迭代执行 – 该过程重复进行，直至证明完成或 LLM 预算耗尽。

所有步骤均由用 Python 编写的轻量控制器协调；繁重的工作（语言理解、计划、反思）则通过 API 调用委托给标准 LLM（例如 GPT‑4 或 Claude）。

结果与发现

• 已证明定理： ReCent‑Prover 在 CoqStoq 上比之前的最先进方法多解决 22.58 % 的定理，在相同的 LLM 调用次数下。
• 效率： 反射步骤提前过滤掉约 30 % 的无效 tactic，减少了昂贵的 Coq 交互次数。
• 策略检索： 基于计划的检索相比纯子目标相似度检索提升了约 45 % 的引理相关性，从而生成更短的证明脚本。
• 消融研究： 移除反射或计划任一组件都会使性能回落到基线水平，证实两者都是必不可少的。

实际意义

• Developer‑Facing Proof Assistants: 将以推理为中心的 LLM 集成到交互式定理证明器中，可以使其更加自主，减少开发者目前所经历的手动“search‑and‑apply”循环。
• CI/CD for Formal Verification: 更快、更可靠的自动化证明生成意味着形式化验证步骤可以嵌入持续集成流水线，而不会产生高昂的计算成本。
• Tooling for Formal Methods Education: 学生可以受益于一个不仅提供策略建议，还解释建议为何失败的助手，将错误转化为学习机会。
• Cross‑Domain Retrieval: 计划条件检索的思路可以迁移到其他领域（例如代码合成、数据‑pipeline 构建），在这些场景中，高层计划应指导可复用组件的选择。

Limitations & Future Work

• LLM 依赖性: 该方法依赖底层 LLM 的质量；较便宜的模型可能无法提供可靠的反思或规划。
• 引理数据库的可扩展性: 随着引理库的增长，检索速度可能成为瓶颈；索引策略需要进一步研究。
• 超出 Coq 的泛化: 系统与 Coq 的 tactic 语言紧密耦合；将其适配到其他证明助理（Isabelle、Lean）将需要非平凡的工程工作。
• 预算敏感性: 虽然作者将 LLM 调用预算固定，但实际部署可能面临更严格的延迟或成本约束，这促使探索更激进的剪枝或缓存技术。

总体而言，ReCent‑Prover 表明，让 LLM 扮演更具策略性、自我批判的角色可以在自动定理证明中实现显著提升——这一洞见可能会重塑开发者利用 AI 进行形式化验证的方式。

作者

• Yican Sun
• Chengwei Shi
• Hangzhou Lyu
• Yingfei Xiong

论文信息

• arXiv ID: 2604.19558v1
• 分类: cs.SE
• 发表时间: 2026年4月21日
• PDF: 下载 PDF