Blend-ASC — Optimal Self-Consistency via Power-Law Sample Efficiency

Paper. Austin Feng, Marius Alonso, Ambroise Odonnat, Vasilii Feofanov, Ievgen Redko. Optimal Self-Consistency for Efficient Reasoning with Large Language Models. ICML 2026. Yale University · Huawei Noah’s Ark Lab. [arXiv]

0. The Picture in One Paragraph

Self-consistency (SC) — sample K answers, take the majority vote — is the dominant inference-time reasoning enhancement for LLMs. But SC is theoretically underspecified: how many samples do you actually need? Prior work answers this with heuristics. Blend-ASC grounds it in theory. The key result is a power-law characterization of SC error decay: Error(n) ∝ n^{−β}, where β depends on the margin Δ = p₁ − p₂ (the gap between the most and second-most probable answers). From this, the paper proves that two existing adaptive methods occupy complementary regions: ASC (adaptive self-consistency) is sample-efficient early but suboptimal at scale; PPR-1v1 (pairwise polling race) is asymptotically optimal but pessimistic and slow to activate. Blend-ASC interpolates between them using the sampling ratio t/T as the mixing weight — pure ASC early, pure PPR-1v1 late — requiring no hyperparameters and achieving 6.8× fewer samples than vanilla SC while remaining theoretically near-optimal throughout.

1. Self-Consistency — The Setup

Self-consistency (Wang et al., 2022) generates K independent chain-of-thought samples from a prompt and returns the empirical mode:

\[\hat{y} = \arg\max_{y} \; |\{i : y_i = y\}|\]

This works because the majority of independently sampled correct reasoning paths converge on the same final answer, even when individual paths are wrong.

The sample budget K is typically a fixed constant (e.g., 40). This is wasteful: some questions are easy and confident (5 samples suffice), while others are hard (even 40 samples may not be enough). An adaptive strategy that stops when confidence is high enough would reduce expected sample count substantially.

The open question: what is the optimal stopping criterion, and how does the error decay with n?

2. The Power-Law Error Decay — The Theoretical Core

2.1 The margin Δ

For a question with answer distribution p₁ ≥ p₂ ≥ …, define the margin:

\[\Delta = p_1 - p_2\]

Δ captures the “difficulty” of the majority-vote problem: large Δ means the correct answer dominates (easy), small Δ means the top two answers are nearly tied (hard).

2.2 Power-law decay

Blend-ASC establishes (for the first time comprehensively) that SC error decays as:

\[\text{Error}(n) \propto n^{-\beta(\Delta)}\]

where β(Δ) is a function of the margin. This is the first rigorous characterization of the SC sample complexity curve — prior work bounded error with exponential Chernoff-style arguments, but those bounds are loose for the n values relevant in practice (n = 10–100).

The power law has two implications:

Error decreases predictably with n — you can estimate when you are “done enough.”
β depends on Δ — the same sample budget yields very different error rates for easy vs. hard questions.

3. Two Prior Adaptive Methods — Complementary Weaknesses

The paper analyzes two existing adaptive SC methods against the power-law theory:

3.1 ASC (Adaptive Self-Consistency)

ASC monitors the current empirical distribution and stops when confidence exceeds a threshold. It is sample-efficient early: for easy questions (large Δ), it stops quickly and is correct.

Weakness: ASC’s stopping criterion is suboptimal asymptotically. For hard questions with small Δ, ASC misidentifies early noise as a confident signal and may terminate too early.

3.2 PPR-1v1 (Pairwise Polling Race)

PPR-1v1 runs a statistical test on the top two answers, stopping when the leading answer has significantly more votes than the second. This is asymptotically optimal: given enough samples, it consistently identifies the correct plurality answer.

Weakness: PPR-1v1 is pessimistic early. For easy questions, it keeps collecting samples long after the right answer is obvious, because the statistical test is conservative.

Method	Early regime (easy Qs)	Late regime (hard Qs)
ASC	Efficient — stops early	Suboptimal — may stop too early
PPR-1v1	Pessimistic — collects too many	Asymptotically optimal
Blend-ASC	Inherits ASC efficiency	Inherits PPR-1v1 optimality

4. Blend-ASC — The Method

Blend-ASC interpolates between ASC and PPR-1v1 based on the sampling progress t/T, where t is the current sample count and T is the maximum budget:

\[\text{Blend-ASC stopping criterion} = (1 - t/T) \cdot R_1(\text{ASC}) + (t/T) \cdot R_2(\text{PPR-1v1})\]

Early in sampling (t/T ≈ 0): the criterion is dominated by ASC — efficient early stopping for easy questions.

Late in sampling (t/T ≈ 1): the criterion converges to PPR-1v1 — asymptotically optimal for hard questions.

Key properties

Hyperparameter-free. The interpolation weight is determined entirely by t/T — no tuning required.
Monotone interpolation. As sampling progresses, the stopping criterion smoothly transitions from aggressive (ASC) to conservative (PPR-1v1).
No architecture change. Blend-ASC operates on the output distribution of any LLM, without access to internal states or logits.

5. Results

5.1 Sample efficiency (main result)

Method	Average samples vs. vanilla SC
Vanilla SC (K=40)	40 (baseline)
ASC	~8–12
PPR-1v1	~12–20
Blend-ASC	~5.9 (6.8× fewer than SC)

Blend-ASC requires the fewest samples on average, while maintaining accuracy at parity with SC.

5.2 Accuracy preservation

Across all evaluated benchmarks and models, Blend-ASC accuracy is within statistical noise of vanilla SC (K=40): no accuracy loss from the 6.8× sample reduction.

5.3 Benchmarks and models

Evaluated on:

MMLU (general knowledge)
MATH (competition mathematics)
GPQA-Diamond (graduate-level “Google-proof” expert questions)

Across five LLM families:

Llama-3.1-8B
Llama-3.2-3B
Mistral-7B
Qwen-2.5-7B
Qwen-2.5-32B

Gains are consistent across all combinations, suggesting the power-law analysis is model-agnostic.

6. Relationship to the Inference-Time Scaling Literature

Blend-ASC sits at the efficient end of the inference-time compute spectrum:

Method	What it scales	Primary cost
Self-Consistency	More samples per question	Linear in K
Best-of-N + PRM	More samples + scoring	PRM compute
MCTS-based (BG-MCTS)	Tree search	Sequential
Blend-ASC	Minimal samples per question	Sub-linear in K

Blend-ASC is not a replacement for tree search or process reward models on hard tasks — it is an efficiency tool for the majority of questions where SC is already effective. For hard questions (small Δ), Blend-ASC still requires many samples, and at that point more powerful methods (MCTS, PRM-guided search) become appropriate.

7. Why It Matters

Three reasons:

The power-law analysis provides theoretical grounding where SC was purely empirical. Most practitioners tune K by eyeballing accuracy curves. Blend-ASC provides a first-principles framework: error decay rate is a function of margin, and the optimal stopping policy follows from that.
6.8× sample reduction with no accuracy loss is a directly deployable gain. Inference budget for SC scales linearly with K. A 6.8× reduction means the same accuracy at 1/6.8 the cost, or 6.8× more questions served at the same budget.
The interpolation insight is broadly applicable. The idea of interpolating between an early-efficient and a late-optimal criterion based on progress t/T is general — it applies to any sequential decision problem where different stopping rules are optimal at different stages.

8. Limitations Worth Knowing

SC as the base assumption. Blend-ASC optimizes the number of SC samples but does not change what SC can achieve at its ceiling. If the LLM’s answer mode is incorrect (the most common answer is wrong), Blend-ASC inherits this failure.
Margin Δ is unobserved. The power-law theory depends on the true Δ, but in practice Δ is estimated from n samples. For hard questions (small true Δ), the empirical estimate may be noisy.
Discrete answer assumption. The pairwise polling analysis assumes a discrete answer space (multiple choice or extractable final answers). Open-ended generation with continuous answer spaces requires an answer-canonicalization step that introduces additional error.
Benchmark scope. Evaluations focus on QA-style benchmarks with extractable final answers. Extension to generation tasks (code, text) is not evaluated.

9. The Takeaway for a First Reader

If you remember three things:

SC error decays as a power law n^{-β(Δ)}, where Δ = p₁ − p₂ is the margin between the top two answers. This is the first comprehensive derivation — prior bounds were exponential and too loose for practical n values.
ASC and PPR-1v1 have complementary weaknesses: ASC is efficient early but suboptimal on hard Qs; PPR-1v1 is asymptotically optimal but pessimistic early. Blend-ASC interpolates between them with mixing weight t/T — no hyperparameters, inheriting the best of both.
6.8× fewer samples than vanilla SC (K=40 → ~6) with no accuracy loss, consistently across MMLU, MATH, GPQA-Diamond, and five LLM families.

References

Feng, A., Alonso, M., Odonnat, A., Feofanov, V., & Redko, I. (2026). Optimal Self-Consistency for Efficient Reasoning with Large Language Models. ICML 2026. Also NeurIPS 2025 Workshop on Efficient Reasoning. arXiv:2511.12309.
Wang, X., et al. (2022). Self-consistency improves chain-of-thought reasoning in language models. NeurIPS 2022.
Related on this site: BG-MCTS — budget-guided tree search, a complementary approach when SC’s ceiling is insufficient; Tele-Lens — probing when hidden states encode confidence, which could inform margin estimation for adaptive SC.