Tree of Thoughts,
explained.

Autoregressive generation is pure System 1: fast, associative, one token after another, no revision. Chain-of-thought made the stream longer and more structured, and self-consistency hedged it by sampling many streams — but every stream is still a one-way street. Nothing in the machinery lets the model consider two alternatives, compare them, or undo a commitment.

For some problems that's fatal by construction. Take Game of 24 — combine 4, 9, 10, 13 with arithmetic to make 24. Humans solve it by trial and error: try (13−9)=4… dead end, back up, try (10−4)=6, 6×(13−9)=24 ✓. A model that can't back up has to guess the winning line on the first try. GPT-4 with CoT managed 4%.

ToT's first move is choosing the right granularity. Searching over individual tokens would be astronomically branchy; searching over whole solutions is just self-consistency. In between sits the thought: a coherent intermediate step — one equation in a math puzzle, one plan paragraph in an essay, one word placement in a crossword.

It's a deliberate reunion of the two AI traditions: the LLM supplies what search always lacked (rich step generation and judgment), and search supplies what LLMs lacked (exploration and the right to change your mind).

At each frontier node, the model proposes several candidate next thoughts. An evaluator scores each one's promise. A search algorithm — plain BFS keeping the best few candidates per depth, or DFS diving deep and retreating on failure — decides what to expand next and what to prune.

Backtracking is the emotional core of the method: a bad branch costs a retreat, not the whole attempt. The model gets what every human problem-solver takes for granted — the ability to say "that didn't work" and still win.

Classical search needs a heuristic function, hand-built per problem. ToT's second insight: the LLM is the heuristic. Prompt it to assess a partial solution — "can these remaining numbers still reach 24: sure, likely, or impossible?" — and you get a usable value function for free, in natural language, on any domain.

Self-evaluation is noisy, and that's fine: a search heuristic doesn't need to be right, only informative enough to rank siblings. Judging "is this partial state promising?" is reliably easier than generating the full correct solution — the same generator-verifier gap that later powers process reward models and LLM-as-judge everywhere.

Not an increment — a different regime. The same model, the same weights, an 18× jump purely from changing how inference explores. Creative writing (plan several outlines, pick the best, then write) and 5×5 mini-crosswords (DFS with backtracking) showed the same shape: wherever solving means trying and revising, the tree crushed the chain.

Every proposal and every evaluation is a model call. A Game of 24 solve runs ~100 calls; deep DFS problems more. ToT is test-time compute spent aggressively — orders of magnitude beyond a single chain — plus orchestration code to manage the tree, the prompts, and the frontier.

It also needs problems with decomposable steps and evaluable partial states. Where a task is one intuitive leap, or progress can't be judged midway, the tree collapses back into an expensive chain. ToT is a specialist's scalpel, not a default decoding mode.

ToT completed the trilogy that defined LLM reasoning's external era: CoT (make thinking visible) → self-consistency (sample and vote) → ToT (search deliberately, with evaluation and backtracking). Together they proved the capability ceiling wasn't the model — it was the inference procedure.

The final act absorbed the lesson: reasoning models trained with RL now explore, self-check, hit dead ends and say "wait, let me reconsider" inside a single generation — the tree internalized into the stream. When o1-class models budget more thinking for harder problems, they're running ToT's playbook without the scaffolding. The scaffold retired; the idea won.