Source-linked AI summary
Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs
Pranjal Aggarwal, Aman Madaan, Yiming Yang, Mausam
TL;DR
Self-Consistency uses a fixed number of samples, making majority voting costly as LLMs and tasks grow more demanding. Adaptive-Consistency dynamically stops sampling based on agreement, reducing sample requirements while preserving comparable accuracy across broad reasoning and coding evaluations.
Problem
Fixed-budget Self-Consistency can make majority voting increasingly costly because it generates a predetermined number of samples for every input.
Method
Adaptive-Consistency is a model-agnostic majority-voting technique that dynamically adjusts sampling with a lightweight stopping criterion based on majority stability.
Results
Across 17 datasets and three LLMs, Adaptive-Consistency uses 2 to 4 times fewer samples while maintaining comparable accuracy, with an average drop below 0.1%.
Takeaways & Limitations
Adaptive-Consistency provides cost-efficient adaptive sampling for reasoning and coding tasks while preserving output quality relative to fixed-budget Self-Consistency.
Takeaways & Limitations
The stopping criterion may trigger when the majority is not stable, and effectiveness may vary across tasks or models.
Abstract
from arXiv · showhide
A popular approach for improving the correctness of output from large language models (LLMs) is Self-Consistency - poll the LLM multiple times and output the most frequent solution. Existing Self-Consistency techniques always generate a constant number of samples per question, where a better approach will be to non-uniformly distribute the available budget based on the amount of agreement in the samples generated so far. In response, we introduce Adaptive-Consistency, a cost-efficient, model-agnostic technique that dynamically adjusts the number of samples per question using a lightweight stopping criterion. Our experiments over 17 reasoning and code generation datasets and three LLMs demonstrate that Adaptive-Consistency reduces sample budget by up to 7.9 times with an average accuracy drop of less than 0.1%. Our code and data are available at https://www.sample-step-by-step.info
1 Introduction
Self-Consistency improves LLM output correctness through repeated sampling and majority voting, but fixed sample budgets make inference increasingly costly. Adaptive-Consistency dynamically stops sampling when agreement is sufficiently stable, reducing cost while preserving accuracy across diverse tasks and models.
- Adaptive-Consistency dynamically adjusts per-input sampling with a lightweight stopping criterion instead of using Self-Consistency’s fixed budget.If a clear majority emerges before the fixed budget, additional samples are omitted.
- The method models sample frequencies with a Dirichlet distribution to estimate whether the current majority will remain dominant.For example, a 9-to-1 majority after ten samples has over 99% likelihood of remaining dominant after 40 samples.
- Adaptive-Consistency reduces sampling by 3.4× on CODE-DAVINCI-002, 1.9× on VICUNA-13B, and 4.4× on GPT-3.5-TURBO with minimal accuracy loss.The reported accuracy effects are no average drop, almost no drop, and less than 0.2%, respectively.
- 3.3× fewer samples with less than 0.1% drop in accuracy across 17 datasets and three LLMs.The evaluation covers mathematical, commonsense, symbolic, and code-generation tasks.
- Up to 5% absolute-point accuracy gains over Self-Consistency occur at fixed sampling cost across datasets.
2 Background
The paper situates Adaptive-Consistency against in-context prompting and Self-Consistency, contrasting fixed-budget majority voting with adaptive early stopping. Its algorithm repeatedly samples outputs and halts when a stopping criterion is met.
- In-context few-shot prompting conditions an LLM on a prompt containing multiple input-answer examples before generating a test answer.
- The Self-Consistency baseline always generates a fixed number of samples before returning the majority result.
- Adaptive-Consistency samples incrementally and stops when a lightweight criterion indicates that further sampling is unnecessary.
- Self-Consistency samples diverse reasoning chains repeatedly and returns their majority answer, improving performance at increased computational cost.
3 Adaptive-Consistency
Adaptive-Consistency estimates the stability of the current majority and uses that estimate to decide whether to continue sampling. The method supports Dirichlet-based reasoning, a faster Beta approximation, and a test-case-aware variant for code generation.
- Adaptive-Consistency evaluates whether the current majority will remain dominant and stops when that probability exceeds a confidence threshold.The method uses the observed counts of unique answers to assess majority stability.
- The Dirichlet formulation integrates probability mass over outcomes that preserve the current majority, assuming the number of unique answers is known.A Chinese Restaurant Process criterion is described as relaxing that assumption.
- The Beta stopping criterion approximates the full calculation by comparing the leading probability with the next largest, enabling faster confidence computation.It uses a non-informative Beta(1, 1) prior.
- The Beta stopping criterion performs similarly to the Dirichlet criterion while being significantly faster.
- For code generation, Adaptive-Consistency treats test cases independently and stops when the geometric mean of their normalized probabilities exceeds a threshold such as 0.95.This avoids relying only on exact equality of complete output vectors across programs.
4 Experiments
The experiments evaluate Adaptive-Consistency across 17 reasoning and coding datasets, four task categories, and three language models, measuring sampled generations and accuracy against Self-Consistency.
- Experimental Setup: The evaluation covers mathematical, commonsense, symbolic reasoning, and code-generation benchmarks across 17 datasets.
- Evaluation: The study compares sampled generations and overall reasoning accuracy, focusing on the efficiency–accuracy trade-off against Self-Consistency.
- Results Across Task Categories: 3.3× fewer samples in mathematical tasks, 2.9× fewer in commonsense tasks, 3.8× fewer in symbolic reasoning, and 2.4× fewer in coding, with accuracy changes from a 0.2% drop to a 0.4% improvement.
- Results Across Language Models: 4.4× fewer generations for GPT-3.5-TURBO, 1.9× fewer for VICUNA-13B, and 3.4× fewer for CODE-DAVINCI-002, with minimal to no accuracy impact.
5 Analysis
The analysis examines threshold, budget, and stopping-function choices for Adaptive-Consistency. It shows that adaptive sampling improves cost-controlled accuracy while exposing trade-offs between confidence, computation, and stopping quality.
- 5.1 Impact of Confidence Threshold: As Cthresh increases, accuracy gradually plateaus while the average number of samples initially rises gradually and then climbs more steeply.
- 5.2 Adaptive-Consistency vs. Self-Consistency For Equal Average Sample Costs: Adaptive-Consistency outperforms Self-Consistency in accuracy across all average sample costs on GSM-8K, with approximately 3% higher accuracy at a cost of 10 samples.
- 5.2 Adaptive-Consistency vs. Self-Consistency For Equal Average Sample Costs: Adaptive-Consistency varies samples by instance complexity, using more samples when consensus is difficult and fewer when answers are consistent.
- 5.3 Evaluation of Different Stopping Functions: BETA consistently achieves higher accuracy than ENTROPY and MAJORITY at the same sampling cost, while DIRICHLET and CRP have similar performance but are about four orders of magnitude slower.
- 5.3 Evaluation of Different Stopping Functions: 7.9× lower computational budget on BOOLEAN EXPRESSIONS is achieved without accuracy loss, while SVAMP reaches comparable accuracy using fewer than 5 samples per input on average.
6 Related Work
Related work spans crowdsourcing, adaptive computation, inference-time computation, and adaptive sampling. Adaptive-Consistency differs by adaptively sampling multiple outputs from pretrained language models during inference.
- Crowdsourcing and Adaptive Consistency: Adaptive-Consistency draws inspiration from crowdsourcing resource-allocation methods but is tailored to LLM computational efficiency and output accuracy.
- Crowdsourcing and Adaptive Consistency: Figure 3 reports that Adaptive-Consistency consistently beats Self-Consistency across sampling costs on GSM-8K and DATE UNDERSTANDING, especially at low cost.
- Crowdsourcing and Adaptive Consistency: Figure 4 reports that BETA beats ENTROPY and MAJORITY in accuracy at the same sampling cost.
- Inference-time Adaptive Computation: Inference-time adaptive-computation work adjusts computation without architectural modifications, whereas Adaptive-Consistency controls the number of sampled outputs.
- Adaptive Sampling in Training and Active Learning: Unlike adaptive training or active-learning methods, Adaptive-Consistency samples multiple outputs per input during inference without soliciting additional labels.
7 Conclusion and Future Work
The conclusion presents Adaptive-Consistency as a cost-efficient, model-agnostic dynamic-sampling method effective across reasoning and coding tasks. It also identifies answer matching as a limitation for generative outputs with equivalent variations.
- Adaptive-Consistency reduces required samples by 2 to 4 times across 17 datasets and three LLMs while maintaining comparable accuracy, with an average drop below 0.1%.
- The method’s majority decision relies on exact matches, which may not capture true majority correctness or relevance when generative outputs vary in form.
- The paper suggests future work on alternative or combined stopping criteria and releases code and LLM outputs for reproducibility.
Limitations
Adaptive-Consistency has limitations involving its stopping criterion, generalizability, task adaptation, and dependence on the pretrained LLM. The authors identify these as areas for future improvement.
- The stopping criterion may trigger when the majority element is unstable, leading to potentially suboptimal decisions.The authors suggest exploring more robust or alternative stopping criteria.
- Effectiveness may vary across tasks or models, and Adaptive-Consistency is anticipated to fail where Self-Consistency fails.The method was tested on 17 datasets and three LLMs, but broader generalizability remains uncertain.
- A task-agnostic design may limit performance on tasks that could benefit from specialized adaptations.The authors report initial code-generation experiments but note that extending task-specific adaptations to other domains may be less straightforward.
- Adaptive-Consistency inherits limitations and biases from the pretrained LLM used to generate multiple samples.Addressing these issues may require improved LLM training or external knowledge sources.
- The method uses a high stopping threshold of Cthresh = 0.95 to maintain accuracy and avoid stopping too early.For other stopping criteria, thresholds are tuned on GSM-8K training data and reused across datasets.
A.2 Benchmarks
The evaluation covers 17 diverse reasoning and code-generation datasets spanning mathematical, commonsense, symbolic, and programming tasks. Experiments query GPT-3.5-TURBO, CODE-DAVINCI-002, and VICUNA-13B, with additional code-generation testing procedures.
- 1. Mathematical Reasoning: Mathematical benchmarks include GSM-8K, SVAMP, and ASDIV, which test gradeschool algebra word problems requiring arithmetic and contextual problem solving.
- 2. Commonsense Reasoning Tasks: Commonsense and symbolic evaluations include strategy inference, date reasoning, translation-error detection, object tracking, logical deduction, Boolean expressions, and pronoun disambiguation.
- The benchmark suite contains 17 datasets across mathematical, commonsense, symbolic reasoning, and code-generation categories.Table 3 describes variation in difficulty, domains, answer types, and test-set sizes.
- 4. Code Generation Tasks: Code-generation evaluation uses HumanEval, MBPP, APPS, and CodeContests, covering basic Python tasks and more challenging competition-level problems.For these tasks, the authors generate up to 10 assert-based test cases in one or two prompts.
- Experiments query GPT-3.5-TURBO and CODE-DAVINCI-002 through OpenAI's API and run VICUNA-13B inference on single A100 GPUs.Coding tasks use zero-shot prompting with temperature=0.8 and top_p=0.95.
B Results
The reported results indicate that Adaptive-Consistency is significantly more efficient in generation count while preserving accuracy differences that are statistically insignificant relative to the baseline.
- Complete results with standard deviations are reported in Table 5, with code-generation results reported separately in Table 4.
- The number of generations is significantly lower for Adaptive-Consistency, while its slight accuracy difference from the baseline is statistically insignificant.Across datasets, the average p-value is 1.5e-3 for generations and 0.50 for accuracy, based on two-sample t-tests over three random seeds.
C.1 Adaptive-Consistency vs. Self-Consistency For Equal Average Sample Costs
At equal average sampling costs, Adaptive-Consistency achieves higher accuracy than Self-Consistency by allocating more samples to difficult instances and fewer to consistent ones. Among stopping criteria, BETA performs best in the desirable accuracy-cost range, while DIRICHLET and CRP are slower and ENTROPY is less interpretable.
- Adaptive-Consistency outperforms Self-Consistency in accuracy across all average sample costs, including approximately 3% higher accuracy on GSM-8K at cost 10.
- Adaptive-Consistency improves overall performance at matched average cost by using more samples for hard instances and fewer for consistent ones.
- DIRICHLET and CRP perform similarly to BETA but are relatively slow, whereas ENTROPY lacks a human-interpretable stopping rationale.
- BETA beats ENTROPY and MAJORITY at the same expected sampling cost, while RANDOM and MAJORITY are inferior across datasets and models.
- DIRICHLET assumes the number of possible unique answers is known, while CRP removes this assumption by modeling new answers as new clusters.
D Derivation of DIRICHLET stopping criteria
The DIRICHLET criterion models uncertainty over answer probabilities from observed sample counts and estimates the probability that the current majority remains dominant. Because the full computation is expensive, BETA reduces the comparison to the leading two answers.
- The derivation assumes the latent probability vector is uniformly distributed over the (m − 1)-simplex before observing samples.
- Given observed answer counts, the posterior over answer probabilities is a Dirichlet distribution with parameters v_i + 1.
- DIRICHLET estimates the probability that the current majority probability remains greater than every other answer probability by integrating over a simplex region.
- Because DIRICHLET requires m − 1 dimensional integration, BETA instead compares the leading two probabilities using a beta distribution with parameters v_1 + 1 and v_2 + 1.
- Across 17 datasets, Adaptive-Consistency reduces sample budget by 3.2× with a 0.07% average accuracy drop, while the generation reduction is statistically significant.
- Adaptive-Consistency consistently beats Self-Consistency at equal average sampling cost, while its accuracy increases and generation count rises sharply as C_thresh becomes stricter.