Let’s Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLM s (2023)

Abstract: 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%

## introduction the increasing adoption of large language models (llms) across various tasks, such as text generation and reasoning @xcite @xcite , mathematical reasoning @xcite @xcite , and code generation @xcite , has underscored the importance of improving the correctness of their outputs. a popular method for achieving this goal is self-consistency @xcite , a majority voting technique where multiple output samples are generated for a given input, and the final decision is based on the most frequently occurring output among the samples. current self-consistency methods typically employ a fixed budget approach, wherein a predetermined number of samples (e.g., 40) are generated to make a decision. however, as llms continue to grow in size and complexity, the sampling time and computational costs associated with majority voting become increasingly challenging. this challenge is particularly evident in high-stakes applications like competition-level code generation @xcite , where generating a large number of programs, sometimes up to a million, is essential for maximizing performance. to address this challenge, we introduce adaptive-consistency, a cost-efficient, model-agnostic majority voting technique. adaptive-consistency employs a lightweight stopping criterion that dynamically adjusts the number of samples (n) for each input, as opposed to using a fixed budget (k). the intuition is that if a clear majority is established with high confidence after sampling fewer than k answers (@xmath0, there is no need to generate additional samples. adaptive-consistency models the probability distribution over unique samples using a dirichlet distribution, allowing us to quantify the confidence in the lead of the majority element over other elements. for instance, if the majority element has a count of 9 out of the first 10 samples, the likelihood of it remaining the majority element even after 40 samples is very high (> 99%). this allows adaptive-consistency to stop sampling at this point, reducing the cost by 30 samples, while self-consistency would continue to sample all 40 answers. as an inference-time technique requiring no additional training, adaptive-consistency provides a convenient off-the-shelf option for all pre-trained language models, offering the flexibility to balance computational cost and performance. we evaluate adaptive-consistency on 17 diverse tasks and three llms of different scales (vicuna-13b, code-davinci-002 and gpt-3.5-turbo). our experimental results show that adaptive-consistency outperforms self-consistency regarding cost efficiency while maintaining comparable output quality. on code-davinci-002, adaptiveconsistency reduces the number of samples required by a factor of 3.4×, with no average drop in accuracy. on vicuna-13b, it requires sampling 1.9× fewer samples, with almost no drop in accuracy. similarly, on gpt-3.5-turbo, it samples 4.4× fewer samples, with less than 0.2% drop in accuracy. in summary, our contributions are: in-context few-shot prompting in-context few-shot prompting is a technique employed by large language models (llms) to learn and generalize from a limited number of examples provided within the input of a given task. the model can quickly adapt to novel tasks without fine-tuning or additional training by conditioning the model on a few examples. specifically, a prompt p is constructed by concatenating multiple input-answer example @xmath1, a i >. the prompt is then prepended to the test input x test , and the model generates the corresponding answer a test . ## adaptive-consistency self-consistency generates a predetermined number of answers (k) from the language model (llm) before returning the majority answer. in contrast, the adaptive-consistency method takes an incremental approach to sampling outputs from the language model. after generating each sample, adaptive-consistency employs a lightweight stopping criteria to determine whether it should 1.) generate an additional sample from llm or 2.) cease sampling and report the current majority answer. this flexible strategy enables adaptive-consistency to dynamically adjust the number of samples generated so far (n) for each input. as our experiments demonstrate, n is typically less than k (on average, 3.3× and up to 7.9× less in some cases), allowing adaptive-consistency to offer greater cost-efficiency compared to the fixed budget approach employed by self-consistency. adaptive-consistency differs from self-consistency only in terms of the stopping criteria (listing 1). the design of the stopping criteria is crucial to our method, as it aims to minimize the average number of samples generated from the llm while maximizing accuracy. the simplicity of our algorithm allows for the use of various stopping criteria interchangeably, each with its own advantages and disadvantages. we expand on a particular choice of stopping function next. ## experiments we evaluate adaptive-consistency using 17 diverse benchmark datasets and three different language models. we use prompts by program-aided language models, pal, @xcite , self-consistency @xcite and codet @xcite . datasets we evaluate our method on a diverse set of reasoning and coding benchmarks, encompassing 17 datasets across 4 distinct categories: 1. mathematical reasoning: we use gsm-8k @xcite , svamp @xcite , and asdiv @xcite which assess the mathematical reasoning capabilities of the llms. 2. commonsense reasoning tasks: we evaluate on 5 datasets: strategyqa (geva et al., 2021), date understanding, snarks, ruin names, salient translation that measures different capabilites of llms such as multi-hop reasoning and emotional understanding. 3. sym-bolic reasoning tasks: we further examine performance on 5 diverse symbolic reasoning tasks: tracking shuffled objects, logi-cal deduction, boolean expressions, dis-ambiguation qa, penguins. 4. code gen-eration tasks we also evaluate our method on coding tasks, which require to generate a working code given a textual problem description. we evaluate on 4 datasets of varying difficulty: hu-maneval @xcite , mbpp @xcite , apps @xcite and codecontests @xcite . we refer readers to appendix a.2 for more details. ## conclusion and future work this paper presented adaptive-consistency, a costefficient and model-agnostic technique for improving the correctness of output from large language models (llms) using dynamic sampling. our approach builds upon the self-consistency method and introduces a lightweight stopping criterion that allows for adaptive sampling based on the amount of agreement in the samples drawn so far. adaptive-consistency is effective across 17 datasets and three llms, on both reasoning and coding tasks. it reduces the required sample budget by 2 to 4 times, while maintaining comparable accuracy, with an average drop of less than 0.1%. our work opens up several avenues for future research. we may develop alternative stopping criteria, or combining multiple criteria could lead to even more efficient sampling techniques. moreover, in our current approach, the majority decision relies on using matches to determine the most common answer. however, this may not always capture the true majority, e.g., in generative tasks, where the output can have variations that do not affect the overall correctness or relevance of the answer. to foster further research and enable reproducibility, we have released the code and llm outputs at https://sample-step-by-step.info/ .