acceptodds
Under review as a conference paper at ICLR 2027

LLM-based Automated Theorem Proving Hinges on Scalable Synthetic Data Generation

Abstract

Recent advancements in large language models (LLMs) have sparked considerable interest in automated theorem proving, and a prominent line of research integrates stepwise LLM-based provers into tree search. In this paper, we introduce a lightweight, one-pass data synthesis method that explores a wide range of intermediate proof states to generate diverse proof steps, which facilitates effective one-shot fine-tuning of the LLM policy model. We also propose an adaptive beam size strategy, which effectively takes advantage of our data synthesis method and achieves a trade-off between exploration and exploitation during tree search. Evaluations on the MiniF2F and ProofNet benchmarks demonstrate that our method achieves competitive results compared to strong baselines, attaining an average pass rate of 60.74% on MiniF2F and 21.18% on ProofNet under the stringent Pass@1 metric, as well as a 68.85% pass rate on MiniF2F under the Pass@16 metric. These results underscore the impact of large-scale synthetic data in advancing automated theorem proving.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
large language models, automated theorem proving, tree search methods

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_5DNfOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a data synthesis method for automated theorem proving, enabling the generation of exploration data for fine-tuning LLMs for ATP. By incorporating an adaptive beam size strategy, the proposed method balances exploration and exploitation during tree search. The approach contributes to improving the proving capabilities of LLM-based ATP systems, particularly under limited computational budgets. Specifically, it achieves an average pass rate of 60.74% on MiniF2F under the Pass@1 setting. Given the relative scarcity of training data in formal theorem proving, the proposed data synthesis method also offers practical value.

Critical strengths
  1. The proposed data synthesis method has practical significance for improving LLM-based ATP, as the amount of available training data for automated theorem proving is considerably smaller than that for other programming languages.

  2. The proposed method achieves a promising proof success rate under the limited inference budget of Pass@1. This result provides valuable insights into balancing inference costs and proof success rates in ATP.

Critical weaknesses
  1. The experimental evaluation lacks sufficient benchmark diversity and, more importantly, comparisons with more recent LLM-based ATP methods, such as Goedel-Prover (https://openreview.net/forum?id=j4C0nALrgK) and APOLLO (https://arxiv.org/abs/2505.05758). While the proposed method does not necessarily need to outperform all existing approaches, the current baseline comparisons are insufficient, especially considering the large number of LLM-based ATP methods already evaluated on MiniF2F and ProofNet. Similarly, the coverage of tree-search-based approaches in the related work section is not comprehensive enough. Have more recent and effective tree-search methods emerged in 2025 and 2026? The paper lacks sufficient citations and comparisons with these recent approaches.

  2. In Sections 3.1 and 3.2, several parameter choices appear to be largely based on empirical observations. While such design choices are reasonable, they raise concerns about the generalizability of the proposed method.

Questions for authors

1.The introduction states that the proposed method uses Lean 4 as its underlying ITP but can be easily applied to other proof assistants. However, has the method been evaluated on other proof assistants, such as Isabelle or Coq, to demonstrate its generalizability?

2.In the methodology section, the paper claims that a carefully selected set of commonly used tactics is sufficient to solve the vast majority of problems in practice. However, formal theorem proving extends beyond mathematical proofs to software and systems verification, such as the seL4 project (https://dl.acm.org/doi/abs/10.1145/1629575.1629596). I believe that commonly used tactics alone may not be sufficient for such systems-level verification tasks, as the proofs often rely heavily on project-specific contexts. Has the proposed method been evaluated in these more complex verification scenarios?

6 comments
AuthorsOpenReview ↗

Response to W1

W1

We thank the reviewer for the suggestions regarding experimental coverage and recent related work. Our experiments primarily examine the effectiveness of data synthesis and search strategies in step-level proving settings. We therefore select InternLM2.5-StepProver and BFS-Prover as the main representative baselines under a unified evaluation environment and search budget to make the comparison as fair as possible. In addition, Appendix A.5.2 (Table 4) includes experiments on four datasets, miniF2F_v2s, miniF2F_v2c, Lean-Workbook, and NuminaMath-LEAN, to further examine the applicability of the adaptive beam size strategy across different problem distributions.

We consider the recent works mentioned by the reviewer to provide important research directions for ATP as well. Goedel-Prover-V2 primarily improves whole-proof generation through multi-stage training and self-correction, while APOLLO focuses on proof repair using Lean feedback. In addition, recent tree-search methods, including MPS-Prover, 3D-Prover, and BFS-Prover-V2, improve search performance through multi-perspective search guidance, tactic diversity selection, and multi-agent collaboration, respectively. In comparison, our work primarily focuses on obtaining high-quality training data at a lower data synthesis cost through a single round of proof state exploration and improving search performance through a lightweight adaptive beam size strategy. These methods differ from ours in research objectives and technical approaches and offer complementary directions for further ATP development. We thank the reviewer for the suggestion. In the revised manuscript, we will further introduce and compare these recent representative methods and, together with the existing experiments, more clearly discuss the differences in training pipelines, search mechanisms, and inference budgets to present the positioning and contributions of our work more comprehensively.

AuthorsOpenReview ↗

Response to W2

W2

We thank the reviewer for raising this issue. We understand the reviewer's concerns about hyperparameter selection and the generalizability of the method. Some parameters in this work are indeed set primarily based on empirical observations across multiple experiments, but their design also reflects the corresponding search mechanisms and practical considerations. Specifically, the parameters in Section 3.1 primarily control the trade-off between exploration diversity and computational efficiency during data synthesis, whereas those in Section 3.2 dynamically adjust the beam size at different search stages to balance exploration and exploitation. We further discuss the roles and selection rationale of these parameters in Appendices A.9.4 and A.10 and provide results under different parameter configurations in Tables 8 and 12. These results show that the method's performance is not limited to a single parameter configuration. In addition, Appendix A.5.2 (Table 4) demonstrates the applicability of the adaptive beam size strategy across multiple datasets under the same parameter configuration. These results provide further support for the effectiveness of the method in different settings. In the revised manuscript, we will further clarify the rationale behind the hyperparameter design. In future work, we will conduct more systematic sensitivity analyses and evaluations across scenarios to further examine the method's robustness and generalizability.

AuthorsOpenReview ↗

Response to Q1

Q1

We thank the reviewer for the question. Although all current experiments are based on Lean 4, our method does not depend on proof syntax specific to Lean 4. Coq and Isabelle also support proof-state-based interactive reasoning, and their commonly used proof commands have similar structures. For example, apply H and rewrite H in Coq, as well as apply (rule lemma) and apply (simp add: lemma) in Isabelle, can all be separated into proof operations and their corresponding arguments. Therefore, our core idea of exploring different proof operations through constrained decoding, completing their arguments with a policy model, and verifying state transitions with a proof assistant is, in principle, also applicable to these proof systems.

Of course, proof languages differ in syntax, proof state representation, and verification interfaces, so practical application still requires corresponding adaptations. We also agree that methodological similarities alone are insufficient to establish cross-language generalizability, and direct experimental validation on Coq and Isabelle is currently lacking. We thank the reviewer for the suggestion. In the revised manuscript, we will adjust the relevant wording to clarify the transferability of the method and the scope of the current experiments, and further validate its effectiveness on other proof assistants in future work.

Reviewer_G3qwOpenReview ↗
Rating
3(+1)
Confidence
3(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a single-pass proof-state exploration method for generating training data for automated theorem proving. It encourages tactic diversity through constrained decoding and combines the resulting synthetic transitions with Mathlib data to fine-tune a 7B model. An adaptive beam-size strategy is also introduced for proof search. The method achieves competitive results, including 60.74% on MiniF2F and 21.18% on ProofNet under Pass@1.

Critical strengths
  1. The paper addresses the important problem of training-data scarcity in formal theorem proving. The single-pass synthesis approach provides a practical alternative to repeated Expert Iteration.
  2. The transition-count-matched EI comparison and the weaker-generation-policy experiment provide useful evidence for the effectiveness of the synthesis method.
Critical weaknesses
  1. The diversity and coverage of the generated data remain insufficiently characterized. Although the paper reports approximately 20M combined training transitions and analyzes local tactic diversity, the synthetic/Mathlib breakdown, seed selection, mathematical-domain distribution, and residual near-duplication are unclear. These details are important for assessing how much distinct supervision the method adds.
  2. The discussion of MCTS is overly broad. Finding a complete proof during a rollout and encountering shared proof states do not establish that MCTS is unsuitable for ATP. Existing adaptations, such as HTPS and RMaxTS, have addressed related challenges. The modified-MCTS result in Appendix A.6 alone does not support a general dismissal.
Questions for authors
  1. Could you provide the synthetic/Mathlib data counts, the number and selection criteria of seed theorems, domain coverage, and near-duplicate statistics after filtering?
  2. Beyond the existing sensitivity studies, how were the budget-decay factor and the 60-tactic cutoff selected? Is the tactic restriction applied only during synthesis? How does it affect coverage of problems requiring less frequent tactics?
  3. Appendix A.12 provides useful whole-proof comparisons, but the computational budgets are not directly comparable. Could you provide a measured comparison under matched inference costs, or narrow the corresponding efficiency claims?
  4. Although Appendices A.6 and A.12 provide related results, comparisons with representative MCTS-based and whole-proof generation methods remain insufficient. Could the authors include an established MCTS-based method, such as RMaxTS, and compare against whole-proof generation under comparable inference budgets?
8 comments
AuthorsOpenReview ↗

Response to W1 && Q1

W1 && Q1

We thank the reviewer for the interest in the composition, diversity, and domain coverage of the synthetic data. To address these questions, we provide additional statistical analyses of the training data composition, seed theorem selection, mathematical domain coverage, and near-duplicate samples.

  1. Data composition and seed theorem selection. The final training set contains 19,945,826 proof transitions, approximately 250K of which come from Mathlib. The remaining approximately 19.70M transitions are synthetic data, accounting for 98.75% of the total training data. For seed theorem selection, we use the STP dataset, whose original data contain approximately 3,262,558 problems and their corresponding proofs. After deduplication by theorem statement, we obtain 809,535 distinct theorems and randomly sample 400,000 of them as seeds. Data synthesis follows the method described in Section 3.1, collecting valid state transitions through a single round of proof state exploration. These transitions are then combined with the Mathlib data and post-processed to obtain the final training set.

  2. Mathematical domain coverage. According to existing studies of the domain distribution of STP, the dataset covers multiple mathematical domains, including algebra, calculus, number theory, inequalities, geometry, and combinatorics, with algebra, calculus, number theory, and inequalities accounting for larger proportions. Our 400,000 seed theorems are randomly sampled from the deduplicated STP data without additional filtering for specific mathematical domains, thereby preserving the broad mathematical domain coverage of the original dataset.

  3. Near-duplicate statistics after filtering. We further performed near-duplicate detection on the final training set to quantify data redundancy after the existing filtering pipeline. Specifically, we measure sample similarity using token 5-gram Jaccard similarity and treat samples with the same tactic and a similarity of ≥0.90\geq 0.90 as near-duplicates. We retrieve candidates using LSH and perform exact verification of the candidates. Among all 19,945,826 training samples, we detected 581,002 additional near-duplicate samples, accounting for only 2.91%. This result shows that the proportion of highly similar samples remaining after the existing filtering pipeline is low, and that the synthetic data substantially expand the training scale while maintaining good sample diversity.

We will include these data statistics and the relevant implementation details in the revised manuscript to make the composition, coverage, and diversity of the training data clearer.

AuthorsOpenReview ↗

Response to W2 && Q3 && Q4

W2 && Q3 && Q4

We thank the reviewer for the suggestions regarding the MCTS discussion and the fairness of comparisons across proving paradigms. We agree that methods such as HTPS and RMaxTS have effectively adapted classical MCTS to the characteristics of ATP. Appendix A.6 primarily discusses the MCTS variants we explored in early experiments and their limitations. We will further clarify the scope of this discussion in the revised manuscript and add analyses of representative MCTS methods.

To strengthen the comparison with MCTS methods, we added controlled experiments with two representative search methods, HTPS and RMaxTS. Specifically, for HTPS, we use PUCT-based node selection, generate eight candidate tactics per expansion, and combine state value estimation with cycle pruning during search. For RMaxTS, we use Discounted UCB for node selection, explore subsequent proof states through rollouts of up to eight steps, and incorporate duplicate-state merging and reward backpropagation. All methods use the same step-level policy model and prompts. To ensure a fair comparison, we adopt a budget setting that is more flexible for MCTS, setting the tactic execution limit to 4,800 per theorem rather than limiting the search to 600 node expansions. All methods use a search timeout of 1,800 seconds and are evaluated over five independent runs on all 244 theorems in MiniF2F. The results are as follows:

Table B: Comparison of Search Strategies under a Matched Tactic Execution Budget

Search StrategyPass@1 (Mean ± Std)
HTPS58.03% ± 0.69%
RMaxTS60.08% ± 0.94%
Ours (Adaptive)62.30% ± 1.00%

The results show that, with the same policy model and tactic execution budget, our adaptive beam size strategy outperforms HTPS and RMaxTS by 4.26 and 2.21 percentage points, respectively. This further validates that, by dynamically adjusting search width, our method effectively balances exploration and exploitation without an additional value network and achieves a higher proof success rate.

For whole-proof generation, we added controlled experiments under a matched output token budget. Building on the comparison in Appendix A.12, we set the cumulative output token limit per theorem to 65,536 for all methods and perform five independent evaluations on MiniF2F. All generated output tokens count toward the budget. We report Pass@1 at different budgets based on the cumulative token consumption when a valid proof is first found. The results are as follows:

Table C: Proof Success Rates under Matched Output Token Budgets

Output Token BudgetOurs (Adaptive)Goedel-Prover-SFTDeepSeek-Prover-V1.5-RLDeepSeek-Prover-V1.5-SFT
16K57.13 ± 0.9459.75 ± 0.3451.80 ± 0.6949.84 ± 0.47
32K59.51 ± 0.7960.66 ± 0.5053.61 ± 0.7951.15 ± 0.53
48K61.39 ± 1.2161.31 ± 0.6254.34 ± 0.9051.80 ± 0.85
64K61.97 ± 1.0661.72 ± 0.6254.67 ± 0.7451.97 ± 0.79

The results show that Goedel-Prover-SFT achieves a higher proof success rate under lower output token budgets. As the budget increases, our method gradually closes the gap and achieves higher Pass@1 at the 48K and 64K budgets. At 64K, our method achieves 61.97%, compared with 61.72% for Goedel-Prover-SFT and 54.67% and 51.97% for DeepSeek-Prover-V1.5-RL and DeepSeek-Prover-V1.5-SFT, respectively. These results further demonstrate that our step-level search method is competitive under a matched output token budget and provide direct experimental evidence for comparing inference costs across proving paradigms.

We again thank the reviewer for the suggestions. In the revised manuscript, we will improve the discussion of MCTS and related methods in Appendix A.6, include the above controlled experiments under matched budgets, and revise the inference efficiency discussion in Appendix A.12 to more accurately present the performance and computational costs of different proving paradigms based on actual measurements.

AuthorsOpenReview ↗

Response to Q2

Q2

We thank the reviewer for the question. The budget decay factor γ=0.9\gamma=0.9 was chosen primarily to account for the efficiency of search budget allocation during data synthesis. For easy problems that admit multiple successful proof paths, continuing to allocate the same search budget can lead to redundant exploration. Therefore, whenever a new successful proof path is found, we multiply the current exploration budget by 0.9 to reduce the search cost for easy problems while retaining exploration of other valid state transitions. This value is based mainly on empirical observations in preliminary experiments, with the aim of avoiding overly rapid budget decay while effectively controlling redundant exploration. The ablation in Appendix A.9.3 further validates the role of budget decay: with CD enabled, introducing BD increases Pass@1 from 61.2% to 63.9%.

For the selection of the 60 tactics, we adopt a data-driven approach based on actual usage frequencies. Specifically, we analyze more than three million proof samples in STP, identify 173 distinct tactics, and filter them using a top-p cumulative frequency threshold of 0.999. This yields the smallest set covering 99.9% of all tactic occurrences, namely 60 tactics (Appendix A.13, Figure 6). This set covers major proof operations such as rewriting, algebraic reasoning, structural decomposition, induction, and logical reasoning. This filtering approach aims to balance tactic coverage and data synthesis cost, allowing the synthesis process to more thoroughly explore the applicability of common tactics across different proof states.

We would like to clarify that the restriction to 60 tactics applies only to constrained decoding during data synthesis and does not restrict inference by the final model. The final training data also include Mathlib data that are not subject to this restriction, and we do not impose the same constraint on the tactics generated at inference time. The model can therefore still use low-frequency tactics outside the set. We acknowledge that 99.9% empirical coverage does not constitute a formal completeness guarantee, and some low-frequency tactics may still be decisive for specific problems, particularly in out-of-distribution settings. However, our method does not require this fixed set of 60 tactics: the candidate set can be expanded or reconstructed according to a different target data distribution without changing the overall framework.

Finally, we again thank the reviewer for the suggestion. In the revised manuscript, we will further clarify the rationale for choosing the budget decay factor and tactic set, specify the scope of the tactic restriction, and add a discussion of low-frequency tactic coverage and its potential limitations.

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

This paper proposes a one-pass synthetic data generation method (Proof State Exploration, Algorithm 1) and a test-time Adaptive Beam Size strategy (Eq. 2) for tree-search Automated Theorem Proving (ATP) in Lean 4. Starting from STP seed problems and using BFS-Prover as the exploration policy, the method applies constrained decoding over 60 common tactics (P=0.999\mathcal{P}=0.999 nucleus-filtered from 173 tactics) to generate B=32B=32 distinct tactic operators per state, completes premises via batch inference, retains αB\alpha B branches (α=0.25\alpha=0.25: top-β\beta by score plus αB−β\alpha B - \beta random branches), and decays the per-problem budget by γ=0.9\gamma=0.9 upon finding new proofs. Fine-tuning Qwen2.5-Math-7B on ~20M valid transitions (combined with Mathlib) yields 60.74% Pass@1 (68.85% Pass@16) on MiniF2F and 21.18% Pass@1 on ProofNet.

Critical strengths
  • Operator-Premise Decoupling Prevents Beam Collapse: Forcing B=32B=32 distinct tactic operators via constrained decoding before completing premises directly resolves the common failure mode where standard beam search collapses onto minor naming variations of a single tactic (e.g., 8 identical have or rcases steps, as shown in Figure 5 and Appendix A.9.5).
  • Unified Evaluation & Model-Agnostic Beam Decay: Re-evaluating InternLM2.5-StepProver and BFS-Prover in the same Lean 4.10 environment (DoBeVi) ensures fair comparison, and the linear beam decay (Eq. 2) consistently improves Pass@1 across all three models on MiniF2F (Table 1).
  • Thorough Ablations on Valid vs. Successful Transitions: Appendix A.9 and A.11 systematically verify constrained decoding and budget decay (Table 10), and show that retaining all kernel-valid transitions outperforms keeping only successful proof paths (61.2% vs. 58.0% Pass@1 in Table 13).
Critical weaknesses
  • Unacknowledged Reliance on an EI-Trained Teacher (BFS-Prover) in Main Results: The paper claims its pipeline achieves competitive performance "without relying on EI" (§4.2). However, the 20M synthetic dataset in §4.1 is generated using BFS-Prover—which itself was trained via 10 rounds of Expert Iteration and DPO. Thus, the main model is distilling state transitions from an EI-trained teacher, and on MiniF2F Pass@1 (Table 1), the resulting student model (59.51% Fixed, 60.74% Adaptive) actually underperforms its teacher BFS-Prover (61.07% Fixed, 61.56% Adaptive).
  • Global Expansion Step e/Ee/E vs. Tree Depth dd Mismatch in Eq. (2): Section 3.2 motivates beam decay by arguing that as search depth increases, smaller beams prevent getting trapped in a single subtree. However, Eq. (2) decays beam size by the global expansion step M=e/EM = e/E (E=600E=600), not node depth. In Best-First Search scored by cumulative log-probability score(si+1j)=log⁡Pθ(tj∣si)+score(si)\text{score}(s_{i+1}^j) = \log P_\theta(t_j|s_i) + \text{score}(s_i) (Eq. 1), deeper nodes accumulate more negative scores, causing the priority queue to frequently jump back to shallow nodes near the root at late expansion steps (e→Ee \to E), where Eq. (2) starves them of branching width (Bmin⁡B_{\min}).
  • Unmatched Total Tactic Executions Between Fixed and Adaptive Search: Section 4.1 defines the search budget as K×B×EK \times B \times E (E=600E=600). In Table 1, Fixed search on MiniF2F uses B∗=8B^*=8 (4,8004,800 tactic executions), whereas Adaptive search uses Bmax⁡=16,Bmin⁡=4,λ=15B_{\max}=16, B_{\min}=4, \lambda=15 (Table 12) or higher, altering the total number of Lean 4 kernel calls per search when EE is fixed at 600.
Questions for authors
  • Clarification Requests:
    1. Premise Scoring rijr_i^j in Algorithm 1 (Line 9): When constrained decoding forces a low-probability tactic operator tij∈Tt_i^j \in \mathcal{T}, is the branch score rijr_i^j used for top-β\beta selection the full joint log-probability log⁡P(tij∣si)+log⁡P(pij∣si,tij)\log P(t_i^j | s_i) + \log P(p_i^j | s_i, t_i^j) or only the conditional premise probability log⁡P(pij∣si,tij)\log P(p_i^j | s_i, t_i^j)? If it is the joint probability, doesn't top-β\beta selection immediately discard the rare tactic operators that constrained decoding was designed to explore?
    2. Matched Kernel Execution Budget: In Table 1, what is the average number of total Lean 4 tactic executions ∑e=1600B(e)\sum_{e=1}^{600} B(e) per theorem for Adaptive vs. Fixed (B∗=8B^*=8) on MiniF2F? Does Adaptive still outperform Fixed when capped at the exact same total tactic execution count (4,8004,800) rather than E=600E=600 expansions?
  • Suggestions for Future Work:
    1. Depth-Conditioned Beam Decay: Condition the beam size schedule on the node's tree depth d(si)d(s_i) (or remaining subgoal count) rather than global step e/Ee/E so late backtracking to shallow states retains exploration width.
5 comments
AuthorsOpenReview ↗

Response to W1

W1

We thank the reviewer for raising this issue. We will revise the overly strong wording to make it more appropriate. We would like to clarify that, by emphasizing that our method does not rely on EI, we mean that its data synthesis and training process does not require the multiple rounds of search and iterative training used in EI, rather than requiring the initial policy model to be entirely independent of EI. Our method itself only requires the initial policy to have some Lean proving capability. The core contribution of this work is to obtain high-quality training data at a lower data synthesis cost through more diverse proof state exploration, thereby providing a more efficient data synthesis strategy than conventional EI.

Specifically, EI primarily collects state transitions along successful proof paths to iteratively improve the current policy. In contrast, our method uses constrained decoding (CD) to actively explore diverse tactic operators and their corresponding valid intermediate state transitions, including transitions that do not belong to successful proof paths. By enforcing exploration over a predefined set of tactic operators and then using the policy model to complete the corresponding premises, we reduce dependence on the teacher model's existing preferences for tactic selection. In addition, adaptive budget decay (BD) reduces redundant exploration of easy problems, thereby improving data synthesis efficiency.

Figure 3 and Appendix A.9.1 directly validate the performance and efficiency advantages of our method over multi-round EI. In controlled experiments using the same initial BFS-Prover, base model, and aligned search budgets, our method requires only approximately 5 hours of data synthesis to outperform EI's initial data generation followed by four subsequent iterations, which require approximately 10 hours of cumulative search, reducing data synthesis time by approximately 50%. Even when the final number of training transitions is strictly matched at 384,093, our method achieves a Pass@1 of 58.20%, exceeding EI's 57.30%.

Appendices A.9.3 and A.9.5 further validate the independent contribution of the constrained exploration mechanism. As shown in Table 10, with other conditions held constant, introducing CD alone increases Pass@1 from 52.2% to 61.2%, and the full pipeline further achieves 63.9%. Table 11 shows that our method increases the average number of deduplicated children per node during data synthesis from 2.51 to 4.12, and the number of Lean-valid children from 2.16 to 3.34. This diversity also carries over to evaluation: our method yields 4.85 deduplicated children and 4.41 valid children, compared with 3.82 and 3.46, respectively, for the EI baseline. This indicates that the performance gains arise not only from the capability of the existing teacher model but also from the improvements to the data distribution and policy behavior introduced by our exploration mechanism.

Furthermore, Appendix A.9.2 verifies that our method does not depend on a strong teacher model trained through multiple rounds of EI. We use Qwen2.5-Math-7B fine-tuned only on Mathlib via SFT as the shared initial policy, which proves 135 out of 1,000 theorems on an independent evaluation set. We then perform three rounds of standard EI and one round of constrained exploration, respectively, matching the final training data size at approximately 414K transitions for both methods. With the same student model initialization and training configuration, EI ultimately proves 171 theorems, whereas our method proves 183. This shows that, even when starting from a weaker initial policy, constrained exploration can yield better training outcomes than multi-round EI.

Finally, we thank the reviewer for the suggestion. We will further refine the relevant wording in the revised manuscript to more accurately delineate the prerequisites and core contribution of our method.

AuthorsOpenReview ↗

Response to W2 && S1

W2 && S1

We thank the reviewer for pointing out this issue. The design of Eq. (2) is fundamentally based on dynamically adjusting the beam size according to global search progress to balance exploration and exploitation under a limited budget. Specifically, a larger beam size is used early in the search to thoroughly explore different proof paths; as the search proceeds, the beam size is gradually reduced to focus the search on more promising, high-scoring states. In particular, given the current lack of sufficiently capable value networks to guide formal proof search, existing best-first search methods rely primarily on model probabilities for node selection and may therefore continue expanding locally high-scoring but unproductive subtrees. By gradually reducing the branching width, our method reduces redundant expansions within these subtrees later in the search, allowing the limited budget to be used to try other candidate paths, without relying on the assumption that node depth increases monotonically with search progress.

To further compare the practical effects of different beam size decay schedules, we added a depth-based control experiment. Specifically, we replace the global expansion progress M=e/EM=e/E in Eq. (2) with the depth dd of the node to be expanded and use the following decay formula:

B(d)=⌊Bmin⁡+(Bmax⁡−Bmin⁡)max⁡(1−dD,0)⌋B(d) = \left\lfloor B_{\min} + (B_{\max} - B_{\min}) \max\left(1 - \frac{d}{D}, 0\right)\right\rfloor

Here, DD controls the rate at which the beam size decays with node depth. We test two configurations, D=4D=4 and D=8D=8, and maintain Bmin⁡B_{\min} after the corresponding depth is reached. All experiments use the same policy model, maximum and minimum beam sizes, search budget (E=600E=600), and other evaluation settings, with five independent evaluations on each of MiniF2F and ProofNet. The results are as follows:

Table A: Comparison of Global-progress and Depth-based Beam Size Decay

DatasetOriginal Method (Global Progress)Depth-based Decay (D=4D=4)Depth-based Decay (D=8D=8)
MiniF2F60.74%60.49%60.41%
ProofNet21.18%20.97%20.97%

The results show that the original global-progress strategy outperforms both depth-based decay configurations on MiniF2F and ProofNet. This comparison further demonstrates the practical performance of the two scheduling approaches across different benchmarks. In the revised manuscript, we will further clarify the distinction between global search progress and node depth, improve the motivation in Section 3.2 regarding search budget allocation and the exploration–exploitation balance, and include the above comparison to more accurately explain the rationale and practical effects of the strategy.

AuthorsOpenReview ↗

Response to W3 && Q2

W3 && Q2

We thank the reviewer for raising these two related questions about computational budget fairness. We agree that an identical expansion budget does not imply an identical number of tactic executions. In the original experiments, both the fixed beam size and adaptive beam size strategies use a maximum of E=600E=600 expansions. Although the adaptive beam size strategy starts with a larger beam size (Bmax⁡=16B_{\max}=16), it quickly decays to Bmin⁡=4B_{\min}=4 with global search progress, so this does not imply a larger actual computational cost. To quantify this difference, we counted the actual tactic executions over five independent runs on MiniF2F, comprising 1,220 theorem evaluations. The results show that a fixed beam size of 8 executes an average of 781.184 tactics per theorem, whereas the adaptive beam size strategy executes only 503.119, a reduction of approximately 35.6%.

To further verify computational budget fairness, we conducted an additional controlled experiment with a matched limit on tactic executions. Specifically, we set the maximum number of tactic executions per theorem to 4,800 for both strategies, the theoretical maximum for a fixed beam size of 8 with E=600E=600. All other experimental settings remain unchanged, and we perform five independent evaluations for each strategy on MiniF2F. The results show that a fixed beam size of 8 achieves an average Pass@1 of 61.15% (149.2/244), whereas the adaptive beam size strategy achieves 62.30% (152.0/244), an improvement of 1.15 percentage points. This shows that, even under the same tactic execution budget, the adaptive beam size strategy achieves a higher proof success rate, and its improvement does not depend on increasing the computational budget.

We again thank the reviewer for their attention to experimental fairness. In the revised manuscript, we will further clarify the distinction between the expansion budget and the tactic execution budget, and include the actual tactic execution statistics and the controlled experiment under a matched execution budget to more fully validate the effectiveness and computational efficiency of the adaptive beam size strategy.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.