Expert Iteration for Automated Theorem Proving

This direction is split into other directions: expert iteration. Its last version stays readable and citable here.

Version 1 of 145 papers52 conceptsfrozen 2026-10-04

Large Language Models (LLMs) are notoriously prone to "hallucinations" in mathematical reasoning. While they can mimic the style of a proof, they often skip logical steps or make subtle algebraic errors that invalidate the entire argument. The emerging research direction of Expert Iteration for Automated Theorem Proving addresses this by coupling LLMs with formal verification systems like Lean, Isabelle, or Coq.

By treating the formal verifier as an objective source of truth, researchers are creating self-improving loops where models search for proofs, learn from their successes, and progressively solve more complex problems without requiring new human-annotated data.

The Formal Verifier as a Perfect Teacher

The core challenge in training reasoning models is the "reward signal." In natural language, determining if a proof is "good" is subjective and expensive. However, in formal mathematics, a proof is a piece of code that either compiles or it doesn't.

As Yuhuai Wu and Markus Norman Rabe demonstrated in Autoformalization with Large Language Models, LLMs can be trained to translate natural language math into formal code. Once in this formal domain, the computer becomes the ultimate judge. This creates a "closed-loop" environment similar to games like Chess or Go: the model proposes a move (a proof step), and the environment (the Lean compiler) provides immediate, 100% accurate feedback on whether that move is valid.

Expert Iteration: The Self-Improvement Loop

The dominant mechanism across this research is Expert Iteration (ExIt). This process, popularized in the context of formal math by Jesse Michael Han and Stanislas Polu in Formal Mathematics Statement Curriculum Learning, follows a simple but powerful cycle:

  1. Search: The current model attempts to solve a set of formal problems using search algorithms (like Monte Carlo Tree Search).
  2. Verify: The formal system filters out all failed attempts, keeping only the verified, correct proofs.
  3. Train: The model is fine-tuned on these successful proofs, effectively "distilling" the results of its intensive search back into its own weights.
  4. Repeat: The improved model is now better at searching, allowing it to find proofs for even harder problems in the next round.

This loop allows a model to bootstrap its own intelligence. For example, LIN Yong and Bohan Lyu used eight rounds of this iteration to develop Goedel-Prover, which achieved state-of-the-art results on the PutnamBench leaderboard by learning from 1.64 million autoformalized problems.

Search as a Policy Improvement Operator

Why does search help the model learn? In reinforcement learning terms, search acts as a policy improvement operator.

A base model might have only a 1% chance of guessing a complex proof in a single try. However, if you allow that model to explore thousands of paths using a tree search, it might find the correct proof once. As Xidong Feng and Ziyu Wan explain in TS-LLM, training on that one successful "lucky" path teaches the model the underlying logic, making it more likely to generate that correct path intuitively (without search) in the future.

This synergy between "thinking slow" (search) and "thinking fast" (the model's raw output) is the roadmap for modern reasoners. Zhiyuan Zeng and colleagues argue in Scaling of Search and Learning that this is the fundamental recipe behind models like OpenAI's o1: using test-time compute (search) to generate the very data needed to scale train-time compute (learning).

Beyond Correctness: Optimizing for Elegance

Recent work has moved beyond just finding any proof to finding the best proof. In Learning Better Representations From Less Data For Propositional Satisfiability, Mohamed Ghanem and Bernd Finkbeiner show that a model can actually surpass its "teacher." If the model's search discovers a proof that is shorter or more efficient than the one provided in the initial training set, it can replace the teacher's example with its own.

Similarly, frameworks like Lean-STaR by Haohan Lin and Sean Welleck train models to interleave formal code with natural language "thoughts." This doesn't just help the model find the proof; it helps the model internalize the rationale behind the proof, leading to better generalization on unseen mathematical concepts.

Summary of the Frontier

The shift from static datasets to iterative, search-based self-improvement represents a paradigm shift in AI reasoning. By leveraging formal systems as a source of infinite, verifiable "ground truth," researchers are moving away from the limitations of human data. As Zijian Wu demonstrates with InternLM2.5-StepProver, when you combine massive-scale expert iteration with critic-guided search, the model stops being a mere predictor of text and starts becoming a genuine mathematical engine.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_expert_iteration_for_automated_theorem_p_0c8a034d,
  title = {Expert Iteration for Automated Theorem Proving},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expert-iteration-for-automated-theorem-proving/rdr_0c8a034db7904bfa8c0770d9f3d74101},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_expert_iteration_for_automated_theorem_p_0c8a034d_v1,
  title = {Expert Iteration for Automated Theorem Proving},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expert-iteration-for-automated-theorem-proving/rdr_0c8a034db7904bfa8c0770d9f3d74101/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}