Tree of Thoughts: How Branching Reasoning Paths Solve Problems Chain-of-Thought Cannot

Chain-of-thought prompting tells the model to work step by step. That helps, but it still commits the model to one sequence of thoughts from start to finish. If the first step goes wrong, the error compounds through every step that follows, and there is no way to reverse course. Tree of Thoughts fixes this by giving the model something it never had in a standard prompt: the ability to explore multiple paths, evaluate which ones look promising, and backtrack from dead ends.

The paper and its core motivation

Tree of Thoughts was introduced in 'Tree of Thoughts: Deliberate Problem Solving with Large Language Models' by Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan, submitted to arXiv on May 17, 2023 (arXiv:2305.10601) and published at NeurIPS 2023. The paper's opening observation is sharp: every major prompting technique up to that point, including chain-of-thought and self-consistency, still let the model make token-level decisions one at a time, moving left to right without the ability to look ahead, reconsider, or revisit an earlier choice. For tasks where the early moves determine whether any solution is reachable at all, that left-to-right constraint is not a minor inconvenience. It is a structural block.

The authors drew the analogy to human reasoning. Humans solving hard problems do not commit to a single chain of thought. They sketch multiple approaches, recognize when one is not working, abandon it, and try a different path. That kind of deliberate exploration, familiar from fields like combinatorial search and planning in classical AI, had never been built into the prompting loop for language models. ToT is the first framework to do it.

What the framework does: thoughts, evaluation, and search

The ToT framework has three moving parts. First, the model generates multiple thoughts at each step. A thought is a coherent chunk of text that represents one intermediate step toward a solution. Rather than producing a single next step, the model produces several candidate steps, typically by sampling with temperature or by prompting it to generate distinct alternatives.

Second, the model evaluates each thought. It is prompted to rate each candidate step as 'sure,' 'maybe,' or 'impossible' with respect to reaching the goal. This is a critical piece: the same language model that generates the thoughts also evaluates them, using a second type of prompt that asks it to reason about which partial paths are viable. Steps rated 'impossible' are pruned immediately. 'Sure' steps are pursued. 'Maybe' steps are held as candidates for further exploration.

Third, a search algorithm navigates the resulting tree. The paper implements both breadth-first search (BFS) and depth-first search (DFS). BFS keeps the best candidates at each level before expanding further; DFS follows one path to completion and backtracks if it fails. The choice between them depends on the task. For the Game of 24, the paper used BFS with five candidates per step. For mini crossword puzzles, it used DFS with backtracking.

Together, the three parts give the model a form of deliberate planning. It does not pick one path; it considers several, prunes the ones that look unpromising, and searches the space of possibilities in a structured way.

What the benchmarks show

The paper tested ToT on three tasks designed to require non-trivial planning: Game of 24, Creative Writing, and Mini Crosswords.

• Game of 24: given four numbers, find a way to combine them with basic arithmetic to reach exactly 24. GPT-4 with standard input-output prompting solved 7.3 percent of tasks. GPT-4 with chain-of-thought prompting solved 4 percent. GPT-4 with ToT solved 74 percent.
• Mini Crosswords: a 5x5 crossword with ten clues. Standard prompting solved roughly 16 percent of words and 0 percent of complete puzzles. ToT with DFS and backtracking solved 60 percent of words and 20 percent of complete puzzles.
• Creative Writing: four random sentences given as a prompt, model asked to write a coherent story passage ending with each sentence used as a paragraph ending. ToT improved GPT-4 judged quality scores compared to direct generation, though the gains here were more modest than on the structured tasks.

The Game of 24 result is the sharpest demonstration. The task is tractable for humans and has a clear right-or-wrong answer, so the comparison is clean. The jump from 4 percent with chain-of-thought to 74 percent with ToT is not a marginal gain. It is a change in what the model can actually accomplish, achieved by changing how it reasons rather than changing the model itself.

The single-prompt shortcut: three experts

Running full ToT with BFS or DFS requires writing orchestration code that manages multiple model calls, tracks partial states, and implements the search loop. That is more infrastructure than most practitioners want to set up for everyday use.

A simpler approximation was proposed by Dave Hulbert in a GitHub repository published shortly after the ToT paper. The idea is to simulate the tree structure inside a single prompt by asking the model to roleplay as several experts thinking in parallel. A version of the prompt reads:

• 'Imagine three different experts are answering this question. All experts will write down one step of their thinking, then share it with the group. Then all experts will go on to the next step, and so on. If any expert realizes they are wrong at any point then they leave. The question is...'

This is not a faithful implementation of the search algorithm from the paper. It does not do BFS or backtracking in the formal sense. But it forces the model to consider multiple partial solutions simultaneously rather than committing to one, and practitioners have found that it often produces visibly better reasoning on planning problems than a standard chain-of-thought prompt, at the cost of a single longer generation rather than multiple API calls.

When to use Tree of Thoughts

ToT earns its complexity on tasks where the right first step is not obvious and a wrong first step forecloses good solutions. Planning problems, combinatorial puzzles, multi-step logical deduction, and code debugging with many plausible starting points all fit this pattern. For any problem where you would naturally want to sketch two or three approaches before committing, ToT is the prompting technique that lets the model do that.

It adds little value on tasks where the reasoning is straightforward or where there is no meaningful choice to be made early on. Summarization, classification with clear categories, and simple extraction tasks do not benefit from tree search because there is no combinatorial space to navigate. Applying ToT to those tasks adds cost and latency without improving output.

Cost is the main constraint to factor in. The full ToT framework makes many model calls per query, multiplying token cost by the number of candidates times the number of search steps. For tasks that truly require it, the accuracy improvement justifies the cost. For tasks that do not, a single well-crafted chain-of-thought prompt is faster and cheaper. Knowing which category your task falls into is the decision that matters most before reaching for ToT. PromptingIndex covers prompts built on the tree-of-thoughts pattern alongside chain-of-thought and self-consistency, tested across reasoning and planning tasks.