Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning

Thank you for the positive and detailed review! We are very encouraged that you found our method to be simple, effective and robust. Below we address your comments.

Comparison with Adaptive-Consistency

Thanks for reminding and we will add citations to [1] and add more discussions on the novelty of our method:

(1) Having additional control scheme

Besides basic early-stopping self-consistency (ESC), we also propose its control scheme to dynamically choose the performance-cost balance. As we all know, along with the number of samples increases, performance will increase as well. For the realistic requirements, it is more practical to choose the affordable sample size rather than just try to maximize performance. We have derived the expectation of $\hat{L}$ (sampling number) and the upper bound of $\mathbb{E}(Q)$ (inconsistent probability). The experiments in Section 3.3 have shown that the predictions we obtain based on Equation 10 and Equation 14 are highly reliable for balancing sampling cost and voting performance.

(2) Less sampling cost

Adaptive-consistency (AC) generates samples step by step, which means each sample requires one input. Considering the demonstrations for in-context learning (usually 8 examples) have a lot of tokens, it will cost quite a portion of the budget. By contrast, ESC generates samples in multiple sampling windows, thus samples within one window can share the same input. Table 7 in updated paper shows that ESC can get higher accuracy with less sampling cost comparing with AC. A quick preview is below:

(3) No hyperparameters

It is necessary for AC to tune the hyperparameter, specifically the confidence threshold. But for proposed ESC, the stopping criterion needs no hyperparameter due to the most conservative strategy to maintain the performance, i.e., all the answers within a window are same. Thus ESC can be conducted directly for different tasks and models, without any validation set. Besides, section 3.2 has proved the robustness regrading to window size w and max sampling size L.

(4) More solid theoretical guarantees

We provide more solid theoretical guarantees than AC lying in two parts: firstly, we rigorously derive the theoretical upper bound of the probability being inconsistent with the case where sampling size is infinite (true distribution of the model predictions according to Equation 3). While AC only considers the condition with next n samples, which is less rigorous; secondly, the upper bound of ESC is much more tight than AC. According to Equation 8, the bound value is only in the interval of $\leq 4 \times 10^{-2}$ to $\leq 2 \times 10^{-5}$ when window size varies from 3 to 10. By comparison，the confidence threshold of AC is chosen as 95%.

Explanation and Fixing issues in Table 1

We apologize that we have filled in the inconsistent values about SQA. That is because the candidate answer for question in SQA is either 'True' or 'False', but there will be some cases that the model generates neither of them. So there are two ways to vote the final answer: one is regarding these noisy answers as another type, e.g. '-1', to be included for voting; the other is removing this type of answers and only voting 'True' or 'False'. Our first choice was to vote based on the former criterion, but later we realized that the latter one made more sense, but we have forgotten to correct some values. We have fixed this problem in the revision.

Modification of the description about Table 1

We thank you for your suggestion! We used the description "by a large margin" because we compared the performance degradation of L-SC with the change between SC and ESC. Sorry for misleading and we have modified the depiction. Here is the reason for this phenomenon: In the paper of vanilla self-consistency [2], the large improvements come from the comparison between single greedy sample and 40 samples. The author plotted the accuracy with respect to varying numbers of samples. Within a certain interval, the performance change is not significant either.

[1] Aggarwal et al., Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning with LLMs, EMNLP 2023.

[2] Wang et al., Self-consistency improves chain of thought reasoning in language models, ICLR 2023.

We thank your insightful comments! We understand your concerns, which are also very important to us. Below we clarify:

Comparison with state-of-the-art method

We thank you for this advice, which we believe helps strengthen our results. Per your suggestion, we conduct the experiment compared with Progressive-Hint Prompting (PHP) [1], a state-of-art method for arithmetic reasoning. In the updated paper, Table 9 from Appendix A.5, ESC (sampling size is 40) gets higher accuracy than PHP (greedy search) with less sampling cost. A quick preview is below:

Actually, ESC is a plug-and-play technique that can be incorporated with most of state-of-art methods, given that self-consistency (SC) is usually orthogonal to them. So we think it will be more meaningful to verify its generalization ability to SOTA methods by combining them. Also taking PHP for example in Table 10, when applying our ESC to PHP, the sampling cost drops significantly while the accuracy is basically unchanged. We believe results from the study can expand the scope of the impact of ESC.

Discussion of limitations

According to Table 1, the decrease in sampling number is relatively small for Llama-2 model and MATH dataset, respectively. These two findings may reveal that the effect of ESC will be less significant under very difficult tasks and low-capability models. It makes sense since the lower accuracy will lead to fewer opportunities to reach the stop criterion, and need more samples to vote the right answer.

Novelty of ESC

Although ESC can not improve the performance compared with original SC under the same max sampling size, it can be achieved with same practical sampling cost. So from this perspective, ESC can also be seen as an method to improving effectiveness because it can get higher accuracy when enlarge the max sampling size to reach the same cost. Beside, as mentioned above, the ESC is also a plug-and-play method that can be incorporated with other competitive methods. Although ESC is more about practical significance, we provide solid theoretical guarantees to support it with rigorous upper bound, making it a key contribution in this field.

[1] Zheng et al., Progressive-hint prompting improves reasoning in large language models, arXiv.2304.09797.

We thank your valuable comments! We understand your concerns, which are also very important to us. Below we clarify:

Contribution of our work

Firstly, the motivation of ESC is quite straightforward and significant. Reducing inference costs is a crucial topic especially for LLMs. To this end, we propose a simple and effective method to considerably reduce the cost of SC without sacrificing performance. We conduct extensive experiments to confirm that ESC can robustly save cost considering different large models, tasks (even open-ended generation tasks), decoding settings, prompts, and combination with SOTA methods (e.g., PHP, in Appendix A.6). Although ESC is simple and intuitive, we provide solid theoretical guarantees for it, which means that ESC is not a naive and heuristic method but backed with rigorous upper bound. Beyond that, we further develop a control scheme to dynamically choose the performance-cost balance according to the sampling budget and performance requirements, which is also important for realistic applications.

Discussion on the choice of introducing observation window for the design of early-stopping strategy

We want to firstly clarify that using the consistency of samples within the window as cut-off point is also a strategy based on variability.

We design the stopping strategy with the introduction of window for the following two reasons:

(1) 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 a certain statistic and its corresponding threshold (hyper-parameter), which is hard to be determined in prior.

(2) We have actually considered using the normalized entropy of the sampled samples as the statistical value for cut-off. As shown in Table below (Figure 5 in the revised version for details) , we found that this method not only has the hyper-parameter problem mentioned above, but also has no advantage over ESC in terms of performance-cost tradeoff (they both outperform SC). 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 to early-stop without sufficient sampling.

Considering the above reasons, we chose the strategy presented. We have added this discussion in the revised version (A.4), thank you for your comments.

Thanks for your detailed feedback! We will address your comments below:

Comparison with Adaptive-Consistency and the novelty of our work

Thanks for reminding and we will add citations to [1] and add more discussions on the novelty of our method:

(1) Having additional control scheme

Besides basic early-stopping self-consistency (ESC), we also propose its control scheme to dynamically choose the performance-cost balance. As we all know, along with the number of samples increases, performance will increase as well. For the realistic requirements, it is more practical to choose the affordable sample size rather than just try to maximize performance. We have derived the expectation of $\hat{L}$ (sampling number) and the upper bound of $\mathbb{E}(Q)$ (inconsistent probability). The experiments in Section 3.3 have shown that the predictions we obtain based on Equation 10 and Equation 14 are highly reliable for balancing sampling cost and voting performance.

(2) Less sampling cost

Adaptive-consistency (AC) generates samples step by step, which means each sample requires one input. Considering the demonstrations for in-context learning (usually 8 examples) have a lot of tokens, it will cost quite a portion of the budget. By contrast, ESC generates samples in multiple sampling windows, thus samples within one window can share the same input. Table 7 in updated paper shows that ESC can get higher accuracy with less sampling cost comparing with AC. A quick preview is below:

(3) No hyperparameters

It is necessary for AC to tune the hyperparameter, specifically the confidence threshold. But for proposed ESC, the stopping criterion needs no hyperparameter due to the most conservative strategy to maintain the performance, i.e., all the answers within a window are same. Thus ESC can be conducted directly for different tasks and models, without any validation set. Besides, section 3.2 has proved the robustness regrading to window size w and max sampling size L.

(4) More solid theoretical guarantees

We provide more solid theoretical guarantees than AC lying in two parts: firstly, we rigorously derive the theoretical upper bound of the probability being inconsistent with the case where sampling size is infinite (true distribution of the model predictions according to Equation 3). While AC only considers the condition with next n samples, which is less rigorous; secondly, the upper bound of ESC is much more tight than AC. According to Equation 8, the bound value is only in the interval of $\leq 4 \times 10^{-2}$ to $\leq 2 \times 10^{-5}$ when window size varies from 3 to 10. By comparison，the confidence threshold of AC is chosen as 95%.

Experiments with smaller sampling size

We thank you for your insightful suggestion and we conduct experiments with smaller sampling sizes (L). From the results in updated paper, Table 8 in Appendix A.3, the absolute value of performance drop is still not significant. We believe there are two reasons for this phenomenon: (1) In the paper of vanilla self-consistency [2], the large improvements come from the comparison between single greedy sample and 40 samples. The author plotted the accuracy with respect to varying numbers of samples. Within a certain interval, the performance change is not significant either. (2) While the performance drop of Table 1 remains insignificant, the corresponding reduction of L decreases a lot compared with table 1, which proves that the interval with smaller L is more unsaturated. A quick preview is below:

Fixing issues in Table 1

We apologize that we have filled in the inconsistent values about SQA. That is because the candidate answer for question in SQA is either 'True' or 'False', but there will be some cases that the model generates neither of them. So there are two ways to vote the final answer: one is regarding these noisy answers as another type, e.g. '-1', to be included for voting; the other is removing this type of answers and only voting 'True' or 'False'. Our first choice was to vote based on the former criterion, but later we realized that the latter one made more sense, but we have forgotten to correct some values. We have fixed this problem in the revision.

As for the representation of L in Table 1, thanks for your advice and we have modified Table 1 to make it more reasonable for reading.

[1] Aggarwal et al., Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning with LLMs, EMNLP 2023.

[2] Wang et al., Self-consistency improves chain of thought reasoning in language models, ICLR 2023.