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

Self-consistency (SC) has been a widely used decoding strategy for chain-ofthought 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 * . 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 a simple decoding strategy called self-consistency (SC) to further improve reasoning performances, which takes advantage of the fact that complex reasoning tasks typically allow for more than one reasoning paths leading to the correct answer. In contrast to the standard chainof-thought prompting 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 votingbased scheme. However, despite generally leading to improvements, the SC strategy incurs a significant overhead proportional to the number of sampled outputs, under the assumption that the sampled outputs are of equal length. Taking the most popular arithmetic reasoning benchmark for LLMs as an example, testing the entire MATH dataset with SC (sampling size is 64 as Lewkowycz et al. ( 2022 )) costs about 2000$ through GPT-4 API, which is a significant burden for many researchers and organizations. Therefore, it is essential to 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 under a specific sampling temperature. Then the most † Equal contributions. ‡ Corresponding author. * Our code and data have been released on https://github.com/Yiwei98/ESC .