Announcing our new Paper: The Prompt Report, with Co-authors from OpenAI & Microsoft!
Check it out →
Learn Prompting◆ Recursion of Thought Prompting
Last updated on September 4, 2024 by Bhuwan Bhatt- Recursion of Thought (RoT) prompting overcomes context length limitations by using a divide-and-conquer strategy, breaking down complex problems into smaller sub-problems.
- RoT solves large-scale tasks by processing parts of a problem in separate contexts and then aggregating the results to form the final answer.
- Training required: Unlike Chain-of-Thought prompting, RoT requires supervised training before use, making it more resource-intensive.
- Key applications include tasks like multi-digit arithmetic and sequence problems that exceed the context window limits of current LLMs.
- Limitations include the need for prior training and lack of length generalization, meaning models trained with RoT do not automatically adapt to larger problems.
What is Recursion of Thought Prompting?
One of the major limitations of present-day Large Language Models (LLMs) is that they are limited by their context length. The table below shows the context limit of today's most advanced language models:
| Model Name | Context Window |
|---|---|
| gpt-4o | 128,000 tokens |
| gpt-3.5-turbo | 16,385 tokens |
| Gemini 1.0 | 32,000 tokens |
As a result, for complex problems, the context length for Chain-of-Thought (CoT) prompting1 can grow exponentially and exceed the maximum allowed length.
Recursion of Thought (RoT) prompting2 is an inference framework that uses the divide and conquer strategy to divide a problem into multiple sub-problems, solve them in separate contexts, and aggregate the answer from each into a final answer.
How to Use Recursion of Thought Prompting?
Unlike other methods in this section, you cannot simply prompt the LLM to use recursive divide and conquer. For the Recursion of Thought to work, you must first train the model using a training dataset. You can train an LLM or any language model, as RoT is a model-agnostic framework.
Training Data sample for Recursion of Thought2
During inference, RoT utilizes special tokens - GO, THINK, STOP - for recursive context control. As expected, GO and STOP mark the start and end of a problem sequence. When the model needs to decompose the problem into a simpler version, the subproblem, and solve it, it produces a THINK token. It then substitutes the solution to the subproblem back into the problem sequence. The process continues till we get the final solution.
What Are Recursion of Thought Results?
-
The authors train GPT-3 using the RoT framework for 48-digit addition/subtraction and 16-digit multiplication/division. CoT cannot solve those problems due to the context limit of 2048 tokens in GPT-3. Consequently, there is no apples-to-apples comparison. However, GPT-3 trained with RoT achieves near-perfect accuracy in both tasks.
-
Results are similar for other problems such as Longest Common Subsequence (LCS), G.2.2 Longest Palindromic Subsequence (LPS), 0-1 knapsack, and Matrix Chain Multiplication (MCM). While CoT cannot solve them beyond a certain complexity, RoT achieves a perfect score.
Limitations of Recursion of Thought Prompting
There are a few limitations to RoT that make it difficult for people to adopt the framework:
- RoT requires supervised training before you can use it to run inference. This can be a costly and time-consuming procedure.
- RoT is built with a goal to support context length greater than 100K. For common problems, this can be an overkill.
- Unlike humans, RoT is incapable of length generalization. Training on 8-digit multiplication with RoT cannot make a model generalize to 16-digit multiplication.
Conclusion
For complex problems requiring a large context length, CoT length grows rapidly with increased complexity. Models like GPT-3 cannot accommodate such a huge context length. The RoT framework allows language models with limited context length to solve complex frameworks. However, RoT requires training the model using a labeled dataset before using it for inference. As such, RoT can be a good alternative to expensive and large language models like GPT-4.