PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Gal Dalal, Assaf Hallak, Gal Chechik, Yftah Ziser

arXiv:2603.15377v2cs.LGcs.AI

TL;DR

Wider beam search is often assumed to help, but when it stops helping with output quality has not been rigorously examined. The paper uses Extreme Value Theory to derive a scorer-dependent useful-width threshold. Perplexity scoring yields ˆk = 1 with no benefit, while PRM scoring yields ˆk ≥4 and gains up to 8.9 percentage points.

  • Problem

    The assumption that a reasonable scoring signal can drive wider search has not been rigorously examined for its effect on output quality.

    Source: §1 · p. 1

  • Method

    The paper uses Extreme Value Theory to model overestimation from selecting among noisy scores and derive a maximum useful beam width based on scorer signal-to-noise ratio.

    Source: §1 · p. 2, §3.3 · p. 4

  • Results

    ˆk = 1 for perplexity scoring, which provides zero benefit, while PRM scoring has ˆk ≥4 and gains up to 8.9 percentage points.

    Source: §7 · p. 8

  • Takeaways & Limitations

    The scorer’s signal-to-noise ratio is the key quantity governing beam-width selection.

    Source: §1 · p. 2

    Evaluation is limited to 7B-parameter models and beam widths up to k = 4, with a single temperature of T = 0.7 throughout.

    Source: Limitations · pp. 8–9

Abstract

from arXiv · show

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 \emph{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 $(\Delta/\sigma)^2$, where $\Delta > 0$ is the quality advantage of correct paths over incorrect ones and $\sigma$ 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.

1 Introduction

The introduction questions the assumption that wider search helps whenever a reasonable scorer is available, and frames scorer quality as central to choosing beam width. It presents an overestimation-based threshold and contrasts perplexity- with PRM-guided search.

1 Introduction

  • The introduction asks whether perplexity is informative enough to score intermediate reasoning steps or instead favors fluent but unfaithful steps.Perplexity is presented as a cheap, training-free signal available for autoregressive models, in contrast to specialized PRMs.Source: §1 · p. 1
  • Perplexity scoring yields no benefit at any beam width, while PRM scoring yields meaningful gains across three model families and ten reasoning domains.Figure 1 shows flat perplexity curves with ˆk = 1 and PRM curves rising through beam width 4 with ˆk ≥4.Source: Figure 1 · p. 2, §1 · p. 2
  • Extreme-value overestimation bias grows with scorer noise, and the predicted maximum useful beam width depends on the scorer’s signal-to-noise ratio.Beyond ˆk, the bias exceeds the quality gap and search degrades performance, a phenomenon termed reward inversion.Source: §1 · p. 2
  • The authors propose score margins and pilot-run comparisons as diagnostics for whether a scorer can support wider search, targeting output quality rather than inference speed.They also argue that investing in scorer quality is more effective than widening the beam.Source: §1 · p. 2

2 Background and Related Work

Prior work covers beam-width efficiency, process supervision, inference-time search, and overestimation, while this paper focuses on when wider search degrades output quality.

2.1 Beam Width Selection

  • Earlier beam-width methods treat width as an efficiency parameter; this work instead asks when adding candidates degrades output quality.Prior approaches include adaptive pruning for translation and dynamic-width speculative beam decoding for LLMs.Source: §2.1 · p. 2

2.2 Process Supervision for LLM Reasoning

  • Process reward models score intermediate reasoning steps, while related work also identifies reward hacking, distribution shift, and false-positive ceilings.The cited literature includes methods intended to reduce PRM annotation costs and findings on over-optimistic estimates in beam search.Source: §2.2 · pp. 2–3

2.3 Inference-Time Search

  • Inference-time search can improve performance and cost-performance trade-offs, but the cited work does not characterize when additional search stops helping.Search strategies may depend on the policy model, PRM, and problem difficulty.Source: §2.3 · p. 3

2.4 Overestimation Bias and Reward Overoptimization

  • Prior work connects maximization over noisy estimates to overestimation in Q-learning and tree search, while reward overoptimization identifies a critical candidate count for degradation.The paper relates best-of-N reward overoptimization to a depth-1, width-N special case of beam search.Source: §2.4 · p. 3

3 Theoretical Framework: Overestimation Bias in Beam Selection

The framework treats wider beam search as selection among noisy candidate scores: maximization inflates incorrect-path scores, yielding a scorer-dependent threshold beyond which widening may hurt. It formalizes a candidate-pool threshold, with beam-width implications tied to the expansion scheme.

3.1 Setup and Notation

  • At each selection step, k beams each generate k continuations, producing n=k² candidates; candidates are independently sampled and scored, and the highest-scoring candidate is selected.The symmetric expansion is a design choice; the theory operates on pool size n regardless of how it is produced.Source: §3.1 · p. 3

3.2 Assumptions

  • The analysis assumes Gaussian noise with common variance and one correct-type candidate among n candidates, with quality advantage ∆>0.The one-correct-candidate setup is a worst case; multiple correct paths make survival more likely.Source: §3.2 · p. 4

3.3 Overestimation Bias from Beam Selection

The correct candidate’s expected score is simply

  • Incorrect candidates receive a maximization bonus of approximately σ√(2 log(n−1)), while the single correct candidate’s expected score remains µc.The asymmetry is structural: the incorrect candidates are selected as a maximum, whereas the correct candidate is a single draw.Source: The correct candidate’s expected score… · p. 4
  • The bound tests whether any incorrect candidate outscores the correct one, although eliminating the correct path requires at least k incorrect candidates to outrank it.Together with the single-correct-path assumption, this overestimates failure probability, so k_hat is a lower bound on the true safe width.Source: The correct candidate’s expected score… · p. 4

3.4 Sub-Optimal Selection Probability

  • The sub-optimal selection bound depends on ∆eff/σ, where ∆eff = ∆−B(σ,n−1); the bound is pessimistic and k_hat lower-bounds the true safe width.High scorer noise enlarges the bias and shrinks ∆eff, while low noise preserves more of the true quality gap.Source: §3.4 · p. 5

3.5 When Does Search Help? A Necessary Condition

  • Beam search can improve over single-sample decoding only while the scorer’s quality gap exceeds its overestimation bias; beyond the threshold, performance may degrade.The failure occurs when maximization-inflated scores cause incorrect paths to be selected.Source: §3.5 · p. 5
  • Because the maximum useful candidate pool grows exponentially with (∆/σ)^2, poor SNR gives k_hat = 1, while moderate SNR can support k_hat ≥ 4.With the experimental expansion scheme n=k², the pool-size threshold maps to beam width; other expansion strategies yield a different mapping.Source: §3.5 · p. 5

4 Experiments

The experiments compare perplexity and PRM scoring across three policy models and ten reasoning domains. Perplexity provides no benefit or degrades at wider beams, while PRM improves performance, consistent with different predicted maximum useful widths.

4.1 Setup

  • Evaluation used MR-BEN’s 5,975 questions across 10 subjects, three policy models, and perplexity or MathShepherd PRM scoring.Beam widths were k ∈ {1, 2, 3, 4}; each beam generated k continuations, for n = k2 candidates at each depth.Source: §4.1 · pp. 5–6

4.2 Main Results

  • Perplexity macro success rate was flat for Qwen (±0.1 points) and fell for Llama (−5.4 points) and Mistral (−3.9 points) at k=4.The model ranking Qwen > Llama > Mistral remained stable across beam widths.Source: §4.2 · p. 6
  • At k=4, PRM macro success rate gains were +8.9 points for Mistral (42.3% to 51.2%), +6.2 for Llama (59.2% to 65.4%), and +3.4 for Qwen (71.7% to 75.1%).The models and search algorithm were unchanged when replacing perplexity with PRM scoring.Source: §4.2 · p. 6

4.3 Interpreting Results Through the Maximum Useful Beam Width

  • Perplexity had predicted maximum useful width k-hat = 1 for all three models, while PRM had k-hat ≥ 4 and all three peaked at k=4.Mistral dipped at k=3 before recovering at k=4; the authors attribute this likely to higher variance rather than a true optimum near k=2.Source: §4.3 · p. 6

5 Case Study: Diagnosing Reward Inversion

The case study traces perplexity-guided beam search failures to reward inversion: wider search can select paths that score better but are worse in quality. Small score margins provide a diagnostic signal for this unreliable selection.

5 Case Study: Diagnosing Reward Inversion

  • On high_school_biology, Mistral scored 59.7% at k=4 with perplexity, versus 63.0% with single-sample decoding despite four times the search effort.The case study traces beam behavior for Mistral-7B-Instruct-v0.3 in this domain.Source: §5 · p. 6

5.1 Reward Inversion at the Trace Level

  • In 25 cases where k=1 was correct but k=4 was wrong, the wider beam consistently selected paths with higher reward, or lower perplexity.One 12-candidate selection favored incorrect path C over correct path A by a reward margin of 0.009.Source: §5.1 · p. 6

5.2 Score Margins as a Diagnostic

  • Across 2,770 selections, 44.3% had top-two reward margins below 0.1, indicating near-random selection that can be detected without ground-truth labels.The authors suggest inspecting score margins on a small pilot run; consistently small margins indicate a likely low maximum useful width.Source: §5.2 · p. 7

6 Discussion

The discussion treats maximum useful beam width as a design parameter governed by scorer signal-to-noise ratio. It recommends diagnosing scorer reliability and improving the scorer rather than simply widening the beam, and outlines an unvalidated bias correction.

6.1 The Optimal Beam Width as a Design Parameter

  • The predicted maximum useful width grows exponentially with the scorer’s squared signal-to-noise ratio, and even strong scorers have a finite useful range.At k=1, there is no maximization and therefore no overestimation bias.Source: §6.1 · p. 7

6.2 Practical Guidance

  • Consistently small score margins suggest a low maximum useful width, though score dispersion is only a rough proxy for scorer unreliability.The dispersion reflects both genuine quality variation and scorer noise, not noise alone.Source: §6.2 · p. 7
  • A small validation pilot comparing k=2 with k=1 can test whether wider search helps; the authors recommend investing in scorer quality over beam width.With ground-truth labels, the separation between correct- and incorrect-candidate score distributions can estimate the signal-to-noise ratio.Source: §6.2 · pp. 7–8

6.3 Toward Bias-Corrected Beam Search

  • The authors propose subtracting an estimated overestimation bias from the best-of-n score, but leave empirical validation for future work.The proposal estimates scorer noise online from score variance across candidates at each selection step.Source: §6.3 · p. 8

7 Conclusion

The analysis predicts a scorer-dependent maximum useful beam width: widening beyond it can degrade performance. The empirical results and diagnostic indicators support choosing width according to scorer quality.

7 Conclusion

  • Beam selection introduces overestimation proportional to scorer noise, with predicted candidate-pool threshold n-hat = 1 + exp(Δ^2/2σ^2) and corresponding beam width k-hat = floor(sqrt(n-hat)).Beyond k-hat, wider search degrades performance.Source: §7 · p. 8
  • Perplexity scoring yields zero benefit at any tested beam width, while PRM scoring with k-hat ≥ 4 yields gains of up to 8.9 percentage points.These findings span three models and ten domains.Source: §7 · p. 8
  • Score margins and pilot-run comparisons can help assess whether a scorer supports wider search, although Δ and σ are not directly observable.Source: §7 · p. 8

Limitations

The analysis and experiments have bounded scope: the theory uses a two-class quality model, evaluations cover 7B models and widths up to four at one temperature, and only perplexity is evaluated among training-free signals.

Limitations

  • The two-class model reduces candidate quality to a binary correct/incorrect split with one gap, making the bound conservative relative to multiple correct candidates or a quality continuum.Source: Limitations · p. 8
  • Experiments cover only 7B models and beam widths up to k = 4, so the PRM turning point has not been empirically located; all runs use T = 0.7.Temperature may affect candidate diversity and effective independence, modulating the relation between pool size and overestimation bias.Source: Limitations · pp. 8–9
  • Among training-free scoring signals, the empirical comparison evaluates only perplexity, leaving other intrinsic signals unevaluated.The paper identifies entropy-based self-certainty and Markovian reward adjustments as alternatives for future comparison.Source: Limitations · p. 9

Ethical Considerations

The paper uses publicly available models and benchmarks and identifies computational cost as its primary ethical consideration.

Ethical Considerations

  • Beam search at width k requires O(k^2) scorer evaluations per step; identifying when wider search is wasteful can help avoid unnecessary computation.Source: Ethical Considerations · p. 9

A Proof of Lemma 3.1

The proof models incorrect-candidate scores as independent Gaussian draws and uses extreme-value theory to approximate their maximum. The correct candidate is a single draw, so its expected score has no max-induced bias.

A Proof of Lemma 3.1

  • The maximum of n − 1 independent Gaussian draws converges to a Gumbel distribution, whose location and scale parameters yield the expected maximum used in equations (2)–(3).The approximation has relative error below 2% for n ≥ 4.Source: A Proof of Lemma 3.1 · p. 11
  • Under Assumption 2, incorrect candidates have scores formed from their mean quality plus independent noise, whereas the correct candidate is one draw with expected score μc.Consequently, the correct candidate has no max-induced bias.Source: A Proof of Lemma 3.1 · p. 11
  • For large n, the Gaussian maximum approximation uses sqrt(2 log(n − 1)) − 1/2, with the Euler–Mascheroni correction becoming negligible.Source: A Proof of Lemma 3.1 · p. 11

B Proof of Theorem 3.2

The proof bounds the chance that an incorrect path outranks the correct path, showing how increasing candidate counts weaken the bound through overestimation bias. The appendix also provides scorer-specific beam-width plots, implementation settings, and a biology case where beam search underperforms and selected paths have higher rewards despite being incorrect.

B Proof of Theorem 3.2

  • The proof bounds the probability that the highest-reward incorrect path exceeds the correct path by applying Cantelli's inequality to Z=max_j R_j−R_c.The proof defines Z as the difference between the maximum incorrect reward and the correct-path reward.Source: B Proof of Theorem 3.2 · p. 11
  • The bound depends on (Δ_eff/σ)^2; as candidate count grows, overestimation bias B increases, Δ_eff shrinks, and the bound moves toward 1.At n=hat n, Δ_eff=0 and the bound becomes vacuous.Source: B Proof of Theorem 3.2 · p. 11

C.1 Perplexity Scoring

  • Figure 4 plots per-subject success rate against beam width for Qwen2.5-7B-Instruct with perplexity scoring.Source: Figure 4 · p. 12
  • Figure 5 plots per-subject success rate against beam width for Llama-3.1-8B-Instruct with perplexity scoring.Source: Figure 5 · p. 12

C.2 PRM Scoring

D Implementation Details

  • Experiments use beam widths 1–4, an equal number of actions, a maximum depth of 24 steps, and temperature 0.7.Source: D Implementation Details · p. 14
  • Perplexity is computed over the full sequence at each depth, while PRM selection uses the most recent step's score and correctness probability at the last step tag.Source: D Implementation Details · p. 14

E Additional Case Study Figures

  • On high_school_biology, beam search underperforms single-sample decoding despite evaluating 16 candidates per step, and k=4 selects incorrect paths with higher rewards than correct k=1 paths.Source: Figure 10 · p. 14, Figure 11 · p. 15
Loading 2603.15377v2…