Research map / Large language models / Reasoning and chain of thought
Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Early-Stopping Self-Consistency (ESC), which samples in windows and stops once a window's answers all agree, cutting chain-of-thought sampling cost by 33-84% with negligible accuracy loss, plus a control scheme to predict the cost-performance trade-off.
Problem
Self-consistency for chain-of-thought reasoning requires a preset large number of samples, which is very expensive (e.g., roughly $2000 for MATH with GPT-4 at 64 samples).
Approach
Sample in small sequential windows and stop as soon as a window's predictions are unanimous (zero entropy), since low-entropy answer distributions make the majority vote stable with few samples; add a control scheme that uses the first window to predict cost and error for different window and max-sample settings.
Key results
- ESC reduces average sampling counts by 33.8% on MATH, 80.1% on GSM8K, 76.8% on StrategyQA, 78.5% on CommonsenseQA, 84.2% on Coin Flip and 67.4% on Last Letters while keeping accuracy within about 0.03 points of SC for GPT-4 and GPT-3.5-Turbo.
- On GSM8K with GPT-4 ESC matches SC accuracy (89.29) using about 7.98 samples on average versus 40.
- Intersection ratio between ESC and SC voting results is about 99-100% across GSM8K, StrategyQA and Letter, supporting the theoretical bound.
- ESC cost on GSM8K with GPT-3.5-Turbo is $0.0052 per item versus $0.0084 for SC and $0.0087 for Adaptive-Consistency, with higher accuracy than AC.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| early-stopping window (ESC) instead of fixed sampling | self-consistency on GSM8K/MATH/CSQA/SQA/Letter · GPT-4, GPT-3.5-Turbo, Llama-2 7b | accuracy and average sampled outputs: sampling reduced 21.6% to 33.7% with accuracy change within about 0.03 points | Helped |
| early stopping on MATH with GPT-4 (window 8, max 64) | self-consistency · MATH | average sampled outputs: -21.60 (L-hat 42.40 vs 64), accuracy unchanged at 60.32 | Helped |
| early stopping on GSM8K with Llama-2 7b | self-consistency · GSM8K | average sampled outputs: -8.79 samples, accuracy -0.01 | Helped |
| early stopping with max sample size varied from 16 to 64 (window 8) (ablation) | self-consistency on MATH, GPT-4 · MATH | accuracy (%): 0.00 at every L | No clear effect |
| early stopping on MBPP open-ended generation | self-consistency with text-similarity voting · MBPP, GPT-3.5-Turbo | accuracy (%): -0.02 to -0.04 at L=20 to 30, with L-hat 23.21% fewer samples at L=30 | No clear effect |
| early stopping vs. adaptive consistency (AC) on GSM8K | self-consistency · GSM8K, GPT-4 | cost per item ($) and accuracy: ESC $0.0769 at 89.29 vs AC $0.1501 at 89.28 | Helped |
| early stopping on GSM8K for Llama-2 7b with lower max L (10 and 20) (ablation) | self-consistency · GSM8K, Llama2-7b | accuracy (%): 0.00 at L=10 and 0.00 at L=20 (variable sampling saved 1.01 and 2.94 samples) | No clear effect |
| replacing entropy-based stopping after each sample with window-based all-same stopping (ablation) | early stopping criterion · CSQA, multiple models | performance-cost trade-off: qualitative: entropy cut-off has no advantage over ESC and adds a hyperparameter | Helped |
| ESC applied to Progressive-Hint Prompting on GSM8K (ablation) | PHP · GSM8K, GPT-3.5-Turbo | accuracy (%): -0.02 at L=20 and 40, with 12.17 to 29.74 fewer samples | No clear effect |
Surprising findings
- Entropy-based stopping after each single sample performed no better than the windowed ESC on the performance-cost trade-off, because per-sample checks are too frequent and noisy.
Limitations
- Theoretical guarantee relies on a one-proportion z-test approximation and assumes the first window reflects the true answer distribution.
- Savings are smaller on MATH (-33.8%) where answers are more diverse, and Llama-2 7b saves little on some tasks.
- Evaluated only on a few models and benchmarks; open-ended generation is tested only on MBPP.
Experimental setup
Datasets: MATH GSM8K CommonsenseQA StrategyQA Last Letter Concatenation Coin Flip MBPP
Benchmarks: MATH GSM8K CommonsenseQA StrategyQA Last Letter Concatenation Coin Flip MBPP
Metrics: accuracy average sampled count (L-hat) API cost ($) performance change percentage
Baselines: CoT SC Adaptive-Consistency Progressive-Hint Prompting ENT (entropy-based stopping)
Builds on: self-consistency chain-of-thought prompting adaptive-consistency
Closest papers by meaning
- Optimal Self-Consistency for Efficient Reasoning with Large Language Models (ICML 2026 · similarity 0.92)
- A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.89)
- Pause and Reflect: Conformal Aggregation for Chain-of-Thought Reasoning (NeurIPS 2026 · similarity 0.88)
- Reliable Chain-of-Thought via Prefix Consistency (NeurIPS 2026 · similarity 0.87)
- THE PATH OF LEAST RESISTANCE: GUIDING LLM REASONING TRAJECTORIES WITH PREFIX CONSENSUS (ICLR 2026 · similarity 0.87)
- Dynamic Early Exit in Reasoning Models (ICLR 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.