Kimina-Prover: Test-time RL Search for Formal Theorem Proving

Overview

Kimina-Prover-72B is a state-of-the-art automated theorem proving (ATP) model designed for the Lean 4 language, achieving a 92.2% pass rate on the miniF2F-test benchmark. By integrating Test-Time Reinforcement Learning (TTRL) search and a novel error-fixing mechanism, the system moves beyond single-step reasoning to autonomously decompose complex mathematical problems into manageable sub-lemmas.

Test-Time Reinforcement Learning (TTRL) Search

The TTRL search framework shifts theorem proving from random exploration to a goal-directed, agentic process. It utilizes a "lemma-enabled pattern" where the model is trained to identify and incorporate intermediate lemmas into its proof construction.

Key components of the TTRL framework include:

  • Dynamic Lemma Scoring: The system tracks the utility of lemmas within a search scope, prioritizing those that frequently contribute to successful proofs while pruning those that fail to meet a minimum utilization threshold (τ=0.10).
  • Recursive Decomposition: When a theorem or lemma fails to be proven after 128 attempts, the system triggers a sublemma generation process. This allows the model to recursively break down hard problems into smaller, provable components.
  • Logical Soundness: To prevent the model from exploiting inconsistencies to generate trivial proofs, the system employs a "negation proving process." If the logical negation of a generated lemma is provable, the original lemma is discarded as inconsistent.

Error-Fixing and Sample Efficiency

Kimina-Prover improves sample efficiency by interpreting Lean’s error messages to perform iterative corrections rather than restarting proofs from scratch. The team developed a specialized Supervised Fine-Tuning (SFT) dataset consisting of (incorrect proof, Lean feedback, correct proof) triplets, augmented with step-by-step reasoning chains synthesized by Claude 3.7 Sonnet.

To integrate this into the reinforcement learning loop, the team implemented a "Batched Failure Replay" strategy. By training on a fixed-size union of previous failures and standard problems, the model learns to resolve complex logical mistakes and syntax errors, consistently outperforming brute-force sampling strategies under equivalent computational budgets.

Model Variants and Performance

In addition to the flagship 72B parameter model, the release includes distilled variants to support diverse deployment needs:

  • Kimina-Prover-72B: Based on Qwen2.5-72B, achieving 92.2% on miniF2F-test.
  • Kimina-Prover-Distill-8B: Based on Qwen3-8B.
  • Kimina-Prover-1.7B: Based on Qwen3-1.7B.

Performance data indicates that while earlier models scaled linearly with sampling budgets, the current system shows diminishing returns beyond pass@1024, suggesting that further improvements rely more on the sophisticated search strategies provided by TTRL than on raw sampling volume.

Sources