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

• URL: http://arxiv.org/abs/2605.25143v2
• Date: Sun, 31 May 2026 05:24:41 GMT
• Title: Beyond the Frontier: Stochastic Backtracking for Efficient Test-Time Scaling
• Abstract summary: Test-time scaling improves language model reasoning by spending additional compute to explore solution trajectories.<n>The key challenge is to maximize accuracy while minimizing the total number of generated tokens during reasoning.<n>We introduce backtracking over a persistent pool of historical prefixes, allowing test-time compute to revisit previously generated states.
• Score: 4.636680302276584
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• ThinkRetrieve: Retrieval-Augmented Reasoning Traces for Test-Time Scaling [60.48279351544583]
  ThinkRetrieve is a test-time scaling framework for large reasoning models.<n>It retrieves relevant exemplars at each intermediate step and injects them directly into the thinking trace.<n>It consistently improves accuracy over standard test-time scaling.
  arXiv  Detail & Related papers  (2026-08-11T13:58:07Z)
• PriFT: Prior-Support Guided Supervised Fine-Tuning [74.65198014829393]
  Supervised fine-tuning (SFT) is an efficient approach for downstream task adaptation.<n>SFT fits fixed demonstrations token by token, including targets poorly aligned with the model's pretrained distribution.<n>We propose PriFT, which derives token weights from a frozen pretrained reference to obtain a stable reweighting signal unaffected by fine-tuning.
  arXiv  Detail & Related papers  (2026-06-08T12:14:06Z)
• DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Diffusion Language Models [76.12556589212666]
  We introduce DPRM (Doob h-transform Process Reward Model), a plug-in token-ordering module for diffusion language models.<n>DPRM starts from confidence-driven progressive ordering and gradually shifts to Doob h transform Process Reward guided ordering through online estimates.<n>Under tractable optimization assumptions, DPRM also yields a sample-complexity advantage over random and confidence-only ordering.
  arXiv  Detail & Related papers  (2026-04-27T11:50:26Z)
• Unleashing Implicit Rewards: Prefix-Value Learning for Distribution-Level Optimization [74.91418266859297]
  Implicit process reward models (PRMs) provide fine-grained reward signals along the reasoning process.<n>PRMs suffer from a train-inference mismatch: training only constrains a sequence-level aggregate, whereas inference requires token-level scores to reflect local step quality.<n>We propose a novel Implicit Prefix-Value Reward Model (IPVRM), which directly learns a prefix-conditioned value function estimating the probability of eventual correctness.<n>We also propose Distribution-Level RL (DistRL), which computes TD advantages for both sampled tokens and high-probability candidate tokens.
  arXiv  Detail & Related papers  (2026-04-14T18:19:54Z)
• AdaPonderLM: Gated Pondering Language Models with Token-Wise Adaptive Depth [23.442686851761298]
  AdaPonderLM is a self-supervised recurrent language model that learns token-wise early exiting during pretraining.<n>AdaPonderLM reduces inference compute at about 10% while maintaining comparable language modeling perplexity and competitive downstream accuracy.
  arXiv  Detail & Related papers  (2026-03-02T14:28:16Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  We propose a self-consistency framework that turns cheap diffusion-sampled reasoning into a reusable pool of step-level candidates.<n>We find that step-level recombination is most beneficial on harder problems.<n>Our training-free framework improves average accuracy by up to 2 across six math and coding tasks.
  arXiv  Detail & Related papers  (2026-02-26T11:08:39Z)
• Save the Good Prefix: Precise Error Penalization via Process-Supervised RL to Enhance LLM Reasoning [59.76691952347156]
  Reinforcement learning (RL) has emerged as a powerful framework for improving the reasoning capabilities of large language models (LLMs)<n>Most existing RL approaches rely on sparse outcome rewards, which fail to credit correct intermediate steps in partially successful solutions.<n>We propose Verifiable Prefix Policy Optimization (VPPO), which uses PRMs only to localize the first error during RL.
  arXiv  Detail & Related papers  (2026-01-26T21:38:20Z)
• Thinking Traps in Long Chain-of-Thought: A Measurable Study and Trap-Aware Adaptive Restart [27.904791075662896]
  We introduce TAAR (Trap-Aware Adaptive Restart), a test-time control framework that trains a diagnostic policy to predict two signals from partial trajectories.<n>At inference time, TAAR truncates the trajectory before the predicted trap segment and adaptively restarts decoding.<n>Experiments show that TAAR improves reasoning performance without fine-tuning base model parameters.
  arXiv  Detail & Related papers  (2026-01-17T07:26:02Z)
• SPINE: Token-Selective Test-Time Reinforcement Learning with Entropy-Band Regularization [24.699488237384134]
  We propose SPINE, a token-selective test-time reinforcement learning framework.<n>We show that SPINE consistently improves Pass@1 over TTRL while avoiding response-length collapse.<n>These results indicate that aligning updates with chain-of-thought branch points is a simple and label-free mechanism for stable and effective test-time adaptation.
  arXiv  Detail & Related papers  (2025-11-22T06:32:34Z)
• TARG: Training-Free Adaptive Retrieval Gating for Efficient RAG [46.122203287541005]
  Training-free Adaptive Retrieval Gating (TARG) is a single-shot policy that decides when to retrieve using only a short, no-latency draft from the base model.<n>On NQ-Open, TriviaQA, and PopQA, TARG consistently shifts the accuracy-efficiency frontier.
  arXiv  Detail & Related papers  (2025-11-12T23:09:52Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs.<n>We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint.<n>We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.