acceptodds
Under review as a conference paper at ICLR 2027

Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling

Abstract

Test-time scaling improves language-model reasoning by spending additional compute to explore multiple solution trajectories. The key challenge is to maximize accuracy while minimizing spent compute (e.g., the total number of generated tokens) during reasoning. Recent PRM-guided methods score intermediate prefixes to steer this search, but most are frontier-only: they keep only the current active prefixes and irreversibly prune or resample away the rest using noisy PRM scores. This can cause premature commitment, diversity collapse, and the loss of prefixes that still admit correct continuations. To address this problem, we introduce stochastic backtracking over a persistent pool of historical prefixes, a novel framework allowing test-time compute to revisit previously generated partial solutions instead of only expanding the current frontier. Under this framework, we propose two complementary efficient algorithms. Subpool Selection strengthens greedy PRM-guided search by applying Top- selection within random subpools, giving historical prefixes a chance to bypass over-scored frontier candidates. Power Backtrack Sequential Monte Carlo extends SMC-style resampling to the persistent pools using powered PRM scores and mixture-corrected weights. Our extensive experimental results show that in comparison with a large number of competitive baselines and across a diverse set of mathematical reasoning benchmarks and model scales, our methods achieve the best accuracy per compute (same level of token count and runtime) demonstrating that persistent-pool stochastic backtracking provides a simple and effective way to improve the accuracy–compute trade-off in PRM-guided test-time scaling.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language model, Test-Time Scaling, Stochastic Backtracking

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_11X7OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how noisy process-reward scores can cause search to discard useful partial solutions permanently. It keeps historical prefixes available for later expansion. Subpool Selection chooses promising prefixes from a random part of this history, while Power Backtrack SMC combines new and historical samples with corrected weights. The paper derives a consistency result for a score-based target and compares accuracy under token and runtime budgets on mathematical reasoning tasks.

Critical strengths
  1. The paper connects the problem in the Introduction to both an explicit search mechanism and experimental evidence. Appendix C.5 gives a concrete case where a useful earlier prefix can be revisited, and Table 5 shows benefits from retaining history and from stochastic access to it. With the same general evaluation protocol, Backtrack SMC improves average accuracy from 50.88 to 52.43, and Subpool Selection improves over persistent greedy selection from 51.89 to 55.00. This supports the claim that simply storing history is not enough.

  2. The evaluation is fairly thorough. It includes repeated runs for Qwen2.5, separate token and runtime comparisons, another generator family, and another reward-model family. The mixture-weight derivation makes the sampling target explicit, and the theorem is correctly described as targeting a reward-score proxy rather than true answer correctness.

Critical weaknesses
  1. The component studies establish the value of backtracking and random subpools more clearly than the value of every part of Power Backtrack SMC. I did not find an ablation that keeps the same historical pool and power schedule but removes or replaces only the mixture correction. The power and mixture sensitivity studies are useful, but they do not isolate that new correction. The direct evidence for the proposed failure also relies heavily on one trace-level example; the overall gains support the method, but do not quantify how often recovery from a previously discarded useful prefix explains those gains. The Qwen3 results are point estimates, as acknowledged, so the ranking on that model remains less certain.

  2. The theorem needs a few implementation details made explicit. Algorithms 1 and 4 initialize weights with the reward score, while Appendix B.5 uses the reward score raised to the initial power. These agree if the initial power is one, but this should be stated. The proof also assumes strictly positive scores and a normalized extension rule for every prefix; the paper should explain score flooring and what happens when a prefix is already complete. In the adaptive-power argument, the schedule uses individual particle counts, so its limiting step deserves more explanation than calling it a continuous function of the weighted empirical measure. Appendix B.4 also says low score variance slows the power increase, while Equation 23 gives a larger increase when variance is low. These are fixable points, but they matter for checking that the implemented algorithm is covered by the stated result.

Questions for authors
  1. Is the initial power fixed to one? Please reconcile the initial weights in Algorithm 4 with those in Appendix B.5, and explain how zero scores and completed prefixes are handled.

  2. Could you make the limiting argument for the adaptive power schedule explicit, including the role of particle multiplicities? Please also resolve the difference between Equation 23 and the following explanation of low score variance.

  3. Is there an existing matched-budget ablation that changes only the mixture correction? If recovery statistics over several problems, or repeated Qwen3 runs, are already available, please provide them; these would affect confidence in the component and accuracy claims.

Reviewer_FRG4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes stochastic backtracking over a persistent pool of reasoning prefixes for PRM-guided test-time search. It introduces two implementations: SPS, which selects high-scoring prefixes within randomly sampled historical subpools, and PB-SMC, which combines historical and new prefixes through weighted sampling. Experiments across several models and math benchmarks show improved accuracy under approximately matched token and runtime budgets.

Critical strengths

The motivation is clear: imperfect PRM scores can lead search to discard promising prefixes too early. The experimental coverage is fairly broad, including existing backtracking methods, comparisons under matched token and runtime budgets, and component ablations. Reporting multiple seeds for the Qwen2.5 and Phi-4 experiments is also helpful.

Critical weaknesses
  • My main concern is that the additional insight beyond existing search ideas feels somewhat limited. Preserving previous states and introducing stochastic exploration are natural approaches to avoiding premature commitment. While the results support their usefulness here, I would appreciate a clearer explanation of what this setting teaches us beyond applying these ideas to reasoning prefixes.

  • I am not fully convinced that the experiments separate the benefit of revisiting historical prefixes from that of having a larger and more diverse candidate pool. The matched-budget comparisons are helpful, but adding history changes both factors. A comparison with a similarly sized candidate pool without historical revisits, together with statistics showing how often successful solutions come from previously discarded prefixes, would help support the proposed explanation.

  • The practical benefit of PB-SMC over the simpler SPS is not yet clear. Their results are generally close, and SPS achieves higher average accuracy in the main Qwen experiments. It would be useful to explain when the additional weighting machinery is preferable, or provide a comparison with a simpler historical-pool sampling rule, such as selecting by PRM score most of the time and exploring randomly otherwise.

Questions for authors

See weakness.

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

This paper studies PRM-guided test-time search and identifies irreversible frontier selection as a failure mode: imperfect intermediate scores can permanently discard prefixes that admit correct continuations. The authors propose a framework that allows historical prefixes to receive further computation, instantiated through two algorithms. Subpool Selection (SPS) selects high-scoring prefixes within randomly sampled historical subpools. Power Backtrack SMC (PB-SMC) combines new and resampled historical prefixes using mixture-corrected importance weights and powered PRM scores. The paper establishes asymptotic consistency for the specified surrogate distribution. Experiments across mathematical reasoning benchmarks, generator families, and two PRMs report improved accuracy under approximately matched token and runtime budgets, supported by component ablations.

Critical strengths
  1. A practical approach to an identifiable search failure. Historical access allows computation to revisit earlier decisions, while stochastic subpool selection reduces repeated allocation to globally high-scoring prefixes. SPS is particularly simple and requires no additional training, making it potentially useful across existing PRM-guided search systems.

  2. Evidence from complementary experimental controls. The evaluation includes token-budget and runtime comparisons, compute-scaling curves, component ablations, and changes in both generator and PRM families. The matched-runtime results and backtracking ablations provide meaningful support that the gains reflect improved search allocation.

Critical weaknesses
  1. Key experimental settings are underspecified. The PRM context limit is 4096 tokens, while Qwen3 generates substantially longer reasoning traces, but the handling of long prefixes is not explained. SPS’s parent budget and important baseline settings are also insufficiently documented, making reproducibility and comparison fairness difficult to assess.
  2. The connection between theory and implementation is unclear. The consistency theorem concerns a PRM-defined surrogate distribution, while Algorithm 4 uses weighted sampling and Appendix C.1 selects the highest-scoring terminal answer. Their relationship and the handling of completed trajectories are not clearly specified, limiting the theory’s support for the implemented method.
Questions for authors
  1. How are Qwen3’s long reasoning prefixes scored under the PRM’s 4096-token context limit? Please specify any truncation or segmentation strategy and whether all PRM-guided methods use the same rules.

  2. How does PB-SMC handle completed trajectories and select its final answer? Please reconcile Algorithm 4’s weighted sampling with Appendix C.1’s terminal PRM ranking and clarify whether the consistency analysis covers the implemented termination procedure.

Comments on the paper

4 comments

Thanks for the detailed response, I'm increasing my score accordingly.

Thank you for the detailed responses and clarifications in the revised manuscript. The explanations have adequately addressed the questions and concerns raised in my original review.

I have no further questions at this stage and will maintain my original rating.

Thanks for the detailed responses and additional experiments! The new comparisons and backtracking statistics address my concern about whether revisiting historical prefixes helps.

I still have one question about PB-SMC versus SPS. I understand the theoretical motivation for PB-SMC, but SPS seems to achieve better average accuracy with fewer tokens. Is there a particular setting where PB-SMC works better, or another practical reason to prefer it over SPS?

Thank you for this question. We agree that on Qwen2.5-7B-Instruct, SPS offers a better average accuracy–token trade-off, and its simplicity makes it an attractive practical choice. Our experiments also identify settings that favor PB-SMC.

For Phi-4-mini-Instruct on Minerva (Table 12, lines 1443–1444), PB-SMC achieves 37.87 ± 0.37% accuracy versus 36.27 ± 0.42% for SPS, using approximately 3.1% more tokens but with less time. For Qwen3-32B Thinking on Minerva (Table 2, lines 394–395), PB-SMC achieves 59.68 ± 0.46% versus 58.21 ± 0.76%, using approximately 2.3% more tokens. Across the three Qwen3 benchmarks, their mean accuracies are nearly identical: 58.23% for PB-SMC and 58.18% for SPS. These comparisons favor different methods in different settings. Practically, we recommend selecting between them on a held-out validation set representative of the intended workload.

Our central contribution is stochastic backtracking over historical prefixes, instantiated through these two complementary approaches. Both benefit from revisiting historical states, while offering different allocation trade-offs. Future work could extend either one of these approaches, or try to combine their strengths. We will emphasize this subtle point in the manuscript. We thank the reviewer again for this thoughtful and constructive question.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.