提出对称性框架,让AI证明数学定理更稳定可靠
What are the Right Symmetries for Formal Theorem Proving?

- 用范畴论定义证明变换的对称性,确保等价命题表现一致
- 现有大模型证明器对同一问题不同表达结果差异大,稳定性差
- 测试时多重重写聚合提升成功率,适合追求鲁棒性的研究者
基于大语言模型(LLM)的形式化定理证明器对问题表述的细微变化极为敏感:语义等价的命题可能表现出截然不同的证明成功率,暴露出其未能尊重形式数学中的结构对称性。这引出核心问题:形式化定理证明中应具备何种正确对称性?本文引入重写范畴(rewriting categories),一种范畴论框架,用于刻画由证明策略引发的组合性、一般不可逆变换,并据此形式化两种对称性概念:证明等变性(proof equivariance),描述证明分布如何随重写变换;成功不变性(success invariance),要求等价命题被解决的概率相同。我们发现,基于状态的下一步策略模型天然满足证明等变性,而当前最先进的LLM证明器两者皆不满足,对等价表述表现波动剧烈。为此,我们提出测试时方法,通过对输入进行等价重写并聚合结果,理论上证明其在采样极限下可恢复成功不变性,实证显示在固定推理预算下显著提升鲁棒性与性能。结果表明,对称性是当前LLM定理证明中缺失的关键归纳偏置,而测试时计算是近似该偏置的可行路径。
原文摘要 · Abstract (English)
Formal theorem provers based on large language models (LLMs) are highly sensitive to superficial variations in problem representation: semantically equivalent statements can exhibit drastically different proof success rates, revealing a failure to respect structural symmetries inherent in formal mathematics. This raises a central question: what are the right symmetries for formal theorem proving? We introduce rewriting categories, a category-theoretic framework capturing the compositional, generally non-invertible transformations induced by proof tactics, and use it to formalize two symmetry notions: proof equivariance, governing how proof distributions transform under rewrites, and success invariance (i.e., invariance of success probability), requiring equivalent statements to be solved with the same probability. We observe that state-based next-tactic provers naturally satisfy proof equivariance by operating on proof states. In contrast, state-of-the-art LLM-based provers satisfy neither property, exhibiting large performance variation across equivalent formulations. To mitigate this, we propose test-time methods that aggregate over equivalent rewritings of the input, showing theoretically that they recover success invariance in the sampling limit, and empirically, that they improve robustness and performance under fixed inference budgets. Our results highlight symmetry as a key missing inductive bias in LLM-based theorem proving and suggest test-time computation as a practical route to approximate it.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。