用原子化策略让AI在Lean4中自动证明定理,效果稳定且可跑在普通电脑上。
Nazrin: An Atomic Neural Proof Automation Tactic in Lean 4
- 将复杂证明拆解为一组基础原子操作,统一调度逻辑
- 在Lean标准库和Mathlib中验证,能处理多种可证命题
- 基于图神经网络,适合普通硬件训练评估,易部署
在机器辅助定理证明中,证明代理需搜索一系列表达式与策略以完成证明。本文提出若干新概念与能力,应对现有挑战。首先引入一组 extbf{原子策略},该有限策略集足以证明Lean中所有可证命题。接着提出 extbf{转置原子化}算法,可将任意证明表达式转化为一系列原子策略。随后设计 extbf{ExprGraph}数据结构,实现对Lean表达式的紧凑表示。最后提出 extbf{Nazrin Prover}(Nuclear Atomizer for Inhabitation Problems),一个基于图神经网络的定理证明代理,采用原子策略与ExprGraph。Nazrin通过仅分发原子策略,有效规避了现有代理的多数难点,并具备在消费级硬件上训练与评估的鲁棒性。我们在Lean标准库和Mathlib的定理上展示了此类工具的潜力。
原文摘要 · Abstract (English)
In Machine-Assisted Theorem Proving, a theorem proving agent searches for a sequence of expressions and tactics that can prove a statement in a proof assistant. In this work, we introduce several novel concepts and capabilities to address obstacles faced by machine-assisted theorem proving. We first present a set of \textbf{atomic tactics}, a small finite set of tactics capable of proving any provable statement in Lean. We then introduce a \textbf{transposing atomization} algorithm which turns arbitrary proof expressions into a series of atomic tactics. We next introduce the \textbf{ExprGraph} data structure, which provides a succinct representation for Lean expressions. Finally, we present the \textbf{Nazrin Prover}, short for \textbf{N}eural \textbf{A}tomi\textbf{z}e\textbf{r} for \textbf{In}habitation Problems, a graph neural network-based theorem proving agent using atomic tactics and ExprGraph. Nazrin circumvents many challenges faced by existing proving agents by exclusively dispatching atomic tactics, and it is robust enough to both train and evaluate on consumer-grade hardware. We demonstrate the potential of tools like Nazrin using theorems from Lean's standard library and from Mathlib.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。