acceptodds
Under review as a conference paper at ICLR 2027

Reap: Uncovering Monte-carlo proof search with lightweight model

Abstract

We present Reap, an open framework for learning and analyzing formal proof search in Lean 4. Reap implements policy–value-guided Monte Carlo Tree Search directly in Lean, sharing proof-state transitions, AND–OR search, and replay verification between inference and training rollouts. Structured action logs expose how neural predictions and tactic execution interact during search. Using this framework, we train Reaper-1, a 1.7B-parameter policy–value model, through continued pre-training, supervised tactic learning, and iterative search-based reinforcement learning. Using a separate premise selector, the final system solves 79.9% of miniF2F-test at pass@32, establishing state-of-the-art performance among open provers of comparable size while remaining competitive with substantially larger models. Beyond improved solve rates, our results suggest that RL strengthens the prover’s ability to organize proofs around useful intermediate results, favoring substantial advances over repeated local adjustments. This more directed proof construction is accompanied by increasingly elaborate tactic programs: fewer explicit search decisions are needed, while more work is performed within each decision. The resulting trade-off between search effort and tactic execution cost provides insight into how learning changes the prover’s problem-solving strategy.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
formal theorem proving

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_jSztOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Reap implements MCTS inside Lean, sharing proof-state transitions, reconstruction, replay, and logging between inference and training. Reaper-1 is a 1.7B backbone trained through continued pre-training, supervised learning, and search-based expert iteration. With a separate premise selector, it solves 195/244 miniF2F-test problems at pass@32.

Critical strengths

S1. The integrated infrastructure combines native proof states, replay verification, and step-level logging in a useful platform for studying proof search.

S2. The reported miniF2F-test improvement is substantial, demonstrating effectiveness of the MCTS-based reinforcement learning

S3. The behavioral analysis is careful and very detailed

Critical weaknesses

W1. What does MCTS add beyond a simpler search? Table 2 retains 193 versus 195 solves without neural value guidance, although guidance reduces mean proof actions by roughly 6% on shared problems; Table 4 reaches 188 solves at 512 simulations. These useful controls do not compare MCTS with simpler search using the same trained model, leaving the practical inference-time benefit of this central design choice unresolved.

Questions for authors
  1. Using the same RL5 model and retriever, how does best-first search compare with MCTS under matched generation and Lean-execution budgets? This would test the inference-time search choice, not whether MCTS was useful during training.
2 comments

Thank you for suggesting this comparison. To examine the inference-time search choice, we implemented best-first search (BFS) in Reap and compared it with MCTS on miniF2F-test using the same RL5 checkpoint and PS-2 retriever, without retraining. Both configurations use 32 L40 GPUs for the prover, pass@8, and a 7,200-second timeout.

Search methodProblems solved (pass@8)Mean time per successful attemptMean completion tokens per successful attempt
MCTS177/244124 s3,533
BFS122/2445 s121

MCTS solves 55 more problems (+22.5 percentage points), while BFS uses substantially less time and fewer tokens per successful attempt. Time is measured end to end through final verification, and completion tokens include all tactics generated during each successful attempt. This comparison uses a common timeout, but does not separately match generation and Lean-execution budgets.

Our current BFS implementation is a preliminary baseline developed for this ablation. Unlike MCTS, it has not been adapted to the AND–OR tree structure used during training rollouts. This mismatch may partly explain the large performance gap, so these results should not be interpreted as a definitive comparison between fully optimized search algorithms.

For inference-time search recommendation, we are continuing to improve the BFS implementation to make it stable and easy to use in the final open-source release.

I thank the authors for their responses. I maintain my score.

Reviewer_jyGGOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces Reap, a Lean-native policy–value-guided MCTS framework that shares proof-state transitions, AND–OR search, proof reconstruction, and replay verification between inference and reinforcement-learning rollouts. Using this framework, the authors train Reaper-1, a 1.7B policy–value model initialized from Qwen3-1.7B-Base, through continued pre-training, supervised tactic learning, and five stages of search-based expert iteration.

Critical strengths
  • Running the semantics-critical search loop inside Lean and sharing it across training and inference is a well-motivated design.
  • The final checkpoint retains 75.8% miniF2F accuracy when PS-2 is replaced by SineQuoNon without retraining, and reaches 77.05% with a 512-simulation budget.
Critical weaknesses
  • The small coverage change in the value-head ablation (195 vs. 193 solved problems) and absence of compute-matched search baselines leave the specific benefit of value-guided MCTS unclear.
  • The additional 8B retriever and heterogeneous baseline budgets mean that the 1.7B backbone alone does not establish an end-to-end efficiency advantage.
  • Increased structural-tactic use does not distinguish better intermediate-lemma discovery from action packaging encouraged by the unit-cost objective.
Questions for authors
  • How does MCTS compare with greedy or best-first search using the same checkpoint and retriever under matched compute budgets?
  • Do the claimed proof-structure improvements persist after expanding compound actions into finer-grained tactic operations?
  • Can you report accuracy versus end-to-end resource usage for both neural and rule-based retrieval, including unsuccessful attempts?
3 comments

Answer to Q1

We implemented best-first search (BFS) in Reap and compared it with MCTS on miniF2F-test using the same RL5 checkpoint, PS-2 retriever, 32 L40 GPUs, pass@8, and a 7,200-second timeout.

Search methodProblems solved (pass@8)Mean time per successful attemptMean completion tokens per successful attempt
MCTS177/244124 s3,533
BFS122/2445 s121

MCTS solves 55 more problems (+22.5 percentage points), while BFS uses substantially less time and fewer tokens per successful attempt. Time is measured end to end through final verification, and completion tokens include all tactics generated during each successful attempt.

Our current BFS implementation is a preliminary baseline developed for this ablation. Unlike MCTS, it has not been adapted to the AND–OR tree structure used during training rollouts. This mismatch may partly explain the large performance gap, so these results should be interpreted with this limitation in mind. We are continuing to improve the BFS implementation to make it stable in the final open-source release.

Answer to Q2

Yes. After splitting compound actions at ; and <;>, the average number of tactics in successful proofs still decreases from 15.27 (RL4) to 12.19 (RL5). Thus, the proofs become shorter under this finer-grained count as well.

We also tracked have, a structural tactic that introduces an intermediate result. Under identical inference budgets on miniF2F, the average number of have occurrences per successful attempt increases from 0.429 (RL4) to 4.269 (RL5), nearly 10x. We count individual occurrences, including multiple have tactics within a compound action, so this count is unaffected by how tactics are grouped into actions. Taken together, fewer decomposed tactics and more explicit intermediate results provide statistical evidence to proof structure improvement, beyond compound-action compression.

From a qualitative perspective, we also observe better proof strategies across RL checkpoints. In the sum-of-cubes example from Appendix D, reproduced below, the proof shrinks from approximately 75 lines (RL4) to 22 lines (RL5). Both proofs use induction, but RL5 makes more direct induction hypothesis, and replaces repeated case analysis with a more focused argument. This reflects an explicit change in proof strategy.

RL4 proof (abridged from Appendix D, Listing 1; comments mark omitted tactics):

theorem induction_sumkexp3eqsumksq_rl4 (n : ℕ) :
    (∑ k ∈ Finset.range n, k ^ 3) = (∑ k ∈ Finset.range n, k) ^ 2 := by
  induction n
  · simp [Finset.sum_range_succ]
  · simp [Finset.range_succ, Finset.sum_insert, *]
    -- ... repeated ring, abel, simp, and ring_nf calls
    clear * -
    -- Start a second induction after clearing the local hypotheses.
    induction' ‹ℕ› with n hn
    · rfl
    · simp [Finset.sum_range_succ]
      ring_nf
      rw [hn]
      -- ... further normalization with ring_nf, abel_nf, and rewriting
      cases n
      · rfl
      · -- ... alternate ring and simp on the goal and induction hypothesis
        rw [Finset.sum_range_id]
        ring_nf at hn ⊢
        -- ... more ring/ring_nf/simp calls, followed by aesop
        -- ... two further nested cases n splits, with more normalization
        -- ... finally, rewrite Finset.sum_range_id again and close with grind

RL5 proof (Appendix D, Listing 2; same imports and options as above):

theorem induction_sumkexp3eqsumksq_rl5 (n : ℕ) :
    (∑ k ∈ Finset.range n, k ^ 3) = (∑ k ∈ Finset.range n, k) ^ 2 := by
  induction n with
    | zero => ?_
    | succ n ih => ?_
  · simp_all
  · simp [Finset.sum_range_succ, ih]
    rw [add_sq]
    rw [Finset.sum_range_id]
    cases n
    · simp at ih ⊢
    · ring_nf
      simp [add_assoc, add_comm, add_left_comm] at ih ⊢
      ring_nf at *
      simp [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] at *
      aesop (add simp [Nat.pow_two, Nat.mul_div_cancel_left])
      rcases n.even_or_odd' with ⟨m, rfl | rfl⟩ <;> grind [Nat.mul_div_cancel']

For intermediate-lemma construction, we observe that later checkpoints introduce useful intermediate results, and we believe this contributes to the final model's ability to solve previously unsolved problems. For example, earlier checkpoints fail to prove amc12a_2021_p18, but RL5 succeeds by introducing identities using have, notably f(25/11)+f(11)=f(25)f(25/11) + f(11) = f(25) and f(25)=2f(5)f(25) = 2f(5). Together with the prime-value assumptions, these imply f(25/11)=−1f(25/11) = -1. The generated proof below illustrates how intermediate results support the deductions needed to solve the problem:

theorem amc12a_2021_p18 (f : ℚ → ℝ) (h₀ : ∀ x > 0, ∀ y > 0, f (x * y) = f x + f y)
    (h₁ : ∀ p, Nat.Prime p → f p = p) : f (25 / 11) < 0 := by
  have h₂ : f (25 / 11 : ℚ) = f ((5 : ℚ) ^ 2 / (11 : ℚ) ^ 1) := by norm_num [pow_succ]
  have h₃ := h₀ (25 / 11 : ℚ) (by norm_num) (11 : ℚ) (by norm_num)
  have h₄ : (25 / 11 : ℚ) * (11 : ℚ) = (25 : ℚ) := by norm_num [div_mul_eq_mul_div]
  have h₅ : f (11 : ℚ) = (11 : ℝ) := h₁ 11 Nat.prime_eleven
  have h₆ := h₀ 5 (by norm_num) 5 (by norm_num)
  have h₇ := h₀ (5 : ℚ) (by norm_num) (5 : ℚ) (by norm_num)
  have h₈ : f (5 * 5 : ℚ) = 2 * f (5 : ℚ) := by linarith [h₆]
  have h₉ : f (5 * 5) = f (5 : ℚ) + f (5 : ℚ) := h₆
  have h₁₀ := h₀ (5 : ℚ) (by norm_num) (5 : ℚ) (by norm_num)
  have h₁₁ : f 5 = 5 := by
      have h₁₂ := h₁ 5 (by decide)
      norm_num at h₁₂ ⊢
      exact h₁₂
  have h₁₂ := h₀ (5:ℚ) (by norm_num) (1/5:ℚ) (by norm_num)
  simp [h₄, h₅, h₁₁] at h₃ h₆ h₇ h₈ h₉ h₁₀ h₁₂ ⊢
  have h₁₃ := h₀ 11 (by norm_num) (25 / 11) (by norm_num [h₅])
  norm_num at h₀ h₁ h₂ h₄ h₅ h₆ h₇ h₈ h₉ h₁₀ h₁₂ h₁₃ ⊢
  have h₁₄ := h₀ 11 (by norm_num) (25 / 11) (by norm_num)
  norm_num [h₅] at h₁₄
  linarith [h₃, h₆, h₇, h₈, h₉, h₁₀, h₁₂, h₁₃, h₁₄, h₅, h₁₁]

Together, the reduction in decomposed tactic counts, increased use of intermediate results, and qualitative improvements in proof strategy suggest that RL improves proof structure and intermediate-lemma construction beyond simply learning longer compound actions.

Answer to Q3

Thank you for this suggestion. We evaluated PS-2, SineQuoNon, and MePo on miniF2F-test using the same RL5 checkpoint, MCTS configuration, pass@8, and a 7,200-second timeout. All three configurations use 32 L40 GPUs for the prover. PS-2 additionally uses 32 L40 GPUs for its neural retrieval service, whereas SineQuoNon and MePo require no additional neural model or retrieval GPUs.

Premise selectorProblems solved (pass@8)Mean successful-attempt timeMean successful-attempt tokensMean unsuccessful-attempt timeMean unsuccessful-attempt tokens
PS-2177/244 (72.5%)124 s3,5331,138 s34,368
SineQuoNon176/244 (72.1%)63 s3,0691,731 s64,307
MePo165/244 (67.6%)453 s5036,976 s8,289

Time is measured end to end, through final verification for successful attempts and termination for unsuccessful attempts. Completion tokens count all policy-generated tactics within an attempt, including failed tactics and branches outside the final proof. We report successful and unsuccessful attempts separately to make their different resource costs explicit.

SineQuoNon solves only one fewer problem than PS-2. But it reduces mean successful-attempt latency by 49.2% with no need foor 8B neural retriever. Its unsuccessful attempts, however, take longer and generate more tokens on average, so the latency reduction does not apply uniformly across all attempts. MePo also retains substantial proving capability (165/244), but has markedly higher latency due to the computational overhead of its own implementation.

Reviewer_SYT4OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors develop a framework using Lean 4 metaprogramming for training and running an MCTS algorithm for theorem proving. They train their own policy-value model and report state-of-the-art performance on miniF2F (pass@32) among similarly sized models. Finally, they analyse how their model's proof style evolves throughout training.

Critical strengths
  • The method (tree search, different training stages) is clearly explained.
  • The reported performance is at or near the state of the art on miniF2F (pass@32) among models of comparable size.
  • The ablations in Section 4.4 are very informative and clarify the roles of the value head and the premise selection model.
Critical weaknesses
  • The benefits of implementing tree search directly in Lean are unclear.
  • Comparing whole-proof systems and step-level systems using pass@32 does not seem entirely fair to me. Evaluating them under equal inference budgets would provide a fairer and more informative comparison.
Questions for authors
  • What are the benefits of implementing tree search directly in Lean? Can these benefits be quantified?
  • Could you provide comparative evaluation results under equal inference budgets?
1 comment

Answer to Q1

Thank you for asking us to clarify this design choice. Implementing tree search directly in Lean serves three practical purposes: providing direct access to proof states, unifying the implementation for training rollouts and interactive use, and facilitating integration with Lean's existing tools.

  1. Implementation provides direct access to proof states. Regardless of the language used to orchestrate the search, some critical operations, such as tactic execution, unification, and proof checking, ultimately must happen in Lean. Reap also manipulates metavariables to decompose goals into AND/OR nodes and manages the corresponding search states. Keeping this logic in Lean allows the search procedure to work directly with these objects, without requiring an additional interface between the search controller and Lean's execution environment. This simplifies state management and avoids communication overhead at the interface boundary.

  2. Implementation unifies training and end use. Reap supports two modes of operation: generating training rollouts and being invoked as a Lean tactic. Reusing the same search implementation helps ensure consistency in tactic execution and goal handling across these settings, reducing discrepancies that might arise if training and inference relied on separately implemented systems. For end users, this also means that they can invoke the tactic simply by importing Reap into their projects, without any additional installation steps.

  3. Integration and maintenance become easier. A Lean implementation facilitates the reuse of native proof-search tools, such as Aesop, and premise-selection interfaces, such as the Lean.LibrarySuggestions API. Additional experiments with alternative premise selectors further illustrate this flexibility. It also centralizes adaptations required for new Lean versions within the Lean codebase, reducing the need to maintain a separate language binding alongside the search implementation.

Regarding quantification, we have not conducted a controlled comparison between Lean-native and externally orchestrated implementations because we could not identify a readily available public MCTS framework for Lean that could serve as a comparable external baseline. Building and debugging such a baseline would require substantial engineering effort, while providing limited additional insight into the design choices. We therefore leave this comparison to future work.

Answer to Q2

Thank you for this suggestion. We agree that equal pass counts do not necessarily imply equal inference budgets across whole-proof and step-level systems. To provide a more informative comparison, we evaluated Reaper-1 against Kimina-Prover-RL-1.7B on miniF2F-test at pass@8 and measured generated tokens and end-to-end latency. Both systems are served on 32 L40 GPUs;

MetricReaper-1 (MCTS)Kimina-Prover-RL-1.7B
Problems solved (pass@8)177/244 (72.5%)161/244 (66.0%)
Mean end-to-end time per successful attempt124 s155 s
Mean completion tokens per successful attempt3,5333,903

For Kimina-Prover, completion tokens include both reasoning and the final proof. For Reaper-1, they include all policy-generated tactics during MCTS, including failed tactics and explored branches outside the final proof. End-to-end time is measured from the start of an attempt through final verification. The averages above are computed over each system's successful attempts.

Reaper-1 solves 16 more problems, a gain of 6.6 percentage points, while using 9.5% fewer completion tokens and 20% less time per successful attempt on average. Although whole-proof generation does not use explicit tree search, its reasoning tokens also contribute to the inference cost. On successful attempts in this experiment, Kimina-Prover's combined reasoning and proof tokens are comparable in number to all tactic tokens generated during MCTS.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.