Elamur Research⌕
☰
home / papers / 2024 / Zero-Shot Chain-of-Thought Reasoning Guided by Evolutionary Algorithms in Large Language Models

Zero-Shot Chain-of-Thought Reasoning Guided by Evolutionary Algorithms in Large Language Models

Paper · 2024 · Feihu Jin, Yifan Liu and Ying Tan

Summary

Standard zero-shot Chain-of-Thought (CoT) methods add one fixed trigger phrase to every question. The authors argue this is suboptimal, since no single wording suits every instance. They propose zero-shot EoT prompting, in which the LLM itself performs the operators of an evolutionary algorithm.

The method starts from two seed CoT promptings. The model applies LLM-Crossover and then LLM-Mutation to create new candidate instructions, chooses the one it judges best for the current question, and uses it to restate the problem. It then reasons toward an answer, which is retrieved with an ordinary answer-extraction prompt. Nothing is fine-tuned, and the whole search happens in discrete text space within a single prompt.

The method was tested with GPT-3.5-turbo and GPT-4 on ten arithmetic, commonsense and symbolic reasoning datasets. It outperformed zero-shot CoT, PS+ and RE2 prompting on every dataset and came close to few-shot CoT, especially for arithmetic and symbolic tasks. The work shows that per-instance prompt adaptation is achievable cheaply, without demonstrations or model training.

Key points

  • Pipeline: two initial CoT promptings → LLM-Crossover → LLM-Mutation → LLM self-selection of a prompt → problem rewriting → step-by-step reasoning → answer extraction.
  • Instruction wording matters (GPT-3.5-turbo): the best EoT instruction variant (P4) was compared with plain "Let's think step by step" (P1):
    • AddSub: 86.5 → 91.6
    • SVAMP: 79.0 → 82.8
    • AQuA: 55.3 → 63.1
    • GSM8K: 75.3 → 77.1
  • Comparisons: baselines were zero-shot CoT (Kojima et al.), PS+ / Plan-and-Solve (Wang et al.) and RE2 (Xu et al.), with few-shot CoT used as a reference point.
  • Code: released on GitHub as stan-anony/Zero-shot-EoT-Prompting.
  • Limitations: experiments cover only two OpenAI API models because of cost. Few-shot settings and other evolutionary schemes, such as differential evolution, were not explored.

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

🎓Peking UniversityBeijing · China244 works · 39,359 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksReasoning · 1,426 works

Cite

Cite as Feihu Jin, Yifan Liu and Ying Tan. 2024. Zero-Shot Chain-of-Thought Reasoning Guided by Evolutionary Algorithms in Large Language Models. arXiv:2402.05376.

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

@misc{jin2024zero,
  title = {{Zero-Shot Chain-of-Thought Reasoning Guided by Evolutionary Algorithms in Large Language Models}},
  author = {Feihu Jin, Yifan Liu and Ying Tan},
  year = {2024},
  doi = {10.48550/arxiv.2402.05376},
  eprint = {2402.05376},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2402.05376}
}

References

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

  1. Anonymous. 2024a. Large language models as optimizers. In The Twelfth International Conference on Learning Representations.
  2. Anonymous. 2024b. Large language models to enhance bayesian optimization. In The Twelfth International Conference on Learning Representations. find
  3. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chri… — Language Models are Few-Shot Learners
  4. Angelica Chen, David Dohan, and David R. So. 2023. Evoprompting: Language models for code-level neural architecture search. ArXiv, abs/2302.14838. — [arXiv:2302.14838](https://arxiv.org/abs/2302.14838) find
  5. 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. 2021. Training verifiers to solve math word problems. ArXiv, abs/2110.14168.
  6. Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. 2021. Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346– 361. find
  7. Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, Yujiu Yang, Tsinghua University, and Microsoft Research. 2023. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. ArXiv, abs/2309.08532. find
  8. Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. 2003. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary Computation, 11:1–18. find
  9. Noah Hollmann, Samuel Müller, and Frank Hutter. 2023. Large language models for automated data science: Introducing CAAFE for context-aware automated feature engineering. In Thirty-seventh Conference on Neural Information Processing Systems. find
  10. Mohammad Javad Hosseini, Hannaneh Hajishirzi, Oren Etzioni, and Nate Kushman. 2014. Learning to solve arithmetic word problems with verb categorization. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 523–533, Doha, Qatar. Association for Comp…
  11. Feihu Jin, Jinliang Lu, Jiajun Zhang, and Chengqing Zong. 2023. Instance-aware prompt learning for language understanding and generation. ACM Trans. Asian Low Resour. Lang. Inf. Process., 22(7):199:1– 199:18. find
  12. Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, volume 35, pages 22199–22213. Curran Associates, Inc.
  13. Rik Koncel-Kedziorski, Hannaneh Hajishirzi, Ashish Sabharwal, Oren Etzioni, and Siena Dumas Ang. 2015. Parsing algebraic word problems into equations. Transactions of the Association for Computational Linguistics, 3:585–597. find
  14. Brian Lester, Rami Al-Rfou, and Noah Constant. 2021. The power of scale for parameter-efficient prompt tuning. In EMNLP.
  15. Junzhi Li and Ying Tan. 2018. Loser-out tournament-based fireworks algorithm for multimodal function optimization. IEEE Transactions on Evolutionary Computation, 22(5):679–691. find
  16. Xiang Lisa Li and Percy Liang. 2021. Prefix-tuning: Optimizing continuous prompts for generation. In ACL. find
  17. Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 2017. Program induction by rationale generation: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 158–167, Vancouver… find
  18. Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew Soon Ong. 2023. Large language models as evolutionary optimizers. ArXiv, abs/2310.19046. — [arXiv:2310.19046](https://arxiv.org/abs/2310.19046) find
  19. Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang. 2021. Gpt understands, too. ArXiv, abs/2103.10385.
  20. Elliot Meyerson, M. Nelson, Herbie Bradley, Arash Moradi, Amy K. Hoover, and Joel Lehman. 2023. Language model crossover: Variation through few-shot prompting. ArXiv, abs/2302.12170. — [arXiv:2302.12170](https://arxiv.org/abs/2302.12170) find
  21. Melanie Mitchell. 1998. An introduction to genetic algorithms. MIT Press. find
  22. Jean-Baptiste Mouret. 2024. Large language models help computer programs to evolve. Nature, 625 7995:452–453. find
  23. OpenAI. 2022. Chatgpt: Optimizing language models for dialogue. In OpenAI Blog. find
  24. OpenAI. 2023. Gpt-4 technical report. abs/2303.08774.
  25. ArXiv, Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021. 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, pages 2080–2094, Online. A…
  26. Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco J R Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi, Josh Grochow, Andrea Lodi, Jean-Baptiste Mouret, Talia Ringer, and Tao Yu. 2023. Mat… — Mathematical Discoveries from Program Search with Large Language Models
  27. Subhro Roy and Dan Roth. 2015. Solving general arithmetic word problems. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1743–1752, Lisbon, Portugal. Association for Computational Linguistics.
  28. Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. 2023. Are emergent abilities of large language models a mirage? In Thirty-seventh Conference on Neural Information Processing Systems.
  29. Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019. 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,…
  30. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. Llama: Open and efficient foundation language models. CoRR, ab…
  31. Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. 2023a. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Lo… find
  32. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023b. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations.
  33. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824–24837. Curran Associates, Inc.
  34. Zhuofeng Wu, Sinong Wang, Jiatao Gu, Rui Hou, Yuxiao Dong, V. G. Vinod Vydiswaran, and Hao Ma. 2022. IDPG: an instance-dependent prompt generation method. CoRR, abs/2204.04497. find
  35. Xiaohan Xu, Chongyang Tao, Tao Shen, Can Xu, Hongbo Xu, Guodong Long, and Jian-Guang Lou. 2023. Re-reading improves reasoning in language models. ArXiv, abs/2309.06275. — [arXiv:2309.06275](https://arxiv.org/abs/2309.06275) find
  36. Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2023. Automatic chain of thought prompting in large language models. In The Eleventh International Conference on Learning Representations.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/jin-2024-zero-shot-chain-thought-reasoning/