Provable test-time scaling: confidence-filtered beam search for LLM reasoning

A theoretical foundation for test-time reasoning: proving vanilla beam search sample bounds and establishing polynomial regret scaling over long horizons via CF-Beam.

Primary source: arXiv:2609.38672: https://arxiv.org/abs/2609.38672

What’s new: Test-time compute scaling has become standard practice for frontier reasoning models, but theoretical guarantees on search efficiency remain sparse. In Provable Test-Time Scaling for Beam Search in LLM Reasoning (arXiv:2609.38672, accepted to NeurIPS 2026), He et al. prove that standard beam search sample complexity scales quadratically with token-level coverage, $\Omega(C^\star(x)^2)$.

To resolve this bottleneck, they introduce Confidence-Filtered Beam Search (CF-Beam), which uses a confidence thresholding mechanism to filter candidate trajectories. CF-Beam reduces the coverage dependence from quadratic to near-linear. The authors prove that CF-Beam’s regret scales polynomially with the reasoning horizon $L$, in contrast to Best-of-N sampling where search terms scale exponentially with sequence length.

Why it matters: As reasoning models generate multi-thousand-token thought traces, naive sampling strategies waste immense compute or succumb to reward hacking. Providing rigorous regret bounds and sample-complexity guarantees gives engineering teams a principled framework for budgeting inference tokens on hard multi-step problems.

Caveats: The theoretical bounds depend on the accuracy of the underlying reward and confidence estimators; noisy verifiers in open-ended domains degrade the filtering guarantees. Empirical verification was conducted on mathematical and algorithmic reasoning, which possess clearer verification signals than subjective domains.