用进化搜索生成多样化的数学形式化表达,提升证明成功率。
FormalEvolve: Neuro-Symbolic Evolutionary Search for Diverse Autoformalization
- 通过变异、交叉和符号重写实现多样性进化搜索
- 在100次调用内达到CombiBench 58.0%、ProofNet 84.9%的准确率
- 适合需要高质量形式化输入的自动证明系统研究者
自动形式化旨在生成忠实表达非正式数学意图的形式化语句。然而,标准单输出评估将多对多问题简化为单输出预测,粒度过粗。对于下游证明而言,形式化语句不仅是翻译终点,更是影响证明搜索效率的接口。因此,本文将自动形式化重构为带预算的测试时搜索:FormalEvolve 维护可复用的编译可行档案库,并报告去重后的语义接受语句集合用于评估与证明。通过大模型驱动的变异、交叉、有限修补和符号抽象语法树(AST)重写扩展档案库,以增强结构多样性。在生成器调用预算 T=100 且固定大模型语义判别器条件下,FormalEvolve 在 CombiBench 上达到 SH@100 58.0%,在 ProofNet 上达 84.9%,优于所有无档案控制组,同时降低跨问题的语义成功集中度。在固定证明器预算 B=64 下评估,其产出语句集显著提升定理完整证明率;更强基线的生成实验也验证了档案搜索优势。人工忠实性审计校准了判别器正向输出。
原文摘要 · Abstract (English)
Autoformalization aims to produce formal statements that compile and faithfully preserve the intended meaning of informal mathematics. Yet standard single-output evaluation protocols collapse a many-to-many problem into a single-output prediction task. For downstream proving, this granularity is too coarse: a formal statement is not merely a faithful translation endpoint, but also a prover-facing interface whose structure can alter proof search under a fixed budget. We therefore recast autoformalization as budgeted test-time search: FormalEvolve maintains a compilation-feasible archive for reuse, while reporting the deduplicated semantically accepted repertoire for evaluation and downstream proving. It expands the archive with LLM-driven mutation, crossover, bounded patch repair, and symbolic Abstract Syntax Tree (AST) rewrites for structural diversity. Under a generator-call budget of T=100 with a fixed LLM semantic judge, FormalEvolve reaches SH@100 of 58.0% on CombiBench and 84.9% on ProofNet, improving over all no-archive controls while reducing the cross-problem concentration of semantic successes. To assess downstream value, we evaluate the resulting repertoires under a fixed B=64 prover budget, where they improve theorem-complete proving over the matched no-archive control; additional stronger-base statement-generation experiments show that archive-search gains hold with stronger seed and repair models. Manual faithfulness audits calibrate these judge-positive outputs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。