More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search

Gal Dalal; Assaf Hallak; Gal Chechik; Yftah Ziser

cs.LGMar 16, 2026

More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search

Authors: Gal Dalal, Assaf Hallak, Gal Chechik, Yftah Ziser

Organizations: NVIDIA Research · Bar-Ilan University · University of Groningen

Abstract

Wider beam search should improve LLM reasoning, but when should you stop widening? Prior work on beam width selection has focused on inference efficiency \citep{qin2025dsbd, freitag2017beam}, without analyzing whether wider search can hurt output quality. We present an analysis, grounded in Extreme Value Theory, that answers this question. Beam selection over noisy scorer outputs introduces a systematic overestimation bias that grows with the candidate pool size, and we derive a maximum useful beam width $\hat{k}$ beyond which search degrades performance. This critical width depends on the signal-to-noise ratio of the scorer: $\hat{k}$ grows exponentially with $(Δ/σ)^2$ , where $Δ> 0$ is the quality advantage of correct paths over incorrect ones and $σ$ is the scorer noise. We validate this theory by comparing perplexity-guided and PRM-guided beam search across three 7B-parameter models and ten domains on MR-BEN (5,975 questions). Perplexity scoring, with its high noise, yields $\hat{k} = 1$ : search provides no benefit at any width tested. PRM scoring, with lower noise, yields $\hat{k} \geq 4$ , with gains of up to 8.9 percentage points. The same model, the same algorithm, but different scorers place $\hat{k}$ at opposite ends of the beam width range. Our analysis identifies the scorer's signal-to-noise ratio as the key quantity governing beam width selection, and we propose diagnostic indicators for choosing the beam width in practice.

Figures & tables

Figure 1: Per-model comparison of perplexity (gray) vs. PRM (green) scoring across beam widths. The two scorers place the predicted maximum useful beam width

\hat{k}

at opposite ends of the range: perplexity curves are flat (

\hat{k}=1

), while PRM curves rise through beam width 4 (

\hat{k}\geq 4

), illustrating how scorer quality determines the optimal beam width.

Model	$k=1$	$k=2$	$k=3$	$k=4$	$\Delta$ ( $k$ =4 $-$ $k$ =1)
Qwen	71.3 $\pm$ 1.0	71.1 $\pm$ 1.0	71.2 $\pm$ 1.1	71.4 $\pm$ 1.5	+0.1
Llama	59.7 $\pm$ 1.3	58.4 $\pm$ 1.5	58.5 $\pm$ 2.1	54.3 $\pm$ 3.4	$-$ 5.4
Mistral	42.4 $\pm$ 1.6	42.0 $\pm$ 1.7	41.0 $\pm$ 2.1	38.5 $\pm$ 2.7	$-$ 3.9

Table 1: Perplexity-scored beam search: Macro success rate (%) by model and beam width. Values are mean

\pm

standard error across subjects and seeds.

Model	$k=1$	$k=2$	$k=3$	$k=4$	$\Delta$ (best $-$ $k$ =1)
Qwen	71.7 $\pm$ 1.2	73.8 $\pm$ 1.3	73.9 $\pm$ 1.4	75.1 $\pm$ 1.3	+3.4
Llama	59.2 $\pm$ 1.7	63.4 $\pm$ 1.8	64.7 $\pm$ 1.8	65.4 $\pm$ 2.4	+6.2
Mistral	42.3 $\pm$ 2.7	50.8 $\pm$ 3.3	47.9 $\pm$ 3.6	51.2 $\pm$ 3.7	+8.9

Table 2: PRM-scored beam search: Macro success rate (%) by model and beam width. Values are mean

\pm

standard error across subjects and seeds.

Figure 2: Per-model change from

k

=1 by scorer. Hatched bars indicate negative

\Delta

. The PRM unlocks search benefits where perplexity cannot.

Figure 3: Reward margin distribution for perplexity-scored beam selections. The peak near zero confirms that 44% of selections have negligible margins, signaling that the scorer cannot support wider search.

Problem	$k=1$	Correct	$k=4$	Correct
cf68a215	$-6.71$	✓	$-2.84$	✗
c1eacc33	$-4.65$	✓	$-2.19$	✗
5c9182fd	$-3.70$	✓	$-2.53$	✗
681201fd	$-4.49$	✓	$-2.82$	✗

Table 3: Reward inversion:

k

=4 selects higher-scoring but incorrect paths.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Per-subject success rate vs. beam width for Qwen2.5-7B-Instruct with perplexity scoring.

Figure 5: Per-subject success rate vs. beam width for Llama-3.1-8B-Instruct with perplexity scoring.

Figure 6: Per-subject success rate vs. beam width for Mistral-7B-Instruct-v0.3 with perplexity scoring.

Figure 7: Per-subject success rate vs. beam width for Qwen2.5-7B-Instruct with PRM scoring.

Figure 8: Per-subject success rate vs. beam width for Llama-3.1-8B-Instruct with PRM scoring.

Figure 9: Per-subject success rate vs. beam width for Mistral-7B-Instruct-v0.3 with PRM scoring.

Figure 10: Accuracy: single-sample (

k

=1) vs. beam (

k

=4) on high_school_biology . Beam search underperforms despite evaluating

k^{2}=16

candidates per step.

Figure 11: Reward inversion: incorrect paths selected by

k

=4 have higher rewards than correct paths from

k

=1.

Inference-Time Search

Inference-time search uses extra computation at deployment to explore, score, and select candidate reasoning paths or actions without retraining a model.

See all 105 papers

Provable Test-Time Scaling for Beam Search in LLM Reasoning
Sep 29, 2026Qijia He, Yu Huang, Yuan Cheng +2Long-Horizon LLM Reasoning Inference-Time Search
The Ohio State University · University of Pennsylvania · National University of Singapore
Thought-Level Beam Search for Reasoning
Aug 8, 2026Lijie Yang, Hongyin Luo, Jiawei Zhao +2Inference-Time Search Efficient Language Model Reasoning
Princeton University · MIT CSAIL · Meta AI
Overwhelmed by Choice: Studying LLM Decision Making at Scale
Sep 26, 2026Yu-Chi Lin, Aryan Seth, Anshul Aravind +4LLM Evaluation LLM Decision-Making
University of California, Los Angeles · University of Cincinnati

Sep 29, 2026J/K move · Enter open · S save

Provable Test-Time Scaling for Beam Search in LLM Reasoning

Qijia He, Yu Huang, Yuan Cheng, Yuxin Chen+1

The Ohio State University · University of Pennsylvania · National University of Singapore

Long-Horizon LLM Reasoning Inference-Time Search Test-Time Scaling

Open paper AskPDF arXiv

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^\star(x)^2)

samples are required for the optimal response to survive, where

C^\star(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.

Abstract

Inference-Time Search

Explore similar work

Provable Test-Time Scaling for Beam Search in LLM Reasoning

Thought-Level Beam Search for Reasoning

Overwhelmed by Choice: Studying LLM Decision Making at Scale