🤖 machine learning

Understanding Tool-Augmented Agents for Lean Formalization: A Factorial Analysis

This paper investigates the effectiveness of tool-augmented agents in translating natural language mathematics into Lean 4 code by conducting a systematic factorial analysis of three tool categories—fine-tuned model querying, knowledge search, and compiler feedback—to demonstrate their significant improvement over one-shot baselines and quantify their individual contributions to compilation success and semantic fidelity.

Original authors: Ke Zhang, Patricio Gallardo, Maziar Raissi, Sudhir Murthy

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ke Zhang, Patricio Gallardo, Maziar Raissi, Sudhir Murthy

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 are trying to translate a beautiful, complex poem written in a human language (like English) into a strict, robotic language that a super-precise computer can understand (called Lean 4).

The problem is that human math is often fuzzy and intuitive, while computer math is rigid and unforgiving. If you just ask a smart AI (a Large Language Model) to do the translation in one go, it often gets it wrong. It might invent words that don't exist in the computer's dictionary or write sentences that look right but mean the wrong thing.

This paper is about building a smart team of AI assistants to fix this problem, rather than relying on a single AI to do everything alone.

The Problem: The "Hallucinating" Translator

Think of a standard AI translator like a student taking a test without a textbook or a calculator.

The Mistake: The student tries to guess the answer. Sometimes they get lucky, but often they "hallucinate"—they make up a theorem or a symbol that doesn't actually exist in the computer's library.
The Result: The computer rejects the code immediately, or worse, accepts code that compiles but says something nonsensical.

The Solution: The "Tool-Augmented" Agent

The authors built an AI agent that doesn't just guess. Instead, it acts like a team of experts working together in a loop. They tested three specific "tools" to see which ones actually helped:

The Expert Draftsman (Fine-tuned Model): A specialist who knows a lot about math and can write a first draft.
The Dictionary (Knowledge Search): A tool that lets the agent look up exactly what a specific symbol or word means in the computer's library.
The Strict Editor (Compiler Feedback): A tool that runs the code immediately. If there's an error, it gives a specific "red ink" note saying exactly what's wrong, so the agent can fix it.

The Experiment: The "Factorial" Test

The researchers didn't just guess which tool was best. They ran a massive experiment (like a scientific cooking show) where they tested every possible combination of these tools on 400 different math problems.

No tools? (Just the AI guessing).
Just the Dictionary?
Just the Editor?
All three together?

The Big Discoveries (The "Aha!" Moments)

1. The "Strict Editor" is the MVP (Most Valuable Player)
The most surprising finding was that the Compiler Feedback (the Strict Editor) was the single most important tool.

Analogy: Imagine trying to learn to ride a bike. If you just guess how to pedal, you'll fall a lot. But if you have a coach standing right next to you saying, "You're leaning too far left, fix it now," you learn incredibly fast.
Result: Without this "coach," the AI failed most of the time. With it, success rates jumped from about 26% to 89%. The ability to try, fail, get a specific error message, and try again was the magic ingredient.

2. The "Dictionary" is a Great Helper
Looking up definitions (Knowledge Search) helped a bit. It stopped the AI from making up fake words.

Analogy: It's like having a dictionary open while you write. It prevents you from using a made-up word, but it doesn't write the sentence for you.
Result: It made the AI more stable and reduced errors, but it wasn't the main reason for the huge success.

3. The "Expert Draftsman" was Surprisingly Useless
The specialized math model (the Expert) didn't help much once the other two tools were present.

Analogy: If you have a genius architect (the Expert) who draws a blueprint, but you also have a strict building inspector (the Editor) who tears it down if it's wrong, the architect's initial draft matters less. The process of fixing the errors is what matters.
Result: The general AI, when allowed to fix its own mistakes with the Editor, didn't need a specialized "expert" to start with.

The Efficiency Lesson

The researchers also found that the AI didn't need to try forever.

The Sweet Spot: Most problems were solved within about 14 attempts. After that, the AI was just spinning its wheels.
The Trade-off: Using the "Dictionary" tool helped the AI solve problems faster because it didn't have to guess as much before asking the "Editor" for help.

The Takeaway

This paper teaches us that for complex tasks like formal math:

Don't just rely on the AI's memory. Even the smartest AI will make up facts if it can't check them.
Verification is King. The ability to run code, see the error, and fix it is far more powerful than having a model that is "trained" on math.
Iterate, Don't Just Generate. The future of AI in math isn't about one perfect answer; it's about a smart loop of Draft → Check → Fix → Repeat.

In short: To translate human math into computer math, you don't need a genius who never makes mistakes. You need a smart worker who knows how to use a dictionary and, most importantly, knows how to listen when the computer says, "That's wrong, try again."

1. Problem Statement

The paper addresses the "formalization bottleneck": the difficulty of automatically translating informal natural language mathematics into strict, machine-checkable Lean 4 code.

The Core Conflict: Large Language Models (LLMs) operate probabilistically, while formal mathematics requires absolute logical certainty.
Key Challenges:
- Hallucination: LLMs frequently invent non-existent theorems or library definitions (e.g., in Mathlib 4), leading to code that fails to compile.
- Semantic Dissonance: There is a fundamental gap between set-theoretic intuition (textbooks) and dependent type theory (Lean).
- Static Limitations: One-shot prompting or fine-tuning on static datasets fails because Mathlib is rapidly evolving; models trained on snapshots generate code targeting deprecated definitions.
- Syntactic vs. Semantic Validity: Code may compile (syntactically valid) but express vacuous or incorrect mathematical statements.

2. Methodology

The authors propose an Agentic Framework that replaces static generation with an iterative "draft-verify-repair" loop.

A. Agent Architecture

Orchestrator: A central LLM (GPT-5.2) maintains a persistent state and interacts with a Lean 4 execution environment via an API.
Toolset: The agent is equipped with three distinct tool categories:
1. Knowledge Search (S): Symbol retrieval tools (e.g., lean inspect name) to query Mathlib for real types and definitions, preventing hallucinations.
2. Expert Drafting (T): Access to a fine-tuned model ("Herald") to provide specialized starting translations.
3. Compiler Feedback (F): A Lean REPL interface to execute code, providing precise error messages for iterative debugging.
Execution Loop: The agent generates a draft, calls tools to verify or refine, and iterates until the code compiles or a step budget ( $T_{max}$ ) is reached.

B. Experimental Design: Factorial Analysis

To move beyond "black box" performance metrics, the authors employ a full $2^3$ factorial design on a new benchmark of 400 graduate-level theorems (covering Real Analysis, Complex Analysis, Topology, and Algebra).

Variables: The presence (1) or absence (0) of each tool (T, F, S).
Goal: Quantify the marginal contribution and interaction effects of each tool, isolating which components drive capability versus efficiency.
Evaluation Protocol:
1. Compiler Verification: Code must compile with Mathlib.
2. Semantic Equivalence: An LLM-as-a-Judge (GPT-5.2) scores faithfulness (0–10). A translation is "Faithful" if it compiles and scores $\ge 9$ .
3. Robustness: Validated via cross-judge agreement (GPT-5.2 vs. Gemini-2.5-Pro) and human expert review.

3. Key Contributions

Systematic Factorial Decomposition: The first study to rigorously quantify the causal impact of specific tools (Retrieval, Drafting, Feedback) in mathematical formalization, moving beyond simple "agent vs. baseline" comparisons.
Identification of the "Capability Bottleneck": The study isolates Compiler Feedback as the primary driver of success, distinguishing it from tools that merely stabilize or accelerate convergence.
Discovery of Negative Interactions: The analysis reveals that certain tool combinations (e.g., Expert Drafting + Compiler Feedback) can be counterproductive, suggesting that specialized drafts can sometimes anchor the model away from optimal solutions when iterative repair is available.
Open Benchmark & Framework: The authors release a 400-theorem benchmark, agent implementation, and interaction logs to support reproducibility and future RL research.

4. Key Results

A. Performance Gains

Baselines: One-shot models (GPT-5.2, Herald) achieve low compilation rates (~~26%) and low faithfulness (~~10–28%).
Full Agent: The tool-augmented agent (all tools enabled) achieves:
- 89.5% Compilation Success.
- 60.5% Faithfulness (vs. 28.0% for the best one-shot baseline).

B. Factorial Main Effects (Quantified Impact)

Using a $2^3$ design, the authors calculated the average marginal gain of each tool:

Compiler Feedback (F): +32.3 points.
- Dominant Driver: This is the "capability bottleneck." Enabling the REPL transforms the system from a low-success regime to a high-success regime. It enables iterative repair, which is essential for semantic fidelity.
Symbol Search (S): +6.8 points.
- Stabilizer: Reduces hallucinations and improves name resolution. It provides a consistent boost but does not create a new performance regime on its own.
Expert Drafting (T): +0.9 points.
- Substitutable: The fine-tuned Herald model offers negligible improvement over a strong generalist LLM (GPT-5.2) when feedback and search are present.

C. Interaction Effects

Feedback $\times$ Search: Negative interaction (-11.1 pts). When Compiler Feedback is active, Search provides diminishing returns (+1.2 pts) because the REPL already provides global diagnostics. Search is most valuable when Feedback is absent (+12.4 pts).
Feedback $\times$ Drafting: Negative interaction (-5.9 pts). Expert drafting actually hurts performance (-2.0 pts) when Compiler Feedback is enabled, likely due to "anchoring" the agent to a suboptimal initial draft that the repair loop struggles to correct.

D. Efficiency and Behavior

Step Budget: The agent converges rapidly; ~50% of problems are solved by step 8, with practical saturation around step 14.
Tool Substitution: Adding Search reduces the number of expensive REPL calls by ~30%, shifting the agent's strategy from "compile-and-repair" to "targeted symbol lookup."
Domain Variance: Complex Analysis is the easiest domain (fewest steps), while Real Analysis is the most difficult.

5. Significance and Implications

Design Principle for Formal Agents: The paper establishes that execution environments (compiler feedback) are the primary scaffold for LLM reasoning in formal tasks, while retrieval serves to stabilize and accelerate convergence.
Critique of Static Fine-Tuning: For rapidly evolving libraries like Mathlib, relying solely on static fine-tuning (Expert Drafting) is brittle. Verification-coupled iteration is more critical than parametric specialization.
Future Directions: The interaction logs generated by the agent provide a rich dataset for training Reinforcement Learning (RL) agents to internalize repair dynamics, potentially reducing the need for live REPL calls in future models.

In conclusion, the paper demonstrates that successful automated formalization relies less on the "intelligence" of a single draft and more on a closed loop of execution, verification, and iterative correction.