Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Generation makes token-level decisions one at a time, left to right, so models fall short on tasks needing exploration, strategic lookahead, or where early decisions are pivotal; e.g. GPT-4 with chain-of-thought solved only 4% of hard Game of 24 problems.

Dual-process theory: token-by-token generation resembles fast, associative “System 1” and could be complemented by deliberate “System 2” planning. And Newell, Shaw and Simon’s view of problem solving as search through a combinatorial problem space represented as a tree.

IO maps input to output directly; CoT samples one chain of intermediate thoughts left to right; CoT-SC samples several chains and takes the majority answer. None explores alternative steps within a chain, and majority voting only works when the output space is small.

A coherent language sequence that is an intermediate step toward a solution: a few words (crosswords), one equation (Game of 24), or a paragraph-long plan (creative writing). It should be small enough to generate diverse, promising candidates, but big enough for the model to judge its promise.

How to decompose the process into thought steps; how to generate candidate thoughts from a state; how to evaluate states heuristically; and which search algorithm to use. A state \(s = [x, z_{1 \ldots i}]\) is the input plus the thoughts so far.

Sampling i.i.d. thoughts from a CoT prompt, good when the thought space is rich (e.g. paragraphs) so samples differ; or proposing several thoughts at once with a “propose prompt”, good when the space is constrained (a word or an equation) so independent samples would duplicate.

The language model itself reasons about states, either valuing each (e.g. a score, or sure/maybe/impossible, via quick lookahead and commonsense such as “1 2 3 are too small to reach 24”) or voting for the most promising among several. Earlier search heuristics were either programmed (Deep Blue) or learned (AlphaGo).

Breadth-first search keeping the \(b\) best states per step (shallow trees: Game of 24, creative writing), and depth-first search exploring the most promising state first, pruning subtrees judged impossible and backtracking (crosswords). A* and MCTS are left for future work.

IO, CoT, CoT-SC and self-refinement are special cases: trees of limited depth and breadth. The model, decomposition, generation, evaluation and search can each be varied independently, and no training is needed.

With GPT-4 on 100 hard games: IO 7.3%, CoT 4.0%, CoT-SC (100 samples) 9.0%, best of 100 CoT samples 49%; ToT with breadth 1 reached 45% and with breadth 5, 74%.

About 60% of CoT samples were already doomed after the first step (the first three words, e.g. “4 + 9”): committing early without exploring alternatives is the main failure.

Task: write four paragraphs ending in four given random sentences. ToT generated 5 plans, let the model vote on the best, then wrote 5 passages from it and voted again. GPT-4 rated coherence 7.56 vs 6.93 for CoT and 6.19 for IO; humans preferred ToT over CoT 41 times to 21 out of 100.

Depth-first search filling one clue at a time, ordering candidate words by the model’s confidence and pruning a state if any remaining clue seemed impossible given its letters. Word-level success rose from under 16% (IO, CoT) to 60%, solving 4 of 20 games.

Backtracking matters: a greedy version without it got only 20% of words right. Pruning matters too but is imperfect: GPT-4 sometimes pruned correct states because of rare or obsolete words it didn’t recognize; outputting the best explored state instead of the heuristic choice solved 7 of 20.

Deliberate search is unnecessary for many tasks GPT-4 already handles; it costs many more model calls than sampling; and it uses an off-the-shelf model, though fine-tuning models for such high-level deliberation might improve problem solving further.