Source-linked AI summary
Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang, Kan Li
TL;DR
Self-consistency improves multi-step reasoning but requires costly preset-size sampling. The paper proposes Early-Stopping Self-Consistency, which serializes sampling into windows and uses answer-distribution entropy to stop early, with a control scheme for choosing the performance-cost balance. Across six benchmarks, ESC substantially reduces sampling while attaining comparable performance.
Problem
Self-consistency improves reasoning but incurs sampling overhead proportional to the number of outputs, motivating lower-cost decoding without sacrificing performance.
Method
ESC serializes self-consistency sampling into windows, stops when a window has low entropy, and adds a control scheme that selects window and maximum sampling sizes.
Results
ESC reduces chain-of-thought sampling across six benchmarks while attaining comparable performance, including reductions from MATH (-33.8%) to Coin Flip (-84.2%).
Takeaways & Limitations
ESC provides a model-agnostic, unsupervised way to reduce self-consistency cost while preserving reasoning performance across tasks and models.
Takeaways & Limitations
The theoretical analysis includes a specific hypothesis-testing setup with an observation-window assumption of w = 8 and a stated rejection rule.
Abstract
from arXiv · showhide
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, \textbf{E}arly-Stopping \textbf{S}elf-\textbf{C}onsistency (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.
1 INTRODUCTION
Self-consistency improves multi-step reasoning by voting across sampled reasoning paths, but its preset sampling size creates substantial cost. ESC serializes sampling into windows and stops when a window provides sufficiently concentrated answers, while a control scheme adapts the performance-cost trade-off.
- Motivation: SC improves reasoning by sampling multiple paths and selecting the most frequent answer, unlike greedy chain-of-thought generation.The sampled paths approximate the model's answer distribution, but SC need not fully estimate that distribution when a confident partial sample suffices.
- Motivation: SC's overhead grows with the number of sampled outputs, making cost reduction necessary for practical multi-step reasoning.Evaluating MATH with GPT-4 using 64 samples costs about 2000$.
- Method: ESC reduces SC's sampling cost by stopping when a window's answers are identical, while aiming to preserve the voting result.The method uses entropy to identify concentrated answer distributions and stops at the strictest zero-entropy threshold.
- Contributions: ESC is unsupervised and model-agnostic, and its control scheme selects window and maximum sampling sizes to balance performance and cost across tasks and models.The paper also derives an upper bound for inconsistent results with early stopping and evaluates the control scheme across settings.
- Results: Across six benchmarks, ESC reduces chain-of-thought sampling while maintaining comparable performance, and its control scheme predicts the performance-cost balance across tasks and models.Reported sampling reductions are MATH (-33.8%), GSM8K (-80.1%), StrategyQA (-76.8%), CommonsenseQA (-78.5%), Coin Flip (-84.2%), and Last Letters (-67.4%).
2 METHOD
ESC reframes self-consistency as adaptive sampling: it stops when a window suggests a sufficiently concentrated answer distribution, while retaining SC when stopping does not occur. Its control scheme estimates cost and inconsistency under candidate settings to select a performance-cost trade-off.
- 2.1 REVISITING SELF-CONSISTENCY: Self-consistency selects the prediction with the highest sampling frequency, approximating the model outcome with the highest probability as the sample size grows.The indicator-based vote counts occurrences of each candidate prediction across L samples.
- 2.2 EARLY-STOPPING SELF-CONSISTENCY: ESC samples consecutive windows and stops when all predictions in a window agree, treating this as evidence that the distribution is sufficiently concentrated.The remaining samples are aggregated for voting, while sampling continues across windows until agreement or the preset maximum is reached.
- 2.3 THEORETICAL ANALYSIS: For unbounded sampling, the analysis states that with window size w = 8, the probability of an ESC voting result inconsistent with SC is ≤2 × 10^-3.The stated upper bound decreases as the window size increases.
- 2.4 CONTROL SCHEME FOR EARLY-STOP SELF-CONSISTENCY: The control scheme estimates expected sampling cost and performance for different window sizes and maximum sample sizes, then chooses settings meeting the available budget and performance requirement.It derives expected stopping cost from the first observation window and accounts separately for early-stop and no-early-stop cases under bounded sampling.
3 EXPERIMENTS
ESC is evaluated across six reasoning benchmarks, three language models, varied sampling settings, an open-ended task, and consistency with SC. Across these experiments, it substantially reduces sampling cost while preserving comparable performance and supports controllable performance-cost trade-offs.
- 3.2 MAIN RESULTS: ESC reduces sampling cost while barely affecting accuracy across six reasoning benchmarks and three language models.Table 1 reports accuracy and average actual generated samples for CoT, SC, ESC, and ˆL-SC.
- 3.2 MAIN RESULTS: ESC maintains performance while saving costs across different maximum sampling sizes and remains robust to window size and maximum sampling number on GSM8K.Table 2 varies maximum sampling size with window size 8, while Figure 3 examines window and maximum sampling size across models.
- 3.2 MAIN RESULTS: ESC’s cost savings correlate positively with performance and do not require prior knowledge of model capabilities or task difficulty.The paper also proposes a control scheme to select a performance-cost balance for different settings.
- 3.3 EFFECTIVENESS OF CONTROL SCHEME FOR ESC: The control scheme’s predicted sampling cost and performance change strongly agree with observed values, with Pearson correlations above 0.8 and low L1 norms.Table 3 evaluates predicted and actual ˆL and Pδ using Pearson correlation and L1 norm.
- 3.4 ESC FOR OPEN-ENDED GENERATIONS: ESC also applies to open-ended generation, where MBPP experiments evaluate accuracy and average generated samples across maximum lengths.The authors report that ESC is suitable for open-ended tasks.
- 3.6 ROBUSTNESS OF ESC: ESC is robust to temperature, top-p values, zero-shot prompting, and different demonstration sets.GSM8K experiments vary sampling temperature, nucleus-sampling p, and demonstrations, with additional results reported for other settings.
4 RELATED WORK
Prior work established chain-of-thought prompting and self-consistency as methods for improving language-model reasoning, while subsequent extensions addressed broader generation and adaptive aggregation. These approaches still generally require multiple samples at a preset size, creating substantial computation cost.
- Chain-of-thought Reasoning: Chain-of-thought prompting solves complex reasoning problems by gradually solving sub-problems, with both few-shot and zero-shot variants stimulating language-model reasoning.
- Self Consistency: Self-consistency improves reasoning by leveraging multiple correct reasoning paths rather than relying on a single greedy chain-of-thought path.
- Self Consistency: Extensions replace answer voting with text-similarity matching for open-ended generation and assign adaptive weights for answer aggregation, but still require multiple samples with a preset size.
5 CONCLUSION
The paper concludes that Early-Stopping Self-Consistency reduces self-consistency sampling costs while retaining comparable performance. Its control scheme further targets task- and model-dependent performance-cost choices without requiring prior capability or difficulty knowledge.
- ESC significantly reduces chain-of-thought sampling on six benchmarks while attaining comparable performance.Additional evaluations report robust cost savings across decoding settings, prompts, and open-ended generation tasks.
- The ESC control scheme dynamically selects the performance-cost balance across tasks and models without extra prior knowledge of model capabilities or task difficulty.
- The control scheme accurately predicts the performance-cost trade-off across various tasks and models.
A.1 DERIVATION OF THE EXPECTATION OF SAMPLING COST
The derivation computes ESC’s expected sampling cost from the probability of stopping in each observation window. It accounts for both early stopping before the maximum and reaching the maximum sampling size.
- The probability of early stopping after j windows is P̂stop × pow(1 − P̂stop, j), combining stopping in the current window with continuation through preceding windows.
- If early stopping does not occur after the first L//w − 1 windows, the next observation window reaches the maximum sampling size L.
- The overall expected sampling cost adds the expected costs of early stopping or reaching L to the initial window cost w0.The displayed expression includes the window-weighted stopping terms, the probability of reaching L, and w0.
A.2 COMPARISON WITH ADAPTIVE-CONSISTENCY (AC)
Compared with Adaptive-Consistency, ESC avoids validation-based threshold tuning and reduces input overhead by generating samples in shared windows. The supplied comparison table reports prompt and completion tokens, sampling cost, and accuracy for the methods.
- ESC needs no hyperparameter because its conservative stopping criterion requires all answers within a window to be identical, unlike AC’s threshold-sensitive criterion.Consequently, ESC can be applied across tasks and models without a validation set.
- AC generates samples step by step, requiring one input per sample and repeating the substantial in-context-learning demonstration tokens.
- ESC shares the same input across samples within each sampling window, and Table 7 compares the methods using prompt tokens, completion tokens, sampling cost, and accuracy.
A.3 COMPARISONS BETWEEN SC AND ESC WHEN L IS RELATIVELY SMALL (10 AND 20)
With smaller maximum sampling sizes of 10 and 20, ESC continues to reduce sampling costs while maintaining or improving performance relative to SC.
- A.3 COMPARISONS BETWEEN SC AND ESC WHEN L IS RELATIVELY SMALL (10 AND 20): ESC consistently saves sampling costs under smaller maximum sampling sizes while improving over SC at the same costs.The experiments use smaller sampling sizes L, with results reported in Table 8.
- A.3 COMPARISONS BETWEEN SC AND ESC WHEN L IS RELATIVELY SMALL (10 AND 20): The small-L analysis tests whether ESC's cost savings persist when the preset sampling budget is reduced.
- A.3 COMPARISONS BETWEEN SC AND ESC WHEN L IS RELATIVELY SMALL (10 AND 20): Table 8 reports reasoning accuracy and average sampling size for varying maximum sampling sizes L, using a window size of 5.
A.4 DISCUSSION ON THE CHOICE OF INTRODUCING OBSERVATION WINDOW FOR THE DESIGN OF EARLY-STOPPING STRATEGY
ESC uses an observation window and stops when all samples in the latest window are consistent, avoiding the statistic and threshold required by one-by-one stopping. Figure 5 compares SC, ESC, and entropy-based ENT on CSQA across models.
- A.4 THE CHOICE OF INTRODUCING OBSERVATION WINDOW: ESC breaks sampling only when all samples in the latest observation window are consistent, providing a strict stopping condition without an additional hyper-parameter.Stopping one sample at a time would require a statistic and corresponding threshold.
- A.4 THE CHOICE OF INTRODUCING OBSERVATION WINDOW: The observation window avoids the threshold-selection problem that arises when stopping based on individual sampled outputs.
- A.4 THE CHOICE OF INTRODUCING OBSERVATION WINDOW: Figure 5 compares SC, ESC, and ENT, which uses entropy to determine the cutoff point, on CSQA with different models.
A.5 THE COMPARISONS BETWEEN ESC AND OTHER STRONG REASONING BASELINES.
ESC is compared with stronger reasoning baselines on performance and overhead, including PHP and PHP combined with ESC. These comparisons report lower sampling costs for ESC while preserving or improving performance, alongside robustness analyses across decoding and stopping settings.
- A.5 THE COMPARISONS BETWEEN ESC AND OTHER STRONG REASONING BASELINES: ESC outperformed CoT by 9.84%, exceeding PHP's 9.25%, while incurring less sampling overhead on GSM8K with GPT-3.5-Turbo.Table 9 compares prompt tokens, completion tokens, average sampling cost, and accuracy; ESC's maximum sampling size is 40.
- A.5 THE COMPARISONS BETWEEN ESC AND OTHER STRONG REASONING BASELINES: PHP with ESC achieved similar performance to PHP with SC while significantly reducing sampling overhead, indicating that ESC can complement an advanced reasoning method.The comparison is reported in Table 10 for GSM8K with GPT-3.5-Turbo and a window size of 5.
- A.5 THE COMPARISONS BETWEEN ESC AND OTHER STRONG REASONING BASELINES: ESC's robustness is analyzed across sampling temperature, nucleus-sampling p, zero-shot demonstration, observation-window size w, and maximum sampling size L.Figure 6 studies these factors on StrategyQA with GPT-3.5-Turbo, while Figure 7 covers multiple datasets and models.
- A.5 THE COMPARISONS BETWEEN ESC AND OTHER STRONG REASONING BASELINES: The experiments use prompts following prior work, including Wei et al. (2022) for datasets other than MATH and dedicated few-shot prompts for MATH.