Research map / Large language models / Reasoning and chain of thought

Provable Test-Time Scaling for Beam Search in LLM Reasoning

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves sample-complexity and regret guarantees for beam search with log-likelihood pruning and proposes confidence-filtered beam search (CF-Beam), which reduces the required per-prefix sample size from quadratic to near-linear in token-level coverage and avoids exponential horizon dependence of Best-of-N and Best-of-Majority.

Problem

Beam search is widely used for LLM test-time scaling, but its theoretical test-time scaling guarantees are unknown; likelihood-based pruning with sampled token probabilities can eliminate the optimal prefix, and sequence-level methods have coverage terms exponential in the horizon.

Approach

Vanilla beam search with sampled log-likelihood scores can crowd out the optimal prefix; filtering out low-frequency sampled tokens below a coverage-scaled threshold before top-b pruning (CF-Beam) reduces the sample requirement to near-linear in token-level coverage, and the regret depends on a polynomial-in-L search term rather than the product of per-token coverages.

Key results

• Vanilla beam search requires per-prefix samples of order C*^2 (lower bound) to keep the optimal response, whereas CF-Beam needs N = Õ(C*_max) for fixed L, kappa, delta.
• CF-Beam regret is bounded by a search error (filtering + pruning terms) plus reward-model error; the reward-free variant removes the reward error term entirely.
• Numerical simulator experiments show CF-Beam has the highest accuracy on hard instances (p=0.01) and remains robust as horizon grows at per-step success 0.8, while sequence-level baselines degrade.

Surprising findings

• Vanilla beam search can fail with constant probability even with large beam widths unless sample size scales quadratically in token-level coverage.
• Without the prefix competitiveness assumption, beam search with width 1 prunes the optimal trajectory with probability at least 3/4 for every sample size.

Limitations

• Advantage relies on prefix competitiveness between likelihood and final reward; otherwise optimal prefixes may be pruned.
• Oracle threshold requires unknown token-level coverage; the empirical variant is heuristic.
• Experiments use a synthetic simulator, with only a pretrained-LLM check deferred to appendix; bounds count token queries, not wall-clock cost.

Experimental setup

Benchmarks: synthetic LLM simulator (per-rollout success p in {0.01,0.05,0.3})

Metrics: accuracy of identifying optimal response regret

Baselines: Vanilla beam search Best-of-N Majority Voting Best-of-Majority

Builds on: Best-of-Majority Best-of-N Vanilla beam search

Closest papers by meaning

• A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.91)
• Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling (NeurIPS 2025 · similarity 0.90)
• Bag of Tricks for Inference-time Computation of LLM Reasoning (NeurIPS 2025 · similarity 0.90)
• Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs (ICML 2026 · similarity 0.90)
• Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving (ICLR 2025 · similarity 0.90)
• Consilience for Verifier-Free Test-Time Scaling (NeurIPS 2026 · similarity 0.89)