Elamur Research⌕
☰
home / papers / 2024 / Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning

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

Paper · 2024 · Yiwei Li, Peiwen Yuan, Shaoxiong Feng et al.

Summary

Self-consistency (SC) improves chain-of-thought reasoning by sampling many reasoning paths and taking a majority vote. Its cost grows linearly with the number of samples. For example, running the full MATH set with 64 samples through GPT-4 costs about $2000. The authors propose Early-Stopping Self-Consistency (ESC). ESC draws samples in small consecutive windows and stops once every answer in a window agrees, meaning the answer distribution's entropy is zero. If no window reaches agreement, sampling continues up to the usual maximum and all collected answers are voted on. This rule rests on the observation that correct answers tend to cluster while wrong ones scatter. ESC needs no training or labels and works with any model. The authors give a z-test bound on how often ESC's vote differs from full SC. They also offer a control scheme that uses the first window to predict cost and accuracy for different window sizes and sampling budgets. Experiments with GPT-4, GPT-3.5-Turbo and Llama-2 7b cover arithmetic, commonsense and symbolic tasks. ESC removes most of the sampling while accuracy stays essentially unchanged, which makes SC far more affordable.

Key points

  • Average sampling reductions with comparable accuracy:
    • MATH: −33.8%
    • GSM8K: −80.1%
    • StrategyQA: −76.8%
    • CommonsenseQA: −78.5%
    • Coin Flip: −84.2%
    • Last Letters: −67.4%
  • Theoretical guarantee: with window size w = 8, the chance that ESC's answer differs from SC's is at most about 2×10⁻³. This bound shrinks as w grows.
  • The control scheme estimates the answer distribution from the first window. From that estimate it predicts expected cost and accuracy, so users can choose w and the maximum sample size L to fit a budget.
  • ESC stays robust across sampling temperatures, nucleus-sampling p values, zero-shot prompting and different window sizes.
  • ESC also works alongside Progressive-Hint Prompting on GSM8K (GPT-3.5-Turbo). With a budget of 40 samples, it reaches 86.98% accuracy versus 87.00% for SC while averaging about 10.3 samples. Code and data are available at github.com/Yiwei98/ESC.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Beijing Institute of TechnologyBeijing · China45 works · 3,758 citations🏢Xiaohongshu (Little Red Book)Shanghai · China16 works · 210 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksComputer Vision and Pattern Recognition · 3,621 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,948 works

Cite

Cite as Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang and Kan Li. 2024. Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning. arXiv:2401.10480.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2401.10480 · arXiv 2401.10480

@misc{li2024escape,
  title = {{Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning}},
  author = {Yiwei Li, Peiwen Yuan, Shaoxiong Feng, Boyuan Pan, Xinglin Wang, Bin Sun, Heda Wang and Kan Li},
  year = {2024},
  doi = {10.48550/arxiv.2401.10480},
  eprint = {2401.10480},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2401.10480}
}

References

29 references, 19 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Pranjal Aggarwal, Aman Madaan, Yiming Yang, and Mausam. Let’s sample step by step: Adaptive-consistency for efficient reasoning with llms. CoRR, abs/2305.11860, 2023. doi: 10.48550/ARXIV.2305.11860. URL https://doi.org/10.48550/arXiv.2305.11860. — [doi:10.48550/arxiv.2305.11860](https://doi.org/10.48550/arxiv.2305.11860) ↗
  2. 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. Program synthesis with large language models. CoRR, abs/2108.07732, 2021. URL https://arxiv.org/abs/2108.07732. ↗
  3. Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, 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 experiments with GPT-4. CoRR, abs/23…
  4. 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 https://arxiv.org/abs/2110.1416… ↗
  5. 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.48550/arXiv.2301.12726. URL https://doi.org/10.48550/arXiv.2301.12726. ↗
  6. Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did aristotle use a laptop? A question answering benchmark with implicit reasoning strategies. Trans. Assoc. Comput. Linguistics, 9:346–361, 2021. doi: 10.1162/tacl\\ a\\ 00370. URL https://doi. org/10.1162/tacl_a_00370… find
  7. 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, NeurIPS Datasets and Benc…
  8. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020.
  9. OpenReview.net, 2020. URL https://openreview.net/forum?id=rygGQyrFvH. ↗
  10. Mohammad Javad Hosseini, Hannaneh 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 SIG…
  11. ACL, 2014. doi: 10.3115/v1/d14-1058. URL https://doi.org/10.3115/v1/d14-1058. ↗
  12. Siddhartha Jain, Xiaofei Ma, Anoop Deoras, and Bing Xiang. Self-consistency for open-ended generations. CoRR, abs/2307.06857, 2023. doi: 10.48550/arXiv.2307.06857. URL https://doi.org/10.48550/arXiv.2307.06857. — [doi:10.48550/arxiv.2307.06857](https://doi.org/10.48550/arxiv.2307.06857) ↗
  13. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In NeurIPS, 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/8bb0d291acd4acf06ef112099c16f326-Abstract-Conference.html. ↗
  14. Aitor Lewkowycz, 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. Solving quantitative reasoning problems with language models. In NeurIPS, 2022. UR…
  15. 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 llms by leveraging negative data. CoRR, abs/2312.12832, 2023. doi: 10.48550/ARXIV.2312.12832. URL https://doi.org/10.48550/arXiv.23… — [doi:10.48550/arxiv.2312.12832](https://doi.org/10.48550/arxiv.2312.12832) ↗
  16. Shen-Yun Miao, Chao-Chun Liang, and Keh-Yih 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, ACL 2020, Online, July 5-10, 2020, pp. 975–984. Association for Computational… find
  17. OpenAI. GPT-4 technical report. CoRR, abs/2303.08774, 2023. doi: 10.48550/arXiv.2303.08774. URL https://doi.org/10.48550/arXiv.2303.08774. ↗
  18. Athanasios Papoulis. Probability and statistics. Prentice-Hall, Inc., 1990. find
  19. 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, 2021…
  20. 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, Portugal, September 17-21, 2015, pp. 1743–1752. The Association for Computational Linguistics, 2015. doi: 10.18653/v1/d15-…
  21. Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqa: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-…
  22. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller,… — Llama 2: Open Foundation and Fine-Tuned Chat Models
  23. 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 on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023.
  24. OpenReview.net, 2023. URL https://openreview.net/pdf?id=1PL1NIMMrw. ↗
  25. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In NeurIPS, 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4-Abstra… ↗
  26. Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26:289–315, 2007. find
  27. Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li. Progressive-hint prompting improves reasoning in large language models. CoRR, abs/2304.09797, 2023. doi: 10.48550/arXiv.2304.09797. URL https://doi.org/10.48550/arXiv.2304.09797. ↗
  28. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, I…
  29. OpenReview.net, 2023. URL https://openreview.net/pdf?id=WZH7099tgfM. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-2024-escape-sky-high-cost-early/