# Provable Test-Time Scaling for Beam Search in LLM Reasoning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 32 of its 47 references that are in the map.
- First posted on arXiv 29 Sep 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, 30 of 32)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [Learning to Reason without External Rewards](https://mlsanity.com/paper/2505.19590/) (2025)
- [Universal Self-Consistency for Large Language Model Generation](https://mlsanity.com/paper/2311.17311/) (2023)
- [Scalable Best-of-N Selection for Large Language Models via Self-Certainty](https://mlsanity.com/paper/2502.18581/) (2025)
- [Theoretical guarantees on the best-of-n alignment policy](https://mlsanity.com/paper/2401.01879/) (2024)
- [Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs](https://mlsanity.com/paper/2305.11860/) (2023)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Does Thinking More always Help? Mirage of Test-Time Scaling in Reasoning Models](https://mlsanity.com/paper/2506.04210/) (2025)
- [Evaluation of Best-of-N Sampling Strategies for Language Model Alignment](https://mlsanity.com/paper/2502.12668/) (2025)
- [Trust, But Verify: A Self-Verification Approach to Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2505.13445/) (2025)
- [ReVISE: Learning to Refine at Test-Time via Intrinsic Self-Verification](https://mlsanity.com/paper/2502.14565/) (2025)
- [Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods](https://mlsanity.com/paper/2408.14511/) (2024)
- [Deductive Beam Search: Decoding Deducible Rationale for Chain-of-Thought Reasoning](https://mlsanity.com/paper/2401.17686/) (2024)
- [Efficient Process Reward Model Training via Active Learning](https://mlsanity.com/paper/2504.10559/) (2025)
- [Certified Self-Consistency: Statistical Guarantees and Test-Time Training for Reliable Reasoning in LLMs](https://mlsanity.com/paper/2510.17472/) (2025)
- [Reward Modeling from Natural Language Human Feedback](https://mlsanity.com/paper/2601.07349/) (2026)
- [Scaling Flaws of Verifier-Guided Search in Mathematical Reasoning](https://mlsanity.com/paper/2502.00271/) (2025)
- [Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling](https://mlsanity.com/paper/2510.03199/) (2025)
- [Optimal Self-Consistency for Efficient Reasoning with Large Language Models](https://mlsanity.com/paper/2511.12309/) (2025)
- [Guaranteed Generation from Large Language Models](https://mlsanity.com/paper/2410.06716/) (2024)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [Theoretical Modeling of Large Language Model Self-Improvement Training Dynamics Through Solver-Verifier Gap](https://mlsanity.com/paper/2507.00075/) (2025)
- [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025)

## Abstract (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 Omega(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.