Tree of Thoughts (ToT)

Tree of Thoughts (ToT) is a prompt engineering framework in which a large language model (LLM) solves a problem by searching a tree of partial solutions. At each step, the model proposes several candidate next steps, called thoughts, rates how promising each resulting state is, and a search algorithm decides which branches to expand, keep, or abandon. Where chain-of-thought prompting commits to one line of reasoning from the first token, ToT can look ahead and backtrack. Shunyu Yao and colleagues at Princeton University and Google DeepMind introduced it in Tree of Thoughts: Deliberate Problem Solving with Large Language Models, presented at NeurIPS 2023, and Jieyi Long proposed a similar tree-search system for solving Sudoku with an LLM in the same month. On the Game of 24 puzzle, ToT raised GPT-4's success rate from 4% with chain-of-thought prompting to 74%.

How Tree of Thoughts Works#

Yao et al. define ToT through four design choices:

• Thought decomposition: What one step is. In Game of 24, a thought is one equation; in creative text generation, a plan for the passage; in a crossword, one word to place.
• Thought generator: How candidates are produced. The model either samples several thoughts independently, which suits open-ended steps, or proposes a list of distinct options in one prompt, which avoids duplicates when the choices are constrained.
• State evaluator: How progress is judged. The model rates each state on its own, for example as "sure", "maybe", or "impossible" to reach the goal, or votes for the best of several states. These ratings serve as the search heuristic, a role filled by a hand-written scoring function in classical search.
• Search algorithm: How the tree is explored. Breadth-first search keeps the best b states at each level, and depth-first search follows the most promising branch, prunes states the evaluator rules out, and backtracks.

Example: Game of 24#

Game of 24 gives four numbers that must be combined with +, -, x, and / to make 24, using each number once. ToT splits the solution into three steps, each an equation that merges two numbers. For the input 4 9 10 13, a propose prompt lists candidates such as:

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

The value prompt then asks whether each remaining set can still reach 24. "4 4 10" is sure, since (10 - 4) x 4 = 24, as is "6 9 13", since (13 - 9) x 6 = 24, while "10 13 13" and "9 10 52" are impossible, so search expands only the first two branches. Following the first gives 10 - 4 = 6 (left: 4 6), then 4 x 6 = 24.

In the paper's experiments on 100 hard games, breadth-first search kept the 5 best states per step, with each state rated three times. ToT with GPT-4 solved 74% of games, compared with 7.3% for direct prompting, 4.0% for chain-of-thought, and 9.0% for chain-of-thought with self-consistency. Even the best of 100 sampled chains of thought reached only 49%, and ToT keeping a single state per step reached 45%.

Where Tree of Thoughts Fits#

ToT helps on problems where early choices constrain later ones and a wrong first step is hard to repair: puzzles, planning, and multi-step math. In 5x5 mini crosswords, depth-first ToT with pruning filled 60% of words correctly and solved 4 of 20 games. The price is computation: every level of the tree costs several generation and evaluation calls, so a single answer can take dozens of model calls or more and many more tokens than one chain, with matching inference latency.

The same generate, evaluate, and expand loop appears at a much coarser grain in automated experiment search, such as hyperparameter tuning. In Ultralytics Platform AutoTrain, Ask AI can train several Ultralytics YOLO models that differ in one setting, such as image sizes of 640, 800, and 960, compare the finished runs by validation mAP50-95, and propose the next experiment from the best result.

Tree of Thoughts vs. Related Methods#

• Chain-of-thought prompting: A single path of reasoning, equivalent to a tree with one branch per level.
• ReAct prompting: Interleaves reasoning with actions in an outside environment, such as searches or tool calls, and moves forward on what those actions return. ToT searches over the model's own candidate thoughts.
• Self-consistency: Samples several complete chains and takes a majority vote on the final answers, without judging partial steps along the way.
• Graph of Thoughts: Generalizes the tree to a graph in which thoughts can also be merged and refined, and reported 62% better sorting quality than ToT at over 31% lower cost.
• Monte Carlo tree search (MCTS): The search algorithm behind AlphaGo, which balances exploring new branches against exploiting good ones and can replace breadth- or depth-first search over thoughts.
• Reasoning models: Trained with reinforcement learning to write long reasoning traces in a single generation, where ToT gets branching and backtracking from an external search program around an ordinary model.