用抽象语法树提升定理证明效率,降低大模型调用成本。
AoA: Theorem Proving Agent over Abstract Syntax Tree of Redesigned Language
- 将证明代理从文本转为抽象语法树,直接操作结构化数据
- 相比现有方法减少2.9至6.9倍的令牌消耗,提速1.4至2.0倍
- 适配新型证明语言Minilang,适合形式化验证与自动化推理研究者
交互式定理证明(ITP)支撑程序验证与形式化数学,但人工成本限制其扩展性。基于大模型的证明代理虽可减轻负担,却面临高令牌消耗与API开销问题。我们发现根源在于:当前代理基于序列化的具体语法,以源码形式生成证明,并通过行号定位状态,每次修改均导致后续行偏移,需重复重定位错误与状态。这一依赖也阻碍了新兴证明语言Minilang的应用——尽管其在大模型证明中已达最先进水平,但尚未被训练语料覆盖。为此,我们提出将代理从源码迁移至抽象语法树(AST):模型以JSON形式输出Minilang的AST表示,通过树编辑模型融合证明操作与状态,使每一步操作自带子目标状态,可直接从树中读取。我们实现该设计为“Agent over AST”(AoA)。在miniF2F和NTP4VC-Pearl基准上,相比Amazon Isabelle Agent,AoA在标准化输入缓存下降低2.3–4.7倍的API成本,使用2.9–6.9倍更少的令牌,减少3.9–8.9倍工具调用,且完成速度提升1.4–2.0倍,同时在更难的验证任务上解决更多问题。
原文摘要 · Abstract (English)
Interactive theorem proving (ITP) underpins program verification and formalized mathematics, but its manual effort limits scalability. LLM-based proof agents promise to ease this effort, but their heavy token consumption and API cost remain a major obstacle. We trace this cost to a shared root: current agents operate on serialized concrete syntax, emitting proofs as source text and recovering proof states through separate, line-number-based queries, so every edit shifts later lines and forces repeated relocation of errors and states. This same dependence on concrete syntax also blocks adoption of Minilang, a recent proof language that reaches SOTA on LLM-based proving but is too new for LLMs' training corpora. We address both problems by lifting the agent off source text and onto the abstract syntax tree (AST): the model supplies proofs as JSON representations of Minilang's AST -- native to tool-calling LLMs -- and drives the prover through a tree-edit model that fuses proof operations and states into one proof tree, so each operation carries its own subgoal's state, readable directly off the tree. We realize this design in \emph{Agent over AST} (AoA). Against Amazon's Isabelle Agent on miniF2F and NTP4VC-Pearl common success sets, AoA cuts API cost by 2.3--4.7x (normalized input-cache accounting), uses 2.9--6.9x fewer tokens and 3.9--8.9x fewer tool calls, and finishes 1.4--2.0x faster -- while also solving far more problems on the harder verification benchmark.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。