Paper deep dive
Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback
Jingkai Huang, Yunfan Zhang, Will Ma, Weihua Zhou, Zhengyuan Zhou
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Self-consistency samples many reasoning trajectories and aggregates their final answers, treating the LLM as a black box that returns one answer per trajectory. Yet the final answer of each trajectory is sampled from a softmax vector that is available from the model's log-probabilities. We refer to this as the grey-box setting in which each trajectory reveals this answer distribution rather than a single draw from it. We formulate efficient inference in this setting as sequential mode identification with distribution-valued observations: sample trajectories one at a time and stop as soon as the LLM's modal answer is identified at a prescribed confidence level. We characterize the asymptotic stopping rate of mode identification with distribution-valued observations exactly and show that it is never worse than the black-box rate. We then propose the ASC-D algorithm, a betting stopping rule that attains this asymptotic stopping rate. On MMLU-Redux, ASC-D uses $46.4$--$95.6\%$ fewer trajectories than answer-only adaptive self-consistency baselines and achieves the highest fixed-budget correct-certification rate across three open-source models.
Tags
Links
- Source: https://arxiv.org/abs/2609.38931v1
- Canonical: https://arxiv.org/abs/2609.38931v1
Trouble viewing inline? Open PDF directly →
Full Text
86,480 characters extracted from source content.
Expand or collapse full text
Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback Jingkai Huang Stern School of Business New York University jh9959@nyu.edu Yunfan Zhang11footnotemark: 1 Stern School of Business New York University yz11751@stern.nyu.edu Will Ma Graduate School of Business Columbia University wm2428@gsb.columbia.edu Weihua Zhou School of Management Zhejiang University larryzhou@zju.edu.cn Zhengyuan Zhou Stern School of Business New York University z26@stern.nyu.edu †thanks: Equal contribution. Abstract Self-consistency samples many reasoning trajectories and aggregates their final answers, treating the LLM as a black box that returns one answer per trajectory. Yet the final answer of each trajectory is sampled from a softmax vector that is available from the model’s log-probabilities. We refer to this as the grey-box setting in which each trajectory reveals this answer distribution rather than a single draw from it. We formulate efficient inference in this setting as sequential mode identification with distribution-valued observations: sample trajectories one at a time and stop as soon as the LLM’s modal answer is identified at a prescribed confidence level. We characterize the asymptotic stopping rate of mode identification with distribution-valued observations exactly and show that it is never worse than the black-box rate. We then propose the ASC-D algorithm, a betting stopping rule that attains this asymptotic stopping rate. On MMLU-Redux, ASC-D uses 46.446.4–95.6%95.6\% fewer trajectories than answer-only adaptive self-consistency baselines and achieves the highest fixed-budget correct-certification rate across three open-source models. 1 Introduction Large language models (LLMs) have demonstrated strong performance on challenging mathematical and logical reasoning tasks. When solving a complex problem, an LLM often produces a sequence of intermediate reasoning steps before giving its final answer, a generation pattern commonly known as chain-of-thought reasoning (Wei et al., 2022; Kojima et al., 2022). Because decoding is stochastic, repeatedly querying the same LLM can produce different reasoning trajectories and different final answers. Self-consistency (SC) exploits this diversity by sampling multiple reasoning trajectories and returning their most frequent final answer (Wang et al., 2022). Because each trajectory requires a separate LLM generation, the inference cost of SC grows with its sampling budget. Standard SC fixes this budget in advance, thus it may cause a computation waste on easy problems that require only a few trajectories. Adaptive self-consistency (ASC) addresses this inefficiency by sampling trajectories sequentially and stopping once the observed answers satisfy sufficient agreement (Aggarwal et al., 2023). Both SC and ASC retain only the final-answer label from each reasoning trajectory, which we refer to as the black-box observation model. Nevertheless, at the end of a trajectory, the probability vector from which the LLM decodes its final answer (token) is readily available and informative. Specifically, when Llama-3.2-3B-Instruct answers a four-choice ARC-Challenge question, we can read the next-token softmax over the four option tokens at the final-answer position, e.g., one recorded trajectory gives (0.26,0.43,0.21,0.10)(0.26,0.43,0.21,0.10) for options A–D, see Appendix B for details on how we obtain the probabilities. This raises a natural question: can such distribution-valued feedback further reduce the number of trajectories required for reliable self-consistency? We address this question by introducing adaptive self-consistency with distribution-valued feedback. Figure 1 contrasts it with the black-box model. Both start from the same reasoning process: a prompt x yields a sampled trajectory r, which induces a probability vector θ over the K candidate answers. The black-box model observes only one answer label drawn from θ, whereas our setting observes the vector itself (as well as the answer label). The two settings share the same answer frequencies and the same modal answer, and differ only in how much of θ they reveal. Thus, we call our observation model grey-box. In a white-box setting, where the token-level probabilities for all possible reasoning trajectories are available, we could in principle identify the modal answer without repeated sampling by directly calculating the final answer probabilities. However, enumerating and evaluating all possible trajectories is generally infeasible. Grey-box feedback therefore offers a practical middle ground between black-box and white-box: it retains trajectory sampling while using each trajectory’s probabilities for all candidate answers. (a) Black-box feedbackPromptxxTrajectoryrrLatent distribution θObserved labelo=ako=a_k(b) Grey-box feedbackPromptxxTrajectoryrrObserved vector=(θ1,⋯,θK) θ=( _1,·s, _K) Figure 1: Black-box and grey-box feedback from the same reasoning process. Building on this richer observation model, we study how much grey-box feedback can reduce the number of trajectories required for reliable mode identification and whether this improvement can be attained by a practical adaptive stopping rule. We summarize our main contributions below. 1. The benefit of grey-box feedback. For general distributions of answer-probability vectors, we derive a lower bound on the asymptotic sample complexity of any algorithm and show that grey-box feedback never requires more trajectories than black-box feedback. Specifically, for small frequency gap Δ between the modal answer and the runner-up, the sample complexity ranges from the black-box order Θ(Δ−2) ( ^-2), when every trajectory commits to a single answer, down to Θ(Δ−1) ( ^-1), when trajectories report the same beliefs. 2. An algorithm that fully realizes the benefit. We develop an algorithm for adaptive self-consistency with distribution-valued feedback (ASC-D), the grey-box counterpart of ASC. Instead of counting answer labels, ASC-D bets on pairwise differences of the probability vectors and stops once the leading answer has accumulated enough evidence against every alternative. It controls the probability of returning a non-modal answer at level δ at every stopping time, and its expected number of trajectories attains the lower bound asymptotically, without any knowledge of the distribution of the probability vectors. The gain identified above is therefore attained in full by a practical procedure. 3. Empirical validation. We validate our theoretical predictions through synthetic experiments and evaluations on MMLU-Redux. On MMLU-Redux, ASC-D uses 46.446.4–95.6%95.6\% fewer trajectories than answer-only baselines as the modal gap narrows. Under a fixed maximum budget of N=128N=128, it achieves the highest correct-certification rate at every tested confidence level across Llama-3.2-1B, Llama-3.1-8B, and Qwen3-1.7B. Organization The rest of the paper is organized as follows. Section 2 reviews related literature. Section 3 presents the problem setup, derives and compares asymptotic lower bounds on the expected stopping time under different observation models. Section 4 introduces the ASC-D algorithm and its theoretical guarantees. Section 5 reports the experiment results on both synthetic and real-world datasets, and Section 6 concludes with a discussion of limitations. Appendix A provides the proof of main results in the paper. Appendix B gives a real-world example of grey-box feedback. Appendices C and D provide omitted details and additional results for the synthetic and real-world experiments, respectively. 2 Related Literature Efficient and Adaptive Self-Consistency Adaptive self-consistency reduces the cost of fixed-budget self-consistency by stopping when the sampled answers show sufficient agreement (Aggarwal et al., 2023). Subsequent methods stop based on answer stability (Li et al., 2024), allocate sampling budgets using estimated question difficulty (Wang et al., 2025), or evaluate both answers and reasoning paths (Wan et al., 2025). Other approaches use scalar confidence signals to weight or filter reasoning trajectories (Taubenfeld et al., 2025; Fu et al., 2026). From a theoretical perspective, Huang et al. (2026a) and Huang (2026) compare the sample complexity of self-consistency and verifier-based best-of-N, showing a separation between their quadratic and linear dependence on the answer gap. Most closely related to our setting, Huang et al. (2026b) studies Bayesian stopping using prior information about answer frequencies, but observes only the final-answer labels. In contrast, our method does not require such prior information and instead gains efficiency by observing the full probability vector associated with each trajectory. Sequential Mode Identification and Anytime-Valid Inference. Our problem is also related to classical sequential hypothesis testing, which studies how to make a reliable decision using as few observations as possible (Wald, 1992; Siegmund, 2013). Sequential mode identification specializes this problem to identifying the most likely outcome of an unknown discrete distribution. Shah et al. (2020) study mode identification under different oracle-query models, while Jain et al. (2022) develops an asymptotically optimal stopping rule using sampled answer labels and martingale confidence sequences. Recent work applies anytime-valid inference to LLM self-consistency: MMC certifies an absolute majority (Cordero-Encinar and Duncan, 2025), whereas CITE certifies a candidate as the unique mode and also considers scalar confidence (Ota et al., 2026). Our work extends this literature from categorical or scalar-weighted observations to probability-vector observations and characterizes the resulting optimal stopping rate. 3 Problem Setup 3.1 Distribution-Valued Feedback For a fixed prompt x with a known set of candidate answers =a1,⋯,aKA=\a_1,·s,a_K\, each LLM call first generates a reasoning trajectory rnr_n and then produces a final answer. Formally, conditional on rnr_n and x, the model assigns a probability to each candidate answer, yielding the trajectory-specific distribution n:=ℙ(⋅∣rn,x)∈ΔK−1,θn,k:=ℙ(ak∣rn,x). θ_n:=P(\,· r_n,x)∈ ^K-1, _n,k:=P(a_k r_n,x). Standard black-box self-consistency returns only the realized answer on|n∼Cat(n)o_n θ_n ( θ_n) sampled from the categorical distribution with parameter n θ_n, whereas the grey-box setting observes the entire vector n θ_n. Because different reasoning trajectories can induce different answer distributions, these vectors may vary across calls. We write θ for a generic trajectory-specific distribution. General Model Since trajectories are sampled independently, the vectors (n)n≥1( θ_n)_n≥ 1 are i.i.d. drawn from an unknown distribution F on ΔK−1 ^K-1. Let ℳM denote the set of all distributions on ΔK−1 ^K-1 and :=F[]=(p1,⋯,pK) π:=E_F[ θ]=(p_1,·s,p_K) for the mean vector of F. We assume throughout that F has a unique mode, and index the candidate answers so that p1>p2≥⋯≥pKp_1>p_2≥·s≥ p_K, and a1a_1 is the modal answer. In this model, the black-box answers are i.i.d. with ℙ(on=ak)=F[θk]=pkP(o_n=a_k)=E_F[ _k]=p_k. Thus, π is the answer-frequency vector of black-box self-consistency, and both observation models target the same modal answer a1a_1. 3.2 Sequential Mode Identification The goal of self-consistency is to identify the modal answer a1a_1 of the LLM, which is the answer that a majority vote over infinitely many trajectories would return. A sequential procedure samples trajectories one at a time, observes (n)n≥1( θ_n)_n≥ 1 in the grey-box setting or (on)n≥1(o_n)_n≥ 1 in the black-box setting, and consists of a stopping time τ with respect to the observations together with a recommendation a^τ a_τ. Stopping is the only decision: every trajectory costs one LLM call, and the procedure should stop as soon as the mode is identified at the prescribed error probability δ. δ-PAC Procedures A procedure is δ-PAC over ℳM if ℙF(a^τ≠a1)≤δfor every F∈ℳ with a unique mode,P_F( a_τ≠ a_1)≤δ every F with a unique mode, that is, its error guarantee holds whatever the trajectories do. Characteristic Time Following Garivier and Kaufmann (2016); Jain et al. (2022), we measure the efficiency of a δ-PAC procedure by the asymptotic constant of its expected stopping time as the confidence grows, lim infδ→0F[τ]/log(1/δ) _δ→ 0E_F[τ]/ (1/δ), and define the characteristic time of F as the best constant over all δ-PAC procedures, T⋆(F):=lim infδ→0F[τ]log(1/δ).T (F):= _δ→ 0 E_F[τ] (1/δ). By definition, every δ-PAC procedure needs at least T⋆(F)⋅log(1/δ)T (F)· (1/δ) trajectories on F asymptotically before stopping. Throughout we write Δ:=p1−p2,p¯:=p1+p22,Xj:=θ1−θj∈[−1,1](j≠1), :=p_1-p_2, p:= p_1+p_22, X_j:= _1- _j∈[-1,1] (j≠ 1), (1) where Δ is the gap between the top two answers and XjX_j is the margin of the mode over its j-th challenger in a single trajectory. The Characteristic Time under Black-Box In the black-box setting, the observations are i.i.d. Cat()Cat( π) whatever the law F, so the procedure sees only π. Shah et al. (2020); Jain et al. (2022) show that the characteristic time of mode identification from categorical samples is Tbb(F):=1p1⋅log2p1p1+p2+p2⋅log2p2p1+p2=4p¯Δ2⋅(1+O(Δ2)), T_ b(F):= 1p_1· 2p_1p_1+p_2+p_2· 2p_2p_1+p_2= 4 p ^2· (1+O( ^2) ), (2) where the expansion holds as Δ→0 → 0, see Appendix A for details. We write Tbb(F)T_ b(F) for this black-box characteristic time, which depends on F only through =F[] π=E_F[ θ]. The denominator is the Kullback–Leibler divergence from Cat()Cat( π) to the closest categorical law in which a2a_2 ties with a1a_1; the quadratic dependence on Δ is the price of resolving a small gap from the hard votes. Since grey-box feedback can always be reduced to black-box feedback by drawing o∼Cat()o ( θ), (2) is an upper bound on the grey-box characteristic time. Whether, and by how much, grey-box feedback improves on this bound is the question we turn to next. 3.3 Asymptotic Lower Bounds How much the grey-box feedback gain depends on how the probability vectors spread around their mean π, and two extreme laws with this mean bracket the possibilities. At one end, the degenerate law δ _ π puts all its mass at π: every trajectory reports the same beliefs. At the other end, the vertex law F0:=∑k=1Kpk⋅δkF_0:= _k=1^Kp_k· _ e_k puts θ at a vertex of the simplex with probability pkp_k: every trajectory commits to one answer, and θ carries no more information than the sampled label o. The following theorem gives the grey-box characteristic time for a general F and shows that these two laws are exactly the two extremes of the characteristic time. Theorem 3.1 (Asymptotic Lower Bound under Grey-box Feedback). For every δ-PAC procedure and every F∈ℳF with a unique mode, under the grey-box feedback model, lim infδ→0F[τ]log(1/δ)≥Tgb(F):=1minj=2,⋯,Kj(F),j(F):=maxλ∈[0,1]F[log(1+λ⋅(θ1−θj))]. _δ→ 0 E_F[τ] (1/δ)≥ T_ gb(F):= 1 _j=2,·s,KG_j(F), _j(F):= _λ∈[0,1]E_F [ (1+λ·( _1- _j) ) ]. (3) where we use Tgb(F)T_ gb(F) to denote the characteristic time for distribution F under the grey-box feedback model. Moreover, Tgb(δ)=1log(1+Δ)≤Tgb(F)≤Tgb(F0)=Tbb(F), T_ gb( _ π)= 1 (1+ )≤ T_ gb(F)≤ T_ gb(F_0)=T_ b(F), (4) i.e., the two endpoints are the grey-box characteristic times of the degenerate law and the vertex law, the most and the least consistent laws with the same answer frequencies. For the first part of the theorem: a standard change-of-measure argument (Kaufmann et al., 2016) gives a lower bound through KL minimization over alternative distributions (in which a1a_1 is not the unique mode). Making a competitor aja_j at least as likely as a1a_1 is equivalent to making the mean of Xj=θ1−θjX_j= _1- _j nonpositive. We show that it suffices to optimize over distributions of this margin. By utilizing the dual representation of Honda and Takemura (2015), we then turn this infinite-dimensional optimization over probability distributions into the one-dimensional maximization over λ∈[0,1]λ∈[0,1] in (3). Thus, j(F)G_j(F) is the minimum KL divergence needed for aja_j to be at least as likely as a1a_1, and the hardest competitor determines the characteristic time. The sandwich bound in (4) can then be derived simply through the Jensen’s inequality. The Value of the Grey-Box Observation Model Under the vertex law F0F_0, every trajectory commits to a single answer and the grey-box observation carries no more information than the sampled answer; accordingly Tgb(F0)=Tbb(F)T_ gb(F_0)=T_ b(F), and the upper bound is attained exactly at this black-box endpoint. Any law that keeps mass away from the vertices stops strictly faster. The gain is bounded, however. Even when every trajectory reports π exactly, a δ-PAC procedure cannot exclude the law that agrees with δ _ π on a fraction 1/(1+Δ)1/(1+ ) of the trajectories and commits to a2a_2 on the rest, whose divergence from δ _ π is log(1+Δ) (1+ ), and it says that without further assumptions the dependence on the gap improves from Θ(Δ−2) ( ^-2) to at best Θ(Δ−1) ( ^-1). Connection with Best-of-N Best-of-N is another widely applied method for test-time compute, which samples N trajectories and selects the answer with the highest verifier score (Cobbe et al., 2021). With an ideal verifier, it succeeds whenever a correct answer appears among the samples. Assuming that the modal answer is correct, Huang (2026) show that the worst-case sample complexity scales as Θ(Δ−1) ( ^-1) for best-of-N, compared with Θ(Δ−2) ( ^-2) for self-consistency. In contrast, our Theorem 3.1 shows that, at the degenerate law δ _ π, grey-box self-consistency has characteristic time 1/log(1+Δ)=Θ(Δ−1)1/ (1+ )= ( ^-1). Thus, maximally consistent grey-box feedback yields the same linear inverse-gap dependence as the worst-case benchmark for ideal best-of-N, using the LLM’s own answer probabilities available under our distribution-valued observation model, without training or evaluating a separate verifier. Connection with Confidence-Weighted ASC Between the black-box and grey-box observation models lies confidence-weighted self-consistency (Taubenfeld et al., 2025; Fu et al., 2026; Ota et al., 2026), in which each trajectory reveals its sampled answer together with the confidence it assigns to that answer. We formalize this feedback as observing the sampled answer together with its conditional probability given the reasoning trajectory: o∣∼Cat(),w:=θo∈(0,1].o θ ( θ), w:= _o∈(0,1]. The pair (o,w)(o,w) can be generated from θ and reduces to o once w is dropped. Thus, when all three feedback models are used to identify the same modal answer a1a_1, the reduction argument of Section 3.2 places the confidence-feedback characteristic time between the black-box and grey-box times. The following proposition characterizes this intermediate rate, where we write QFQ_F for the law of (o,w)(o,w) for ∼F θ F. Proposition 3.1 (Asymptotic Lower Bound under Confidence Feedback). For every F∈ℳF with unique mode a1a_1, any procedure that observes (o,w)(o,w) and is δ-PAC over ℳM satisfies: lim infδ→0F[τ]log(1/δ)≥Tcw(F):=[minj≠1infF′∈ℳ:F′[θj]≥F′[θ1]DKL(QF∥QF′)]−1. _δ→ 0 E_F[τ] (1/δ)≥ T_ cw(F):= [ _j≠ 1 _ subarraycF :E_F [ _j] _F [ _1] subarrayD_KL(Q_F\|Q_F ) ]^-1. (5) Moreover, Tgb(F)≤Tcw(F)≤Tbb(F)T_ gb(F)≤ T_ cw(F)≤ T_ b(F). Proposition 3.1 shows that confidence feedback can reduce the characteristic time relative to observing only the sampled answer, while revealing the full answer distribution can yield a further reduction. The Gain under Dirichlet Heterogeneity To further quantify these gains, we now consider a Dirichlet model. We hold the answer frequencies π fixed and vary a single concentration parameter c, which controls the agreement across trajectories. This lets us compare all three characteristic times on the same family of instances. Assumption 1 (Dirichlet Heterogeneity). Assume F=Dir(c)F=Dir(c π) for a concentration c>0c>0, i.e., ∼Dir(cp1,⋯,cpK) θ (cp_1,·s,cp_K). Under Assumption 1, we still have [θk]=pkE[ _k]=p_k and Var(θk)=pk⋅(1−pk)c+1,Cov(θk,θj)=−pk⋅pjc+1(k≠j). ( _k)= p_k·(1-p_k)c+1, ( _k, _j)=- p_k· p_jc+1 (k≠ j). (6) The parameter c measures how much the trajectories agree with one another. As c→∞c→∞, F converges to the degenerate law δ _ π, and as c→0c→ 0 it converges to the vertex law F0F_0. Between the two endpoints, (6) shows that observing θk _k instead of the one-hot coordinate of o, whose variance is pk(1−pk)p_k(1-p_k), reduces the variance by exactly the factor c+1c+1. Assumption 1 makes the gain explicit through the single parameter c, interpolates between the black-box endpoint F0F_0 and the fully consistent endpoint δ _ π. Besides, although Tgb(Dir(c))T_ gb(Dir(c π)) still has no closed form for general π, in the hard regime p1≈p2p_1≈ p_2 it reduces to the black-box constant divided by a single factor, as shown in the following proposition. Proposition 3.2 (Characteristic Time under the Dirichlet Assumption). Let F=Dir(c)F=Dir(c π). Fix c>0c>0, p¯ p and (p3,⋯,pK)(p_3,·s,p_K), and let Δ→0 → 0. Then Tgb(F)=Tbb(F)c+1⋅(1+O(Δ)), T_ gb(F)= T_ b(F)c+1· (1+O( ) ), (7) and the maximizer in (3) is λ⋆=(c+1)Δ2p¯⋅(1+O(Δ))λ = (c+1) 2 p·(1+O( )) for j=2j=2. For fixed Δ and c→∞c→∞, Tgb(F)→1/log(1+Δ)T_ gb(F)→ 1/ (1+ ). The following table compares the three feedback models on the same Dirichlet instances. Confidence feedback gives an intermediate gain, with a substantial gap from grey-box feedback at moderate c. Besides, the approximation Tbb(F)/(c+1)T_ b(F)/(c+1) closely matches Tgb(F)T_ gb(F) for small c. As c increases, however, the approximation tends to zero, while Tgb(F)T_ gb(F) approaches the limit 1/log(1+Δ)1/ (1+ ). Table 1: Characteristic times for F=Dir(c)F=Dir(c π) with =(0.4,0.3,0.2,0.1) π=(0.4,0.3,0.2,0.1). For all c, Tbb(F)=139.52T_ b(F)=139.52 and 1/log(1+Δ)=10.491/ (1+ )=10.49. The values of Tcw(F)T_ cw(F) and Tgb(F)T_ gb(F) are computed numerically through simulation. The last row is the fixed-c, small-gap approximation in (7). c 0.010.01 0.10.1 11 22 33 55 1010 2020 5050 100100 10001000 Tcw(F)T_ cw(F) 139.52139.52 139.50139.50 138.22138.22 125.66125.66 109.15109.15 84.9984.99 55.7655.76 33.7033.70 15.6215.62 11.8511.85 10.7610.76 Tgb(F)T_ gb(F) 138.15138.15 126.95126.95 70.3370.33 47.2447.24 35.7035.70 24.1724.17 15.0115.01 12.3412.34 11.1611.16 10.8210.82 10.5210.52 Tbb(F)/(c+1)T_ b(F)/(c+1) 138.14138.14 126.84126.84 69.7669.76 46.5146.51 34.8834.88 23.2523.25 12.6812.68 6.646.64 2.742.74 1.381.38 0.140.14 4 The ASC-D Algorithm 4.1 From the Rate to the Algorithm The rate in Theorem 3.1 tells us which statistic to compute: Consider a gambler who starts with wealth 11 and, on every trajectory i, bets a fraction λ of his wealth on “aka_k beats aja_j”, receiving 1+λ⋅(θi,k−θi,j)1+λ·( _i,k- _i,j) per unit bet. After n trajectories his wealth is Wn(k,j)(λ):=∏i=1n(1+λ⋅(θi,k−θi,j)),λ∈[0,1), W_n^(k,j)(λ):= _i=1^n (1+λ·( _i,k- _i,j) ), λ∈[0,1), (8) which is nonnegative because θi,k−θi,j≥−1 _i,k- _i,j≥-1, and j(F)G_j(F) is the best expected log-wealth per trajectory of the bet on “a1a_1 beats aja_j”. The process has the two properties a stopping statistic needs. Validity at Stopping Time If aka_k does not beat aja_j, i.e., F[θk−θj]≤0E_F[ _k- _j]≤ 0, then F[1+λ(θi,k−θi,j)]≤1E_F[1+λ( _i,k- _i,j)]≤ 1, so (8) is a nonnegative supermartingale with initial value 11, and Ville’s inequality gives ℙF(supn≥1Wn(k,j)(λ)≥1α)≤α.P_F ( _n≥ 1W_n^(k,j)(λ)≥ 1α )≤α. Wealth above 1/α1/α is therefore evidence at level α that aka_k beats aja_j, and the guarantee holds uniformly over time, which is what a data-dependent stopping rule requires. Growth at the Optimal Rate If a1a_1 beats aja_j, the law of large numbers gives 1nlogWn(1,j)(λ)→F[log(1+λ(θ1−θj))] 1n W_n^(1,j)(λ) _F[ (1+λ( _1- _j))], so at the optimal fraction the wealth grows at rate j(F)G_j(F) and crosses 1/δ1/δ after log(1/δ)/j(F) (1/δ)/G_j(F) trajectories, as illustrated by Theorem 3.1. However, we note that two quantities in this argument are unknown to the procedure: the optimal fraction λ and the modal answer itself. Unknown Optimal Fraction The optimal fraction depends on F. As F is itself unknown, we consider to average the wealth over a finite grid Λ⊂[0,1) ⊂[0,1), W¯n(k,j):=1|Λ|∑λ∈ΛWn(k,j)(λ). W_n^(k,j):= 1| | _λ∈ W_n^(k,j)(λ). (9) A convex combination of supermartingales is a supermartingale, so validity is preserved, and logW¯n(k,j)≥maxλ∈ΛlogWn(k,j)(λ)−log|Λ| W_n^(k,j)≥ _λ∈ W_n^(k,j)(λ)- | |, so the averaged wealth grows at the best rate on the grid, maxλ∈ΛF[log(1+λ(θ1−θj))] _λ∈ E_F[ (1+λ( _1- _j))], only at the price of a constant that does not affect the rate. The choice of the grid will be discuss in the following subsection. Unknown Mode Answer As the algorithm cannot know in advance which answer to bet on (i.e., which answer is the modal answer), so it calculates (9) for every ordered pair (k,j)(k,j). The current leader is the answer with the largest cumulative mass Sn,k:=∑i≤nθi,kS_n,k:= _i≤ n _i,k, the grey-box counterpart of the plurality vote, and the procedure stops once the leader’s averaged wealth against every challenger exceeds (K−1)/δ(K-1)/δ. An error means that some ak≠a1a_k≠ a_1 is returned, which requires W¯n(k,1)≥(K−1)/δ W_n^(k,1)≥(K-1)/δ for a pair in which aka_k does not beat a1a_1. As each of these K−1K-1 events has probability at most δ/(K−1)δ/(K-1) by Ville’s inequality, and a union bound to the K−1K-1 components then gives the error probability δ. Algorithm 1 provides the detailed procedure. If we use only the sampled answer from each trajectory instead of its full answer distribution, ASC-D reduces to the known-K adaptation of CITE (Ota et al., 2026). Using full answer distributions allows ASC-D to also use the probabilities assigned to answers that were not sampled. Our later analysis will quantify this information gain and shows that ASC-D attains the optimal characteristic time Tgb(F)T_ gb(F) with a properly designed betting grid. Algorithm 1 ASC-D: adaptive self-consistency with distribution-valued feedback 1: prompt x, candidate answers a1,⋯,aK\a_1,·s,a_K\, confidence δ, grid Λ . 2: ℓk,j(λ)←0 _k,j(λ)← 0 for all k≠jk≠ j and λ∈Λλ∈ ; Sk←0S_k← 0 for all k 3: for n=1,2,⋯n=1,2,·s do 4: sample a trajectory rn∼ℙ(⋅∣x)r_n (· x) and read off n=ℙ(⋅∣rn,x) θ_n=P(· r_n,x) over the candidate set 5: Sk←Sk+θn,kS_k← S_k+ _n,k for all k ⊳ cumulative mass of each answer 6: ℓk,j(λ)←ℓk,j(λ)+log(1+λ⋅(θn,k−θn,j)) _k,j(λ)← _k,j(λ)+ (1+λ·( _n,k- _n,j) ) for all k≠jk≠ j and λ∈Λλ∈ 7: k^←argmaxkSk k← _kS_k ⊳ current leader 8: logW¯j←log1|Λ|∑λ∈Λexp(ℓk^,j(λ)) W_j← 1| | _λ∈ ( _ k,j(λ) ) for all j≠k^j≠ k ⊳ averaged against each challenger 9: if minj≠k^logW¯j≥logK−1δ _j≠ k W_j≥ K-1δ then 10: return ak^a_ k 11: end if 12: end for 4.2 Performance Guarantees Design of the Grid The grid Λ should approximate each challenger’s optimal betting fraction λj⋆ _j in (3). Two insights guide its design (see Appendix A for details). (i) The middle can be coarse; (i) Both ends should be dense. We therefore utilize the geometric grid Λr,m:=r−i:i=1,⋯,m∪1−r−i:i=1,⋯,m,r>1,m∈ℕ. _r,m:= \r^-i:\ i=1,·s,m \∪ \1-r^-i:\ i=1,·s,m \, r>1,\ m . (10) Asymptotic Upper Bound of ASC-D Define jΛ(F):=maxλ∈ΛF[log(1+λ⋅(θ1−θj))],TgbΛ(F):=1minj≠1jΛ(F), _j(F):= _λ∈ E_F [ (1+λ·( _1- _j) ) ], T_ gb (F):= 1 _j≠ 1G _j(F), (11) The following theorem provides the performance guarantees of Algorithm 1. Theorem 4.1 (Performance Guarantees of ASC-D). Let (τD,a^τD)(τ D, a_τ D) be the stopping time and the output of Algorithm 1 with grid Λ⊂[0,1) ⊂[0,1), then for every δ∈(0,1)δ∈(0,1), ℙF(τD<∞,a^τD≠a1)≤δP_F(τ D<∞,\ a_τ D≠ a_1)≤δ. (i) Let Λ=Λr,m = _r,m with r−m≤minj≠1λj⋆r^-m≤ _j≠ 1λ _j. We have lim supδ→0F[τD]log(1/δ)≤TgbΛ(F)≤r⋅Tgb(F) _δ→ 0 E_F[τ D] (1/δ)≤ T_ gb (F)≤ r· T_ gb(F). (i) Let Λ=Λrδ,mδ = _r_δ,m_δ with rδ:=1+(log(1/δ))−1/4r_δ:=1+ ( (1/δ) )^-1/4, and mδ:=⌈(log(1/δ))1/2⌉m_δ:= ( (1/δ))^1/2 . We have lim supδ→0F[τD]log(1/δ)≤Tgb(F). _δ→ 0 E_F[τ D] (1/δ)≤ T_ gb(F). (12) Together with Theorem 3.1, (12) gives, for every F with a unique mode, limδ→0F[τD]log(1/δ)=Tgb(F) _δ→ 0 E_F[τ D] (1/δ)=T_ gb(F). Thus, ASC-D can attain the optimal characteristic time of distribution-valued feedback exactly. 5 Experiments We evaluate whether distribution-valued feedback improves the sample efficiency of mode identification in both synthetic and real-world settings. In both settings, all methods target the same population mode and are evaluated on the same trajectories. We test sample efficiency in two ways: the number of generations needed to certify the mode at a fixed confidence level (i.e., the stopping time), and the probability of correct certification of the mode within a fixed maximum trajectory budget N (i.e., ℙ(a^τ=a1,τ≤N)P( a_τ=a_1,τ≤ N)). Section 5.1 studies the effect of the feedback type in synthetic datasets, and Section 5.2 tests whether the same gains persist on the probability vectors generated from live LLM calls. Code, stored probability vectors and trajectories, and experiment scripts are available at https://anonymous.4open.science/r/ICLR2027-ASCD-7B09/. 5.1 Controlled Comparison of Feedback Types We set K=4K=4 and consider Δ=(0.35+Δ/2,0.35−Δ/2,0.15,0.15) π_ =(0.35+ /2,0.35- /2,0.15,0.15), where 0<Δ≤0.40< ≤ 0.4 is the probability gap between the top-two answers. At each time t, we draw Zt∼Cat(Δ)Z_t ( π_ ), form t=12Zt+12Δ θ_t= 12 e_Z_t+ 12 π_ , and sample Yt|t∼Cat(t)Y_t θ_t ( θ_t). This construction gives [t]=ΔE[ θ_t]= π_ and Yt∼Cat(Δ)Y_t ( π_ ). We compare the ASC-D with observation of t θ_t, a confidence-weighted variant using θt,Yt⋅Yt _t,Y_t· e_Y_t, and CITE-4 (Ota et al., 2026) using Yt e_Y_t and its native certification rule. All procedures use the same 15-point grid, and we run 10,000 paired replays per condition. Table 2: Controlled comparison of feedback types. (a) Mean stopping time under 1−δ=0.951-δ=0.95 Δ ASC-D Conf.-wt. CITE-4 0.10 188.42 444.57 907.72 0.20 46.20 99.21 231.54 0.30 26.79 46.58 109.82 0.40 20.62 32.12 71.72 (b) Correct-certification rate under Δ=0.1 =0.1 1−δ1-δ ASC-D Conf.-wt. CITE-4 0.90 98.44% 71.37% 30.86% 0.95 97.49% 62.49% 24.22% 0.975 96.40% 54.83% 18.38% 0.99 94.23% 45.11% 12.73% Table 2(a) shows that under the 95%95\% confidence level, ASC-D uses 35.835.8–57.6%57.6\% fewer than the confidence-weighted method, and 71.371.3–80.1%80.1\% fewer than CITE-4, with larger savings at smaller gaps. For the harder setting Δ=0.1 =0.1 with a maximum trajectory budget of N=512N=512, Table 2(b) shows that ASC-D correctly certifies the mode in 94.2394.23–98.44%98.44\% of trials across the tested confidence levels, substantially more often than the reduced-feedback methods. Note that the correct-certification rate decreases as the confidence requirement 1−δ1-δ becomes stricter, since the fixed budget constraint leaves less time to accumulate the required evidence. Together, these results establish ASC-D as the most sample-efficient among the evaluated methods. Appendix C further validates ASC-D’s characteristic-time scaling and the concentration-dependent gain in Proposition 3.2. 5.2 Real-World Experiments Exp. 1: Required number of trajectory generations across modal gaps. For each of 120 MMLU-Redux questions, we use 256 Qwen3-1.7B trajectories and rescale their stored answer logits with Ta∈4,8,16,32T_a∈\4,8,16,32\, where larger TaT_a flattens the vectors and narrows the modal gap. At each temperature, the rescaled vectors define the empirical population F^=256−1∑i=1256δi F=256^-1 _i=1^256 _ θ_i, with mean ^=256−1∑i=1256i π=256^-1 _i=1^256 θ_i, mode index a⋆=argmaxkπ^ka = _k π_k, and modal gap Δ=π^a⋆−maxj≠a⋆π^j = π_a - _j≠ a π_j. We then run 500 paired replays by sampling uniformly from F F. ASC-D observes t θ_t; its matched one-hot ablation observes Yt e_Y_t with Yt|t∼Cat(t)Y_t θ_t ( θ_t); CITE-4 and PPR-1v1 (Jain et al., 2022) observe the same YtY_t. The number of trajectory generation (Num. Gen.) is the stopping time for each method under confidence level 95%95\%, and answer accuracy (Ans. Acc.) is evaluated against the correct answer. We observe benefits of our ASC-D over other benchmarks among all the 120 questions. Specifically, we focus on the 90 questions that retain the same ordered top-two answers across temperatures and for which every method attains the 95% success target within the maximum budget of 32,768 trajectories. Table 3 reports the corresponding results on these 90 questions. Table 3: Number of trajectory generations required for 95%95\% confidence and the answer accuracy on the 90 common questions. Here, Δgeo _ geo denotes the geometric mean of the modal gap. ASC-D ASC-D (one-hot) PPR-1v1 CITE-4 TaT_a Δgeo _geo Num. Gen. Ans. Acc. Num. Gen. Ans. Acc. Num. Gen. Ans. Acc. Num. Gen. Ans. Acc. 4 0.61 24.67 72.51% 41.82 71.83% 46.05 71.65% 58.19 71.70% 8 0.42 27.82 72.40% 90.73 70.97% 99.21 70.92% 113.92 70.94% 16 0.21 42.17 72.36% 346.55 70.78% 380.76 70.77% 403.87 70.78% 32 0.10 76.87 72.16% 1593.49 70.73% 1732.97 70.74% 1711.74 70.74% The results yield two main findings. First, as TaT_a increases from 44 to 3232, the geometric-mean gap decreases from 0.6100.610 to 0.0980.098, and ASC-D’s advantage grows. It uses 41.041.0–95.2%95.2\% fewer trajectories than its matched one-hot ablation, 46.446.4–95.6%95.6\% fewer than PPR-1v1, and 57.657.6–95.5%95.5\% fewer than CITE-4. Because full-vector and one-hot ASC-D use the same stopping rule and differ only in the observed feedback, their comparison isolates the benefit of distribution-valued feedback. These savings come without a loss in answer accuracy. Second, regressing each question’s log required budget on log(1/Δ) (1/ ) gives a median slope of 0.7660.766 for ASC-D, versus 1.9691.969, 1.9661.966, and 1.8541.854 for its one-hot ablation, PPR-1v1, and CITE-4, respectively. This finite-range comparison supports the predicted near-linear rather than quadratic dependence on the inverse gap, and that the ASC-D slope below one is not an asymptotic claim. Appendix D reports bootstrap confidence intervals and the corresponding log–log plot. Exp. 2: Correct certification within a fixed budget. At the natural answer temperature Ta=1T_a=1, we fix the maximum budget at N=128N=128 and evaluate the same 90 MMLU-Redux questions used in Exp. 1 across Qwen3-1.7B, Llama-3.2-1B, and Llama-3.1-8B. For each model and question, the first 128 probability vectors define F F, π, and a⋆a as in Exp. 1. We run 200 paired replays at 1−δ∈0.95,0.975,0.991-δ∈\0.95,0.975,0.99\. At each step, we sample t θ_t uniformly from F F and draw Yt|t∼Cat(t)Y_t θ_t ( θ_t). ASC-D observes t θ_t, while CITE-4 and PPR-1v1 observe the matched draw YtY_t. A replay succeeds only if the method stops within the fixed maximum budget and returns a⋆a . Table 4: Correct-certification rate within N=128N=128 trajectories on the 90 common questions. Model Method 1−δ=0.951-δ=0.95 1−δ=0.9751-δ=0.975 1−δ=0.991-δ=0.99 Llama-3.2-1B ASC-D 56.57% 53.38% 49.83% CITE-4 37.51% 35.21% 32.93% PPR-1v1 36.11% 34.14% 31.94% Llama-3.1-8B ASC-D 80.62% 78.84% 76.44% CITE-4 71.69% 69.48% 66.94% PPR-1v1 70.34% 68.34% 66.01% Qwen3-1.7B ASC-D 90.75% 89.83% 88.77% CITE-4 89.29% 88.39% 87.44% PPR-1v1 88.69% 87.97% 87.03% Table 4 shows that ASC-D achieves the highest correct-certification rate for every model and confidence level. Its advantage is largest on Llama-3.2-1B, where it exceeds CITE-4 and PPR-1v1 by up to 19.0619.06 percentage points and 20.4620.46 percentage points, respectively, highlighting the value of distribution-valued feedback. 6 Conclusion and Limitations In this paper, we show that observing the LLM’s probabilities for all candidate answers on each trajectory can reduce the number of trajectories needed to identify the LLM’s most consistent answer. Our analysis characterizes the optimal asymptotic rate and proposes ASC-D, an algorithm that attains this rate with a suitable betting grid. The limitations of this work are as follows: (i) ASC-D identifies the LLM’s most consistent answer, which need not be the correct answer, and therefore inherits self-consistency’s failure mode when the model is confidently wrong; (i) the method requires log-probabilities over a finite candidate set, covering multiple-choice and short-answer tasks with specified candidates but not directly open-ended generation with an unbounded answer space; and (i) our experiments are limited to small open-source models and multiple-choice benchmarks, with evaluation on larger models and open-ended reasoning tasks left for future work. References Aggarwal et al. (2023) Pranjal Aggarwal, Aman Madaan, Yiming Yang, et al. Let’s sample step by step: Adaptive-consistency for efficient reasoning and coding with llms. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 12375–12396, 2023. Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. Cordero-Encinar and Duncan (2025) Paula Cordero-Encinar and Andrew B Duncan. Certified self-consistency: Statistical guarantees and test-time training for reliable reasoning in llms. arXiv preprint arXiv:2510.17472, 2025. Fu et al. (2026) Yichao Fu, Xuewei Wang, Hao Zhang, Yuandong Tian, and Jiawei Zhao. Deep think with confidence. In International Conference on Learning Representations, volume 2026, pages 94355–94377, 2026. Garivier and Kaufmann (2016) Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998–1027. PMLR, 2016. Honda and Takemura (2015) Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. The Journal of Machine Learning Research, 16(1):3721–3756, 2015. Huang (2026) Baihe Huang. Large Language Models as Statistical Decision-Makers at Inference Time. PhD thesis, University of California, Berkeley, 2026. Huang et al. (2026a) Baihe Huang, Shanda Li, Tianhao Wu, Yiming Yang, Ameet Talwalkar, Kannan Ramchandran, Michael Jordan, and Jiantao Jiao. Sample complexity and representation ability of test-time scaling paradigms. In International Conference on Learning Representations, volume 2026, pages 54262–54298, 2026a. Huang et al. (2026b) Jingkai Huang, Will Ma, and Zhengyuan Zhou. Optimal bayesian stopping for efficient inference of consistent llm answers. arXiv preprint arXiv:2602.05395, 2026b. Jain et al. (2022) Shubham Anand Jain, Rohan Shah, Sanit Gupta, Denil Mehta, Inderjeet J Nair, Jian Vora, Sushil Khyalia, Sourav Das, Vinay J Ribeiro, and Shivaram Kalyanakrishnan. Pac mode estimation using ppr martingale confidence sequences. In International Conference on Artificial Intelligence and Statistics, pages 5815–5852. PMLR, 2022. Kaufmann et al. (2016) Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1–42, 2016. Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199–22213, 2022. Li et al. (2024) Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang, and Kan Li. Escape sky-high cost: Early-stopping self-consistency for multi-step reasoning. In International Conference on Learning Representations, volume 2024, pages 14751–14768, 2024. Ota et al. (2026) Hirofumi Ota, Naoto Iwase, Yuki Ichihara, Junpei Komiyama, and Masaaki Imaizumi. CITE: Anytime-valid statistical inference in LLM self-consistency. arXiv preprint arXiv:2605.05873, 2026. Shah et al. (2020) Dhruti Shah, Tuhinangshu Choudhury, Nikhil Karamchandani, and Aditya Gopalan. Sequential mode estimation with oracle queries. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):5644–5651, 2020. Siegmund (2013) David Siegmund. Sequential analysis: tests and confidence intervals. Springer Science & Business Media, 2013. Taubenfeld et al. (2025) Amir Taubenfeld, Tom Sheffer, Eran Ofek, Amir Feder, Ariel Goldstein, Zorik Gekhman, and Gal Yona. Confidence improves self-consistency in llms. In Findings of the Association for Computational Linguistics: ACL 2025, pages 20090–20111, 2025. Wald (1992) Abraham Wald. Sequential tests of statistical hypotheses. In Breakthroughs in statistics: Foundations and basic theory, pages 256–298. Springer, 1992. Wan et al. (2025) Guangya Wan, Yuqi Wu, Jie Chen, and Sheng Li. Reasoning aware self-consistency: Leveraging reasoning paths for efficient llm sampling. 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), pages 3613–3635, 2025. Wang et al. (2025) Xinglin Wang, Shaoxiong Feng, Yiwei Li, Peiwen Yuan, Yueqi Zhang, Chuyi Tan, Boyuan Pan, Yao Hu, and Kan Li. Make every penny count: Difficulty-adaptive self-consistency for cost-efficient reasoning. In Findings of the Association for Computational Linguistics: NAACL 2025, pages 6919–6932, 2025. Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022. Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022. Appendix A Proof of Main Results Characteristic Time for the Black-box Observation Model The reciprocal of the black-box constant is the KL divergence from Cat(π)Cat(π) to the merge alternative, 1Tbb(F)=p1logp1p¯+p2logp2p¯=g(p¯+Δ2)+g(p¯−Δ2),g(x):=xlogxp¯. 1T_ b(F)=p_1 p_1 p+p_2 p_2 p=g ( p+ 2 )+g ( p- 2 ), g(x):=x x p. Expanding g around p¯ p, we have g(p¯)=0g( p)=0, g′(p¯)=1g ( p)=1 and g′(p¯)=1/p¯g ( p)=1/ p. The first-order terms of the two summands are +Δ2+ 2 and −Δ2- 2 and cancel, so only the second-order terms remain: 1Tbb(F)=2⋅12g′(p¯)(Δ2)2+O(Δ4)=Δ24p¯+O(Δ4),henceTbb(F)=4p¯Δ2⋅(1+O(Δ2)). 1T_ b(F)=2· 12\,g ( p) ( 2 )^2+O( ^4)= ^24 p+O( ^4), T_ b(F)= 4 p ^2· (1+O( ^2) ). The cancellation is the whole reason for the quadratic rate: the merge moves p1p_1 and p2p_2 by the same amount in opposite directions, so the divergence has no linear part in Δ . Proof of Theorem 3.1. For distribution F with unique mode a1a_1, we define the alternative set Alt(F)Alt(F) as Alt(F):=F′∈ℳ:argmaxkF′[θk]≠1=⋃j=2KF′:F′[Xj]≤0,Alt(F):=\F : _kE_F [ _k]≠ 1\= _j=2^K\F :E_F [X_j]≤ 0\, i.e., Alt(F)Alt(F) stands for the set of distributions in ℳM for which a1a_1 is not the unique mode. We let Altj(F):=F′:F′[Xj]≤0Alt_j(F):=\F :E_F [X_j]≤ 0\ for all j≠1j≠ 1. Thus Alt(F)=∪j=2KAltj(F)Alt(F)= _j=2^KAlt_j(F). First, take an alternative F′∈Alt(F)F (F), and let E be the event that the procedure recommends a1a_1 as the unique mode. We have the procedure is δ-PAC at both F and the alternative F′F , i.e., ℙF(E)≥1−δ,ℙF′(E)≤δ.P_F(E)≥ 1-δ, _F (E)≤δ. Then, by applying Lemma 1 of Kaufmann et al. (2016), we can conclude the lower bound of: F[τ]⋅DKL(F∥F′)≥DKL(Bern(ℙF(E)∥ℙF′(E)))≥(1−2δ)⋅log1−δ.E_F[τ]·D_KL(F\|F ) _KL(Bern(P_F(E)\|P_F (E)))≥(1-2δ)· 1-δ. Therefore, taking the supremum over the alternative set, we obtain lim infδ→0F[τ]log(1/δ)≥1infF′∈Alt(F)DKL(F∥F′). _δ→ 0 E_F[τ] (1/δ)≥ 1 _F (F)D_KL(F\|F ). (13) Next, it suffices to calculate the denominator in (13). We have infF′∈Alt(F)DKL(F∥F′)=minj≠1infF′:F′[Xj]≤0DKL(F∥F′) aligned _F (F)D_KL(F\|F )= _j≠ 1 _F :E_F [X_j]≤ 0D_KL(F\|F ) aligned (14) according to the definition of Alt(F)Alt(F). For a distribution G on [−1,1][-1,1], we define inf(G):=infDKL(G∥G′):suppG′⊆[−1,1],G′[X]≤0, _ (G):= \D_KL(G\|G ): supp\,G [-1,1],\ E_G [X]≤ 0 \, (15) which represents the minimal KL divergence from the distribution G to the set of candidate distributions G′G supported on [−1,1][-1,1] with a mean less than or equal to 0. According to Proposition 1 of Honda and Takemura (2015), we have for any distribution G on [−1,1][-1,1] with positive mean, inf(G)=maxλ∈[0,1]G[log(1+λX)].K_ (G)= _λ∈[0,1]E_G[ (1+λ X)]. Fix j≠1j≠ 1, and let GjG_j be the law of XjX_j under F. For every F′∈Altj(F)F _j(F), the law Gj′G _j of XjX_j under F′F has nonpositive mean. Data processing inequality therefore implies DKL(F∥F′)≥DKL(Gj∥Gj′)≥inf(Gj).D_KL(F\|F ) _KL(G_j\|G _j) _ (G_j). To obtain the reverse inequality, we construct an alternative F′F that differs from F only in the distribution of XjX_j. Sampling from F can be viewed as two steps: first draw Xj∼GjX_j G_j, and then draw θ from its conditional distribution under F given XjX_j. Now we take any candidate law G′G in (15). Replace the first step by drawing Xj∼G′X_j G , while leaving the second step unchanged. Let F′F denote the resulting distribution of θ. Under F′F , the margin XjX_j has exactly the law G′G , whose mean is nonpositive. Thus F′∈Altj(F)F _j(F). Moreover, the conditional distribution used in the second step is the same under F and F′F , so it contributes no additional KL divergence. The chain rule for relative entropy therefore gives DKL(F∥F′)=DKL(Gj∥G′).D_KL(F\|F )=D_KL(G_j\|G ). Hence every candidate G′G in the one-dimensional problem gives a candidate F′F in the original problem with the same KL divergence. Taking the infimum over G′G proves the reverse inequality: infF′∈Altj(F)DKL(F∥F′)≤infG′:G′[X]≤0DKL(Gj∥G′)=inf(Gj). _F _j(F)D_KL(F\|F )≤ _G :E_G [X]≤ 0D_KL(G_j\|G )=K_ (G_j). Combining these two directions of the inequalities yields the equation of infF′∈Altj(F)DKL(F∥F′)=inf(Gj)=maxλ∈[0,1]F[log(1+λXj)]=j(F). _F _j(F)D_KL(F\|F )=K_ (G_j)= _λ∈[0,1]E_F[ (1+λ X_j)]=G_j(F). Taking the result back to (13) and (14), we obtain the main statement of the theorem. We then focus on the inequalities of 1Tbb(F)≤minj≠1j(F)≤log(1+Δ). 1T_ b(F)≤ _j≠ 1G_j(F)≤ (1+ ). (16) For the RHS of (16): for any F and λ∈[0,1]λ∈[0,1], since logx x is concave in x, by applying the Jensen’s inequality, F[log(1+λXj)]≤log(1+λF[Xj])=log(1+λ⋅(p1−pj))≤log(1+p1−pj).E_F[ (1+λ X_j)]≤ (1+ _F[X_j])= (1+λ·(p_1-p_j))≤ (1+p_1-p_j). Let j=2j=2 and we obtain minj≠1j(F)≤log(1+Δ) _j≠ 1G_j(F)≤ (1+ ). For F=δF= _ π, every margin is the positive constant p1−pjp_1-p_j, therefore j(δ)=log(1+p1−pj)G_j( _ π)= (1+p_1-p_j) and thus F=δF= _ π can achieve the upper bound. For the LHS of (16): concavity of the logarithm and ∑kθk=1 _k _k=1 give, for 0≤λ<10≤λ<1, log(1+λ(θ1−θj)) (1+λ( _1- _j)) =log(θ1(1+λ)+θj(1−λ)+∑k∉1,jθk) = ( _1(1+λ)+ _j(1-λ)+ _k∉\1,j\ _k ) ≥θ1log(1+λ)+θjlog(1−λ). ≥ _1 (1+λ)+ _j (1-λ). Taking expectations and optimizing over λ yields j(F) _j(F) ≥sup0≤λ<1p1log(1+λ)+pjlog(1−λ) ≥ _0≤λ<1\p_1 (1+λ)+p_j (1-λ)\ =Dj:=p1log2p1p1+pj+pjlog2pjp1+pj, =D_j:=p_1 2p_1p_1+p_j+p_j 2p_jp_1+p_j, (17) with the maximizer λ=(p1−pj)/(p1+pj)λ=(p_1-p_j)/(p_1+p_j). Because pj≤p2p_j≤ p_2 and log(1−λ)≤0 (1-λ)≤ 0, the supremum in (17) is at least its value with pjp_j replaced by p2p_2. Thus Dj≥D2D_j≥ D_2 for every j≠1j≠ 1, and minj≠1j(F)≥D2=1Tbb(F). _j≠ 1G_j(F)≥ D_2= 1T_ b(F). Finally, under the vertex law F0=∑kpkδkF_0= _kp_k _ e_k, the margin XjX_j equals 11, −1-1, and 00 with probabilities p1p_1, pjp_j, and 1−p1−pj1-p_1-p_j, respectively. Hence j(F0)=DjG_j(F_0)=D_j, and thus the vertex law F0F_0 can achieve the lower bound. ∎ Proof of Proposition 3.1. Let F∈ℳF have unique mode a1a_1, and recall that QFQ_F is the distribution of the observed pair (o,w)(o,w). We use the same alternative sets as in the proof of Theorem 3.1: Altj(F):=F′∈ℳ:F′[Xj]≤0,Alt(F)=⋃j≠1Altj(F),Alt_j(F):=\F :E_F [X_j]≤ 0\, (F)= _j≠ 1Alt_j(F), where Xj=θ1−θjX_j= _1- _j. Thus Alt(F)Alt(F) contains the distributions for which a1a_1 is not the unique mode. First take an alternative F′∈Alt(F)F (F) with a unique mode different from a1a_1, and let E be the event that the procedure recommends a1a_1. Since the procedure is δ-PAC under both F and F′F , ℙF(E)≥1−δ,ℙF′(E)≤δ.P_F(E)≥ 1-δ, _F (E)≤δ. The same change-of-measure argument used in the proof of Lemma 1 Kaufmann et al. (2016), now applied to observations with laws QFQ_F and QF′Q_F , gives, F[τ]⋅DKL(QF∥QF′)≥DKL(Bern(ℙF(E)∥ℙF′(E)))≥(1−2δ)⋅log1−δ.E_F[τ]·D_KL(Q_F\|Q_F ) _KL(Bern(P_F(E)\|P_F (E)))≥(1-2δ)· 1-δ. Similarly, taking the supremum over the alternative set, and letting δ→0δ→ 0, we obtain lim infδ→0F[τ]log(1/δ) _δ→ 0 E_F[τ] (1/δ) ≥1infF′∈Alt(F)DKL(QF∥QF′) ≥ 1 _F (F)D_KL(Q_F\|Q_F ) =[minj≠1infF′∈Altj(F)DKL(QF∥QF′)]−1=Tcw(F). = [ _j≠ 1 _F _j(F)D_KL(Q_F\|Q_F ) ]^-1=T_ cw(F). Finally, for the sandwich bound Tgb(F)≤Tcw(F)≤Tbb(F)T_ gb(F)≤ T_ cw(F)≤ T_ b(F): the pair (o,w)(o,w) can be generated from θ, and the sampled answer o is obtained by dropping w. The data processing inequality therefore gives, for every F′∈Alt(F)F (F), DKL(F∥F′)≥DKL(QF∥QF′)≥DKL(Cat()∥Cat(F′[])).D_KL(F\|F ) _KL(Q_F\|Q_F ) _KL (Cat( π)\|Cat(E_F [ θ]) ). Taking infima over the same alternative set, the first term gives 1/Tgb(F)1/T_ gb(F) by Theorem 3.1. The last term gives 1/Tbb(F)1/T_ b(F) in (2). Thus we obtain the desired result. Besides, we also note that this asymptotic lower bound is achievable through some properly designed algorithm (with similar idea to that of our ASC-D). We omit the details as this is not the main focus of the paper. ∎ Proof of Proposition 3.2. Throughout, F=Dir(cπ)F=Dir(cπ) and ϕj(λ):=F[log(1+λXj)] _j(λ):=E_F[ (1+λ X_j)], so that j(F)=maxλ∈[0,1]ϕj(λ)G_j(F)= _λ∈[0,1] _j(λ). Second moment of X2X_2. By (6), Var(X2)=Var(θ1)+Var(θ2)−2Cov(θ1,θ2)=p1(1−p1)+p2(1−p2)+2p1p2c+1=p1+p2−Δ2c+1,Var(X_2)=Var( _1)+Var( _2)-2Cov( _1, _2)= p_1(1-p_1)+p_2(1-p_2)+2p_1p_2c+1= p_1+p_2- ^2c+1, and since [X2]=ΔE[X_2]= , [X22]=2p¯−Δ2c+1+Δ2=2p¯c+1⋅(1+O(Δ2)). [X_2^2]= 2 p- ^2c+1+ ^2= 2 pc+1· (1+O( ^2) ). (18) Expansion of 2G_2. The function ϕ2 _2 is concave on [0,1][0,1], with ϕ2′(λ)=[X2/(1+λX2)] _2 (λ)=E[X_2/(1+λ X_2)] for 0≤λ<10≤λ<1. Fix λ0∈(0,1) _0∈(0,1). Since 1+λ0X2≤21+ _0X_2≤ 2, ϕ2′(λ0)=[X21+λ0X2]=[X2−λ0X221+λ0X2]≤Δ−λ02[X22], _2 ( _0)=E [ X_21+ _0X_2 ]=E [X_2- _0X_2^21+ _0X_2 ]≤ - _02\,E[X_2^2], which is negative for small Δ by (18). Since ϕ2′(0)=Δ>0 _2 (0)= >0, the maximizer λ⋆λ lies in (0,λ0)(0, _0), and we have: Δ=λ⋆[X221+λ⋆X2]≥λ⋆2[X22], =λ E [ X_2^21+λ X_2 ]≥ λ 2E[X_2^2], so λ⋆≤2Δ/[X22]=O(Δ)λ ≤ 2 /E[X_2^2]=O( ). On this interval, log(1+u)=u−u22+R(u) (1+u)=u- u^22+R(u) with |R(u)|≤C0|u|3|R(u)|≤ C_0|u|^3 for some constant C0>0C_0>0 for any |u|≤λ0|u|≤ _0, and |X2|3≤X22|X_2|^3≤ X_2^2 since |X2|≤1|X_2|≤ 1, so with u=λX2u=λ X_2, ϕ2(λ)=λΔ−λ22[X22]+r(λ),|r(λ)|≤C0λ3[X22]. _2(λ)=λ - λ^22\,E[X_2^2]+r(λ), |r(λ)|≤ C_0λ^3\,E[X_2^2]. (19) The quadratic part is maximized at λ^:=Δ/[X22]=(c+1)Δ2p¯⋅(1+O(Δ2)) λ:= /E[X_2^2]= (c+1) 2 p·(1+O( ^2)), which lies in [0,λ0][0, _0] for small Δ , with value Δ22[X22]=(c+1)Δ24p¯⋅(1+O(Δ2)) ^22E[X_2^2]= (c+1) ^24 p·(1+O( ^2)). Evaluating (19) at λ λ gives 2(F)≥(c+1)Δ24p¯(1+O(Δ2))−C0λ^3[X22]G_2(F)≥ (c+1) ^24 p(1+O( ^2))-C_0 λ^3E[X_2^2], and the remainder is O(Δ3)O( ^3) since λ^=O(Δ) λ=O( ). Conversely, the quadratic part at λ⋆λ is at most its value at λ λ, and r(λ⋆)=O(Δ3)r(λ )=O( ^3) because λ⋆=O(Δ)λ =O( ). Thus 2(F)≤Δ22[X22]+O(Δ3)G_2(F)≤ ^22E[X_2^2]+O( ^3). Therefore 2(F)=(c+1)Δ24p¯⋅(1+O(Δ)). _2(F)= (c+1) ^24 p· (1+O( ) ). (20) For the maximizer, ϕ2′(λ)=[X2]−λ[X22]+O(λ2[X22]) _2 (λ)=E[X_2]- [X_2^2]+O(λ^2E[X_2^2]) for λ≤λ0λ≤ _0, so the stationary condition ϕ2′(λ⋆)=0 _2 (λ )=0 gives λ⋆=Δ[X22]⋅(1+O(λ⋆))=(c+1)Δ2p¯⋅(1+O(Δ))λ = E[X_2^2]·(1+O(λ ))= (c+1) 2 p·(1+O( )). Along this limit, p1=p¯+Δ/2p_1= p+ /2 and p2=p¯−Δ/2p_2= p- /2. For K>2K>2, the fixed probabilities satisfy pj<p¯p_j< p for every j≥3j≥ 3, since pj≤p2p_j≤ p_2. The pairwise lower bound j(F)≥DjG_j(F)≥ D_j in (17) then gives lim infΔ→0j(F)>0 _ → 0G_j(F)>0 for each j≥3j≥ 3, whereas (20) gives 2(F)→0G_2(F)→ 0. Thus minj≠1j(F)=2(F) _j≠ 1G_j(F)=G_2(F) for sufficiently small Δ . For K=2K=2 this result is immediate. Combining (20) with the black-box expansion in (2), we thus obtain now Tgb(F) T_ gb(F) =12(F)=4p¯(c+1)Δ2(1+O(Δ)) = 1G_2(F)= 4 p(c+1) ^2 (1+O( ) ) =Tbb(F)c+1(1+O(Δ)). = T_ b(F)c+1 (1+O( ) ). ∎ Insights on the Grid Design The averaged wealth (9) grows at the best rate on the grid. For each challenger j≠1j≠ 1, let λj⋆∈(0,1] _j ∈(0,1] be a maximizer in (3), and write ϕj(λ):=F[log(1+λ(θ1−θj))],j(F)=ϕj(λj⋆). _j(λ):=E_F[ (1+λ( _1- _j))], _j(F)= _j( _j ). The optimal fraction depends on the unknown law F, so the grid must cover a range of possible values. The two insights are: (i) The middle can be coarse. The function ϕj _j is concave and satisfies ϕj(0)=0 _j(0)=0. Hence ϕj(λ)≥λj⋆j(F),0≤λ≤λj⋆. _j(λ)≥ λ _j G_j(F), 0≤λ≤ _j . Thus a point in [λj⋆/r,λj⋆][ _j /r, _j ], for r>1r>1, retains at least a fraction 1/r1/r of the optimal growth rate. The width of this interval is λj⋆(1−1/r) _j (1-1/r), so relatively coarse spacing suffices when the optimum lies in the middle of [0,1][0,1]. (i) Both ends should be dense. When λj⋆ _j is small, the interval [λj⋆/r,λj⋆][ _j /r, _j ] is narrow. Under Assumption 1, for example, λ2⋆≈(c+1)Δ/(2p¯) _2 ≈(c+1) /(2 p) tends to zero with the gap for fixed c and p¯ p. A uniform grid with spacing h cannot provide a positive point below the optimum once λj⋆<h _j <h. Geometrically spaced points r−ir^-i instead cover progressively smaller fractions. At the other endpoint, highly consistent trajectories can favor fractions close to 11. We therefore also include points 1−r−i1-r^-i, which approach 11 for large i. Proof of Theorem 4.1. We write ℱn:=σ(i:i≤n)F_n:=σ( θ_i:i≤ n) and Mi(k,j):=θi,k−θi,j∈[−1,1]M^(k,j)_i:= _i,k- _i,j∈[-1,1], so that Wn(k,j)(λ)=∏i≤n(1+λMi(k,j))W_n^(k,j)(λ)= _i≤ n(1+λ M^(k,j)_i) and F[Mi(k,j)]=pk−pjE_F[M^(k,j)_i]=p_k-p_j. Throughout, ϕj(λ):=F[log(1+λM1(1,j))] _j(λ):=E_F[ (1+λ M^(1,j)_1)], so that jΛ(F)=maxλ∈Λϕj(λ)G _j(F)= _λ∈ _j(λ) in (11), and for a finite grid Λ⊂[0,1) ⊂[0,1) we further define gΛ:=minj≠1jΛ(F)=1TgbΛ(F),BΛ:=maxλ∈Λlog11−λ.g_ := _j≠ 1G _j(F)= 1T_ gb (F), B_ := _λ∈ 11-λ. Fix k≠1k≠ 1 and λ∈Λλ∈ . Since pk−p1<0p_k-p_1<0, F[Wn(k,1)(λ)∣ℱn−1]=Wn−1(k,1)(λ)⋅(1+λ⋅(pk−p1))≤Wn−1(k,1)(λ),E_F [W_n^(k,1)(λ) _n-1 ]=W_n-1^(k,1)(λ)· (1+λ·(p_k-p_1) )≤ W_n-1^(k,1)(λ), so (Wn(k,1)(λ))n≥0(W_n^(k,1)(λ))_n≥ 0 is a nonnegative supermartingale with W0(k,1)(λ)=1W_0^(k,1)(λ)=1, and so is its average W¯n(k,1) W_n^(k,1) over λ∈Λλ∈ defined in (9). Ville’s inequality for the supermartingale gives ℙF(supn≥1W¯n(k,1)≥K−1δ)≤δK−1.P_F ( _n≥ 1 W_n^(k,1)≥ K-1δ )≤ δK-1. On the event τD<∞,a^τD=ak\τ^D<∞, a_τ^D=a_k\ the stopping condition of Algorithm 1 holds at time τDτ^D with leader k^τD=k k_τ^D=k, and in particular W¯τD(k,1)≥(K−1)/δ W_τ^D^(k,1)≥(K-1)/δ. Hence ℙF(τD<∞,a^τD≠a1)≤∑k=2KℙF(supn≥1W¯n(k,1)≥K−1δ)≤δ.P_F(τ^D<∞,\ a_τ^D≠ a_1)≤ _k=2^KP_F ( _n≥ 1 W_n^(k,1)≥ K-1δ )≤δ. Part (i). Let Λ=Λr,m = _r,m with r−m≤minj≠1λj⋆r^-m≤ _j≠ 1λ _j. Fix j≠1j≠ 1, ϕj _j is concave on [0,1][0,1] with ϕj(0)=0 _j(0)=0 and ϕj(λj⋆)=j(F)>0 _j( _j )=G_j(F)>0, so λj⋆>0λ _j>0. The grid contains a point λ∈[λj⋆/r,λj⋆]λ∈[ _j /r, _j ]: if λj⋆<r−1 _j <r^-1, then r−i≤λj⋆<r−i+1r^-i≤ _j <r^-i+1 for some 2≤i≤m2≤ i≤ m because r−m≤λj⋆r^-m≤ _j , and λ=r−iλ=r^-i falls within the bandwidth. If λj⋆≥r−1 _j ≥ r^-1, then λ=r−1λ=r^-1 falls within the bandwidth because λj⋆≤1 _j ≤ 1. For such λ, concavity and ϕj(0)=0 _j(0)=0 give ϕj(λ)=ϕj(λj⋆⋅λj⋆+(1−λj⋆)⋅0)≥λj⋆⋅j(F)≥j(F)r. _j(λ)= _j ( λ _j · _j + (1- λ _j )· 0 )≥ λ _j ·G_j(F)≥ G_j(F)r. Hence jΛ(F)≥j(F)/rG_j (F) _j(F)/r for every j≠1j≠ 1, i.e., gΛr,m≥1r⋅Tgb(F)>0andTgb(F)≤TΛr,m(F)≤r⋅Tgb(F). g_ _r,m≥ 1r· T_ gb(F)>0 T_ gb(F)≤ T_ _r,m(F)≤ r· T_ gb(F). (21) Next, we show that every finite grid Λ with gΛ>0g_ >0 satisfies lim supδ→0F[τD]/log(1/δ)≤TgbΛ(F) _δ→ 0E_F[τ^D]/ (1/δ)≤ T_ gb (F). For each j≠1j≠ 1 fix λj∈argmaxλ∈Λϕj(λ) _j∈ _λ∈ _j(λ), so that ϕj(λj)=jΛ(F)≥gΛ _j( _j)=G _j(F)≥ g_ . The variables Yi,j:=log(1+λjMi(1,j))Y_i,j:= (1+ _jM^(1,j)_i) are i.i.d. in i with mean ϕj(λj) _j( _j) and, since λj<1 _j<1 and |Mi(1,j)|≤1|M^(1,j)_i|≤ 1, bounded by |Yi,j|≤BΛ|Y_i,j|≤ B_ . Let L:=log((K−1)|Λ|/δ)L:= ((K-1)| |/δ ) and consider the good event En:=⋂j≠1∑i=1nYi,j≥L∩k^n=1E_n:= _j≠ 1 \ _i=1^nY_i,j≥ L \∩ \ k_n=1 \ that at time n, the leader is the true modal answer and the cumulative log wealth for each challenger j is greater than L. Condition on the good event EnE_n, we have for every j≠1j≠ 1, W¯n(1,j)≥|Λ|−1⋅Wn(1,j)(λj)=|Λ|−1⋅exp(∑i≤nYi,j)≥(K−1)/δ W_n^(1,j)≥| |^-1· W_n^(1,j)( _j)=| |^-1· ( _i≤ nY_i,j )≥(K-1)/δ (since the wealth is nonnegative), so the stopping condition holds at time n with leader a1a_1 and τD≤nτ^D≤ n. Therefore ℙF(τD>n)≤ℙF(Enc)P_F(τ^D>n) _F(E_n^c), and we bound the two parts of EncE_n^c by Hoeffding’s inequality: for i.i.d. Z1,⋯,Zn∈[a,b]Z_1,·s,Z_n∈[a,b] with mean μ and t>0t>0, we have ℙ(∑i=1nZi≤n⋅(μ−t))≤exp(−2nt2(b−a)2).P ( _i=1^nZ_i≤ n·(μ-t) )≤ (- 2nt^2(b-a)^2 ). First, k^n≠1 k_n≠ 1 requires Sn,1−Sn,k=∑i≤nMi(1,k)≤0S_n,1-S_n,k= _i≤ nM^(1,k)_i≤ 0 for some k≠1k≠ 1, and Mi(1,k)∈[−1,1]M^(1,k)_i∈[-1,1] has mean p1−pk≥Δp_1-p_k≥ , so ℙF(k^n≠1)≤∑k≠1ℙF(∑i≤nMi(1,k)≤0)≤(K−1)⋅exp(−nΔ2/2).P_F( k_n≠ 1)≤ _k≠ 1P_F ( _i≤ nM^(1,k)_i≤ 0 )≤(K-1)· (-n ^2/2). Second, fix ε∈(0,1) ∈(0,1) and let n0:=⌈L/((1−ε)gΛ)⌉n_0:= L/((1- )g_ ) . For n≥n0n≥ n_0 we have L≤(1−ε)⋅ngΛ≤nϕj(λj)−εngΛL≤(1- )· ng_ ≤ n _j( _j)- ng_ , so ∑i≤nYi,j<L _i≤ nY_i,j<L implies ∑i≤nYi,j≤n⋅(ϕj(λj)−εgΛ) _i≤ nY_i,j≤ n·( _j( _j)- g_ ), and Hoeffding’s inequality with [a,b]=[−BΛ,BΛ][a,b]=[-B_ ,B_ ] and t=εgΛt= g_ gives ℙF(∑i≤nYi,j<L)≤exp(−nε2gΛ22BΛ2),n≥n0.P_F ( _i≤ nY_i,j<L )≤ (- n ^2g_ ^22B_ ^2 ), n≥ n_0. With γ:=minΔ2/2,ε2gΛ2/(2BΛ2)>0γ:= \ ^2/2, ^2g_ ^2/(2B_ ^2)\>0 we obtain ℙF(τD>n)≤2(K−1)⋅e−γnP_F(τ^D>n)≤ 2(K-1)· e^-γ n for all n≥n0n≥ n_0. Hence τD<∞τ^D<∞ almost surely, and F[τD]=∑n≥0ℙF(τD>n)≤n0+∑n≥n02(K−1)⋅exp(−γn)≤log((K−1)|Λ|/δ)(1−ε)⋅gΛ+1+2(K−1)1−exp(−γ). splitE_F[τ^D]&= _n≥ 0P_F(τ^D>n)≤ n_0+ _n≥ n_02(K-1)· (-γ n)\\ &≤ ((K-1)| |/δ )(1- )· g_ +1+ 2(K-1)1- (-γ). split (22) For a fixed grid the last two terms do not depend on δ, so dividing by log(1/δ) (1/δ), letting δ→0δ→ 0 and then ε→0 → 0 gives lim supδ→0F[τD]/log(1/δ)≤TgbΛ(F) _δ→ 0E_F[τ^D]/ (1/δ)≤ T_ gb (F). Part (i). We write τδDτ^D_δ for the stopping time with the grid Λδ:=Λrδ,mδ _δ:= _r_δ,m_δ and ℓ:=log(1/δ) := (1/δ) and let δ be small enough so that ℓ≥1 ≥ 1. Now according to the definition, we have rδ=1+ℓ−1/4r_δ=1+ ^-1/4 and mδ:=⌈ℓ1/2⌉m_δ:= ^1/2 . Then 1<rδ≤21<r_δ≤ 2 and mδ≤2ℓ1/2m_δ≤ 2 ^1/2. Since log(1+x)≥x/2 (1+x)≥ x/2 for x∈[0,1]x∈[0,1], mδlogrδ≥ℓ1/2⋅12ℓ−1/4=12ℓ1/4→∞,m_δ r_δ≥ ^1/2· 12 ^-1/4= 12 ^1/4→∞, so rδ−mδ→0r_δ^-m_δ→ 0 and the condition rδ−mδ≤minj≠1λj⋆r_δ^-m_δ≤ _j≠ 1λ _j of Part (i) holds for all δ small enough. For such δ, (21) gives gΛδ≥1/(rδTgb(F))≥1/(2Tgb(F))g_ _δ≥ 1/(r_δT_ gb(F))≥ 1/(2T_ gb(F)), and the argument of Part (i) gives τδD<∞τ^D_δ<∞ almost surely together with (22). It remains to control how the grid enters (22). First, |Λδ|≤2mδ≤4ℓ1/2| _δ|≤ 2m_δ≤ 4 ^1/2, so log((K−1)|Λδ|)=O(logℓ) ((K-1)| _δ|)=O( ). Second, a point λ=1−rδ−iλ=1-r_δ^-i contributes log(1/(1−λ))=ilogrδ≤mδlogrδ≤mδ(rδ−1)≤2ℓ1/4 (1/(1-λ))=i r_δ≤ m_δ r_δ≤ m_δ(r_δ-1)≤ 2 ^1/4 to BΛδB_ _δ, and a point λ=rδ−iλ=r_δ^-i contributes at most log(1/(1−rδ−1))=log(1+1/(rδ−1))=log(1+ℓ1/4)≤ℓ1/4 (1/(1-r_δ^-1))= (1+1/(r_δ-1))= (1+ ^1/4)≤ ^1/4. Hence BΛδ≤2ℓ1/4B_ _δ≤ 2 ^1/4 and now we need γ≥minΔ22,ε232Tgb(F)2ℓ1/2.γ≥ \ ^22, ^232T_ gb(F)^2\, ^1/2 \. Using 1/(1−exp(−γ))≤1+1/γ1/(1- (-γ))≤ 1+1/γ, the last two terms of (22) are O(ℓ1/2)O( ^1/2) for fixed ε . Dividing (22) by ℓ and using 1/gΛδ≤rδTgb(F)1/g_ _δ≤ r_δT_ gb(F) gives: F[τδD]log(1/δ)≤rδ⋅Tgb(F)1−ε⋅(1+log((K−1)|Λδ|)ℓ)+O(ℓ−1/2)→δ→0Tgb(F)1−ε. E_F[τ^D_δ] (1/δ)≤ r_δ· T_ gb(F)1- · (1+ ((K-1)| _δ|) )+O( ^-1/2) [δ→ 0] T_ gb(F)1- . since rδ→1r_δ→ 1. Letting ε→0 → 0 then proves (12). ∎ Appendix B A Real-World Grey-Box Observation Example We give a complete example from the released demo data to make the grey-box observation model operationally concrete. The record is trajectory 0 (seed 20260922) for ARC-Challenge test item MCAS_2001_5_3, generated by mlx-community/Llama-3.2-3B-Instruct-bf16 at reasoning temperature Tr=0.6T_r=0.6 (top-p=0.95p=0.95, top-k=20k=20). Answer probabilities are evaluated at the natural temperature Ta=1T_a=1. Original problem Question: Which of the following is LEAST responsible for the weathering of rocks? A. freezing B. plant growth C. rain D. lightning The benchmark answer is D. Prompt The model receives the following system and user messages through its chat template. System: You are a careful reasoner. The final answer must be exactly one of A, B, C, or D. User: Solve this multiple-choice problem carefully. Question: Which of the following is LEAST responsible for the weathering of rocks? Options: A. freezing B. plant growth C. rain D. lightning Give a concise explanation in at most 120 words. Do not repeat the question or options. During this stage, do not output the final A/B/C/D letter and do not quote the exact chosen option. End exactly with <END_REASONING>. LLM output The sampled reasoning trajectory, before answer scoring, is: Plant growth is not a primary cause of weathering, as it primarily contributes to physical weathering through roots breaking apart the rock. Freezing, on the other hand, is a significant factor in chemical weathering, causing ice to expand and exert pressure on the rock, leading to cracking. Rain is a major contributor to physical weathering, as it can physically wear away the rock surface through erosion and abrasion. Lightning, while not directly causing weathering, can contribute to it by igniting wildfires that can further break down the rock. END_REASONING The observed probability vector After this trajectory, we append the decision prefix Final answer (one letter only): The prefix ends in the token "):" (token ID 1680). Each allowed continuation is one token: A (362), B (426), C (356), or D (423). Thus the observation comes from one precisely identified next-token position: the transitions from the terminal ): token to each of the four option tokens. If ℓk _k is the full-vocabulary log-probability of option token k at that position, we record qk=exp(ℓk),θk=exp(ℓk/Ta)∑j∈A,B,C,Dexp(ℓj/Ta).q_k= ( _k), _k= ( _k/T_a) _j∈\A,B,C,D\ ( _j/T_a). For this trajectory, the exact values are: Table 5: A single real-world grey-box observation. The raw probabilities qkq_k are the full-vocabulary next-token probabilities assigned to the four allowed label tokens. Their total mass is 0.96300.9630 and renormalizing over A–D at Ta=1T_a=1 gives the observed vector =(0.2635,0.4344,0.2052,0.0969) θ=(0.2635,0.4344,0.2052,0.0969). Option token Token ID ℓk _k qkq_k θk _k A 362 −1.3715-1.3715 0.25370.2537 0.26350.2635 B 426 −0.8715-0.8715 0.41830.4183 0.43440.4344 C 356 −1.6215-1.6215 0.19760.1976 0.20520.2052 D 423 −2.3715-2.3715 0.09330.0933 0.09690.0969 Sum 0.96300.9630 1.00001.0000 This observation is not a product of probabilities along the reasoning trajectory. It is a single next-token softmax, restricted and renormalized over the known candidate labels, after the sampled reasoning has been placed in the context. Final answer Since argmaxkθk=B _k _k=B, greedy decoding returns B. The released record also stores an independently seeded paired black-box draw o∼Cat()o ( θ), which happened to be A in this trajectory; ASC-D instead observes the entire vector in Table 5. The greedy answer B and the paired draw A are both incorrect relative to the benchmark answer D, illustrating that the grey-box observation exposes uncertainty rather than assuming that a single trajectory is correct. Appendix C Additional Synthetic Experiments The following experiments test two distinct theoretical predictions. The first validates the characteristic-time scaling for a general, non-Dirichlet feedback law, while the second examines how the gain from distribution-valued feedback changes with Dirichlet concentration. Characteristic Time Validation To test the characteristic-time prediction beyond the Dirichlet model, we fix K=10K=10 and =(0.4,0.3,0.03758) π=(0.4,0.3,0.03751_8) and consider the discrete family Z∼Cat(),=(1−ρ)Z+ρ,ρ∈[0,1]. Z ( π), θ=(1-ρ) e_Z+ρ π, ρ∈[0,1]. (23) Every FρF_ρ has mean π and therefore induces the same black-box law Cat()Cat( π). Increasing ρ changes only the information in the probability vector, moving from the vertex law F0F_0 to the degenerate law F1=δF_1= _ π. For ρ∈0,0.2,0.4,0.6,0.8,1ρ∈\0,0.2,0.4,0.6,0.8,1\, we compute Tgb(Fρ)T_ gb(F_ρ) and run 2,000 repetitions of ASC-D for δ∈0.2,0.1,0.05,0.02,0.01,0.002,10−3,2×10−4,10−5,10−6,10−8δ∈\0.2,0.1,0.05,0.02,0.01,0.002,10^-3,2× 10^-4,10^-5,10^-6,10^-8\. We use Λ1.5,16 _1.5,16 and a maximum budget of 20,000. For each ρ, we estimate the empirical characteristic time by fitting [τD]=αρ+βρlog(1/δ)E[τ D]= _ρ+ _ρ (1/δ) over δ≤10−3δ≤ 10^-3. Confidence intervals use 2,000 paired bootstrap samples. Figure 2: Characteristic-time scaling across the feedback family FρF_ρ. Figure 2 compares theoretical and empirical characteristic times (left) and mean stopping time versus log(1/δ) (1/δ) (right). Although all FρF_ρ induce the same black-box law, Tgb(Fρ)T_ gb(F_ρ) decreases from the vertex upper bound toward the degenerate lower bound as ρ increases. The fitted slopes differ from Tgb(Fρ)T_ gb(F_ρ) by at most 5.2%5.2\%, while the finite grid increases the predicted leading constant by at most 1.53%1.53\%. The approximately linear trends in the right panel support the predicted logarithmic dependence on 1/δ1/δ. Effect of Dirichlet Concentration To examine the prediction in Proposition 3.2, we fix K=10K=10, δ=0.05δ=0.05, and =(0.4,0.3,0.03758) π=(0.4,0.3,0.03751_8), and draw t∼Dir(c) θ_t (c π) for c∈0.01,0.1,1,3,10,100,1000c∈\0.01,0.1,1,3,10,100,1000\. For each c, we run 1,000 paired trials of ASC-D using either the full vector t θ_t or the one-hot sample Yt e_Y_t, where Yt|t∼Cat(t)Y_t θ_t ( θ_t). Both versions use the same grid, stopping rule, and maximum budget of 65,536. Figure 3: Mean stopping time versus Dirichlet concentration. As shown in Figure 3, the one-hot stopping time is nearly constant because its marginal feedback law remains Cat()Cat( π), whereas full-vector ASC-D becomes faster as increasing concentration makes trajectories more consistent. The two methods perform similarly near the vertex endpoint; full-vector ASC-D is 4.22×4.22× faster at c=3c=3 and 15.56×15.56× faster at c=1000c=1000, close to the limiting gain of 15.58×15.58×. The concentration-dependent gain and its eventual saturation are consistent with Proposition 3.2. Appendix D Additional Real-World Analyses This section supplements Section 5.2 with uncertainty estimates for the modal-gap scaling analysis and budget-resolved results for the fixed-budget cross-dataset replication. Uncertainty in Modal-Gap Scaling For each of the 90 common questions in Exp. 1, we regress log required budget on log(1/Δ) (1/ ) across Ta∈4,8,16,32T_a∈\4,8,16,32\. Table 6 reports the median within-question slope. Here the confidence intervals use 5,000 paired question-bootstrap resamples. Table 6: Gap-scaling exponents on the 90 common questions. ASC-D ASC-D (one-hot) PPR-1v1 CITE-4 Median β β 0.766 1.969 1.966 1.854 95% CI [0.692,0.810][0.692,0.810] [1.953,2.001][1.953,2.001] [1.949,1.990][1.949,1.990] [1.841,1.861][1.841,1.861] Figure 4: Required trajectory budget versus inverse empirical modal gap on the 90 common questions. Points show geometric means, error bars show 95% paired question-bootstrap confidence intervals, and reference lines have slopes one and two on the log–log scale. The bootstrap intervals separate ASC-D from its matched one-hot ablation and the other hard-label methods. Figure 4 shows the same contrast directly: as the modal gap narrows, the required budget grows much more slowly for ASC-D than for ASC-D (one-hot), PPR-1v1, and CITE-4. These are finite-range empirical slopes and do not imply asymptotic scaling better than Δ−1 ^-1. Cross-Dataset Replication on ARC-Challenge We replicate Exp. 2 on a fixed set of 100 four-choice ARC-Challenge questions using Qwen3-1.7B and Llama-3.2-1B. For each model and question, 128 probability vectors define the empirical population and its modal answer; we retain all 100 questions without screening by modal majority. We run 200 paired replays at 1−δ∈0.95,0.975,0.991-δ∈\0.95,0.975,0.99\ with the same N=128N=128 trajectory budget as in Section 5.2. At each step, ASC-D observes a resampled probability vector, whereas CITE-4 and PPR-1v1 observe the same paired categorical draw. As in Exp. 2, a replay succeeds only if the method stops within the budget and returns the empirical mode. Table 7: Correct-certification rate within N=128N=128 trajectories on 100 ARC-Challenge questions. Each entry aggregates 200 paired replays per question. Model Method 1−δ=0.951-δ=0.95 1−δ=0.9751-δ=0.975 1−δ=0.991-δ=0.99 Llama-3.2-1B ASC-D 74.48% 71.99% 69.06% CITE-4 55.59% 53.40% 51.20% PPR-1v1 54.25% 52.43% 50.30% Qwen3-1.7B ASC-D 97.48% 97.27% 96.94% CITE-4 97.07% 96.72% 96.20% PPR-1v1 96.86% 96.55% 95.97% Table 7 shows that ASC-D achieves the highest correct-certification rate for both models at every confidence level. The gains are larger for Llama-3.2-1B: ASC-D outperforms CITE-4 by 17.8617.86–18.8918.89 percentage points and PPR-1v1 by 18.7618.76–20.2320.23 percentage points. For Qwen3-1.7B, where all methods already achieve high certification rates, the gains are smaller but remain consistent, ranging from 0.410.41 to 0.970.97 percentage points. These results demonstrate that the benefit of distribution-valued feedback transfers from MMLU-Redux to ARC-Challenge and is especially substantial in more challenging certification settings.