🤖 AI

Efficient Test-Time Optimization for Multi-Agent Proof Autoformalization

The paper introduces ToMap, a multi-agent framework that optimizes test-time compute by identifying the proof decomposition step as the critical bottleneck and iteratively refining it using formal verification and semantic rubrics, thereby achieving significant improvements in full-proof autoformalization accuracy and efficiency on ProofFlowBench.

Original authors: Tian-Shuo Liu, Shiyuan Zhang, Zijie Geng, Haoyu Liu, Runjie Xu, Pengyuan Wang, Lei Yuan, Yang Yu

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tian-Shuo Liu, Shiyuan Zhang, Zijie Geng, Haoyu Liu, Runjie Xu, Pengyuan Wang, Lei Yuan, Yang Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you're trying to teach a brilliant but slightly scattered robot how to write a perfect math proof. You hand it a messy, handwritten note full of clever ideas, logical jumps, and "obvious" steps that a human would get instantly. Your goal? To get that robot to translate your messy note into a strict, computer-checkable language called Lean that never makes a mistake.

This is the challenge of full-proof autoformalization. But here's the catch: the robot isn't just translating words; it's trying to build a skyscraper of logic, one brick at a time. If the first brick is crooked, the whole tower collapses.

The Problem: The "Fix-It-All" Trap

In the past, researchers tried to solve this by letting the robot try, fail, and then try again. If the computer said, "Error! This proof is wrong," the robot would just guess a new way to write the whole thing and try again.

The authors of this paper argue that this is like trying to fix a broken car engine by randomly swapping out the tires, the radio, and the seats, hoping one of them was the problem. It's expensive, slow, and mostly useless. They found that most of the time, the error wasn't in the tires (the final proof) or the radio (the translation); the problem was in the blueprint.

The Discovery: The "Blueprint" is the Bottleneck

The team, led by researchers at Nanjing University, broke the robot's job down into three specialists:

The Decomposer: The architect who breaks the big, messy proof into tiny, manageable steps.
The Formalizer: The translator who turns those steps into computer code.
The Prover: The builder who actually constructs the proof in the computer.

They ran a series of experiments (like a controlled crash test) to see which specialist was the weak link. They found that if the Decomposer (the architect) gave a bad blueprint, the other two specialists couldn't save the day, no matter how hard they tried. Even if you gave the Formalizer and Prover infinite chances to fix their work, they couldn't overcome a bad starting plan.

The main finding: To get the best results, you shouldn't waste time fixing the translator or the builder. You should spend all your energy helping the Decomposer draw a better blueprint.

The Solution: TOMAP (The Smart Architect)

Enter TOMAP, a new system that acts like a super-efficient coach for the Decomposer. Instead of letting the robot guess blindly, TOMAP uses a clever "evolution" loop:

Drafting: The Decomposer creates several different blueprints (decompositions) for the same proof.
The "Rubric" Check: Before the robot even tries to build anything, a smart judge (an AI) looks at the blueprints and scores them on three things:
- Faithfulness: Did you stick to the original proof's ideas?
- Provability: Is this step actually solvable?
- Lean-friendliness: Is the language clear enough for the computer?
The Pareto Frontier: The system keeps the "best of the best" blueprints—those that are strong in all areas—and discards the weak ones.
Evolution: It takes the best blueprint, critiques it, and asks the Decomposer to try again, making tiny improvements.
The Gatekeeper: Only when a blueprint scores perfectly on the "Rubric" does the system let the Formalizer and Prover actually try to build it.

Think of it like a talent show. The "Rubric" is the preliminary audition. You don't let every contestant perform the full song on the main stage (which is expensive and takes time). You only let the ones who passed the audition perform the full song. This saves a massive amount of time and computing power.

The Results: Faster, Smarter, and More Accurate

When they tested TOMAP on a benchmark called PROOFFLOWBENCH (which has 184 math problems) and miniF2F (244 problems), the results were impressive:

TOMAP improved the success rate by 19.0% compared to the best previous method when looking at both the code's correctness and its faithfulness to the original proof.
It did this while using less time and fewer computer resources than the other methods.
Interestingly, the biggest improvements happened very quickly. Most of the gains were made within just a few rounds of "evolution," suggesting you don't need to run the system for hours to get great results.

What They Didn't Do (And What They Didn't Say)

It's important to know what this paper doesn't claim.

It's not a magic wand for bad math: The system assumes the original human proof is correct. If the human proof is wrong or incomplete, TOMAP faithfully translates the mistake. It doesn't fix bad math; it just translates it better.
It's not for research-level giants yet: The tests were done on standard math problems (like high school competitions or undergraduate courses). The authors admit they haven't tested this on massive, cutting-edge research proofs that might take pages to write.
It's not a "training" miracle: Unlike other methods that require training a new, giant AI model from scratch (which costs a fortune), TOMAP is a "test-time" optimization. It works with the models we already have, just by being smarter about how it uses them.

The Bottom Line

This paper suggests that in the world of AI math proofs, quality control at the start is everything. By focusing our limited computing power on refining the initial plan (the decomposition) rather than endlessly retrying the final build, we can build better, more reliable proofs faster. It's a shift from "try harder" to "plan better," and the data shows it works.

Technical Summary: Efficient Test-Time Optimization for Multi-Agent Proof Autoformalization

1. Problem Statement

Full-proof autoformalization aims to translate extensive natural language mathematical proofs into formally validated reasoning within proof assistants like Lean. Unlike statement-level formalization, which focuses on translating a single theorem, full-proof autoformalization is a long-horizon challenge. It requires coordinating claims, contexts, and dependencies across numerous proof steps to construct a globally checkable whole.

Current approaches face two primary limitations:

Costly Training: Many methods rely on large-scale supervised fine-tuning, which is difficult due to the scarcity of proof-level paired supervision data.
Inefficient Test-Time Optimization: Existing inference-time methods often apply excessive, unguided repair or iterative refinement across the entire pipeline. In full-proof settings, verifier feedback (e.g., Lean errors) arrives only after a long generation chain, rarely revealing which upstream decision caused the failure. This makes it challenging to direct limited test-time compute toward targeted improvements rather than unguided retries.

2. Methodology: The TOMAP Framework

The authors introduce TOMAP (Test-time Optimization for Multi-Agent Proof autoformalization), a framework that structures the task as a Decomposer-Formalizer-Prover pipeline. The core innovation is an efficient test-time optimization strategy that identifies and targets the system's critical bottleneck.

2.1 Multi-Agent Pipeline

The system consists of three specialized agents:

Decomposer ( $D$ ): Splits the informal proof into atomic, self-contained sub-propositions (proof units) with explicit dependencies.
Formalizer ( $F$ ): Translates each natural language sub-proposition into a formal Lean statement.
Prover ( $P$ ): Generates tactic scripts to prove each formalized goal.
Verifier ( $V$ ): An external Lean checker that validates the assembled proof file.

2.2 Weak-Link Analysis

Before optimizing, the authors perform a "weak-link analysis" to determine where test-time compute yields the highest return. By intervening on each stage (Decomposer, Formalizer, Prover) individually while holding others fixed, they measure the recoverability of end-to-end verification success.

Finding: The Decomposer is the critical bottleneck. Revising the natural-language proof-unit specification (claims, assumptions, dependencies) yields significantly higher gains in final verification success (51.1% accuracy) compared to revising formal statements (45.1%) or proof scripts (33.7%).
Implication: High-quality, atomic, and self-contained proof units reduce downstream formalization and proving to local tasks within the capabilities of the Formalizer and Prover.

2.3 Test-Time Optimization Strategy

TOMAP focuses all test-time compute on refining the Decomposer, treating the Formalizer and Prover as fixed downstream executors. The optimization follows a GEPA-style (Reflective Prompt Evolution) loop:

Candidate Pool: Maintains a pool of candidate decompositions for a given input.
Rubric Scoring: Instead of immediately calling the expensive Lean verifier, candidates are scored by an LLM-based "Rubric Judge" against three dimensions:
- Semantic Faithfulness: Alignment with the original natural language proof.
- Provability: Whether each unit is self-contained and logically complete.
- Lean Friendliness: Clarity, explicitness of assumptions, and avoidance of ambiguity.
Pareto-Guided Evolution: Candidates are evaluated on a Pareto frontier based on the rubric scores. A reflective LLM proposer selects high-performing candidates, critiques them based on the rubric feedback, and proposes revised decompositions.
Verification Gating: Only candidates that meet a high-quality threshold (passing the rubric gate) are committed to the downstream Formalizer-Prover pipeline for the expensive, ground-truth Lean verification.

This two-level design balances cheap, dense proxy feedback (rubrics) to steer the search with costly, faithful verification reserved only for promising candidates.

3. Key Contributions

Bottleneck Identification: The paper provides empirical evidence via weak-link analysis that proof decomposition quality is the primary determinant of success in full-proof autoformalization, shifting the optimization focus from the entire pipeline to the Decomposer interface.
TOMAP Framework: A novel test-time optimization method that decouples search from verification. It evolves proof decompositions using multi-objective rubric feedback and Pareto selection, significantly reducing the reliance on expensive Lean calls during the search phase.
Efficiency and Performance: The approach achieves state-of-the-art results without requiring large-scale training, relying instead on efficient inference-time optimization.

4. Experimental Results

Experiments were conducted on PROOFFLOWBENCH (184 undergraduate-level problems) and miniF2F (244 high-school level problems).

Performance: TOMAP outperforms both training-based baselines (e.g., ProofBridge) and training-free baselines (e.g., PROOFFLOW, Monotonic).
- On PROOFFLOWBENCH, TOMAP (using Gemini3-Pro) improved the joint Syntactic Correctness and Semantic Faithfulness score by 19.0% over the best previous method.
- On miniF2F, it achieved an 8.2% improvement in the joint metric.
Semantic Faithfulness: TOMAP significantly outperforms monolithic generators in preserving the semantic structure of the original proof, avoiding the tendency of other methods to generate semantically incorrect but syntactically valid Lean code.
Cost Efficiency: While TOMAP requires more test-time compute than naive baselines, it achieves higher success rates with lower total cost compared to methods that rely on extensive iterative retries of the full pipeline.
Scaling Analysis: Ablation studies reveal that most performance gains occur within the first few iterations of decomposition evolution, providing practical guidance for selecting the test-time budget.

5. Significance and Claims

The paper claims that full-proof autoformalization is fundamentally a problem of decomposition quality. By identifying the Decomposer as the most feedback-recoverable stage, the authors demonstrate that efficient test-time optimization can be achieved by focusing resources on refining the natural-language proof structure rather than repeatedly retrying formalization or proving.

The significance of TOMAP lies in its ability to:

Elevate the ceiling of verifiable mathematical reasoning by bridging the gap between informal proofs and formal verification more faithfully.
Provide a scalable, training-free alternative to complex fine-tuning approaches.
Offer a practical framework for allocating limited test-time compute in multi-agent systems by prioritizing the "weak link" identified through causal analysis.

The authors note limitations, including the restriction to benchmark-scale proofs rather than long, research-level mathematics, and the assumption that input informal proofs are correct. They leave the detection and repair of incorrect proof steps as future work.