acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback

10 views

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.

Primary area:
learning theory
Keywords:
Test-time compute, LLM self-consistency, Adaptive sampling, Sequential hypothesis testing, Mode identification

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6rDPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes grey-box feedback that uses the full probability vector over candidate answers. It formulates adaptive inference as sequential mode identification with distribution-valued observations. The authors characterize the optimal asymptotic stopping rate in this setting. They propose ASC-D, which bets on probability differences between candidate answers and stops sampling when sufficient evidence has accumulated. With an appropriately designed betting grid, the algorithm attains the theoretically optimal characteristic time. The experiments include synthetic distributions, MMLU-Redux, and additional ARC-Challenge results in the appendix. In empirical replay experiments on a shared set of 90 MMLU-Redux questions, ASC-D uses 46.4%–95.6% fewer trajectory observations than PPR-1v1.

Critical strengths
  1. The paper clearly characterizes the informational value of full probability distributions relative to single answer labels.
  2. The stopping rule is closely aligned with the theoretical analysis.
  3. The experiments help distinguish the contributions of feedback information and the stopping rule.
Critical weaknesses
  1. The real-model experiments mainly validate replay performance on empirical distributions, with limited guarantees for the original model distribution.
  2. The conditions for termination guarantees with a finite betting grid need further clarification.
  3. The main results rely on a filtered shared question set, whose representativeness needs further validation.
Questions for authors
  1. Do the current certification results concern the empirical population or the original model’s answer distribution? Please clarify the statistical relationship between the empirical population and the original model distribution. In particular, how uncertain is the reference mode estimate when the modal gap is small? Are there experiments that determine the reference mode using an independent trajectory pool? Such experiments would then use newly generated trajectories to evaluate stopping times and incorrect-certification probabilities. This information will affect my assessment of online sampling savings and certification validity.
  2. How does the practical betting grid ensure termination, and how does this relate to the δ-PAC definition? Please provide the betting grid used in each experiment and explain how it was chosen. Is eventual termination guaranteed at a fixed confidence level when the distribution is unknown and the modal gap is extremely small? If not, how are runs handled when the budget is exhausted? How are the probabilities of incorrect certification and non-certification measured separately? This information will affect my assessment of the theoretical guarantees and the conditions under which the algorithm applies.
  3. Do the main conclusions still hold on the full set of 120 questions? Please report stopping times, correct-certification rates within the budget, and the proportion of uncertified runs on the full question set. Please also explain which selection criteria the 30 excluded questions failed to meet. If some runs reach the budget limit, how are they handled when computing the average number of trajectories? Please clarify how reusing this question set affects comparisons across models. This information will affect my assessment of the reported savings and the representativeness of the results.
1 comment

We thank the reviewer for raising these questions and provide our clarifications and additional results below.

W1/Q1: Empirical populations and reference-mode uncertainty. The certification results in Exps. 1–2 concern the empirical population F^=M−1∑i=1Mδθi\widehat F=M^{-1}\sum_{i=1}^{M}\delta_{\boldsymbol{\theta}_i}, where MM is the number of stored probability vectors. Its mode is computed exactly from π^k=M−1∑i=1Mθi,k\widehat\pi_k=M^{-1}\sum_{i=1}^{M}\theta_{i,k}, so no additional reference pool is needed for evaluation under F^\widehat F. We conduct hundreds of paired replays per question and setting to reduce Monte Carlo error in the performance estimates under F^\widehat F.

The relationship to the original model distribution FF involves sampling uncertainty. Under i.i.d. sampling from FF, Hoeffding's inequality gives max⁡k∣π^k−pk∣≤εM\max_k|\widehat\pi_k-p_k|\leq\varepsilon_M w.p. at least 1−α1-\alpha, where εM=log⁡(2K/α)/(2M)\varepsilon_M=\sqrt{\log(2K/\alpha)/(2M)}. On this event, the empirical and original modes agree whenever the empirical gap exceeds 2εM2\varepsilon_M. Small gaps can leave this agreement unresolved. This does not affect evaluation against the exact empirical mode.

In addition, we added Exp. 3/Table 5 to measure fresh-sampling costs (trajectories, tokens, and runtime). We have not established original-distribution certification-error rates using an independently validated reference mode.

W2/Q2: Practical grids and budgeted certification.

(1) Grids. ASC-D uses Λ2,8\Lambda_{2,8} (15 points) in Table 2 and the Dirichlet-concentration study, Λ1.5,16\Lambda_{1.5,16} (32 points) in the characteristic-time study (Appendix D), and 0,0.01,…,0.99\\{0,0.01,\ldots,0.99\\} (100 points) in all real-model experiments. Geometric grids densify both endpoints. The uniform grid fixes numerical resolution and is shared with matched controls.

(2) Termination. The δ\delta-PAC definition requires almost-sure termination and error at most δ\delta. A fixed finite grid need not ensure termination for arbitrarily small gaps. Our optional Hoeffding backup supplies this guarantee and preserves the applicable asymptotic rates. See Reviewer NaQQ's W2/Q1 and Remark 3.1 and Appendix B, Corollary B.1.

(3) Budgeted outcomes. In fixed-budget certification comparisons, non-crossing runs are uncertified and charged NN; Num. Gen. is the mean min⁡(τ,N)\min(\tau,N). Relative to the exact empirical mode a⋆a^\star, we estimate

p_{\mathrm{nc}}(N)=\mathbb{P}(\tau > N)$$ from fractions of all replays. Correct certification, incorrect certification, and non-certification sum to one, in which $\delta$ controls incorrect certification. W3/Q3 reports full-set results. The accuracy-matched ASC comparison permits a budget-end estimate, which is not a certificate. True-mode error evaluation with fresh trajectories is discussed in W1/Q1. **W3/Q3: Question selection and full-set evaluation.** We first clarify the selection used in *Exp. 1*. Of the original 120 questions, 17 have different ordered top-two answers across $T_a\in\\{4,8,16,32\\}$ in the Qwen3-1.7B analysis. Among the remaining 103, another 13 fail to reach 95% correct recovery for at least one method at a tested temperature within 32,768 trajectories. The retained 90 keep the leading answer and closest competitor fixed while varying the gap, allowing required-budget estimates within the cap. We repeated *Exp. 2* on all 120 questions for all three models at $T_a=1$ and $N=128$. Every run contributes $\min(\tau,N)$ to mean Num. Gen.; uncertified runs are charged $N$. Corr. Cert. and Uncert. are percentages of all runs that correctly certify the empirical mode by $N$ and that do not stop by $N$, respectively. The table gives $95\\%$ results. ASC-D uses fewer trajectories and achieves higher correct-certification rates than both baselines on every model, also at $97.5\\%$ and $99\\%$ confidence. Full results appear in *Appendix E.4, Table 13*. | Model | Method | Num. Gen. | Corr. Cert. | Uncert. | |---|---|---:|---:|---:| | Llama-3.2-1B | ASC-D | **79.75** | **57.21%** | **42.77%** | | Llama-3.2-1B | CITE-4 | 98.48 | 35.87% | 64.10% | | Llama-3.2-1B | PPR-1v1 | 100.05 | 34.41% | 65.58% | | Llama-3.1-8B | ASC-D | **48.62** | **78.67%** | **21.32%** | | Llama-3.1-8B | CITE-4 | 61.46 | 68.52% | 31.46% | | Llama-3.1-8B | PPR-1v1 | 63.40 | 67.22% | 32.77% | | Qwen3-1.7B | ASC-D | **36.68** | **83.49%** | **16.49%** | | Qwen3-1.7B | CITE-4 | 39.88 | 81.64% | 18.35% | | Qwen3-1.7B | PPR-1v1 | 41.56 | 81.00% | 18.98% | *Exp. 1*'s filtering enables controlled gap scaling; *Exp. 2* does not require it. We reused the Qwen-selected 90 questions for consistency with *Exp. 1* and common composition across models. This selection can influence cross-model averages, whereas the unfiltered 120-question evaluation removes that filter.
Reviewer_amyROpenReview ↗
Rating
2
Confidence
3
Informativeness
3(+1)
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies adaptive self-consistency for LLM reasoning, where trajectories are sampled one at a time and sampling stops once the model's majority answer can be identified with a given confidence. Instead of recording only the sampled final answer of each trajectory, the authors propose to record the model's full probability vector over the candidate answers, which is available from the log-probabilities at the answer position. They characterise the asymptotic number of trajectories needed to identify the modal answer under this "grey-box" feedback, show that it is never worse than the answer-only setting, and propose ASC-D, a betting-based stopping rule that attains this rate while controlling the probability of returning a wrong mode. Experiments on synthetic data and on MMLU-Redux with three open-source models show that ASC-D needs fewer trajectories than answer-only baselines.

Critical strengths
  1. The idea is simple and practical. The probability vector over candidate answers is already computed by the model, so using it costs nothing extra, and it is natural to ask how much it can save over counting votes.
  2. The analysis is clean and well motivated. The paper characterises the optimal stopping rate for the grey-box setting, shows that it interpolates between the answer-only rate and a much faster rate depending on how consistent the trajectories are, and gives a procedure that attains it with a valid error guarantee at any stopping time.
  3. The experiments are set up carefully within their scope. All methods are compared on the same trajectories, and the one-hot ablation of ASC-D isolates the effect of the richer feedback from the effect of the stopping rule.
Critical weaknesses
  1. The relation to existing confidence-based self-consistency methods needs to be clarified. Using the model's probabilities instead of hard votes is close in spirit to several prior works: confidence-weighted self-consistency (Taubenfeld et al., 2025; Fu et al., 2026), CITE (Ota et al., 2026), which the paper describes as already considering scalar confidence, and soft self-consistency (Wang et al., 2024), which scores answers by model likelihood and is not cited. The paper positions itself as extending these methods from scalar confidence to the full probability vector, and the main addition appears to be the characterisation of the optimal stopping rate and a procedure that attains it. This may well be a useful contribution, but the paper does not make the difference explicit. It does not state what these methods would achieve in the same sequential setting, or how much of the gain comes from the full vector rather than from confidence weighting as such. The empirical comparison does not settle this either. The confidence-weighted variant appears only in the synthetic study (Table 2), and in the MMLU-Redux experiments (Tables 3 and 4) the baselines are answer-only: CITE-4 is run with one-hot observations rather than its confidence-aware form, and the original adaptive-consistency rule of Aggarwal et al. (2023) is not included.

  2. The empirical evaluation is too small to support the practical claims, and the size of the reported gains needs more explanation. The real-world experiments use a single dataset, MMLU-Redux, with 120 questions, of which 90 are used for the main results, and three models of at most 8B parameters. All results come from offline replays of stored trajectories. There are no other benchmarks, no larger models, and no task beyond four-way multiple choice, even though the method also applies to short-answer tasks with a specified candidate set. The headline reduction of 46.4–95.6% in trajectories comes from Exp. 1, where the stored answer logits are rescaled with temperatures of 4 to 32 to artificially narrow the gap between the top two answers. At the model's natural temperature (Exp. 2, Table 4), the differences are much smaller for the stronger models; for Qwen3-1.7B, for example, ASC-D certifies 90.75% of questions against 89.29% for CITE-4 at the 95% level. Answer accuracy also stays around 72% for all methods in Table 3, so the benefit is in the number of samples rather than in accuracy. It is therefore not clear how much ASC-D would save in a realistic deployment.

Overall, I find the analysis sound and the idea reasonable, but given the unclear distinction from existing confidence-based methods and the limited experimental validation, I think the contribution is not yet sufficient.

Questions for authors
  1. What exactly does this paper add over confidence-weighted self-consistency (Taubenfeld et al., 2025; Fu et al., 2026), CITE with confidence (Ota et al., 2026), and soft self-consistency (Wang et al., 2024)? Is the main contribution the optimal-rate analysis and the stopping rule, or does the full probability vector also give a practical gain over scalar confidence?
  2. In the MMLU-Redux experiments, how does ASC-D compare with confidence-weighted baselines (e.g. the confidence-weighted variant from Table 2, or CITE with confidence) and with the original adaptive-consistency rule of Aggarwal et al. (2023)?
  3. Do the gains hold on other benchmarks (e.g. other multiple-choice datasets or short-answer tasks with a candidate set), on larger models, and with live sampling rather than offline replay?
  4. How large are the savings in trajectories at the model's natural answer temperature, across all three models? This would show how much of the gain in Exp. 1 depends on the temperature rescaling.
3 comments

W1/Q1: Contribution and full-vector feedback. We thank the reviewer for this question. We characterize the optimal asymptotic rate with full answer-probability vectors (Theorem 2.1) and develop ASC-D to attain it with a suitable betting grid and error control (Theorem 3.1).

Compared with confidence-weighted self-consistency (Taubenfeld et al., 2025; Fu et al., 2026), CITE with confidence (Ota et al., 2026), and soft self-consistency (Wang et al., 2024), ASC-D uses probabilities for all candidates for modal certification. Proposition 2.1 proves Tgb≤Tcw≤TbbT_{\mathrm{gb}}\leq T_{\mathrm{cw}}\leq T_{\mathrm{bb}} for the same modal target and error requirement. If Tgb<TcwT_{\mathrm{gb}} < T_{\mathrm{cw}}, no δ\delta-PAC procedure observing (Y,θY)(Y,\theta_Y) can match the full-vector rate asymptotically. Table 1 quantifies the gap. Table 2 holds the modal target, betting rule, grid, and threshold fixed on matched synthetic trajectories, changing only feedback: θt\boldsymbol\theta_t versus θt,YteYt\theta_{t,Y_t}\boldsymbol e_{Y_t}. ASC-D uses 35.8–57.6% fewer trajectories at 95% confidence.

W1/Q2: Confidence-based methods and original ASC. We thank the reviewer for pointing this out. Our comparisons required a common modal target and error guarantee. However, confidence weighting can change the target, while original ASC uses posterior confidence.

For example, with i.i.d. P(A)=0.51\mathbb{P}(A)=0.51 and P(B)=0.49\mathbb{P}(B)=0.49, four initial BB answers make original ASC stop at posterior 1−2−5=0.968751-2^{-5}=0.96875. This non-modal return occurs with probability at least 0.494=0.057648>0.050.49^4=0.057648 > 0.05, so a 0.950.95 posterior threshold does not give uniform 55\\% error control. We therefore added two MMLU-Redux comparisons at Ta=1T_a=1 (Appendix E.2, Tables 10–11).

(1) Confidence-weighted methods. We retain questions whose original and weighted modes agree and follow Exp. 2 at 95% confidence and N=128N=128. The weighted control shares ASC-D's betting rule and grid; W-CITE-4 adapts confidence-aware CITE to four known candidates. ASC-D has the highest correct-certification rate on each model: 57.8157.81\\% on Llama-3.2-1B, versus 47.8247.82\\% for the weighted control and 46.4446.44\\% for W-CITE-4.

(2) Original ASC. We calibrate thresholds by five-fold cross-validation to common model-specific minimum empirical-mode accuracy targets. Budget-end estimates count toward this accuracy, not certification. ASC-D uses 96.5696.56 versus 120.02120.02 trajectories on Llama-3.2-1B and 21.3121.31 versus 23.1623.16 on Llama-3.1-8B, with higher observed mode accuracy. On Qwen, accuracy is similar and original ASC is slightly cheaper (9.879.87 versus 10.9910.99).

W2/Q3: Broader evaluation and fresh sampling. We thank the reviewer for these comments. The paper includes 100 ARC-Challenge questions (Appendix E). For the 90-question selection for gap scaling, see Reviewer 6rDP's W3/Q3. Separately executed online token/latency comparisons appear in Exp. 3/Table 5 and Reviewer NaQQ's W1.

We added fresh-sampling experiments on GSM8K with Qwen3-1.7B and Qwen3-14B, and MATH500 with Mistral-NeMo-12B and Qwen2.5-14B, at Ta=1T_a=1, 95% confidence, and N=128N=128 (Appendix E.3, Table 12). Methods share fresh trajectory streams. On GSM8K, ASC-D uses 6.056.05\\% fewer trajectories than CITE-KK and 9.639.63\\% fewer than PPR-1v1 on Qwen3-1.7B. For Qwen3-14B, the corresponding reductions are 10.9810.98\\% and 13.4613.46\\%. The concentrated answer vectors, especially for the stronger 14B model, leave negligible gains over the matched one-hot control. On MATH500, savings over this control are 12.3012.30\\% for NeMo-12B and 3.693.69\\% for Qwen2.5-14B. Across all four settings, ASC-D uses fewer trajectories than CITE-KK and PPR-1v1, with equal or higher observed answer accuracy. Extra full-vector gains vary with the model, dataset, and vector concentration.

W2/Q4: Natural-temperature results. We thank the reviewer for this question. Appendix E.1, Table 9 reports MMLU-Redux results using the Exp. 2 questions and setup at Ta=1T_a=1, 95% confidence, and N=128N=128. Savings over PPR-1v1 are 11.9611.96\\% on Qwen3-1.7B, 18.4818.48\\% on Llama-3.2-1B, and 23.6423.64\\% on Llama-3.1-8B; the corresponding CITE-4 savings are 7.007.00\\%, 17.1817.18\\%, and 21.0421.04\\%. It also reports the matched one-hot control. We now lead the abstract and introduction with natural-temperature results. The goal is fewer samples while preserving answer quality. The 46.446.4–95.695.6\\% savings remain specific to Exp. 1: it rescales answer logits while keeping reasoning fixed to test modal-gap scaling. Over the tested range, higher TaT_a flattens vectors and narrows the gap, increasing the relative value of full-vector feedback.

Thank you for the detailed response and for answering my questions so thoroughly. I think revising the abstract and adding the new baselines definitely makes the paper stronger. That said, seeing that the benefit of the full vector over one-hot feedback becomes mostly negligible on stronger models at Ta=1T_a=1, I remain slightly hesitant about the overall scope of the contribution. After careful consideration, I will maintain my current score. Thanks for all your effort again!

We really thank the reviewer for the thoughtful review and constructive discussion. We agree that the gains depend on the setting: when a strong LLM answers an easy question and its answer distributions are already highly concentrated on the same answer, full-vector feedback offers little additional information over sampled answers.

However, when substantial answer uncertainty remains, for example with weaker LLMs on challenging questions (a setting we believe is common when cost efficiency is a priority), our simple procedure can use the additional probability information to further improve sampling efficiency and save inference cost compared with standard adaptive self-consistency methods. We see this as the practical value of our contribution, instead of a uniform strict improvement across all LLMs and tasks. We appreciate the opportunity to reflect on and clarify the scope of our contribution, and thank you again for your constructive suggestions.

Reviewer_NaQQOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies adaptive self-consistency when each reasoning trajectory reveals a probability vector over a known answer set. It characterizes the optimal instance-dependent asymptotic sample complexity and proposes ASC-D, a betting-based stopping rule that attains this rate with an appropriately refined grid. Validation includes synthetic experiments and replay-based evaluations using probability vectors collected from MMLU-Redux and ARC-Challenge. The certification target is the model’s modal answer.

Critical strengths
  1. A precise theoretical characterization of richer feedback. The matching asymptotic bounds explain how the benefit depends on variation across trajectory-level probability vectors. The interpolation between categorical feedback and fully consistent probability vectors provides a meaningful contribution beyond an empirical soft-voting heuristic.

  2. A controlled evaluation of the information gain. The matched one-hot ablation holds the stopping rule fixed while changing the feedback. This helps isolate the value of observing the full probability vector and connects the experiments directly to the theoretical question.

Critical weaknesses
  1. The strongest empirical gains have limited external validity. The headline savings primarily come from artificially increased answer temperatures and replay over finite empirical populations. At natural temperature, gains vary substantially across models. These results establish a useful controlled comparison, but provide limited evidence for comparable savings in online inference or total computational cost.

  2. Finite-confidence termination requires clarification. The error guarantee controls incorrect outputs when the procedure stops, whereas the stopping-time analysis requires sufficient grid coverage relative to an unknown instance. A finite grid can contain no bet with positive expected log growth for a small-gap instance. Consequently, reliable termination at a fixed prescribed confidence level is not fully established by the stated asymptotic result.

Questions for authors
  1. Does the proposed procedure terminate almost surely for every unique-mode distribution at each fixed δ\delta? How is this ensured when the finite grid misses all bets with positive expected log growth?

  2. At natural temperature and 95% confidence, ASC-D improves certification over CITE by 19.06 percentage points on Llama-3.2-1B, but only 1.46 points on Qwen3-1.7B. Can differences in the predicted characteristic-time ratio or the distribution of trajectory-level margins explain this discrepancy?

3 comments

W1: Natural-Temperature Results and Online Cost. We thank the reviewer for this helpful feedback. We have added experiments to address these concerns. (i) Natural-temperature results. Using the Exp. 2 setup, we evaluate three models on MMLU-Redux and two on ARC-Challenge (Appendix E.1, Table 9). At Ta=1T_a=1, 1−δ=0.951-\delta=0.95, and N=128N=128, ASC-D reduces mean budget-capped trajectory use by 4.964.96–25.7925.79\\% relative to its matched one-hot version, 11.9611.96–28.7228.72\\% relative to PPR-1v1, and 7.007.00–27.0127.01\\% relative to CITE-4. Gains vary with the extra information supplied by full vectors across models, datasets, and answer temperatures. (ii) Online inference and computational cost. We run Qwen3-1.7B and Llama-3.2-1B on 10 questions per dataset at the same temperature, confidence, and budget. Each method separately generates fresh trajectories until stopping or reaching NN (Exp. 3, Section 4.2). Table 5 reports trajectories, output tokens, and online time. Relative to its matched one-hot version, ASC-D reduces these costs by 6.606.60–20.8520.85\\%, 5.645.64–19.0719.07\\%, and 5.565.56–19.2119.21\\%, respectively. The corresponding reductions are 7.867.86–29.9129.91\\%, 6.726.72–34.3334.33\\%, and 6.666.66–33.7333.73\\% relative to PPR-1v1, and 7.187.18–23.1523.15\\%, 6.176.17–28.1728.17\\%, and 6.436.43–26.8026.80\\% relative to CITE-4.

W2/Q1: Termination Guarantees and Grid Conditions. We thank the reviewer for distinguishing error control from termination. Our bound PF(τ<∞,a^τ≠a1)≤δ\mathbb{P}_F(\tau < \infty,\widehat a_\tau\neq a_1)\leq\delta controls error, but the original finite grid need not ensure almost-sure termination for every unique-mode distribution at fixed δ\delta. We have added an optional Hoeffding backup in Remark 3.1, with its construction and guarantees in Appendix B, Corollary B.1.

(1) A Hoeffding-based backup stopping rule. Fix η∈(0,1)\eta\in(0,1) independently of δ\delta and split the error budget as δB=(1−η)δ\delta_{\mathrm B}=(1-\eta)\delta and δH=ηδ\delta_{\mathrm H}=\eta\delta. Run Algorithm 1 at level δB\delta_{\mathrm B} and also stop when

\bigl(\widehat p_{n,\widehat k_n}-\widehat p_{n,j}\bigr) > b_n, \qquad b_n= \sqrt{\frac{2}{n} \log\left(\frac{(K-1)n(n+1)}{\delta_{\mathrm H}}\right)}$$ where $\widehat p_{n,k} = n^{-1} \sum_{i=1}^n \theta_{i,k}$ and $\widehat k_n = \arg\max_k \widehat p_{n,k}$. Thus the extended procedure will always return the current leader when either rule triggers. Let $\tau_{\mathrm{new}}$ be the first crossing of either rule, returning the current leader. By the strong law, the leader is eventually $a_1$ and its empirical gaps converge to $p_1-p_j > 0$. Since $b_n\to0$, the backup eventually triggers and $\mathbb{P}_F(\tau_{\mathrm{new}} < \infty)=1$. An incorrect output requires either a betting error, bounded by $\delta_{\mathrm B}$, or a wrong Hoeffding crossing. Hoeffding's inequality and a union bound give $$\mathbb{P}_F(\tau_{\mathrm{new}} < \infty,\widehat a_{\tau_{\mathrm{new}}}\neq a_1) \leq\delta_{\mathrm B} +\sum_{k\neq1}\sum_{n=1}^{\infty} \frac{\delta_{\mathrm H}}{(K-1)n(n+1)} =\delta_{\mathrm B}+\delta_{\mathrm H}=\delta.$$ Since $\tau_{\mathrm{new}}\leq\tau_{\mathrm B}$ and $\log(1/\delta_{\mathrm B})\sim\log(1/\delta)$, *Theorem 3.1*'s asymptotic bounds remain valid under its grid conditions, including optimality with its refining grid. For example, $\delta_{\mathrm H}=10^{-4}\delta$ leaves the betting level close to $\delta$. **(2) Sufficient condition for the original grid.** Recall that $\Delta=\min_{j\neq1}(p_1-p_j)$. Expected log-growth increases whenever $\lambda < p_1-p_j$, so $\lambda_j^\star\geq p_1-p_j\geq\Delta$. Thus $\Delta\geq r^{-m}$ implies $r^{-m}\leq\min_{j\neq1}\lambda_j^\star$, satisfying *Theorem 3.1(i)* and ensuring finite expected stopping time for the original geometric-grid procedure. **Q2: Model Differences and Full-Vector Gains.** We thank the reviewer for raising this question. The discrepancy is consistent with Qwen's more concentrated answer probabilities. In *Exp. 2*, $87.3\\%$ of Qwen's trajectory-level vectors assign at least $0.99$ probability to one answer, versus $8.6\\%$ for Llama-3.2-1B. These nearly one-hot vectors add little information beyond the sampled answer. The predicted characteristic-time ratio supports this explanation. Using the same empirical populations as in *Exp. 2*, the median $T_{\mathrm{bb}}/T_{\mathrm{gb}}$ is $2.10$ for Llama-3.2-1B but only $1.03$ for Qwen3-1.7B. This ratio measures how many trajectories sampled-answer feedback requires relative to full-vector feedback asymptotically.

Thanks for adding the proofs and experiments. I'll raise my score to 3.

Thank you for your careful review and for reconsidering your assessment. We appreciate your constructive feedback, which helped us strengthen the proofs and experiments.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Contributions and Revisions

We thank all reviewers for the discussions, which helped us strengthen the guarantees, broaden the evaluation, and clarify the contribution. Here we summarize the core contributions of this work and the main revisions after the discussion.

Core contributions

We characterize the optimal asymptotic sample complexity of identifying an LLM’s modal answer from full answer-probability vectors and propose ASC-D, a simple betting procedure that attains this rate with a suitably refined grid. The analysis quantifies the information gained over sampled answers and scalar-confidence feedback, while matched ablations isolate the benefit of the full vector. The theory also connects grey-box self-consistency to Best-of-N. When trajectories consistently report the same probability vector and the modal answer is correct, our method matches the order of gap dependence in the worst-case sample complexity of Best-of-N with an ideal verifier, using only the LLM’s own answer probabilities.

Main revisions

1. Termination guarantees (Reviewers NaQQ, 6rDP). We clarify that error control alone does not ensure termination for an arbitrary finite grid. We add an optional Hoeffding backup that guarantees almost-sure termination and preserves error control and the applicable asymptotic rates (Remark 3.1; Appendix B).

2. Confidence-based baselines (Reviewer amyR). The original main text already included theoretical and controlled experimental comparisons between full-vector and scalar-confidence feedback. In the revision, we make these results more prominent and expand the empirical comparisons to include confidence-weighted methods, confidence-aware CITE, and original ASC (Appendix E.2).

3. Broader and more practical evaluation (Reviewers NaQQ, amyR). We expanded the evaluation to include fresh online sampling, token and runtime measurements, and additional benchmarks, GSM8K and MATH500, with LLMs up to 14B parameters. We also revised the abstract to emphasize results at the models’ natural answer temperature (Section 4.2, Table 5; Appendices E.1 and E.3).

4. Selection and evaluation scope (Reviewer 6rDP). We explain the question selection and add results on all 120 questions across three LLMs. ASC-D continues to use fewer trajectories and achieve higher correct-certification rates than CITE-4 and PPR-1v1 on each LLM (Appendix E.4, Table 13).

We believe the added proofs, comparisons, and experiments have addressed the main concerns about the theoretical guarantees and empirical evaluation. The remaining concern, emphasized by Reviewer amyR, is the practical scope of the gains: full-vector feedback offers little additional benefit when answer vectors are already nearly one-hot. When substantial uncertainty remains and the vectors contain useful information beyond sampled answers, our simple procedure can improve sampling efficiency and reduce inference costs. We therefore see the contribution as explaining when richer feedback helps and providing a method that exploits it, rather than claiming uniform improvement across all LLMs and tasks.

We sincerely thank the reviewers again for their constructive suggestions, which helped us improve the paper and clarify its contributions and limitations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.