[
    {
        "id": "osp-20336",
        "type": "article-journal",
        "title": "Provable Test-Time Scaling for Beam Search in LLM Reasoning",
        "author": [
            {
                "family": "He",
                "given": "Qijia"
            },
            {
                "family": "Huang",
                "given": "Yu"
            },
            {
                "family": "Cheng",
                "given": "Yu An"
            },
            {
                "family": "Chen",
                "given": "Yuxin"
            },
            {
                "family": "Liang",
                "given": "Yingbin"
            }
        ],
        "URL": "https://omanscience.com/ar/articles/provable-test-time-scaling-for-beam-search-in-llm-reasoning",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "abstract": "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 $Ω(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."
    }
]