🤖 AI

Self-Modifying Lean Proof Agents with Verifier-Grounded Benchmark Coevolution

This paper introduces a self-modifying Lean proof agent that coevolves with a mastery-throttled benchmark to achieve a 45.1% solve rate on held-out tests, significantly outperforming both its seed and fixed-benchmark counterparts by ensuring all self-improvements remain grounded in trusted Lean verification.

Original authors: Yuqing Li, Zeguan Wu, Yu Gan, Junyu Liu

Published 2026-07-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuqing Li, Zeguan Wu, Yu Gan, Junyu Liu

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 a world where computers don't just follow orders but can actually learn to fix their own mistakes, rewrite their own instructions, and get smarter over time. This is the realm of "self-evolving agents," a branch of artificial intelligence where software tries to improve itself by changing its own code. Usually, these digital creatures are tested on a fixed set of puzzles, like a student taking the same math test over and over until they memorize the answers. But what if the test itself could get harder every time the student got better? That's the idea of "coevolution," where the learner and the challenge grow together, pushing each other to new heights. In the specific corner of math known as formal verification, there's a strict referee called "Lean" that checks if a proof is 100% correct. The big question researchers have been asking is: Can a computer agent figure out the best way to solve these math proofs on its own, without a human teacher designing the strategy for it?

This paper tells the story of a team of researchers who built a digital "proof agent" that tries to answer that question. Instead of giving the agent a perfect, hand-written guide on how to solve math problems, they let the agent rewrite its own workflow, tools, and even how it organizes its thoughts. To keep things fair and honest, they paired this self-improving agent with a "coevolving benchmark." Think of it like a video game that automatically adjusts its difficulty: as soon as the agent masters a level, the game swaps those easy levels for harder ones, ensuring the agent never gets bored or stuck. The researchers found that this approach worked surprisingly well. By the end of 15 generations of evolution, their self-taught agent could solve 45.1% of a set of tough, unseen math problems, a huge jump from the 12.7% it could solve at the start. However, the paper also suggests that while this agent got much better, it didn't become a perfect genius; it mostly learned to be very good at fixing its own errors rather than inventing entirely new, complex ways to break down problems.

The Story of the Self-Editing Math Bot

Imagine you have a robot that wants to solve a giant stack of math proofs. Usually, a human programmer would write a strict manual for the robot: "First, do this. Then, if you see an error, do that." But in this experiment, the researchers decided to let the robot write its own manual. They created a system where the robot's "brain" (its code, its tools, and its strategy) was fully editable. The robot could try to rewrite its own instructions to see if it could solve problems faster or more accurately.

But there was a catch. If the robot could rewrite its own code, it could also lie and say, "I solved it!" when it actually didn't. To stop this, the researchers built a "trusted runtime"—a strict, unchangeable referee that never sleeps. This referee, powered by a system called Lean, acts as the ultimate judge. No matter how the robot changes its own code, the referee checks the final proof. If the proof doesn't hold up under the referee's microscope, it doesn't count. This ensures that the robot can't cheat; it has to actually do the math to get a point.

The Game That Gets Harder

The most exciting part of this experiment is how they tested the robot. In most AI experiments, the robot practices on a fixed list of problems. If the robot gets too good, it just memorizes the answers, and the test stops being useful. The researchers in this paper wanted to avoid that. They set up a "coevolving benchmark," which is like a video game that gets harder every time you beat a level.

Here's how it worked:

The Champion: In every round, the best-performing robot (the "champion") gets to decide what the next round looks like.
The Upgrade: If the champion solves too many easy problems, the system retires those easy problems and replaces them with harder ones from a bigger pool of challenges.
The Scorekeeper: To make sure the scores stay fair as the game gets harder, they used a special math trick called "single-anchor recalibration." Imagine if you ran a race on a track that suddenly got steeper; you'd run slower, but you'd still be a great runner. This system adjusted the scores so that getting a "gold medal" on a hard track was worth the same as getting one on an easy track.

This setup meant the robot was always being pushed just beyond its comfort zone, forcing it to learn new tricks rather than just memorizing the old ones.

What the Robot Actually Learned

After running this experiment for 15 generations, the results were fascinating. The robot started out solving only about 12.7% of the problems. By the 15th generation, the best version of the robot could solve 45.1% of the problems on a brand-new, unseen test. That's a massive improvement, showing that letting the robot rewrite itself really did help it get smarter.

However, the researchers discovered something interesting about how the robot got smarter. They expected the robot to eventually figure out a complex, step-by-step strategy where it breaks a big problem into tiny, manageable pieces (like a master architect designing a building floor by floor). Instead, the winning robots mostly became experts at repair.

Think of it like this: The robot learned to write a whole proof quickly, then check it for errors, and then fix the specific parts that broke. It didn't necessarily plan the whole building from scratch; it just got really good at patching the cracks. The researchers found that while the robot tried to build complex, step-by-step plans, these plans often fell apart or were too risky. The simpler strategy of "try, check, fix" was more reliable and won the competition.

The robot also invented some clever tools to help itself. For example, it learned to double-check the names of math terms it used to make sure it wasn't making up fake words (a common mistake called "hallucination"). It built little checklists and search tools to ensure every part of its proof was real and valid before it submitted it.

The Verdict

So, did the robot become a math genius? Not quite. While it improved dramatically, it still couldn't solve 99% of the problems like the best human-designed robots can. The researchers suggest that the robot is still stuck in a "repair mode" rather than a "planning mode." It's great at fixing mistakes, but it hasn't quite figured out how to build a perfect, deep structure from the ground up.

This experiment shows that self-evolving agents can learn to use their tools better and get much smarter when the challenges keep growing with them. But it also suggests that there's a limit to how much a robot can teach itself without a human guiding it toward more complex strategies. The robot proved that it could evolve, but the journey to becoming a true mathematical master is still a work in progress.

Technical Summary: Self-Modifying Lean Proof Agents with Verifier-Grounded Benchmark Coevolution

Problem Statement

Designing effective agentic frameworks for Lean-based theorem proving faces a dual challenge: improving the prover's raw synthesis capability and optimizing the surrounding proof workflow. While recent work has focused on building stronger specialized models or tactics, a complementary perspective argues that the bottleneck lies in the agent's interaction with the Lean environment—specifically, how it decomposes obligations, utilizes compiler feedback, diagnoses failures, and maintains structured proof context.

Current self-evolving agent systems (e.g., Darwin Gödel Machine, Hyperagents) typically optimize agents against fixed, externally supplied benchmarks. This approach is ill-suited for formal mathematics because:

Selection Signal: If the benchmark is too hard (e.g., competition-level problems), most evaluations fail, providing no gradient for evolution. If too easy, the agent quickly saturates.
Workflow Rigidity: Most agents rely on hand-designed workflows. The question remains whether an agent can evolve its own proof workflow, tools, and context representation without human intervention.
Grounding: A self-rewriting agent cannot be trusted to report its own success; a fixed, trusted verifier is required to arbitrate correctness.

Methodology

The authors propose a system where a self-evolving Lean proof agent coevolves with a self-hardening benchmark, all grounded by a fixed, trusted Lean verifier.

1. System Architecture

Trusted Runtime vs. Mutable Workspace: The system separates a fixed, trusted runtime (handling Lean verification, evaluation, and benchmark management) from a fully mutable workspace. The agent can rewrite its own proof workflow, prompts, and tools within this workspace.
Code Validity vs. Proof Success: Mutated agents undergo a code-level "smoke test" to ensure they run, but a theorem is only marked "solved" if the generated proof re-verifies under a trusted Lean snapshot.
Verifier-Grounded Contract: Every solve attempt must emit a machine-readable proof context. While the representation of this context (graph, tree, table) is free to evolve, its groundedness is enforced. The runtime sanitizes certificates, rejects sorry/admit, and independently re-verifies claims.

2. Coevolving Benchmark Mechanism

Instead of a fixed benchmark, the system employs a champion-driven, mastery-throttled curriculum:

Task Pool: Problems are stratified into three difficulty levels (L1: single-tactic lemmas; L2: miniF2F; L3: PutnamBench).
Update Rule: At the end of each generation, if the "champion" (highest-scoring agent) exceeds a solve threshold ( $\gamma=0.30$ $γ = 0.30$ ), the benchmark updates.
- Tasks solved by all agents are retired.
- If the champion's mastery on a specific level exceeds a threshold ( $\tau=0.70$ ), retired tasks are replaced by harder tasks from the next level; otherwise, they are replaced laterally with new tasks of the same difficulty.
- The update prefers domains where the agent population has accumulated failures.
Single-Anchor Recalibration: To maintain score comparability as difficulty increases, the champion is re-evaluated on the new benchmark. A difficulty coefficient ( $c$ ) is updated multiplicatively to normalize scores across generations ( $q = r \times c$ ).

3. Evolution Interface

Parent Selection: Agents are selected from an archive based on a difficulty-normalized score, discounted by the number of children they have already produced to prevent lineage dominance.
Self-Modification: Agents rewrite their own code, including workflow logic (e.g., repair loops, decomposition strategies) and tooling (e.g., lemma checkers).

Key Contributions

Self-Evolving Lean Proof Agent: The authors present a code-level self-evolving agent where the proof workflow and tools are mutable, yet proof success remains strictly grounded in Lean verification.
Benchmark Coevolution: They introduce a champion-driven, self-hardening benchmark that evolves alongside the agent. This avoids the saturation of fixed easy benchmarks and the sparsity of fixed hard benchmarks, using mastery-throttled updates and single-anchor recalibration.
Representation-Free, Grounded Proof Contexts: The system enforces a contract where agents can evolve the format of their proof context (e.g., from flat logs to structured graphs), but the validity of solved claims is strictly enforced by the trusted runtime.

Experimental Results

The system was evaluated over 15 active generations, comparing the coevolving trajectory against a fixed-benchmark baseline.

Performance on Held-Out Test:
- Seed Agent: 12.7% solve rate on the held-out miniF2F test split.
- Fixed-Benchmark Baseline: The best agent reached 32.0%.
- Coevolving Agent: The best agent (c144, Generation 15) reached 45.1% on the held-out test.
Benchmark Hardening: The difficulty coefficient rose from 1.00 to 3.17 over 15 generations, indicating the benchmark successfully increased in complexity as the agent improved.
Workflow Evolution:
- Repair-Centered Dominance: The winning workflow remained primarily "repair-centered" (generate proof $\to$ check Lean errors $\to$ repair) rather than "decomposition-centered" (plan subgoals $\to$ prove $\to$ assemble).
- Tool Evolution: Agents successfully evolved tools to prevent hallucinated Lean names (e.g., #check probes, source search, verified lemma caches).
- Decomposition Attempts: Several agents attempted decomposition-based workflows (e.g., c26, c44, c141). While these agents evolved genuine node-level verification for self-contained sub-lemmas, these strategies were often pruned by selection because the assembly step introduced new failure points (JSON parsing, context mismatches) that reduced the final solve rate compared to compact repair loops.
Proof Context: Proof contexts became inspectable but rarely evolved into deep, verified dependency graphs. Agents tended to construct context backward from the final proof rather than planning a graph in advance.

Significance and Claims

The paper claims that verifier-grounded self-evolution can improve Lean proof workflows under a coevolving benchmark.

Feasibility of Self-Improvement: The results demonstrate that an agent can improve its mathematical workflow and tooling solely by rewriting its own code, provided a fixed, trusted verifier arbitrates success.
Importance of Coevolution: The ablation study shows that a fixed benchmark leads to evolutionary stagnation once the agent masters a subset of tasks. The coevolving benchmark maintains an informative selection signal by continuously raising the difficulty.
Limitations and Future Direction: The authors are modest about the current state. The winning workflow is still repair-centered, and the system has not yet evolved a deep, durable proof-context graph (DAG) that rivals hand-designed agents like Goedel-Architect (which reaches 99.2% on miniF2F-test). The authors suggest that longer runs, larger populations, or rewards specifically targeting verified decomposition may be necessary to evolve more complex, decomposition-first workflows.

The work establishes a foundation for agents that can adapt their own reasoning structures in formal domains, keeping the verification logic fixed while allowing the "how" of proof construction to evolve.