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

Abstract: Generating intermediate steps, or Chain of Thought (CoT), is an effective way to significantly improve language models’ (LM) multi-step reasoning capability. However, the CoT lengths can grow rapidly with the problem complexity, easily exceeding the maximum context size. Instead of increasing the context limit, which has already been heavily investigated, we explore an orthogonal direction: making LMs divide a problem into multiple contexts. We propose a new inference framework, called Recursion of Thought (RoT), which introduces several special tokens that the models can output to trigger context-related operations. Extensive experiments with multiple architectures including GPT-3 show that RoT dramatically improves LMs’ inference capability to solve problems, whose solution consists of hundreds of thousands of tokens.

## introduction recently, lms have become a prominent direction to solve reasoning. given a question sequence, the models are tasked to predict the following answer sequence. one recent line of research for reasoning with lms is chain of thought (cot) generation @xcite @xcite . in cot generation, complex reasoning problems are solved by generating intermediate reasoning steps, or chain of thought, before producing the final answer. this allows the problem's complexity to be spread across multiple token generations, making each generation more straightforward given the previous tokens. although cot dramatically increases reasoning accuracy, there is a critical issue that limits its utility: the effective context size of sequence models cannot grow unbounded. context refers to the set of input tokens that a model is conditioned on when generating output. practically, all sequence models have a limit on the maximum context length due to various reasons. for instance, transformers @xcite suffer from a quadratic computational cost on the context length, and rnns @xcite struggle with long-term dependency modeling. therefore, even the state-of-the-art lms limit the maximum context length to a few thousand tokens. however, complex real-world problems may take even millions of tokens of reasoning steps to reach the answer. while there has been extensive research on transformers with longer contexts @xcite , we explore an orthogonal direction: divide and conquer. our new model-agnostic inference framework recursion of thought (rot) lets an lm recursively create multiple contexts by producing special tokens. therefore, even if a problem's solution exceeds the maximum context size, the model can divide it into multiple short contexts. we show the potential of rot with our new synthetic benchmark consisting of eight arithmetic and algorithmic tasks. one can easily adjust the difficulty of the tasks to produce problems with extremely long (100k+ tokens) reasoning steps. without any taskspecific component, such as a calculator, the models with rot can easily learn to solve extremely complex problems whose solutions consist of hundreds of thousands of tokens. to the best of our knowledge, no previous work comes close to handling this scale of reasoning procedures. since rot is an early exploration in this direction, it needs several improvements to be applied to more practical scenarios. nonetheless, the impressive experimental results suggest that the multi-context paradigm of rot might play an important role in future lms. in the supplementary file, we provide our pytorch @xcite implementation that can fully reproduce the experiments. guage models to produce cot can largely improve reasoning accuracy. in the paper, the authors also mention the confined context size as a major hurdle to scaling their method. more recently, it has been found that sufficiently large pre-trained language models can be induced to produce cot, by simply tuning the prompt @xcite . several concurrent works extend cot prompting to decompose complex problems into smaller problems @xcite @xcite . although these works also share the principle of divide and conquer like rot, they mostly focus on improving the reasoning accuracy of relatively small problems whose solutions usually can fit in a single context. on the other hand, we focus on solving problems that the solutions are orders of magnitude longer than the context size. more detailed description of related work can be found in appendix a. ## conclusion we explored the novel idea of making lms produce special tokens to create multiple contexts. following the principle of divide and conquer, lms with rot can solve extremely complex problems that have never been handled by any lm. we believe the core idea of utilizing multiple contexts has a great potential and can play an essential role in future language models.