Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Chain-of-thought prompting asks a model to write out intermediate steps, but it still writes them once, left to right. If the first step is wrong, nothing later can undo it. Shunyu Yao and colleagues at Princeton and Google DeepMind, drawing on Newell and Simon's view of problem solving as search through a space of partial solutions, proposed Tree of Thoughts (ToT), presented at NeurIPS 2023.

A thought is a meaningful intermediate step: one equation in a math puzzle, one word in a crossword, one paragraph-level plan for an essay. Designing a ToT system means answering four questions. How should the problem be split into thoughts? How should candidate thoughts be generated, by sampling several independently or by asking for a list? How should states be evaluated, by rating each one ("sure", "maybe", "impossible") or by having the model vote for the best among several? And which search should run on top: breadth-first, keeping the best few states per level, or depth-first with pruning and backtracking?

The paper built three tasks that GPT-4 found hard. In the Game of 24 (combine four numbers to make 24), chain of thought solved 4% of 100 hard games; ToT with breadth-first search keeping five states solved 74%. In creative writing (four paragraphs ending in four given sentences), ToT plans were rated more coherent. In 5×5 mini crosswords, ToT with depth-first search got 60% of words right and solved 4 of 20 games, against under 16% of words for chain of thought.

The cost was stated plainly. A Game of 24 problem took about 5,500 generated tokens with ToT, close to 100 chain-of-thought samples, and cost $0.74 against $0.47.

Most customer tasks do not need tree search; GPT-4 with chain of thought already did well on GSM8K in the paper's own appendix. But some do: scheduling with constraints, configuration that must satisfy many rules, multi-step plans where an early choice locks in the rest. ToT gives a vocabulary for those cases, and its numbers give you the trade-off.

Search helps when early mistakes are fatal and detectable. Sixty percent of the failed chains had gone wrong at the first equation. A rater that can say "this can no longer reach 24" lets the search drop those branches early.

The evaluator decides the outcome. ToT works only as well as the model's judgment of partial states. If you have a programmatic check, such as a constraint solver, a schema or a unit test, use it as the evaluator instead.

Ask whether a program would solve it outright. The Game of 24 is a few hundred milliseconds of exhaustive search in code. ToT shows how an LLM can search; for a customer task with a formal structure, letting the model write or call a solver is usually cheaper and exact.

Price it per problem. ToT spent five to a hundred times more generated tokens than chain of thought, by the authors' estimate. Work out the cost per resolved case before proposing it.