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

• URL: http://arxiv.org/abs/2603.15377v2
• Date: Tue, 17 Mar 2026 15:04:49 GMT
• Title: More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search
• Abstract summary: We present an analysis, grounded in Extreme Value Theory, on beam selection over noisy scorer outputs.<n>We derive a maximum useful beam width $hatk$ beyond which search degrades performance.<n>Our analysis identifies the scorer's signal-to-noise ratio as the key quantity governing beam width selection.
• Score: 40.90281862767655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 \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 $(Δ/σ)^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.

Related papers

• Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
  We consider a multi-objective bandit problem where, at each round, the agent selects a slate of $k$ arms and observes their $d$-dimensional reward vectors under semi-bandit feedback.<n>We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an $$-approximate hypervolume regret with respect to the best size-$k$ subset achievable in hindsight.<n>We establish a gap-free regret bound $tildeO(dsqrtnkT)$ that holds on every instance, together with a gap
  arXiv  Detail & Related papers  (2026-07-28T21:10:39Z)
• SHEAF: Self-profiled Hardness Estimation from Answer-set Flux for Predicting Query Hardness in Graph-based ANN Search [0.9179857807576733]
  This paper presents a new measure, namely Self-profiled Hardness Estimation from Answer-set Flux (SHEAF), which represents a query's hardness as how much its own top$k$ answer set changes between two shallow probe widths.<n>We develop a fixed-probe evaluation protocol that scores each measure over all queries with an observed minimum sufficient beam.
  arXiv  Detail & Related papers  (2026-07-14T00:20:13Z)
• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation.<n>We analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining.
  arXiv  Detail & Related papers  (2026-06-28T05:07:27Z)
• The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection [1.2647816797166167]
  We introduce Bits-over-Random (BoR), a measure of retrieval selectivity that reveals when high success rates mask random-level performance.<n>We show that when the expected coverage ratio $left(fracK cdot barR_qNright)$ exceeds 3-5, the baseline dominates and selectivity collapses.<n>These findings suggest reporting BoR alongside traditional metrics and reconsidering depth choices when additional retrieval provides negligible selectivity gains.
  arXiv  Detail & Related papers  (2026-05-14T00:19:57Z)
• GridProbe: Posterior-Probing for Adaptive Test-Time Compute in Long-Video VLMs [3.9266376632068485]
  GridProbe is an efficient training-free posterior-probing inference paradigm.<n>It scores evidence in answer space using a frozen VLM's own reasoning.<n>It selects question-relevant frames adaptively, resulting in sub-quadratic attention cost with little to no accuracy loss.
  arXiv  Detail & Related papers  (2026-05-11T15:57:46Z)
• Diffusion-Based Generative Priors for Efficient Beam Alignment in Directional Networks [2.1326442458534403]
  Beam alignment is a key challenge in directional mmWave and THz systems, where narrow beams require accurate yet low-overhead training.<n>We recast beam alignment as a generative task and propose a conditional diffusion model that learns a probabilistic beam prior to compact geometric and multipath features.
  arXiv  Detail & Related papers  (2026-03-30T09:21:03Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• Best-of-Majority: Minimax-Optimal Strategy for Pass@$k$ Inference Scaling [54.50689440956967]
  LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of-N (BoN)<n>We propose Best-of-Majority (BoM) with a pivotal step that restricts the candidates to the responses with high frequency in the $N$ samples before selecting the top-$k$ rewards.<n>Unlike majority voting and BoN, BoM has a key advantage: unlike majority voting and BoN, its performance does not degrade when increasing $N$.
  arXiv  Detail & Related papers  (2025-10-03T17:35:45Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  We investigate the high-dimensional sparse linear bandits problem in a data-poor regime.<n>We show novel offline statistical guarantees of the lasso estimator for the linear model.<n>We propose a meta-algorithm based on corralling that does not need knowledge of optimal sparsity parameter $k$ at minimal cost to regret.
  arXiv  Detail & Related papers  (2024-10-26T01:42:03Z)
• Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
  We study the problem of estimating the score function of an unknown probability distribution $rho*$ from $n$ independent and identically distributed observations in $d$ dimensions. We show that a regularized score estimator based on a Gaussian kernel attains this rate, shown optimal by a matching minimax lower bound.
  arXiv  Detail & Related papers  (2024-02-12T16:17:40Z)
• (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum [7.095058159492494]
  Heavy ball momentum (SHB) is commonly used to train machine learning models, and often provides empirical results over gradient descent.<n>We show that SHB can attain an accelerated mini-batch size when the mini-batch size is larger than a threshold $b*$ that on the condition number $kappa2$.
  arXiv  Detail & Related papers  (2024-01-12T18:17:28Z)
• Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
  We introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of Large Language Model (LLM) We propose a decoding algorithm integrating the self-evaluation guidance via beam search. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34%$, $9.56%$, and $5.46%$ on the GSM8K, AQuA, and StrategyQA.
  arXiv  Detail & Related papers  (2023-05-01T02:37:59Z)
• UB3: Best Beam Identification in Millimeter Wave Systems via Pure Exploration Unimodal Bandits [7.253481390411171]
  We develop an algorithm that exploits the unimodal structure of the received signal strengths of the beams to identify the best beam in a finite time. Our algorithm is named Unimodal Bandit for Best Beam (UB3) and identifies the best beam with a high probability in a few rounds.
  arXiv  Detail & Related papers  (2022-12-26T09:24:22Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Beam Search: Faster and Monotonic [15.20931404997906]
  We show how to make beam search monotonic; that is, we provide a new variant that guarantees non-increasing solution cost as the beam width is increased. We also show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs.
  arXiv  Detail & Related papers  (2022-04-06T16:40:13Z)
• Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
  We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-free algorithm. We provide a theoretical analysis of the failure probability of OD-LinBAI.
  arXiv  Detail & Related papers  (2021-05-27T09:19:10Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)

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.