← AI Techniques Radar
Reasoning & planning

Test-Time Reinforcement Learning (TTRL) lemma-guided search for formal proof construction

A trainable, agentic search procedure for formal theorem proving that uses reinforcement-learning to organize, score, filter, and recursively compose intermediate lemmas at test time. It builds proof attempts by sampling lemma-augmented inputs, prunes lemmas that repeatedly fail, recursively generates and integrates sublemmas when proofs fail, and enforces logical soundness by discarding newly generated lemmas whose negations are provable.

Discovered 2026-11-10 · Sources checked 2026-11-10

This summary was generated with AI assistance.

Why it matters

Long formal proofs often require multi-stage, deeply nested reasoning. By turning proof construction into a structured, goal-directed search over intermediate lemmas (rather than single-step generation or random lemma insertion), the method is designed to extend effective reasoning depth and improve proof reliability through soundness checks.

What changed

Instead of relying on random lemma prepending and single trajectory generation, the approach introduces a lemma-enabled pattern plus a test-time RL search loop that: (1) maintains a lemma utilization score within a defined search scope, (2) preferentially builds inputs using top-scoring lemmas while still exploring additional combinations, (3) prunes unhelpful lemmas based on repeated failure to contribute, (4) recursively decomposes problems by generating sublemmas after repeated failures, and (5) filters out logically inconsistent lemmas via negation proving.

Where it helps

  • Lean-based automated theorem proving with long, multi-stage proofs
  • Neuro-symbolic systems that can consume intermediate lemma candidates during search
  • Proof assistants where error messages and feedback can guide correction loops
  • Any formal reasoning task requiring recursive subgoal/lemma composition

Evidence & reproduction

Reproduction not evaluated. A linked paper or repository does not establish independent reproduction.

Limitations & open questions

The method’s described search also depends on generated/translated candidate lemmas; if lemma quality is poor, the system must rely on its filtering and negation-consistency checks to avoid constructing unsound or trivial proofs.

Sources