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:

AlgorithmHow 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).