arXiv:2605.25556cs.LOcs.AI2026-05

通过快照复用证明状态,显著加速Lean 4中的自动定理搜索。

Keep the Proof State Live: Snapshotting for Efficient Tactic Search in Lean 4

  • 引入证明状态快照技术,避免重复重构
  • 在48个测试问题上平均提速14倍,最高达50倍
  • 适合大规模自动定理证明研究者使用

基于Lean 4的自动化定理证明系统越来越多地采用并行策略搜索部分指定的证明,如Draft-Sketch-Prove(DSP)流水线。当前系统中,每个搜索分支需重新运行求解过程以重建证明状态,导致巨大开销。在包含Mathlib的Lean 4环境中,该开销由两部分构成:(1) 导入加载,即反序列化预编译库(约60秒/分支);(2) 定理体求解,需重新校验目标结论前的所有上下文(根据证明复杂度估算为18–735秒)。二者合计占分支总耗时超99%,使组合式搜索在规模上不可行。我们发现此开销源于证明搜索结构与执行模型的不匹配:分支通过重复重建证明状态实现,而非直接复用。为此,我们提出证明状态快照机制,仅在首次构建后保存并跨分支复用,仅需对Lean 4语言服务器做小范围扩展。在48个miniF2F-v2问题(45个证明阶段基准 + 3个完整端到端运行)上,相较标准回退方案,平均提速14倍,中位数9.7倍,最高达50倍。提速效果随分支数增加而增强。该方法与导入级缓存(如Kimina Lean Server)正交——后者可避免导入加载,但无法减少定理体求解开销。发布时将开放修补后的Lean二进制及Snapshot-DSP流水线源码。

原文摘要 · Abstract (English)

Automated theorem proving systems built on Lean 4 increasingly rely on parallel tactic search over partially specified proofs, such as those generated by Draft-Sketch-Prove (DSP) pipelines. In current systems, each search branch reconstructs a proof state by re-running elaboration, leading to substantial per-branch overhead. In Lean 4 with Mathlib, this cost has two components: (1) import loading, which deserializes pre-compiled libraries (~60 s per branch); and (2) theorem-body elaboration, which re-checks the theorem context up to the target goal (estimated 18-735 s depending on proof complexity). Together, these account for >99% of per-branch wall time, making portfolio-based search impractical at scale. We observe that this overhead arises from a mismatch between the structure of proof search and its execution model: branching is implemented via repeated reconstruction of proof states rather than direct reuse. To address this, we introduce proof-state snapshotting, which captures the elaborated proof state once and reuses it across branches via a small extension to the Lean 4 language server. Across 48 miniF2F-v2 problems (45 prove-phase benchmarks and 3 full end-to-end runs), our approach achieves a 5.6-50x wall-time speedup over the standard fallback (average 14x, median 9.7x). Speedup increases with the number of proof branches. Our method is orthogonal to import-level caching (e.g., Kimina Lean Server), which avoids import loading but not theorem-body elaboration. The patched Lean binary and the Snapshot-DSP pipeline will be released as open source upon publication.

定理证明Lean 4效率优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。