Recursion of thought: a complete guide

Chain-of-thought reasoning works until the reasoning gets long. Write out every step of a 48-digit multiplication and the scratch work blows past the context window before you reach the answer. Recursion of Thought (RoT) flips the fix: instead of stretching the window, it teaches the model to spawn a fresh context for each sub-problem, solve it there, and paste the answer back. In the original paper, Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models (Soochan Lee and Gunhee Kim, Findings of ACL 2023), this let a fine-tuned GPT-3 hit near-perfect accuracy on problems whose full solution runs to hundreds of thousands of tokens.

See it work

Take a hard multiplication. Plain chain-of-thought tries to keep every partial product and carry in one window, and runs out of room:

Prompt: Compute 7821 x 4093, showing all work.

Output (chain-of-thought):
7821 x 3 = 23463
7821 x 90 = 703890
7821 x 0 = 0
7821 x 4000 = 31284000
Now add 23463 + 703890 + ... [context window full — truncated]

RoT trains the model to delegate instead. When it meets a sub-problem it can't finish inline, it emits a special token, hands that sub-problem to a brand-new context, and waits for the result:

Prompt: Compute 7821 x 4093.

Context A (parent):
  7821 x 4093 = ?
  -> needs: 7821 x 3, 7821 x 90, 7821 x 4000, then a sum
  THINK( 7821 x 3 )        -> spawns Context B
  THINK( 7821 x 90 )       -> spawns Context C
  THINK( 23463 + 703890 )  -> spawns Context D
  ...
  STOP -> 32011953

Context B (child):  7821 x 3 = 23463  STOP
Context C (child):  7821 x 90 = 703890  STOP

Each context only ever holds one small problem, so no single window overflows. The parent stitches the returned answers together. Same arithmetic, but the work is spread across many short contexts instead of one impossible one.

The mental model

Think of how a recursive function works in code. A function that can't solve a big case directly calls itself on smaller cases, gets their return values, and combines them. RoT gives a language model that same call / return ability: the THINK token is the function call, the spawned context is the stack frame, and the answer it sends back is the return value.

RoT is divide-and-conquer for reasoning: when the scratch work won't fit, don't make the page bigger — tear off a sub-problem, solve it on a fresh page, and bring the answer home.

How it works

RoT is an inference framework wrapped around a model that's been fine-tuned to emit three control tokens. A small driver loop watches the output stream and acts on those tokens.

The steps:

1. Start a context. The problem is placed in an empty context, opened with a GO token.
2. Generate. The model writes reasoning token by token, exactly like chain-of-thought.
3. Delegate on THINK. When the model decides a piece is its own sub-problem, it emits THINK around that sub-problem. The driver pauses the parent.
4. Recurse in a clean context. The captured sub-problem is dropped into a new empty context and solved by the same procedure. This nests as deep as needed.
5. Return on STOP. A child finishes with STOP. The driver copies its answer back into the parent stream, right where the THINK was.
6. Continue and finish. The parent resumes with the answer filled in, and eventually emits its own STOP.

A fourth token, TAIL, marks tail-recursion: it lets a problem hand off to its continuation without growing the call stack, so deep chains don't overflow.

Why it works

Where it shines

RoT pays off when the correct solution is long and has a recursive or divide-and-conquer shape. The paper proves it on two task families:

• Arithmetic — addition, subtraction, multiplication, and division on long integers. A fine-tuned GPT-3 reached near-perfect accuracy on 48-digit addition and subtraction and 16-digit multiplication and division, where chain-of-thought failed because the work exceeded the 2048-token window. The tiny from-scratch models were pushed even further — 64-digit addition/subtraction and 32-digit multiplication/division (a 32-digit number won't even fit a 64-bit integer).
• Algorithmic dynamic programming — longest common subsequence (LCS), longest palindromic subsequence (LPS), 0-1 knapsack, and matrix chain multiplication (MCM). These have solutions that naturally recurse into sub-instances, which is exactly RoT's strength. The catch: naive recursion can explode — the LCS of two length-32 sequences would spill past 10^18 tokens if every sub-call recomputed from scratch — so RoT pairs with dynamic-programming memoization to reuse solved sub-problems instead of re-deriving them.

Across every experiment, RoT let the models solve instances whose full solution spans tens to hundreds of thousands of tokens — far beyond what a single context could ever hold. The headline isn't a few points of accuracy; it's that previously impossible problem sizes became solvable.

When to use it (and when not)

Reach for RoT when:

• The full solution provably exceeds the context window.
• The problem has a recursive or divide-and-conquer structure (arithmetic, DP, parsing, tree search).
• You can build supervised traces that show where to split.
• Correctness on huge instances matters more than setup cost.

Skip it when:

• The reasoning fits comfortably in one window — chain-of-thought is simpler and cheaper.
• You can't or won't fine-tune. RoT is not a pure-prompting trick; it needs training on labeled decompositions.
• The problem doesn't decompose cleanly into self-similar parts.

Model fit. RoT needs a model you can fine-tune to emit the control tokens reliably. The paper showed it on a 536K-parameter Tiny Transformer (2048-token context), a 272K-parameter Tiny LSTM (512-token context), and a fine-tuned GPT-3. A frozen, prompt-only API model can imitate the idea but won't place the tokens dependably.

When to escalate. If you can't fine-tune, step down to prompting-only decomposition (Least-to-Most, Decomposed Prompting). If the problem doesn't recurse, a longer-context model or retrieval is the better lever.

Structure and components

An RoT setup has three pieces:

1. The control tokens — GO (open a context), THINK (delegate a sub-problem), STOP (return an answer), and TAIL (tail-call without stack growth).
2. The fine-tuned model — trained on ground-truth traces so it learns where to emit THINK and STOP.
3. The driver loop — plain code that watches the token stream, spawns child contexts on THINK, and substitutes returned answers back into the parent on STOP.

The prompt format is just the problem in a fresh context; all the structure lives in the learned tokens, not in a hand-written template.

The core mechanism

The driver is a short recursive function. It runs the model on a context, and whenever the model asks to think, it solves that sub-problem in a clean context first:

def rot_solve(problem, model):
    context = [GO] + tokenize(problem)
    while True:
        token = model.generate_next(context)
        if token == THINK:
            sub = read_until_close(model, context)   # the delegated sub-problem
            answer = rot_solve(sub, model)            # fresh context, recurse
            context += tokenize(answer)               # paste the result back
        elif token == STOP:
            return read_answer(context)               # return to the caller
        else:
            context.append(token)                     # ordinary reasoning token

Because each rot_solve call starts a brand-new context, the parent's length never grows without bound — the long total solution is split across the call stack instead of one window.

Configuration

Implementation workflow

1. Confirm the structure. Check the task decomposes into self-similar sub-problems. If not, RoT is the wrong tool.
2. Define the split. Decide what counts as a sub-problem (a partial product, a smaller DP cell) and write a generator for ground-truth traces with THINK/STOP in the right places.
3. Add the tokens. Reserve GO, THINK, STOP, TAIL in the vocabulary.
4. Fine-tune. Train on the traces until the model places control tokens reliably. The paper fine-tuned GPT-3 for 10K steps at batch size 256.
5. Wrap with the driver. Implement the recursive loop that spawns and resolves child contexts.
6. Evaluate by difficulty. Test across problem sizes, especially sizes whose solution can't fit one window — that's where RoT should still hold up.

Do and don't

• Do keep each sub-context minimal — one sub-problem, no inherited clutter.
• Do add a recursion-depth guard so a bad split can't loop forever.
• Don't expect length generalization. Training only on 8-digit problems won't transparently solve 16-digit ones; cover the sizes you need.
• Don't reach for RoT when chain-of-thought already fits — you'd pay training and token costs for nothing.

Debugging

Testing

Evaluate per difficulty level and report the largest size that still solves correctly — RoT's whole claim is holding accuracy as instances grow past the single-window limit. Compare against two baselines from the paper: Without Thought (WT), which answers directly, and Chain of Thought (CoT), which keeps every step in one context. CoT's accuracy collapses at the size where its trace hits the window; RoT should stay near-perfect past that line.

# Compare accuracy as problem size grows
for n_digits in [4, 8, 16, 32, 48]:
    problems = make_problems(n_digits, k=1000)
    cot_acc = accuracy(cot_solve, problems)     # falls off a cliff at the window limit
    rot_acc = accuracy(rot_solve, problems)     # should stay near 1.0
    print(n_digits, cot_acc, rot_acc)

Limitations

• It needs supervised training. Unlike chain-of-thought, you can't just prompt for it — you must fine-tune on labeled decompositions. That's the biggest practical barrier.
• No length generalization. The model only reliably splits sizes it saw during training.
• Token and call overhead. One answer can cost hundreds of thousands of generated tokens across many model calls — high latency and spend.
• Only for decomposable problems. If a task doesn't break into self-similar sub-problems, there's nothing for RoT to recurse on.

Advanced techniques and ecosystem

RoT sits in the decomposition family alongside Least-to-Most prompting and Decomposed Prompting (DECOMP). The difference is recursion and separate contexts: Least-to-Most builds a fixed front-to-back list of sub-questions in one growing context, while RoT spins up an isolated context per sub-problem and nests arbitrarily deep. Tree of Thoughts also branches, but to search alternatives, not to beat a context limit.

Natural hybrids: pair RoT with retrieval so each sub-context pulls only the facts it needs, or use RoT as the long-horizon planner inside an agent loop, delegating tool calls as sub-problems. The official implementation is open-sourced (soochan-lee/RoT on GitHub, arXiv:2306.06891) with the arithmetic and algorithmic benchmark generators.

Future directions

The open questions are length generalization (learning to split sizes never seen in training), letting models discover good decompositions without hand-built traces, and merging RoT-style recursion with the very long native context windows now common — using recursion not because the window is small, but because clean sub-contexts reason more accurately than one cluttered one.

Summary

• Recursion of Thought (RoT) beats the context window by recursion, not by a bigger window: split a problem, solve each piece in a fresh context, paste answers back.
• It uses learned control tokens — GO, THINK, STOP, and TAIL — that act like a function call and return for reasoning.
• It's an inference framework over a fine-tuned model, not a pure prompting trick; that training requirement is its main cost.
• Proven on long arithmetic (48-digit add/subtract, 16-digit multiply/divide on GPT-3; 64-digit and 32-digit on tiny from-scratch models) and DP tasks (LCS, LPS, knapsack, matrix chain), reaching near-perfect accuracy on solutions of hundreds of thousands of tokens.
• Reach for it when the honest solution overflows the window and decomposes into self-similar sub-problems; skip it when chain-of-thought already fits or you can't fine-tune.