Tree of thought

What to watch for

This lesson’s companion video is Shunyu Yao — the author of both the Tree-of-Thoughts and ReAct papers — giving what amounts to a broad PhD-defense talk covering his whole body of research, not a video dedicated to Tree of Thought alone, and it runs much longer than a typical lesson video. Treat it as a bonus straight from the source rather than a tightly-scoped tutorial; this lesson’s own explanation below stands on its own regardless of how much of the talk you watch.

When one chain is not enough

ReAct and chain-of-thought both produce a single line of reasoning: one thought leads to one action leads to one next thought, in sequence. That works well when each step has an obviously correct next move. It works poorly when a problem genuinely branches — when, at some point, there are two or three plausible next steps and no way to tell in advance which one leads somewhere useful. Committing to one guess and running it all the way to a dead end wastes the entire chain; there is no earlier point to return to, because a chain has no stored alternatives. Tree of thought addresses exactly this by keeping several candidate continuations alive at once, evaluating how promising each looks, and discarding the weak ones before they are extended any further — turning the single committed guess into a search over several.

The mechanism: branch, score, prune, continue

At each step with more than one plausible move, the agent generates several candidate next steps rather than one. Each candidate is then evaluated — either by the model itself judging how promising the partial path looks, or by a simple checkable rule for how close it gets to the goal. Candidates that score poorly are pruned: the agent stops extending them and does not spend further computation on them. The agent continues extending the surviving, more promising candidates, repeating the branch-score-prune cycle at each subsequent decision point. If every surviving path from an early branch eventually dead-ends, the agent backtracks — returns to an earlier branch point and tries a different candidate that was set aside rather than being forced to start the whole problem over.

A worked example: Game of 24

In Game of 24, you are given four numbers and must combine them with +, −, ×, ÷ to reach exactly 24. Take the numbers 4, 7, 8, 8.

Branch 1 (first step): the agent considers several first moves: 8 × 8 = 64, 8 + 8 = 16, 7 − 4 = 3, 8 ÷ 4 = 2.

Score: 16 (from 8+8, leaving 4, 7) looks promising because 16 is close to 24 and the remaining numbers 4 and 7 could plausibly adjust it. 64 is pruned immediately — it overshoots badly and the remaining numbers 4, 7 can’t bring 64 down to 24 cleanly. 3 and 2 are kept as weaker backups.

Branch 2 (extend the 16 branch): from 16 with remaining numbers {4, 7}, the agent tries 16 + 7 = 23 and 16 + 4 = 20 — both close to 24 but neither reachable exactly with the one number left over in each case. This branch is pruned: it cannot resolve.

Backtrack: the agent returns to the branch point and tries a candidate set aside earlier — 8 ÷ 8 = 1, remaining numbers {4, 7, 1}. Scored as promising because 1 is a flexible number to combine with 7.

Branch 3 (extend the 8÷8=1 branch): from remaining {4, 7, 1}, try 7 − 1 = 6, leaving {4, 6}. Scored highly: 6 × 4 = 24 exactly.

Resolution: the full path is (7 − 8 ÷ 8) × 4 = 24, using all four original numbers exactly once. The agent only found this by abandoning the 16-branch once it stalled and returning to try 8 ÷ 8 = 1 instead — a move the tree kept on record as a backup candidate rather than discarding the moment the first branch looked promising.

The point of the walkthrough is the shape, not the arithmetic: several first moves tried, the clearly bad one (8×8=64) pruned immediately, the next-most-promising one (8+8=16) extended and then abandoned when it stalled, and a backtrack to a previously-set-aside candidate that turned out to be the winning path. A single linear chain gets exactly one guess at the first move and has no way back if it’s wrong; the tree keeps options open and gets to try again.

Why this costs more, and when that’s worth it

Generating and scoring multiple candidates at every branch point means tree of thought does strictly more work than a single chain — if a chain takes one pass per step, a tree with three candidates per branch does roughly three times the generation and all the scoring on top. That cost is wasted on problems that don’t actually branch, which is why chain-of-thought and ReAct remain the default for sequential, mostly-linear tasks. Tree of thought earns its keep specifically on puzzles, planning problems, and creative tasks where an early wrong turn is expensive to discover late and cheap to avoid early — paying more compute upfront to avoid committing to a plan that only reveals its flaw several steps downstream.