用中间状态链将自然语言证明转为形式化证明,提升成功率。
Translating Informal Proofs into Formal Proofs Using a Chain of States
- 先提取逻辑步骤间的中间形式状态序列,再生成连接动作
- 在有限计算资源下,证明成功率达78.3%,优于基线方法
- 适合数学自动化证明研究者和形式化系统开发者
我们解决在受限计算预算下,将自然语言表达的非正式数学证明转换为Lean4中的形式化证明的问题。核心思路是:非正式证明常通过一系列逻辑推演(如蕴含或等价)推进,但不显式写出中间结果或辅助引理;而形式系统如Lean4要求每个证明状态及连接它的策略都明确表达。为此,我们提出两阶段框架:首先从非正式论证中提取“状态链”(Chain of States, CoS),即与逻辑结构对齐的一系列中间形式证明状态;随后生成策略以在相邻状态间转移,构建完整形式证明。该中间表示显著降低策略生成复杂度,并增强与非正式推理模式的对齐。我们构建了专用数据集和评估基准,并引入交互式框架支持从形式状态生成策略。实验表明,本方法显著优于现有基线,在相同条件下证明成功率达到78.3%。
原文摘要 · Abstract (English)
We address the problem of translating informal mathematical proofs expressed in natural language into formal proofs in Lean4 under a constrained computational budget. Our approach is grounded in two key insights. First, informal proofs tend to proceed via a sequence of logical transitions - often implications or equivalences - without explicitly specifying intermediate results or auxiliary lemmas. In contrast, formal systems like Lean require an explicit representation of each proof state and the tactics that connect them. Second, each informal reasoning step can be viewed as an abstract transformation between proof states, but identifying the corresponding formal tactics often requires nontrivial domain knowledge and precise control over proof context. To bridge this gap, we propose a two stage framework. Rather than generating formal tactics directly, we first extract a Chain of States (CoS), a sequence of intermediate formal proof states aligned with the logical structure of the informal argument. We then generate tactics to transition between adjacent states in the CoS, thereby constructing the full formal proof. This intermediate representation significantly reduces the complexity of tactic generation and improves alignment with informal reasoning patterns. We build dedicated datasets and benchmarks for training and evaluation, and introduce an interactive framework to support tactic generation from formal states. Empirical results show that our method substantially outperforms existing baselines, achieving higher proof success rates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。