Elamur Research
☰
home / papers / 2022 / Least-to-most prompting enables complex reasoning in large language models

Least-to-most prompting enables complex reasoning in large language models

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/2205.10625

Summary

Chain-of-thought prompting works well when test problems look like the worked examples in the prompt. It struggles when test problems are harder than those examples, for instance longer inputs or new combinations of known parts (easy-to-hard generalization). Zhou et al. from Google Research propose least-to-most prompting to fix this. It runs in two few-shot stages and needs no training or finetuning. First, the model splits a hard question into a sequence of simpler subquestions. Then it answers them in order, and each prompt includes the answers already produced. The authors test the method with GPT-3 code-davinci-002 on three task types: symbolic manipulation (last-letter concatenation), compositional generalization (SCAN), and math word problems (GSM8K, DROP). Least-to-most prompting handles problems much harder than its examples. On SCAN it scores at least 99% on every split, including the length split, using only 14 exemplars. This matters because it shows that good prompt design alone can give strong generalization to harder inputs. Specialized models that solve SCAN need over 15,000 training examples.

Key points

  • Method: a decomposition prompt produces the subproblems, then a solving prompt answers them one at a time. Each step adds the previous subquestion–answer pairs to the prompt, so the examples teach a base case plus a recursive step. The method can be combined with chain-of-thought or self-consistency, and for some tasks both stages fit in a single pass.
  • Last-letter concatenation: test lists were built from Wiktionary words, with 500 lists for each length from 4 to 12. At length 12, least-to-most scores 74.0%, chain-of-thought 31.8% (up to 38.4% with 8 independent exemplars), and standard prompting 0%.
  • SCAN: with least-to-most, code-davinci-002 reaches at least 99% accuracy on all splits, versus about 16% for chain-of-thought on the length split.
  • Math reasoning (GSM8K, DROP): the gains are smaller on GSM8K overall (about 62% vs 61%) but larger on problems that need many solution steps. On DROP the improvement is clearer.
  • The name comes from educational psychology, where it means helping a learner with a sequence of prompts that grows step by step. The paper's appendix includes all the prompts.

Note: the paper text you sent had its middle section cut out. The SCAN figure of at least 99% on every split comes from the abstract you provided. The other numbers in the Math reasoning point (GSM8K, DROP) and the about-16% SCAN figure for chain-of-thought come from my own knowledge of the paper, not from your excerpt, so please check them against the full PDF before adding this to the library.

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

Fields: Mathematics & statistics

Cited by

830 papers of our library cite it (of the 140673 whose bibliographies we read); 61 of them have a page here, 769 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 2205.10625

@misc{anon2022least,
  title = {{Least-to-most prompting enables complex reasoning in large language models}},
  year = {2022},
  eprint = {2205.10625},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.10625}
}

References

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

  1. Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. Learning to recombine and resample data for compositional generalization. In International Conference on Learning Representations, 2021. find
  2. Jacob Andreas. Good-enough compositional data augmentation. In Annual Meeting of the Association for Computational Linguistics, 2020. find our card
  3. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020. find
  4. Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. Compositional generalization via neural-symbolic stack machines. Advances in Neural Information Processing Systems, 33:1690–1701, 2020. find
  5. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. PaLM: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022. find
  6. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. find our card
  7. Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In International Conference on Learning Representations, 2019. find
  8. Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs. arXiv preprint arXiv:1903.00161, 2019. find our card
  9. 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. Transactions of the Association for Computational Linguistics (TACL), 2021. find
  10. Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. Permutation equivariant models for compositional generalization in language. In International Conference on Learning Representations, 2020. find
  11. Jonathan Herzig and Jonathan Berant. Span-based semantic parsing for compositional generalization. In Annual Meeting of the Association for Computational Linguistics, 2021. find
  12. Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measuring compositional generalization: A comprehensive method on realistic data. International Conference on Learning Represen… find
  13. Yoon Kim. Sequence-to-sequence learning with latent neural grammars. Advances in Neural Information Processing Systems, 34, 2021. find
  14. Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In International conference on machine learning, pp. 2873–2882. PMLR, 2018. find
  15. Brenden M Lake. Compositional generalization through meta sequence-to-sequence learning. Advances in neural information processing systems, 32, 2019. find
  16. Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hestness. Compositional generalization for primitive substitutions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4… find
  17. Myrna E Libby, Julie S Weiss, Stacie Bancroft, and William H Ahearn. A comparison of most-to-least and least-to-most prompting on the acquisition of solitary play skills. Behavior analysis in practice, 1(1):37–43, 2008. find
  18. Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 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), 2017. find
  19. Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. Compositional generalization by learning analytical expressions. Advances in Neural Information Processing Systems, 33:11416–11427, 2020. find
  20. Maxwell Nye, Armando Solar-Lezama, Josh Tenenbaum, and Brenden M Lake. Learning compositional rules via neural program synthesis. Advances in Neural Information Processing Systems, 33:10832–10842, 2020. find
  21. Ethan Perez, Patrick Lewis, Wen-tau Yih, Kyunghyun Cho, and Douwe Kiela. Unsupervised question decomposition for question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 8864–8880, 2020. find
  22. Jake Russin, Jason Jo, Randall C O’Reilly, and Yoshua Bengio. Compositional generalization in a deep seq2seq model by separating syntax and semantics. arXiv preprint arXiv:1904.09708, 2019. find
  23. Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. Advances in Neural Information Processing Systems, 34, 2021. find
  24. Peter Shaw, Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. Compositional generalization and natural language variation: Can a semantic parsing approach handle both? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint… find
  25. Boshi Wang, Xiang Deng, and Huan Sun. Shepherd pre-trained language models to develop a train of thought: An iterative prompting approach. arXiv preprint arXiv:2203.08383, 2022a. find
  26. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022b. find our card
  27. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Brian Ichter, Fei Xia, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35, 2022. find our card
  28. Tongshuang Wu, Michael Terry, and Carrie Jun Cai. AI chains: Transparent and controllable human-AI interaction by chaining large language model prompts. In CHI Conference on Human Factors in Computing Systems, pp. 1–22, 2022. find
  29. Jingfeng Yang, Haoming Jiang, Qingyu Yin, Danqing Zhang, Bing Yin, and Diyi Yang. Seqzero: Few-shot compositional semantic parsing with sequential prompts and zero-shot models. arXiv preprint arXiv:2205.07381, 2022. find