Beam-search-based test-time methods provide an effective way to improve large language model (LLM) performance on long-horizon generation by pruning invalid reasoning paths early, leading to significantly improved reasoning efficiency and more favorable test-time cost scaling. Despite strong empirical success, the theoretical understanding of beam search remains limited. In this paper, we study the test-time compute guarantee of the commonly used beam search framework that uses the model's internal log-likelihood for intermediate scoring, while relying on an external reward model only after a complete response is generated. We first establish a lower bound for vanilla beam search, showing that at least Ω(C⋆(x)2) samples are required for the optimal response to survive, where C⋆(x) is the token-level coverage coefficient for prompt x. This motivates our modified confidence-filtered beam search (CF-Beam), which reduces the sufficient coverage dependence from quadratic to nearly linear under prefix competitiveness, for fixed horizon, gap, and target accuracy. We then show that the regret of CF-Beam is upper-bounded by the probability of rare failure events and the reward estimation error scaled by a path-level coverage coefficient, where the rare-failure term vanishes as per-step sampling increases. Our results highlight a fundamental advantage of beam search over sequence-level inference methods such as Best-of-N and Best-of-Majority. While the guarantees of these approaches typically involve coverage coefficients that grow exponentially with the horizon L, CF-Beam controls the dominant search-induced term through a token-level coverage coefficient that scales polynomially with L. Our numerical experiments further confirm that beam search is more robust on hard instances and under increasing reasoning horizons.
Prefix (trajectory) up to step t : st=(a1,…,at) .
b
Beam width, i.e., the number of trajectories retained at each step.
B
Test-time compute budget, i.e., the total number of samples drawn from πref .
Table 1 : Summary of Notations Used in the Paper
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Best-of- N
Majority Voting
Best-of- Majority
Vanilla-Beam
CF-Beam
Accuracy
0.332
0.304
0.326
0.372
0.388
Budget ( ×103 )
16.8
16.8
16.8
18.6
16.2
Appendix
Table 2 : Comparison on 500 synthetic 4×4 integer matrix-multiplication problems using Qwen3-1.7B-Base. Beam methods use N=12 and b=2 ; Empirical CF-Beam uses γ=0.3 . Budgets are reported in thousands of token-level policy queries.
γ=0
0.15
0.3
0.45
0.6
0.75
0.9
b=2
0.372
0.378
0.388
0.372
0.318
0.292
0.290
b=4
0.482
0.512
0.472
0.392
0.374
0.330
0.302
b=8
0.536
0.550
0.480
0.434
0.364
0.292
0.300
Appendix
Table 3 : Accuracy under different beam widths b and filtering coefficients γ on the same LLM task, with N=12 . The column γ=0 corresponds to Vanilla-Beam. Bold entries mark the highest accuracy for each beam width.
Test-time compute scaling is a primary driver of performance in large reasoning models (LRMs), but extreme inefficiency bounds current approaches, shifting the critical question from \emph{how much} compute to spend, to \emph{where} to allocate it. We formalize test-time reasoning as a constrained compute allocation problem over partial trajectories. Under a fixed hardware budget, existing paradigms fail to actively allocate the compute to the most promising partial progress: traditional parallel sampling treats traces independently and induces severe memory bottlenecks, while subtractive pruning starves hardware and fails to actively and sufficiently shift the output distribution. To overcome this dichotomy, we introduce Gambit, an inference algorithm that executes \emph{thought-level beam search}. By periodically pruning unpromising trajectories and immediately branching from high-quality prefixes, Gambit dynamically concentrates compute onto the most promising reasoning traces via a light-weight scorer probing hidden states while maintaining continuous high hardware utilization. Extensive evaluations across multiple models and benchmarks demonstrate that Gambit strictly dominates existing baselines. Under identical hardware constraints, our method yields up to a +6.7% absolute accuracy gain on HMMT-24 and +3.3% on AIME-25 over pruning baselines, delivers >2× higher throughput on trace completion, and reduces total token consumption by up to 68.5% relative to standard parallel sampling.
As pretraining scaling laws approach saturation, Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior. Viewed at a high level, TTS reframes inference as search over a space of partial reasoning states. While Chain-of-Thought (CoT) exposes intermediate steps, common instantiations rely on single-trajectory decoding, limiting recovery from early errors and exploration. This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding. We trace the evolution from uninformed search to Monte Carlo Tree Search (MCTS), highlighting how sampling-based control supports principled exploration-exploitation trade-offs. To unify a fragmented literature, we introduce a Unified Design Space spanning search topology, evaluation signals, and control dynamics, and advocate a standardized compute-reporting abstraction to make compute-accuracy trade-offs explicit and comparable.
Jiaqi Wei, Xiang Zhang, Yuejin Yang +10
1Zhejiang University · 2Shanghai AI Laboratory · 4Fudan University +3
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.