Tree of Thoughts

The Problem

Chain-of-Thought (CoT) prompting allowed models to reason step-by-step, and Self-Consistency improved reliability by sampling multiple paths. However, both of these methods treat text generation as a relentless march forward. Once a model starts generating a chain of thought, it is committed to that path. If it makes a mistake early on, it cannot realize it, erase the mistake, and try a different approach.

Humans don't solve hard problems this way. When trying to solve a Sudoku puzzle, prove a theorem, or plan a complex itinerary, humans engage in deliberate search. We try a step, evaluate if it looks promising, and if it leads to a dead end, we backtrack and try a different branch. Standard LLM decoding lacked this ability to "look ahead" and "backtrack," severely limiting performance on tasks requiring long-horizon planning or exploration.

The Idea

The authors introduced Tree of Thoughts (ToT), which fundamentally reframes LLM inference. Instead of just prompting a model to output a string of text, ToT wraps the LLM inside a classical computer science search algorithm (like Breadth-First Search or Depth-First Search).

In ToT, the problem is broken down into a series of distinct intermediate steps, or "thoughts." The LLM is used for two separate functions:

1. Generation: Given the current state, generate a few possible next thoughts.
2. Evaluation: Given a sequence of thoughts, evaluate how promising the current state is (e.g., "sure," "maybe," or "impossible" to reach the goal from here).

By generating multiple options at each step and having the model evaluate its own progress, the system builds a "tree" of thoughts. The search algorithm can then selectively expand the most promising branches, prune the dead ends, and backtrack when necessary.

How It Works

Imagine the task is the "Game of 24" (using four numbers and basic arithmetic to reach 24).

• Input: 4 9 10 13
• Generate (Step 1): The model is prompted to generate possible first steps. It might output:
  • Path A: 13 - 9 = 4 (leaves 4, 4, 10)
  • Path B: 10 - 4 = 6 (leaves 6, 9, 13)
  • Path C: 13 + 10 = 23 (leaves 4, 9, 23)
• Evaluate: The model is prompted to evaluate each new state.
  • State A (4, 4, 10): Can this make 24? The model might reason "Yes, 10 + 4 = 14, 14 + 10... wait no. But 4 * 4 = 16... hard." It scores it as maybe.
  • State B (6, 9, 13): Can this make 24? The model might reason "Yes, 13 * ... wait. Oh, 13 - 9 = 4, 4 * 6 = 24! Yes!" It scores it as sure.
• Search/Backtrack: The classical search algorithm running outside the model sees that Path B scored sure. It chooses to expand Path B, ignoring or pruning the others.
• Generate (Step 2): From Path B, generate the next steps... and the process repeats until the goal is reached.

This process allows the system to actively prune bad reasoning paths before wasting compute on generating the rest of the sentence, and it allows the model to effectively "undo" mistakes by switching to a different branch of the tree.

Why It Mattered

Tree of Thoughts achieved massive performance gains on tasks requiring deliberate planning. On the Game of 24, GPT-4 with standard Chain-of-Thought solved only 4% of the problems. With Tree of Thoughts, GPT-4 solved 74%.

It was one of the first major papers to demonstrate that we could dramatically boost LLM performance not by training a bigger model, but by wrapping the model in a scaffolding framework (an "agentic" loop) that structures its inference. It proved that LLMs could act as both the "generator" of ideas and the "heuristic evaluator" of those ideas within classical search algorithms.

What Came After

Tree of Thoughts sparked a massive wave of "agentic reasoning" frameworks. It blurred the line between prompt engineering and software engineering, showing that the best way to get complex behavior out of an LLM is to call it multiple times in a structured loop rather than relying on a single magic prompt.

The core idea—generating multiple candidate thoughts and using a verifier or value model to evaluate them—became the blueprint for next-generation reasoning models. When OpenAI released the o1 series of models (which "think" before they speak), the underlying mechanism was widely understood to be a scaled-up, reinforcement-learning-trained version of the Tree of Thoughts search process happening under the hood.