Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
Authors: Yiwei Li
Peiwen Yuan
Shaoxiong Feng
Boyuan Pan
Xinglin Wang
Bin Sun
Heda Wang
Kan Li
Venue: ICLR 2024 poster (2024)
Keywords: Self-consistency
Chain-of-Thoughts
Multi-Step Reasoning
Large Language Models
Primary area: general machine learning (i.e., none of the above)
TL;DR: We propose early-stopping self-consistency (ESC), a simple and scalable process which is capable of greatly reducing the cost of SC while maintaining performance.

Abstract: Self-consistency (SC) has been a widely used decoding strategy for chain-of-thought reasoning. Despite bringing significant performance improvements across a variety of multi-step reasoning tasks, it is a high-cost method that requires multiple sampling with the preset size. In this paper, we propose a simple and scalable sampling process, Early-Stopping Self-Consistency (ESC), to greatly reduce the cost of SC without sacrificing performance. On this basis, one control scheme for ESC is further derivated to dynamically choose the performance-cost balance for different tasks and models. To demonstrate ESC's effectiveness, we conducted extensive experiments on three popular categories of reasoning tasks: arithmetic, commonsense and symbolic reasoning over language models with varying scales. The empirical results show that ESC reduces the average number of sampling of chain-of-thought reasoning by a significant margin on six benchmarks, including MATH (-33.8%), GSM8K (-80.1%), StrategyQA (-76.8%), CommonsenseQA (-78.5%), Coin Flip (-84.2%) and Last Letters (-67.4%), while attaining comparable performances.

Published as a conference paper at ICLR 2024
ESCAPE SKY-HIGH CoST: EARLY-STOPPING SELF- CONSISTENCY FOR MULTI-STEP REASONING
Yiwei Li
Peiwen Yuan Shaoxiong Feng", Boyuan Pan?,
Xinglin Wang',
Bin Sun', Heda Wang". Kan Li
1 School of Computer Science, Beijing Institute of Technology
Xiaohongshu Inc
(Liyiwei,pewwentee peiwenyuan binsun, wangxinglin, likan) @bit ebit.edu.tt.ttnn.. (shaoxiongfeeng222,, whd. thu @maall com [panboyuan] http:o/unnnnkiaaacaggg.s...u. @xiachongshu.com
ABSTRACT
Self-consistency (SC) has been a widely used decoding strategy for chain-of- thought reasoning. Despite bringing significant performance improvements across a variety of multi-step reasoning tasks, it is a high-cost method that requires mul- tiple sampling with the preset size. In this paper, propose simple and scalable sampling process, Early-Stopping Self- Self-Consistency (ESC), to greatly reduce the cost of SC without sacrificing performance. On this basis, one control scheme for ESC is further derivated to dynamically choose the performance-com balance for different tasks and models. To demonstrate ESC's effectiveness, we conduct extensive experiments on three popular categories of reasoning tasks: arithmetic, commonsense and symbolic reasoning over language models with varying scales. The empirical results show that ESC reduces the average number of sampling by a significant margin on six benchmarks, including MATH (-33.8%), GSMSK (- 80.1%), StrategyQA (-76.8%) CommonsenseQQ (-78.5%), Coin Flip (-84.2%) and Last Letters 67.4%) while attaining comparable performances".
INTRODUCTION
Large language models (LLMs) have exhibited strong reasoning capabilities (Bubeck et al. 2023) especially with chain-of-thought (CoT) prompting (Wei et al.) 2022). Based on this, Wang et al. (2023) introduce simple decoding strategy called self-consistency (SC) to further improve reason- ing performances, leveraging the fact that complex reasoning tasks typically allow for more than one reasoning paths leading to the correct answer. In contrast to the standard thain-of-thoughe prompt- ing which only generates the greedy one, this method samples multiple reasoning paths according to the predetermined sample size, and then derives the final answer through voting- noting-based scheme.
However, despite generally leading improvements, the SC strategy incurs significant overhead proportional to the number of sampled outputs. Taking MATH dataset as an example, evaluating the entire test with SC (sampling size 64 following Lewkowyez al. (2022)) costs about 2000S through GPT-4 API, which is a significant burden for many researchers and organizations. Therefore, essential minimize the cost of SC while maintaining performance.
The process of generating multiple samples in SC can be viewed as approximating the true answer distribution predicted by the language model. Then the most frequent one is taken as the final answer to mitigate the stochasticity of the single-sampling strategy. However, given that only the most confident answer is needed for SC, it perfectly. Therefore, we argue that it is not necessary to directly generate all reasoning paths aligning with the preset sampling size for every input. Instead, the generation process can be serialized as smaller parts, each of which is named as sampling window. Considering both the small window and the large number of sampling outputs are generated from the same predicted answer distribution,
necessary whether the whole answer distribution fits
'quual contributions.
i "ooresppnning author.
"Or code and data have been released httth::/ggtthbbe com 98/ KSC

---

Published as a conference paper at ICLR 2024
SC
Demonstrations (optional)
cost:20 samples
Voting:
Question: robe takes? 2 bolts of blue fiber and half that much white fiber. How many bolts total does take?
Sampling
3
3
3
3
3
4
1st window
2nd window
LLM
ESC cost:10 samples
Voting:
Saving Stepping
Entropy is zero
Figure 1: Full process of ESC compared with original SC. We divide the large sample size into several sequential small windows. Stop sampling when answers within a window are all the same, i.e., the entropy score of predicted answer distribution is zero.
can be deemed as a probe to reveal some information of the true distribution with only small sampling number.
For the answer distribution, one conjecture that the correct ones are often concentrated, and the incorrect answers are scattered. We employ entropy as a representation of the answer distribution shape. Figure shows the mean entropy value correct and incorrect voting answer within a win- dow respectively, showing that distributions with correct one as highest probability answer typically have much lower entropy values. Thus, it can be a indicator to determine whether sampling should continue. Based this, we propose early-stopping self-consistency (ESC), truncating the sampling process with low entropy window. Figure Iillstraate its process with an example. In order to main- tain the performance as much as possible, set the strictest threshold: the entropy equals zero, i.e., all generated samples within a window have the same answer. Stop sampling when this situation occurs to reduce sampling consumption while minimize performance impact.
Early stopping Yao et al. 2007) is a widely used tech- nique to prevent poor generalization when training mod- els. But in this paper, we introduce this strategy to early stop the generation process for saving the cost. As with original SC, ESC is unsupervised and model-agnostic, without any human annotation and additional training. We derive the theoretical upper bound of inconsistent probability of the results with or without early stopping scheme in SC, indicating that ESC is highly likely to maintain performance. In addition, one control scheme for ESC is further derivated to dynamically choose the performance-cost balance for different tasks and models by selecting the size of window and maximum sampling times for meeting the practice requirements.
Entropy
85
Window Size
Figure 2: The mean entropy score within the window on MATH dataset from GPT-4.
We evaluate ESC on a wide range of arithmetic, commonsense and symbolic reasoning tasks over three language models with varying scales: GPT-4, GPT-3.5-Turbo and Llama-2 7b. The empirical results show that ESC reduces the sampling times by significant margin on six popular benchmarks, including MATH (Hendryeks et al. (021)) (-33.8%), GSMSK (Cobbe et al. (021) (-80.1% %)), Strat- egyQA (Geva et 202 (-76.8%) CommonsenseQA (Talmor et al. 2019 (-78.5%). Coin Flip (-84.2%) and Last Letters (Wei al. 2022) (-67.4%). while attaining comparable performances. In additional experiments, we show our control scheme for ESC can predict the performance-cost balance accurately across various tasks and models, showcasing reliable application prospects. We also show ESC can robustly save cost considering different decoding settings and prompts.
2 METHOD
2.1 REVISITING SELF-CONSISTENCY
self-consistency WWag et al. 2023) capitalizes the notion that intricate problem requiring logical thinking usually admits several distinct approaches that all lead to the same correct answer. Based this, multiple candidate predictions (ύ' { to problem are suggested to generate through
2

---

Published as a conference paper at ICLR 2024
sampling, and the most consistent is selected as the final prediction through voting process:
= arg MIXX
(1)
where 1,:= is the indicator function (equal to I when E' is equal to prediction i, and O otherwise). We conduct more in-depth derivation follows:
Et= 1p:= arg max f
y arg max
(2)
where (i) denotes the frequency of the model's predicted outcome being i in L sampling in- stances, According to the Law of Large Numbers (Papoulis) 1990), the sample size L approaches infinity, (i) P(t), where P(i) represents the true probability of the model predicting the out- come as this basis, we can further deduce:
i arg P(i) (Given L + o0)
According to equation we can re-conceptualize SC as the process of mitigating noise introduced by individual sampling through multiple samplings. Its objective is to ensure that the prediction with the highest probability, denoted as arg max; P(t) is chosen as the final answer.
From this perspective, we contend that when the entropy of P is low (an extreme case being the one-hot-like distribution), smaller value of L (L is enough for one-hot-like distribution) can mitigate the impact sampling noise according to the Law of Large Numbers.
2.2 EARLY-STOPPING SELF- CONSISTENCY
Building upon the aforementioned analysis, propose Early-Stopping Self-Consistency (ESC) to achieve comparable performance to SC at a much lower sampling cost by adaptively adjusting the sampling times. The execution flow of ESC is illustrated in Algorithm
Algorithm Early-Stopping seff-Consistency.
Require: model M, dataset {(x, ,)
N, window size w. sampling size L, past sampling set Sport
Ensure: predictions set Spredtctions
Spredictions f- Ø for i range N do Scandidetes Ø, Swindow Spast if Spast # Ø else Ø for E &range (L/ do
Swindow + Sampling predictions w times from M given x² if Swindow Ø else Swindoww if predictions in Swindow the same then
Seandidates Swindow break
end if
Scandidates t- Seandidates Swindow- Swindow <- Ø
end for Spredictiona - Sppedcction--ppenddeee max, EpEBanduuate. 1pms)
end for return Spredictions
We view consecutive set of w sampling predictions an observation window for the probability distribution P predicted by model M for input x. When these predictions are all the same, the entropy of P is likely to be sufficiently low. At this point, the voting result of these w samples is very likely to be equal to arg max; P(i), which is exactly the voting result that SC aims for. Therefore, we stop sampling when this situation occurs to save additional sampling consumption while barely affecting performance. We will iterate to obtain multiple observation windows until the preset sampling size L is reached if no observation window meets the need during this procedure. The predictions of all the samples will constitute the final outcome according to equation I
2.3 THEORETICAL ANALYSTS
Now, we analyze to what extent ESC will effect the performance compared with SC. For simplicity, study the case where I. is infinite (we will examine the case of bounded I. in section 2.4.2). We
3

---

Published as a conference paper at ICLR 2024
conduct one proportion z-test with the following null hypothesis. Ho* Prediction appears in an observation window 7" times, where o arg max P(i).
According to the definition of one proportion z-test, the calculation formula for the z-statistic is:
(f T.) v
(4)
To
where 7' is the observed mean, Tμ represents the expected mean, T~ represents the expected standard
deviation, and n represents the observed times. Considering the null hypothesis Hu, where p + arg max; P(t), we can derive as follows:
P(p) - (P(p) mar(P))/2 Σ P(1/2 1/2
(S)
As w samples make up an observation window, according to Bernoulli distribution and equation Tp w. P(p) w/2
(6)
T. = V P(p) P(p)) S vw/2
Taking equation 6 into equation z-statistic has the following lower bound when / > Ty:
w/2) v
V8/2
The voting results of ESC are inconsistent with the voting results of SC if and only if T equals to (when early-stop happens while + arg max; P(i)). When this situation occurs, we have the observed times and π = w, which we take into equation
w/2) VI
Vw/2
Suppose 8, and we choose to reject Ho if 2 V8 (the lower bound in equation g). In this case, the probability false positive This means that when we conduct ESC with w = 8, the probability of the voting outcome being inconsistent with the voting outcome of SC (false positive) is According to equation we can see that as w increases, the lower bound of increases accordingly, resulting smaller upper bound of the probability that ESC performance being affected.
x 10-3 fone-sided p-value corresponding
/8).
10 10-3 which extremely low.
2.4 CONTROL SCHEME FOR EARLY-STOP SELF- CONSISTENCY
In practical applications, the desired scenario is that we can adjust the ESC strategy (window size w, max sampling size L) based on our sampling budgets and performance requirements. Therefore, propose control scheme for ESC to achieve this goal. Specifically, will deduce the expec- tation of voting performance and sampling cost under different (wc, L) settings based on the first observation window (denote its window size Wp).
2.4.1 THE EXPECTATION OF SAMPLING COST
We first use the sampling frequency in the first observation window to approximate the true proba- bility distribution P, and denote it as P. Based on this, the probability of stopping sampling in each observation window (where the sampled values within the window are all the same)
Potop Σ
Epow
(9)
According to Algorithm
the expected average sampling times i. of dataset ID) is:
L//w-1
E(L) = EPEME))
[[Pstop x pow(1 Pstop. j) x x w) + pow(1 - Pstop, L//w) x L] + wo (10)
see Appendix A.I for detailed derivation. According to equation 10
we can determine the mapping
relationship from the choice (w, L) to the expected sampling cost L based on the sampling results of the first observation window.
4

---

Published as a conference paper at ICLR 2024
2.4.2 THE EXPECTATION OF VOTING PERFORMANCE
When L is bounded (practical scenarios), we discuss the probability of ESC voting outcome being inconsistent with arg max, P(a) with (denoted as (P)) and without (denoted QP(P) the occurrence of early-stop.
When early-stop happens, similar to the derivations in section 2.3 the 7-statistic under the P distribution. We then calculate the sum of the probabilities that the voting outcome of ESC being inconsistent with the voting outcome of SC for all candidate p when early- stop happens, where p + arg max; P(i):
we substitute P to P to calculate
w w P(p)
Qu = Σ
querying(
(11)
pylarg max, P())
V V P(p)(1 P(p))
where querying(-) represents the process of querying p-value corresponding to the z-statistic.
When early-stop happens, ESC degenerates into SC. We view the whole L samples an obser- vation window and has the following derivation of z-statistic:
f L P())
=
(12)
VL L+ P()) ((p))
prediction p is selected as the voting outcome, then the the following inequality should hold: / 2 L/2. Combining with equation 12 we derive the upper bound of (P):):
L/2 L P(p)
Qa(P)
querying(
(13)
I. P(p)( P(p))
paarg P(t)
According to equation 9 the probability of that early-stop not happens is pow(1 - Patops L// L//w). Thus, the upper bound of the expected probability of ESC voting outcome being inconsistent with arg max, P(t) is:
B(Q) & BPEM(n (1 - -pow(1 - Pstops L//w)) Qw) + pow(1 - Pacopy L//w) Qo(P)
(14)
2.4.3 CONTROLLABLE EARLY-STOP CONSSSONNYYYYNCC
Based on the above derivation, we propose our control scheme for ESC shown in Algorithm| 2 First, we sample win times on the whole dataset. Based on the results the first observation window, we calculate the expected sampling cost and performance under different settings of (w, L.). Finally, considering the sampling budget and performance requirements, we choose appropriate values of (w, L) based on the respective expected values to execute ESC.
Algorithm 2 Control Scheme for Early-Stop Self- celf-Consistency.
Require: model M, dataset {(x; y)) initial window size we (recommended as 5), sampling budget B, performance expectation P.
Ensure: Predictions set Spredictions
3 Sfirsturindow for (x,y)
Susndow + Sampling predictions we times from M given x
S Sfirstwendww S fostwindow + Swindow
end for
for (un, T.) do
B(L) + section 2.4.1 (S @frrttuindow w, L), BBQ) + section 2.4,2 @ Srrstwindown L)
(E( (E( B(Q)
meets the need of (B, P) then
1b + w, L + break
end if end for return Algorithm 1 M. D ((x,)))' á. L. Sjiretwindow)
5

---

Published as a conference paper at ICLR 2024
3 EXPERIMENTS
3.1 EXPERIMENT SETUP
We evaluate the proposed ESC on six benchmark datasets from three categories of reasoning tasks: For arithmetic reasoning, we consider MATH (Hendrycks et al. 2021) and GSM8K (Cobbe et al. 2021I. MultiArith (Roy & Roth 2015). SVAMP (Patel et al. al.] 2022). I). AddSub (Hosseimi et al. 2014) and ASDiv (Miao et al. (0200) are not chosen in this paper because they are relatively simple. For commonsense reasoning, Commonsense(QA (Tammor et al. 2019) and Strategy (Geva al., 2021 are used. For symbolic reasoning. we use Last Letter Concatenation and Coin Flip from Wei ct al. (2022). The data version is from Kojima et al. (2022).
ESC is evaluated across three language models with varying scales: GPT-4 (OpenAl 2023), GPT- 3.5-Turbo and LLaMA-2 7B (Touvron et al. 2023). All experiments are conducted in the few-shot setting without training fine-tuning the language models. To ensure fair comparison, same prompts as Wei et al. (2022). Details on the prompts used are given in Appendix.
the
The sampling temperature T for MATH is 0.5 while for other datasets is 0.7. GPT-4 and GPT- 3.5-Turbo samples predictions without truncating. For Ilaaa 2, the threshold for top truncation (Holtzman al. 2020) is 0.9. Similarly to Wang et al. (2023), provide ablation study in Section 0.6 to show that ESC is generally robust to sampling strategies and parameters.
3.2 MAIN RESULTS
The baseline we compare to Mhain-of-thoughe prompting with greedy decoding (CoT) and self- consistency (SC) with sampling. Following Lewkowyc7 et al. (2022), the sample size L, for MATH is 64 and for others is 40, and ESC uses the same value as maximum sample size. Accordingly, the window size for MATH is 8 and for others is 5. We report the results averaged over 10 runs and omit variance for limited space.
Accuracy (%) and L (average actual number of generated samples in ESC, in gray) across six reasoning benchmarks. i-SC denotes the accuracy of SC with sample size as L.
Table 1:
MATH
GSM8K
CSQA
SQA
Letter
Coinflip
CoT
50.44
87.70
83.71
78.63
93.12
100.00
SC
60.32
89.29
87.18
81.67
95.00
/
GPT-4
ESC
60.32 (0.00)
89.29 (0.00)
87.18 (0.0)
81.70 (40.0))
94.98 (-002)
L
42.40 (-21.60)
7.98 (-2202)
9.29 (:3071))
7.19 (-11,99
6.32 (-33688)
/
i-sc
59.98 (-034)
89.07 (-022)
86.49 (-0.9)
81,40 60227)
94,59 (-039)
CoT 35.53
75.83
74.17
67.66
80,50
83.74
SC
49.97
85.69
78.10
75.90
83.21
99.54
GPT-3.5
ESC
(400))
85.67 (-0.2)
78.10
75.71 (-0.19)
83.15 (-006)
99.49 (4005)
Turbo
L
52.37 (:1163)
14.65 (:25.35)
11.70 (28,30)
8.51 (227.93)
8.82 (31.18)
13.03 (12639)
i-sc
49.79 (0013)
84.82 (0.85)
77.67 (10.3)
75.07 (0083)
82.74 (-0.41)
98.67 (-0.22)
CoT
5.09
18.07
65.28
46.23
14.87
54.74
SC
7.68
21.75
67.70
63.15
23.32
59.13
Llama-2 7B
ESC
7.68 (0.00)
21.74 (0001)
67.68 (.002))
63.01 (:0.14)
23.32 (0.00)
58.99 (40.14)
L
62.48 (:1.22)
31.21 (18.9)
11.82 ((28.18)
11.00 (23.96)
34.73 (6:27)
14.87 (:25.13)
L-SC
7.68 (0.00)
21.52 (022)
66.97 (0.71)
61.19
23.11 (0221)
58.11
ESC significantly reduces costs while barely affecting performance. Table summarizes ac- curacy of CoT, SC, proposed ESC and i, the average actual number of generated samples ESC, for each dataset among three language models. The first observation is that SC: outperforms CoT substantially, which confirms the effectiveness of the voting process for reasoning. For ESC, the Ż is largely smaller than the corresponding maximum sampling size L. while the accuracy has remained almost unchanged. Given that the accuracy of Coin Flip GPT-4 is 100%, there is no need to conduct SC and ESC it. We also test SC with f. the sampling size (L.-SC), whose accuracy

---

Published as a conference paper at ICLR 2024
drops in accordance with the performance curve relative to the number of samples from Wang al. (023). Overall, ESC can reduce costs significantly while barely affecting performance. other words, ESC can get higher accuracy under the same sampling costs.
Table 2: Reasoning accuracy (%) and & with various max sampling size L. The window size is 8.
Model
Method
16
24
32
48
64
SC
58.92
59.40
59.77
59.95
60.07
60,31
GPT-4
ESC
58.92 (0.00)
59.40 (0.00)
59.77 (0.00)
59.95 00.00
60.07 (0.00)
60.31 (000)
13.56 (244)
18.72 (5.28)
23.67t8.33)
(1159)
(11.5)
33.21 (14.79)
42,41 (-21.9)
47.34
48.48
49.02
49.40
49.65
49.96
GPT-3.5
ESC
47.33 (0.0))
48.49 (10.01)
49.02 (0.00)
49.41 (50.01)
49.64 (0001)
49.96 (0.00)
Turbo
L
14.84 (1.16)
21.38 (-2.62)
27.76 (-4.44)
34.02 (5598)
40.20 (-7.00
52.37 (-11.33
SC
7.10
7.28
7.40
7.45
7.54
7.70
Llama-2 7B
7.10 (0.00)
7.28 (0.00)
7.40 (0.00)
7.45 (0.00)
7.54 (0:00)
7.70 (0.00)
L
15.88 (40.2)
23.72 (4.29)
31.52 (-0.88)
39.29
47.04 (0.96)
62,48 (-1.52)
ESC a scalable decoding process across sampling and window size. We conduct experiments with various window size and sampling size to valid the scalability of ESC. Table 2 shows the performance across different maximum sampling sizes. First we can see the performance of SC continuously improves sampling size L increases, which is consistent with the results in (Wang) ct al, 20033. On this basis, ESC can significantly save costs while maintaining performance for different L. Figure 3 shows performance-cost balancing lines among three language models on GSM8K. ESC is robust to different window size and maximum sampling number. Please refer to Aigendix-Figure for results on other datasets.
Cost savings are positively correlated with performance. As shown in both Table and Ta- ble(2, an obvious phenomenon is that cost savings are positively correlated with performance. is intuitive since better performance often eliminates the need for larger sample size as recommended Wang al. (2023). However, ESC does not require any prior knowledge model capabilities and task difficulty. In addition, control scheme for ESC is also proposed and will be evaluated in Section 3.3
GPT4: GSMBK
GFT:3.5 GSMBK
Liama 2-7b: GSMBK
40.
42
42
10
A2B
K3
K23
32
9:3
A:30
M012
8:10
20
22
SC
30
12
16
MCC
Figure 3: Robustness analysis of ESC regarding the observation window size and max sampling
size L on GSM8K with different models.
3.3 EFFECTIVENESS OF CONTROL SCHEME FOR ESC
To assess the effectiveness of control scheme for ESC, we compared the consistency between our predicted and actual values of sampling cost L and performance change percentage between SC and ESC on the GSMSK dataset. We chose LI norm and Pearson correlation to measure the consistency shown in Table the Pearson correlations for both L and Ps exceed 0.8, indicating strong linear correlation between the predicted and actual values. Also, the LI norm for both L
"We vary the max sampling size to obtain multiple sets of results for calculating the Pearson correlation and L1 norm.

---

Published as a conference paper at ICLR 2024
and P3 are very low. These results indicate that the predictions obtain based on equation and equation 14 are highly reliable for balancing sampling cost and voting performance.
Table 3: Consistency between the predicted (through control scheme for ESC) and actual values of
L: sampling times, and Ps (%): performance change percentage between SC and ESC. We choose
LI norm and Pearson correlation to measure the consistency. All the p-values < 0.05.
Model
I ace irre I Pearson i L
| Parell
Pearson Pa P
GPT-4
0.27
1.00
0.43
0,81
GPT-3.5 Turbo
0.62
1.00
0.06
0,86
Llama-2 7B
1.43
1.00
0.52
0.86
3.4 ESC FOR OPEN-ENDED GENERATIONS
Original SC is only suitable for problems that have fixed answers, WhileJain al. (2023) extended it for open-ended generation tasks by replacing voting through text similarity matching. We conduct ESC on MBPP dataset (Austin al. 202T) with various sampling size (window size is 5). The results in Table shows that ESC is also suitable for open-ended task.
Table 4: Reasoning accuracy (%) and i. for MBPP with various max length L on GPT-3.5-Turbo.
Method
10
15
20
25
30
SC
61.96
61.96
62.04
62.15
62.18
ESC
61.96 (1.00
61.96 (0:00)
62.02 (-002)
62.11 (0.04
62.15 (40.03)
5.62 (4438)
6.02 (8.98)
6.32 (-1.68)
6.57 (41843)
6.79 (23.21)
3.5 INTERSECTION BETWEEN ESC AND SC
Table 5: Intersection ratio between ESC and SC.
According Section 2.3 the voting results of ESC should have a high probability of being con- sistent with SC. From Table the intersection ratios of the voting results of SC and ESC are quite high, which indicates the upper bound of the performance being affected by ESC derived in Section 2.4.2 is reliable.
Model
GSM8K
SQA
Letter
that
GPT-4
99.69
99.69
99.96
GPT-3.5-Turbo
99.92
99.25
99.76
Ilama-2-7B
99.77
99.13
99.75
3.6 ROBUSTNESS OF ESC
Additional experiments were conducted to further test the robustness of the proposed ESC, including its robustness to sampling parameters and prompts: (1) In Figure g (up) we show how ESC behaves for GSM8K as the decoding sampling temperature increases. Savings
consistent across different generation temperatures. (2) Figure 4 (bottom left corner) shows that ESC is robust to p values for top-p sampling. (3) 4 right corner) indicates ESC can generalize zero-shot manner. (4) 6 the accuracy of ESC and SC with different groups of demonstrations. We can see that ESC is robust to various demonstrations (see Appendix-Figume 6 for results on StrategyQA).
Table 6: Reasoning accuracy (%) and i. for GSMSK on GPT-3.5-Turbo with different demonstra-
tions. The max sampling size is 40 and window size 5.
Demonstration Groups
1st
2nd
3rd
4th
Sth
SC
85.69
85.56
84,80
85.63
85.24
ESC
85.67 (-002)
85.58 (0.02)
84.80 (0.00)
85.64 (0.01)
85.23 (-001)
14.65 (25.35)
14.53 (2547)
15.64 (:2436)
14.76 (22.24))
14.59 (25.411)
8

---

Published as a conference paper at ICLR 2024
15
15-
28
33-
80.5
62.3
125
32.0
12.5
835
120
02.5
830
06.5 145
85.0
1635
ACC
ACC
ACC
ACC
pm]
35-
33
28
20
15
15
023
825
136
635
540
865
85.0
83 85
925 934
835
545
850
855
ACC
ACC
ACC
ACC
Figure 4: Robustness analysis of ESC regarding the sampling temperature T, in nucleus sampling, and zero-shot demonstration on GSM8K with GPT-3.5-Turbe
4 RELATED WORK
Chain-of-thoupg Reasoning Chain-of-thought prompting has been proven to be an effective method of solving complex reasoning problems (Wei al. 2022). By following the pattern of grad- ually solving sub-problems. both few-shot CoT (Fu et al. 2023) and zero-shot CoT (Kojima et al. 2022] are capable of stimulating LLM reasoning abilities. On this basis, Least-to-mont tosstt prompting (Zhou et al. 2023) suggests explicitly splitting the problem and solving them step by step. Zheng al. (2023) iteratively generating answers and adding the historically generated answers as hints to the context to achieve the final convergence on the answer.
Self Consistency Self-consistency (Wang et al. 2023) refers to a simple decoding strategy for further improving reasoning performance, leveraging the fact that complex reasoning tasks typically allow for more than one correct reasoning path. Jain et al. (203) extend it for open-ended gener- ation tasks like code generation and text summarization by replacing voting through text similarity matching. Li et al.] (003) assign appropriate weights for answer aggregation to achieve adaptive self-consistency. However, all of them require multiple sampling with the pre-set size, which will incur much more computation cost. Aggarwal et al. (2023) introduce an adaptive stopping criterion based on the amount of agreement between the samples so far, but it needs additional data tune the hyperparameter and is sensitive to threshold. By contrast, ESC has no hyperparamter for stopping criterion and has additional control scheme to meet realistic requirements.
CONCLUSION
We have introduced a simple yet effective sampling process called carly-stopping self-consistency (ESC). By stopping the decoding process with high confident window, ESC greatly reduce the cost of SC without sacrificing performance. control scheme for ESC is further derivated dynamically select the performance-cost balance for different tasks and models, which requires no extra prior knowledge of model capabilities and task difficulty. The empirical results show that ESC reduces the actual number of samples of thain-of-thought reasoning by significant margin six popular benchmarks, while attaining comparable performances. We also show control scheme for ESC can predict the performance-con trade-off accurately across various tasks and models. The additional evaluations indicate that ESC can robustly save cost considering different decoding settings and prompts, and even open-ended generation tasks.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work supported by Beijing Natural Science Foundation (No. (22.4222037, L181010).
REFERENCES
Pranjal Aggarwal, Aman Madaan, Yiming Yang. and Mausam. Let's sample step by step: Adaptive- consistency for efficient reasoning with 1lms. CoRR, abs/2305. 11860, 2023. doi: 10.48550/
ARXIV.2305. 1860. URLhttps: /tw.//dd....oo www.doo....oooooooooooooooooooo. www./o............o..ooo........ 48550/ aat.vvaxvvv./..m///vv 23... 11860
Jacob Austin, Augustus Odena, Maxwell I. Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J. Cai, Michael Terry, Quoc V. Le, and Charles Sutton. Pro- gram synthesis with large language models. CoRR, abs/2108.07735. 2021. URL https:
07732
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Ka- mar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott M. Lundberg, Harsha Nori, Hamid Palangi, Marco Túlio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experi- ments with GPT-4. CoRR, abs/2303.12712, 2023. doi: 10448550VarXx..2333.2277 URL
12712
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. CoRR, abs/2110.14168. 2021. URL
httts::/arxiv.co aww.//////////////a/oo//// 2210. 14168
Yao Fu, Hao Peng, Litu Ou, Ashish Sabharwal, and Tushar Khot. Specializing smaller language models towards multi-step reasoning. CoRR, abs/2301.12726, 2023. doi: 10.485500/rXiv.2300.1 12726. httpt::t/////o org /t.zg/10..
2301. 12726
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did aristotle use laptop? A question answering benchmark with implicit reasoning strategies. Trans. Assoc. Comput. Linguisties, 9:346 361, 2021. doi: 10.1162/tacl,, _a) URL https:://oii
00370
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual, 2021, URI. htw.:/ssee.e.bbbeeeeaannr----ees htrpree--eeeeeeeee------rrreeeee nwwrieuris... cc/ wttpc//pppppep211111 - round2. html
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case neural text degeneration. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, OpenReview.net, 2020. URL htttps://peerrevieee net/fooung saarrumiiddryyG@yyrF30
Mohammad Javad Hosseini, Hannanch Hajishirzi, Oren Etzioni, and Nate Kushman. Learning to solve arithmetic word problems with verb categorization. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, Special Interest Group of the ACL, pp. 523 533. ACL, 2014. doi: 10.31155v1/d1441055 /
Siddhartha Jain, Xiaofei Ma, Anoop Deoras, and Bing Xiang. Self-consistency for open-ended generations. CoRR, 0ix/2307.06857 2023. doi: 10.48550/a2x...2337..666 2307.06677.. URL https:
//doi. www.oo..................o
18850//rxiiv 10300006833
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke
Iwasawa.
Large
language models zero-shot reasoners. In NeurIPS, 2022.
URL
10

---

Published as a conference paper at ICLR 2024
Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay V. Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman- Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solv- ing quantitative reasoning problems with language models. URL
In NeurlPS, 2022.
http://papers.a wwtpssiwwpp...pppepeeeeeppppmp wwtpaperppppc.eceeece saaapper_fleesppeeee wfw.le//paerr/222//aaaas
Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Bin Sun, Xinglin Wang, Heda Wang, and
Kan Li. Turning dust into gold: Distilling complex reasoning capabilities from Ilms by leveraging
negative data. CoRR, abs/2312 12832, 2023, doi: (044850/ARXXY12312288888 URL https:
085555/ar 2312. 12832
Shen- Yun Miao, Chao-Chur Liang, and Keh- Su. A diverse corpus for evaluating and developing
english math word problem solvers. In Proceedings of the 58th Annual Meeting of the Association
for Computational Linguistics,, ACI. 2020, Online, July 5-10, 2020, pp. 975-984. Association for Computational Linguistics, 2020. doi: 10. 10118633/1/2022..cc-mmaam
URL httpp:://d/
maainmain..... 92
OpenAl. GPT-4 technical report. CoRR, URL http:tttp///i...//.....44
2023. doi: 10.45550//XXX1:2333.07744
Athanasios Papoulís. Probability and statistics. Prentice-Hall, Inc., 1990.
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are NLP models really able to solve simple math word problems? In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 1, 2021, pp. 2080-2094 Association for Computational Linguistics, 2021. 12201/11222222222 maacl-main.nnnee URL https::/do...oooo http://00...00010011153///1//11
doi:
naacl maacc-maing mwn.mmain..m 168
Subhro Roy and Dan Roth. Solving general arithmetic word problems. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, Lisbon, Por- tugal, September 17-21, 2015, pp. 1743-1752. The Association for Computational Linguistics, 2015. doi: 1118653/v1/d15 1/222 URL https:: /tt.///ooiia/ org/ 10. http:///11..1111111111111--11111
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqa: A ques- tion answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Con- ference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL-IILT 2019, Minneupolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Pupers), pp. 4149-4158, Association for Computational Linguistics, 2019. doi: 111655/v1/n111116 URL (tt.l:tttts//t wttp:////////.....10.........10. 1ttp://00000133311111111111
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajwwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshom, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee. Diana Liskovich, Yinghai Lu. Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine- tuned chat models. CORR, 0bs/2307.09288. 2023. doi: 10.48550/arxiv.2307.00 09288..... URL
415.0/.8555/220 htttps://dii http:///////.////..1.....
09288
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference Learning Representattinss, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https: http://///ppeeeeeee.ee.m net/ pdf pdf 1
11

---

Published as a conference paper at ICLR 2024
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi,
Quoe V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In NeurIPS, 2022. URL http: http::/paperss...ee/ nips wttpppperrreeeee/paaaaaaaaeeeeaa wwwes/papepl.eeeee
9d5
html
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn- ing. Constructive Approximation, 26:289-315, -35, 2007.
Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li. Progressive-hint prompting improves reasoning large language models. CoRR, abs/2204.09797, 2023, doi: 10.48550/ arXiv.2304.09797. URL /ttLL/ttt:///...ooo http://ii.orrr...///oo org/10 48550/ arwiv 2 .00.099997
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. Least-to-most prompting en- ables complex reasoning in large language models. In The Eleventh International Conference on Learming Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
URL https: httttps://penreviewse net wdwpid=wzhhiaaaa
12

---

Published as a conference paper at ICLR 2024
A
APPENDIX
A.1 DERIVATION OF THE EXPECTATION OF SAMPLING COST
Given the probability of stopping sampling in each observation window as Pstop, the probability of continue sampling is Pstop- Therefore, the probability of early-stop occurring after windows is P. Pstop X pow(1 Pstop: j). On this basis, the expected sampling cost in the first T windows can be denoted as:
L/fw-1
B(L1) = = BEM(())
Σ J=U
(Pstop pow(1 Pstop: j) x j x w)
(15)
If early-stop occurs after observing L//w- windows, then the maximum sampling size L. is reached upon the next observation window. The expected sampling cost this part can be denoted as:
L//w-1
E E(L2) = (P)
Σ
pow(1 - Pstops L//w) x L
(16)
Including Wo, the overall expected sampling cost is:
1//w-1
E(Í.) EPEME)
Σ
[(Pstop x pow(1 Potop: 1) x w0 + pow(1 Potop: L//w) x L] + uo (17)
A.2 COMPARISON WITH ADAPTIVE-CONSISTENCY (AC)
Aggarwal et al. 2023) introduce adaptive stopping criterion based on the amount of agreement between the samples so far, but it needs additional data to tune the hyperparameter and is sensitive to threshold. But for proposed ESC, the stopping criterion needs no hyperparameter due to the most conservative strategy to maintain the performance, i.c., all the answers within a window are same. Thus ESC can be conducted directly for different tasks and models, without any validation set.
Another drawback AC generating samples step by step, which means each sample requíres one input. Considering the demonstrations for in-context learning (usually 8 examples) have lot of tokens, will cost quite a portion the budget. By contrast, ESC generates samples in multiple sampling windows, thus samples within window share the same input. Table shows that ESC can get higher accuracy with less sampling cost comparing with AC.
Table 7: Prompt token count (tokens/item, denoted as #prompt), completion token count (to- kens/item, denoted as # completion), average sampling cost (S/item) and accuracy (%) resulting from different methods. The best and second-best results are emphasized with bold and underline.
GPT-3.5 Turbo
GPT-4
Datasets Method
# prompt # completion
Cost
Acc
prompt completion Cost
Acc
SC
496.9
2909.0
0.0084
85.69
495.9
2646.5
0.2316
89.29
GSM8K
AC
4930.3
813.2
0.0087
85.66
2927.6
412.5
0.1501
89.28
ESC
1469.2
1220.8
0.0052
85.67
793.0
564.8
0.0769
89.29
SC
428.7
1382.9
0.0043
78.10
427.8
1474.6
0.1351
87.18
CSQA
AC
3522.3
294.2
0.0055
78.05
2844.5
271.5
0.1355
87.15
ESC
1003.2
420.9
0.0024
78.10
794.6
384.0
0.0625
87.18
166.0
1463.1
0.0041
83.21
165.0
1396.9
0.1184
95.00
Letter
1057.5
233.6
0.0020
83.15
791.7
167.5
0.0451
94.97
ESC
293.0
323.7
0.0012
83.15
208.7
220.7
0.0260
94.98
13

---

Published as a conference paper at ICLR 2024
A.3 COMPARISONS BETWEEN SC AND ESC WHEN L RELATIVELY SMALL (10 AND 20)
we conduct experiments with smaller sampling sizes L. From the results in Table 8 we found that ESC can consistently save sampling costs in such scenarios, while achieving improvement compared to SC under the same costs.
Table 8: Reasoning accuracy (%) and L. with various max sampling size L. The window size is 5.
CSQA
GSM8K
Letter
Model
Method
==
L
== 10
L
== 10
SC
86.49
86.83
89.16
89.24
94.66
94.79
ESC
86.49 (0.00)
86.84 (40.01)
89.16 (0/0)
89.24
94.66 (0.00)
(40.))
GPT-4
5.92 (4.08)
7.27 (-1278)
5.79 (4.21)
6,76 (-1324)
5.57(4443)
5.92(-14.08)
L-SC
86.07
(0.42)
86.31 (0.52)
88.95 (0211)
89.02 (0022)
94.58
94.58:0221)
SC
77.63
77.93
84.10
85.15
82.80
83.00
GPT-3.5
ESC
77.63
(0.00)
77.91 (4.02)
84.10 (0.00)
85.15 (0.00
82.81 (4001)
82.98 (-0.02)
Turbo
L
6.47
(3.53)
8.60 (-11.40)
7.09 (-291)
10.14 (-986)
6. ((c.8))
7.36x-12.6)
i-sC
77.39
(4124)
77.55 (4038)
83.31 (60.9)
84.10 (-105)
82.45.0.35)
82.65.035)
SC
66.89
67.25
20.74
21.32
21.21
22.49
ESC
66.89
67.26 (+0:01)
20.74
21.32
21.21 (0.00)
22.48 (-0.11)
Llama2-7b
6,59 (3.41)
8.78 (-1.22)
8.99 (-101))
17.06 (-2:4)
9.67(-0.3)
18.47(.159)
L-SC
66.80 (-009)
66.84 (0.41)
20.59 (0.15)
21.21 (-0.11
21.21
22.32.0.17)
A.4 DISCUSSION ON THE CHOICE OF INTRODUCING OBSERVATION WINDOW FOR THE DESIGN OF EARLY-STOPPING STRATEGY
We design the stopping strategy with the introduction of window for the following two reasons. Firstly, we break the sampling process only if all of the samples in the latest window are consistent, thus avoiding any hyper-parameter. If sample one by one and stop based on the observation of the sampled samples, obviously we cannot adopt such a strict truncation condition. In this case, we need to introduce certain statistic and its corresponding threshold thyper-parameter/ which is hard to determined prior. Secondly, we have actually considered using the normalized entropy of the sampled samples as the statistical value for cut-off. As shown in Figure 5 we found that this method not only has the pappee-prameter problem mentioned above, but also has no advantage over ESC in terms of performance-cost trade-off. We believe this is because examining the cut-off point after each single sampling is too frequent, introducing greater randomness. This makes the model more likely early-stop without sufficient sampling.
Llama2-7b: CSQA
GPT-3.5 Turbo:
GPT-4:
014
Figure 5: Comparisons between SC, ESC and ENT(usiing entropy to determine the cut-off point) on CSQA with different models.
A.5 THE COMPARISONS BETWEEN ESC AND OTHER STRONG REASONING BASELINES.
ESC achieves better results compared to SC with the same overhead by saving sampling costs while almost not sacrificing performance. From the perspective of performance improvement, we are cu- rious about the comparison results between ESC and advanced reasoning methods that focus on per-
14

---

Published as a conference paper at ICLR 2024
formance enhancement. For this purpose. compared ESC with Progressive- Higt Prompting(PHPP) (Zheng et al. 2023) in terms of both performance and overhead. PHP improves performance by ap- proaching answers through the stepwise generation of clues. As shown in Table 2 we found that ESC outperformed CoT by 9.84%, higher than PHP's 9.25%. Additionally, ESC incurs less sam- pling overhead. PHP, due to the need for multiple inputs the model with previously enhanced prompts, has larger overhead in the prompt part. Overall, ESC achieves better performance with lower sampling costs.
Table 9: Prompt token count (tokens/item, denoted #prompt), completion token count (to- kens/item, denoted as # completion), average sampling cost ($/item) and accuracy (%) comparison between CoT, PHP (Zheng al. 2023) and ESC on GSM8K with GPT-3.5-Turbe Max sampling
size of ESC is 40. CoT and PHP apply greedy search as sampling strategy.
Method
prompt
# completion
Sampling Cost
Accuracy
CoT
496.9
72.7
0.0006
75.83
РHP
6552.0
360.8
0.0072
85.08
ESC
1469.2
1220.8
0.0052
85.67
A.6 THE ORTIIOGONALITY ESC OTHER STRONG REASONING BASELINE.
To assess the orthogonality of ESC with other advanced reasoning methods, we applied ESC on PHP. As shown Table IO] PHP w. ESC achieved similar performance with PHP w. SC while signifi- cantly reduced sampling overhead. This indicates that existing advanced methods can significantly reduce costs by applying ESC with almost no sacrifice performance.
Table 10: Reasoning accuracy (%) and L for GSM8K on GPT-3.5-Turbo with Progressive-Hins Prompting(PHP) (Zheng et al. 2023). The window size is 5.
Max sampling
20
PHIP w. SC
86.32
86.64
86.76
87.00
PHP ESC
86.32 (0.00
86.62 (0002)
86.77 (40.0))
86.98 (-002)
i
6.15 (3385)
7.83 (42.77)
9.15 (20.85)
10.26 (-2924)
L-PHP w. SC
86.02 (.030)
86.29 (0.35)
86.32 (-0.4))
86.35 (1065)
A.7 ADDITIONAL RESULTS
Figure 6 shows the robustness of ESC regarding the sampling temperature T, in nucleus sampling. and zero-shot demonstration on Strategy with GPT-3.5-Turee Figure 77oowss the robustness of ESC regarding the observation window size and max sampling size L on multiple datasets with different models.
A.8 8 PROMPTING DETAILS
We list the details the prompts used for MATH dataset. Following Wang et al. (2023), we use the same prompts for other datasets as in Wei et al. (2022) for fair comparison.
15

---

Published as a conference paper at ICLR 2024
Strateg/44 T-0.3
StategyOA T-0.55
Stratgp0OA T-0.7
Stratog/04 T-0.9
ESC
EX
7325 7338 1575 1882 7425 1430 7435
75.5 1487
1625
1837 19.5 15,00
142
16.
753
14.5
ACC
Strateg/44 p-0.9
StotegyO4 p-0.55
StrategyOA p=1
StratogeCC Zero shot
S5 ESC
F2
14.
75.5
753
755
744
165
35.0
355
14.5
75.
755
98.53 6435 09.30 (675 3326 7055
ACC
Figure 6: Robustness analysis of ESC regarding the sampling temperature T, p in nucleus sampling. and zero-shot demonstration Strategy QA with GPT-3.5-Turke
16

---

Published as a conference paper at ICLR 2024
Letters,
Llama-2-78 Letters,
04.4
$4.5
34.6
34.7 ACC
942
94.9
86.0
12.0
922
62.
62.5
92.
$3.0
852
27
18
23
22
ACC
ACC
GPT-4: Commansarse@A
GPT-3,-- Commor neniAA
1lama-2-7B: CommansinsiiC
40
40
40
30
30
R55
R55
RC5
RC5
10
M10
8730
9C
20
9C
SC
12
MATH
10
10
54
57
5.8
45
48
5.0
1.5
ACC
ACC
ACC
GPT-4: Sir OA
GPT-3.--Turb: StrateggOA
Uama-222 2-78: StrategyGA
43
4144
804
R04
K55
A73
33
KGB
K5
A110
A112
A132
SC
75.5
GPT-3.5-Turb: Flip
Llama-2-7h: Coin Flip
20
1
10
12.5
57.2
$0.0
58.5
590
ACC
ACC
Figure 7: Robustness analysis of ESC regarding the observation window size and max sampling size on multiple datasets with different models.
17

---

Published as a conference paper at ICLR 2024
Table 11: Few-shot prompts for MATH dataset.
system: Think the question step by step and give the answer.
user: Problem:
Find the domain of the expression vō-a"
VØ-2
assistant: Solution: The expressions inside each square root must be non-neg negative. There- fore, z - 2 2 0, so x 2 2, and 5 2 0, I 5. Also, the denominator cannot be equal
to zero, so - x > O, which gives x < Therefore, the domain the expression is [2, 5)
user: Problem: Compute: 55 x 1212 15 1212.
assistant: Solution: We have 55 x 1212 15 1212 1212(55 15) = 1212(40)
4848(10) = 48480
16
user: Problem: Compute
15
16
16
assistant: Solution:
16
15
user: Problem: Find x, where is a square number which is divisible by four, and between 39 and 80.
assistant: Solution: We know that is between 39 and 80, and since 6 36 < 39 and 9a = 81 > 80, this means that 6² < x < 92. This leaves us with two possibilities for æ,
which are 72 = 49, and 8 = 64. We then see that only 64 is divisible by four, so = 64
user: Problem: Solve the inequality
(x 2) 3) 4) 0. (x 1) 5)(x 6)
Solution: We can build a sign chart, but since all of the factors are linear, we can track what happens to the expression as increases. At x 0, the expression is positive. As x increases past 1, the expression becomes negative. As x increases past 2, the expression becomes positive, and so Thus, the solution
assistant:
x E 1) (2, u (6,
user: Problem: right circular cone has volume of 12T cubic centimeters. The height of the cone is 4 em. How many centimeters is the circumference of the base of the cone, in terms of T?
assistant: Solution: The volume of cone is 2 We given that the volume is 12m and the height is Thus, 7T
12x. Solving for r, we find r 3. Therefore, the circumference of the base is 2nr = -x
user: Problem: How many perfect squares less than 1000 have a ones digit 2, or 4? assistant: Solution: Checking the squares from 12 to 102, we that squares end in 2 3, while square ends in 4 if its square root ends in 2 or 8. Since 312 < 1000 < 322, we see
that the squares less than 1000 ending in 4 are 2, 8, 12, 18, 22, 28. Thus the desired answer
6..
user: Problem: The diagonals of a rhombus are 10 inches and 24 inches. What is the perime- ter of the rhombus, in inches?
assistant: Solution: The diagonals are perpendicular bisectors of each other, so therefore the side length of the rhombus be calculated as V52 + 122 13. Therefore, the perimeter
of the rhombus is 13 52 inches.
18


Reviews:
[{"review_id": "C5gU1B0zgi", "reviewer": "Reviewer_qSHs", "summary": "This paper presents Early-Stopping Self-Consistency (ESC), an adaptation of the original self-consistency to reduce the sampling cost. Instead of generating all samples at once, ESC generates samples in multiple sampling windows, and stops when all samples inside the same window produce the same results. They also provide a theoretical analysis on the sampling cost and the ESC performance compared to SC. They empirically evaluate ESC on multiple reasoning benchmarks, and demonstrate that ESC achieves comparable accuracies to SC, while the number of samples notably reduces.", "questions": "1. Please clarify the novelty of this work. In particular, discuss and compare the approach to [1].\n\n2. Show this comparison in Table 1 for smaller sampling sizes, e.g., those in Table 2, and see if the performance improvement achieved by ESC can be more significant.\n\n3. Explain and fix issues in Table 1. For example, the SQA results of L-SC are generally much higher than SC, which look problematic. Also, it is confusing to list L in the table without additional notes, as L represents the sample size, while all other rows represent the task accuracies.\n\n[1] Aggarwal et al., Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning with LLMs, EMNLP 2023.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. ESC is a simple yet effective adaptation of the original self-consistency to reduce the sampling cost.\n\n2. The ablation studies and theoretical analysis show that ESC is generally applicable to different benchmarks, and stays effective with different setups.", "weaknesses": "1. The novelty of this work is unclear. [1] already proposed an adaptation of self-consistency to reduce the sampling cost, but this work did not cite and discuss this prior work. Without a thorough discussion and direct comparison, it is unclear whether ESC is more effective.\n\n2. In Table 1, when comparing ESC and L-SC, the performance difference is generally small. The reason can be that the improvement of SC saturates when the sample size increases, thus reducing the sampling size also does not drastically degrade the performance for SC. It is helpful to show this comparison for smaller sampling sizes, e.g., those in Table 2, and see if the performance improvement achieved by ESC can be more significant.\n\n3. There are some issues in Table 1. For example, the SQA results of L-SC are generally much higher than SC, which look problematic. Also, it is confusing to list L in the table without additional notes, as L represents the sample size, while all other rows represent the task accuracies.\n\n[1] Aggarwal et al., Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning with LLMs, EMNLP 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A8jimmXNql", "reviewer": "Reviewer_J879", "summary": "The paper proposes to use an early stopping criterion, based on answer entropy, when sampling alternative answers from a LLM in a self-consistency (SC) setting. SC is a form of ensemble answering, where multiple answers are sampled and a vote decides on the final answer. With early stopping answers are sampled window-wise iteratively until the whole window contains the same answer. Experiments show that this can reduce the number of necessary calls to a LLM while maintaining similar accuracy in reasoning benchmarks.", "questions": "No specific questions", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "LLMs are a popular topic currently and their execution is costly, either in monetary terms or computationally. Therefore, it is a good approach to reduce the number of calls necessary, as is proposed in the paper.\nIt is also a positive thing that existing proven techniques and statistical approaches are re-visited and used in these settings, such as early stopping or using answer entropy as a cut-off criterion.\nThe experimental evaluation confirms the suitability of the approach over the more exhaustive standard SC technique. Experiments are extensive and consider many facets of the proposed approach.", "weaknesses": "The contribution is not particularly strong. Early stopping or using the confidence respectively the variation in multiple answers in an ensemble of answers is a well known technique. While we have (maybe, I'm not sure) not seen this in LLM sampling, it is not a particularly strong contribution in the context of an ICLR paper.\n\nI'm also not sure we actually need the notion of the window in the method or if other statistical measurements of the confidence resp. variability  could be used to determine the cut-off point. Unfortunately, this has not been discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2E5rjpfmQJ", "reviewer": "Reviewer_rrBP", "summary": "The paper presents a new technique called early-stopping self-consistency (ESC) aimed at improving the computational efficiency of machine learning models, particularly in the context of complex reasoning tasks. Leveraging the essence of Chain-of-thought Reasoning and Self Consistency, the authors introduce ESC as a mechanism to strike a balance between computational cost and performance. Through extensive experiments, the paper claims significant reduction in computational overhead without a noticeable drop in performance.", "questions": "The Early-Stop Consistency (ESC) strategy is an optimized or \"pruned\" version of the Self-Consistency (SC) method, and its effect is not improved compared to SC. From this point of view, the method is lack of novelty. The primary innovation of ESC lies not in a theoretical advance but in its practical utility. It addresses real-world constraints by optimizing the balance between computational expenditure and performance fidelity.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The introduction of ESC offers a fresh perspective in the realm of efficient machine learning algorithms.\nQuality: The experimental setup, including testing on six benchmarks, demonstrates the thoroughness of the research.\nClarity: The paper, for the most part, is well-written and concepts are explained clearly.", "weaknesses": "Comparison with State-of-the-art: It would be helpful to see direct comparisons with current state-of-the-art methods in terms of efficiency and performance.\nGeneralizability: The paper could discuss potential limitations or scenarios where ESC might not be the optimal solution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KuKtlTzhnY", "reviewer": "Reviewer_UrCF", "summary": "To address the issue of high costs associated with self-consistency (SC), this paper introduces an approach called Early-Stop Self-Consistency (ESC). ESC incorporates an early-stop strategy into SC to reduce the overall number of samples needed. The method achieves this by dividing the large sample size used in SC into smaller sequential windows, and it stops sampling when all answers within a window are the same. Additionally, the paper presents a control scheme for ESC that dynamically selecting the size of window and maximum sampling times for different tasks and models. The effectiveness and reliability of ESC are supported by solid theoretical guarantee and extensive experiments. The empirical results demonstrate that ESC significantly reduces the average number of samples required in SC across six benchmark tasks, all while maintaining comparable performance levels.\n\nContributions: \n(1) This paper introduces an early-stop self-consistency method (ESC) to significantly reduce the computational cost of self-consistency while maintaining comparable performance.\n(2) This paper also puts forth a control scheme for ESC that assists in the selection of an optimal window size and maximum sampling times, considering the sampling budget and performance requirements.\n(3) Furthermore, this paper offers ample theoretical evidence to uphold the reliability of ESC.", "questions": "Question:\n\n(1) In the \"SQA\" dataset, Lˆ-SC outperforms both SC and ESC, even though SC has a larger sample size. If there are no data errors, is there any possible reasonable explanation?\n \nSuggestion:\n\n(1) In Table 1, the accuracy of Lˆ-SC seems decreases slightly (less than 0.5%) in more than half situations. Therefore, it might not be accurate to claim \"a large margin\", as the paper does, that \"We also test SC with Lˆ as the sampling size (Lˆ-SC), whose accuracy drops by a large margin.\".", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The method is simple and effective.\n\n(2) It is backed by a solid theoretical foundation.\n\n(3) Extensive experiments have been conducted to confirm its effectiveness and reliability.", "weaknesses": "(1) A related paper with a similar idea, called \"Let’s Sample Step by Step: Adaptive-Consistency for Efficient Reasoning with LLMs\" (https://arxiv.org/pdf/2305.11860.pdf), was not referenced.\n\n(2) In Table 1, there appear to be inaccuracies in some of the results highlighted in green. For instance, in the row labeled \"Lˆ-SC (GPT4)\" and the column labeled \"SQA,\" the value \"(-0.27)\" should actually be \"(+0.87)\" because the correct difference is 0.78 (81.42 - 80.55 = 0.78). Similar issues can be found in the \"SQA\" column. Additionally, it's puzzling that in the \"SQA\" dataset, Lˆ-SC outperforms SC, even though SC has a larger sample size. This phenomenon requires further explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)