Source-linked AI summary
Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback
Jingkai Huang, Yunfan Zhang, Will Ma, Weihua Zhou, Zhengyuan Zhou
TL;DR
Self-consistency discards each trajectory’s available answer-probability vector and retains only its sampled label, motivating whether richer feedback can reduce the trajectories needed for reliable inference. The paper formulates sequential mode identification with distribution-valued observations and proposes ASC-D, which bets on pairwise probability differences and stops when evidence supports the leading answer over every alternative. ASC-D outperforms answer-only baselines as the modal gap narrows; under maximum budget N = 128, it achieves the highest correct-certification rate at every tested confidence level across three models.
Problem
Self-consistency discards each trajectory’s available answer-probability vector and retains only its sampled label, motivating whether richer feedback can reduce the trajectories needed for reliable inference.
Source: §1 · p. 1Method
The paper formulates sequential mode identification with distribution-valued observations and proposes ASC-D, which bets on pairwise probability differences and stops when evidence supports the leading answer over every alternative.
Source: §3.2 · p. 4, §4.1 · p. 8Results
ASC-D outperforms answer-only baselines as the modal gap narrows; under maximum budget N = 128, it achieves the highest correct-certification rate at every tested confidence level across three models.
Source: §1 · p. 3Takeaways & Limitations
The analysis shows that full answer-probability feedback can reduce the trajectories needed to identify the LLM’s most consistent answer, and ASC-D attains the optimal asymptotic rate with a suitable betting grid.
Source: §6 · p. 12The method identifies the model’s most consistent answer, not necessarily the correct one, and requires log-probabilities over a finite candidate set; experiments cover small open-source models and multiple-choice benchmarks.
Source: §6 · p. 12
Abstract
from arXiv · showhide
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.
1 Introduction
Self-consistency usually keeps only sampled answer labels, although each trajectory’s answer-probability vector is available. The paper develops adaptive self-consistency using those vectors, characterizes its efficiency, and evaluates it on MMLU-Redux.
1 Introduction
- Grey-box feedback reveals each trajectory’s full answer-probability vector, rather than only its sampled answer, while preserving the same answer frequencies and modal answer.The paper frames this as a practical middle ground between black-box label observations and infeasible enumeration of all reasoning trajectories.Source: §1 · pp. 1–2
- The paper characterizes the asymptotic benefit of distribution-valued feedback and proposes ASC-D, which bets on pairwise probability differences and stops when evidence supports the leading answer over every alternative.Its contributions also include synthetic experiments and a fixed-budget evaluation on MMLU-Redux.Source: §1 · p. 2
- 46.4–95.6% fewer trajectories than answer-only adaptive self-consistency baselines; ASC-D also has the highest fixed-budget correct-certification rate across three tested models.The certification comparison holds at every tested confidence level under a maximum budget of N = 128.Source: §1 · pp. 2–3
2 Related Literature
Prior work studies adaptive self-consistency, confidence-weighted reasoning, and sequential mode identification. This paper extends that line by using full answer-probability vectors and characterizing their optimal stopping rate.
2 Related Literature
- Prior adaptive methods stop on answer stability, allocate samples by estimated difficulty, assess reasoning paths, or use scalar confidence; Bayesian stopping can use answer-frequency priors but observes only labels.The paper says its method instead uses each trajectory’s full probability vector and does not require prior information about answer frequencies.Source: §2 · p. 3
- Classical sequential testing and mode-identification work includes label-based stopping and anytime-valid LLM procedures; this work extends the setting to probability-vector observations and characterizes their optimal stopping rate.The cited LLM procedures include majority certification and unique-mode certification.Source: §2 · p. 3
3 Problem Setup
The paper models each reasoning trajectory as yielding a distribution over a known set of candidate answers, then studies how many sequential observations are needed to identify its modal answer. Its lower bounds compare full-distribution feedback with label-only and confidence feedback, including under a Dirichlet model of trajectory heterogeneity.
3.1 Distribution-Valued Feedback
- Grey-box feedback observes each trajectory’s full answer-probability vector, whereas black-box self-consistency observes only the sampled answer; both target the mode of the same mean answer-frequency vector.Trajectory-specific vectors are modeled as i.i.d. draws from an unknown distribution over the probability simplex.Source: §3.1 · p. 4
3.2 Sequential Mode Identification
- Sequential mode identification samples trajectories until it can recommend the modal answer with error probability at most δ, counting each trajectory as one LLM call.The mode is the answer that an infinite-sample majority vote would return.Source: §3.2 · p. 4
3.3 Asymptotic Lower Bounds
- The grey-box characteristic time is bounded above by the black-box time, and its lower bound is determined by the hardest competitor to the modal answer.The paper characterizes that competitor’s cost through the minimum KL divergence needed to make it at least as likely as the mode.Source: §3.3 · p. 5, §3.2 · p. 5
- With a small modal gap, the black-box rate is Θ(∆^-2), while maximally consistent grey-box trajectories attain Θ(∆^-1); when every trajectory commits to one answer, grey-box feedback has no additional information.The fully consistent endpoint has characteristic time 1 / log(1 + ∆), while the vertex-law endpoint matches the black-box time.Source: §3.3 · pp. 5–6
- At the degenerate endpoint, grey-box self-consistency has the same Θ(∆^-1) gap dependence as worst-case ideal best-of-N under the assumption that the modal answer is correct.The comparison is with best-of-N’s Θ(∆^-1) rate, versus self-consistency’s Θ(∆^-2) rate.Source: §3.3 · p. 6
- Confidence feedback has an intermediate characteristic time, with Tgb(F) ≤ Tcw(F) ≤ Tbb(F); full probability-vector feedback can therefore improve further over answer labels plus confidence.The ordering applies when the feedback models identify the same modal answer.Source: §3.3 · p. 6
- Under a Dirichlet model with fixed answer frequencies, concentration c controls agreement across trajectories, and observing the probability vector reduces variance by a factor of c + 1 relative to the sampled-answer indicator.As c grows, the model approaches the fully consistent endpoint; as c shrinks, it approaches the vertex-law endpoint.Source: §3.3 · pp. 6–7
- For small modal gaps under the Dirichlet assumption, the grey-box characteristic time has a simple approximation, while at fixed gap it approaches 1 / log(1 + ∆) as c grows.The paper reports that the approximation Tbb(F)/(c + 1) closely matches Tgb(F) for small c, but tends to zero as c increases while Tgb(F) approaches its limit.Source: §3.3 · p. 7
4 The ASC-D Algorithm
ASC-D uses pairwise betting on distribution-valued observations to identify the modal answer and stop when its leader clears every challenger. It provides a finite-confidence error guarantee and attains the optimal asymptotic characteristic time.
4.1 From the Rate to the Algorithm
- Pairwise betting uses wealth above 1/α as time-uniform evidence that one answer beats another, with expected log-wealth growth at the optimal betting fraction.For a bet fraction λ, the per-trajectory payoff is 1 + λ(θi,k − θi,j).Source: §4.1 · pp. 7–8
- A finite grid averages wealth across candidate betting fractions, preserving validity; its geometric design uses a coarse middle and dense ends to approximate the unknown optimum.The optimal fraction depends on the unknown distribution F.Source: §4.1 · p. 8, §4.2 · p. 8
- Because the modal answer is unknown, ASC-D evaluates every ordered answer pair and stops when the cumulative-mass leader’s averaged wealth exceeds (K − 1)/δ against every challenger.The leader is the answer with the largest cumulative mass across observed distributions.Source: §4.1 · p. 8
- Full answer distributions let ASC-D use probabilities assigned to unsampled answers; using only sampled labels reduces it to the known-K adaptation of CITE.Source: §4.1 · p. 8
4.2 Performance Guarantees
- As δ→0, ASC-D’s expected stopping time divided by log(1/δ) equals Tgb(F); for every δ∈(0,1), its probability of finite-time error is at most δ.The asymptotic guarantee holds for distributions with a unique mode.Source: §4.2 · p. 9
5 Experiments
The experiments compare distribution-valued feedback with reduced-feedback methods in synthetic and real-world settings. ASC-D uses fewer trajectories in the reported comparisons and leads in correct certification within a fixed budget.
5 Experiments
- Experiments compare stopping time at fixed confidence and correct certification under a fixed budget, using synthetic probability vectors and vectors from live LLM calls.The real-world trajectory-generation comparison rescaled stored Qwen3-1.7B answer logits across four temperatures; the fixed-budget study evaluated three open-source models at the natural answer temperature.Source: §5 · p. 9, §5.1 · pp. 9–10, §5.2 · pp. 10–11
5.1 Controlled Comparison of Feedback Types
- At 95% confidence, ASC-D used 35.8–57.6% fewer trajectories than the confidence-weighted method and 71.3–80.1% fewer than CITE-4, with larger savings at smaller gaps.Source: Table 2 · p. 10, §5.1 · p. 10
5.2 Real-World Experiments
- Median log-budget slopes were 0.766 for ASC-D versus 1.969, 1.966, and 1.854 for its one-hot ablation, PPR-1v1, and CITE-4; this finite-range result is not asymptotic.Source: §5.2 · pp. 10–11
- 41.0–95.2% fewer trajectories than its matched one-hot ablation, 46.4–95.6% fewer than PPR-1v1, and 57.6–95.5% fewer than CITE-4 as the geometric-mean modal gap narrowed from 0.610 to 0.098.The comparison covers 90 MMLU-Redux questions with the same ordered top-two answers across temperatures; savings came without loss in answer accuracy.Source: §5.2 · p. 10, Table 3 · p. 11
- ASC-D achieved the highest correct-certification rate for every model and confidence level within N=128 trajectories, exceeding CITE-4 and PPR-1v1 by up to 19.06 and 20.46 percentage points on Llama-3.2-1B.Source: Table 4 · p. 11, §5.2 · p. 11
6 Conclusion and Limitations
The paper concludes that per-trajectory answer probabilities can reduce the trajectories needed to identify the LLM’s most consistent answer, and that ASC-D attains the optimal asymptotic rate. Its scope is limited by the need for finite candidate answers and by experiments on small open-source models and multiple-choice benchmarks.
Conclusion
- Observing candidate-answer probabilities can reduce the trajectories needed to identify the LLM’s most consistent answer.The analysis characterizes the optimal asymptotic rate, and ASC-D attains it with a suitable betting grid.Source: §6 · p. 12
Limitations
- ASC-D identifies the LLM’s most consistent answer, which may differ from the correct answer when the model is confidently wrong.This limitation is inherited from self-consistency.Source: §6 · p. 12
- The method requires log-probabilities over a finite candidate set, so it does not directly cover open-ended generation with an unbounded answer space.Source: §6 · p. 12
- Experiments cover small open-source models and multiple-choice benchmarks; larger models and open-ended reasoning tasks remain for future evaluation.Source: §6 · p. 12
A Proof of Main Results
The proofs characterize the information needed to distinguish the modal answer from alternatives, compare grey-box and black-box rates, and establish that ASC-D can attain the grey-box asymptotic rate. They also derive the gap dependence under Dirichlet heterogeneity and justify the algorithm’s betting-grid design.
KL reduction
- The alternative-distribution KL minimization reduces to a one-dimensional problem over each challenger’s margin, with the minimum equal to Kinf for that margin distribution.The proof constructs alternatives by changing the margin law while keeping the conditional distribution unchanged, preserving the KL divergence.Source: A Proof of Main Results · p. 16
Characteristic-time bounds
- For the grey-box bound, vertex law F0 can achieve the lower bound, while degenerate law F = δπ can achieve the upper bound; under δπ, every margin is the positive constant p1−pj.Source: A Proof of Main Results · pp. 16–17
Asymptotic lower bounds
- The grey-box characteristic time is no worse than the black-box time because observing the full vector retains information that is lost when reducing it to a sampled answer.The proof uses data processing to compare the two observation models and notes that the grey-box lower bound is achievable by a suitable algorithm.Source: A Proof of Main Results · p. 17
Dirichlet heterogeneity
- Under Dirichlet heterogeneity, the closest challenger is the runner-up as ∆ shrinks, and its grey-box growth rate is quadratic in ∆.The proof combines the expansion for G2 with the black-box expansion to characterize the small-gap regime.Source: A Proof of Main Results · p. 18
ASC-D guarantee and grid
- Geometric grid points near 0 and 1 cover small optimal betting fractions and highly consistent trajectories, while a coarser middle grid retains a fraction of optimal growth.The finite-grid characteristic time is bounded by a factor r of the grey-box time; the proof’s confidence-dependent grid yields the matching asymptotic rate.Source: A Proof of Main Results · pp. 19, 21
B A Real-World Grey-Box Observation Example
The example shows how a sampled reasoning trajectory yields a grey-box observation: a next-token distribution over the allowed answer labels. Its modal answer and a paired black-box draw can both be wrong, while the vector exposes uncertainty rather than presuming correctness.
Observed probability vector
- The four-label vector is (0.2635, 0.4344, 0.2052, 0.0969), obtained by renormalizing raw option-token probabilities totaling 0.9630.Source: Table 5 · p. 23
Observation construction
- The observed vector is a single next-token softmax over the allowed answer labels, renormalized after the reasoning trajectory is placed in context.The example identifies the final-answer prefix and the four allowed continuation tokens at that position.Source: B A Real-World Grey-Box Observation… · p. 23
Example outcome
- The modal answer B and paired black-box draw A are both wrong against benchmark answer D, illustrating that the vector exposes uncertainty rather than assuming a trajectory is correct.Source: B A Real-World Grey-Box Observation… · p. 23
C Additional Synthetic Experiments
The synthetic experiments test characteristic-time predictions across a feedback family with a shared black-box law and measure how Dirichlet concentration changes the gain from full-vector feedback. The empirical trends align with the predicted scaling and concentration-dependent advantage.
Characteristic Time Validation
- All Fρ share the same black-box law, while increasing ρ changes the probability-vector information from the vertex law toward the degenerate law.The experiment uses 2,000 ASC-D repetitions per feedback setting and fits stopping time against log(1/δ).Source: C Additional Synthetic Experiments · p. 24
- Across Fρ, fitted slopes differ from theoretical characteristic times by at most 5.2%, and the finite grid raises the predicted leading constant by at most 1.53%.The mean stopping-time trends are approximately linear in log(1/δ).Source: Figure 2 · p. 24, C Additional Synthetic Experiments · p. 24
Effect of Dirichlet Concentration
- At c = 3 and c = 1000, full-vector ASC-D is respectively 4.22× and 15.56× faster than one-hot ASC-D, approaching the limiting gain of 15.58×.The one-hot stopping time is nearly constant, while full-vector stopping becomes faster as concentration increases.Source: Figure 3 · p. 25, C Additional Synthetic Experiments · p. 25
D Additional Real-World Analyses
Additional analyses test modal-gap scaling with uncertainty estimates and replicate fixed-budget certification results on ARC-Challenge. ASC-D retains the strongest certification performance across both tested models, while its budget grows more slowly as the modal gap narrows in the finite-range scaling analysis.
Uncertainty in Modal-Gap Scaling
- The scaling analysis regresses log required budget on log(1/∆) across Ta ∈{4, 8, 16, 32} for 90 common questions.Table 6 reports median within-question slopes, with confidence intervals from 5,000 paired question-bootstrap resamples.Source: D Additional Real-World Analyses · p. 26, Table 6 · p. 26
- As the modal gap narrows, required budget grows much more slowly for ASC-D than for ASC-D (one-hot), PPR-1v1, and CITE-4, but these are finite-range empirical slopes.Figure 4 plots required trajectory budget against inverse empirical modal gap, with reference slopes one and two.Source: D Additional Real-World Analyses · p. 26, Figure 4 · p. 26
Cross-Dataset Replication on ARC-Challenge
- On ARC-Challenge, ASC-D had the highest correct-certification rates for both models; on Llama-3.2-1B, gains were 17.86–18.89 percentage points over CITE-4 and 18.76–20.23 percentage points over PPR-1v1.The comparison used 100 questions and 200 paired replays per question within a 128-trajectory budget.Source: D Additional Real-World Analyses · pp. 26–27, Table 7 · p. 27