History Problem Core Idea Tasks Results Impact Quiz Takeaways
Interactive Paper Explainer

Search Over Thoughts
Tree of Thoughts

Language models decode left-to-right and commit instantly. ToT turns reasoning into search: branch over coherent thought-steps, self-evaluate the promising ones, backtrack from the dead ones — GPT-4 on Game of 24 goes from 4% to 74%.

Start Learning Read the Paper ↗
4% → 74%
Game of 24 (CoT → ToT)
3
Search strategies
2
Planning + search tasks
2023
Yao et al.
History

One Path, No Regrets

The decoding constraint ToT named and broke: token-level, left-to-right, no looking back.

2022
CoT: one visible path
Chain-of-thought (entry #48) exposes reasoning — as a single linear stream that cannot branch, re-rank itself, or retreat.
2022
Self-consistency: many paths, one vote
Entry #49 samples parallel chains and majority-votes — exploration without structure: no shared prefix, no lookahead.
May 2023
🚀 Tree of Thoughts
Yao et al.: thoughts as tree NODES; the LM proposes branches, evaluates promising states, and BFS/DFS-searches with backtracking — deliberate, global decisions.
2023-24
Search-based reasoning spreads
Graph-of-Thoughts, MCTS-style reasoning, and verifier-guided decoding (entry #58) generalize the pattern.
2024-25
The industry synthesis
o1/R1-class models internalize exploration in training; test-time compute (entry #58) quantifies the trade ToT dramatized — search buys accuracy with tokens.
Reasoning as Graph Search

ToT's four moves: (1) thoughts — coherent intermediate steps, not single tokens; (2) proposal — the LM generates several candidate next-steps from a partial solution; (3) self-evaluation — the LM scores states' promise as a search heuristic; (4) search — BFS or DFS over the tree, expanding high-value nodes and backtracking from dead ends. The general recipe subsumes CoT (a degenerate single-branch tree) and self-consistency (a star, not a tree) — and restores what decoding lost: lookahead, global decisions, and second thoughts.

Chapter 01

Committed at Token One

Why left-to-right generation fails exactly when deliberation matters.

➡️
The Decoding Straitjacket
  • Autoregressive generation commits each token permanently — no branch exploration, no retreat
  • Early wrong turns dominate: in search-flavored tasks, an initial bad choice poisons everything after
  • CoT fixes visibility, not control — the path is still one railroad track
  • Self-consistency votes over independent tracks — no shared progress, no mid-course correction
🌳
The ToT Answer
  • Thought steps become tree nodes — branch, keep options open
  • The LM proposes k candidate continuations per node (a generator as search engine)
  • The LM self-evaluates states (value prompt) — a heuristic for where to spend search
  • BFS/DFS with pruning and backtracking — global decisions replace greedy commitments
Analogy — Chess, Not Typing

Standard decoding is touch-typing a novel: every letter is final the instant it exists. Self-consistency types several novels and holds a vote. ToT plays chess: consider candidate moves, evaluate the positions they create, look ahead along the promising line, and — crucially — take the piece back when line 3 turns sour. The board state is the partial solution; thinking is navigation, not transcription.

Chapter 02

The Game of 24 Walkthrough

The paper's flagship task, end to end — the anatomy of a solved search.

The task
  • Input: four numbers (e.g. 4, 7, 8, 8) · Goal: combine with + − × ÷ to reach exactly 24
  • Branching structure: a "thought" = one intermediate equation step (leaving 3 numbers, then 2, then the result)
  • Depth is shallow (3 levels) but the branching × evaluation burden is the point: one wrong early equation kills the subtree
  • CoT GPT-4 solves 4% — the single-path commitment is fatal
The search (BFS variant)
  • Propose k equations per state → evaluate each remaining-set's promise (LM value score)
  • Keep the best few states per level (beam-style pruning)
  • Dead branches pruned early; when all children fail, backtrack to the parent and re-expand
  • Result: 74% solved — with identical GPT-4 weights and no training
Interactive Demo — Search a Tree, Not a Line

Solve 4, 7, 8, 8 → 24 with BFS: propose, evaluate, prune, backtrack — every mechanism of ToT in one run.

Chapter 03

The Other Tasks and the Costs

Creative writing (plan-then-write with re-ranking) and mini crosswords (constrained DFS) — plus the honest bill.

Beyond Arithmetic

The bill, paid honestly: each ToT solve means many more model calls (proposals + evaluations per node) than a single CoT pass — the trade later quantified by test-time-compute research (entry #58). ToT is a demonstration that structure buys correctness; industry's answer was to fold that structure into training.

Interactive Demo — CoT vs Self-Consistency vs ToT

Tab through the three reasoning-control paradigms — the structural family ToT completes.

Chapter 05

4% → 74%, Same Weights

The headline and the cost, together.

GAME OF 24 · CoT
4%
GPT-4, single-path reasoning
GAME OF 24 · ToT
74%
same model, tree search + backtracking
TASKS
3 families
planning/search: 24, writing, crosswords
COST
N× calls
proposal + evaluation per node — the known price
Interactive Demo — Where the Idea Went

ToT's search structure, three careers later. Press reveal.

Inference paradigmPaths exploredMid-course controlGame of 24 (GPT-4)
Standard prompting1none~4%-class failure
Chain-of-thought1, visiblenone — linear4%
Self-consistencyN independentvote at the end onlyimproved, still capped
Tree of Thoughtsbranching treepropose · evaluate · backtrack74%

Game of 24 figures from the paper (CoT 4% vs ToT 74% with GPT-4). The structural contrast — not the specific task — is the export.

Legacy

Legacy — Deliberation as an Engineering Object

ToT made reasoning control explicit, visual, and measurable.

🌲 The reasoning-search family
Graph-of-Thoughts, thought decomposition variants, and MCTS-based reasoning systems all descend from this framing — thoughts as explicit searchable states.
📈 The 70-point proof
4% → 74% on the same weights made 'inference-time control' undeniable — the datapoint that legitimized spending tokens on search (entry #58's premise).
🔁 The controller pattern
Propose/evaluate/backtrack control loops reappear in agent frameworks and self-correction stacks — ToT is the generic shape of deliberate retry.
🧠 The training-side absorption
o1/R1-class reasoning models train the exploration behavior in — ToT's structure as learned policy rather than external script.
⚠️ What it did NOT solve
Cost (many calls per solve); hand-designed tree granularity per task; self-evaluation is a noisy heuristic (bad value prompts mislead search); and on non-search-shaped tasks, plain CoT often suffices.
🛤 Read next
The control lineage: Chain-of-Thought · Self-Consistency · Test-Time Compute
Test Yourself

Quick Quiz

Check your understanding of the key concepts from Tree of Thoughts.

Reference

Key Takeaways

Everything you need to remember about this paper.

✅ Thoughts as tree nodes: coherent steps that branch, get evaluated, and can be abandoned.
✅ The LM plays two roles: move proposer and state evaluator (the search heuristic).
✅ BFS/DFS with backtracking restores lookahead and global decisions to left-to-right models.
✅ Game of 24: GPT-4 goes 4% (CoT) → 74% (ToT) — no weight changes, pure inference-time control.
✅ Also lifts creative writing (plan re-ranking) and constrained crossword search.
✅ Read it as the proof that deliberation is a search problem — later folded into training by o1/R1.