Paper deep dive
Provable Test-Time Scaling for Beam Search in LLM Reasoning
Qijia He, Yu Huang, Yuan Cheng, Yuxin Chen, Yingbin Liang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 10/4/2026, 2:45:59 AM
Summary
This paper provides a theoretical analysis of test-time scaling for beam search in Large Language Models (LLMs). It establishes that vanilla beam search requires a sample complexity of at least Ω(C*(x)^2) to preserve the optimal response, where C*(x) is the token-level coverage coefficient. To address this, the authors propose Confidence-Filtered Beam Search (CF-Beam), which reduces the sample complexity dependence to nearly linear O~(C*(x)) under prefix competitiveness. The study demonstrates that CF-Beam offers provable advantages over sequence-level methods like Best-of-N and Best-of-Majority by controlling search-induced terms via polynomially scaling token-level coefficients rather than exponentially scaling sequence-level coefficients.
Entities (8)
Relation Signals (6)
CF-Beam → reducessamplecomplexityto → O~(C*(x))
confidence 95% · CF-Beam... reduces the sufficient coverage dependence from quadratic to nearly linear... sample complexity bound of O~(C*(x))
Vanilla-Beam → requiressamplecomplexity → Omega(C*(x)^2)
confidence 95% · We establish a lower bound for vanilla beam search, showing that at least Ω(C*(x)^2) samples are required for the optimal response to survive
CF-Beam → outperforms → Best-of-N
confidence 90% · Our results highlight a fundamental advantage of beam search over sequence-level inference methods such as Best-of-N
CF-Beam → outperforms → Best-of-Majority
confidence 90% · Our results highlight a fundamental advantage of beam search over sequence-level inference methods such as Best-of-N and Best-of-Majority.
Best-of-N → hascoveragegrowth → Exponential
confidence 85% · While the guarantees of these approaches typically involve coverage coefficients that grow exponentially with the horizon L
CF-Beam → hascoveragegrowth → Polynomial
confidence 85% · CF-Beam controls the dominant search-induced term through a token-level coverage coefficient that scales polynomially with L.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\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.
Tags
Links
- Source: https://arxiv.org/abs/2609.38672v1
- Canonical: https://arxiv.org/abs/2609.38672v1
Trouble viewing inline? Open PDF directly →
Full Text
142,026 characters extracted from source content.
Expand or collapse full text
Provable Test-Time Scaling for Beam Search in LLM Reasoning Qijia He †thanks: equal contribution Affiliation: The Ohio State University Email: he.2806@osu.edu Yu Huang* Affiliation: University of Pennsylvania Email: yuh42@wharton.upenn.edu Yuan Cheng* Affiliation: National University of Singapore Email: yuan.cheng@u.nus.edu Yuxin Chen Affiliation: University of Pennsylvania Email: yuxinc@wharton.upenn.edu Yingbin Liang Affiliation: The Ohio State University Email: liang.889@osu.edu 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⋆(x)2) (C (x)^2) samples are required for the optimal response to survive, where C⋆(x)C (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. 1 Introduction Test-time computing has emerged as a powerful paradigm for improving the performance of large language models (LLMs) by allocating additional computation at inference time. Unlike post-training approaches such as supervised fine-tuning and reinforcement learning from human feedback, which improve performance by updating the model’s parameters, test-time methods operate on a fixed model and improve accuracy via repeated sampling, aggregation, and selection. Due to their simplicity in implementation and striking performance scaling behavior, test-time methods have been widely deployed in real-world systems (Zaharia et al., 2024; Team et al., 2023). Existing and widely studied test-time methods include Best-of-N sampling (BoN), majority voting, chain-of-thought (CoT) reasoning, and their corresponding variants (Jinnai et al., 2024; Ichihara et al., 2025; Wang et al., 2022; Liu et al., 2025a; Di et al., 2025). Despite their empirical success, applying these approaches to complex real world tasks can be prohibitively expensive, as BoN and voting-based schemes require a rapidly increasing number of samples to maintain accuracy as context length grows. Moreover, the presence of imperfect verifiers can exacerbate selection errors by over-trusting spurious candidates or discarding correct but low-scoring solutions (Huang et al., 2025). To improve the reasoning capabilities of LLMs on long reasoning chains and mitigate the compounding errors in final answers that arise from accumulated small mistakes or model imperfections across intermediate steps (Xu et al., 2025; Xie et al., 2023), beam search has been found to be a promising test-time approach for sparse-success and long-horizon settings. This method expands candidate responses token by token and applies a step-level verifier, which can be either an external reward model (Lightman et al., 2023; Setlur et al., 2024) or an internal self-evaluation metric (Xie et al., 2023), to prune low-quality continuations at each step. By aggregating candidate trajectories and pruning inferior paths, beam search allocates inference-time computation to the most promising prefixes toward desired outputs, thereby increasing the probability of identifying correct solutions (Yu et al., 2025a; Zhu et al., 2024) while simultaneously reducing unnecessary test-time computation. Despite a rich body of empirical evidence demonstrating the effectiveness of beam search, theoretical analysis of beam search remains limited. Meister et al. (2020) studied what implicit objective function beam search optimizes. Recently, Fadeeva et al. (2025) studied beam search for self-consistency-based uncertainty quantification. To the best of our knowledge, there has not been a principled theoretical understanding of its test-time scaling performance, which raises the following fundamental research questions: 1. How does beam search scale at test time, particularly when test-time compute is constrained and verifiers are imperfect? 2. Compared to recent test-time guarantees for Best-of-Majority Di et al. (2025) and best-of-N Huang et al. (2025), does beam search enjoy provable advantages? From the analysis standpoint, the main technical obstacle is that step-by-step pruning in beam search induces strong token-level dependencies over time, making the resulting dynamics harder to analyze than in sequence-level methods. Moreover, beam search often relies on heuristic intermediate verifiers whose step-wise scores are not aligned with a single, globally consistent objective. In this paper, we answer the above questions by analyzing the test-time performance of beam search in a sampling-access setting, where token probabilities are estimated from sampled continuations and used as an internal verifier, while an external reward model is accessible only after the complete response is generated. • Vanilla-Beam vs. CF-Beam. We establish a lower bound of sample complexity, showing that vanilla beam search (Vanilla-Beam) requires the sample size to be at least Ω(C⋆(x)2) (C (x)^2) for the optimal response to survive, where C⋆(x)C (x) is the token-level coverage coefficient for prompt x∈x . This motivates us to filter the low-probability samples via the estimated sampling policy, resulting in the confidence-filtered beam search (CF-Beam) as shown in Figure 1, which reduces the sufficient coverage dependence from quadratic to nearly linear under prefix competitiveness, for fixed horizon, gap, and target accuracy. • Regret Analysis. We 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 those approaches involve coverage coefficients that may potentially grow exponentially with the horizon L, CF-Beam controls the dominant search-induced term through a token-level coverage coefficient that scales only polynomially with L. • Reward-Model-Free Regret. We further analyze the regret for a fully self-consistent CF-Beam. In contrast to standard CF-Beam, whose guarantees depend on the error of an external reward model, the regret bound for the self-consistent version is driven solely by the probability of rare failure events. Since the regret is decoupled from the reward-model error, self-consistent CF-Beam admits a sufficient total query budget growing only linearly in L, up to logarithmic factors, for fixed beam width, token-level coverage, prefix gap, and target accuracy. • Numerical experiments. Our numerical results compare CF-Beam against vanilla beam search, BoN, Majority voting and Best-of-Majority, demonstrating that CF-Beam achieves better performance on hard instances and is more robust to increasing horizon length. 2 Preliminaries Problem Setting and Decoding. Test-time algorithms are decoding strategies that use extra inference-time compute to map an input prompt under a fixed LLM model to an improved output response. Formally, given a prompt x∈x , the goal of the algorithm is to produce a response y, which is represented as a length-L token sequence y=(a1,…,aL)∈Ly=(a_1,…,a_L) ^L, based on a fixed reference LLM policy πref:→Δ(L) _ref:X→ (A^L). Here, A denotes the token vocabulary, and Δ(L) (A^L) is the set of probability distributions over LA^L. Figure 1: Confidence-Filtered Beam Search Pipeline The quality of the complete response y is evaluated by a ground-truth outcome reward r⋆:×→[0,1]r :X×Y→[0,1], which is only revealed after the entire response is generated. Such sparse outcome rewards are standard in LLM settings, e.g., in reinforcement learning with verifiable feedback (RLVR) (Chen et al., 2025; He et al., 2025). In practice, r⋆r is typically unavailable, and the algorithm designer instead relies on an approximate reward model r^:×→[0,1] r:X×Y→[0,1] that assigns a surrogate score r^(x,y) r(x,y) to assess the quality of response y for any prompt x. The reference policy πref _ref further admits a standard autoregressive factorization by steps. Let st−1:=(a1,…,at−1)s_t-1:=(a_1,…,a_t-1) denote the token prefix generated up to step t−1t-1 (with s0=∅s_0= ). Then we have πref(y∣x)=∏t=1Lπref(at∣x,st−1), _ref(y x)= _t=1^L _ref(a_t x,s_t-1), Here, on the right-hand side, with a slight abuse of notation, we use πref _ref to also denote a token-level reference policy ×→Δ()X×S→ (A), where S is the set of all token prefixes from steps 1 to L. Since beam search algorithms aggregate and process information at the token level, we focus throughout the remainder of the paper on the token-level policy πref:×→Δ() _ref:X×S→ (A). We assume black-box sampling access to the reference policy, without access to full logits or exact next-token probabilities, so token probabilities must be estimated from sampled continuations. Goal and Evaluation. Given a prompt x, the goal of parallel test-time computing is to design an algorithm Alg that interacts with the base policy πref(⋅∣s,x) _ref(· s,x) through sampling and aggregation and outputs a response y∼πAlg(⋅∣x)y _Alg(· x), aiming to maximize the expected ground-truth reward y∼Alg(⋅|x)[r⋆(x,y)]E_y (·|x) [r (x,y) ]. Let y⋆:=argmaxy∈r⋆(x,y)y := _y r (x,y) denote the optimal response that maximizes the true outcome reward. We define the regret on instance x as Reg(x)=r⋆(x,y⋆)−y∼πAlg(⋅∣x)[r⋆(x,y)].Reg(x)=r (x,y )-E_y _Alg(· x)\! [r (x,y) ]. (1) Computational Complexity. We measure the test-time computational cost of an algorithm Alg by the number of token-level policy queries it makes to the base model. Concretely, each time Alg queries πref(⋅∣s,x) _ref(· s,x) to sample from the next-token distribution at a prefix s, we count one query. We use N to denote the (per-prefix) sample complexity, i.e., the number of such queries issued at each prefix s, and let B(x)B(x) denote the total number of such queries on instance x. We refer to B(x)B(x) as the total (query) budget of Alg. Coverage Coefficient. To quantify the ability of the base policy πref _ref to generate the optimal response, following Huang et al. (2025), we introduce coverage coefficients that measure how difficult it is for the base policy πref _ref to sample the optimal trajectory. Definition 1 (Token- and sequence-level coverage). Fix an instance x and let y⋆(x)=(a1⋆,…,aL⋆)y (x)=(a_1 ,…,a_L ) be the unique optimal response, with optimal prefixes st−1⋆=a⋆1:t−1s_t-1 =a _1:t-1. Let π⋆π denote the oracle policy that deterministically follows the optimal token at each step, i.e., π⋆(at⋆∣st−1⋆,x)=1π (a_t s_t-1 ,x)=1 for all t∈[L]t∈[L]. The token-level coverage coefficient is defined as Ct⋆(x):=π⋆(at⋆∣st−1⋆,x)πref(at⋆∣st−1⋆,x)=1πref(at⋆∣st−1⋆,x).C_t (x):= π (a_t s_t-1 ,x) _ref(a_t s_t-1 ,x)= 1 _ref(a_t s_t-1 ,x). (2) We further define Cmax⋆(x):=maxt∈[L]Ct⋆(x)C _ (x):= _t∈[L]C_t (x) and C¯(x):=∏t=1LCt⋆(x) C(x):= _t=1^LC_t (x) as the sequence-level coverage coefficient. The quantity Ct⋆(x)C_t (x) captures the inverse probability of sampling the optimal token at depth t under πref _ref, while C¯(x) C(x) reflects the compounding difficulty along an autoregressive trajectory. This notion is consistent with the L1L_1 coverage coefficient studied in Huang et al. (2025); Di et al. (2025). For notational convenience, we omit the dependence on the instance x when no ambiguity arises. 3 Algorithm Algorithm 1 Vanilla-Beam vs CF-Beam: CF-Beam adds highlighted lines (Line 14-15) 1: Input: Base policy πref _ref, beam width b≥1b≥ 1, depth L, sample sizes N, threshold βtt=1L\ _t\_t=1^L, reward estimator r r, and prompt x∈x . 2: ℬ0←∅B_0←\ \ initial beam 3: Q(s0)←0Q(s_0)← 0 initial score over trajectory s0=∅s_0= 4: for t=1t=1 to L do 5: t←∅D_t← candidate prefixes at depth t 6: for all st−1∈ℬt−1s_t-1 _t-1 do 7: initialize Nt(st−1,at)←0N_t(s_t-1,a_t)← 0 for all at∈a_t 8: for i=1i=1 to N do 9: sample at(i)∼πref(⋅∣st−1,x)a^(i)_t _ref(· s_t-1,x) 10: Nt(st−1,at(i))←Nt(st−1,at(i))+1N_t(s_t-1,a^(i)_t)← N_t(s_t-1,a^(i)_t)+1 11: end for 12: for all at∈a_t with Nt(st−1,at)≥1N_t(s_t-1,a_t)≥ 1 do 13: π^(at∣st−1,x)←Nt(st−1,at)/N π(a_t s_t-1,x)← N_t(s_t-1,a_t)/N 14: if π^(at∣st−1,x)<βt π(a_t s_t-1,x)< _t then 15: skip //CF-Beam only 16: else 17: st′←st−1⊕ats _t← s_t-1 a_t append ata_t to st−1s_t-1 18: Q(st′)←Q(st−1)+logπ^(at∣st−1,x)Q(s _t)← Q(s_t-1)\!+\! π(a_t s_t-1,x) 19: t←t∪st′D_t _t∪\s_t \ 20: end if 21: end for 22: end for 23: ℬt←top-bst′∈t ranked by Q(st′)B_t -b\s _t _t ranked by Q(s _t)\ 24: end for 25: y^←argmaxy∈ℬLr^(x,y) y← _y _L r(x,y) 26: Output: y y Beam search is a search-based decoding algorithm for LLM inference, which explores diverse responses and applies a step-level verifier to prune low-quality continuations at each step, aiming to ultimately concentrate on the most promising prefixes and reduce unnecessary test-time computational cost. Vanilla Beam Search (Vanilla-Beam). Vanilla-Beam, as shown in Section 3 (Xie et al., 2023; Yu et al., 2025a), generally maintains a beam of b trajectories. At each step, it expands each trajectory by enumerating multiple next-token candidates (Lines 6-11), scores the newly formed trajectories under a chosen metric (Line 18), and prunes these trajectories to the top b candidates, which forms the beam ℬB for the next step (Line 23). After reaching the end-of-sequence or length limit, it selects the final output by maximizing an external reward model over the top-b estimated log-likelihood candidates (Line 25). In particular, the log-likelihood is used as the scoring metric. For each time step t∈[L]t∈[L], we draw N fresh i.i.d. samples at(1),…,at(N)∼πref(⋅∣st−1,x)a_t^(1),…,a_t^(N) _ref(· s_t-1,x), and then estimate the action distribution at step t by the empirical frequencies: π^(at|st−1,x)=1N∑i=1N1(at(i)=at). π(a_t|s_t-1,x)= 1N _i=1^N1(a_t^(i)=a_t). The score of a trajectory, denoted as Q(st)Q(s_t) is defined as the sum of estimated log-probabilities: Q(st)=∑i=1tlogπ^(ai|si−1,x).Q(s_t)= _i=1^t π(a_i|s_i-1,x). Samples at distinct prefixes use independent randomness. We keep only the top-b trajectories for the next round, i.e., ℬt=top-bst∈t:Q(st).B_t=top-b \s_t∈D_t:Q(s_t) \. If filtering leaves an empty beam, the algorithm returns any fixed response; ties are resolved by a fixed rule. In practice, retaining only the top-b trajectories can be fragile in Vanilla-Beam. Since the action space A is typically enormous, most tokens lie in the low-probability tail and are rarely sampled. Yet occasional tail samples amplified by finite-sample estimation and hard top-b pruning can introduce spurious candidates and thereby crowd out the optimal prefix s⋆s . Since beam search is path-dependent, eliminating s⋆s at an early step is irreversible and prevents recovery even if subsequent steps are estimated accurately. The following theorem formalizes this phenomenon by constructing a hard instance where Vanilla-Beam fails (i.e., the correct trajectory is discarded with a constant probability), without a sufficiently large sample size. Detailed proof of constructing the hard instance is deferred to Appendix C. Theorem 1. There exists an LLM instance π∈Ππ∈ satisfying 50≤Ci⋆(x):=C⋆(x)≪(||)1/450≤ C_i (x):=C (x) (|A|)^1/4 for all i∈[L]i∈[L], such that if we set N≤(C⋆(x))2/16N≤(C (x))^2/16, the probability of eliminating the correct answer y⋆y using Vanilla-Beam with 2≤b≤N/22≤ b≤ N/2 is at least 0.50.5. Theorem 1 shows that without the sample size N to be at least N>Ω((Cmax⋆)2)N> ((C_ )^2), Vanilla-Beam cannot survive the correct response to the end of the process. Confidence-Filtered Beam Search (CF-Beam). In order to reduce the sample complexity of Vanilla-Beam, inspired by Di et al. (2025), we introduce a thresholding step (Lines 14-15 in Section 3), which filters low-probability samples based on the estimation of their probability of sampling. We call this modified algorithm Confidence-Filtered Beam Search (CF-Beam). To be specific, for each prefix st,t∈[L]s_t,\ t∈[L], after generating N actions, we keep only those satisfying π^t(at∣st−1,x)≥βt π_t(a_t s_t-1,x)≥ _t, and then select the top-b trajectories from such a filtered action set. We will show in Section 4.2 (Theorem 2 and Corollary 1) that this simple modification yields a sample complexity bound of O~(Cmax⋆) O(C_ ) for fixed horizon, prefix gap, and target accuracy, thereby improving the sample complexity from the quadratic to nearly linear dependence on Ct⋆(x)C _t(x). 4 Regret Analysis 4.1 Technical Assumptions In this subsection, we introduce the technical assumptions to establish the performance guarantee for the beam search method. First, while the performance metric is defined with respect to the true reward r⋆r , the algorithm typically has access only to an approximate reward model r r. We capture the quality of r r via a distributional estimation error under πref _ref, which is a commonly adopted assumption in the literature (Huang et al., 2025; Di et al., 2025). Assumption 1 (Reward estimation error). For each instance x∈x , the reward model satisfies y∼πref(⋅∣x)[(r⋆(x,y)−r^(x,y))2]≤ϵRM2(x).E_y _ref(· x) [ (r (x,y)- r(x,y) )^2 ]≤ _RM^2(x). (3) Assumption 2 (Globally optimal response). For each instance x, there exists a unique optimal response y⋆(x)=argmaxy∈r⋆(x,y),y (x)= _y r (x,y), (4) with r⋆(x,y⋆(x))=1r (x,y (x))=1. Here, y⋆(x)=(a1⋆,…,aL⋆)y (x)=(a _1,…,a _L) captures the entire optimal path. Moreover, the reward model error at the optimum is bounded as |r⋆(x,y⋆(x))−r^(x,y⋆(x))|≤ϵopt(x). |r (x,y (x))- r(x,y (x)) |≤ _opt(x). (5) It is obvious that the reward model error is crucial for the success of inference time algorithms, and building an accurate reward model has been extensively studied in the Reinforcement Learning with Human Feedback (RLHF) framework (Wang et al., 2026; Sun et al., 2025b; Duan et al., 2025; Yu et al., 2025b). Since our work mainly focuses on sampling strategy of the base model, we directly assume that we have access to a reward model with the estimation errors controlled by ϵRM2 _RM^2 and ϵopt _opt. Furthermore, since the reward signal is only available at the sequence level, the algorithm can evaluate a completed response y using r^(x,y) r(x,y), but does not observe intermediate-step rewards for partial prefixes. In such settings, inference-time decisions must rely on signals intrinsic to the base policy, such as its self-likelihood and uncertainty over candidate continuations. As having been justified by prior analyses (Cordero-Encinar and Duncan, 2025; Feng et al., 2025), we impose the following prefix separability condition. Assumption 3 (Prefix competitiveness). There exists a common κ∈(0,1]κ∈(0,1] such that, for each depth t∈[L]t∈[L] and any prefix s=(a1,…,at)∈ts=(a_1,…,a_t) ^t with s≠st⋆=(a1⋆,…,at⋆)s≠ s _t=(a _1,…,a _t), we have 1t∑i=1tlog(πref(ai⋆∣si−1⋆,x)πref(ai∣si−1,x))≥κ, 1t _i=1^t ( _ref(a _i s _i-1,x) _ref(a_i s_i-1,x) )≥κ, (6) where si−1=a1:i−1s_i-1=a_1:i-1 and s⋆i−1=a⋆1:i−1s _i-1=a _1:i-1. Any larger positive gap lower bound also implies the condition with κ=1κ=1, so restricting the chosen lower bound to (0,1](0,1] does not restrict the model class. Such a gap condition is needed whenever intermediate pruning decisions rely on likelihood-based signals rather than direct reward feedback. Related gap-dependent analyses have also appeared in self-consistency and certification-based decoding settings; see, e.g., Cordero-Encinar and Duncan (2025); Aeeneh et al. (2024). The following proposition shows that, in our beam-search setting, this prefix-competitiveness condition is not merely technical: without it, likelihood-based pruning can irreversibly discard the optimal trajectory even with an arbitrarily large sampling budget. Proposition 1 (Necessity of Assumption 3). Without Assumption 3, there exists an LLM instance (πref,r⋆)( _ref,r ) on which, for every sample size N≥1N≥ 1, beam search with beam width b=1b=1 prunes the optimal trajectory y⋆y from the final beam with probability at least 3/43/4. The proof is deferred to Appendix D, and additional discussion is provided in Appendix B. 4.2 Regret Upper Bound The regret arises from three factors: (i) the accuracy of the reward model used for the final selection, (i) the capacity of the base model πref _ref, and (i) search failures, i.e., events under which the optimal response is eliminated during inference. The first factor is captured by Assumptions 1 and 2, and the second by the coverage coefficients in Definition 1. To control the third factor, we define good events that separate two failure modes: the optimal action fails to pass confidence filtering, or the optimal prefix passes filtering but is discarded by top-b pruning. Pre-sampled histograms. Since the algorithm samples only at prefixes in the current beam, the empirical frequency π^(at⋆∣st−1⋆,x) π(a_t s_t-1 ,x) is undefined once an optimal prefix has been discarded. To define it for every t, we use an equivalent description of the sampling process. Before the algorithm runs, we independently draw, for every prefix s of depth less than L, a histogram of N i.i.d. samples from πref(⋅∣s,x) _ref(· s,x); the histogram of s is revealed only when the algorithm expands s. Since each prefix is expanded at most once, the output of the algorithm has the same distribution as under fresh sampling, and the construction is used only in the analysis. Under this coupling, the empirical frequencies along the optimal path are defined whether or not the path survives, and histograms at distinct prefixes are mutually independent. Definition 2 (Good events). We define the following events. (i) Filtering event. The optimal action passes confidence filtering at every depth: ℰβ:=∀t∈[L]:π^(at⋆∣st−1⋆,x)≥βt.E_β:= \∀ t∈[L]:\ π(a_t s_t-1 ,x)≥ _t \. (i) Beam-survival event. Let rankt(s)rank_t(s) denote the rank of s∈ts _t when tD_t is sorted by Q(⋅)Q(·) in descending order, with ties broken by the rule of the algorithm. Define ℰb:=∀t∈[L]:st⋆∈t⇒rankt(st⋆)≤b.E_b:= \∀ t∈[L]:\ s_t _t\ \ rank_t(s_t )≤ b \. The overall good event is ℰ:=ℰβ∩ℰbE:=E_β _b. By induction over the depths, ℰE holds if and only if y⋆∈ℬLy _L: on ℰβE_β, every optimal prefix in the beam generates its optimal extension as a candidate, and on ℰbE_b, top-b pruning retains this extension. We refer to ℙ(ℰc)P(E^c) as the search error. Now we present our main result on the regret of the CF-Beam algorithm. Theorem 2 (Regret of CF-Beam). Suppose L≥2L≥ 2, N≥48Cmax⋆κ2max2,log(2Cmax⋆)N≥ 48C_ κ^2 \2, (2C_ )\, and βt=(1−1/L)/Ct⋆(x) _t=(1-1/L)/C_t (x) for all t∈[L]t∈[L]. Under Assumptions 1, 2, and 3, the regret of CF-Beam in Section 3 satisfies Reg(x)≤ℙ(ℰc)+ϵopt(x)+2C¯(x)ϵRM2(x)⏟reward-model error,Reg(x) (E^c)+ _opt(x)+2 C(x) _RM^2(x)_reward-model error, (7) where the search error satisfies ℙ(ℰc)≤Lexp(−N2Cmax⋆L2)⏟filtering error+2Cmax⋆bexp(−κ2N48Cmax⋆)⏟pruning error.P(E^c)≤ L \! (- N2C_ L^2 )_filtering error+ 2C_ b \! (- κ^2N48C_ )_pruning error. (8) Theorem 2 separates the regret into a search error and a reward-model error. The search error accounts for filtering out an optimal action or pruning its prefix from the beam. Both probabilities decay exponentially with the per-prefix sample size N; their rates depend on the token-level coverage Cmax⋆C_ , the horizon L for filtering, and the prefix gap κ for pruning. A wider beam reduces the pruning term, since discarding the optimal prefix requires at least b filtered competitors to match or exceed its score. Once the optimal response survives, the remaining regret comes from the final reward-based selection. Its bound involves the sequence-level coefficient C¯(x) C(x), which arises when transferring the reward-model error guarantee under πref _ref to the selected output; this term does not decrease with N or b. The threshold βt _t depends on the unknown Ct⋆(x)C_t (x), so this result gives an oracle guarantee rather than a directly implementable rule. For practical use, Appendix H.1 describes an empirical variant of CF-Beam that replaces the unknown optimal-token probability 1/Ct⋆(x)1/C_t (x) with the largest empirical next-token frequency at the current prefix, and sets the threshold to βt(s)=γmaxa∈π^(a∣s,x) _t(s)=γ _a π(a s,x) for a constant γ∈(0,1)γ∈(0,1). This proxy is reasonable when the optimal continuation is locally competitive, in which case the optimal-token probability is of the same order as the largest next-token probability. Proof sketch. We first bound the probability that the optimal response is lost during search. At each depth, the empirical count of the optimal action is binomial; a Chernoff lower-tail bound and a union bound over depths control the filtering error. The threshold lies a relative 1/L1/L below the mean frequency, which yields the L2L^2 factor in this bound. For pruning, we count the filtered competitors whose empirical scores match or exceed that of the optimal prefix. Truncated binomial moment bounds control their score differences even when low-probability actions happen to pass the filter. Assumption 3 supplies the true likelihood gap, and summing over competitors uses their total probability mass rather than their number. If the optimal prefix passes filtering but is pruned, at least b competitors must match or exceed its score; Markov’s inequality then controls the pruning error. On ℰE, the optimal response reaches the final beam, so the remaining regret comes from reward-based selection. For each response y, the joint probability Pr(y^=y,ℰ) ( y=y,E) is at most πref(y∣x)∏t=1Lβt−1≤4C¯(x)πref(y∣x) _ref(y x) _t=1^L _t^-1≤ 4 C(x) _ref(y x). This comparison and Cauchy–Schwarz transfer the reward-model error bound under πref _ref to the selected response, while the pointwise error at y⋆y contributes ϵopt(x) _opt(x). We provide the comprehensive proof in Appendix E. Corollary 1 (Sample complexity). Under the assumptions and threshold choice of Theorem 2, for δ∈(0,1)δ∈(0,1), it suffices to take N≳Cmax⋆maxL2log2Lδ,1κ2(log(eCmax⋆)+[log1bδ]+)N C_ \L^2 2Lδ, 1κ^2 ( (eC_ )+ [ 1bδ ]_+ ) \ (9) to achieve regret at most δ+ϵopt(x)+2C¯(x)ϵRM2(x)δ+ _opt(x)+2 C(x) _RM^2(x), where [u]+:=maxu,0[u]_+:= \u,0\ and the implicit constant is universal. Corollary 1 shows that the sufficient per-prefix sample size grows linearly in Cmax⋆C_ and quadratically in L, up to logarithmic factors, and only logarithmically in 1/δ1/δ. Since the total query budget is at most LbNLbN, the total budget is O~(bL3Cmax⋆) O(bL^3C_ ) for fixed κ and δ. The beam width enters only through log(1/(bδ)) (1/(bδ)): a wider beam relaxes the requirement from the pruning error until the filtering error or the baseline condition dominates. Benefit of confidence filtering. For fixed L, κ, and δ, Corollary 1 shows that N=O~(Cmax⋆)N= O(C_ ) samples per prefix suffice for the search error to be at most δ. In contrast, Theorem 1 exhibits an instance satisfying Assumption 3 on which Vanilla-Beam with 2≤b≤N/22≤ b≤ N/2 and N≤(C⋆)2/16N≤(C )^2/16 discards y⋆y with probability at least 1/21/2. Confidence filtering therefore reduces the per-prefix sample requirement from quadratic to nearly linear in the token-level coverage. 4.3 Comparison with Other Test-time Methods In this subsection, we compare the search-induced component of CF-Beam with other commonly adopted test-time algorithms for which regret guarantees have recently been established. First, Di et al. (2025) proposed the Best-of-Majority algorithm, which first applies majority voting (self-consistency) to discard low-frequency candidates and then selects the final response from the remaining set using an external reward model. They established a regret bound given by Reg(x)≲ϵopt(x)+C¯(x)ϵRM2(x)+C¯(x)exp(−N~/C¯(x)), (x) _opt(x)+ C(x)\, _RM^2(x)+ C(x) \! (- N/ C(x) ), where C¯(x):=∏t=1LCt⋆(x) C(x):= _t=1^LC_t (x) captures the coverage along the entire trajectory in our path-based notation, and N~ N refers to the number of complete responses sampled. To make the search-induced term at most δ, the sample size N~ N needs to satisfy N~≳C¯(x)log(C¯(x)/δ) N C(x) \! ( C(x)/δ ), which leads to the total computation budget B=LN~B=L N on the order of B≳LC¯(x)log(C¯(x)/δ)B L\, C(x) \! ( C(x)/δ ). Whenever Cmin⋆:=min1≤t≤LCt⋆(x)>1C _min:= _1≤ t≤ LC_t (x)>1, this budget can scale exponentially with the horizon length L. This exponential scaling of the coverage-dependent term also appears in other test-time algorithms such as Best-of-N Huang et al. (2025), where the regret bound takes the form of O(C¯(x)⋅log(1/εRM(x))/N~+N~⋅εRM2(x)).O ( C(x)· (1/ _RM(x))/ N+ N· _RM^2(x) ). Similarly, the dependence on C¯(x) C(x) can lead to exponentially large sample complexity as L increases. In contrast, our CF-Beam method controls the rare-failure term with a budget B=LbNB=LbN that satisfies Corollary 1, which scales only polynomially in L (up to the beam-width factor b). Hence, beam-pruning combined with β-filtering effectively replaces the potentially exponential dependence on C¯(x) C(x) with a polynomial dependence on L in the search-induced component, yielding substantially reduced computation-cost scaling in long-horizon settings when the reward-model error is controlled. The above comparison suggests that CF-Beam can be more favorable on hard instances. Compared to sequence-level parallel sampling methods, a key advantage of CF-Beam is that its search-induced guarantee scales with LCmax⋆LC_ rather than the product C¯(x)=∏t=1LCt⋆(x) C(x)= _t=1^LC_t (x). When all Ct⋆(x)C_t (x) are close to 11 and L is moderate, sequence-level methods such as Best-of-N or Best-of-Majority may be more sample-efficient. In contrast, when some Ct⋆(x)C_t (x) are large, C¯(x) C(x) grows rapidly, and CF-Beam becomes more favorable due to its dependence on LCmax⋆LC_ in the search-induced term. This qualitative trend is consistent with the empirical scaling study of Snell et al. (2024). 4.4 Regret Lower Bound In this subsection, we establish the lower bound for the beam search algorithm. Theorem 3. For the CF-Beam algorithm, when b≥2b≥ 2, there exist hard instances with a sufficiently small constant κ′>0κ >0 and Ct⋆(x)=||/(1+||κ′)C _t(x)=|A|/(1+|A|κ ) for all t∈[L]t∈[L], such that the regret can be lower bounded as Ω(C¯(x)ϵRM2(x)). ( C(x) _RM^2(x) ). This lower bound matches the reward model error term in the upper bound in Theorem 2, demonstrating the minimax optimality of the regret with respect to the reward estimation error ϵRM2(x) _RM^2(x). To be specific, the lower bound is determined by (i) the difficulty of the problem C¯ C and (i) the accuracy of the reward model. These two dependencies are necessary, since outputting the optimal response requires both the model’s ability to generate it and the reward model’s ability to identify it. Di et al. (2025) established a general lower bound for the pass@k inference problem with a similar structure. However, their construction cannot be directly applied to our setting, as it does not satisfy Assumption 3. Our lower bound instead constructs a family of instances with an arbitrarily small prefix gap κ, under which it is information-theoretically difficult for any intermediate pruning strategy to eliminate all suboptimal prefixes with high probability before the final step. The incurred regret is then driven by the inability of the imperfect reward model to always select the true optimum among the surviving candidates. 4.5 Extension to Reward Model Free Setting Algorithm 2 Self-consistent CF-Beam 1: Given: base policy πref _ref, beam width b≥1b≥ 1, depth L, sample sizes N, threshold βtt=1L\ _t\_t=1^L. 2: Input: prompt x∈x . 3: Execute Algorithm 3, Lines 2–24. 4: y^←argmaxy∈ℬLQL(y) y← _y _LQ_L(y). 5: return y y In the case when a reliable reward model is unavailable (or severely noisy), finding the most probable path becomes a natural metric to identify the optimality of the path. To this end, we can derive a reward-model-free variant of CF-Beam by replacing the final selection rule, namely, instead of selecting the candidate with the largest estimated reward, we define QL(y):=∑t=1Llogπ^(at∣st−1,x)Q_L(y):= _t=1^L π(a_t s_t-1,x) and output y^←argmaxy∈ℬLQL(y), y← _y _LQ_L(y), i.e., the most “self-consistent” candidate within the final beam according to the intrinsic score QLQ_L. This modification yields Algorithm 4.5, which can be viewed as a reward-model-free variant of CF-Beam in Algorithm 3. The same filtered-score analysis controls this variant, with an additional comparison at the final step: the selected complete response must have the largest empirical likelihood, rather than merely remain in the beam. The proof is deferred to Appendix E.4. Corollary 2. Suppose y⋆y is an optimal response with r⋆(x,y⋆)=1r (x,y )=1, Assumption 3 holds, N≥48Cmax⋆κ2max2,log(2Cmax⋆)N≥ 48C_ κ^2 \2, (2C_ )\, and βt=1/(2Ct⋆(x)) _t=1/(2C_t (x)). The regret of Section 4.5 satisfies Reg(x) (x) ≤Lexp(−N8Cmax⋆)+2Cmax⋆bexp(−κ2N48Cmax⋆)+[Cmax⋆exp(−κ2N48Cmax⋆)]L. ≤ L \! (- N8C_ )+ 2C_ b \! (- κ^2N48C_ )+ [C_ \! (- κ^2N48C_ ) ]^L. In particular, N≳(Cmax⋆/κ2)log(eLCmax⋆/δ)N (C_ /κ^2) (eLC_ /δ) suffices to achieve regret at most δ∈(0,1)δ∈(0,1). No reward-model accuracy assumption is needed. The first two terms account for filtering and intermediate beam pruning, and the last controls final selection by the empirical score. Since the guarantee does not involve reward-model error, the threshold multiplier can be fixed at 1/21/2 independently of L. This removes the L2L^2 factor from the filtering contribution to the sufficient per-prefix sample size in Corollary 1. The resulting total query budget is O~(LbCmax⋆/κ2) O(LbC_ /κ^2), with only logarithmic dependence on L in the per-prefix sample requirement. 5 Experiments (a) p=0.01p=0.01 (b) p=0.05p=0.05 (c) p=0.3p=0.3 Figure 2: Algorithm performance on different difficulty-level problems. Figure 3: Algorithm performance vs. horizon length. We validate our theoretical findings by comparing two implementations of CF-Beam, Oracle CF-Beam and Empirical CF-Beam, against four baselines: Vanilla beam search, Best-of-N (Huang et al., 2025), Majority Voting, and Best-of-Majority (Di et al., 2025). Oracle CF-Beam uses the threshold in Theorem 2, while Empirical CF-Beam sets βt(s)=γmaxa∈π^(a∣s,x) _t(s)=γ _a π(a s,x) with γ=0.3γ=0.3, without requiring the optimal-token probability. Following the RLVR setting, we evaluate each algorithm on a synthetic LLM simulator paired with a noisy reward model of error level ϵRM2=0.01 _RM^2=0.01, and report the accuracy of identifying the optimal response. Baseline descriptions, the experimental protocol, simulator construction, and parameter setups are deferred to Appendix H. We also evaluate Empirical CF-Beam on a pretrained LLM in Appendix H.2. Figure 3 compares the algorithms under varying total budgets across three difficulty levels, parameterized by the per-rollout success probability p∈0.01,0.05,0.3p∈\0.01,0.05,0.3\ (larger p = easier). CF-Beam algorithms achieve the largest advantage in the hardest setting (p=0.01p=0.01, Figure 2(a)), where sparse coverage and tail fluctuations are most pronounced—precisely the regime that amplifies the failure mode of Theorem 1. As p increases (Figures 2(b)–2(c)), the gap narrows and Vanilla-Beam catches up under sufficiently large budgets. This trend mirrors the relationship between C¯ C and Cmax⋆C _ shown in each panel: as p grows, C¯ C approaches Cmax⋆C _ , reducing CF-Beam’s edge. These observations align with our theoretical discussion in Section 4.3. Figure 3 reports accuracy as the horizon L grows, with per-step success probability 0.80.8. Sequence-level baselines (Best-of-N, Best-of-Majority, Majority Voting) degrade rapidly, while beam-based methods remain robust, and CF-Beam consistently attains the highest accuracy. This is consistent with our theory: CF-Beam’s dominant sample-complexity term scales only polynomially in L, whereas sequence-level methods can suffer exponential dependence on L. 6 Related Works In this section, we focus on related work in theoretical studies of test-time scaling. Additional related work is deferred to Appendix A. Despite extensive literature on test-time computing (Wang et al., 2022; Kang et al., 2025; Jinnai et al., 2024; Ichihara et al., 2025; Wei et al., 2022; Ghosal et al., 2025; Liu et al., 2025a), especially beam search (Xu et al., 2025; Xie et al., 2023; Zhu et al., 2024), theoretical analyses have only emerged recently. Hu et al. (2024) decomposed the statistical error of Chain-of-Thought (CoT) estimators and showed it vanishes with more demonstrations. Huang et al. (2024) analyzed Best-of-N and showed that larger N does not necessarily improve performance. Cordero-Encinar and Duncan (2025) and Aeeneh et al. (2024) established convergence rates for Majority Voting, while Di et al. (2025) proposed Best-of-Majority, which selects the top-k response from a set of highly self-consistent candidates with non-degrading sample complexity. Yu et al. (2025c) combined Best-of-N with a rewind-and-repeat strategy (Kim et al., 2024; Beirami et al., 2024) to derive stronger guarantees. The existing theoretical studies on beam search methods remains rather limited. Meister et al. (2020) characterized the implicit objective optimized by beam search, and Fadeeva et al. (2025) analyzed beam search for self-consistency-based uncertainty quantification. To our knowledge, no prior work studies the test-time scaling guarantees of beam search; Our work fills this research gap and provides the first test-time computing guarantee for beam search type algorithms. 7 Conclusion and Limitations This paper studied test-time guarantees for beam search in LLM reasoning, where model likelihood scores intermediate trajectories and an external reward model is queried only after full responses are generated. We showed that vanilla beam search can be theoretically suboptimal, and proposed Confidence-Filtered Beam Search to filter low self-consistency tokens before beam selection. CF-Beam improves the search-induced scaling over sequence-level methods on hard and long-horizon instances. The limitation is that this advantage relies on prefix alignment between likelihood and final reward; otherwise, reward-optimal prefixes may be pruned before final reward evaluation. Future work includes prompt-adaptive choices between beam-based and sequence-level methods, and settings with external rewards or process verifiers available before full responses are generated. References Aeeneh et al. (2024) S. Aeeneh, N. Zlatanov, and J. Yu New bounds on the accuracy of majority voting for multiclass classification. IEEE Transactions on Neural Networks and Learning Systems 36 (4), p. 6014–6028. Cited by: Appendix A, §4.1, §6. Aggarwal et al. (2023) P. Aggarwal, A. Madaan, Y. Yang, et al. Let’s sample step by step: adaptive-consistency for efficient reasoning and coding with llms. arXiv preprint arXiv:2305.11860. Cited by: Appendix A. Beirami et al. (2024) A. Beirami, A. Agarwal, J. Berant, A. D’Amour, J. Eisenstein, C. Nagpal, and A. T. Suresh Theoretical guarantees on the best-of-n alignment policy. arXiv preprint arXiv:2401.01879. Cited by: §6. Chen et al. (2025) F. Chen, Z. Jia, A. Rakhlin, and T. Xie Outcome-based online reinforcement learning: algorithms and fundamental limits. arXiv preprint arXiv:2505.20268. Cited by: §2. Chen et al. (2023) X. Chen, R. Aksitov, U. Alon, J. Ren, K. Xiao, P. Yin, S. Prakash, C. Sutton, X. Wang, and D. Zhou Universal self-consistency for large language model generation. arXiv preprint arXiv:2311.17311. Cited by: Appendix A. Cordero-Encinar and Duncan (2025) P. Cordero-Encinar and A. B. Duncan Certified self-consistency: statistical guarantees and test-time training for reliable reasoning in llms. arXiv preprint arXiv:2510.17472. Cited by: Appendix A, §4.1, §4.1, §6. Di et al. (2025) Q. Di, K. Ji, X. Li, H. Zhao, and Q. Gu Best-of-majority: minimax-optimal strategy for pass@ k inference scaling. arXiv preprint arXiv:2510.03199. Cited by: Appendix A, §H.1, item 2., §1, §2, §3, §4.1, §4.3, §4.4, §5, §6. Duan et al. (2025) K. Duan, Z. Liu, X. Mao, T. Pang, C. Chen, Q. Chen, M. Q. Shieh, and L. Dou Efficient process reward model training via active learning. arXiv preprint arXiv:2504.10559. Cited by: §4.1. Fadeeva et al. (2025) E. Fadeeva, M. Goloburda, A. Rubashevskii, R. Vashurin, A. Shelmanov, P. Nakov, M. Sachan, and M. Panov Don’t throw away your beams: improving consistency-based uncertainties in llms via beam search. arXiv preprint arXiv:2512.09538. Cited by: Appendix A, Appendix A, §1, §6. Feng et al. (2025) A. Feng, M. Alonso, and A. Odonnat Optimal self-consistency for efficient reasoning with large language models. arXiv preprint arXiv:2511.12309. Cited by: Appendix A, §4.1. Feng et al. (2023) X. Feng, Z. Wan, M. Wen, S. M. McAleer, Y. Wen, W. Zhang, and J. Wang Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17179. Cited by: §B.3. Ghosal et al. (2025) S. S. Ghosal, S. Chakraborty, A. Reddy, Y. Lu, M. Wang, D. Manocha, F. Huang, M. Ghavamzadeh, and A. S. Bedi Does thinking more always help? understanding test-time scaling in reasoning models. arXiv preprint arXiv:2506.04210. Cited by: Appendix A, §6. He et al. (2025) S. He, T. Xia, X. Zhou, and H. Wei Response-level rewards are all you need for online reinforcement learning in llms: a mathematical perspective. arXiv preprint arXiv:2506.02553. Cited by: §2. Hu et al. (2024) X. Hu, F. Zhang, S. Chen, and Z. Yang Unveiling the statistical foundations of chain-of-thought prompting methods. arXiv preprint arXiv:2408.14511. Cited by: Appendix A, §6. Huang et al. (2024) A. Huang, A. Block, D. J. Foster, D. Rohatgi, C. Zhang, M. Simchowitz, J. T. Ash, and A. Krishnamurthy Self-improvement in language models: the sharpening mechanism. arXiv preprint arXiv:2412.01951. Cited by: §B.2, §6. Huang et al. (2025) A. Huang, A. Block, Q. Liu, N. Jiang, A. Krishnamurthy, and D. J. Foster Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. arXiv preprint arXiv:2503.21878. Cited by: Appendix A, §H.1, item 2., §1, §2, §2, §4.1, §4.3, §5. Ichihara et al. (2025) Y. Ichihara, Y. Jinnai, T. Morimura, K. Ariu, K. Abe, M. Sakamoto, and E. Uchibe Evaluation of best-of-n sampling strategies for language model alignment. arXiv preprint arXiv:2502.12668. Cited by: Appendix A, §1, §6. Jinnai et al. (2024) Y. Jinnai, T. Morimura, K. Ariu, and K. Abe Regularized best-of-n sampling to mitigate reward hacking for language model alignment. In ICML 2024 Workshop on Models of Human Feedback for AI Alignment, Cited by: Appendix A, §1, §6. Joag-Dev and Proschan (1983) K. Joag-Dev and F. Proschan Negative association of random variables with applications. The Annals of Statistics, p. 286–295. Cited by: Appendix F. Kang et al. (2025) Z. Kang, X. Zhao, and D. Song Scalable best-of-n selection for large language models via self-certainty. arXiv preprint arXiv:2502.18581. Cited by: Appendix A, §6. Kim et al. (2024) M. Kim, T. Thonet, J. Rozen, H. Lee, K. Jung, and M. Dymetman Guaranteed generation from large language models. arXiv preprint arXiv:2410.06716. Cited by: §6. Lee et al. (2025) H. Lee, S. Oh, J. Kim, J. Shin, and J. Tack Revise: learning to refine at test-time via intrinsic self-verification. arXiv preprint arXiv:2502.14565. Cited by: Appendix A. Lightman et al. (2023) H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe Let’s verify step by step. In The Twelfth International Conference on Learning Representations, Cited by: §1. Liu et al. (2025a) X. Liu, T. Liang, Z. He, J. Xu, W. Wang, P. He, Z. Tu, H. Mi, and D. Yu Trust, but verify: a self-verification approach to reinforcement learning with verifiable rewards. arXiv preprint arXiv:2505.13445. Cited by: Appendix A, Appendix A, §1, §6. Liu et al. (2025b) Z. Liu, Y. Chen, M. Shoeybi, B. Catanzaro, and W. Ping Acemath: advancing frontier math reasoning with post-training and reward modeling. In Findings of the Association for Computational Linguistics: ACL 2025, p. 3993–4015. Cited by: §H.2. Meister et al. (2020) C. Meister, R. Cotterell, and T. Vieira If beam search is the answer, what was the question?. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, p. 2173–2185. Cited by: Appendix A, §1, §6. Pinelis (2021) I. Pinelis Best lower bound on the probability of a binomial exceeding its expectation. Statistics & Probability Letters 179, p. 109224. Cited by: Appendix G. Setlur et al. (2024) A. Setlur, C. Nagpal, A. Fisch, X. Geng, J. Eisenstein, R. Agarwal, A. Agarwal, J. Berant, and A. Kumar Rewarding progress: scaling automated process verifiers for llm reasoning. arXiv preprint arXiv:2410.08146. Cited by: §1. Snell et al. (2024) C. Snell, J. Lee, K. Xu, and A. Kumar Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314. Cited by: §4.3. Stahlberg and Byrne (2019) F. Stahlberg and B. Byrne On nmt search errors and model errors: cat got your tongue?. In Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP), p. 3356–3362. Cited by: Remark 3. Sun et al. (2025a) Y. Sun, Y. Liang, Z. Zhang, and J. Teng Theoretical modeling of llm self-improvement training dynamics through solver-verifier gap. arXiv preprint arXiv:2507.00075. Cited by: Appendix A. Sun et al. (2025b) Z. Sun, Y. Guo, Y. Lin, X. Chen, Q. Qi, X. Tang, J. Wen, et al. Uncertainty and influence aware reward model refinement for reinforcement learning from human feedback. In The Thirteenth International Conference on Learning Representations, Cited by: §4.1. Team et al. (2023) G. Team, R. Anil, S. Borgeaud, J. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805. Cited by: §1. Wang et al. (2022) X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171. Cited by: Appendix A, §1, §6. Wang et al. (2026) Z. Wang, R. Wang, Y. Wu, Y. Yu, P. Zhang, S. Sun, Y. Yang, and Y. Li Reward modeling from natural language human feedback. arXiv preprint arXiv:2601.07349. Cited by: §4.1. Wei et al. (2022) J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35, p. 24824–24837. Cited by: Appendix A, §6. Wu et al. (2024) Y. Wu, Z. Sun, S. Li, S. Welleck, and Y. Yang Inference scaling laws: an empirical analysis of compute-optimal inference for problem-solving with language models. arXiv preprint arXiv:2408.00724. Cited by: §B.3. Xie et al. (2023) Y. Xie, K. Kawaguchi, Y. Zhao, J. X. Zhao, M. Kan, J. He, and M. Xie Self-evaluation guided beam search for reasoning. Advances in Neural Information Processing Systems 36, p. 41618–41650. Cited by: Appendix A, Appendix A, §1, §3, §6. Xu et al. (2025) Y. Xu, S. Ren, and J. Zhang Collaborative beam search: enhancing llm reasoning via collective consensus. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, p. 11409–11421. Cited by: Appendix A, §1, §6. Yang et al. (2025) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §H.2. Yao et al. (2023) S. Yao, D. Yu, J. Zhao, I. Shafran, T. Griffiths, Y. Cao, and K. Narasimhan Tree of thoughts: deliberate problem solving with large language models. Advances in neural information processing systems 36, p. 11809–11822. Cited by: §B.3. Yu et al. (2025a) F. Yu, Y. Li, and B. Wang Scaling flaws of verifier-guided search in mathematical reasoning. arXiv preprint arXiv:2502.00271. Cited by: Appendix A, Appendix A, §1, §3. Yu et al. (2025b) Y. Yu, Z. Chen, A. Zhang, L. Tan, C. Zhu, R. Y. Pang, Y. Qian, X. Wang, S. Gururangan, C. Zhang, et al. Self-generated critiques boost reward modeling for language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 11499–11514. Cited by: §4.1. Yu et al. (2025c) Y. Yu, Q. Di, Q. Gu, and D. Zhou On the limits of test-time compute: sequential reward filtering for better inference. arXiv preprint arXiv:2512.04558. Cited by: Appendix A, §6. Zaharia et al. (2024) M. Zaharia, O. Khattab, L. Chen, J. Q. Davis, H. Miller, C. Potts, J. Zou, M. Carbin, J. Frankle, N. Rao, and A. Ghodsi The shift from models to compound ai systems. Note: https://bair.berkeley.edu/blog/2024/02/18/compound-ai-systems/ Cited by: §1. Zhao et al. (2025) X. Zhao, Z. Kang, A. Feng, S. Levine, and D. Song Learning to reason without external rewards. arXiv preprint arXiv:2505.19590. Cited by: Appendix A. Zhu et al. (2024) T. Zhu, K. Zhang, J. Xie, and Y. Su Deductive beam search: decoding deducible rationale for chain-of-thought reasoning. arXiv preprint arXiv:2401.17686. Cited by: Appendix A, §1, §6. Table 1: Summary of Notations Used in the Paper Notation Description πref(⋅|x) _ref(·|x) a fixed LLM model that maps →Δ(L)X→ (A^L) L Response length (horizon) of y=(a1,…,aL)y=(a_1,…,a_L). a An action/token from the vocabulary A. sts_t Prefix (trajectory) up to step t: st=(a1,…,at)s_t=(a_1,…,a_t). b Beam width, i.e., the number of trajectories retained at each step. B Test-time compute budget, i.e., the total number of samples drawn from πref _ref. N Number of samples drawn per prefix st∈ℬts_t _t at each step. tD_t Candidate set after confidence filtering at step t. ℬtB_t Beam set at step t, consisting of at most b selected prefixes (i.e., |ℬt|≤b|B_t|≤ b). Q(st)Q(s_t) Estimated score of prefix sts_t, e.g., Q(st)=∑i=1tlogπ^(ai∣si−1,x)Q(s_t)= _i=1^t π(a_i s_i-1,x). κ Prefix gap parameter between optimal and suboptimal trajectories; see Assumption 3. ϵRM2 _RM^2 Reward-model estimation error; see Assumption 1. ϵopt _opt Reward-model error on the optimal response; see Assumption 2. Ct⋆(x)C_t (x), Cmax⋆(x)C_ (x), C¯(x) C(x) Coverage coefficients; see Definition 1. βt _t Confidence-filtering threshold at step t. Notations. We use Bin(N,p)Bin(N,p) to denote the binomial distribution with parameters N∈ℕ+N ^+ and p∈[0,1]p∈[0,1]. Appendix A Related Works Test-time computing. Beyond post-training scaling laws, recent work has increasingly focused on scaling computation at inference time to improve the quality of a fixed base model. Existing work mainly falls into two approaches: parallel and sequential test-time computation. For parallel methods, the compute budget is used to generate multiple candidate trajectories simultaneously, increasing the probability of finding a high-quality response. Existing such type of methods include Best-of-N (BoN) (Huang et al., 2025; Jinnai et al., 2024; Ichihara et al., 2025), majority voting (Wang et al., 2022; Kang et al., 2025), and beam search (Xie et al., 2023; Yu et al., 2025a). In sequential test-time computation, computation is allocated adaptively through iterative refinement or search, using methods like Chain-of-Thought (Wei et al., 2022; Ghosal et al., 2025; Hu et al., 2024) and self-verification (Liu et al., 2025a; Lee et al., 2025). Some recent studies aimed to bridge the gap between existing test-time computation methods. Di et al. (2025) proposes Best-of-Majority, which used majority voting as a filtering mechanism and an external reward model to select the final answer. Yu et al. (2025c) included a sequential technique for BoN sampling. The beam search method we study here mainly falls into the first category, since candidates are generated in parallel rather than sequentially. Beam search. Beam search algorithms have been widely used as a decoding strategy for large language models. Xu et al. (2025) and Xie et al. (2023) mainly used self-consistency as the evaluation metric for top-b selection; Zhu et al. (2024) introduced beam search to increase the successful rate of chain of thought; Yu et al. (2025a) empirically compared beam search algorithms with the methods like BoN and majority voting, and pointed out the weakness and strengths of beam search-based algorithms. Despite the empirical success of beam search and its many variants, there has been rather limited theoretical studies of beam search algorithms. Meister et al. (2020) studied what implicit objective function beam search optimizes. A recent work Fadeeva et al. (2025) studied beam search for consistency-based uncertainty quantification and provided a theoretical comparison between beam-based candidate generation and multinomial sampling estimators. To our best knowledge, there has not been any work theoretically analyzing the test-time scaling performance of beam search. Our work provides the first test-time computing guarantee for beam-search decoding algorithms in modern LLM settings. Self-consistency. Self-consistency improves reasoning by sampling multiple independent solution paths and selecting the answer that appears most consistently across them. Existing works have demonstrated the effectiveness of self-consistency, when it is used in self-evaluated post-training (Fadeeva et al., 2025; Liu et al., 2025a; Zhao et al., 2025; Sun et al., 2025a) and test-time computing (Aggarwal et al., 2023; Chen et al., 2023). Cordero-Encinar and Duncan (2025); Feng et al. (2025) and Aeeneh et al. (2024) provided theoretical analysis of the convergence rate of self-consistency methods. Our CF-Beam is related to self-consistency methods in that it uses a self-consistency score to prune beams at intermediate steps. Appendix B Discussion of Assumptions and Computational Costs We clarify how response uniqueness and prefix competitiveness enter our guarantees, and distinguish the sampling budget from the cost of maintaining and processing candidate prefixes. B.1 Uniqueness of the Optimal Response Assumption 2 makes the optimal response unique to simplify the path-based presentation. The analysis can accommodate several reward-optimal responses by tracking one that satisfies the required prefix and reward-model error conditions. As seen in the following remark. Remark 1 (Multiple reasoning trajectories leading to the same answer). Multiple reasoning trajectories yielding the same correct answer are a special case of nonunique reward-optimal responses. Let ⋆(x):=y∈L:r⋆(x,y)=1Y (x):=\y ^L:r (x,y)=1\ be nonempty, and fix an optimal witness y†=(a1†,…,aL†)∈⋆(x)y =(a_1 ,…,a_L ) (x) with prefixes st†:=a1:t†s_t :=a_1:t . Suppose Assumption 3 holds with st⋆s_t replaced by st†s_t , and |r⋆(x,y†)−r^(x,y†)|≤ϵopt(x)|r (x,y )- r(x,y )|≤ _opt(x). The prefix gap must hold against every distinct competing prefix, including prefixes of other correct trajectories. Define Ct†(x):=1/πref(at†∣st−1†,x)C_t (x):=1/ _ref(a_t s_t-1 ,x), Cmax†(x):=maxtCt†(x)C_ (x):= _tC_t (x), and C¯†(x):=∏t=1LCt†(x) C (x):= _t=1^LC_t (x). With oracle thresholds βt=(1−1/L)/Ct†(x) _t=(1-1/L)/C_t (x), the guarantees in Theorem 2 and Corollary 1 extend under Assumption 1 and the same sample-size conditions, with the optimal path and its coverage coefficients replaced by those of the witness. The filtering and ranking arguments track this path, and, on its survival event, the selected response y y satisfies r^(x,y^)≥r^(x,y†) r(x, y)≥ r(x,y ), so the reward-error argument applies with y†y as an optimal comparator. This extension does not exploit the aggregate probability mass or shared-prefix structure of all correct trajectories; sharper bounds that do so remain an interesting direction. B.2 Prefix Competitiveness and Its Relaxation Assumption 3 formalizes alignment between the likelihood of an optimal prefix and the final outcome reward. A correct trajectory can be difficult to sample in full because of limited token-level coverage or a long horizon, while its prefixes still have a likelihood advantage over competing prefixes. This is the regime in which likelihood-based pruning can exploit token-level coverage without sampling the entire trajectory independently. When the base policy instead assigns higher likelihood to suboptimal prefixes, intermediate pruning can irreversibly discard the optimal trajectory. Proposition 1 exhibits such an instance with a constant failure probability for every sample size. Thus, increasing the sampling budget alone cannot compensate for arbitrary misalignment between policy likelihood and outcome reward. Sequence-level methods such as Best-of-N or majority voting may be more competitive in these regimes because they postpone selection until complete responses are available (Huang et al., 2024); the relative benefit of beam search depends on the instance. Remark 2 (Relaxing prefix competitiveness). For reward-based CF-Beam, the gap condition can allow a limited number of exceptions. Suppose that, at each depth, at most k−1k-1 distinct competing prefixes violate the gap inequality relative to the optimal prefix, where 1≤k≤b1≤ k≤ b, and every other competing prefix satisfies the same lower bound κ. If the optimal prefix passes filtering but is pruned, at least b−k+1b-k+1 competitors satisfying the gap inequality must match or exceed its empirical score. Restricting the probability-mass sum in Lemma 5 to these competitors gives the same ranking bound with b replaced by b−k+1b-k+1. The filtering and selected-output bounds remain unchanged, so Theorem 2 extends with this replacement in the ranking term. We use the top-1 condition in the main text for simplicity. The reward-free final selection in Corollary 2 still requires the top-1 gap: a higher-likelihood suboptimal response could otherwise be selected even with exact scores. B.3 Sampling Budget and Candidate Processing Remark 3 (Beam expansion and query cost). At each depth, Algorithm 3 samples N next tokens for each active prefix, applies confidence filtering, and then retains at most b candidate prefixes. Consequently, |ℬt|≤b|B_t|≤ b and, since the initial beam contains only the empty prefix, the total query budget satisfies B(x)≤N+(L−1)bNB(x)≤ N+(L-1)bN. Before top-b pruning, the candidate pool at depth t contains at most N|ℬt−1|≤bN|B_t-1|≤ bN children; confidence filtering can only shrink this pool and introduces no additional branching. Thus, for fixed N and b, both the number of sampling queries and the number of processed candidates grow linearly in L, whereas the full output space has size ||L|A|^L, which makes exhaustive search intractable (Stahlberg and Byrne, 2019). These bounds count token-level policy draws, as defined in Section 2. They are not direct measures of neural-network forward passes, wall-clock latency, or KV-cache memory. For instance, when the model is run locally, the N draws at a common prefix can be generated from a single forward pass, whereas under pure API access each draw may constitute a separate call; actual costs further depend on batching and cache management. Comparisons with tree-search methods such as Tree-of-Thoughts or MCTS-based decoding (Yao et al., 2023; Feng et al., 2023; Wu et al., 2024) therefore require specifying both the search configuration and the cost measure. Appendix C Proof of Theorem 1 Proof of Theorem 1. We consider the following LLM instance, where 50≤Ci⋆(x):=C⋆(x)≪(||)1/450≤ C_i (x):=C (x) (|A|)^1/4. For time step t=1t=1, there exists a unique optimal action a1⋆a _1 with πref(a1⋆∣x)=1C⋆(x), _ref(a_1 x)= 1C (x), and all other actions a′∈\a1⋆a \a_1 \ have equal probability πref(a′|x)=1−1/C⋆(x)||−1. _ref(a |x)= 1-1/C (x)|A|-1. For time step t=2t=2, conditioned on the optimal prefix a1⋆a_1 , the next-step distribution satisfies πref(a2⋆∣a1⋆,x)=1C⋆(x),πref(a2′∣a1⋆,x)=1−1/C⋆(x)||−1, _ref(a_2 a_1 ,x)= 1C (x), _ref(a_2 a_1 ,x)= 1-1/C (x)|A|-1, where a2′∈\a2⋆a_2 \a_2 \. Otherwise, if conditioned on any suboptimal prefix a1′≠a1⋆a_1 ≠ a_1 , there exist two actions a2,1⋆a _2,1 and a2,2⋆a_2,2 , such that πref(a2,1⋆∣a1′,x)=πref(a2,2⋆∣a1′,x)=12,πref(a2′∣a1′,x)=0, _ref(a_2,1 a_1 ,x)= _ref(a_2,2 a_1 ,x)= 12, _ref(a_2 a_1 ,x)=0, where a2′∈\a2,1⋆,a2,2⋆a_2 \a_2,1 ,a_2,2 \. Notice that this constructed πref _ref does not violate our Assumption 3, since πref(s2⋆)=1/(C⋆(x))2≥1/(2(||−1))>πref(s2′) _ref(s _2)=1/(C (x))^2≥ 1/(2(|A|-1))> _ref(s_2 ) for any s2′≠s2⋆s_2 ≠ s _2. For time step t>2t>2, we let πref(⋅|st−1,x) _ref(·|s_t-1,x) be any distribution such that Assumption 3 holds. Case 1: N≤34N≤ 34. Under this case, we show that the probability that the optimal prefix will not even be sampled is at least 1/21/2: Pr(y⋆ is eliminated) (y is eliminated) ≥Pr(y⋆ is eliminated in the first round) ≥ (y is eliminated in the first round) ≥(1−1C⋆(x))N≥(4950)34>0.5. ≥ (1- 1C (x) )^N≥ ( 4950 )^34>0.5. Case 2: N≥35N≥ 35. Before proceeding, we define the following events. Let E1E_1 denote the event that the optimal trajectory s⋆s is eliminated in the first round, and let E2E_2 denote the event that s⋆s is eliminated in the second round. Let ℬ1B_1 be the top-b beam (candidate set) retained after the first round, and define B⋆:=|ℬ1|=bB_ \;:=\; \\,|B_1|=b\, which implies the event that we sample at least b distinct trajectories from x. By the definition of our events, we have Pr(s⋆ is eliminated) (s is eliminated) =Pr(E1)+Pr(E1c)Pr(E2|E1c) = (E_1)+ (E_1^c) (E_2|E_1^c) ≥Pr(E1)+Pr(E1c)Pr((E2∩B⋆)|E1c) ≥ (E_1)+ (E_1^c) ((E_2∩ B_ )|E_1^c) =Pr(E1)+Pr(E1c)Pr(B⋆|E1c)Pr(E2|(B⋆∩E1c)) = (E_1)+ (E_1^c) (B_ |E_1^c) (E_2|(B_ ∩ E_1^c)) ≥Pr(E1)Pr(B⋆|E1c)Pr(E2|(B⋆∩E1c)) ≥ (E_1) (B_ |E_1^c) (E_2|(B_ ∩ E_1^c)) +(1−Pr(E1))Pr(B⋆|E1c)Pr(E2|(B⋆∩E1c)) +(1- (E_1)) (B_ |E_1^c) (E_2|(B_ ∩ E_1^c)) =Pr(B⋆|E1c)Pr(E2|(B⋆∩E1c)). = (B_ |E_1^c) (E_2|(B_ ∩ E_1^c)). We next bound each of the term correspondingly. 2.1 Bounding Pr(B⋆∣E1c) (B_ E_1^c). Let K:=#samples equal a1⋆∼Bin(N,p),p:=πref(a1⋆∣x)=1/C⋆.K:=\#\samples equal a_1 \ (N,p), p:= _ref(a_1 x)=1/C . We first justify that suboptimal actions are (essentially) all distinct when the action space is large. Conditioned on K, there are N−KN-K suboptimal draws. Since by our construction, the suboptimal mass is sufficiently spread out (e.g., maxa≠a1⋆πref(a∣x)≤1/(||−1) _a≠ a_1 _ref(a x)≤ 1/(|A|-1)), then by a union bound, Pr(∃a repeated suboptimal action∣K)≤(N−K2)maxa≠a1⋆πref(a∣x)≤N(N−1)2(||−1). \! (∃\,a repeated suboptimal action K )\;≤\; N-K2 _a≠ a_1 _ref(a x)\;≤\; N(N-1)2(|A|-1). Hence, under the regime ||≫N2|A| N^2, the above collision probability is negligible. In the sequel, we work on this high-probability “no-collision” event, so that the N−KN-K suboptimal samples correspond to N−KN-K distinct suboptimal actions. Step 1: Relating E1cE_1^c and K. Under the no-collision condition, every suboptimal action appears at most once, and hence has empirical frequency 1/N1/N. If K≥2K≥ 2, then a1⋆a_1 appears at least twice and thus has empirical frequency at least 2/N2/N, strictly larger than any suboptimal action. Therefore, a1⋆a_1 must be retained in the top-b set after the first round, i.e., K≥2⊆E1c.\K≥ 2\ E_1^c. Step 2: Characterizing B⋆cB_ ^c. Recall B⋆B_ is the event that the first-round beam ℬ1B_1 is fully populated by b distinct candidates. On the no-collision event, there are exactly N−KN-K distinct suboptimal candidates available. Since one slot is occupied by the optimal prefix (on E1cE_1^c), the beam fails to be fully populated only if there are fewer than b−1b-1 distinct suboptimal candidates, namely, B⋆c⊆N−K<b−1.B_ ^c\; \;\\,N-K<b-1\,\. Consequently, Pr(B⋆c∣E1c)=Pr(B⋆c∩E1c)Pr(E1c)≤Pr(N−K<b−1)Pr(E1c)≤Pr(N−K<b−1)Pr(K≥2), (B_ ^c E_1^c)= (B_ ^c∩ E_1^c) (E_1^c)\;≤\; (N-K<b-1) (E_1^c)\;≤\; (N-K<b-1) (K≥ 2), where the last inequality follows because K≥2⊆E1c\K≥ 2\ E_1^c. Step 3: Bounding the ratio. If b≤N/2b≤ N/2, then N−K<b−1N-K<b-1 implies K≥N−b+2≥⌈N/2⌉K≥ N-b+2≥ N/2 . Hence Pr(B⋆c∣E1c)≤Pr(K≥⌈N/2⌉)Pr(K≥2). (B_ ^c E_1^c)≤ (K≥ N/2 ) (K≥ 2). For the numerator, since p<1p<1, Pr(K≥⌈N/2⌉)=∑k=⌈N/2⌉N(Nk)pk(1−p)N−k≤∑k=⌈N/2⌉N(Nk)pk≤pN/2∑k=0N(Nk)=2NpN/2. (K≥ N/2 )= _k= N/2 ^N Nkp^k(1-p)^N-k≤ _k= N/2 ^N Nkp^k≤ p^N/2 _k=0^N Nk=2^Np^N/2. For the denominator, we lower bound Pr(K≥2) (K≥ 2) by a single term: Pr(K≥2)≥Pr(K=2)=(N2)p2(1−p)N−2. (K≥ 2)≥ (K=2)= N2p^2(1-p)^N-2. Combining the above together yields Pr(B⋆c∣E1c)≤2NpN/2(N2)p2(1−p)N−2=2N(N2)⋅pN2−2(1−p)N−2=:f(N,p). (B_ ^c E_1^c)≤ 2^Np^N/2 N2p^2(1-p)^N-2= 2^N N2· p N2-2(1-p)^N-2=:f(N,p). In particular, for any fixed p≤1/50p≤ 1/50, f(N,p)f(N,p) is monotonically decreasing with N. For any fixed N, f(N,p)f(N,p) is monotonically increasing with p. Then we have f(N,p)≤f(35,p)≤f(35,1/50)≤235(352)⋅(1/50)352−2(49/50)35−2≤5.21×10−19.f(N,p)≤ f(35,p)≤ f(35,1/50)≤ 2^35 352· (1/50) 352-2(49/50)^35-2≤ 5.21× 10^-19. As a result Pr(B⋆c∣E1c)≤f(35)≤5.21×10−19. (B_ ^c E_1^c)≤ f(35)≤ 5.21× 10^-19. Therefore, Pr(B⋆∣E1c)=1−Pr(B⋆c∣E1c)≥1−5.21×10−19≈1. (B_ E_1^c)=1- (B_ ^c E_1^c)≥ 1-5.21× 10^-19≈ 1. Interpretation. Under a large action space, suboptimal samples are almost surely all distinct. So the only way for the top-b beam ℬ1B_1 to not be fully populated by b distinct candidates is that the optimal action a1⋆a_1 is sampled too many times (so that N−KN-K is too small to provide b−1b-1 distinct suboptimal candidates). Since K∼Bin(N,p)K (N,p) with small p=1/C⋆p=1/C , such a large-deviation event K≥N/2K≥ N/2 has exponentially small probability, leading to Pr(B⋆∣E1c)≈1 (B_ E_1^c)≈ 1, which implies that we sample at least b distinct trajectories from x almost surely. 2.2 Bounding Pr(E2∣B⋆∩E1c) (E_2 B ∩ E_1^c). For the analysis in this part, we introduce an auxiliary path-likelihood quantity Q~(st):=∏i=1tπ^(ai∣si−1,x), Q(s_t)\;:=\; _i=1^t π(a_i s_i-1,x), which differs from the additive score Q(⋅)Q(·) used by the algorithm in Section 3 and is used solely within this proof. We further define the good event ℰE as ℰ:=Q~(s2⋆)<14N∩∃at least b suboptimal trajectories s2′∈2 such that Q~(s2′)≥14N,E:= \\, Q(s_2 )< 14N\, \∩ \∃\,at least b suboptimal trajectories s_2 _2 such that Q(s_2 )≥ 14N \, where 2S_2 is the set of all trajectories generated by ℬ1B_1. We first control the score of the optimal trajectory under the same conditioning used in this subsection. Let K1:=Nπ^(a1⋆∣x),K2:=Nπ^(a2⋆∣a1⋆,x).K_1:=N π(a_1 x), K_2:=N π(a_2 a_1 ,x). The event B⋆∩E1cB ∩ E_1^c is determined by the first-round samples, whereas K2K_2 is generated from the second-round samples at the optimal prefix. Hence, conditional on K1K_1, the random variable K2K_2 remains independent of B⋆∩E1cB ∩ E_1^c and satisfies K2∼Bin(N,1/C⋆(x)).K_2 \! (N,1/C (x) ). Moreover, Q~(s2⋆)=π^(a1⋆∣x)π^(a2⋆∣a1⋆,x)=K1K2N2. Q(s_2 )= π(a_1 x) π(a_2 a_1 ,x)= K_1K_2N^2. Therefore, by Markov’s inequality, Pr(Q~(s2⋆)≥14N|B⋆∩E1c)=Pr(K1K2≥N4|B⋆∩E1c)≤[K1K2∣B⋆∩E1c]N/4. \! ( Q(s_2 )≥ 14N\, |\,B ∩ E_1^c )= \! (K_1K_2≥ N4\, |\,B ∩ E_1^c )≤ E\! [K_1K_2 B ∩ E_1^c ]N/4. It remains to control the conditional expectation in the numerator. Since K2K_2 is independent of the first-round samples and [K2]=N/C⋆(x)E[K_2]=N/C (x), we have [K1K2∣B⋆∩E1c]=[K1∣B⋆∩E1c]NC⋆(x).E\! [K_1K_2 B ∩ E_1^c ]=E\! [K_1 B ∩ E_1^c ] NC (x). On the no-collision event considered in Section 2.1, the event E1cE_1^c can only add outcomes with K1=1K_1=1 beyond the event K1≥2\K_1≥ 2\, while the event B⋆B only removes outcomes with too many repeated samples of the optimal action. Hence [K1∣B⋆∩E1c]≤[K1∣K1≥2].E\! [K_1 B ∩ E_1^c ] \! [K_1 K_1≥ 2 ]. For a binomial random variable, conditioning on at least two successes is stochastically dominated by adding two deterministic successes to an independent binomial count over the remaining trials. Thus [K1∣K1≥2]≤2+NC⋆(x)≤2+C⋆(x)16≤C⋆(x)9,E\! [K_1 K_1≥ 2 ]≤ 2+ NC (x)≤ 2+ C (x)16≤ C (x)9, where the second inequality uses N≤(C⋆(x))2/16N≤(C (x))^2/16, and the last one uses C⋆(x)≥50C (x)≥ 50. Therefore, [K1K2∣B⋆∩E1c]≤N9,E\! [K_1K_2 B ∩ E_1^c ]≤ N9, and consequently Pr(Q~(s2⋆)<14N|B⋆∩E1c)≥1−49=59. \! ( Q(s_2 )< 14N\, |\,B ∩ E_1^c )≥ 1- 49= 59. (10) Next, we control the second event in ℰE. For any suboptimal prefix a∈ℬ1a _1, conditioned on B⋆∩E1cB ∩ E_1^c, its second-step distribution has two possible offspring, s2,1′=(a,a2,1⋆)s_2,1 =(a,a_2,1 ) and s2,2′=(a,a2,2⋆)s_2,2 =(a,a_2,2 ), satisfying πref(a2,1⋆∣a,x)=πref(a2,2⋆∣a,x)=12. _ ref(a_2,1 a,x)= _ ref(a_2,2 a,x)= 12. We can bound the probability that both generated trajectories have sufficiently large likelihood as follows: Pr(Q~(s2,1′)>14N,Q~(s2,2′)>14N|B⋆∩E1c) \! ( Q(s_2,1 )> 14N, Q(s_2,2 )> 14N\, |\,B ∩ E_1^c ) =Pr(π^(a2,1⋆∣a,x)π^(a∣x)>14N,π^(a2,2⋆∣a,x)π^(a∣x)>14N|B⋆∩E1c) = \! ( π(a_2,1 a,x) π(a x)> 14N, π(a_2,2 a,x) π(a x)> 14N\, |\,B ∩ E_1^c ) ≥Pr(π^(a2,1⋆∣a,x)>14,π^(a2,2⋆∣a,x)>14) ≥ \! ( π(a_2,1 a,x)> 14, π(a_2,2 a,x)> 14 ) =Pr(14<π^(a2,1⋆∣a,x)<34) = \! ( 14< π(a_2,1 a,x)< 34 ) =1−Pr(|π^(a2,1⋆∣a,x)−12|≥14) =1- \! ( | π(a_2,1 a,x)- 12 |≥ 14 ) ≥1−2exp(−N8), ≥ 1-2 \! (- N8 ), where the first inequality holds because every selected first-step prefix has empirical probability at least 1/N1/N, i.e., π^(a∣x)≥1/N π(a x)≥ 1/N; the second equality follows from π^(a2,1⋆∣a,x)+π^(a2,2⋆∣a,x)=1 π(a_2,1 a,x)+ π(a_2,2 a,x)=1; and the last inequality follows from Hoeffding’s inequality applied to Nπ^(a2,1⋆∣a,x)∼Bin(N,1/2)N π(a_2,1 a,x) (N,1/2). Then, at the second step, for each such suboptimal prefix s1∈ℬ1s_1 _1, let (s1) Succ(s_1) denote the event that its two offspring trajectories s2,1′s_2,1 and s2,2′s_2,2 satisfy Q~(s2,1′)≥1/(4N),Q~(s2,2′)≥1/(4N). Q(s_2,1 )≥1/(4N),\ Q(s_2,2 )≥1/(4N). By construction, Pr((s1)∣B⋆∩E1c)≥1−2exp(−N/8), \! ( Succ(s_1) B ∩ E_1^c )≥ 1-2 \! (-N/8 ), and these events are independent across different suboptimal prefixes. Hence the number of successful suboptimal prefixes conditioned on B⋆∩E1cB ∩ E_1^c stochastically dominates Z∼Bin(b−1, 1−2exp(−N8)).Z \! (b-1,\,1-2 \! (- N8 ) ). In particular, there exists b suboptimal trajectories s2′s_2 such that Q~(s2′)≥1/(4N) Q(s_2 )≥ 1/(4N) is implied by Z≥⌈b/2⌉\Z≥ b/2 \, and therefore Pr(∃ at least b suboptimal trajectories s2′ with Q~(s2′)≥14N|B⋆∩E1c) \! (∃ at least b suboptimal trajectories s _2 with Q(s _2)≥ 14N\, |\,B ∩ E_1^c ) ≥Pr(Z≥⌈b2⌉)=Pr(Bin(b−1, 1−2exp(−N8))≥⌈b2⌉). ≥ \! (Z≥ b2 )= \! (Bin\! (b-1,\,1-2 \! (- N8 ) )≥ b2 ). (11) By Lemma 1 (see Appendix C.1), the above binomial tail probability is nondecreasing along the even subsequence b=2,4,6,…\b=2,4,6,…\ and along the odd subsequence b=3,5,7,…\b=3,5,7,…\. Consequently, Pr(Bin(b−1, 1−2exp(−N8))≥⌈b2⌉) \! (Bin\! (b-1,\,1-2 \! (- N8 ) )≥ b2 ) ≥minPr(Bin(1, 1−2exp(−N8))≥1),Pr(Bin(2, 1−2exp(−N8))≥2) ≥ \! \ \! (Bin\! (1,\,1-2 \! (- N8 ) )≥ 1 ), . . \! (Bin\! (2,\,1-2 \! (- N8 ) )≥ 2 ) \ =(1−2exp(−N8))2. = (1-2 \! (- N8 ) )^2. (12) Using a union bound under the conditioning B⋆∩E1cB ∩ E_1^c, we obtain Pr(ℰ∣B⋆∩E1c)≥(1−2exp(−N8))2−49. \! (E B ∩ E_1^c )≥ (1-2 \! (- N8 ) )^2- 49. Since N≥35N≥ 35 in Case 2, we have (1−2exp(−N8))2−49≥(1−2exp(−358))2−49=0.506 (1-2 \! (- N8 ) )^2- 49≥ (1-2 \! (- 358 ) )^2- 49=0.506 Under the good event ℰE, there exist at least b suboptimal trajectories s2′s_2 such that Q~(s2⋆)<14N≤Q~(s2′). Q(s_2 )< 14N≤ Q(s_2 ). Therefore, the optimal response is crowded out of the top-b candidates by b suboptimal trajectories. Combining this result with the bound of Pr(B⋆∣E1c) (B E_1^c) yields Pr(s⋆ is eliminated)≥0.5. (s is eliminated)≥ 0.5. The proof is completed. ∎ C.1 Technical Lemmas In the subsection, we show that Pr(Bin(b−1,p)≥b2) \! (Bin(b-1,p)≥ b2 ) is monotone along the odd and even subsequences of b, respectively. This result is useful in bounding Equation (11) in the proof of Theorem 1. Lemma 1 (Monotonicity in b for odd/even subsequences). Let N>30N>30 and let p:=1−4N>12p:=1- 4N> 12. Define, for integers b≥2b≥ 2, F(b):=Pr(Bin(b−1,p)≥b2),F(b):= \! (Bin(b-1,p)≥ b2 ), where for odd b the threshold is understood in the usual way: Bin(b−1,p)≥b/2=Bin(b−1,p)≥⌈b/2⌉\Bin(b-1,p)≥ b/2\=\Bin(b-1,p)≥ b/2 \. Then F(b)F(b) is nondecreasing along the even subsequence b=2,4,6,…\b=2,4,6,…\ and also nondecreasing along the odd subsequence b=3,5,7,…\b=3,5,7,…\. In particular, F(2)≤F(4)≤F(6)≤⋯,F(3)≤F(5)≤F(7)≤⋯.F(2)≤ F(4)≤ F(6)≤·s, F(3)≤ F(5)≤ F(7)≤·s. Proof. Fix p>12p> 12. We consider the following two cases. Even b. Let b=2kb=2k with k≥1k≥ 1 and let Sk∼Bin(2k−1,p)S_k (2k-1,p). Then F(2k)=Pr(Sk≥k)F(2k)= (S_k≥ k). We further have Sk+1=Sk+B1+B2,S_k+1=S_k+B_1+B_2, where B1,B2∼i.i.d.Bern(p)B_1,B_2 i.i.d. Bern(p) are independent of SkS_k. A direct decomposition over Sk∈k−1,k,≥k+1S_k∈\k-1,k,≥ k+1\ gives F(2k+2)−F(2k)=−(1−p)2Pr(Sk=k)+p2Pr(Sk=k−1).F(2k+2)-F(2k)=-(1-p)^2 (S_k=k)+p^2 (S_k=k-1). For Sk∼Bin(2k−1,p)S_k (2k-1,p), Pr(Sk=k)Pr(Sk=k−1)=(2k−1k)(2k−1k−1)⋅p1−p=k⋅p1−p=p1−p. (S_k=k) (S_k=k-1)= 2k-1k 2k-1k-1· p1-p= kk· p1-p= p1-p. Hence Pr(Sk=k−1)=Pr(Sk=k)1−p (S_k=k-1)= (S_k=k) 1-pp. Substituting yields F(2k+2)−F(2k)=Pr(Sk=k)(1−p)(2p−1)≥0,F(2k+2)-F(2k)= (S_k=k)\,(1-p)\,(2p-1)≥ 0, which implies that F(2k)k≥1\F(2k)\_k≥ 1 is nondecreasing. Odd b. Let b=2k+1b=2k+1 with k≥1k≥ 1 and let Tk∼Bin(2k,p)T_k (2k,p). Then F(2k+1)=Pr(Tk≥k+1)F(2k+1)= (T_k≥ k+1). We then have Tk+1=Tk+B1+B2T_k+1=T_k+B_1+B_2 with the same B1,B2B_1,B_2. Similarly, F(2k+3)−F(2k+1)=−(1−p)2Pr(Tk=k+1)+p2Pr(Tk=k).F(2k+3)-F(2k+1)=-(1-p)^2 (T_k=k+1)+p^2 (T_k=k). For Tk∼Bin(2k,p)T_k (2k,p), Pr(Tk=k+1)Pr(Tk=k)=(2k+1)(2k)⋅p1−p=k+1⋅p1−p. (T_k=k+1) (T_k=k)= 2kk+1 2kk· p1-p= kk+1· p1-p. Hence, Pr(Tk=k)=Pr(Tk=k+1)k+1k1−p (T_k=k)= (T_k=k+1) k+1k 1-pp. Therefore, F(2k+3)−F(2k+1)=Pr(Tk=k+1)(1−p)(k+1kp−(1−p)).F(2k+3)-F(2k+1)= (T_k=k+1)\,(1-p) ( k+1kp-(1-p) ). Since p>12p> 12 implies k+1kp≥p>1−p k+1kp≥ p>1-p, the bracketed term is positive. Hence, F(2k+3)≥F(2k+1)F(2k+3)≥ F(2k+1) for all k≥1k≥ 1. This proves monotonicity on both subsequences. Finally, the assumption N>30N>30 ensures p=1−4N>12p=1- 4N> 12, and hence the above applies. ∎ Appendix D Proof of Proposition 1 Proof of Proposition 1. We exhibit an instance with horizon L=1L=1 that violates Assumption 3 and bound the survival probability of y⋆y via Markov’s inequality. Construction. Let =a⋆,a1,…,a||−1A=\a ,a_1,…,a_|A|-1\ and define πref(a⋆∣x)=18,πref(a1∣x)=78,πref(ai∣x)=0for i≥2. _ref(a x)= 18, _ref(a_1 x)= 78, _ref(a_i x)=0\;\;for i≥ 2. Set the ground-truth reward as r⋆(x,a⋆)=1r (x,a )=1 and r⋆(x,a)=0r (x,a)=0 for all a≠a⋆a≠ a , so that y⋆=a⋆y =a is the unique optimal response. Violation of Assumption 3. At depth t=1t=1, the suboptimal prefix s=a1≠s1⋆=a⋆s=a_1≠ s_1 =a satisfies log(πref(a⋆∣x)πref(a1∣x))=log1/87/8=−log7<0, \! ( _ref(a x) _ref(a_1 x) )= 1/87/8=- 7<0, so no κ>0κ>0 can satisfy the prefix-competitiveness condition on this instance. Survival probability. Fix any N≥1N≥ 1. Let X⋆:=Nπ^(a⋆∣x)∼Bin(N,18),X1:=Nπ^(a1∣x)∼Bin(N,78).X :=N\, π(a x) \! (N, 18 ), X_1:=N\, π(a_1 x) \! (N, 78 ). Since a⋆a and a1a_1 are the only tokens with positive mass under πref(⋅∣x) _ref(· x), we have X⋆+X1=NX +X_1=N almost surely. With b=1b=1, the algorithm retains the sampled candidate with the largest score Q(a)=Q(s0)+logπ^(a∣x)=logπ^(a∣x)Q(a)=Q(s_0)+ π(a x)= π(a x). Since the logarithm is strictly increasing, this is equivalent to retaining the candidate with the largest empirical frequency π^(a∣x) π(a x). Hence y⋆=a⋆y =a is retained in the final beam only if π^(a⋆∣x)≥π^(a1∣x) π(a x)≥ π(a_1 x), equivalently X⋆≥X1X ≥ X_1. Since X⋆+X1=NX +X_1=N, this is equivalent to X⋆≥N/2X ≥ N/2. Applying Markov’s inequality to the nonnegative random variable X⋆X with [X⋆]=N/8E[X ]=N/8, Pr(X⋆≥N2)≤[X⋆]N/2=N/8N/2=14. \! (X ≥ N2 )\;≤\; E[X ]N/2\;=\; N/8N/2\;=\; 14. Consequently, Pr(y⋆ retained in the final beam)≤Pr(X⋆≥N2)≤14, (y retained in the final beam)\;≤\; \! (X ≥ N2 )\;≤\; 14, so the probability of pruning y⋆y is at least 1−14=341- 14= 34, completing the proof. ∎ Appendix E Regret Upper Bound: Proof of Theorem 2 and Corollary 2 E.1 Technical Lemmas: Filtering and Beam Survival We first control the distribution of the final output and the probability of filtering out an optimal action. We then bound moments of filtered score differences and use them to control the rank of the optimal prefix. The binomial moment inequalities used below are proved in Lemma 6 in the Auxiliary Lemmas section. Fix x throughout this section. As in Definition 2, independently generate an N-sample histogram at every prefix of depth less than L and reveal it only if the algorithm visits that prefix. Along a fixed path, these histograms belong to distinct nodes and are independent; paths with shared ancestors still have dependent scores. For a prefix st=(a1,…,at)s_t=(a_1,…,a_t), write ℱ(st):=π^(ai∣si−1,x)≥βi,i∈[t]F(s_t):=\ π(a_i s_i-1,x)≥ _i,\ i∈[t]\. On this event, Q(st)=∑i=1tlogπ^(ai∣si−1,x)Q(s_t)= _i=1^t π(a_i s_i-1,x) is finite. Expressions involving inverse empirical probabilities or differences of scores are defined to be zero outside the indicated filtering events. In particular, ℰβ=ℱ(sL⋆)E_β=F(s_L ). This construction is used only for analysis and does not change the algorithm’s queries. Lemma 2 (Output probabilities under confidence filtering). For any thresholds βi∈(0,1] _i∈(0,1] and any fixed y∈Ly ^L, the output ybeamy^beam of CF-Beam satisfies Pr(ybeam=y,ℰ)≤πref(y∣x)∏i=1Lβi−1. (y^beam=y,E)≤ _ref(y x) _i=1^L _i^-1. Proof. On ℰE, the final beam is nonempty, and any output y=(a1,…,aL)y=(a_1,…,a_L) has passed filtering along all its edges. Hence Pr(ybeam=y,ℰ) (y^beam=y,E) ≤Pr(ℱ(y))=∏i=1LPr(π^(ai∣si−1,x)≥βi) ≤ (F(y))= _i=1^L ( π(a_i s_i-1,x)≥ _i ) ≤∏i=1L[π^(ai∣si−1,x)]βi=πref(y∣x)∏i=1Lβi−1. ≤ _i=1^L E[ π(a_i s_i-1,x)] _i= _ref(y x) _i=1^L _i^-1. The equality uses independence of the histograms along the fixed path, and the inequality follows from Markov’s inequality and unbiasedness of each empirical frequency. The argument does not condition the histograms on the output-selection event. ∎ Lemma 3 (Optimal actions pass filtering). For βt=α/Ct⋆(x) _t=α/C_t (x) with 0<α<10<α<1, Pr(ℰβc)≤Lexp(−N(1−α)22Cmax⋆). (E_β^c)≤ L \! (- N(1-α)^22C_ ). Proof. For each t, the count Nπ^(at⋆∣st−1⋆,x)N π(a_t s_t-1 ,x) has distribution Bin(N,1/Ct⋆(x))Bin(N,1/C_t (x)). Applying the lower-tail Chernoff bound in Lemma 8 with relative deviation 1−α1-α, and then a union bound, gives Pr(ℰβc) (E_β^c) ≤∑t=1LPr(Nπ^(at⋆∣st−1⋆,x)<αNCt⋆(x)) ≤ _t=1^L (N π(a_t s_t-1 ,x)< α NC_t (x) ) ≤∑t=1Lexp(−N(1−α)22Ct⋆(x))≤Lexp(−N(1−α)22Cmax⋆). ≤ _t=1^L \! (- N(1-α)^22C_t (x) )≤ L \! (- N(1-α)^22C_ ). ∎ Lemma 4 (Moments of filtered score differences). Let βi=α/Ci⋆(x) _i=α/C_i (x) with 1/2≤α<11/2≤α<1. For every st≠st⋆s_t≠ s_t and integer 1≤r≤Nα/(4Cmax⋆)1≤ r≤ Nα/(4C_ ), [er(Q(st)−Q(st⋆))ℱ(st)∩ℱ(st⋆)]≤(πref(st∣x)πref(st⋆∣x))rexp(3tCmax⋆r2Nα).E\! [e^r(Q(s_t)-Q(s_t ))1_F(s_t) (s_t ) ]≤ ( _ref(s_t x) _ref(s_t x) )^r \! ( 3tC_ r^2Nα ). Proof. For each depth i, let Ki=⌈Nβi⌉≥Nα/Cmax⋆K_i= N _i ≥ Nα/C_ , so 2r≤Ki/22r≤ K_i/2. Apply the positive and inverse moment bounds of Lemma 6 with order 2r2r to each edge. Independence along each fixed path yields [e2rQ(st)ℱ(st)] \! [e^2rQ(s_t)1_F(s_t) ] ≤πref(st∣x)2rexp(∑i=1t(2r)(2r−1)2(Ki−2r+1)), ≤ _ref(s_t x)^2r \! ( _i=1^t (2r)(2r-1)2(K_i-2r+1) ), [e−2rQ(st⋆)ℱ(st⋆)] \! [e^-2rQ(s_t )1_F(s_t ) ] ≤πref(st⋆∣x)−2rexp(∑i=1t(2r)(2r+1)2Ki). ≤ _ref(s_t x)^-2r \! ( _i=1^t (2r)(2r+1)2K_i ). All optimal edge probabilities are positive by the finiteness of Cmax⋆C_ . A competing path of true probability zero has zero probability of passing filtering, so its contribution is zero. Cauchy–Schwarz now gives [er(Q(st)−Q(st⋆))ℱ(st)∩ℱ(st⋆)] \! [e^r(Q(s_t)-Q(s_t ))1_F(s_t) (s_t ) ] ≤([e2rQ(st)ℱ(st)][e−2rQ(st⋆)ℱ(st⋆)])1/2 ≤ (E[e^2rQ(s_t)1_F(s_t)]E[e^-2rQ(s_t )1_F(s_t )] )^1/2 ≤(πref(st∣x)πref(st⋆∣x))rexp[∑i=1t((2r)(2r−1)4(Ki−2r+1)+(2r)(2r+1)4Ki)] ≤ ( _ref(s_t x) _ref(s_t x) )^r \! [ _i=1^t ( (2r)(2r-1)4(K_i-2r+1)+ (2r)(2r+1)4K_i ) ] ≤(πref(st∣x)πref(st⋆∣x))rexp(∑i=1t3r2Ki)≤(πref(st∣x)πref(st⋆∣x))rexp(3tCmax⋆r2Nα). ≤ ( _ref(s_t x) _ref(s_t x) )^r \! ( _i=1^t 3r^2K_i )≤ ( _ref(s_t x) _ref(s_t x) )^r \! ( 3tC_ r^2Nα ). For the penultimate inequality, Ki−2r+1≥Ki/2K_i-2r+1≥ K_i/2 bounds the two terms by (2r2−r)/Ki(2r^2-r)/K_i and (r2+r/2)/Ki(r^2+r/2)/K_i, respectively. In particular, Cauchy–Schwarz controls the common optimal score and shared-prefix randomness without requiring independent path scores. ∎ Lemma 5 (Survival under top-b pruning). Suppose Assumption 3 holds, βi=α/Ci⋆(x) _i=α/C_i (x) with 1/2≤α<11/2≤α<1, and N≥48Cmax⋆κ2max2,log(2Cmax⋆)N≥ 48C_ κ^2 \2, (2C_ )\. Then Pr(ℰβ∩ℰbc)≤2Cmax⋆bexp(−κ2N48Cmax⋆). (E_β _b^c)≤ 2C_ b \! (- κ^2N48C_ ). More precisely, let ZtZ_t count the filtered nonoptimal prefixes in the full depth-t tree whose scores are at least Q(st⋆)Q(s_t ), and set Zt=0Z_t=0 if ℱ(st⋆)F(s_t ) fails. For every integer m≥1m≥ 1, Pr(Zt≥m)≤1m[Cmax⋆exp(−κ2N48Cmax⋆)]t. (Z_t≥ m)≤ 1m [C_ \! (- κ^2N48C_ ) ]^t. (13) Proof. For any admissible integer r≥1r≥ 1 in Lemma 4, each competitor counted by ZtZ_t contributes at least one to the corresponding likelihood-ratio moment. Since the depth-t tree is finite, summing the lemma gives [Zt] [Z_t] ≤∑st≠st⋆[er(Q(st)−Q(st⋆))ℱ(st)∩ℱ(st⋆)] ≤ _s_t≠ s_t E\! [e^r(Q(s_t)-Q(s_t ))1_F(s_t) (s_t ) ] ≤exp(3tCmax⋆r2Nα)∑st≠st⋆(πref(st∣x)πref(st⋆∣x))r ≤ \! ( 3tC_ r^2Nα ) _s_t≠ s_t ( _ref(s_t x) _ref(s_t x) )^r ≤exp(3tCmax⋆r2Nα−(r−1)tκ)∑st≠st⋆πref(st∣x)πref(st⋆∣x) ≤ \! ( 3tC_ r^2Nα-(r-1)tκ ) _s_t≠ s_t _ref(s_t x) _ref(s_t x) ≤[Cmax⋆exp(−(r−1)κ+3Cmax⋆r2Nα)]t. ≤ [C_ \! (-(r-1)κ+ 3C_ r^2Nα ) ]^t. The third line uses Assumption 3, which implies πref(st∣x)≤e−tκπref(st⋆∣x) _ref(s_t x)≤ e^-tκ _ref(s_t x), and r−1≥0r-1≥ 0. The last line uses total prefix probability at most one and πref(st⋆∣x)−1=∏i=1tCi⋆(x)≤(Cmax⋆)t _ref(s_t x)^-1= _i=1^tC_i (x)≤(C_ )^t. Thus the sum is controlled by true probability mass rather than by the number of adaptively selected candidates. Choose r=⌊Nακ/(6Cmax⋆)⌋r= Nακ/(6C_ ) . The sample-size condition and 1/2≤α<11/2≤α<1, 0<κ≤10<κ≤ 1 imply Nακ2/Cmax⋆≥48Nακ^2/C_ ≥ 48 and 1≤r≤Nα/(4Cmax⋆)1≤ r≤ Nα/(4C_ ). Using the two bounds on the floor function, −(r−1)κ+3Cmax⋆r2Nα -(r-1)κ+ 3C_ r^2Nα ≤−Nακ212Cmax⋆+2κ≤−Nακ224Cmax⋆≤−Nκ248Cmax⋆. ≤- Nακ^212C_ +2κ≤- Nακ^224C_ ≤- Nκ^248C_ . The middle inequality follows from Nακ2/Cmax⋆≥48≥48κNακ^2/C_ ≥ 48≥ 48κ. Markov’s inequality applied to ZtZ_t proves (13). On ℰβE_β, if the optimal path is first discarded by beam pruning at depth t, it is a generated candidate and at least b other generated candidates have scores at least its score. These candidates are among the full-tree filtered prefixes, so Zt≥bZ_t≥ b. Counting all ties against the optimal prefix makes this implication valid for any tie-breaking rule. Since the sample-size condition also gives Cmax⋆e−Nκ2/(48Cmax⋆)≤1/2C_ e^-Nκ^2/(48C_ )≤ 1/2, a union bound and a geometric sum yield Pr(ℰβ∩ℰbc) (E_β _b^c) ≤∑t=1LPr(Zt≥b)≤1b∑t=1L[Cmax⋆e−Nκ2/(48Cmax⋆)]t ≤ _t=1^L (Z_t≥ b)≤ 1b _t=1^L [C_ e^-Nκ^2/(48C_ ) ]^t ≤Cmax⋆e−Nκ2/(48Cmax⋆)b(1−Cmax⋆e−Nκ2/(48Cmax⋆))≤2Cmax⋆be−Nκ2/(48Cmax⋆). ≤ C_ e^-Nκ^2/(48C_ )b (1-C_ e^-Nκ^2/(48C_ ) )≤ 2C_ be^-Nκ^2/(48C_ ). This bounds the intersection with ℰβE_β directly; no concentration inequality is applied after conditioning on a future good event. ∎ E.2 Proof of Theorem 2 Proof. For L≥2L≥ 2, the threshold multiplier 1−1/L1-1/L lies in [1/2,1)[1/2,1). Applying Lemmas 3 and 5 with α=1−1/Lα=1-1/L gives Pr(ℰc) (E^c) =Pr(ℰβc)+Pr(ℰβ∩ℰbc) = (E_β^c)+ (E_β _b^c) ≤Lexp(−N2Cmax⋆L2)+2Cmax⋆bexp(−κ2N48Cmax⋆). ≤ L \! (- N2C_ L^2 )+ 2C_ b \! (- κ^2N48C_ ). On ℰE, induction over the depths gives y⋆∈ℬLy _L, so the final selection satisfies r^(x,ybeam)≥r^(x,y⋆) r(x,y^beam)≥ r(x,y ). On ℰcE^c, the regret is at most one because rewards lie in [0,1][0,1]. Consequently, Reg(x) (x) ≤Pr(ℰc)+[ℰ(r⋆(x,y⋆)−r^(x,y⋆)+r^(x,y⋆)−r^(x,ybeam) ≤ (E^c)+E\! [1_E (r (x,y )- r(x,y )+ r(x,y )- r(x,y^beam) +r^(x,ybeam)−r⋆(x,ybeam))] 100.00015pt+ r(x,y^beam)-r (x,y^beam) ) ] ≤Pr(ℰc)+ϵopt(x)+[ℰ|r^(x,ybeam)−r⋆(x,ybeam)|] ≤ (E^c)+ _opt(x)+E\! [1_E | r(x,y^beam)-r (x,y^beam) | ] ≤Pr(ℰc)+ϵopt(x)+(∑y∈LPr(ybeam=y,ℰ)(r^(x,y)−r⋆(x,y))2)1/2 ≤ (E^c)+ _opt(x)+ ( _y ^L (y^beam=y,E) ( r(x,y)-r (x,y) )^2 )^1/2 ≤Pr(ℰc)+ϵopt(x)+[(1−1L)−LC¯(x)∑y∈Lπref(y∣x)(r^(x,y)−r⋆(x,y))2]1/2 ≤ (E^c)+ _opt(x)+ [ (1- 1L )^-L C(x) _y ^L _ref(y x) ( r(x,y)-r (x,y) )^2 ]^1/2 ≤Pr(ℰc)+ϵopt(x)+2C¯(x)ϵRM2(x). ≤ (E^c)+ _opt(x)+2 C(x) _RM^2(x). The second inequality uses Assumption 2 and reward maximization. The third is Cauchy–Schwarz with Pr(ℰ)≤1 (E)≤ 1, and the fourth applies Lemma 2. The last inequality follows from Assumption 1 and (1−1/L)−L≤4(1-1/L)^-L≤ 4 for integer L≥2L≥ 2. This inequality follows because ulog(1−1/u)u (1-1/u) is nondecreasing for u≥2u≥ 2: its derivative is log(1−1/u)+1/(u−1)≥0 (1-1/u)+1/(u-1)≥ 0 by log(1+v)≤v (1+v)≤ v. The distribution comparison is for the joint probabilities Pr(ybeam=y,ℰ) (y^beam=y,E), so no normalization by Pr(ℰ) (E) is needed. ∎ E.3 Proof of Corollaries 1 Proof of Corollary 1. Each search-error term in (8) is at most δ/2δ/2 whenever N≥max48Cmax⋆κ2max2,log(2Cmax⋆),2Cmax⋆L2log2Lδ,48Cmax⋆κ2[log4Cmax⋆bδ]+.N≥ \ 48C_ κ^2 \2, (2C_ )\, 2C_ L^2 2Lδ, 48C_ κ^2 [ 4C_ bδ ]_+ \. The first term is the sample-size condition in Theorem 2; the other two follow by solving the two exponential inequalities. Since Cmax⋆≥1C_ ≥ 1, [log(4Cmax⋆/(bδ))]+≤log(4Cmax⋆)+[log(1/(bδ))]+[ (4C_ /(bδ))]_+≤ (4C_ )+[ (1/(bδ))]_+, so (9) with a sufficiently large universal constant implies all three requirements. Substitution into (7) proves the corollary. ∎ E.4 Proof of Corollary 2 Proof. Apply Lemma 3 with α=1/2α=1/2 to obtain Pr(ℰβc)≤Lexp(−N/(8Cmax⋆)) (E_β^c)≤ L (-N/(8C_ )). Unlike reward-based selection, the final maximum-score selection must also distinguish y⋆y from every remaining competitor. If ℰβE_β holds, Zt<bZ_t<b at every t<Lt<L, and ZL=0Z_L=0, then the optimal path survives the first L−1L-1 rounds, has strictly larger score than every other filtered complete path, and is selected at the final round. Thus Reg(x) (x) ≤Pr(ybeam≠y⋆)≤Pr(ℰβc)+∑t=1L−1Pr(Zt≥b)+Pr(ZL≥1) ≤ (y^beam≠ y )≤ (E_β^c)+ _t=1^L-1 (Z_t≥ b)+ (Z_L≥ 1) ≤Lexp(−N8Cmax⋆)+1b∑t=1L−1[Cmax⋆e−Nκ2/(48Cmax⋆)]t+[Cmax⋆e−Nκ2/(48Cmax⋆)]L ≤ L \! (- N8C_ )+ 1b _t=1^L-1 [C_ e^-Nκ^2/(48C_ ) ]^t+ [C_ e^-Nκ^2/(48C_ ) ]^L ≤Lexp(−N8Cmax⋆)+2Cmax⋆bexp(−Nκ248Cmax⋆)+[Cmax⋆e−Nκ2/(48Cmax⋆)]L. ≤ L \! (- N8C_ )+ 2C_ b \! (- Nκ^248C_ )+ [C_ e^-Nκ^2/(48C_ ) ]^L. The first inequality uses bounded rewards and optimal reward one. The next bounds follow from (13) and the same geometric sum as in Lemma 5; final selection is controlled with m=1m=1, while intermediate pruning is controlled with m=bm=b. For an explicit sufficient sample size, take N≥96(Cmax⋆/κ2)log(6LCmax⋆/δ)N≥ 96(C_ /κ^2) (6LC_ /δ). This satisfies the sample-size condition of Lemma 5 and gives Cmax⋆e−Nκ2/(48Cmax⋆)≤δ/(6L)C_ e^-Nκ^2/(48C_ )≤δ/(6L). The ranking sum is then at most δ/(3L)δ/(3L), and its final-depth power is at most δ/(6L)δ/(6L), since b≥1b≥ 1 and δ/(6L)<1δ/(6L)<1. Also N≥8Cmax⋆log(3L/δ)N≥ 8C_ (3L/δ), so the filtering term is at most δ/3δ/3. Their sum is at most δ, proving the stated sufficient sample complexity. ∎ Appendix F Regret Lower Bound: Proof of Theorem 3 Proof of Theorem 3. Fix a horizon L and an action set =1,2,…,||A=\1,2,…,|A|\ with ||≥logLlog(4/3)+2|A|≥ L (4/3)+2. We construct an instance in which, at each time step t∈[L]t∈[L], there is a unique optimal action along the optimal trajectory. Without loss of generality (by relabeling actions), we denote this optimal action at⋆a_t by at,1a_t,1. Let st−1⋆s_t-1 be the state reached by following the optimal action sequence up to time t−1t-1 (i.e., the “optimal-prefix” state), and let st−1s_t-1 denote any state that is not on this optimal prefix. We define a reference policy πref(⋅∣s,x) _ref(· s,x) as follows: πref(at,1∣st−1⋆,x)=1||+κ′,πref(at,i∣st−1⋆,x)=1||−κ′||−1,i=2,…,||, _ref(a_t,1 s_t-1 ,x)= 1|A|+κ , _ref(a_t,i s_t-1 ,x)= 1|A|- κ |A|-1,\ \ i=2,…,|A|, and for any off-prefix state st−1≠st−1⋆s_t-1≠ s_t-1 , πref(at,i∣st−1,x)=1||,i=1,…,||. _ref(a_t,i s_t-1,x)= 1|A|, i=1,…,|A|. By construction, ∑i=1||πref(at,i∣st−1⋆,x)=1 _i=1^|A| _ref(a_t,i s_t-1 ,x)=1, and we assume κ′κ is a sufficiently small value that will be assigned later. Next, define the true reward r⋆r and the estimated reward r r for complete trajectories. Let y⋆y denote the unique optimal trajectory induced by choosing at,1a_t,1 at every step along the optimal prefix, and let y≠y⋆y≠ y denote any other trajectory. We set r⋆(x,y⋆)=1,r⋆(x,y)=1−δ(y≠y⋆),r (x,y )=1, r (x,y)=1-δ\ \ (y≠ y ), while the reward estimator is misspecified in the opposite direction: r^(x,y⋆)=1−2δ,r^(x,y)=1−δ(y≠y⋆), r(x,y )=1-2δ, r(x,y)=1-δ\ \ (y≠ y ), where δ∈(0,1/2]δ∈(0,1/2] will be chosen later, which ensures all rewards lie in [0,1][0,1]. This construction satisfies Assumption 3. Thereby, under this hard instance, if the final top-b response contains suboptimal responses, the reward model will output the incorrect result with probability one. According to the definition of Regret, Reg(x) (x) =r⋆(x,y⋆)−y∼πbeam(⋅|x)[r⋆(x,y)]=δπbeam(′|x), =r (x,y )-E_y _beam(·|x)[r (x,y)]=δ _beam(Y |x), where ′=\y⋆Y =Y \y \. Since we have b≥2b≥ 2 and the reward model will choose a suboptimal response if the final top-b set contains y∈′y , πbeam(′|x)=1−Pr(the final top b only contains y⋆). _beam(Y |x)=1- (the final top $b$ only contains y ). Providing the lower bound is to providing the upper bound for Pr(the final top b only contains y⋆) (the final top $b$ only contains y ). We next prove Pr(the final top b only contains y⋆)≤3/4 (the final top $b$ only contains y )≤ 3/4 by cases, and hence πbeam(′|x)≥1/4 _beam(Y |x)≥ 1/4 is in a constant order. Case 1: N≤maxCt⋆(x)N≤ \C _t(x)\. Under this case, let κ′≤1/||κ ≤ 1/|A|. At the step where Ct⋆(x)=Cmax⋆C _t(x)=C_ , the probability generating the correct response can be upper bounded by 1−(1−1Ct⋆)N≤1−(1−1Ct⋆)Ct⋆≤3/4.1- (1- 1C _t )^N≤ 1- (1- 1C _t )^C_t ≤ 3/4. where the last inequality follows by Ct⋆=||κ′||+1≥2C _t= |A|κ |A|+1≥ 2. Therefore, the optimal response y⋆y is excluded from the final top-b candidate set with probability at least 1/41/4, and hence Pr(the final top b only contains y⋆)≤3/4 (the final top $b$ only contains y )≤ 3/4. Case 2.1: N>maxCt⋆(x)\N> \C _t(x)\ and ∃βt≥1/Ct⋆(x)∃\ _t≥ 1/C_t (x)\. In this case, the optimal trajectory will be eliminated with a constant probability greater than 1/4, since Pr(Bin(N,1/Ct⋆(x))<Nβt)≥Pr(Bin(N,1/Ct⋆(x))<NCt⋆(x))≥14, (Bin(N,1/C _t(x))<N _t )≥ (Bin(N,1/C _t(x))< NC _t(x) )≥ 14, where the last inequality follows from Lemma 12. Thus we exclude the optimal response from the final top b candidate set with probability at least 1/41/4, and hence Pr(the final top b only contains y⋆)≤3/4 (the final top $b$ only contains y )≤ 3/4. Case 2.2: N>maxt∈[L]Ct⋆(x)\N> _t∈[L]C_t (x)\ and ∀t,βt<1/Ct⋆(x)∀ t,\ _t<1/C_t (x)\. In this case, every filtering threshold βt _t lies below the optimal-trajectory probability 1/Ct⋆(x)1/C_t (x). Hence, for each t∈[L]t∈[L], there exists some α∈(0,1)α∈(0,1) such that βt<αCt⋆(x). _t< αC_t (x). We choose κ′κ so that the probability of any fixed suboptimal next-token choice at the optimal prefix dominates the scaled optimal one, namely α(1||+κ′)≤1||−κ′||−1.α ( 1|A|+κ )\;≤\; 1|A|- κ |A|-1. Equivalently, απref(at⋆∣st−1⋆,x)≤πref(at,i∣st−1⋆,x),∀i∈2,…,||.α\, _ref\! (a_t s_t-1 ,x )\;≤\; _ref\! (a_t,i s_t-1 ,x ),\ ∀ i∈\2,…,|A|\. Now fix any round t and consider any suboptimal child st′s_t obtained by taking corresponding at,ia_t,i with i≥2i≥ 2 from the optimal prefix st−1⋆s_t-1 . Let p:=πref(at,i∣st−1⋆,x)=1||−κ′||−1.p:= _ref(a_t,i s_t-1 ,x)= 1|A|- κ |A|-1. By the choice of α and κ′κ , we have βt<α/Ct⋆(x)≤p _t<α/C_t (x)≤ p. Therefore, under N i.i.d. draws, this suboptimal child survives the βt _t-filtering with constant probability: Pr(Bin(N,p)≥Nβt)≥Pr(Bin(N,p)>Nβt)≥Pr(Bin(N,p)>Np)≥14, \! (Bin(N,p)≥ N _t )\;≥\; \! (Bin(N,p)>N _t )\;≥\; \! (Bin(N,p)>Np )\;≥\; 14, where the last inequality follows from Lemma 11. Consequently, the probability that a single suboptimal child is eliminated at round t is at most Pr(Bin(N,p)<Nβt)≤34. \! (Bin(N,p)<N _t )≤ 34. Since b≥2b≥ 2, as long as at least one suboptimal trajectory remains in the beam, the final top-b set cannot consist solely of y⋆y unless all suboptimal trajectories are eliminated at some intermediate round by the βt _t-filtering (so that the beam collapses to a singleton). Formally, for each t∈[L]t∈[L] define the event Et:=at round t, after βt-filtering, no suboptimal child survives,E:=⋃t=1LEt.E_t:= \at round $t$, after $ _t$-filtering, no suboptimal child survives \, E:= _t=1^LE_t. Then the final top-b set contains only y⋆⊆E\the final top-$b$ set contains only y \ E, and hence Pr(the final top-b set contains only y⋆)≤Pr(E)≤∑t=1LPr(Et). (the final top-$b$ set contains only y )≤ (E)≤ _t=1^L (E_t). Next, fix a round t and consider the N draws from the next-token distribution at the optimal prefix st−1⋆s_t-1 . Let (Nt,1,…,Nt,||)(N_t,1,…,N_t,|A|) denote the resulting multinomial count vector with parameters N and probabilities (pt,1,…,pt,||)(p_t,1,…,p_t,|A|). Since multinomial counts are negatively associated, and thus satisfy a negative lower-orthant dependence bound Joag-Dev and Proschan (1983): Pr(Et)≤Pr(⋂i=2||Nt,i<Nβt)≤∏i=2||Pr(Nt,i<Nβt). (E_t)≤ \! ( _i=2^|A|\N_t,i<N _t\ )≤ _i=2^|A| (N_t,i<N _t). Moreover, for each i≥2i≥ 2, Nt,i∼Bin(N,pt,i)N_t,i (N,p_t,i), and by the previous bound Pr(Bin(N,pt,i)<Nβt)≤3/4 (Bin(N,p_t,i)<N _t)≤ 3/4. Therefore, Pr(Et)≤(34)||−1. (E_t)≤ ( 34 )^|A|-1. Consequently, Pr(E)≤∑t=1LPr(Et)≤L⋅(34)||−1≤34, (E)≤ _t=1^L (E_t)≤ L· ( 34 )^|A|-1≤ 34, where the last inequality follows from our choice of |||A|, namely ||≥logLlog(4/3)+2|A|≥ L (4/3)+2. Taking Case 1, Case 2.1 and Case 2.2 together, Pr(the final top b only contains y⋆)≤3/4 (the final top $b$ only contains y )≤ 3/4. Finally, we specify δ through the notation of reward model error. By the definition of ϵRM2 _RM^2, we have ϵRM2=y∼πref(⋅|x)[(r∗(x,y)−r^(x,y))2]=πref(y⋆|x)⋅4δ2=4δ2C¯. _RM^2=E_y _ref(·|x) [ (r^*(x,y)- r(x,y) )^2 ]= _ref(y |x)· 4δ^2= 4δ^2 C. Therefore, taking δ=C¯(x)ϵRM2(x)/2δ= C(x) _RM^2(x)/2, the regret can be lower bounded as Reg(x) (x) =δπbeam(′|x) =δ _beam(Y |x) =C¯(x)ϵRM2(x)4(1−Pr(the final top b only contains y⋆)) = C(x) _RM^2(x)4(1- (the final top $b$ only contains y )) ≥14C¯(x)ϵRM2(x)4. ≥ 14 C(x) _RM^2(x)4. The proof is completed. ∎ Appendix G Auxiliary Lemmas Lemma 6 (Truncated binomial moments). Let X∼Bin(N,p)X (N,p) and let K∈1,…,NK∈\1,…,N\. For every integer 1≤q≤K1≤ q≤ K, [(X/N)qX≥K]≤pqexp(q(q−1)2(K−q+1)).E\! [(X/N)^q1_\X≥ K\ ]≤ p^q \! ( q(q-1)2(K-q+1) ). If p>0p>0, then for every integer q≥1q≥ 1, [(Np/X)qX≥K]≤exp(q(q+1)2K),E\! [(Np/X)^q1_\X≥ K\ ]≤ \! ( q(q+1)2K ), where the integrand is zero on X<K\X<K\. Proof. Write (X)q=X(X−1)⋯(X−q+1)(X)_q=X(X-1)·s(X-q+1). On X≥K≥qX≥ K≥ q, the inequality log(1+u)≤u (1+u)≤ u gives logXq(X)q X^q(X)_q =∑j=0q−1log(1+jX−j)≤∑j=0q−1jX−j≤q(q−1)2(K−q+1), = _j=0^q-1 (1+ jX-j )≤ _j=0^q-1 jX-j≤ q(q-1)2(K-q+1), [(X/N)qX≥K] [(X/N)^q1_\X≥ K\] ≤eq(q−1)/(2(K−q+1))Nq[(X)q]=(N)qNqpqeq(q−1)/(2(K−q+1)) ≤ e^q(q-1)/(2(K-q+1))N^qE[(X)_q]= (N)_qN^qp^qe^q(q-1)/(2(K-q+1)) ≤pqeq(q−1)/(2(K−q+1)). ≤ p^qe^q(q-1)/(2(K-q+1)). The factorial-moment identity follows by expressing (X)q(X)_q as the sum over ordered q-tuples of distinct Bernoulli trials of the product of their success indicators. This also covers p=0p=0. For the inverse moment, take p>0p>0. Expanding the binomial probability mass function and substituting y=x+qy=x+q yields 1(X+1)⋯(X+q) 1(X+1)·s(X+q) =∑x=0N!px(1−p)N−x(x+q)!(N−x)! = _x=0^N N!p^x(1-p)^N-x(x+q)!(N-x)! =N!(N+q)!pq∑y=qN+q(N+qy)py(1−p)N+q−y = N!(N+q)!p^q _y=q^N+q N+qyp^y(1-p)^N+q-y =PrBin(N+q,p)≥qpq(N+1)⋯(N+q)≤1pq(N+1)⋯(N+q). = \Bin(N+q,p)≥ q\p^q(N+1)·s(N+q)≤ 1p^q(N+1)·s(N+q). For p=1p=1, the same identity follows directly from X=NX=N. On X≥KX≥ K, the product ∏j=1q(1+j/X) _j=1^q(1+j/X) is at most exp(q(q+1)/(2K)) (q(q+1)/(2K)). Consequently, [(Np/X)qX≥K] [(Np/X)^q1_\X≥ K\] ≤(Np)qeq(q+1)/(2K)1(X+1)⋯(X+q) ≤(Np)^qe^q(q+1)/(2K)E 1(X+1)·s(X+q) ≤Nq(N+1)⋯(N+q)eq(q+1)/(2K)≤eq(q+1)/(2K), ≤ N^q(N+1)·s(N+q)e^q(q+1)/(2K)≤ e^q(q+1)/(2K), which proves the inverse-moment bound without a lower bound on p. ∎ Definition 3 (Bernoulli KL). For p,q∈(0,1)p,q∈(0,1), the Bernoulli KL divergence is defined as KL(p∥q):=plogpq+(1−p)log1−p1−q.KL\! (p\, \|\,q ):=p pq+(1-p) 1-p1-q. Lemma 7 (Markov’s inequality). Let X≥0X≥ 0 be a nonnegative random variable with [X]<∞E[X]<∞. Then for any a>0a>0, ℙ(X≥a)≤[X]a.P(X≥ a)≤ E[X]a. Lemma 8 (Chernoff Inequality under Binomial Setting). Let Xi∼Ber(p)X_i (p), S=∑i=1nXi∼Bin(n,p)S= _i=1^nX_i (n,p), μ=[S]μ=E[S], then ∀δ>0∀δ>0, Pr(S≥(1+δ)μ)≤(eδ(1+δ)1+δ)μ≤exp(−μδ22+δ), (S≥(1+δ)μ )≤ ( e^δ(1+δ)^1+δ )^μ≤ (- μδ^22+δ ), Pr(S≤(1−δ)μ)≤exp(−μδ22). (S≤(1-δ)μ )≤ (- μδ^22 ). A KL-form Chernoff bound is: Pr(Sn≥α)≤exp(−nKL(α∥p))for α>p, \! ( Sn≥α )≤ \! (-n\,KL(α\|p) ) α>p, Pr(Sn≤α)≤exp(−nKL(α∥p))for α<p, \! ( Sn≤α )≤ \! (-n\,KL(α\|p) ) α<p, where KL(α∥p)=αlogαp+(1−α)log1−α1−p.KL(α\|p)=α αp+(1-α) 1-α1-p. Lemma 9. Let Xi,1,…,Xi,N∼i.i.d.Ber(π(ai∣si−1,x))X_i,1,…,X_i,N .i.d. Ber(π(a_i s_i-1,x)) for some π(ai∣si−1,x)∈(0,1)π(a_i s_i-1,x)∈(0,1), and define π^(ai∣si−1,x)≜1N∑j=1NXi,j. π(a_i s_i-1,x) 1N _j=1^NX_i,j. Then for any ε∈(0,1) ∈(0,1), Pr(|logπ^(ai∣si−1,x)π(ai∣si−1,x)|≥log(11−ε))≤2exp(−Nπ(ai∣si−1,x)ε23). ( | π(a_i s_i-1,x)π(a_i s_i-1,x) |≥ ( 11- ) )≤ 2 (- Nπ(a_i s_i-1,x) ^23 ). Proof. By Lemma 8, we have Pr(|π^(ai∣si−1,x)−π(ai∣si−1,x)|≥επ(ai∣si−1,x))≤2exp(−Nπ(ai∣si−1,x)ε23). \! ( | π(a_i s_i-1,x)-π(a_i s_i-1,x) |≥ \,π(a_i s_i-1,x) )≤ 2 (- Nπ(a_i s_i-1,x) ^23 ). That is, with probability at least 1−2exp(−Nπ(ai∣si−1,x)ε23)1-2 (- Nπ(a_i s_i-1,x) ^23 ), we have (1−ε)π(ai∣si−1,x)≤π^(ai∣si−1,x)≤(1+ε)π(ai∣si−1,x).(1- )π(a_i s_i-1,x)≤ π(a_i s_i-1,x)≤(1+ )π(a_i s_i-1,x). This implies logπ^(ai∣si−1,x)π(ai∣si−1,x)∈[log(1−ε),log(1+ε)]. π(a_i s_i-1,x)π(a_i s_i-1,x)∈[ (1- ), (1+ )]. Hence, |logπ^(ai∣si−1,x)π(ai∣si−1,x)|≤max−log(1−ε),log(1+ε)=log(11−ε). | π(a_i s_i-1,x)π(a_i s_i-1,x) |≤ \- (1- ), (1+ )\= ( 11- ). Therefore, Pr(|logπ^(ai∣si−1,x)π(ai∣si−1,x)|≥log(11−ε))≤2exp(−Nπ(ai∣si−1,x)ε23). ( | π(a_i s_i-1,x)π(a_i s_i-1,x) |≥ ( 11- ) )≤ 2 (- Nπ(a_i s_i-1,x) ^23 ). ∎ Lemma 10. Let α∈(0,1)α∈(0,1) and p∈(0,1)p∈(0,1). Then the following two lower bounds hold: KL(p∥αp)≥(log(1/α)−(1−α))p,KL(p\|α p)≥ ( (1/α)-(1-α) )p, (14) KL(αp∥p)≥((1−α)−αlog(1/α))p.KL(α p\|p)≥ ((1-α)-α (1/α) )p. (15) Proof. We prove Equations 14 and 15 separately. Proof of Equation 14. By the definition of Bernoulli KL, KL(p∥αp)=plogpαp+(1−p)log1−p1−αp=plog1α−(1−p)log1−αp1−p.KL(p\|α p)=p pα p+(1-p) 1-p1-α p=p 1α-(1-p) 1-α p1-p. Let u:=(1−α)p1−p>0u:= (1-α)p1-p>0, then 1−αp1−p=1+u. 1-α p1-p=1+u. Using log(1+u)≤u (1+u)≤ u, we obtain −(1−p)log1−αp1−p=−(1−p)log(1+u)≥−(1−p)u=−(1−α)p.-(1-p) 1-α p1-p=-(1-p) (1+u)≥-(1-p)u=-(1-α)p. Combining the last display with the expression of KL(p∥αp)KL(p\|α p) yields KL(p∥αp)≥(log(1/α)−(1−α))p.KL(p\|α p)≥ ( (1/α)-(1-α) )p. Proof of Equation 15. Again by the definition of Bernoulli KL, KL(αp∥p)=αplogαp+(1−αp)log1−αp1−p=αplogα+(1−αp)log1−αp1−p.KL(α p\|p)=α p α pp+(1-α p) 1-α p1-p=α p α+(1-α p) 1-α p1-p. Let x:=(1−α)p1−p>0x:= (1-α)p1-p>0, so that 1−αp1−p=1+x. 1-α p1-p=1+x. Using log(1+x)≥x1+x (1+x)≥ x1+x, we get (1−αp)log1−αp1−p=(1−αp)log(1+x)≥(1−αp)x1+x.(1-α p) 1-α p1-p=(1-α p) (1+x)≥(1-α p) x1+x. Note that x1+x=(1−α)p1−p1+(1−α)p1−p=(1−α)p1−αp. x1+x= (1-α)p1-p1+ (1-α)p1-p= (1-α)p1-α p. Hence (1−αp)x1+x=(1−α)p.(1-α p) x1+x=(1-α)p. Therefore, KL(αp∥p)≥αplogα+(1−α)p=((1−α)−αlog(1/α))p.KL(α p\|p)≥α p α+(1-α)p= ((1-α)-α (1/α) )p. This completes the proof. ∎ Lemma 11. Let X∼Bin(N,p)X (N,p) with N≥1N≥ 1 and p∈(0,1)p∈(0,1). If p≥cN,where c:=ln(4/3)=0.28768…,p≥ cN, c:= (4/3)=0.28768…, then Pr(X>[X])≥14. \! (X>E[X] )≥ 14. Proof. See Theorem 1 of Pinelis (2021). ∎ Lemma 12. Let X∼Bin(N,p)X (N,p) with N≥1N≥ 1 and p∈(0,1/2]p∈(0,1/2]. Then Pr(X<[X])=Pr(X<Np)≥14. \! (X<E[X] )= (X<Np)≥ 14. Proof. Let q:=1−p∈[1/2,1)q:=1-p∈[1/2,1) and define Y:=N−XY:=N-X. Then Y∼Bin(N,q)Y (N,q) and [Y]=NqE[Y]=Nq. Moreover, X<Np⇔N−X>N−Np⇔Y>Nq⇔Y>[Y],\X<Np\ \N-X>N-Np\ \Y>Nq\ \Y>E[Y]\, so Pr(X<Np)=Pr(Y>[Y]) (X<Np)= (Y>E[Y]). If N=1N=1, then Y∈0,1Y∈\0,1\ and [Y]=q∈(1/2,1)E[Y]=q∈(1/2,1), hence Pr(Y>[Y])=Pr(Y=1)=q≥12. (Y>E[Y])= (Y=1)=q≥ 12. If N≥2N≥ 2, since q≥1/2q≥ 1/2 and c=ln(4/3)<1/2c= (4/3)<1/2, we have q≥1/2≥c≥c/Nq≥ 1/2≥ c≥ c/N. Thus the condition of Lemma 11 holds for Y, and so Pr(Y>[Y])≥14. (Y>E[Y])≥ 14. Combining both cases yields Pr(X<Np)=Pr(Y>[Y])≥1/4 (X<Np)= (Y>E[Y])≥ 1/4. ∎ Appendix H Experiment Details and Supplemental Experiments H.1 Details of Numerical Experiments Baselines. We compare CF-Beam against four representative test-time methods: (i) Vanilla beam search, which follows the same beam pipeline as CF-Beam but without the confidence-filtering step; (i) Best-of-N (Huang et al., 2025), which samples N responses independently and selects the one with the highest reward; (i) Majority Voting, which samples N responses independently and selects the one with the highest frequency; and (iv) Best-of-Majority (Di et al., 2025), which first filters candidates via majority voting (self-consistency) and then chooses the highest-scoring response under an external reward model. Remark 4 (Oracle CF-Beam and Empirical CF-Beam). The threshold used in Theorem 2 is βt=1−1/LCt⋆(x)=(1−1L)πref(at⋆∣st−1⋆,x), _t= 1-1/LC_t (x)= (1- 1L ) _ref(a_t s_t-1 ,x), which depends on the unknown optimal token probability along the optimal prefix. Therefore, this choice is oracle and is generally not directly implementable in practice. In the experiments, we include this version as Oracle CF-Beam, which serves as a diagnostic reference for the theory-prescribed threshold. For a practical implementation, we instead use a prefix-adaptive empirical threshold βt(st−1)=γp^max,t(st−1),p^max,t(st−1):=maxa∈π^(a∣st−1,x), _t(s_t-1)=γ\, p_ ,t(s_t-1), p_ ,t(s_t-1):= _a π(a s_t-1,x), where γ∈(0,1)γ∈(0,1) is a tuning parameter. This rule is motivated by the fact that the oracle threshold is a constant fraction of the optimal token probability. In likelihood-aligned regimes, where the optimal continuation is locally competitive under the reference policy, the optimal token probability is of the same order as the local maximum probability. Thus p^max,t(st−1) p_ ,t(s_t-1) provides a scale-adaptive proxy for the unknown quantity 1/Ct⋆(x)1/C_t (x), while avoiding the need to know either Ct⋆(x)C_t (x) or the optimal token at⋆a_t . This empirical rule preserves the main purpose of the oracle threshold: it filters out low-frequency tail tokens whose empirical probabilities are small relative to the local mode, while retaining multiple plausible high-probability continuations. In our experiments, we set γ=0.3γ=0.3 and refer to this implementation as Empirical CF-Beam. Figures 3 and 3 show that Empirical CF-Beam achieves performance comparable to, and sometimes slightly better than, Oracle CF-Beam. Experimental protocol. In all experiments, we use an LLM simulator specified by the collection of conditional next-token distributions πref(⋅∣s,x)s∈≤L−1\ _ref(· s,x)\_s ^≤ L-1, which fully characterizes the rollout distribution πref(⋅∣x) _ref(· x) over trajectories y∈Ly ^L for a fixed prompt x. The optimal output is defined as y⋆:=argmaxy∈Lπref(y∣x)y := _y ^L _ref(y x). Following the setting of Reinforcement Learning with Verifiable Reward (RLVR), we define the ground-truth reward r⋆(x,y⋆)=1r (x,y )=1 and r⋆(x,y)=0r (x,y)=0 for all y∈L∖y⋆y ^L \y \, and evaluate each algorithm by its accuracy in identifying y⋆y . The noisy reward model r r with error level ϵRM2=0.01 _RM^2=0.01 is implemented as symmetric label noise: r^(x,y) r(x,y) flips r⋆(x,y)r (x,y) independently with probability 0.010.01. For each instance, we run each algorithm for 300300 independent trials and report the average accuracy of returning the correct answer. Construction of the LLM simulator. We construct a history-dependent token policy πref(⋅∣s,x) _ref(· s,x) over an action set A with horizon L, optimal-suboptimal gap κ′κ , and target optimal-trajectory probability p=1C¯(x)∈(0,1)p= 1 C(x)∈(0,1). The construction ensures: (i) there exists a unique optimal trajectory sL⋆s _L with πref(sL⋆|x)=p _ref(s _L|x)=p, and (i) for every state st−1s_t-1 at depth t−1t-1, the best action at⋆(st−1)a _t(s_t-1) satisfies the log-gap condition logπref(st⋆∣x)−logπref(st∣x)≥7κ′ _ref(s _t x)- _ref(s_t x)≥ 7κ for all st≠st⋆s_t≠ s _t. To be specific, we first generate the optimal trajectory’s distribution Ct⋆(x)t=1L\C_t (x)\_t=1^L, and then generate the suboptimal action’s distribution at each time step t∈[L]t∈[L]. The key steps are illustrated as follows. Step 1 (optimal path). Since the probability of generating the correct answer using one single rollout is 1/C¯1/ C, the geometric mean per-step probability along the optimal trajectory is (1/C¯)1/L(1/ C)^1/L. To add randomness towards the language model, we draw (ξ1,…,ξL)( _1,…, _L) from a zero-sum Gaussian distribution (e.g., ξ~t∼(0,σ2) ξ_t (0,σ^2) i.i.d. and ξt=ξ~t−1L∑j=1Lξ~j _t= ξ_t- 1L _j=1^L ξ_j), and set log1Ct⋆(x)=1Llogp+ξt,t=1,…,L. 1C_t (x)= 1L p+ _t, t=1,…,L. The larger the value of σ2σ^2, the greater the variability in per-step difficulty. Step 2 (suboptimal actions distribution). Since the optimal trajectory is set, we now focus on designing the distribution for suboptimal actions over optimal and suboptimal trajectories. First, for any suboptimal trajectories st−1≠st−1⋆s_t-1≠ s_t-1 , t∈[L]t∈[L], we assign the probability of generating local best action with π(at⋆(st−1)∣st−1,x)=π(at⋆∣st−1⋆,x)=1Ct⋆(x)π(a_t (s_t-1) s_t-1,x)=π(a_t s _t-1,x)= 1C_t (x). Second, for suboptimal actions on both optimal and suboptimal trajectories, we sample their probability mass vector using a Dirichlet distribution: (πref(a∣st−1,x))a∈∖a⋆(st−1)∼Dirichlet(α), ( _ref(a s_t-1,x) )_a \a (s_t-1)\ ( 1), where α controls the concentration of the suboptimal action distribution. Finally, we normalize the distribution over suboptimal actions such that ∑a≠at⋆(s)πref(a∣s,x)=1−1Ct⋆(x) _a≠ a_t (s) _ref(a s,x)=1- 1C_t (x) and it does not violate our unique optimal trajectory assumption. Therefore, given the basic parameters |||A|, L and p, together with the hyperparameters σ and α, we construct next-token distributions πref(⋅∣s,x) _ref(· s,x) for all prefixes s of length at most L−1L-1, thereby simulating the LLM sampling process. Parameter setup. Figure 3: |||A|=100, L=10, p=[0.01,0.05,0.3]p=[0.01,0.05,0.3], κ=0.01κ=0.01, α=0.5α=0.5, σ=1σ=1. Figure 3: |||A|=100, L∈[2,40]L∈[2,40], p=0.8Lp=0.8^L, κ=0.01κ=0.01, α=0.1α=0.1, σ=1σ=1. Detailed empirical findings. We expand here on the discussion in Section 5 with a finer-grained, per-panel analysis of Figures 3 and 3. Difficulty experiment (Figure 3). In the hardest setting (p=0.01p=0.01, Figure 2(a)), both Oracle CF-Beam and Empirical CF-Beam achieve substantially higher accuracy than the sequence-level parallel baselines (Best-of-N, Majority Voting, Best-of-Majority) and Vanilla-Beam, especially under limited budgets. This is precisely the regime where sparse coverage and finite-sample tail fluctuations are most pronounced, and hence where the failure mode identified in Theorem 1 is most amplified. As the problem becomes easier (Figure 2(b)), the performance gap narrows: the sequence-level baselines catch up at moderate-to-large budgets, and the improvement of CF-Beam over Vanilla-Beam becomes more moderate. In the easiest regime (p=0.3p=0.3, Figure 2(c)), most methods achieve comparable performance, and Vanilla-Beam nearly matches CF-Beam once the budget is sufficiently large. These trends suggest that the confidence filter is most beneficial in hard, sparse-coverage instances, while its marginal gain decreases when the base policy is already accurate enough for the optimal prefixes to be reliably sampled. This is also consistent with the gap between the sequence-level coefficient C¯ C and the worst-step coefficient Cmax⋆C_ shown in each panel: as p increases, this gap becomes less pronounced, reducing the potential advantage of CF-Beam. Horizon-length experiment (Figure 3). We consider a setting where, at each step, the model selects the correct action with mean probability 0.80.8. As the horizon grows, the accuracy of Best-of-N, Best-of-Majority, and Majority Voting drops rapidly, whereas the beam-based methods are more robust. Among them, the CF-Beam variants consistently maintain the highest accuracy, indicating that confidence filtering further improves the stability of beam search in long-horizon regimes. This is consistent with our theory, which shows that the dominant sample-complexity term for CF-Beam grows only polynomially in the horizon length L. In contrast, sequence-level baselines can exhibit exponential dependence on L, causing their performance to degrade more rapidly as the horizon increases. Remark 5 (Finite-budget performance of Empirical CF-Beam). It may seem counterintuitive that, in Figure 3, Empirical CF-Beam slightly outperforms Oracle CF-Beam. Here, oracle refers to knowledge of the optimal-token probability used to set the threshold; the theory-prescribed choice need not maximize accuracy at every finite budget. Writing pt⋆:=πref(at⋆∣st−1⋆,x)p_t := _ref(a_t s_t-1 ,x), the oracle threshold (1−1/L)pt⋆(1-1/L)p_t leaves a margin of only pt⋆/Lp_t /L below the mean empirical frequency. As L grows, this shrinking margin makes the filter more sensitive to downward sampling fluctuations. The sufficient condition in Corollary 1 includes N≳Cmax⋆L2log(2L/δ)N C_ L^2 (2L/δ) to control filtering errors, whereas the horizon experiment fixes the total sampling budget and therefore cannot increase the per-prefix sample size at this rate. With γ=0.3γ=0.3, the empirical threshold γp^max,t(st−1⋆)γ p_ ,t(s_t-1 ) can provide a lower cutoff when p^max,t(st−1⋆) p_ ,t(s_t-1 ) tracks pt⋆p_t . This reduces the risk of premature elimination, while potentially admitting more suboptimal candidates, and provides a plausible explanation for the observed empirical advantage. H.2 Additional Experiments over LLMs To complement the simulator experiments, we evaluate CF-Beam on a matrix-multiplication task using a pretrained LLM. This experiment examines whether the empirical confidence filter improves response accuracy under a comparable sampling budget when both the reference policy and the reward model are implemented by neural networks. Experimental setup. We evaluate Qwen3-1.7B-Base Yang et al. (2025) on 500500 synthetic 4×44× 4 integer matrix-multiplication problems. All methods sample from the same reference policy πref _ref, given by the base model at sampling temperature 1.31.3. Completed responses are scored by AceMath-7B-RM (Liu et al., 2025b), which supplies the outcome reward for methods that use reward-based selection. We compare Empirical CF-Beam with the same four baselines used in the simulator experiments: Best-of-N, Majority Voting, Best-of-Majority, and Vanilla-Beam. Both beam methods follow Algorithm 3, with per-prefix sample size N=12N=12 and beam width b=2b=2. For Empirical CF-Beam, we use the prefix-adaptive threshold βt(s)=γp^max,t(s) _t(s)=γ p_ ,t(s) with γ=0.3γ=0.3, as defined in the preceding subsection. We report the accuracy of the final selected response and the sampling budget, using the token-level policy-query accounting defined in the main text. Table 2: Comparison on 500500 synthetic 4×44× 4 integer matrix-multiplication problems using Qwen3-1.7B-Base. Beam methods use N=12N=12 and b=2b=2; Empirical CF-Beam uses γ=0.3γ=0.3. Budgets are reported in thousands of token-level policy queries. Best-of-N Majority Voting Best-of- Majority Vanilla-Beam CF-Beam Accuracy 0.332 0.304 0.326 0.372 0.388 Budget (×103× 10^3) 16.8 16.8 16.8 18.6 16.2 Comparison with baselines. Table 2 shows that Empirical CF-Beam achieves the highest accuracy among the evaluated methods, reaching 0.3880.388 with a sampling budget of 16.2k16.2k. This improves on Vanilla-Beam by 1.61.6 percentage points while using a smaller budget (16.2k16.2k versus 18.6k18.6k). Relative to the strongest sequence-level baseline, Best-of-N, CF-Beam improves accuracy by 5.65.6 percentage points, again with a slightly smaller sampling budget. These results provide evidence that confidence filtering can improve the accuracy–budget tradeoff in this LLM setting, consistent with the trends observed in the simulator experiments. Ablation over the filtering threshold and beam width. We further vary γ∈0,0.15,0.3,0.45,0.6,0.75,0.9γ∈\0,0.15,0.3,0.45,0.6,0.75,0.9\ and b∈2,4,8b∈\2,4,8\ while keeping N=12N=12 fixed. Here, γ=0γ=0 disables confidence filtering and recovers Vanilla-Beam. Since the response lengths and reward-model errors depend on the chosen model and task, this ablation focuses on the two algorithmic parameters γ and b. Table 3: Accuracy under different beam widths b and filtering coefficients γ on the same LLM task, with N=12N=12. The column γ=0γ=0 corresponds to Vanilla-Beam. Bold entries mark the highest accuracy for each beam width. γ=0γ=0 0.150.15 0.30.3 0.450.45 0.60.6 0.750.75 0.90.9 b=2b=2 0.372 0.378 0.388 0.372 0.318 0.292 0.290 b=4b=4 0.482 0.512 0.472 0.392 0.374 0.330 0.302 b=8b=8 0.536 0.550 0.480 0.434 0.364 0.292 0.300 Table 3 shows that the best accuracy is attained at a moderate filtering coefficient: γ=0.3γ=0.3 for b=2b=2 and γ=0.15γ=0.15 for b=4b=4 and b=8b=8. At each beam width, the best filtered configuration improves on Vanilla-Beam. Larger thresholds lead to substantially lower accuracy, consistent with overly aggressive filtering discarding useful continuations. These observations reflect the tradeoff between removing low-frequency tail candidates and preserving plausible reasoning trajectories. Increasing the beam width also improves the best observed accuracy, from 0.3880.388 at b=2b=2 to 0.5120.512 at b=4b=4 and 0.5500.550 at b=8b=8. This comparison holds the per-prefix sample size fixed; maintaining a wider beam generally requires a larger total sampling budget.