Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs
Authors: Pranjal Aggarwal
Aman Madaan
Yiming Yang
Mausam .
Venue: EMNLP 2023 Main (2023)
Keywords: LLMs
reasoning
efficient reasoning
sampling in llms
TL;DR: We propose Adaptive Consistency, a method that significantly reduces the sampling cost of LLMs, with negligible drop in accuracy for coding and reasoning tasks.

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%

cost-efficient, Let's Sample Step by Step:
Sopptive-Consisteneyy for Efficient Reasoning and Coding with LLMs
Pranjal Aggarwal' Aman Madaan' Yiming Yang* Mausam
'Department of Computer Science, Indian Institute of Technology, Delhi 2 Yardi School of Artificial Intelligence, Indian Institute of Technology, Delhi Language Technologies Institute, Carnegie Mellon University pranjal204 mennjal2441@gmal...m com, amadaan@cs, cmu.edu, yimingêcs. cmc.ess.ccccco cmu. edu, mausamēcse. iitd.
Abstract
to grow in size and complexity, the sampling time and computational costs associated with majority voting become increasingly challenging. This chal- lenge is particularly evident in high-stakes appli- cations like competition-level code generation (Li et al., 2022), where generating large number of programs, sometimes up to a million, is essential for maximizing performance.
A popular approach for improving the correct- ness of output from large language models (LLMss) is Self-Consistency poll the L.M 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 non-uniformly distribute the available bud- get based on the amount of agreement in the samples generated so far. In response, we in- troduce CllaptveeCoossssenne
To address this challenge, we introduce Adaptive- Consistency, cost-efficient, model-agnostic ma- jority voting technique. Coappivv-CCnsssteneyy em- ploys lightweight stopping criterion that dynam- ically adjusts the number of samples (n) for each input, as opposed to using a fixed budget (A:). The intuition is that if clear majority is established with high confidence after sampling fewer than k answers (n < k), there is no need to generate addi- tional samples.
model-agnostic technique that dynamically ad- justs the number of samples per question us- ing a lightweight stopping criterion. Our ex- periments over 17 reasoning and code genera- tion datasets and three LLMs demonstrate that reduces sample budget by up to 7.9 times with an average accuracy drop of less than 0.1% 1..
Plaptive-Conssitennyy models the probability distribution over unique samples using a Dirich- let distribution, allowing us to quantify the con- fidence in the lead of the majority element over other elements. For instance, if the majority ele- ment has count of 9 out of the first 10 samples, the likelihood of it remaining the majority element even after 40 samples very high (> 99%). This allows Chnssive- to stop sampling at this point, reducing the cost by 30 samples, while Self- SofffCoosistencyy would continue to sample all 40 answers. As an inference-time technique requir- ing no additional training. cdaptive-Consistene provides a convenient off-the-shelf option for all pre-trained language models, offering the flexibility to balance computational cost and performance.
1 Introduction
The increasing adoption of large language models (LLMs) across various tasks, such text genera- tion and reasoning (Wei et al., 2022; Kojima et al., 2022; Wang et al., 2022a; Mishra et al., 2022), mathematical reasoning (Lewkowycz et al., 2022; Gao et al., 2022; Arora et al., 2023), and code gen- eration (Li et al., 2022; Madaan et al., 2023b), has underscored the importance of improving the cor- rectness of their outputs. A popular method for achieving this goal is Self- Consisteeyyy (Wang et al., 2022b), 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.
We evaluate Adaptive- Coaerivv-Cosssttncyy on 17 diverse tasks and three LLMs of different scales (VICUNA- 13B, CODE-DAVINCE Our experimental results show that Adaptive- Consistency outperforms Self-Consistency regard- ing cost efficiency while maintaining comparable output quality. On CODE-DAVINCI-002 Adaptive-
Current Self- Consistency methods typically em- ploy fixed budget approach, wherein predeter- mined number of samples (c.g., 40) are generated make decision. However, as LLMs continue
and GPT-3.5-TURBO)
'Code and I.IM outputs are available at https:// sample-step-b-- styy-step.iifi info/.

---

Majority
11 The Answer
72
72 V
Answer
33 The Answeris
sample
Q: John has 3 boxes. Each box 5 inches by inches by inches. The walls are inch thick, What is the total inner volume of all boxes?
Sampling
40
Self Consistency
40. The Answer
72
Cost
Adaptive Consistency
Resample
Stopping Criterta
Report
72
Answer
Cont-Consittency Adaptive-Conseee Consistency
Sampling
10%
Cost
23 The Answer
72
BOX
11-018
-92%
sajuees
30
0
Answer
72
MATH
CommonSennse
Symbolic
10.1 The Answer is
72
Figure 1: An overview of Adaptive- Consistency: Self Consistency samples a predetermined number of answers. iteratively samples until lightweight Stopping Criteria, decides report the
whereas Adaptive-Consisen majority answer. The figure demonstrates an example where adaptive-Consistern requiring only ten samples to report the majority answer. The bottom-left graph contrasts Adaptive- Consistency with Self-Consistency across three reasoning categories, showing average sample budget reduction of 3.3x with a negligible 0.04% drop in accuracy.
reduces sampling costs by 4x,
Consistency reduces the number of samples re- quired by a factor of 3.4x, with no average drop in accuracy. On VICUNA- 13B, requires sampling 1.9x fewer samples, with almost no drop accu- racy. Similarly, on GPT-3.5-TURBH 4.4x fewer samples, with less than 0.2% drop in accuracy. In summary, our contributions are:
Our analysis reveals that for fixed sam- pling cost, Adaptive-Consistenn consistently achieves better accuracy than Self-Consistency across all datasets (upto 5% absolute points). Additionally, we experiment with various stop- ping criterias and show the efficacy of Adaptive- Consistency in terms of speed and accuracy.
samples
We propose Chaaptive-oossstennyy cost- efficient sampling technique for large language models that dynamically adjusts the number of samples using a lightweight stopping criterion based on the stability of the majority element.
Background
In-Context Few-Shot Prompting In-context few-shot prompting is a technique employed by large language models (LLMs)) to learn and gener- alize 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 additional training by conditioning the model on few examples. Specifically, a prompt p is con- structed by concatenating multiple input-answer example pairs 34₁ 0g >. The prompt is then prepended to the test input Stests and the model generates the corresponding answer atest-
We conduct extensive experiments using three different LLMs on diverse set of 17 datasets. These datasets encompass a wide range of tasks, including MATH, COMMONSENSE, SYM- BOLIC reasoning, and CODE GENERATION tasks. Adaptive-Consistern consistently and significantly outperforms fixed-budget methods like Calf-Consistency, requiring an average of 3.3x fewer samples with less than 0. % drop in accuracy across all datasets and models.

---

be the normal- Consistency only in terms of the stopping criteria (Listing 1). The design of the stopping criteria is crucial to our method, as aims to minimize the average number 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 particular choice of stopping function next.
def edaactiee.ommsstteeyyrex.xx.c
stop_criterion):
observations = []
for k in range(1, max_gens):
observations farssaaeeeemmmmaeeeeooon.... if atop_criterion((bservviiooo break return majjritty(cbservationn
def stop_cr cri Lerionn (onbeeerrvations threshold):
it Implement your stopping criterion
def self_ wtt._/oossstecyyaa..eeeee observations = for k in range(1, max_gens): observations append(sample_frrmm..
Dirichlet Stopping Criteria Let n be the num- ber of samples generated from LLM so far, with m unique samples. Let t [v1, .2,.... Umm] be the counts of each element, and p;
return majjorit((obeeratioon
ized count. For instance, if n 10, and 3 (10 samples generated, with 3 unique elements), if [8, 1, 1], then we can be more confident that 01 the answer. On the other hand, if o = [4, 4, 2). then more samples need to be generated. Our goal is to formalize and quantify this intuition.
Listing I: Comparison of Alassive-Consistency (top) and Self- Cofsisteeste (bottom). Seff-Consistency al- ways generates a fixed number samples. contrast, Adaptive-Consiie Consistency rion, allowing it to adaptively halt the sampling process, which can lead improved efficiency and performance.
lightweight stopping crite-
By convention, let pi max(p;). We want to assess the stability p1 as the majority element.? Specifically, we want to ask the following question: what is the probability that P1 will be the majority element if we repeat the process of generating n samples again? Intuitively, if this probability is higher than some predetermined threshold Ctbresh- then we can be more confident in our decision stop sampling and return Pı as the majority ele- ment:
Cols-onnsstency Wang al. (2022b) proposed Coffissnsstt which improved performance by sampling multiple diverse reasoning chains and aggregating their outputs using a simple major- ity voting mechanism. However, higher accuracy is achieved with an increased computational cost, since the LLM must be prompted multiple times for the same question.
3 Adaptive-Consiste
P(p > max
b) > Cthresh
Solf-Consistency generates a predetermined num- ber of answers (Ie) from the language model (LLM) before returning the majority answer. In contrast, the Aalaptive-Consistee
To answer this question, we establish a connec- tion with the Dirichlet distribution. Specifically, we note that the counts v parameterize Dirichlet distribution, Dir(V).3 This connection allows to explore the behavior of the sampling process by drawing more samples from Dir(V) and observ- ing the stability of pi as the majority element. To compute the probability p1 being the majority element, we can integrate the joint probability den- sity function of the Dirichlet distribution over the appropriate region of the probability simplex. The integral can be expressed as follows:
method takes an incre- mental approach to sampling outputs from the language model. After generating each sample, Conssive- employs lightweight slop- ping criteria to determine whether it should 1.) generate additional sample from LIM 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 i (on average, 3.3x and up to 7.9x less in some cases), allowing Chaptive-Consistenne to of- fer greater cost-efficiency compared to the fixed budget approach employed by Self-Consistency. Adaptive-Cone Consisteecy differs from Self-
Note that we overload the notation use Pı to represent both majority element its probability (usage clear from context).
Dirichlet is distribution over multinomials parameter- ized by counts V; each draw from Dirichlet is a multinomial distribution p. See Details in Appendix D

---

We now turn our attention CODE GENERATION lasks, which involve generat- ing programs that can correctly pass multiple test cases. More details on test case generation can be found in Appendix A.4.
Code-Generation
P(p >
m maxpi Ps V) == - -fo -o f(p1:P2. P2..... Pm V).
The configuration of code generation tasks sig- nificantly impacts the Self- ColiiConns measure- ment since different programs might yield varying outputs for given set of test cases. This variation can cause simple majority voting schemes to be ineffective in evaluating stability. To address this, we explore two distinct methods for aggregating answers across multiple test cases.
dp2... dpm:
where
S(p1) = ((p,...., Pm)) ph > max Ps:
i=2
m
p: = 11=1-pp Σ
(I) In Equation 1, (p/, P2.... .............................. Pml V) represents the joint probability density function of the Dirich- let distribution conditioned on the counts V. The bounds on the integral for p1 range from 0 to 1. The probability simplex S(p)) is defined for each pl value, such that p max Pt, and the remain- ing ps values sum to - --1 This constraint ensures that we are considering all possible values of pl1 that would maintain its majority status. Here we as- sume, that the number of possible unique answers (m) is known, based on the current set of observa- tions (V). In Analysis ((S 5.3), we further evaluate a CHINESE RESTAURANT PROCESS (CRP) stop- ping criteria, which relaxes this assumption by not requiring the number of possible unique answers (m) to be known in advance.
In the first method, inspired by the approach used in AlphaCode (Li et al.. 2022), we concatenate the outputs for all test cases into a single vector with i elements and apply Self-Consistency across the entire vector. This implies that two programs are considered identical only if their outputs for all t test cases match exactly. However, this simple setup may overestimate the output variance, dif- ferent programs can produce distinct outputs for the set of test cases.
To overcome the limitations of the simple setup, we propose an alternative method that treats test inputs as independent entities and applies Adaptive- Consistency to each test case separately:
P max pi (V)
(3)
Beta Stopping Criteria Since the number of unique answers in the observation set can be large, Equation (1) is computationally expensive to solve. As an approximation, we observe that establishing the majority of p1 over the next largest probability, P2, is sufficient for our purpose.
In this equation, P computed using Equa- tion 1. The claptive-Consistenge method termi- nates the sampling process when the normalized probabilit--eppreseed as the geometric mean of P across all test cases exceeds predefined threshold (e.g.. 0.95).
In this setting, the probability in Equation (3) simplifies a Beta distribution with parameters (vi + 1, 222 + 1), and Equation (1) replaced by Equation (2). This approximation, which assumes a non-informative prior of BETA(1, 1), allows us to efficiently compute the confidence in p1 being the majority, enabling early stopping decisions without incurring substantial computational overhead.
Experiments
We evaluate Adaptive-Consissency using 17 di- verse benchmark datasets and three different lan- guage models. We use prompts by program-aided language models, PAL. (Gao et al., 2022), Self- Consistency (Wang al., 2022b) and CodeT (Chen et al.. 2022).
P2 22 (0
0.5
2 (1-12)) dp2
(2)
Empirically, we show the performance be sim- ilar to Dirichlet stopping criteria but significantly faster (See Section 5.3). Throughout experiments, we refer to this Beta Stopping Criteria as Adaptive- Consistency.
Datasets We evaluate our method on diverse set of reasoning and coding benchmarks, encom- passing 17 datasets across distinct categories: 1. Mathematical Reasoning: We use GSM- 8K (Cobbe et al., 2021), SVAMP (Patel et al.,

---

2021), and ASDIV (Miao et al., 2020) which as- sess 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 multi-hop reasoning and emotional understanding. 3. SYM- BOLIC Reasoning Tasks: We further examine performance on 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 work- ing code given textual problem description. We evaluate on 4 datasets of varying difficulty: HU- MANEVAL (Chen et al., 2021), MBPP (Austin al., 2021), APPS (Hendrycks al., 2021) and CODECONTESTS (Li al., 2022). We refer readers to Appendix A.2 for more details.
and 1000 samples in CODECONTESTS.
The only hyperparameters in Adaptive-Consistency are those related to param- eters in stopping criteria (Cihresh). We use high By us-
Hyperparameters
Cthresh = 0.95 for ing high threshold, we aim maintain high ac- curacy and prevent the algorithm from stopping too early. For other Stopping Criteria, we tune pa- rameters on the training set of GSM-8K, and use the same thresholds across all the datasets. The impact of the chosen threshold on the performance of our method is further analyzed in the analysis section ($ 5.1).
Baselines We compare our method against Self- Consistency, which is the current state-of-the-an method. Further, in Section 5.3, we evaluate Adaptive-Consistency against different stopping criteria, such RANDOM stopping and MAJOR- ITY (stopping at majority), ENTROPY, DIRICHLET and CRP.
Models We evaluate our method on three differ- ent language models: 1. GPT-3.5-TURBO:" An RLHF-finetned GPT-3 based model (unreleased number of parameters). 2. VICUNA-13B: (Chi-
Evaluation Metries We evaluate the perfor- mance of our method and the baselines using two metrics: average generations sampled from the LLMs, and overall reasoning accuracy. Our results show that
ang ct al., 2023) an open-source transformer model fine-tuned on instruction-follovin dataset (Taori et al., 2023) from the base Llama series (Touvron al., 2023). 3. CODE-DAVINCI-0022 A GPT- 3-based publicly available model (Brown et al., 2020) which part of the Codex series (Chen et al., 2021) and has 175 billion parameters.
achieves similar performance to Self-Consistency while often reduc- ing sample budget considerably.
4.1 Results
Table 1 presents the main results, and is divided into two parts showing results across different task categories (top sub-table) and on various language models (bottom sub-table). We focus on the poten- tial tradeoff between efficiency and accuracy.
Prompting and Sampling We use similar prompts as in PAL (Gao et al., 2022) and CHAIN OF THOUGHT (Wei et al., 2022). Specifically, for mathematical reasoning and DATE UNDERSTAND- ING tasks, we use prompts from PAL. For other commonsense and SYMBOLIC reasoning tasks, we use COT (Wei et al., 2022).
Results Across Task Categories Our experimen- tal results demonstrate the significant efficiency gains achieved by Adaptive-Consistency across dif- ferent task categories 3.3x times fewer samples in mathematical tasks with a 0.1 % accuracy drop, 2.9x times fewer samples in commonsense tasks with a 0.2% accuracy drop, 3.8x times fewer sam- ples in symbolic reasoning tasks maintaining accu- racy, and 2.4x times fewer samples in coding tasks while improving accuracy by 0.4%. These findings confirm the effectiveness of adaptive-Consistenne in identifying the majority element early, highlight- ing its potential across various applications, includ- ing reasoning and coding.
For sampling, we follow the scheme suggested in Wang et al. (2022b). Specifically, we use tem- perature of 0.7 for sampling and limit the number of generations to a maximum of 40. For coding tasks, we follow the exact procedure as used in CodeT (Chen et al., 2022), with 50 samples for APPS, 100 samples for HUMANEVAL. and MBPP
ptttps://openaa.com/ wwt..//w//ccatttttooeooooooooo
'We have access to Codex models through OpenAl's re- searcher access program. Note that we only need access to the model outputs for this work, and we have released all outputs in the accompanying repository for reproducibility.

---

Accuracy
Num. Generations
A
Category
Self- Self-Consistency
Adasive--onniiseeccy Self-Consistency Aduptive-Consistengy Num. Gen.
Acc.
MATH
73.2
73.1
40
13.8
3.3x
-0.1
COMMONSENSE
66.0
65.8
40
15.8
2.9
-0.2
SYMBOLIC Reasoning
72.8
72.8
40
13.1
3.8x
+0.0
CODE GENERATION
35,2
35.6
312.5
173.6
2,4x
+0.4
Accuracy
Num. Generations
Model
Self-Consiseency Adussiv-- Self-Consistency Adaptive-Consisteney Num. Gen.
GPT-3.5-TURRO
76.4
76.2
40
10.0
4.4x
-0.2
VICUNA-
54.0
54.1
40
21.7
1,9x
+0.0
CODE-DAVINCI-002
69.7
69.8
104.1
49.4
3.4x
+0.0
Table Main results:
Conptive-Conssteenyyy achieves significant reduction the number of generations, with negligible impact on accuracy. The A columns display reductions in generations (Num. Gen.) and accuracy (Acc.) between Self-Consist and Adaptive-Consistency Detailed results are in Table
Results Across Language Models Examining the results across different language models, find that Adastive-Connistenneyy model-agnostic, and consistently reduces the number of generations with minimal to no impact on accuracy. Adaptive- Consistency consistently reduces the number of generations required, with reductions of 4.4x for GPT-3.5-TURBO. 1.9x for VICUNA-13B, and 3.4x for CODE-DAVINCI-O09) highlighting its cost-effective nature and adaptability different scales of models. Moreover, the minimal accuracy differences and slight improvements showcase the practical utility of Adaptive Consistency, empha- sizing its diverse applicability and model-agnostic characteristics.
displays the model's accuracy, while the right y- axis shows the average number of samples drawn. The plot (for GSM-8K) shows the expected be- havior of two curves: the blue curve (accuracy) increases gradually and then plateaus, while the red curve (average number of samples) initially increases linearly and then climbs more steeply. The plateau in accuracy signifies that the model has reached its maximum achievable accuracy, and further sampling will not improve it much. Meanwhile, the red curve's climbing rate indi- cates that the model requires more samples to meet an increasingly stringent confidence threshold for stopping, highlighting the trade-off between ac- curacy and cost efficiency. We refer readers to Appendix C.4 for more results.
5 Analysis
5.2 Adaptive-Consistenn vs. Self-Consistency For Equal Average Sample Costs
5.1 Effect of Confidence Threshold in Adasstve
Section 4.1 previously demonstrated that Adaptive- Consistency achieves comparable performance to Self-Consistency using fewer samples. In this section. our primary objective is to com- pare the performance of Adaptive-Conssittnng to Self-Consistency across various sampling bud- gets. For each fixed sampling budget k, we con- trast the performances and Self-Consistencyy where Self-Consistency dis- tributes sample budget uniformly to each question, Conniste- uses nonuniform allocation, rather than consistently across all instances.
The confidence threshold, Cttresh, is a crucial hy- perparameter for Adaptive-Consistenoy, as it deter- mines when to stop sampling based on the desired level of confidence in the majority element. While we set the threshold to stringent value of 0.95 for all experiments, in this section, we analyze the impact of varying Cthresh from 0.5 to 1 to under- stand the trade-offs between model accuracy and cost-efficiency.
Adaptive-Consistenge
In Figure 2, present visualization that amines the relationship between the confidence threshold, Cthresh, and the performance of adap- tive consistency terms of both accuracy and cost- efficiency. The x-axis represents the confidence threshold, varying from 0.5 to 1. The left y-axis
We evaluate Adaptive-Consistenccy using vary- ing thresholds, with each threshold producing a distinct point (#samples, performance) on the cost- quality curve. For every specific sample count

---

02-
BETA
ENTROPY
DIRICHLET
CRP
Time (ms)
0.03
0.03
101.3
94.6
Table 2: Time comparison of different stopping criterias, when evaluated on GSM-8K and DATE UNDERSTAND- ING datasets. All stopping criterias are significantly faster than LLM inference, with BETA being 4 orders of magnitude faster than other variants.
76
Accurec
24
Accuracy Average Samples
stopping criterion used in Adaptive- Adaptive-Consistennyy Consistemcy, based on Equation (2), 5) DIRICHLET: The stop- ping criterion, based on Equation (1), 6) CHINESE RESTAURANT PROCESS (CRP): Unlike DIRICH- LET, CRP makes no assumption on the number of possible unique answers. Based on the available observations, we first model the concentration pa- rameter (a), denoting the probability of getting a new answer, then perform Monte Carlo simulations to obtain stability of the current majority (see Ap- pendix C.3 for more details).
66
0.5
0.8
0.9
Confidence Threshold
Figure 2: Impact of Confidence Threshold (hrres)) on Adassive-Consistenny for GSM-8K: As Cthresh varies, the accuracy of Slaptive-Consistene increases gradu- ally, eventually plateauing. Initially, the average number of generations also increases gradually but then sharply climbs, reflecting the accuracy-confidence trade-off.
(#samples) generated by Ddaative-Conssitennyy we subsequently run Self-Consistency to obtain its cor- responding performance. The relationship between the two methods across these data points is visual- ized in Figure 3 which provides a visual compar- ison of the performance of Adaptive-Consistencyy and Self-Consistency on GSM-8K. Adaptive- Consistency outperforms Self-Consistency in ac- curacy across all average sample costs. For exam- ple, when the average sample cost is 10, Adaptive- Consistency achieves approximately 3% higher ac- curacy GSM-8K. Similar results hold on other datasets; see Appendix C. for full results.
The parameters for all these methods are tuned, as discussed in Section 4. Figure 4 compares BETA to ENTROPY and MAJORITY over a range of ex- pected sampling costs. BETA consistently achieves higher accuracy than both for the same sampling cost. Further, we find RANDOM be the least effective method as expected, whereas MAJORITY almost consistently underperforms both BETA and ENTROPY. While DIRICHLET and CRP have a similar performance to BETA, they are both about four orders of magnitude slower than BETA due to the expensive multivariate integral calculation. Nonetheless, despite being run single epu core, even DIRICHLET and CRP have negligible time and cost compared LLM inference. The exact tim- ings are presented in Table 2. The detailed results are presented in Appendix C.2, Table 7.
The success of tributed to the fact that it varies the number of samples based on the complexity of the instance. using more samples where clear consensus is hard to reach and fewer where answers are consistent. Consequently, Dlaptive-Consisterr achieves im- proved overall performance when controlled for cost budget.
can be at-
In summary, larly effective in two scenarios: trend is evident early in the sampling process, such as in the SVAMP dataset where it achieves com- parable accuracy to Self- Self-Consistency using fewer than 5 samples on average per input; and (ii) for tasks with a limited set of potential answers, such as the BOOLEAN EXPRESSIONS dataset where reduces the computational budget by 7.9 times without any loss in accuracy.
Chassive-Consisteney is particu-
(i) when majority
5.3 Evaluation of Different Stopping Functions
Slaptive-Consistens allows a flexible choice of stopping criteria, based on intended objective and requirements. Here, we evaluate six different func- tions: 1) RANDOM:
randomly stopping with prob- ability p, 2) MAJORITY: stopping after the most common answer has a majority above a threshold,
Related Work
3) ENTROPY: stopping after the entropy of an- swers is below a threshold, 4) BETA: The main
Crowdsoureing and Adaptive Consistency finds inspiration in tech-

---

accuracy. In line with our vision, (Parameswaran et al., 2023) have recently proposed declarative prompt engineering, viewing LLMs like crowd gies.
(10
workers and leveraging multiple prompting strate-
Accuraty
76
74
Architectures for adaptive computation A re- lated body of work on adaptive computation aims to preempt computation based on intermediate rep- resentations (Liu et al., 2020; Zhou et al., 2020; Schuster et al., 2021; Geng et al., 2021; Xin et al., 2020). Schuster et al. (2022) present CLAM, lan- guage model that performs language generation adaptively. Hou et al. (2020) propose Dynamic Bert, which can adapt the depth and width of the transformer to satisfy various computational con- straints. Xing et al. (2020) propose a dynamic deep neural network with an early-exit strategy embed- ded for enhancing the quality of compressed im- ages. Another direction of work focuses pruning model weights or training sparse weights (Fan al., 2019; Jayakumar et al., 2021) to reduce training and inference time. In contrast to these methods, our approach completely obviates making any ar- chitectural modifications.
70
60
Adaptive Consistency
SelfConssstancy
5
10
15
20
25
30
35
40
Sampic Budget
Figure 3: Comparison of Conssive with Self- Consisonss on various average sampling costs on 2 datasets: GSM-8K and DATE UNDERSTANDING. Adaptive-Conee Conpsise-C is able consistently beat Self- Consistency, especially when the sampling cost is low.
Accuracy vs Number Conerattons CSM BK
Data
0.50
0.78
Inference-time adaptive computation These methods focus on adaptive computation at infer- ence time without making architectural modifica- tions to the models. Schwarzschild et al. (2021b,a) focus on three different generalization tasks. They observe that increasing the number of test iterations (which corresponds to the network depth in their setting) helps the models in generalizing better to difficult problems. Madaan and Yang (2022) lever- age two different networks trained for the same task, larger variant (slow) and a smaller variant (fast). The switch from fast to slow happens during inference, based on the complexity of generation at the current step. Xue et al. (2023) train language models to adaptively read tokens from a tape bank for each input. Different from these works, our fo- cus is tasks where the multiple samples are drawn from a model (vs. iteratively solving a task, which is a focus of these works). Additionally, recent works such as (Madaan et al., 2023a; Chen et al., 2023) have propsed to adaptively selecting models of varying sizes based on verification signals de- rived from the output of the smaller model. Our methods, however, distinguish themselves by not necessitating the use of an additional verifier, and without the need of multiple models.
12 Mumbber Generations
20
1.1
1.5
3.0
Figure 4: Comparison of BETA, ENTROPY and MA- JORITY stopping criterias. BETA consistently beats EN- TROPY and MAJORITY in terms of accuracy for the same sampling cost.
niques from crowdsourcing (Lin et al., 2012; Dai et al., 2013; Weld et al., 2015; Bragg et al., 2016). Traditionally, crowdsourcing involves aggregating diverse human judgments, which presents chal- lenges in managing resource iotoocationnnoowiii when to query additional contributors or stop based on the consistency of responses (Doan et al., 2011; Quinn and Bederson, 2011). Farly research con- centrated on probabilistic models estimating the 'true' answer and worker reliability (Dawid and Skene, 1979; Whitehill et al., 2009), later consider- ing factors like worker expertise, task complexity, and answer quality (Raykar et al., 2010; Welinder et al., 2010). However, rather than addressing these issues with multiple human contributors, Adaptive- Consistency is tailored specifically for LLMs, op- timizing for computational efficiency and output

---

Adaptive Sampling in Training and Active Learning Another line of work focuses on importance-based sampling of input instances dur- ing training (Bengio and Senecal, 2008; Prabhu et al., 2019; Berger et al., 2017). In contrast to the aforementioned methods, our approach centers on adaptively sampling multiple outputs per input instance during the inference phase, without so- liciting additional labels. Our method is crafted efficiently obtain reliable predictions from pre- trained language models by adaptively sampling their outputs, distinguishing it from both adaptive sampling in training and active learningg which focus on the training phase.
also partially supported by the CSE Research Ac- celeration Fund of IIT Delhi Aman is supported by a contract from the DARPA KAIROS pro- gram under agreement number FA8750-19 1977000-9---200) The U.S. Government authorized to reproduce and distributc reprints for Governmental purposes, notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the U.S. Govermment.
Limitations
7 Conclusion and Future Work
Despite the promising results of our proposed Adaptive-Consistency method, it bears several lim- itations and scopes for future improvement.
This paper presented Sraptive-Consistency a cost- efficient and model-agnostic technique for improv- ing the correctness of output from large language models (LLMs) using dynamic sampling. Our ap- proach builds upon the Self-Consistency method and introduces a lightweight stopping criterion that allows for aduptive 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 to 4 times, while maintaining comparable accuracy, with average drop of less than 0.1%.
Stopping criterion sensitivity: The current stopping criterion, based on the majority el- ement's stability in the sample set, may not always indicate sample agreement optimally. Instances may arise where the majority element lacks stability, yet the criterion triggers, poten- tially leading to suboptimal decisions. Future work could explore more robust or alternative stopping criteria.
Generalizability: The effectiveness of method may vary across tasks or models, de- spite testing on a diverse range of 17 datasets and three different LLMs of contrastive scale. Notably, dlaptive-Consistems is anticipated to fail where Self-Consistency fails.
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 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 wtse--e--stee.piie
Task-specific adaptations: The aask-agnostic nature of Adaptive- -oppiive-Consstteceyy might limit its performance on tasks that could benefit from task-specific adaptations. Specialized versions of Adaptive-Consisstnccy for specific tasks or domains could potentially enhance per- formance. We have initiated this by experi- menting on CODE GENERATION dataset, but to other do-
extending Adaptive-Consisen mains may not be as straightffrward.
Acknowledgements
Reliance on the pretrained LLM: Our method depends on the pretrained LLM for gen- erating multiple samples. Consequently, any limitations biases in the LLM would per- sist in the Adaptive-Consistencyy Addressing these issues might require improvements in the LLM training process itself or the integration of external knowledge sources.
We thank the anonymous reviewers for their useful comments and suggestions. Mausam is supported by grants from Microsoft, Google and Verisk, Wipro CoE on generative AI, Yardi School of Al travel funds, and the Jai Gupta chair fellowship by ITT Delhi. We thank the ITT Delhi HPC facility for its computational resources. This work was

---

References
Carr, Jan Leike, Joshua Achiam. Vedant Misra, Evan Morikawa, Alec Radford, Matthew M. Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, llya Sutskever, and Wojciech Zaremba. 2021. Evaluat- ing large language models trained code. ArXiv. 0hs/2107.0333.
Daman Arora, Himanshu Gaurav Singh, and Mausam. 2023. Have Ilms advanced enough? challenging problem solving benchmark for large language mod- els. In Conference on Empirical Methods in Natural Language Processing (EMNLP).
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe V. Le, and Charles Sutton. 2021. Program synthesis with large language models. ArXiv, abs/2108.07732.
Wei-Linn Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng. Siyuan Zhuang. Yonghao Zhuang. Joseph E. Gonzalez, lon Stoica, and Eric P. Xing. 2023. Vicuna: An open- source chatbot impressing gpt-4 with 90%* chatgpt quality.
Yoshua Bengio and Jean-Sébastien Senecal. 2008. Adaptive importance sampling to accelerate train- ing of a neural probabilistic language model. IEEE Transactions on Neural Networks, 19:713-722.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. ArXiv, abs/2110.14168.
Lorenz Berger, Eoin R. Hyde. M. Jorge Cardoso, and Sébastien Ourselin. 2017. An adaptive sam- pling scheme to efficiently train fully convolutional networks for semantic segmentation. In Annual Conference on Medical Image Understanding and Analysis.
Peng Dai, C. H. Lin, Mausam, and Daniel S. Weld. 2013. Pomdp-based control of workflows for crowdsoure- ing. Artif. Intell., 202:52-88 -5.
A. Philip Dawid and Allan Skene. 1979. Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of The Royal Statistical Society Series C-applied Statistics, 28:20-28
Jonathan Bragg. Mausam, and Daniel S. Weld. 2016. Optimal testing for crowd workers. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. Singapore, May 9-13, 2016, pages 966-974. ACM.
AnHai Doan, Raghu Ramakrishnan, and Alon Y. Halevy. 201 Crowdsoureing systems on the world-wide web. Communications of the ACM. 54:86 - 96.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah. Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Fric Sigler, Mateusz: Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners.
Angela Fan, Edouard Grave, and Armand Joulin. 2019. Reducing transformer depth on demand with struc- tured dropout. ArXiv, abs/1909) 1556.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Gra- ham Neubig. 2022. Pal: Program-aided language models. ArXiv, abs/2211.10453
Bei Chen, Fengji Zhang, A. Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. 2022. Codet: Code generation with generated tests. ArXiv. 0bs/2207.10397.
Shijie Geng, Peng Gao, Zuohui Fu, and Yongfeng Zhang. 2021. Romebert: Robust training of multi- exit bert. arXiv preprint MoXXx:221110075:
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021. Did aristotle use a laptop? question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346-
Lingjiao Chen, Matei A. Zaharia, and James Y. Zou. 2023. Frugalgpt: How to use large language mod- els while reducing cost and improving performance. ArXiv, hiss23055.0117.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harrison Ed- wards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray. Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Moham- mad Bavarian. Clemens Winter, Philippe Tillet, Fe- lipe Petroski Such, David W. Cummings, Matthias Plappert, Fotios Chantzis. Elizabeth Barnes, Ariel Herbert- Voss, William H. Guss, Alex Nichol, Igor Babuschkin, S. Arun Balaji, Shantanu Jain, Andrew
361.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Xiaodong Song, and Jacob Steinhardt. 2021. Measuring coding challenge competence with apps. ArXiv. .05.9908...
Lu Hou, Zhiqi Huang, Lifeng Shang, Xin Jiang, and Qun Liu. 2020. Dynabert: Dynamic bert with adap- tive width and depth. ArXiv, 044077

---

Siddhant M. Jayakumar, Razvan Pascanu, Jack W. Rae, Simon Osindero, and Erich Elsen. 2021. Top-kast: Top-k always sparse training. ArXiv, abs/2106.03517.
Computational Linguistics, pages 975-984, Online.
Association for Computational Linguistics.
Bhavana Dalvi Mishra, Oyvind Tafjord, and Peter Clark. 2022. Towards teachable reasoning systems: Using dynamic memory of user feedback for continual system improvement.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large Language Models Zero-Shot Reasoners. arXiv
preprint arXiv:2205.11916
Aditya G. Parameswaran, Shreya Shankar, Parth Asawa, Naman Jain, and Yujie Wang. 2023. Revisiting prompt engineering via declarative crowdsourcing. ArXiv, abs/2308.0320 033554.
Aitor Lewkowycz. Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al. 2022. Solving quantitative reasoning problems with language models, arXiv preprint arx:v:2006. 148588
Arkil Patel, S. Bhattamishra, and Navin Goyal, 2021. Are nlp models really able to solve simple math word problems? In North American Chapter of the Association for Computational Linguistics.
Yujia Li, David H. Choi, Junyoung Chung, Nate Kush- man, Julian Schrittwieser, Rémi Leblond, Tom, Ee- cles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de, Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang. Johannes Welbl, Sven Gowal, Alexey, Cherepanov, James Molloy, Daniel Jaymin Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de, Freitas, Koray Kavukcuoglu, and Oriol Vinyals. 2022. Competition-leve code genera- tion with alphacode. Science, 378: 178:1092- - 1097.
Ameya Prabhu, Charles Dognin, and Maneesh Kumar Singh. 2019. Sampling bias deep active clas- sification: An empirical study. In Conference on Empirical Methods in Natural Language Processing.
Alexander J. Quinn and Benjamin B. Bederson. 2011. Human computation: survey and tax- onomy of a growing field. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.
Christopher H. Lin. Mausam, and Daniel S. Weld. 2012. Crowdsourcing control: Moving beyond mul- tiple choice. In Proceedings of the Twenty-Eighth Conference Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, August 14-18, 2012, pages 491-500 AUAI Press.
Vikas Chandrakant Raykar, Shipeng Yu, Linda H. Zhao, Gerardo Hermosillo, Charles Florin, Luca Bogoni, and Linda Moy. 2010. Learning from crowds. Mach. Learn. Res., 11:1297-1322.
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghami, Dara Bahri, Vinh Q Tran, Yi Tay, and Donald Metzler. 2022. Confident adaptive language modeling. arXiv preprint arXiv:2207.0704
Weijie Liu, Peng Zhou, Zhiruo Wang, Zhe Zhao, Haotang Deng, and Qi Ju. 2020. Fastbert: self- distilling bert with adaptive inference time. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguisties, pages 6035-6044.
Tal Schuster, Adam Fisch, Tommi Jaakkola, and Regina Barzilay. 2021. Consistent accelerated inference via confident adaptive transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 4962-4979.
Aman Madaan, Pranjal Aggarwal, Ankit Anand, Sriv- idya Pranavi Potharaju, Swaroop Mishra, Pei Zhou, Aditya Gupta, Dheeraj Rajagopal, Karthik Kappagan- thu, Yiming Yang, Shyam Upadhyay, Mausam, and Manaal Faruqui. 2023a. Automix: Automatically mixing language models.
Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Arpit Bansal, Zeyad Emam, Furong Huang, Micah Gold- blum, and Tom Goldstein. 2021a. Datasets for Study- ing Generalization from Easy to Hard Examples. arXiv: 108.0601 [es]. ArXiv: 2108.06011.
Aman Madaan, Alexander Shypula, Uri Alon, Milad Hashemi, Parthasarathy Ranganathan, Yiming Yang, Graham Neubig, and Amir Yazdanbakhsh. 2023b. Learning performance-inprovingg code edits. arXiv preprint 2722
Avi Schwarzschild, Bitan Borgnia, Arjum Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. 202 Can You Learn an Algo- rithm? Generalizing from Easy to Hard Problems with Recurrent Networks. In Advances in Neural Information Processing Systems, volume 34, pages 6695-6706. Curran Associates, Inc.
Aman Madaan and Yiming Yang. 2022. Flowgen: Fast and slow graph generation. DyNN workshop the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA, 2022.
Rohan Taori, Ishaan Guirajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. 2023. Stanford alpaca: An instruction following followino Ilama model. https:// // gi thub. com/ wtw/ tatsu-labb anford_alpaca.
Shen-yun Miao, Chao-Chun Liang, and Keh-Yih Su. 2020. A diverse corpus for evaluating and developing English math word problem solvers. Proceedings of the 58th Annual Meeting of the Association for

---

Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux. Timothée Lacroix, Baptiste Rozière, Naman Goyal, Fric Hambro, Faisal Azhar, Aur' elien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. Llama: Open and efficient foundation language models. ArXiv, abs/2302.13971.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. 2022a. Rationale- Augmented Ensembles in Language Models. arXiv preprints arXiv:2207.0077:
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Fdd Huai hsin Chi, and Denny Zhou. 2022b. Self- consistency improves chain of thought reasoning in language models. ArXiv, abs/2203.11177
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Lc, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning large language models. ArXiv, abs/2201.11903.
Daniel S Weld, Mausam, Christopher Lin, and Jonathan Bragg. 2015. Artificial intelligence and collective intelligence. Handbook of Collective Intelligence, pages 89-100. MIT Press.
Peter Welinder, Steve Branson, Serge J. Belongie, and Pietro Perona. 2010. The multidimensional wisdom crowds. NIPS.
Beate West. 1992. Hyperparameter estimation in dirich- let process mixture models.
Jacob Whitehill, Paul Ruvolo, Tingfan Wu, Jacob Bergsma, and Javier Movellan. 2009. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In NIPS.
Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy J. Lin. 2020. Deebert: Dynamic early exiting for accelerating bert inference. In Annual Meeting of the Association for Computational I. Linguistics.
Qunliang Xing, Mai Xu, Tianyi Li, and Zhenyu Guan. 2020. Early exit or not: ceoource-ffficiere blind quality enhancement for compressed images. In European Conference on Computer Vision.
Fuzhao Xue, Valerii Likhosherstov, Anurag Amab, Neil Houlsby, Mostafa Dehghani, and Yang You. 2023. Adaptive computation with elastic input sequence. ArXiv, abss/200..1199...
Wangchunshu Zhou Canwen Xu, Tao Ge, Julian McAuley, Xu, and Furu Wei. 2020. Bert loses patience: Fast and robust inference with early exit. Advances in Neural Information Processing Systems, 33:18330-133 18341.

---

A Experimental Setup
Dataset
IN (eee
Answer Format
GSM-8K
1519
Numerical
ASDIV
2096
Numerical
A.1 Hyperparameters
SVAMP
1900
Numertcal
DATE UNDERSTANDING
369
String
The only hyperparameters in Adaptive- Consistency, are those related to parameters in stopping criterias (Cthresh). We use high
SRUFLED
250
MCQ
LOGICAL DEDUCTION
250
MCQ
STRATECYQA
2279
Binary
ROOLBAN EXPRISSIONSS
250
Bistry
250
Rinary
Cihresh 0.95 for Adaptive-Consistennyy By using a high threshold, we aim to maintain high accuracy and prevent the algorithm from stopping too early. For other Stopping Criterias, we tune our parameters on the training set of GSM-8K, and use the same thresholds across all the datasets. The impact of the chosen threshold on the performance of our method is further analyzed in the Analysis Section (5 5.1). We further evaluate all methods on a set of seeds and report the table with standard deviation in Table 5. We use only a single seed for GPT-3,5-TURBO because of the cost associated.
RUIN NAMES
178
MCQ
SALIENT TRANSLATION
250
MCQ
DISAMIGGATION QA
250
MCQ
PENGUINS
146
XEQQ
HUMANEVAL MBPP
164
Python Cude
427
Python Code
APPS
5000
Coding
CODECONTESTS
165
Competitive Coding
Table 3: Dataset Statistics. We evaluate 17 diverse reasoning datasets, having different difficulty, domains, answer types, sizes (N N_tesf).
task that demands the model to deduce the order of a sequence of objects based on a minimal set of conditions. 3.) BOOLEAN EXPRESSIONS boolean expressions task that evaluates whether a language model has learned the rules of deductive reasoning, i.e., formal (zeroth-order) logic asso- ciated with the words "and," "or," "not," etc. 4.) DISA MBIGUATION QA is disambiguation task that necessitates the model to select the person whom the pronoun refers. 5.) PENGUINS describes a table of penguins and requires the model to an- swer questions about the penguins' attributes.
A.2 Benchmarks
We evaluate our method on diverse set of coding and reasoning benchmark datasets, encompassing 17 datasets across four distinct categories:
1. MATHEMATICAL Reasoning: To assess mathematical reasoning capabilities, we utilize the following datasets: GSM-8K (Cobbe et al., 2021), SVAMP (Patel et al., 2021), and ASDIV (Miao et al., 2020). These datasets consist of grade- school-level algebra word problems necessitating arithmetic operations and problem-solving based contextual information.
4. CODE GENERATION Tasks: We further evaluate the performance of method by con- ducting experiments on four diverse standard cod- ing tasks. These tasks encompass a range of pro- gramming challenges, including both basic human- written and crowd-sourced Python tasks found in the 1.) HUMANEVAL (Chen et al., 2021) and 2.) MBPP (Austin et al., 2021) datasets, as well as more challenging competition-level coding tasks from the 3.) APPS (Hendrycks et al., 2021) and 4.) CODECONTESTS (Li et al., 2022) datasets.
2. COMMONSENSE Reasoning Tasks: We evaluate Adaptive-Cone Consistency on four COMMON- SENSE reasoning tasks. 1.) STRATEGY QA (Geva et al., 2021) comprises questions that demand the model to infer a multi-hop strategy with reason- ing steps implicitly embedded in the questions. 2.) DATE UNDERSTANDING entails questions that require the model to deduce dates from natural language descriptions and perform arithmetic oper- ations accordingly. 3.) SALIENT TRANSLATION is a salient translation error detection task that re- quires the model to identify the type of error in a translation. 4.) SNARKS and 5.) RUIN NAMES both focus on emotional understanding tasks.
A.3 Tools and Framework
For qucrying GPT-3.5-TURBO and CODE- DAVINCI-002 models (Chen et al., 2021), we use the api library provided by OpenA1 We use the official code provided for running VICUNA-13B model (Chiang et al., 2023). We run inference on VICUNA-13B models on single A100 gpus. For coding tasks, we use the outputs provided by CodeT (Chen et al., 2022), where models are zero- shot prompted with temperature=0.8, and top_p=
3. SYMBOLIC Reasoning Tasks: We examine the performance of our method six diverse SYM- BOLIC reasoning tasks. 1.) TRACKING SHUF- FLED OBJECTS is tracking task that necessitates the model to infer the final state of a system, given its initial state and a sequence of modifications.
2.) LOGICAL DEDUCTION is a logical deduction
API available at: https:/plaaformooppmi.cco

---

0.95. stopping criteria in Adastive-Consistencyy are fast to run, and we use single-core machine. For numerical integration, we use the Scipy library in Python.
Figure 3 provides visual comparison of the performance of adaptive-Consistenny and Self- Consistency on GSM-8K: Adaptive-Consistenyy outperforms Selfisoonsst in accuracy across all average sample costs. For example, when the average sample cost is 10, Adaptive-Consisten achieves approximately 3% higher accuracy on GSM-8K.
A.4 Test-Case Generation
For CODE GENERATION tasks, we generate test cases in a similar fashion to CodeT (Chen et al., 2022). Specifically, we prompt the model with function description and prompt for generation of assert statements. However, unlike CodeT, limit ourselves only 10 test cases, which are generated 1-2 prompts to LLM, thus adding neglible effect on the code generation itself.
The success of Slaptive-Consistenee can be at- tributed to its adaptive sampling strategy. By vary- ing the number of samples based on the complexity of the unstnnc--using more samples where a clear consensus is hard to reach and fewer where an- man-
swers are AeaissttttAAappti---Coniiii ages to secure improved overall performance even when the average sample cost matches that of Self- Consistency.
Dataset Statistics are presented in Table 3.
B Results
We present the complete results with standard de- viation in Table 5. For CODE GENERATION tasks, results are presented in Table 4
C.2 Stopping Criterias
This section follows from the main discussion Section 5.3. We evaluate different stopping cri- terias for claptive-Consistennyy We evaluate 6 different functions:
Further in Table we show that improvements by Adapiiv-Conssisenncy are statistically significant across all datasets. We perform sample t-test on 3 random seeds. While p-value of number of gen- erations is much less than 0.05 (average: 1.5e-3), indicating that our method is significantly more ef- ficient, the p-value of accuracy much larger than 0.05 (average: 0.50), indicating that the slight accu- racy difference between baseline and our method is statistically insignificant.
1. RANDOM: randomly stopping with a proba- bility p. 2.)
2. MAJORITY: stopping after the most common answer has majority above threshold,
3. ENTROPY: stopping after the entropy of an- swers is below threshold,
Analysis
4. BETA: The main stopping criteria used in based the Equa-
C.1 Adaptive-Consistenyy vs. Self-Consistency For Equal Average Sample Costs
tion (2),
5. DIRICHLET: The stopping criteria, based on Equation (1).
In Section 5.2, we demonstrate that Adaptive- Consistency achieve better accuracy over Self- Consistency when both are operating
CHINESE RESTAURANT PROCESS (CRP): The stopping criteria, which models proba- bility as chinese restaurant process making no assumption on possible number of unique answers.
pected sample cost, Figure 5 we show the com- plete results.
Section 4.1 previously demonstrated that achieves comparable per- formance to Self-Consistency using fewer sam- ples. In this section, we consider scenario where Adassive and Self-Consistency operate with the same average number of sam- ples. For each fixed sampling budget k of Self-Consistencyy we contrast the performance of Slaptive-Consistenge and Celf-Consistency, where uses k samples on average, rather than consistently across all instances.
For comparison, we tune the Cthresh in each case on the training set of GSM-8K dataset. Results are presented in Table 7. RANDOM and MAJORITY inferior BETA across all datasets and models. Further, while DIRICHLET and CRP are almost sim- ilar to BETA, they are relatively very slow. While Although, from Table 7, ENTROPY looks appears to be on par with BETA, in Figure 6, we show BETA

---

Self-Consistency
Adaptive-Consistnnyy
A
Model
Avg. Gen.
Accuracy
Avg. Gen.
Accuracy
Gen. Reduc.
Acc. Dift.
CODE-DAVINCI-002
100
61.4
23.6
63.4
4.3x
+2.0
HUMANEVAL
INCODER-6B
100
19.5
51.2
20.1
2.0x
+0.6
CODEGEN-
100
54.7
36.0
1.8x
ODDE-DAVINCI-002
100
64.4
36.3
63.9
2.8x
MBPP
INCODER-6R
100
30.7
53.8
30.9
1.9x
+0.2
CODEGEN-168
100
49.6
57.8
50.4
1.7x
+0.8
APPS
CODE-DAVINCI-002
|
50
11.9
44.4
11.9
1.1x
0.0
CODECONTESTS
CODE-DAVINCI-002
1000
3.0
590.2
3.0
1.6x
0.0
Table Comparison of table presents the accuracy of Self-Consistency, the average number of generations (Avg. Gen.) for Adaptive- Consistency, and the accuracy of The A columns display the reduction in generations (Gen. Reduc.) and the difference in accuracy (Ace. Diff.) between Self-Cons Ceff-Consistency and use 50, while HUMANEVAL and MBPP use 100 generations each.
with Self-Consistence on diverse code generation datasets. The
Self-Consistency always draws a fixed number of samples.
For CODECONTESTS, Self- Seff-Consistency uses 1000, APPS
beats ENTROPY given the same expected sampling cost.
ing to existing cluster is directly proportional to the size of the cluster, and is given by:
Finally, BETA has additional key advantages: BETA incorporates a measure uncertainty, which makes it more robust to variations in data order, mitigates the influence of noise, and offers a quan- titative measure of confidence in the majority out- come. Consider an extreme case where the first generated solutions are identical. The major- ity voting strategy would instantly halt the process. potentially missing out on better solutions. In con- trast, BETA will keep sampling as the confidence for stopping has not yet reached.
P(e)
74
(4)
71 +
whereas the probability that new unseen answer will form new cluster is given by:
P(Cnow)
(5)
T. + or
where is the concentration parameter, which pa- rameterizes the probability of generating new answer.
Our goal is to calculate the probability that the current majority cluster in observations will remain the same even with more generations. The first task is to estimate the concentration parameter a. We use the approximation proposed by (West, 1992) to model the as
C.3 Chinese Restaurant Process
the DIRICHLET stopping criteria, we assume that the number of unique answers that can be gener- ated by the LLM is known in advance (and equal to the number of unique answers in the current obser- vation set). However, this assumption may not hold for datasets such GSM-8K, where numerical swers expected. The CHINESE RESTAURANT PROCESS (CRP) is generalization of the DIRICH- LET process that addresses this limitation by not making any assumption on the number of unique answers.
p(a(k,n) G(a 1,b + log(n)), (6)
where is the number of unique answers (clusters) in the current observation, n. is the total number of answers, and b are priors and both set equal to I, and is Euler's 's constant and G'aaa + k 1, + 7 (n)((()) denotes the probability density function of the Gamma distribution with shape parameter 1: 1 and rate parameter + We sample a multiple times (100), and for each sample, we run Monte-Cate Simulation (1000 sim- ulations) based on the CRP probability modeling.
In CRP, consider list of same answers cluster, denoted by c; where is the index of the cluster. Let n; be the number of elements cluster Ci and n be the total number of elements across all clusters. The probability of new answer belong-

---

Each simulation starts from from current of ob- servations, and performed till 40 generations are sampled. The probability that the current majority cluster remains the majority is then given by:
Rule,
P 0) P(O p) P(p) P(O)
Here P(O) is normalizing constant and can be omitted for computation. From Assumption 1, since i sampled from uniform distribution,
No NMCS
P(majority) NMS
Σ
Σ
7(majority )
m
P(D)
II dp
(7) where No is the number of times we sample NMCS is the number of Monte-Carle Simulations, and ( is indicator function that equals if the current majority remains the ma- jority after 40 generations, and otherwise.
Thus conditional joint probability distribution of p given O can be written as:
P(p 0) -Di((11 U2 ...... Um + 1)
C.4 Effect of Confidence Threshold Adassive-Consisteney
dpmdpm ... dp2
(8)
Now integrate the above equation over subset of (m 1)-simplex, such that pl max (2 Pt. This gives us the equation:
We follow the discussion in Section 5.1, and present complete results on all datasets for CODE-DAVIT 002.
D Derivation of DIRICHLET stopping criteria
P(p > max pi
O)
- - (swi)
Consider for a given input (/), the model can generate one of m distinct answers A := "m..aam..mm.. Define the probability of generat- ing answer given input p; ;= P(a; I). Now, consider observation set (O) with counts of each of a; vis such that Σ U/ n. Now, with- out loss of generality, consider P1 max Pi- Now, based on Equation (3), we need to find the probability:
PΦ1
dp2 ... dpm dp
where
S(r1) = (12.....PP)) |r1 >
max Pi:
m
x=2
= 1- p/}.
(9)
P(p1
m max pa O) 1=2
We note that the integration has closed-form solution, and we use numerical approximation to compute the above integral.
However, here the p.s are latent variables, and only O is available to us. We next make the follow- ing
Defining region of integration: S(p() Next, for computation of Equation (9), we need to pre- cisely calculate the limits of each integration such that they represent the region S(p(). We do so by noting the following constraints on pt: 1.) The pi = is valid V2 < S m, 2.) Given {pm Pm- PPtt1..Pit Pi+1 are fixed and in region S(p(). Pi < not allowed, 3.) Since P1 > max Pj. so max]" as as clse the p. will lie outside the (m 1)-simplex, which is in- Vind. The first condition makes the lower limit for each integration 0, and the minimum of condition and condition gives the upper bound (limit) on each of the integrations.
The vector F = {p1,P2... ... Pm is sampled from uniform distribution over (m 1)- simplex.
Assumption 1:
Thus, P1 mー Ps. Since the observation set
follows multinomial distribution with parameters p. conditional joint probability distribution of O given ş can be written as:
1 1-Em Ei as else pi 2 which is
Pi < <1
ビ}=i+1 <1-
n!!
m
P(O p)
p
Dir(11 +1, 222 +1
(v.))
where Dir represents the dirichlet distribution
with iy + 1, as its parameters. Applying Baye's

---

BETA stopping criteria Due to m dimen- sions integrations involved. with m often getting larger than 10, computing Equation (9) is not ef- ficient. Instead, we observe that establishing the majority of P1 over the next largest probability, P2, is sufficient for our purpose. Then, pdf simplifies to BETA distribution with parameters U1 + 1, + 1. and Equation (9) simplifies to:
P2
(1 - p2
(10)
We use Scipy library in Python numerically com- pute the above equation.

---

Self-Consistency
Adaptive
A
Accuracy
Avg. Gen.
Accuracy
Gen. Redue.
Acc. Diff.
VICUNA-13R
31.6
26.8:
31.5
1.4x
-0.1
GSM-8K
CODE-DAVINCI-002
81.1 (g
13.
81.0
2.9x
GPT-3.5-TURBO
82.7
9.2
82.7
4.3x
0.0
VICUNA-13B
63.0
18.8
(2.8
2.1x
0.2
SVAMP
CODE-DAVINCI-002
85.1 (50.3)
9.5 (29.))
85.0
4.2x
00.1
GPT-3.5-TURBO
85.1
9.5
85.0
4.2x
00.1
VICUNA-13B
64.0.
16.5/1900
64.0
2.4x
ASDIV
CODE-DAVINCI-002
(00.2)
10.0,co.m
(3.2
4.0%
0.0
GPT-3.5-TURBO
83.0
10.0
83.0
4.0x
0.0
VICUNA-13B
(9.8
17.3 po00
60.2
2.3x
UNDERSTANDING
KODE-DAVINCI-ONI
(0.3
10.7
79.5
3,7x
-0.8
GPT-3.5-TUURO
77.5
9.1
77.0
4.4x
0.5
VICUNA-13B
31.8
20.3 (00.))
32.0
2.0x
40,2
TRACKING SHUFFLED OBJECTS
CODE-DAVINCI-002
77.2 (e1.5)
9.7 (29.))
(7.1
4.1x
0.1
GPT-3.5-TURBO
85.2
6.2
85.6
6.4x
+0.4
VICUNA-13B
51.2
18.1 (10.)
51.4 (1.4.00.
2.2x
+0.2
LOGICAL DEDUCTION
CODE-DAWINCI-002
89.4.1..a
8.5
89.4
4.7x
0.0
GPT-3.5-TURBO
86.8
7.5
86.8
5.3x
0.0
VICUNA-13B
65.8
16.3 Loun
65.8 (.08)
2.5x
0.0
STRATEGYQA
CODE-DAWINCI-002
79.0.1a.0
11.9
78.8
3.4x
002
GPT-3.5-TURBO
68.1
11.8
67.9
3.4x
0.2
VICUNA-13B
79.2 (9:.0
(6.2
78.4
2.5x
0.8
BOOLEAN EXPRESSIONS
CODE-DAVINCI-002
94.5
6.6
94.5
6.0%
0.0
GPT-3.5-TURBO
93.2
5.0
92.8
7.9x
0.4
VICUNA-13B
73.2
23.2, 1omm
13.6:
1.7x
+0.4
SNARKS
CODE-DAVINCI-002
74.0.11.0
12.7/1944
14.0
3.1x
0.0
GPT-3.5-TURBO
65.7
8.8
65.2
4.5x
0.6
VICUNA-13B
43.6
33.8
43.6
1.2x
0.0
RUIN NAMES
CODE-DAVINCI-002
78.0.
17.2,
18.0
2,3x
0.0
GPT-3.5-TURBO
74.8
13.1
74.0
3.1x
0.8
VICUNA-133B
28.9.22-0
28.7
28.7(ax))
1.2x
0.3
SALIENT TRANSLATION
CODE-DAVINCI-002
64.3
11.8
64.3
3.4x
0.0
GPT-3.5-TURBO
11.1
56.8
3,6x
VICUNA-13B
63.7
22.8
63.5
1.8x
00.
DISAMBIGUATION QA
CODE-DWVINCI-002
74.9
13.5
75.1
3.0x
+0.1
GPT-3.5-TURBO
13,9
62.5
2.9x
0.0
VICUNA-13B
46.8
22.9
47.3
1.7x
+0.5
PENGUINS
CODE-DAVINCI-QU2
83.8
11.0:250)
84.0
3.6x
GPT-3.5-TURBO
71.9
14.2
71.9
2.8x
0.0
Average
70.3
14.1
70.2
3.2x
-0.07
Table 5: Comparison of Adaptive-Consiitteme with Self-Consistency on 17 diverse coding & reasoning datasets. Self-Consistency always draws 40 samples. The table shows accuracy, average generations (Avg. Gen.). The A columns display reductions in generations (Gen. Reduc.) and accuracy (Acc. Diff.) between Colf-Consistency and adaptive-Consistene Adaptive-Consister achieves 3.2x reduction in sample budget (Gen. Reduc.) with minimal average accuracy drop of 0.07% (Acc. Diff.).

---

Dataset
Model
P-Value (Accuracy)
P- P-Value (Num Gens)
GSM-8K
VICUNA-13B
0.5
0.0056
GSM-8K
CODE-DAVINCI-002
0.42
2.09E-06
SVAMP
VICUNA-13B
0.07
3.47E-06
VAMP
CODE-DAVINCI-OUS
0.42
7.40E-06
ASDIV
VICUNA-13B
0.0005
ASDIV
0.0023
DATE UNDERSTANDING
VICUNA-13B
0.057
7.68E-05
DATE UNDERSTANDING
RODE-DAVINCI 002
0.04
4.63E-05
TRACKING SHUFFLED OBJECTS
VICUNA-13B
0.5
0.00002
TRACKING SHUFFLED OBJECTS
CODE-DAVIINC-002
0.67
9.88E-06
LOGICAL DEDUCTION
VICUNA-13B
0.5
0.0007
LOGICAL DEDUCTION
CODE-DAVINCC-002
0.0016
STRATEGYQA
VICUNA-13B
0.90
1.16E-05
STRATEGYQA
CODE-DAVINCI-002
0.24
0.0005
BOOLEAN EXPRESSIONS
VICUNA-13B
0.32
8.52E-05
BOOLEAN EXPRESSIONS
4.98E-00
SNARKS
VICUNA-
0.18
0.0007
SNARKS
KODE-DAVINCI-00>
0.0001
RUIN NAMES
VICUNA-
0.0049
RUIN NAMES
SADE-DAVINCI-00S
8.72E-06
SALIENT TRANSLATION
VICUNA-
0.18
0.021 1
SALIENT TRANSLATION
CODE-DAVINCIE DAVINCI--00
0,0001
DISAMBIGUATION QA
VICUNA-
0.53
0.0015
DISAMBIGUATION QA
CODE DAVINCI-002
0.42
0,0002
PENGUINS
VICUNA-
0.18
0.0009
PENGUINS
CODE DAVINCI
0.42
7.79E-05
Average
0.503
0.0002
Table 6: P-values using 2 sample t-test over 3 seeds on multiple datasets and models. The p-value for 'number of generations' is significantly less than 0.05 (average: 1.5e-3), confirming our method's efficiency, while the p- p-value for accuracy is much larger than 0.05 (average: 0.50), indicating that the slight accuracy difference is statistically insignificant.

---

234 $121
78
11
(a) GSM-8K
(h) ASDIV
(c) SVAMP
270 magg
(d) DATE UNDERSTANDING
(c) TRACKING SHUFFLED ORJECTS
(1) LOGICAL DEDUCTION
523 100
SeBCCrnarraccy
79
15
gg) STRATEGYQA
(h) BOOLEAN EXPRESSIONS
(i) SNARKS
200
( RUIN NAMES
SALIENT TRANSLATION DISAMBIGUATION QA
(m) PENGUINS
Figure 5: Comparison of alaptive-Consistens with Self-Consistency various average sampling costs. Adaptive- Consistency is able to consistently beat Coff-Consistency, especially when the sampling cost is low. Moreover. Covrash 0.95 is good indication of saturation in accuracy indicating the value works out-of-box for most configurations considered.

---

Accuracy Number of Generations GSM-9K
Accuraty Number Generations
Entropy Ma,ority
Entropy
Majoriyy
0.78
Acuretyy
Accuraty
0.77
0.75
18
16
(a) GSM-8K
(b) STRATEGYQA
Figure 6: Comparison of BETA, MAJORITY and ENTROPY stopping criterias. In the two representative datasets, BETA consistently beats ENTROPY and MAJORITY for the same sampling cost. This shows in practice BETA performs better than both for the desirable range of accuracy and sampling cost.
Surtgg:
Accracy
Metrgg:
Meragg
Accray
Aucrac
Atrege
Ascerac
Strrage
Ascuray
29.3
317
CoDP 001
11.
200
16:6
2009
15.
41.0
115
S10
153
8L1
11.
85.1
AEDIV
ConY 2000000001000
138
41.
85.1
188
130
80.3
10.1
-35
80.1
SVAMP
COOP noUncc-0033
0033
18.7
8811
DAYE ENDERUAANINNGG
VIDUNA-138
350
663
TRACSING SOLTTEE OIJECTS
VINUNG-33
276
318
15:
300
154
303
3800
353
30.0
31
318
COOB NW 001
11.7
59
1966
383
686
1066
30.2
16.2
664
114
760
72
77.6
345
753
115
75.8
348
160
21.
BOOLEAN EXPRISSIONS
1004
14.5
VINEIN 1:8
WC1
213
212
755
755
121
C00
71.
123
18.4
:23
BUI NAMESS
103
100
211
235
7249
318
7370
331
4127
SALIOV
310
201
14
383
300
353
36.7
254
36.0
391
68.
DSANNEGUATION QA
0003
361
323
1033
351
100
255
752
COOB D0UNNC1-02
133
00.
80
111
038
120
800
228
800
110
155
Table 7: Comparison various Stopping Criterias in Adaptive-Comsisteneyy In general, BETA outperforms RANDOM and MAJORITY decent margins across all datasets. BETA has comparable performance DIRICHLET. but the latter is much slower. ENTROPY performs similarly to BETA but lacks human interpretable stopping rationale.

---

12
12
01.
125
0.7
(a) GSM-8K
(b) ASDIV
(c) SVAMP
185
10
182
Serdin
Serolee
03-
(d) DATE UNDERSTANDING
(c) TRACKING SHUFFLED ORJECTS
(1) LOGICAL DEDUCTION
20.55
0053
922
09.5
Sendie
2235
Samole
05
0.5
2.8
g STRATEGYQA
(h) BOOLEAN EXPRESSIONS
(i) SNARKS
( RUIN NAMES
(k) SALIENT TRANSLATION (1) DISAMBIGUATION QA
(m) PENGUINS
Figure 7: Impact of Confidence Threshold (Cereesh) on Adaptive-Consisenncy: As Cthresh varies, the accuracy of Conpsite-C increases gradually, eventually plateauing. Initially, the average number of generations also increases gradually but then sharply climbs, reflecting the accuracy-confident trade-off. The trend is observed almost consistently across all datasets.


Reviews:
[{"review_id": "UamIZ5nJZX", "reviewer": "Reviewer_HiHf", "summary": "", "questions": "On what kind of tasks or datasets can adaptive consistency reduce more generations while maintaining comparable accuracy? Are there any commonalities in these datasets or tasks?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our paper. We're pleased that you found value in our Adaptive-Consistency approach, appreciating its potential for dynamic sample adjustment in contrast to traditional Self-Consistency methods. We believe that all your inquiries can be addressed during this discussion period. Please see our response below. We would love to address additional questions during the discussion period if anything is unclear.\n\n\n\n---\n\n**On what kind of tasks or datasets can adaptive consistency reduce more generations while maintaining comparable accuracy? Are there any commonalities in these datasets or tasks?**\n\nAdaptive-Consistency is particularly effective in two scenarios:\n\n1. Tasks where a clear majority becomes apparent early during the sampling process. This allows Adaptive-Consistency to recognize dominant trends early on during the sampling process. For instance, as demonstrated in Figure 5c, on the 'Svamp' mathematical reasoning dataset, Adaptive-Consistency attains an accuracy similar to Self-Consistency, while utilizing an average of less than 5 samples per input. \n\n2. Tasks that naturally produce a limited variety of unique answers. In such contexts, Adaptive-Consistency can efficiently deduce the majority due to the constrained answer space. For instance in 'boolean expressions' dataset, Adaptive Consistency reduces budget by 7.9 times, without hurting accuracy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "(1) Interesting Idea: The idea of dynamically adjusting the number of samples is innovative and addresses a significant limitation of existing Self-Consistency techniques. It has wide potential applications across different domains involving large language models.\n\n(2) Efficiency: The claim that Adaptive-Consistency reduces the sample budget by up to 7.9 times is remarkable, and the minimal accuracy drop demonstrates the method's effectiveness and efficiency.\n\n(3) Comprehensive Experiments: The paper's experimental design, covering 17 datasets and three different LLMs, provides broad insights into the method's performance across various scenarios.\n", "reasons_to_reject": "No obvious reason to reject", "questions_to_authors": "On what kind of tasks or datasets can adaptive consistency reduce more generations while maintaining comparable accuracy? Are there any commonalities in these datasets or tasks?", "paper_topic_and_main_contributions": "The paper introduces a new technique named Adaptive-Consistency, which dynamically adjusts the number of samples per question for improving the output of large language models (LLMs). Unlike traditional Self-Consistency methods that generate a constant number of samples, this approach non-uniformly distributes the sample budget according to the agreement level in the samples generated so far. The paper reports experimental results over 17 reasoning and code generation datasets and three LLMs, showcasing substantial improvements in sample budget efficiency with a minimal decrease in accuracy.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0Ex1mg29eE", "reviewer": "Reviewer_tDcp", "summary": "", "questions": "In Section 5.2, how is the average number of samples enforced on Adaptive-Consistency? My (perhaps incorrect) understanding is that AC involves adding a stopping criteria, which does not provide direct control over the average.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper! We were happy to read that you found our method straightforward and well-justified, and that you appreciated our comprehensive experiments demonstrating the method's effectiveness, especially in terms of savings over the \"fixed-budget\" self-consistency.\n\nWe think that all your questions are addressable within this discussion period. Please see our response below. We would love to address additional questions during the discussion period if anything is unclear.\n\n---\n\n**In particular, while Table 1 shows that Adaptive-Consistency achieves comparable performance with fewer samples, it is a little challenging to interpret the results without statistical tests or error bars.**\n\n Page 16-Table 4 shows the error bars calculated by evaluating Adaptive Consistency (our method) on 2 models with 3 different seeds. \\\nFurther, based on your suggestion, we have computed p-values for both accuracy and number of generations over 3 seeds using 2-sample t-test. The p-value for 'number of generations' is significantly less than 0.05 (average: 1.5e-3), confirming our method's efficiency, while the p-value for accuracy is much larger than 0.05 (average: 0.50), indicating that the slight accuracy difference is statistically insignificant. \nWe will include these results with p-values and a detailed discussion in the revised paper. \n| Dataset             | Model   | P-Value (Accuracy) | P-Value (Num Gens) |\n|---------------------|---------|--------------------|--------------------|\n| gsm                 | Vicuna-13B  |                0.5 |     0.0056 |\n| gsm                 | Code-Davinci-002 (175B) |       0.42 |           2.09E-06 |\n| svamp               | Vicuna-13B  |      0.07 |           3.47E-06 |\n| svamp               | Code-Davinci-002 (175B) |       0.42 |           7.40E-06 |\n| asdiv               | Vicuna-13B  |                  1 |    0.0005  |\n| asdiv               | Code-Davinci-002 (175B) |                  1 |     0.0023 |\n| date                | Vicuna-13B  |      0.057 |           7.68E-05 |\n| date                | Code-Davinci-002 (175B) |      0.04   |           4.63E-05 |\n| tracking_three      | Vicuna-13B  |                0.5 |   0.00002  |\n| tracking_three      | Code-Davinci-002 (175B) |       0.67 |           9.88E-06 |\n| logical_three       | Vicuna-13B  |                0.5 |    0.0007  |\n| logical_three       | Code-Davinci-002 (175B) | -                  |     0.0016  |\n| strategy_qa         | Vicuna-13B  |       0.90   |           1.16E-05 |\n| strategy_qa         | Code-Davinci-002 (175B) |       0.24     |     0.0005   |\n| boolean_expressions | Vicuna-13B  |       0.32     |           8.52E-05 |\n| boolean_expressions | Code-Davinci-002 (175B) | -                  |           4.98E-06 |\n| snarks              | Vicuna-13B  |       0.18     |      0.0007  |\n| snarks              | Code-Davinci-002 (175B) |                  1 |    0.0001 |\n| ruin_names          | Vicuna-13B  | -                  |     0.0049   |\n| ruin_names          | Code-Davinci-002 (175B) |                  1 |           8.72E-06 |\n| salient_translation | Vicuna-13B  |       0.18    |      0.0211   |\n| salient_translation | Code-Davinci-002 (175B) |                  1 |    0.0001  |\n| disambiguation      | Vicuna-13B  |       0.53   |     0.0015  |\n| disambiguation      | Code-Davinci-002 (175B) |       0.42    |    0.0002  |\n| penguins            | Vicuna-13B  |       0.18     |    0.0009   |\n| penguins            | Code-Davinci-002 (175B) |       0.42    |           7.79E-05 |\n| average              |             |      0.503    |            0.0002    |  \n\n\n---\n\n**Q:  In Section 5.2, how is the average number of samples enforced on Adaptive-Consistency? My (perhaps incorrect) understanding is that AC involves adding a stopping criteria, which does not provide direct control over the average.**\n\nYou are correct in noting that Adaptive-Consistency (AC) employs a threshold-based stopping criterion, and does not allow for directly controlling the number of generations. However, the confidence threshold in our stopping criterion influences the average number of samples: a lower threshold means AC stops earlier, possibly sacrificing accuracy, while a higher one uses more samples (Sec 5.1, L384). This threshold can be optimized using the training set, by adjusting it and observing the sample count.\n\nIn Section 5.2, when we refer to the \"average number of samples\", we're presenting the empirical average observed across multiple instances. This observed average emerges as a result of AC's adaptive stopping — in some cases, it might stop early, while in others it might sample more, depending on the task. However, on average, AC consistently reduces the number of generations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The method is straightforward and well-justified, and the experiments are sufficiently comprehensive to demonstrate the effectiveness of this method (which mostly boils down to savings in number of samples over the \"fixed-budget\" self-consistency).", "reasons_to_reject": "The exact analysis on performance vs budget is a little lighter than I would have liked (while acknowledging that there is a good amount of analysis already, and that these experiments are expensive to run given the large number of samples).\nIn particular, while Table 1 shows that Adaptive-Consistency achieves comparable performance with fewer samples, it is a little challenging to interpret the results without statistical tests or error bars.", "questions_to_authors": "In Section 5.2, how is the average number of samples enforced on Adaptive-Consistency? My (perhaps incorrect) understanding is that AC involves adding a stopping criteria, which does not provide direct control over the average.", "paper_topic_and_main_contributions": "The authors present a straightforward and easy approach for improving decoding performance, essentially being self-consistency with an early exit based on a stopping criteria. They present results on a variety of tasks and current leading models.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FhdwdfGfXE", "reviewer": "Reviewer_pwx4", "summary": "", "questions": "Question A: Can you elaborate more on the setup for the dynamic budget experiments in section 5.2?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper! We were delighted to read that you found our Adaptive-Consistency approach both neat and intuitive, and appreciated our integration of traditional probabilistic models with LLMs. We're particularly encouraged that you recognized the practical implications, especially the potential for significant monetary and time savings when querying LLMs repeatedly.\n\nWe think that all your questions are addressable within this discussion period. Please see our response below. We would love to address additional questions during the discussion period if anything is unclear.\n\n---\n\n**Experiments with dynamic budget are not very clear.  / Question A: Can you elaborate more on the setup for the dynamic budget experiments in section 5.2?**\n \n\nOur primary objective is to compare the performance of Adaptive-Consistency (AC) and Self-Consistency (SC) across various sampling budgets. We first run AC with different thresholds (a lower threshold results in fewer generations, and vice-versa, as outlined in Section 5.1), producing a series of (#samples, performance) pairs for AC. Then, for each unique sample count from this set, we run SC to obtain a corresponding set of (# samples, performance) pairs for SC. Both sets of data points are presented in Figures 3 (detailed version in Figure 5.1), and show that AC consistently outperforms SC across all sampling costs. We will expand on this explanation and provide more examples in the next version to ensure clarity.\n\n--- \n \n**It is not clear how expensive it is to perform the numerical integrations necessary for the Dirichlet/Beta/CRP models**\n\nAs shown in the table below, the Beta model (used in our experiments) takes less than 0.1 ms per sample, while the Dirichlet and CRP models average around 100ms. These times are *significantly less* than LLM inference, especially considering that our experiments were run on a single core machine.\n\n| Stopping Criteria | Time per sample (ms) |\n|-------------------|----------------------|\n| Beta              | 0.03                 |\n| Dirichlet        | 101.3                 |\n| CRP               | 94.6                  |\n\nWe will include these details in the revised paper to clarify that the stopping criteria that are indeed much less expensive than LLM inferences.\n\n\n---\n\n**No explicit mention that this presupposes that one does not have access to LLM probabilities**\n\nWhile our approach assumes no access to LLM probabilities, it's worth noting that Self-Consistency [1] has shown that even with access to these probabilities, multiple sampling outperforms a single pass. Further, several recent studies [2, 3] have demonstrated better performance using Self-Consistency despite having full access to model weights and token probabilities. \nWe will include this discussion in the revised paper for clarity.  \n\n---\n\n**References**\n1. Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E.H., & Zhou, D. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. ArXiv, abs/2203.11171.\n2. Li, Y., Choi, D.H., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Tom, Eccles, Keeling, J., Gimeno, F., Lago, A.D., Hubert, T., Choy, P., de, C., d’Autume, M., Babuschkin, I., Chen, X., Huang, P., Welbl, J., Gowal, S., Alexey, Cherepanov, Molloy, J., Mankowitz, D.J., Robson, E.S., Kohli, P., de, N., Freitas, Kavukcuoglu, K., & Vinyals, O. (2022). Competition-level code generation with AlphaCode. Science, 378, 1092 - 1097.\n3. Anil, Rohan et al. “PaLM 2 Technical Report.” ArXiv abs/2305.10403 (2023): n. pag.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "**This is a neat and intuitive idea, and the results are very encouraging**. This is an interesting application of more traditional probabilistic models to the field of LLMs, with results suggesting how a Self-Consistency—a common technique—can be substantially improved by preemptively stopping sampling when one can identify the most likely output with high probability.\n\n**Practically useful.** These results indicate that there could be significant monetary cost (and maybe time) savings when repeatedly querying LLMs to get a consensus answer.", "reasons_to_reject": "**Experiments with dynamic budget are not very clear**. It is not clear exactly what the setup in section 5.2 is. Do you fix a budget before hand (that is shared across all datapoints), and then run your approaches and the Self-Consistency baseline until the budget is depleted? If so, what would happen if the budget runs out early, e.g., before all datapoints are processed? I would expect to see more details about this on the paper, or in an appendix.\n\n**It is not clear how expensive it is to perform the numerical integrations necessary for the Dirichlet/Beta/CRP models**. While these numbers are not critical from monetary cost perspective, they are important to understand whether this method also results in net wall time savings in getting an answer from an LLM.\n\n**No explicit mention that this presupposes that one does not have access to LLM probabilities**. The way I see it, this approach is best suited for the setting where ones does not have access to the probabilities of outputs under the LLM (e.g., GPT-4). If one *did* have access to the LLM probabilities (e.g., Vicuna, one of the baselines), then this approach is less useful since one would never benefit from repeated observations of the same output. While this is not a limitation of the proposed method per se, I would expect at least some mention of this in the paper/limitations (maybe I missed it).", "questions_to_authors": "Question A: Can you elaborate more on the setup for the dynamic budget experiments in section 5.2?", "paper_topic_and_main_contributions": "This paper proposes Adaptive-Consistency as a more efficient alternative to Self-Consistency. The key idea is that, instead of making a fixed number of calls to an LLM and taking the majority as the answer (aka. Self-Consistency), the authors propose taking the posterior distribution under a Dirichlet-Multinomial model, and preemptively stop making calls to the LLM when one of the answers has over 95% probability of being the most likely answer (aka. their Dirichlet stopping criterion). They also explore variants of this approach which instead use a Chinese restaurant process (which models the fact that the next sample of the LLM may be completely different from the ones seen so far) and a simpler Beta-Bernoulli model with the two most frequent answers (which is more amenable to computation). They find that their approach reduces the number of calls made to an LLM by a factor of 2-4x, with essentially no impact in downstream performance.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "L427: bidget → budget"}, "extra_text": {}}, {"review_id": "ztXhlGVhCa", "reviewer": "Reviewer_FcEp", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review of our paper! We are pleased to know that you found the paper clearly written and easy to comprehend. We appreciate your recognition of the simplicity yet effectiveness of the Adaptive-Consistency technique, and its potential benefits across various LLM applications.\n\nWe think that all your questions are addressable within this discussion period. Please see our response below. We would love to address additional questions during the discussion period if anything is unclear.\n\n---\n\n**The problem addressed in this paper is basically a statistical inference problem of estimating parameters of the population distribution from samples, which is not specific to LLM, assuming that samples are randomly generated**\n\nWe agree with your observation that the proposed approach has general applicability and isn't confined to LLMs. As you rightly noted, its relevance extends to various online sampling scenarios, especially when sampling is resource-intensive and an early stopping mechanism is advantageous. The related work on crowdsourcing, as exemplified in Section 6, has explored nuanced solutions to the same challenge, and we draw inspiration from these techniques.\n\n---\n\n**I suspect that basic statistical inference techniques based on confidence intervals can be applied to this problem.**\n\nThank you for your suggestion regarding the applicability of confidence intervals to our problem. We aim to provide a probability that a particular element is the majority, rather than estimating a range for a parameter. Consequently, our methodology is tailored to offer a direct probability estimate (Equation 1 and Appendix D).\n\nTo demonstrate the efficacy of Adaptive-Consistency, we tested various baselines, including majority voting, entropy, and CRP. As illustrated in Table 1 and Appendix Table 5, these methods either fall short of our approach in terms of performance or are notably resource-intensive. \n\nIf the reviewer has specific suggestions on integrating confidence interval-based methods with our approach, we will be happy to explore them during the discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper is very clearly written. I feel no difficulty in reading the paper.\n\n2. The proposed method is simple but addresses an important problem. The proposed adaptive-consistency technique would be beneficial for a wide range of LLM applications.\n\n3. Extensive evaluations clearly show the effectiveness of the proposed approach.", "reasons_to_reject": "Although the extension for the code generation task and experimental evaluations are important and\nspecific to the LLM, the problem addressed in this paper is basically a statistical inference problem of\nestimating parameters of the population distribution from samples, which is not specific to LLM, assuming that samples \nare randomly generated. I suspect that basic statistical inference techniques based on confidence intervals can be\napplied to this problem.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes a technique called Adaptive-Consistency, which dynamically determines the number of samples\ngenerated from LLM to draw the conclusion. The existing Self-consistency technique can improve the stability of the output\nof LLMs by generating multiple output samples and selecting the most frequent one as the systems' output. While self-consistency\nalways needs a fixed number of samples. The proposed method can dynamically determine the number of samples and contribute to reducing the average number of samples. Experimental results show that the proposed method can significantly reduce the number of samples with\na negligible drop in accuracy with combinations of multiple datasets and LLMs.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces the novel technique of Adaptive-Consistency for large language models (LLMs), addressing the limitation of traditional Self-Consistency by dynamically adjusting the number of samples. This adjustment is based on the agreement level in the generated samples, leading to more efficient and targeted sampling. Experimentally, across 17 reasoning and code generation datasets with three distinct LLMs, the technique exhibited an impressive reduction in sample budget (up to 7.9 times) with only a marginal compromise in accuracy. Reviewers noted simple but innovative approach, thorough experiments, and broad application potential. 

Pros:

Innovative approach that dynamically adjusts sample numbers, addressing existing limitations in Self-Consistency.

Comprehensive experimental design and results across various datasets, showcasing efficiency and effectiveness.

Clear and well-justified presentation coupled with the potential for significant practical benefits in terms of cost and time.
Cons:

Some lack of clarity on experiments with a dynamic budget and potential complications if the budget is depleted prematurely.

Absence of details on the computational expense (in original draft) related to the numerical integrations for the Dirichlet/Beta/CRP models, raising questions about real-time efficiency.
Decision: Accept-Main