Provable Test-Time Scaling for Beam Search in LLM Reasoning¶
Conference: NeurIPS 2026
arXiv: 2609.38672
Area: Others
Keywords: Beam Search / Test-Time Scaling / LLM Reasoning / Confidence Filtering / Regret Analysis
TL;DR¶
Addressing the exponential test-time compute scaling of sequence-level sampling methods in long-horizon LLM reasoning, this paper establishes the first theoretical test-time guarantees for beam search, uncovers a quadratic coverage lower bound for vanilla beam search, and proposes Confidence-Filtered Beam Search (CF-Beam) to achieve near-linear coverage dependence and polynomial scaling with reasoning horizon length.
Background & Motivation¶
In complex multi-step reasoning tasks such as mathematical problem solving, code generation, and logical deduction, autoregressive large language models operating via single-pass greedy decoding are highly prone to compounding errors, where minor early imperfections derail the entire reasoning trajectory. To push past the static capabilities of fixed model parameters, test-time computing has emerged as a dominant paradigm. Existing parallel inference techniques, including Best-of-N (BoN) sampling, majority voting, and their hybrid variants such as Best-of-Majority, typically operate at the sequence level by drawing multiple full candidate completions and filtering or re-ranking them using an outcome verifier. However, these sequence-level strategies face severe scaling bottlenecks on sparse-success, long-horizon tasks: maintaining target output accuracy requires an overall sample budget that grows exponentially with sequence-level coverage coefficients, and any distributional error in an imperfect external reward model significantly exacerbates false candidate selection.
In contrast to post-hoc sequence selection, step-level pruning via beam search maintains the top-\(b\) promising prefixes at each intermediate token step, demonstrating compelling empirical efficiency and compute allocation in long-horizon generation. Despite widespread empirical success, a principled theoretical understanding of beam search under test-time compute constraints and imperfect verifiers has remained open. This gap is largely due to the severe token-level statistical dependencies induced by step-by-step pruning over time, as well as the misalignment between heuristic step-wise self-likelihood scores and global outcome objectives. Fundamental theoretical questions thus arise: how does beam search scale test-time compute under black-box sampling access and sparse terminal rewards, and does beam search offer provable sample complexity advantages over sequence-level inference methods?
Core Idea: By introducing an empirical frequency threshold at each generation step to prune low-probability tail actions, Confidence-Filtered Beam Search (CF-Beam) eliminates the crowding out of optimal prefixes by finite-sample noise, theoretically reducing the per-step sample complexity from quadratic coverage \(\Omega(C^\star(x)^2)\) to near-linear \(\widetilde{O}(C_{\max}^\star)\) and taming the dominant search-induced compute budget from exponential to polynomial in the reasoning horizon \(L\).
Method¶
Overall Architecture¶
CF-Beam operates under black-box sampling access to a reference policy \(\pi_{\text{ref}}\), estimating next-token transition probabilities via Monte Carlo continuations while relying on an external reward model \(\hat{r}(x,y)\) only after complete responses are generated. The decoding pipeline consists of four main phases: prefix expansion via local sampling, empirical frequency estimation and confidence filtering, cumulative log-likelihood scoring with Top-\(b\) pruning, and terminal reward selection (or reward-free self-consistent selection). Initialized with the empty beam \(\mathcal{B}_0 = \{\emptyset\}\), the algorithm iteratively draws \(N\) independent next-token samples for each prefix in \(\mathcal{B}_{t-1}\) at depth \(t \in [L]\). After computing empirical token frequencies, candidate continuations falling below an adaptive threshold \(\beta_t\) are pruned immediately; surviving prefixes are updated with cumulative empirical log-likelihood scores and sorted, retaining the top-\(b\) candidates for \(\mathcal{B}_t\). Finally, an external reward model selects the highest-scoring complete trajectory \(\hat{y}\) from \(\mathcal{B}_L\).
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input prompt x and initial beam B_0"] --> B["Prefix expansion sampling<br/>Draw N independent actions per prefix"]
B --> C["Empirical scoring and finite-sample failure<br/>Compute empirical frequencies and path scores"]
C --> D["Confidence-filtered beam search<br/>Filter tail actions below threshold beta_t"]
D --> E["Top-b pruning retaining top b prefixes<br/>Advance generation depth t toward L"]
E --> F["Decoupled regret bounds and reward-free extension<br/>Evaluate final candidates via RM or self-consistency"]
F --> G["Output optimal reasoning trajectory y_hat"]
Key Designs¶
1. Empirical scoring and finite-sample failure: exposing tail vulnerability in vanilla beam search Under black-box sampling access without direct token logits, vanilla beam search estimates action probabilities using empirical counts \(\hat{\pi}(a_t \mid s_{t-1}, x) = \frac{1}{N} \sum_{i=1}^N \mathbf{1}(a_t^{(i)} = a_t)\), defining trajectory scores as cumulative empirical log-likelihoods \(Q(s_t) = \sum_{i=1}^t \log \hat{\pi}(a_i \mid s_{i-1}, x)\). However, the token vocabulary \(\mathcal{A}\) in modern language models is vast (\(|\mathcal{A}| \geq 10^4\)), placing most tokens in a low-probability tail. Although individual tail tokens have negligible true probability, finite sampling can cause spurious tail candidates to be drawn by chance, whose single-hit empirical probability (\(1/N\)) drastically overestimates their true likelihood. Under hard top-\(b\) pruning, these amplified spurious continuations readily crowd out the true optimal prefix \(s_t^\star\). Because autoregressive pruning is irreversible, dropping \(s_t^\star\) at early steps permanently destroys the correct solution. Theorem 1 formalizes this fundamental vulnerability: on hard instances satisfying bounded token-level coverage \(C^\star(x)\), if the sample size satisfies \(N \leq (C^\star(x))^2 / 16\), vanilla beam search discards the optimal trajectory \(y^\star\) with constant probability at least 0.5. Hence, vanilla beam search fundamentally demands an \(\Omega(C^\star(x)^2)\) sample complexity to ensure survival.
2. Confidence-filtered beam search (CF-Beam): compressing coverage dependence from quadratic to near-linear To overcome the tail-crowding failure mode, CF-Beam incorporates an explicit confidence thresholding step directly following empirical estimation: a candidate action \(a_t\) observed during local sampling is retained for trajectory extension \(s_t' = s_{t-1} \oplus a_t\) if and only if its empirical frequency satisfies \(\hat{\pi}(a_t \mid s_{t-1}, x) \geq \beta_t\). In theoretical analysis, the oracle threshold is set to \(\beta_t = (1 - 1/L) / C_t^\star(x)\), where \(C_t^\star(x) = 1/\pi_{\text{ref}}(a_t^\star \mid s_{t-1}^\star, x)\) represents the inverse probability of the optimal token. For practical deployment, an empirical prefix-adaptive proxy is introduced: \(\beta_t(s_{t-1}) = \gamma \max_{a \in \mathcal{A}} \hat{\pi}(a \mid s_{t-1}, x)\) with tuning coefficient \(\gamma \in (0, 1)\) (set to 0.3 in experiments). Under the standard prefix competitiveness condition (Assumption 3, ensuring an intrinsic log-likelihood gap \(\kappa\) between the optimal path and suboptimal prefixes), Chernoff lower-tail bounds guarantee that the probability of erroneously filtering the optimal action decays exponentially in \(N\). Simultaneously, threshold filtering strictly excludes the multitude of low-probability tail tokens, suppressing the sum of competitor probabilities that could match the optimal score. Theorem 2 establishes that CF-Beam requires only \(\widetilde{O}(C_{\max}^\star)\) samples per prefix, effectively converting the sample complexity dependence on coverage from quadratic to near-linear.
3. Decoupled regret bounds and reward-free extension: controlling verifier error and polynomial horizon scaling The expected regret of CF-Beam is bounded by isolating search failure from reward estimation errors. Under Assumptions 1โ3, Theorem 2 proves: $\(\mathrm{Reg}(x) \leq L\exp\left(-\frac{N}{2C_{\max}^{\star}L^{2}}\right) + \frac{2C_{\max}^{\star}}{b}\exp\left(-\frac{\kappa^{2}N}{48C_{\max}^{\star}}\right) + \epsilon_{\mathrm{opt}}(x) + 2\sqrt{\overline{C}(x)\epsilon_{\mathrm{RM}}^{2}(x)}\)$ Here, the first two terms characterize search error \(\mathbb{P}(\mathcal{E}^c)\), capturing filtering and pruning failures respectively. Crucially, while sequence-level methods (e.g., Best-of-N and Best-of-Majority) incur search sample complexities scaling with the entire trajectory coverage \(\overline{C}(x) = \prod_{t=1}^L C_t^\star(x)\) (which grows exponentially with horizon \(L\)), CF-Beam's search failure depends only on the single-step maximum coverage \(C_{\max}^\star = \max_t C_t^\star\). The total policy query budget scales as \(\widetilde{O}(b L^3 C_{\max}^\star)\), achieving polynomial scaling in \(L\). Furthermore, for settings where external reward models are unavailable or untrustworthy, Algorithm 2 presents a reward-free self-consistent variant that selects the terminal response with maximal cumulative internal score \(Q_L(y)\). Corollary 2 proves that this reward-free variant completely decouples regret from reward error, achieving an overall query budget of \(\widetilde{O}(L b C_{\max}^\star / \kappa^2)\) that scales near-linearly with \(L\).
Loss & Training¶
As a purely inference-time test-time scaling algorithm, CF-Beam requires no gradient backpropagation or parameter updates; reference model parameters remain completely frozen throughout inference. The algorithm's computational mechanics center on adaptive inference-time query allocation and discrete selection: 1. Per-step Scoring Rule: At expansion step \(t\), candidate trajectory scores accumulate empirical log-probabilities: $\(Q(s_t) = Q(s_{t-1}) + \log \hat{\pi}(a_t \mid s_{t-1}, x) = \sum_{i=1}^t \log \left( \frac{1}{N} \sum_{j=1}^N \mathbf{1}(a_i^{(j)} = a_i) \right)\)$ 2. Filtering and Pruning Operations: The candidate prefix pool is formed via \(\mathcal{D}_t = \{s_{t-1} \oplus a_t \mid s_{t-1} \in \mathcal{B}_{t-1}, \hat{\pi}(a_t \mid s_{t-1}, x) \geq \beta_t\}\), and subsequently pruned to \(\mathcal{B}_t = \text{top-}b \{s_t' \in \mathcal{D}_t \text{ ranked by } Q(s_t')\}\). 3. Terminal Selection: Under reward-guided mode, the output is selected via \(\hat{y} = \arg\max_{y \in \mathcal{B}_L} \hat{r}(x, y)\); under self-consistent mode, it is chosen via \(\hat{y} = \arg\max_{y \in \mathcal{B}_L} Q_L(y)\). 4. Compute Accounting: The total policy query budget is strictly bounded by \(B(x) \leq L \cdot b \cdot N\), enabling flexible trade-offs between beam exploration breadth \(b\) and per-step estimation depth \(N\) under tight latency constraints.
Key Experimental Results¶
Main Results¶
To evaluate CF-Beam on real neural language models, experiments were conducted using Qwen3-1.7B-Base across 500 synthetic \(4 \times 4\) integer matrix multiplication problems. Completions sampled at temperature 1.3 were verified using AceMath-7B-RM. Beam methods used per-prefix sample size \(N=12\) and beam width \(b=2\), with Empirical CF-Beam setting \(\gamma=0.3\).
| Method | Sampling Strategy | Accuracy | Query Budget (\(\times 10^3\)) | Gain vs. Best-of-N |
|---|---|---|---|---|
| Best-of-N | Sequence-level independent sampling | 0.332 | 16.8 | Baseline (0.0%) |
| Majority Voting | Sequence-level frequency voting | 0.304 | 16.8 | -2.8% |
| Best-of-Majority | Sequence-level self-consistency + RM | 0.326 | 16.8 | -0.6% |
| Vanilla-Beam | Step-wise vanilla beam search | 0.372 | 18.6 | +4.0% |
| CF-Beam (Empirical) | Step-wise confidence-filtered beam search | 0.388 | 16.2 | +5.6% |
Ablation Study¶
On the same Qwen3-1.7B-Base matrix multiplication benchmark, the authors ablated the empirical filtering threshold coefficient \(\gamma \in \{0, 0.15, 0.3, 0.45, 0.6, 0.75, 0.9\}\) across beam widths \(b \in \{2, 4, 8\}\) with fixed \(N=12\) (where \(\gamma=0\) recovers Vanilla-Beam).
| Beam Width (\(b\)) | \(\gamma=0\) (Vanilla) | \(\gamma=0.15\) | \(\gamma=0.3\) | \(\gamma=0.45\) | \(\gamma=0.6\) | \(\gamma=0.75\) | \(\gamma=0.9\) | Note |
|---|---|---|---|---|---|---|---|---|
| \(b=2\) | 0.372 | 0.378 | 0.388 | 0.372 | 0.318 | 0.292 | 0.290 | Moderate filtering \(\gamma=0.3\) yields peak accuracy |
| \(b=4\) | 0.482 | 0.512 | 0.472 | 0.392 | 0.374 | 0.330 | 0.302 | Gentle filtering \(\gamma=0.15\) optimal for wider beams |
| \(b=8\) | 0.536 | 0.550 | 0.480 | 0.434 | 0.364 | 0.292 | 0.300 | Consistent gain over vanilla; overly harsh \(\gamma\) hurts |
Key Findings¶
- Confidence filtering improves accuracy-budget Pareto efficiency: In LLM evaluations, Empirical CF-Beam achieved higher accuracy (0.388 vs. 0.372) while using a smaller query budget (16.2k vs. 18.6k) compared to Vanilla-Beam, outperforming Best-of-N by 5.6 percentage points.
- Robustness over increasing reasoning horizons: In synthetic simulator experiments, as horizon length \(L\) increased from 2 to 40, sequence-level methods suffered catastrophic accuracy drops due to exponential coverage decay \(\overline{C}(x)\), whereas beam methods remained robust and CF-Beam consistently retained the highest accuracy.
- Peak advantages in hard, sparse-coverage regimes: When single-rollout success probability dropped from \(p=0.3\) to \(p=0.01\), tail sampling noise severely degraded vanilla beam search and sequence baselines, while CF-Beam maintained substantial accuracy gains.
Highlights & Insights¶
- First theoretical test-time scaling analysis of beam search: Resolves a long-standing open question by proving that vanilla beam search suffers a quadratic coverage lower bound \(\Omega(C^\star(x)^2)\), explaining finite-sample tail instability.
- Fundamental leap from exponential to polynomial scaling: Rigorously establishes that step-wise confidence filtering limits search error propagation to the per-step coverage \(C_{\max}^\star\) and polynomial orders of horizon \(L\), bypassing the sequence-level curse of horizon dimensionality.
- Simple and plug-and-play empirical implementation: The prefix-adaptive rule \(\beta_t(s) = \gamma \max_a \hat{\pi}(a \mid s, x)\) eliminates the need for oracle knowledge of optimal path probabilities, offering immediate deployment utility in existing LLM decoding pipelines.
Limitations & Future Work¶
- Reliance on prefix likelihood-reward alignment: The theoretical guarantees hinge on prefix competitiveness (Assumption 3); if the base model suffers from severe high-confidence hallucinations early on, the optimal prefix may be pruned before reaching the terminal reward.
- Sensitivity to hard threshold tuning: Aggressive threshold values (\(\gamma \geq 0.6\)) cause premature pruning of valid continuations; future research could explore entropy-adaptive dynamic filtering thresholds.
- Lack of step-level process verifiers: The current formulation queries verifiers only at the terminal step; extending CF-Beam to intermediate Process Reward Models (PRMs) represents an important future direction.
Related Work & Insights¶
- vs. Best-of-N (Huang et al., 2025): Best-of-N evaluates complete trajectories post-hoc, leading to query complexity scaling with path-level coverage \(\overline{C}(x)\); CF-Beam controls the dominant search term with step-level coverage \(C_{\max}^\star\) and polynomial horizon dependence.
- vs. Best-of-Majority (Di et al., 2025): Best-of-Majority performs frequency filtering at the full-sequence level, which remains costly in long-horizon contexts; CF-Beam pushes consistency filtering forward to intermediate token distributions, pruning invalid branches earlier.
- vs. Heuristic Tree Search (Feng et al., 2023): AlphaZero-style tree search approaches demand expensive Monte Carlo rollouts or trained value functions; CF-Beam provides a minimal, self-contained frequency thresholding mechanism supported by minimax regret guarantees.
Rating¶
- Novelty: โญโญโญโญโญ Establishes the first rigorous test-time scaling theory for beam search, proving polynomial horizon scaling over sequence-level baselines.
- Experimental Thoroughness: โญโญโญโญ Combines controlled synthetic simulator experiments spanning multiple difficulty/horizon settings with real LLM matrix reasoning evaluations.
- Writing Quality: โญโญโญโญโญ Exceptionally rigorous mathematical proofs coupled with clear intuitive motivations and transparent algorithmic trade-offs.
- Value: โญโญโญโญโญ Delivers critical theoretical foundations and practical design guidelines for test-time compute scaling in modern reasoning models.