LEAP: LLM-in-Lean Environment Agentic Prover
> Paper: LEAP: LLM-in-Lean Environment Agentic Prover > Authors: Po-Nien Kung, Linfeng Dawsen Hwang, et al. (Google DeepMind) > Link: https://arxiv.org/abs/2606.03303 > Resources: Open-source framework, built on a general LLM (Gemini 3.1 Pro)
The "Last Mile" Problem of Formal Mathematics
Formal mathematics — writing machine-verifiable proofs in strict languages like Lean, Isabelle, or Coq — is a holy grail of mathematical reasoning. Yet the barrier is enormous: even top mathematicians may need years to formalize complex proofs. Georges Gonthier's team spent 10 years formalizing the Kepler conjecture.
LLMs promised help, but when asked to directly output Lean code, even frontier models like Gemini and GPT achieve a success rate near zero. Why? Formal proof is not a translation problem but a structured engineering problem: decomposing arguments into lemmas, understanding Lean's type system and tactic library, iterating on compiler feedback, and maintaining global consistency across hundreds of lines.
The conventional solution is specialized fine-tuning (AlphaProof, DeepSeek Prover V2, etc.) — expensive and limiting generalization. LEAP asks a radical question: what if, instead of fine-tuning, we give a general LLM a good enough scaffold?
Core Insight: The Bottleneck Is Structure, Not Language
> General LLMs fail not because they don't understand math or Lean, but because producing long, complex, correct proofs in a single pass exceeds any model's single-hop capability.
Failure-mode observations show general LLMs *can* write correct informal proofs, understand Lean compiler errors, and revise code from feedback — but cannot emit 2,000 error-free lines in one shot. LEAP's strategy: let the LLM build proofs step by step in a structured agent environment, much like how human mathematicians work.
Framework Architecture
LEAP is an agent framework, not a single model, organized as a plan–execute–verify loop:
1. State Reader — retrieves the theorem statement, existing lemmas, and context 2. NL Prover — generates natural-language proof sketches or decomposition blueprints 3. Formal Prover — translates informal content into Lean code 4. Verifier — checks syntax, types, and logic via the Lean compiler; on failure, a Reviser rewrites from error messages 5. Reviewer — an LLM evaluating decomposition quality, filtering dead-end subgoals 6. State Writer — commits new lemmas/decompositions to the DAG and checks acyclicity
#### Innovation 1: AND-OR DAG Hierarchical Memoization
- OR nodes: open goals (theorems/lemmas to prove) — solvable by any valid proof strategy
- AND nodes: candidate decompositions — succeed iff all subgoals are proven
- Lemma memoization: proven lemmas become shared nodes, reusable by any branch
- Anticipatory lemma planning: high-level nodes can propose auxiliary lemmas useful downstream
- Monotonic refinement: once a goal is decomposed, search only expands descendants
- Hard verification (Lean compiler): syntax/type correctness;
sorryallowed only for newly proposed subgoals - Soft heuristics (LLM reviewer): evaluates whether subgoals are actually simpler and relevant; filters useless decompositions and triggers backtracking
- Donald Knuth's Hamilton decomposition problem: whether edges of a directed Cayley graph can be partitioned into three Hamilton cycles. LEAP autonomously decomposed a 20-page informal proof involving 3D routing dynamics and synthesized over 5,000 lines of verified Lean code.
- Erdős problem 457: autonomously derived the known proof from first principles, no human intervention.
- Geometry: all methods near 0% on Lean-IMO-Bench geometry; domain frameworks (e.g., GeoCoq) may be needed
- Compute cost: hard problems need many LLM calls (Putnam A5: 3,000)
- Search efficiency: currently simple DFS; LLM-based heuristic pruning / MCTS / A* is unexploited
- Hybrid architectures: combining general-LLM structural reasoning with specialized provers for local step generation may be optimal
- Kung, P. N., Song, L., Hwang, D., et al. (2026). *LEAP: LLM-in-Lean Environment Agentic Prover*. arXiv:2606.03303.
- Compared methods: AlphaProof, DeepSeek Prover V2, Goedel Prover V2, Hilbert, Aristotle
Unlike tree-based recursive search (e.g., Hilbert), the DAG provides:
Ablation: replacing the DAG with a naive tree drops the Lean-IMO-Bench Advanced solve rate from 56.7% to 40.0%.
#### Innovation 2: Interleaved Informal–Formal Planning
All proof attempts pass through a natural-language stage first:
| Path | Flow |
|------|------|
| Direct proof | informal argument → Lean code → compiler verification |
| Decomposition | informal blueprint (intermediate lemmas) → Lean sketch (sorry placeholders allowed) → structural verification |
Benefits: leverages LLM strength in informal reasoning, provides per-step interpretability, isolates errors earlier, and enables gradual formalization.
#### Innovation 3: Verification-Guided Proof Search
On Putnam 2025 problem A5, full LEAP (with the reviewer) succeeded in 2 rollouts; without the reviewer, 8 rollouts still failed. The reviewer catches decompositions that are formally acceptable but mathematically vacuous (e.g., subgoals identical to ancestor goals).
Experimental Results
#### Putnam 2025: A Clean Sweep, 12/12
| Method | Type | Solved | Rate | |--------|------|--------|------| | Gemini-3.1-pro (Pass@128) | general LLM direct formalization | 0/12 | 0% | | Goedel-Prover-V2-32B (Pass@128) | specialized prover | 0/12 | 0% | | Hilbert (open-source framework) | hybrid system | 4/12 | 33.3% | | Aristotle (proprietary, IMO-gold level) | proprietary system | 9/12 | 75.0% | | LEAP | general LLM + agent | 12/12 | 100% |
Efficiency: the easiest problem (b2) took 46 LLM calls and a 300-line proof; the hardest (a5) took 3,000 LLM calls, a 2,000-line proof, and 170 active DAG nodes.
#### Lean-IMO-Bench: From <10% to 70%
A new benchmark of 60 IMO-style problems (30 basic / 30 advanced) with short statements but high unconventionality:
| Method | Basic (%) | Advanced (%) | |--------|-----------|--------------| | Gemini-3.1-Pro (Pass@128) | 20.0 | 3.3 | | Goedel-V2-32B (Pass@128) | 10.0 | 0 | | Hilbert | 36.6 | 6.6 | | Aristotle | 76.7 | 20.0 | | LEAP | 83.3 | 56.7 |
By domain: algebra and number theory reach 100% (both levels); combinatorics 100%/25%; geometry stays near 0% for all methods — formalizing olympiad geometry in Lean still needs domain-specific frameworks.
Key finding: direct one-shot formalization by general LLMs is under 10%; LEAP lifts it to 70%. The gap lies in architecture, not model capability.
#### Research-Level Applications
Comparison with Existing Approaches
Specialized provers (AlphaProof, DeepSeek Prover V2) vs. LEAP: specialized models need heavy compute and generalize poorly; notably Goedel-Prover-V2-32B performs *worse* in iterative formalization (10.0% → 6.6%), lacking the ability to interpret errors, maintain context, and multi-step revise — strengths of general LLMs.
Hybrid systems (Hilbert) vs. LEAP: Hilbert's tree search suffers exponential redundancy O((n·b)^d); LEAP's DAG with lemma memoization achieves polynomial sharing — 4/12 vs. 12/12 on Putnam, 36.6% vs. 83.3% on Lean-IMO-Bench basic.
Aristotle vs. LEAP: the closed-source IMO-gold-level system trails LEAP across all metrics (75% vs. 100% Putnam; 20.0% vs. 56.7% Lean-IMO advanced), and unlike Aristotle, LEAP is open and reproducible.
Design Philosophy: Scaffolding Beats Fine-Tuning
> For tasks requiring deep reasoning and strict verification, a carefully designed agent scaffold may be more effective than expensive specialized fine-tuning.
Key principles: 1. Decomposition over end-to-end: break complex problems into manageable subgoals 2. Verification-guided search: hard verification (compiler) ensures correctness; soft heuristics (LLM reviewer) steer direction 3. Memoization avoids duplication: proven lemmas are reused, not rediscovered 4. Human-collaboration interface: natural-language blueprints make proofs inspectable and intervenable
Limitations and Future Directions
Conclusion
LEAP's significance goes beyond competition scores. It demonstrates that (1) general LLMs' potential is underestimated — with proper structural scaffolding they can perform rigorous, verifiable reasoning; (2) agent architecture can compensate for single-shot generation limits; and (3) an open, reproducible approach can surpass closed proprietary systems. As the paper states:
> "Modern general LLMs, when equipped with appropriate structural scaffolds, have substantial reasoning capabilities for rigorous domain-specific tasks."
The paradigm — don't rush to specialize; try better scaffolding first — extends to program verification, hardware design, and protocol analysis.