The paper provides theoretical guarantees for as a method for LLM reasoning. It shows that vanilla beam search requires sample complexity quadratic in a token-level coverage coefficient for the optimal response to survive, and proposes Confidence-Filtered Beam Search (CF-Beam) that filters low-confidence tokens before beam selection, reducing this dependence to nearly linear under prefix competitiveness. The analysis also bounds regret by rare failure events plus reward estimation error, and shows beam search's coverage coefficient grows polynomially in horizon length, while Best-of-N and Best-of-Majority can have exponential coverage. This matters because it explains why beam search is more robust on hard and long-horizon reasoning tasks.
Confidence filtering gives beam search stronger test-time scaling guarantees
The authors prove that a modified beam search can reduce its dependence on token-level coverage from quadratic to nearly linear under specified assumptions.
Top University
Qijia He · Yu Huang · Yuan Cheng · Yuxin Chen · Yingbin Liang
The Ohio State University · University of Pennsylvania · National University of Singapore
Research Digest··2 min read
Thread:Decoding as Optimization
In one line
Confidence-filtered beam search reduces test-time sample complexity from quadratic to nearly linear and provably outperforms sequence-level inference.
Before you read this
Three ideas this paper builds ontest-time scalingAllocating extra computation during inference to improve output quality.121 papers →beam searchA search algorithm that expands multiple promising candidates simultaneously to balance generation quality and computational cost.7 papers →large language modelA neural network trained on massive text corpora to generate coherent text and perform diverse language tasks.334 papers →
Read it as
He et al. analyze beam search when token probabilities must be estimated from sampled continuations and an external reward model scores only completed responses.
The authors model test-time reasoning as a sequential search in which candidate responses are expanded token by token.
How it works
before and afterThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.