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

arXiv: https://arxiv.org/abs/2603.15377 · HTML: https://mlsanity.com/paper/2603.15377/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 16 Mar 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 12 of 12)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Beam Search Strategies for Neural Machine Translation](https://mlsanity.com/paper/1702.01806/) (2017)
- [Scalable Best-of-N Selection for Large Language Models via Self-Certainty](https://mlsanity.com/paper/2502.18581/) (2025)
- [Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling](https://mlsanity.com/paper/2502.06703/) (2025)
- [LLM Reasoners: New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Models](https://mlsanity.com/paper/2404.05221/) (2024)
- [A Survey of Process Reward Models: From Outcome Signals to Process Supervisions for Large Language Models](https://mlsanity.com/paper/2510.08049/) (2025)

## Built on by (most cited first, 3 of 3)

- [Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck](https://mlsanity.com/paper/2608.18931/) (2026)
- [Shattering the Autoregressive Curse: Dynamic Epistemic Entropy Orchestrated Erasable Reinforcement Learning for LLMs](https://mlsanity.com/paper/2606.17735/) (2026)
- [Strategic Self-Consistency](https://mlsanity.com/paper/2609.30352/) (2026)

## Abstract (arXiv)

Wider beam search should improve LLM reasoning, but when should you stop widening? Prior work on beam width selection has focused on inference efficiency citepqin2025dsbd, 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 hatk beyond which search degrades performance. This critical width depends on the signal-to-noise ratio of the scorer: hatk grows exponentially with (Delta/σ)2, where Delta > 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 hatk = 1: search provides no benefit at any width tested. PRM scoring, with lower noise, yields hatk ≥ 4, with gains of up to 8.9 percentage points. The same model, the same algorithm, but different scorers place hatk 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.