Expert Iteration for Formal Theorem Proving

25 concepts18 papers1 proposal

When large language models (LLMs) attempt complex multi-step reasoning in natural language, they often suffer from compounding errors. A single logical misstep early in a derivation can derail the entire solution. Because natural language lacks an objective, automated judge, models cannot easily verify their own correctness during training, leading to semantic drift and reinforced hallucinations.

Formal theorem proving solves this fundamental bottleneck by replacing vague natural language with machine-verifiable code (written in languages like Lean, Isabelle, Coq, or HOL Light). In this domain, a research direction known as expert iteration has emerged. By pairing a generative model with an automated verification kernel, systems can autonomously explore problem spaces, filter out logical errors, and continuously retrain on their own verified successes.

The Core Feedback Loop

Expert iteration operates as a self-reinforcing loop between two distinct phases: exploration and learning.

   ┌────────────────────────────────────────┐
   │                                        │
   ▼                                        │
[Exploration Phase]                         │
Model generates candidate proof paths       │ [Learning Phase]
   │                                        │ Model fine-tunes on
   ▼                                        │ verified successes
[Verification Filter]                       │
Formal kernel validates steps ──────────────┘

As Amitayush Thakur notes in ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving, static training datasets inherently limit a model's ultimate reasoning capacity. Expert iteration breaks this limitation by transforming the model into a data generator.

  1. Exploration: The model is presented with a set of mathematical conjectures. It generates multiple candidate proof trajectories using sampling strategies or search heuristics.
  2. Verification: Instead of relying on a noisy neural evaluator, the candidate proofs are passed directly to a formal symbolic kernel. The kernel acts as an infallible judge, verifying whether the sequence of logical steps successfully reaches the target terminal state.
  3. Learning: Trajectories that fail verification are discarded or mined for negative feedback. Trajectories that successfully pass verification are added back into the training pool. The model is then fine-tuned on this high-quality, self-generated data.

As Xueliang Zhao et al. demonstrate in SubgoalXL: Subgoal-based Expert Learning for Theorem Proving, this filtering process allows the system to approximate an optimal distribution of high-quality reasoning steps. Similarly, Jing Xiong et al. utilize this mechanism in TRIGO: Benchmarking Formal Mathematical Proof Reduction for Generative Language Models to force models to prioritize actions that lead strictly to valid terminal states within a formal system.

Why It Works: Overcoming Data Scarcity and Surpassing the Teacher

In traditional imitation learning, a model is trained to mimic human-authored proofs. However, human proof logs are scarce, expensive to produce, and often omit intermediate algebraic steps that humans find intuitive but models struggle to bridge.

Expert iteration circumvents this by allowing the model to discover novel reasoning paths that do not exist in the training data. In HOList: An Environment for Machine Learning of Higher Order Logic Theorem Proving, Kshitij Bansal et al. showed that combining supervised imitation with a reinforcement learning loop of self-discovered proofs significantly outperforms pure imitation. By attempting proofs independently, the model develops a form of mathematical intuition that generalizes beyond human demonstrations.

Crucially, this loop allows a neural model to eventually surpass its initial teacher. In Learning Better Representations From Less Data For Propositional Satisfiability, Mohamed Ghanem et al. designed a system where a model initially learns from a symbolic teacher. However, during the expert iteration loop, if the model discovers a proof that is shorter or more efficient than the teacher's solution, the system replaces the teacher's example with the model's own discovery. This bootstrapping process optimizes logical derivations beyond the quality of the original training set.

Generating a flawless formal proof from scratch is highly improbable due to the combinatorial explosion of possible mathematical steps. To make expert iteration practical, researchers use structured search algorithms to guide the exploration phase.

Policy and Value Networks

A common paradigm couples the language model with Monte Carlo Tree Search (MCTS). Cezary Kaliszyk et al. implemented this in Reinforcement Learning of Theorem Proving, alternating between search playouts and model retraining. The data generated during successful and failed proof attempts refines both a policy network (which predicts the next logical step) and a value network (which estimates the likelihood of a state leading to a valid proof). This self-reinforcing loop allows the system to solve increasingly complex conjectures over successive iterations.

Internal Guidance and Premise Selection

Provers must also learn which existing mathematical theorems (premises) are relevant to a new conjecture. Zarathustra Amadeus Goertzel et al. demonstrate in The Isabelle ENIGMA that successful proof traces from one round can be fed back to specialize internal guidance models for a target domain. Furthermore, Bartosz Piotrowski et al. show in ATPboost: Learning Premise Selection in Binary Setting with ATP Feedback that mining negative data—specifically looking at which premises were selected during failed proof attempts—is just as critical for refining a model's accuracy over multiple rounds.

Decomposing Proofs into Plans and Subgoals

Rather than treating a proof as a single monolithic string, recent frameworks break the problem down into high-level plans and low-level execution steps.

Abstract Planning

In CPL: Critical Plan Step Learning Boosts LLM Generalization in Reasoning Tasks, Junzhe Chen et al. shift the focus of expert iteration from task-specific solutions to high-level abstract plans. By training the model to identify and optimize critical planning steps rather than exhaustive token chains, the system achieves significantly better out-of-domain generalization.

Subgoal Completion

When acting as an assistant to human mathematicians, a model often needs to fill in technical gaps within a high-level proof sketch. Xiao-Wen Yang et al. explore this in FormalML: A Benchmark for Evaluating Formal Subgoal Completion in Machine Learning Theory, showing that training models on their own successful subgoal completions through expert iteration highly optimizes their ability to handle complex, research-level mathematical contexts.

Interleaving Thought and Code

To bridge the gap between human intuition and formal code, models can be trained to generate natural language reasoning before emitting formal tactics. Haohan Lin et al. introduced Lean-STaR: Learning to Interleave Thinking and Proving, which uses expert iteration to refine a model's internal "thoughts." By validating only the final code with a symbolic solver, the model learns which natural language reasoning paths consistently yield correct formal proofs.

[Conjecture] ──► [Internal Thought (NL)] ──► [Formal Tactic (Code)] ──► [Lean Kernel (Verify)]

Bootstrapping from Scarcity to Lifelong Learning

Expert iteration requires a starting point. If a model is too weak to find even a single valid proof, the feedback loop never starts. Researchers use several bootstrapping techniques to kickstart the loop:

Once the loop is active, the final challenge is preventing the model from forgetting old mathematical domains as it learns new ones. Adarsh Kumarappan et al. address this in LeanAgent: Lifelong Learning for Formal Theorem Proving by maintaining a dynamic database of solved problems across diverse repositories. As the model solves new tasks, these verified solutions are continually integrated back into the training curriculum, enabling lifelong learning without catastrophic forgetting.

Key Foundational Work

Reinforcement Learning of Theorem Proving (2018) — contributed 2 concept elements to this direction.
HOList: An Environment for Machine Learning of Higher Order Logic Theorem Proving (2019) — contributed 2 concept elements to this direction.
ATPboost: Learning Premise Selection in Binary Setting with ATP Feedback (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_expert_iteration_6874a199,
  title = {expert iteration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expert-iteration/rdr_6874a19924e64744bcc69dddc01fc61a},
  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_6874a199_v1,
  title = {expert iteration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expert-iteration/rdr_6874a19924e64744bcc69dddc01fc61a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake