Tree of Thoughts (ToT) is a prompting technique that structures the reasoning of an LLM like a tree. The model explores several reasoning paths in parallel, evaluates the potential of each path, and backtracks from weak paths.
CoT follows 1 path from start to end, so 1 wrong step can spoil the answer. ToT keeps several branches open and prunes the weak branches.
Structure
ToT has 3 steps:
graph TD A[Thought decomposition] --> B[Thought generation] B --> B1[Sampling] B --> B2[Proposing] B1 --> C[State evaluation] B2 --> C C --> C1[Value] C --> C2[Vote] C1 --> D[Search algorithm] C2 --> D
Remembering tip
Split, Score, Search.
Split the problem into thoughts, score each state, then search the tree.
Thought decomposition
Decompose the problem into intermediate steps. Each step is 1 thought.
These are the 2 ways to generate the candidate thoughts for a step:
- sample: sample several thoughts from the step with CoT, means we send the same prompt times and each call writes one thought
- propose: propose new thoughts with a generator, means we send a prompt like "give me 3 possible next steps" and the model generates them altogether
State evaluation
A state is the partial solution at 1 point in the tree. The LLM itself acts as the evaluator, and it reasons about each state.
These are the 2 ways to evaluate the states:
- value: calculate a value for each state independently
- vote: compare all the states at the same level or depth, then vote for the best state
Search algorithm
The search algorithm moves through the solution space. These are the 2 basic algorithms that ToT uses:
| Algorithm | How it moves |
|---|---|
| Breadth-first search (BFS) | Explores all the branches at 1 level before it goes deeper into the tree |
| Depth-first search (DFS) | Explores 1 branch deeply, then backtracks to explore the other branches |
Example
Problem: you get 4 random sentences. Write a passage of 4 paragraphs, where each paragraph ends with 1 of the 4 sentences, in order.
The steps:
- decompose and generate: ask the LLM to write 5 plans for the passage
- evaluate by vote: give all 5 plans to the LLM and ask it to choose the best plan
- repeat the vote: do the vote 5 times, then keep the plan that gets the most votes
- go deeper: write passages from the chosen plan, then use the same vote to choose the best passage
When to use
ToT is useful for:
- problem solving: it explores a wider range of possibilities, so the solutions are more creative and accurate on complex tasks
- decision making: it evaluates several options at each step, so the decisions are more informed and deliberate
- creativity: the branches encourage diverse solutions
- transparency: the tree shows how the model got to its answer
- complex tasks: tasks that need strategic thinking, planning and deliberate decisions
Limitations
Limitations of ToT:
- computational overhead: many paths and evaluations need much processing power and memory
- overfitting: the model can focus too much on 1 branch, which gives a poor result or decision paralysis
- misalignment of goals: reasoning that is logical inside the tree can fail the real-world constraints and goals
- prompt engineering: good ToT prompts are hard to write and need a deep understanding of the subject
A tree can only split its branches. When thoughts must also merge, the method becomes Graph of Thoughts (GoT).