Elamur Research⌕
☰
home / papers / 2023 / Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models

Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models

Paper · 2023 · Soochan Lee and Gunhee Kim

Summary

Writing out intermediate steps (Chain of Thought) helps language models with multi-step reasoning. For hard problems, though, those steps can grow far beyond a model's maximum context window. Rather than extending the window, Lee and Kim propose Recursion of Thought (RoT), a model-agnostic inference scheme. The model emits special tokens (GO, STOP, THINK, and TAIL for tail recursion) that open each subproblem in a fresh, separate context. The sub-answer that comes back is substituted where THINK was produced. Training is fully supervised. Ground-truth decomposition traces, modeled on human procedures such as school arithmetic, become target sequences. A standard next-token loss is applied, with padded positions ignored. The authors also build a synthetic benchmark of eight arithmetic and algorithmic tasks whose solutions can exceed 100K tokens. With RoT, three kinds of models reach near-perfect accuracy:

  • fine-tuned GPT-3;
  • a tiny Transformer trained from scratch;
  • a tiny LSTM trained from scratch.

On the same problems, direct answering collapses and CoT no longer fits in context. The work points to multi-context reasoning as a complementary route to scaling LM reasoning.

Key points

  • Benchmark tasks: four arithmetic operations (adding, subtracting, multiplying, and dividing numbers) plus four algorithmic problems: finding the longest common or longest palindromic subsequence, solving 0-1 knapsack, and ordering matrix chain multiplication. Everything is pure sequence modeling with no calculator. A problem counts as solved only if every intermediate step and the final answer are correct.
  • GPT-3 setup and results:
    • Fine-tuned via the OpenAI API for 10K steps with batch size 256, under a 2048-token context limit.
    • With RoT it nearly solves problems such as 48-digit addition/subtraction and 16-digit multiplication/division.
    • For reference, Minerva reportedly gets about 80% on 10-digit and 20% on 18-digit addition.
  • Tiny models:
    • A 536K-parameter Transformer (context 2048) and a 272K-parameter LSTM (context 512), both with no pre-training.
    • Each setting is run 8 times and tested on 30K problems.
    • The Transformer handles up to 64-digit addition/subtraction and 32-digit multiplication/division.
  • Baselines: Without Thought (WT), which answers directly, and a scratchpad-style CoT built by flattening the same recursion into one context. WT accuracy drops fastest as difficulty grows. CoT is accurate but limited to small problems by context size.
  • Limitations:
    • RoT needs supervised traces; the authors' prompting attempts with GPT-3 gave unsatisfactory accuracy.
    • All tasks are synthetic.
    • RoT gives no length generalization: training on 8-digit multiplication does not transfer to 16-digit.

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

🎓Seoul National UniversitySeoul · South Korea47 works · 46,072 citations🏢LG AI ResearchSeoul · South Korea10 works · 410 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 2Research subjects and languages the work is about.Language models & pretraining · 4,145 worksReasoning · 1,948 works

Cite

Cite as Soochan Lee and Gunhee Kim. 2023. Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models. Findings of the Association for Computational Linguistics: ACL 2023.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2023.findings-acl.40 · arXiv 2306.06891

@inproceedings{lee2023recursion,
  title = {{Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models}},
  author = {Soochan Lee and Gunhee Kim},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2023},
  year = {2023},
  doi = {10.18653/v1/2023.findings-acl.40},
  eprint = {2306.06891},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2023.findings-acl.40}
}

References

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

  1. Jonathon Cai, Richard Shin, and Dawn Song. 2017. Making neural programming architectures generalize via recursion. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. find
  2. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek B Rao, Parker Barnes, Yi Tay, Noam M. Shazeer, Vinodkumar Prabhakaran… — PaLM: Scaling Language Modeling with Pathways
  3. Dheeru Dua, Shivanshu Gupta, Sameer Singh, and Matt Gardner. 2022. Successive prompting for decomposing complex questions. ArXiv, abs/2212.04092. find
  4. Roy Fox, Richard Shin, Sanjay Krishnan, Ken Goldberg, Dawn Song, and Ion Stoica. 2018. Parametrized hierarchical procedures for neural programming. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. Ope… find
  5. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. find
  6. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9:1735– 1780. find
  7. Tushar Khot, H. Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. 2022. Decomposed prompting: A modular approach for solving complex tasks. ArXiv, abs/2210.02406.
  8. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
  9. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. ArXiv, abs/2205.11916.
  10. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Te-jani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and… — PyTorch: An Imperative Style, High-Performance Deep Learning Library
  11. Thomas Pierrot, Guillaume Ligner, Scott E. Reed, Olivier Sigaud, Nicolas Perrin, Alexandre Laterre, David Kas, Karim Beguir, and Nando de Freitas. 2019. Learning compositional neural programs with recursive tree search and planning. In Advances in Neural Information Processing Systems 32: Annual Con… find
  12. Scott E. Reed and Nando de Freitas. 2016. Neural programmer-interpreters. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. find
  13. Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. 2020a. Long range arena: A benchmark for efficient transformers. ArXiv, abs/2011.04006.
  14. Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. 2020b. Efficient transformers: A survey. ACM Computing Surveys, 55:1 – 28.
  15. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017,…
  16. Aitor Lewkowycz, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. 2022. Solving quantitative reasoning problems with language models. A…
  17. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning in large language models. ArXiv, abs/2201.11903.
  18. Chengtao Li, Daniel Tarlow, Alexander L. Gaunt, Marc Brockschmidt, and Nate Kushman. 2017. Neural program lattices. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. find
  19. Denny Zhou, Nathanael Scharli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Olivier Bousquet, Quoc Le, and Ed Huai hsin Chi. 2022. Least-to-most prompting enables complex reasoning in large language models. ArXiv, abs/2205.10625.
  20. Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. 2021. Show your work: Scratchpads for intermediate computation with language models. ArXiv, abs/2112.00114.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lee-2023-recursion-thought-divide-conquer-approach/