Tree of thoughts: a complete guide

Chain-of-thought writes one reasoning path left to right and commits to it. If an early step is wrong, the whole chain is wrong, with no way back. Tree of Thoughts (ToT) flips that: the model branches into several candidate "thoughts" at each step, scores them, and explores the promising ones with a search algorithm that can backtrack. On the Game of 24 puzzle, GPT-4 with chain-of-thought solved 4% of tasks; ToT solved 74% (Yao et al., 2023, NeurIPS).

See it work

Take the Game of 24: use 4, 9, 10, and 13 with +, -, ×, ÷ to make 24.

Chain-of-thought guesses one line and hopes it lands:

Prompt: Use 4 9 10 13 to make 24.
Output (CoT): 13 - 9 = 4, 4 + 10 = 14, 14 + 4 = 18.  ✗ dead end, no recovery

Tree of Thoughts instead treats each arithmetic step as a branch, keeps the plausible ones, and prunes the rest:

Step 1 — generate candidate first moves, then score each:
  10 - 4 = 6     → "sure" (6 and 9,13 left, 6 × ... looks reachable)
  13 - 9 = 4     → "maybe"
  4 + 9 = 13     → "impossible" (two 13s, hard to reach 24)

Step 2 — expand the "sure" branch:
  6, 9, 13  →  13 - 9 = 4,  then 6 × 4 = 24   ✓ solved

Same model, same puzzle. The win isn't a smarter step — it's keeping several steps alive and being able to walk back when a branch dies.

The mental model

Chain-of-thought is a person thinking out loud in a single stream. Tree of Thoughts is a chess player: at each move you imagine a few candidate moves, look ahead to judge how good each position is, follow the best line, and if it goes bad you return to an earlier position and try a different one.

Tree of Thoughts = generate a few thoughts per step + evaluate how promising each is + search the tree (with backtracking) instead of committing to one path.

How it works

A ToT problem is defined by four pieces. The first frames the problem, the next two are language-model calls, and the last is plain search code wrapped around them.

1. Thought decomposition. Split the problem into intermediate steps sized so the model can generate and judge one at a time — an equation in Game of 24, a paragraph plan in writing, a word in crosswords.
2. Thought generator. Ask the model for several candidate next thoughts per state. Two styles: sample (draw k independent thoughts from a CoT prompt, good when the space is rich) or propose (ask one prompt to list distinct options, good when the space is narrow and you want no duplicates).
3. State evaluator. Have the model judge how promising each partial state is. Two styles: value (score each state independently — for Game of 24, label it sure / maybe / impossible) or vote (show the model the states side by side and have it vote for the most promising, good for open-ended tasks like writing).
4. Search algorithm. Wrap the above in a classic search. BFS keeps the best b states at each depth (used for Game of 24 with b=5). DFS dives down one path and backtracks when the evaluator deems a state hopeless (used for crosswords).

Why it works

The gains stack up roughly in this order:

Where it shines

ToT pays off when a task needs search, planning, or trial-and-error — and when you can score a partial solution. The headline results, all GPT-4, all from the paper:

• Game of 24 (math planning): chain-of-thought 4%, CoT with self-consistency (k=100) 9%, ToT with b=1 45%, ToT with b=5 74%.
• Creative writing (coherent 4-paragraph passage with fixed end sentences): average coherence 7.56/10 for ToT vs 6.93 for CoT and 6.19 for plain IO prompting. Human raters preferred ToT over CoT in 41 of 100 pairs, the reverse in only 21.
• Mini crosswords (constraint search): ToT reached 60% word-level and 20% game-level success, versus CoT's 15.6% word-level and 1% game-level.

The pattern: the bigger the planning/search component, the bigger the lift.

When to use it (and when not)

Reach for ToT when:

• The problem decomposes into steps you can evaluate (math, planning, puzzles, constraint satisfaction, multi-step proofs).
• A single greedy chain often fails and you'd benefit from exploring alternatives.
• You can write a cheap-ish evaluator (the model judging its own partial states).

Skip ToT when:

• The model already nails the task one-shot — the extra branches just burn tokens.
• You can't define meaningful intermediate steps or score them.
• Latency or cost is tight (see below).

Model fit. ToT leans on the model being a decent self-evaluator. It was validated on GPT-4; weaker models give noisier state scores, which blunts the pruning that makes ToT work. Escalation path: start with CoT, add self-consistency if answers are unstable, and move to ToT only when the task needs real search and you can score partial states.

The core algorithm

The whole method is a search loop around two model calls. Here's BFS, the Game-of-24 setup, in pseudocode:

def tot_bfs(problem, steps, b, k):
    states = [problem]                      # frontier of partial solutions
    for _ in range(steps):                  # one level per decomposed step
        candidates = []
        for s in states:
            thoughts = generate(s, k)        # k next thoughts (sample or propose)
            candidates += [extend(s, t) for t in thoughts]
        scores = [evaluate(c) for c in candidates]   # value or vote
        states = top_b(candidates, scores, b)        # keep best b, prune rest
    return best(states)

generate and evaluate are prompts, not new infrastructure. Swap BFS for DFS and you get the crosswords setup: descend one branch, and when evaluate returns "impossible," pop back up and try the next.

A minimal value-evaluation prompt looks like:

Evaluate whether these numbers can reach 24 (answer: sure / maybe / impossible).
Numbers: 6 9 13
Reasoning: 13 - 9 = 4, 6 * 4 = 24. Answer: sure

Configuration

Implementation workflow

1. Decompose the task into steps small enough to generate and judge individually.
2. Write the generator prompt — sample or propose k candidates per state.
3. Write the evaluator prompt — value-score or vote on states; this is the highest-leverage piece to tune.
4. Pick the search — BFS (keep best b) for breadth, DFS (backtrack on "impossible") for depth.
5. Set b and k small, measure, and raise b only if accuracy is still climbing and budget allows.
6. Add a stop rule — a found solution, a depth cap, or a call budget.

Do: keep thoughts coherent and self-contained; make the evaluator return a usable signal (a label or 1–10 score); cap the call budget explicitly. Don't: decompose into steps the model can't score; crank b before the evaluator is reliable; reach for ToT when one CoT call already works.

Debugging

• Search explores junk → the evaluator is weak. Improve the scoring prompt or switch value↔vote before touching breadth.
• Cost explodes → lower b and k, or cap depth; breadth multiplies calls fast.
• Always finds the same dead end → generator lacks diversity. Use propose to force distinct candidates, or raise temperature on sample.
• No gain over CoT → the task may not need search, or the steps aren't scorable. Drop back to CoT-SC.

Limitations

ToT's cost is its defining constraint: many more model calls than single-path methods, which hurts latency and budget. It needs task-specific design — a sensible decomposition, generator, and evaluator per problem, so it's less plug-and-play than CoT. It depends on the model being a competent self-evaluator; the paper's results use GPT-4, and weaker evaluators erode the pruning. And on tasks the model already handles in one pass, the tree adds cost without adding accuracy.

Summary

• Tree of Thoughts generalizes chain-of-thought by branching into multiple candidate thoughts per step, scoring them, and searching the tree with backtracking.
• A ToT problem has four parts: thought decomposition, a thought generator (sample or propose), a state evaluator (value or vote), and a search algorithm (BFS or DFS).
• Headline result: Game of 24 went from 4% (CoT) to 74% (ToT, b=5) on GPT-4; it also beat baselines on creative-writing coherence (7.56 vs 6.93) and mini crosswords (60% vs 15.6% word-level).
• Use it for tasks needing search or planning where you can score partial states; skip it when one-shot or plain CoT already works.
• The trade-off is cost — ToT spends many model calls per answer, so reserve it for problems where exploration genuinely pays.
• Source: Yao et al., 2023, "Tree of Thoughts: Deliberate Problem Solving with Large Language Models," NeurIPS.