Abstract
Self-consistency (SC) has been a widely used decoding strategy for chain-of-thought reasoning. Despite bringing significant performance improvements across a variety of multi-step reasoning tasks, it is a high-cost method that requires multiple sampling with the preset size. In this paper, we propose a simple and scalable sampling process, Early-Stopping Self-Consistency (ESC), to greatly reduce the cost of SC without sacrificing performance. On this basis, one control scheme for ESC is further derivated to dynamically choose the performance-cost balance for different tasks and models. To demonstrate ESC's effectiveness, we conducted extensive experiments on three popular categories of reasoning tasks: arithmetic, commonsense and symbolic reasoning over language models with varying scales. The empirical results show that ESC reduces the average number of sampling of chain-of-thought reasoning by a significant margin on six benchmarks, including MATH (-33.8%), GSM8K (-80.1%), StrategyQA (-76.8%), CommonsenseQA (-78.5%), Coin Flip (-84.2%) and Last Letters (-67.4%), while attaining comparable performances.
Introduction
Self-consistency (SC) has become the gold standard for boosting the reasoning capabilities of Large Language Models (LLMs). By sampling multiple reasoning paths and taking a majority vote, SC significantly outperforms simple "greedy" decoding. However, there is a catch: it is incredibly expensive. Standard SC treats every problem with the same level of effort, generating a fixed number of outputs (e.g., 40 or 64) regardless of the problem's difficulty. Whether a question is a simple addition or a complex calculus problem, the model generates the same number of samples, leading to massive computational waste on easier queries where the model might have reached the correct consensus after just a few samples.
In this work, we propose Early-Stopping Self-Consistency (ESC)—a simple, elegant way to get the benefits of self-consistency at a fraction of the cost. ESC is a plug-and-play decoding strategy that reduces the computational cost of self-consistency by stopping the sampling process as soon as a high-confidence consensus is reached.
Methodology: The Sampling Window
The core idea of ESC is the Sampling Window. Instead of generating a large fixed number of samples at once, ESC generates them in small sequential batches (windows) of size $w$.
- The Stopping Criterion: If all generated answers within a single window are identical (meaning the entropy of the distribution in that window is zero), the system stops and returns that answer.
- Theoretical Backing: The method uses a one-proportion z-test to prove that if a model produces the same answer $w$ times in a row, the probability that this answer is not the eventual majority winner of a much larger sample set is statistically negligible.
- Control Scheme: We introduce a secondary algorithm that uses a small initial "probe" of the dataset to dynamically determine the optimal window size ($w$) and maximum sample limit ($L$) for a specific model and task, balancing the user's budget against their accuracy requirements.
Experimental Setup
We evaluated ESC across three categories of reasoning using GPT-4, GPT-3.5-Turbo, and Llama-2 7b:
- Arithmetic: MATH and GSM8K.
- Commonsense Reasoning: StrategyQA and CommonsenseQA (CSQA).
- Symbolic Reasoning: Coin Flip and Last Letter Concatenation.
- Open-ended Generation: MBPP (Mostly Basic Python Problems) to demonstrate the method's utility beyond fixed-choice answers.
Key Insights
- Entropy as a Confidence Signal: Correct answers tend to cluster tightly (low entropy), while incorrect reasoning paths lead to a "scattered" distribution of wrong answers. A unanimous window is a very strong signal that the model has "found" the correct path.
- Simplicity and Model-Agnosticism: Unlike previous "adaptive" methods, ESC requires no extra training, no human annotation, and no complex hyperparameters. It is entirely unsupervised and works across different model architectures.
- Orthogonality: ESC can be combined with other advanced prompting techniques. For example, applying ESC to Progressive-Hint Prompting (PHP) makes advanced reasoning pipelines significantly more efficient.
Results and Discussion
The empirical results are striking. ESC achieved nearly identical accuracy to standard SC while drastically reducing the average number of samples:
- GSM8K: Reduced samples by 80.1%.
- StrategyQA: Reduced samples by 76.8%.
- CommonsenseQA: Reduced samples by 78.5%.
- MATH: Reduced samples by 33.8% (reflecting the higher difficulty and lower model confidence on this dataset).
- Cost Savings: On GSM8K using GPT-4, the cost per item dropped from roughly $0.23** (standard SC) to **$0.08 (ESC).
Crucially, the "Intersection Ratio" (how often ESC and SC pick the same answer) remained above 99% across most models and tasks, proving that the early exit rarely leads to a different conclusion than the full, expensive run.
Conclusion and Limitations
While ESC is highly effective, the "all answers in a window must be the same" rule is conservative. In extremely difficult tasks where the model is highly uncertain, ESC might rarely trigger, reverting to the full cost of SC. Additionally, choosing a window that is too small (e.g., $w=2$) could lead to "false" consensuses on deceptive problems.
In summary, ESC provides a much-needed "off-ramp" for the expensive sampling processes currently required for high-performance LLM reasoning, making advanced AI more accessible to researchers and developers with modest budgets.
Summary updated