Back to paper library
arXiv 2023NeurIPS 2023Language & TransformersPaper notes

Tree of Thoughts

Dead end

Original paper

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Paper authors

Shunyu Yao · Dian Yu · Jeffrey Zhao …

Show all 7 authors

Shunyu Yao · Dian Yu · Jeffrey Zhao · Izhak Shafran · Thomas L. Griffiths · Yuan Cao · Karthik Narasimhan

Publication
NeurIPS 2023Conference
First submitted to arXiv
arXiv:2305.10601
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{transformerstreeofthoughts2023,
  title = {{Tree of Thoughts: Deliberate Problem Solving with Large Language Models}},
  author = {Shunyu Yao and Dian Yu and Jeffrey Zhao and Izhak Shafran and Thomas L. Griffiths and Yuan Cao and Karthik Narasimhan},
  year = {2023},
  eprint = {2305.10601},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.10601}
}
On this page

From GPT to GPT-4, the way language models produce text has never changed: left to right, one token after another, and once something is written there's no going back.

Chain of thought has the model write out its reasoning steps first, but it still follows one path all the way to the end. Self-Consistency walks a few more paths and votes at the end, yet each of those paths is also written in one go; the model never stops halfway to compare "is this step better taken this way, or that way?" If the first step goes wrong, it doesn't matter how nicely the rest is written.

Yao and colleagues at Princeton, working with Google DeepMind, went back to the earliest research in artificial intelligence for inspiration. In the 1950s, Newell and Simon described human problem solving as a search over a tree: each node is a partial solution, each branch is a possible next step, rules of thumb decide which way to go, and when a path leads nowhere you back up. This paper has the language model do the same.

Defining the problem

The authors write the approaches of the time in a common form. The input is xx, the output is yy, and the language model is pθp_\theta:

  • Input-output prompting (IO): generate the answer directly, y∼pθ(y∣x)y \sim p_\theta(y \mid x).
  • Chain of thought (CoT): insert a series of thoughts z1,…,znz_1, \ldots, z_n between the input and the output, where each thought is a meaningful piece of text, such as one line of arithmetic. In practice, the whole chain is written in one go.
  • Chain of thought with Self-Consistency (CoT-SC): sample kk chains of thought independently and pick the answer that shows up most often.

Seen as a search over a tree, these approaches are missing two things. Locally, they don't explore different ways of writing the same step; globally, there is no planning, lookahead or backtracking of any kind.

Solving the problem

Original Figure 1. Four ways of solving problems with a language model; each box is a thought. (a) Input-output prompting goes straight from input to output. (b) Chain of thought is a string of thoughts on a straight line. (c) Self-Consistency is several independent chains of thought with a majority vote at the end. (d) Tree of Thoughts expands from the input into a tree with several candidate thoughts at each level; shades of green show how well each was evaluated, red marks abandoned branches, and the path with the best evaluations leads to the output.
Original Figure 1, Yao et al., from PDF page 2, CC BY 4.0.

Tree of Thoughts (ToT) treats a problem as a search over a tree. Each node is a state s=[x,z1,…,zi]s = [x, z_1, \ldots, z_i], that is, the input plus the thoughts so far. To apply it to a given problem, you have to answer four questions.

1. How big should a thought be

A thought has to be small enough for the model to produce diverse, promising candidates, and big enough for the model to judge whether it's going anywhere. A single token is too small to evaluate; a whole book is too big to write coherently.

The authors cut thoughts differently depending on the problem: in the Game of 24, a thought is one line of arithmetic; in creative writing, it's a writing plan; in crosswords, it's one word filled in for a clue.

2. How to generate the next thought

  • Independent sampling: use a chain-of-thought prompt and sample kk times independently. This suits cases where the thought space is large, such as a whole plan; separate samples are naturally diverse.
  • Proposing them together: use a "propose prompt" and have the model list kk candidates in a single output. This suits cases where the thought space is tightly constrained, such as one line of arithmetic or one word; listing them together in the same passage avoids duplicates.

3. How to evaluate a state

This is where ToT differs most from ordinary search algorithms. In traditional search, the rule of thumb is either hard-coded (as in Deep Blue) or a trained model (as in AlphaGo). ToT takes a third route and has the language model reason in text on its own about whether a state is promising.

  • Scoring each state on its own: for each state, ask the model for a score, or for a classification as "sure / likely / impossible". The judgment can rest on trying a few steps ahead, for example 5, 5, 14 quickly gives 5 + 5 + 14 = 24; or on common sense, for example 1, 2, 3 are too small to reach 24 however you combine them.
  • Comparing states against each other: when success is hard to score directly, for instance whether a passage is coherent, put several candidates side by side and ask the model to vote for the most promising one. This is a bit like running Self-Consistency at every step.

The evaluation doesn't have to be perfect; it just has to be roughly helpful for making decisions. You can also ask several times and average, trading cost for a more reliable judgment.

4. Which search to use

  • Breadth-first search (BFS): keep only the bb most promising states at each step. Used for the Game of 24 and creative writing, where the tree is shallow (at most 3 steps).
  • Depth-first search (DFS): follow the most promising direction all the way down first; if the evaluation says the problem can't be solved from this state, prune the whole subtree and back up one level to try the next candidate. Used for crosswords, where 10 words have to be filled in.

From this angle, IO, CoT and CoT-SC are all special cases of ToT, just with limits on the depth and width of the tree. The whole framework needs no training at all; an off-the-shelf language model is enough.

Discussion

All three experiments use GPT-4 in chat mode at temperature 0.7, run between May 5 and 16, 2023. The authors deliberately picked three tasks that even GPT-4 does poorly on with IO or CoT.

Game of 24

Original Figure 2. ToT solving the Game of 24. On the left is a search tree, with kept candidates in green and pruned ones in red. The input is 4 9 10 13; first-level candidates include 10 − 4 = 6 (leaving 6 9 13) and 4 + 9 = 13 (leaving 10 13 13), followed by 13 − 6 = 7, 13 − 9 = 4 and so on, ending with 4 × 6 = 24. Top right is the propose prompt: given the remaining numbers, the model lists possible next steps, such as 4 + 9 = 13 (left: 10 13 13) and 10 − 4 = 6 (left: 6 9 13). Bottom right is the value prompt: it asks whether the remaining numbers can make 24, and the model works it out, for example 10 14 gives 10 + 14 = 24, judged sure; for 10 13 13 several attempts all come out too big, judged impossible.
Original Figure 2, Yao et al., from PDF page 5, CC BY 4.0.

The Game of 24 asks you to make 24 from four numbers using addition, subtraction, multiplication and division. The authors scraped 1,362 games from 4nums.com, which sorts them from easy to hard by human solving time, and tested on the 100 harder games numbered 901 to 1,000.

With ToT, the problem naturally splits into 3 steps, one line of arithmetic each. Each node passes the remaining numbers to the propose prompt, which lists possible next steps; each candidate then goes to the value prompt, which judges it sure, maybe or impossible, asking 3 times for each. The search is breadth-first, keeping the best 5 at each step.

MethodSuccess rate
IO prompting7.3%
CoT prompting4.0%
CoT-SC (majority of 100)9.0%
ToT (b=1b = 1)45%
ToT (b=5b = 5)74%
IO + iterative refinement (up to 10 rounds)27%
IO (best of 100)33%
CoT (best of 100)49%

Compiled from Table 2 of the paper.

CoT gets only 4.0%, lower than answering directly; voting only gets it to 9.0%. ToT reaches 45% keeping just 1 candidate, and 74% keeping 5.

The lower half of the table holds a few looser baselines. "Iterative refinement" asks the model to reflect and try again every time it answers wrong, but its feedback is the ground truth on whether the equation is correct. "Best of 100" counts a success if any one of 100 attempts is right; in real use you can't know which attempt is right, so it's an upper bound. Even as an upper bound, CoT gets only 49%, still below ToT.

Original Figure 3. (a) Success rate against nodes visited per game. For IO and CoT, the best of k attempts is taken, and the curves rise slowly, with CoT at about 0.49 by 100 attempts; ToT with b from 1 to 5 visits fewer than 100 nodes yet reaches a much higher success rate, about 0.45 to 0.74. (b) The step at which each method's samples fail. About 60% of CoT samples have already failed at step 1, and about 30% at step 2; most ToT (b = 5) samples make it to the end and are correct.
Original Figure 3, Yao et al., from PDF page 6, CC BY 4.0.

The right panel is the one to look at. About 60% of CoT samples are already doomed never to reach 24 once the first step is written, that is, after the first three words (such as "4 + 9").

Why is the first step so decisive? Take 4 9 10 13. Picking two numbers and applying one arithmetic operation gives 36 possible first moves, and only 7 of them can still reach 24, such as 10 − 4, 9 + 10 and 13 − 9. Pick a step at random and there's an 80% chance you've walked into a dead end. CoT, written left to right, can't go back; get the first step wrong and the whole game is lost.

Plain depth-first search with no judgment at all, trying moves all the way down and backing up a level whenever the end doesn't make 24, also finds an answer, for example 4 − 10 = −6, 9 − 13 = −4, (−6) × (−4) = 24, but it has to go through over a thousand states. A program can brute-force that; a language model pays one API call for every step and can't afford it. ToT's value prompt plays the role of pruning, cutting states like "10 13 13 is too big however you combine it" early and expanding only a few promising branches.

The cost is still considerable. ToT generates an average of 5,500 tokens per Game of 24 problem, close to the 6,700 for sampling CoT 100 times, at about 0.74 US dollars per problem, versus about 0.47 US dollars for 100 CoT samples. For roughly the same number of tokens, ToT's success rate is 74%, while the best of 100 CoT attempts is 49%.

The authors also tried GPT-3.5, where ToT gets only 19%. In the cross tests, GPT-4 generating thoughts with GPT-3.5 evaluating gets 64%; GPT-3.5 generating with GPT-4 evaluating gets only 31%. In this game, the bottleneck is generating good candidates, not evaluating them.

Creative writing

Given 4 random sentences, write a 4-paragraph passage in which each paragraph ends with one of those 4 sentences. The task has no reference answer, so the authors judge coherence in two ways: GPT-4 gives a score from 1 to 10, averaged over 5 runs; and some of the authors, without knowing which passage came from which method, compare CoT and ToT passages in pairs.

ToT has only two levels here: first generate 5 writing plans and vote 5 times to pick the best one; then write 5 passages from that plan and pick one by vote the same way.

MethodGPT-4 score
IO6.19
CoT (write a plan first, then the passage)6.93
ToT7.56
IO + iterative refinement7.67
ToT + iterative refinement7.91

Compiled from Section 4.2 of the paper; scores are averages over 100 tasks.

The human comparison agrees, with ToT judged more coherent in 41 of 100 pairs, CoT judged better in 21, and the remaining 38 about the same. Iterative refinement works well on this task, and the authors treat it as a third way of generating thoughts: modifying old thoughts into new ones.

Mini crosswords

Original Figure 6. ToT solving a 5 × 5 crossword. (a) From the current board (h1.tasks and h2.motor already filled), the model proposes several sets of candidates with confidence levels, such as h4.salon (sure), v5.srdry (low) and v3.string (high), which are aggregated into a priority order; DFS tries h4.salon, h3.grand and v3.string in turn. (b) Each state goes to the evaluator, which checks every remaining clue for whether it can be filled: v3 Pretentious; flowery can be filled (sure), v1 To heap is impossible under its letter constraints (impossible), and v5 Desiccator; more dry might work (maybe). As soon as one clue is judged impossible, the whole subtree is pruned and the search backs up a level.
Original Figure 6, Yao et al., from PDF page 8, CC BY 4.0.

The trees in the first two tasks are shallow, at most 3 steps. A crossword needs 10 words (5 across, 5 down) that constrain each other, which makes it a harder search problem. The authors scraped 156 games from GooBix and tested on 20 of them.

Here the search is depth-first. Each state turns the words already filled in into letter constraints for the remaining clues, asks the model for candidates 5 times with a confidence for each candidate, and aggregates them into a priority order. Evaluation checks every remaining clue in turn; as soon as one is judged impossible to fill, the whole subtree is pruned and the search backs up a level. The search runs at most 100 steps and finally outputs the deepest state it reached.

MethodLettersWordsGames
IO38.7140
CoT40.615.61
ToT786020
ToT, outputting the best state82.467.535
ToT, no pruning65.441.55
ToT, no backtracking54.6205

Compiled from Table 3 of the paper; values in %, with "Games" being the share of the 20 games solved completely.

IO and CoT both get fewer than 16% of words right; ToT gets 60% and fully solves 4 of the 20 games.

The last three rows are ablations. If each game simply outputs the best state found during the search (which requires knowing the answer, so it's an upper bound), 7 games are solved, which shows the "output the deepest state" rule still has room to improve.

Pruning makes mistakes too. To fill the grid, 5 × 5 crosswords use some rare or obsolete words. "agend", for example, is an old form of "agendum", but GPT-4 took it for a misspelling of "agenda" and pruned a correct board. With pruning removed, the overall scores drop, but in 4 games the search did come across the correct board at some point, and 3 of those are games that ToT with pruning can't solve within 100 steps. How good the evaluator is directly determines how far the search can go.

Remove backtracking, filling in the most promising word each time for at most 20 steps with overwriting allowed, and word accuracy falls to just 20%.

Not needed for easy problems

The appendix applies zero-shot ToT to ordinary problems: first generate 5 solution strategies and vote for one, then write 5 solutions following that strategy and vote for one.

MethodGSM8KStrategyQA
IO5173
CoT8682
ToT9083

Compiled from Table 4 of the paper; GPT-4, 100 questions each, in %.

ToT still beats CoT, but only by a small margin. GPT-4 with CoT is already strong on these problems, and StrategyQA's bottleneck is outside knowledge, not reasoning. The authors suggest trying small models with ToT on traditional NLP tasks, and saving GPT-4 with ToT for hard problems that even GPT-4 with CoT can't handle.

Limitations

The authors raise a few points in their discussion:

  • Many tasks don't need it: tasks GPT-4 is already good at don't call for such laborious search; and this paper only explored three relatively simple tasks that GPT-4 does poorly on.
  • Cost: depending on the prompts and the search method, ToT generates 5 to 100 times as many tokens as CoT. The main experiments came to about 106 US dollars for the Game of 24 and creative writing combined, and the crosswords were estimated to stay under 100 US dollars too.
  • Only off-the-shelf models: the authors mention that models could later be fine-tuned in a ToT-like way, so that they learn to make decisions at the level of "how should the next passage go" rather than only predicting the next token.

It's also worth noting that every ToT task has to be designed by hand: how to cut thoughts, how to write the propose and value prompts, and which search to use. Switch to a different problem and all of this has to be thought through again.

What came next

The direction the authors point to at the end was later realized by reasoning models, though not along the ToT path.

The DeepSeek-R1 paper has a section on "unsuccessful attempts." The team tried Monte Carlo tree search (MCTS) for exploration at inference time, splitting the answer into small pieces and guiding the search with a value model, but ran into two problems: the search space of token generation is far larger than in board games, so even with a cap on how many children each node expands, the search easily gets stuck in local optima; and training a fine-grained enough value model is hard in itself. What finally worked was reinforcement learning with answer correctness as the reward, which let the model learn, within a single very long chain of thought, to check itself, doubt itself, and go back and rethink.

Search at inference time didn't go away. When to search, when to let the model revise its own answer, and how to spend compute most efficiently were later compared systematically.

Conclusion

ToT hooks the tree search of classical AI up to a language model, making the model responsible for both proposing candidates and judging them. With GPT-4 on the Game of 24, CoT gets only 4% and ToT reaches 74%; on crosswords, word accuracy goes from 15.6% to 60%.

It also makes the price of this kind of method very clear. Every problem needs a human to design how thoughts are cut, the propose and value prompts, and the search method; the token count is several to a hundred times that of CoT; and once the evaluator misjudges, like that "agend" taken for a typo, the correct answer gets pruned.

A little over a year later, reasoning models flattened this tree. Within one long chain of thought, the model stops on its own to say "wait, that's not right" and goes back to rethink; branching, evaluation and backtracking are all still there, they just no longer need an outside search program to run them.