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

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-$N$ 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.