1. Why This Matters
Large Language Models (LLMs) have achieved astonishing success by predicting the next token in a sequence. However, this underlying mechanism is strictly autoregressive and left-to-right. Once a token is sampled, it is locked in. The model cannot "think ahead," explore alternative branches, or backtrack if it realizes a previous choice was a dead-end.
In human cognitive psychology, dual-process theory suggests our minds operate in two modes:
- System 1 (Fast & Intuitive): Automatic, unconscious processing. This mirrors standard LLM token generation.
- System 2 (Slow & Deliberate): Conscious, planning, and reasoning. This is where we weigh alternatives, look ahead, and backtrack when we hit a wall.
For complex tasks like mathematical puzzle-solving, strategic planning, or creative writing, System 1 thinking is highly prone to failure. If the initial token decisions are slightly off, the model falls into a cascade of errors. To bypass this, we need a way to wrap the model's generation capabilities in a deliberative, System 2 search framework.
2. The Big Idea
The Tree of Thoughts (ToT) framework translates the classic artificial intelligence paradigm of heuristic search (pioneered by Newell, Shaw, and Simon in the 1950s) to modern language modeling. Instead of generating a single continuous path, ToT maintains a tree of partial solutions, where each node represents a coherent "thought".
By decomposing the problem into discrete thought steps, we can prompt the LLM itself to act as a State Evaluator. It judges the viability of intermediate thoughts (e.g., classifying them as "sure", "maybe", or "impossible"), allowing classical tree-search algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS) to navigate the solution space systematically.
Interactive Paradigm Visualizer
Compare how different prompting strategies explore the reasoning space.
Input-Output (IO) Prompting
The standard paradigm. The model takes the input prompt and directly maps it to the final output in one continuous autoregressive stream. There are no intermediate stages or sanity checks.
3. How It Works
ToT formalizes problem solving as search over a tree. A state is represented as a sequence of thoughts $s = [x, z_1, \dots, z_i]$. A complete instantiation requires defining four main components:
1. Thought Decomposition
Unlike CoT which generates thoughts continuously, ToT defines a specific grain size for a "thought". It must be small enough for the model to generate diverse proposals, yet large enough for the model to evaluate its potential.
2. Thought Generator $G(p_\theta, s, k)$
Given a state $s$, we generate $k$ candidate thoughts for the next step. Two strategies are used:
- Sample (i.i.d.): Good for rich thought spaces (e.g., creative writing plans).
- Propose (sequentially): Better for constrained spaces (e.g., crossword words) to avoid duplicates.
3. State Evaluator $V(p_\theta, S)$
The evaluator estimates the progress of states toward a solution. It serves as the search heuristic.
- Value independently: Evaluate each state $s$ with a scalar (e.g., 1-10) or category (sure/maybe/impossible).
- Vote across states: Compare states against each other and select the most promising one.
4. Search Algorithm
Depending on the tree structure, we can plug in classical search algorithms:
- Breadth-First Search (BFS): Maintains a frontier of the $b$ most promising states at each step. Ideal for shallow trees (e.g., Game of 24).
- Depth-First Search (DFS): Explores the most promising branch first, pruning subtrees that fall below a threshold and backtracking to parent nodes. Ideal for deep trees (e.g., Crosswords).
Game of 24 BFS Simulator
Input: 4, 9, 10, 13. Goal: Use basic arithmetic to reach 24. Step through the BFS tree.
We start with the initial numbers: 4, 9, 10, 13. The model needs to propose operations that reduce this set.
DFS Crossword & Backtracking
Watch DFS dynamically search, evaluate, prune, and backtrack to solve a 5x5 crossword.
"Introduce or show"
4. Experimental Results
The authors evaluated ToT on three highly challenging tasks that stump standard prompting methods.
In Game of 24, standard prompts fail because they make greedy, left-to-right calculations. ToT achieves 74% success by decomposing the problem into three equations and maintaining a beam of 5 candidate paths.
5. Limitations & Open Questions
While ToT provides massive performance gains, it introduces unique engineering and research challenges:
- Computational Cost: ToT requires querying the LLM multiple times per step (to generate and evaluate thoughts). This drastically increases token consumption and latency.
- Heuristic Quality: The success of search heavily relies on the model's ability to evaluate states. If the model fails to recognize an impossible state, it may waste computations exploring dead branches.
- Fine-tuning Opportunities: The current study uses off-the-shelf models. Fine-tuning LMs specifically for ToT-style counterfactual reasoning could unlock even higher performance with fewer steps.
6. Glossary
Autoregressive Generation
A sequence generation method where the model predicts the next token based strictly on previously generated tokens, moving strictly from left to right.
Heuristic Search
A search strategy that uses practical guidelines or "rules of thumb" (heuristics) to estimate which branches of a decision tree are most likely to lead to a solution.
Backtracking
An algorithmic technique where a search process abandons a path (backtracks) upon realizing it cannot lead to a valid solution, returning to a previous decision point to try a different path.
7. Citation
@inproceedings{yao2023tree,
title={Tree of thoughts: Deliberate problem solving with large language models},
author={Yao, Shunyu and Yu, Dian and Zhao, Jeffrey and Shafran, Izhak and Griffiths, Thomas L and Cao, Yuan and Narasimhan, Karthik},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023}
}