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

arXiv: https://arxiv.org/abs/2605.25143 · HTML: https://mlsanity.com/paper/2605.25143/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 13 of its 61 references that are in the map.
- First posted on arXiv 24 May 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 13 of 13)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Phi-4-Mini Technical Report: Compact yet Powerful Multimodal Language Models via Mixture-of-LoRAs](https://mlsanity.com/paper/2503.01743/) (2025)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [Learning to Refine: Self-Refinement of Parallel Reasoning in LLMs](https://mlsanity.com/paper/2509.00084/) (2025)
- [When is the consistent prediction likely to be a correct prediction?](https://mlsanity.com/paper/2407.05778/) (2024)
- [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025)
- [CoLD: Counterfactually-Guided Length Debiasing for Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2507.15698/) (2025)
- [Mitigating Premature Exploitation in Particle-based Monte Carlo for Inference-Time Scaling](https://mlsanity.com/paper/2510.05825/) (2025)
- [Ensembling Language Models with Sequential Monte Carlo](https://mlsanity.com/paper/2603.05432/) (2026)

## Built on by (most cited first, 3 of 3)

- [CUSUM-Shaped Inference-Time Monitoring and Targeted Re-Decoding for Quantized Small Language Model Reasoning](https://mlsanity.com/paper/2607.20129/) (2026)
- [Chopthin-Consensus Power Sampling: A Diversity-Preserving Approach to LLM Decoding](https://mlsanity.com/paper/2609.12243/) (2026)
- [Budget Boundary Effects in Test-Time Mathematical Reasoning](https://mlsanity.com/paper/2609.38699/) (2026)

## Abstract (arXiv)

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 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. We introduce stochastic backtracking over a persistent pool of historical prefixes, allowing test-time compute to revisit previously generated states instead of only expanding the current frontier. To make this efficient, we propose two complementary mechanisms. 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 pool using powered PRM scores and mixture-corrected weights. Across mathematical reasoning benchmarks and model scales, our methods consistently achieve higher accuracy per token count, and the same level of accuracy using only a fraction of the token count in comparison to strong PRM-guided baselines, demonstrating that persistent-pool stochastic backtracking provides a simple and effective way to improve the accuracy-token trade-off in test-time scaling.