Tree-of-Thought Prompting Explained

TL;DR: Tree-of-thought prompting is a real 2023 research method, not just a synonym for asking for a few options. It generates several candidate reasoning steps, scores them, keeps the strongest, and can backtrack, at a real cost: the paper's own numbers show 5 to 100 times more tokens than chain-of-thought. Most everyday prompts don't need it, and modern reasoning models already do a version of internal deliberation by default.

What is tree-of-thought prompting, exactly?

Most single-search-result summaries flatten it into asking the model to consider several options before answering. That description is close enough to be misleading: it captures the branching part and drops the two things that make the method work, evaluation and backtracking.

The paper frames its own contribution as a generalization of chain-of-thought prompting, and names the framework Tree of Thoughts (ToT). Its own description of what the generalization buys you: "ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices to decide the next course of action, as well as looking ahead or backtracking when necessary to make global choices."

Three verbs matter more than the branching itself: evaluating, looking ahead, and backtracking. A prompt that only asks for three different answers and picks a favorite is doing self-consistency, a related but different and much cheaper technique, closer to why the same prompt can return a different answer twice than to a search procedure.

Where does the technique actually come from?

It's a published, peer-reviewed method, not a community mnemonic. The full citation: Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao and Karthik Narasimhan, "Tree of Thoughts: Deliberate Problem Solving with Large Language Models," first submitted to arXiv on May 17, 2023 (v1), revised December 3, 2023 (v2), and published as a NeurIPS 2023 camera-ready paper. It's listed under arXiv:2305.10601 with a full code repository of prompts and trajectories.

That matters for how much weight to put on any number attached to it: it's a genuine, citable experimental result, run on GPT-4 in mid-2023, not a blog post's summary of a summary.

How is tree-of-thought actually different from chain-of-thought?

The paper is explicit that a specific instantiation requires answering four separate design questions, quoted directly: "A specific instantiation of ToT involves answering four questions: 1. How to decompose the intermediate process into thought steps; 2. How to generate potential thoughts from each state; 3. How to heuristically evaluate states; 4. What search algorithm to use."

Two of those, evaluation and search, are exactly what plain chain-of-thought and even self-consistency lack. The authors describe the gap directly: "Locally, they do not explore different continuations within a thought process – the branches of the tree" and "Globally, they do not incorporate any type of planning, lookahead, or backtracking to help evaluate these different options – the kind of heuristic-guided search that seems characteristic of human problem-solving."

Concretely, the method plugs in a thought generator (sample several candidate next steps), a state evaluator (score or vote on which partial solutions look promising), and a search procedure over the resulting tree, either breadth-first search, keeping a fixed number of the best states at each step, or depth-first search, pursuing the most promising branch and backtracking when a state looks like a dead end. Read post 43's introduction to chain-of-thought first if that baseline isn't already familiar; this page assumes it.

What did the original paper actually measure?

On its hardest reported task, Game of 24 (combine four given numbers into 24 using arithmetic), the paper reports the following success rates against GPT-4:

The headline comparison, quoted directly from the abstract: "in Game of 24, while GPT-4 with chain-of-thought prompting only solved 4% of tasks, our method achieved a success rate of 74%." That's a genuinely large, reported gap on a task picked specifically because it punishes committing to one reasoning path too early.

The paper's second task, a creative-writing exercise that has to end in four fixed sentences, tells a similar story with a softer margin. GPT-4 itself scored the outputs on a 1-10 coherence scale, and "ToT (7.56) is deemed to generate more coherent passages than IO (6.19) and CoT (6.93) on average." Human judges preferred the tree-of-thought passage in 41 of 100 head-to-head pairs against chain-of-thought's 21, with the rest rated about equal. A smaller edge than Game of 24's, and worth noting: it came from a method with only one intermediate step (a short plan, voted on before the passage itself is generated), not a deep search tree.

What do the breadth-first and depth-first search steps actually do?

"Search algorithm" isn't a figure of speech in the paper; it names two specific procedures, and the choice between them is part of setting the method up for a given task.

Breadth-first search keeps a fixed number of the strongest candidate states after every step, discarding the rest before generating the next round of thoughts. The paper uses it for Game of 24 and the creative-writing task, both restricted to a shallow tree of only a few steps, so pruning down to a handful of survivors after each one is cheap enough to search exhaustively.

Depth-first search takes the opposite shape: the paper describes it as exploring "the most promising state first, until the final output is reached", backtracking whenever a branch looks unlikely to succeed. When it does back off, the paper states plainly what happens: "DFS backtracks to the parent state of s to continue exploration." That backtracking step, abandoning a branch entirely and returning to try a different one from an earlier point, is the part a single chain-of-thought pass has no mechanism for at all; once it commits to a wrong early step, there's no path back to it.

Self-consistency, the other close relative worth naming precisely, works differently from both: it samples several complete chains-of-thought independently, then keeps whichever final answer showed up most often across the samples. That helps, the paper explains, "because there are generally different thought processes for the same problem", and it never inspects or compares partial reasoning inside a single chain. Picking the most common answer only makes sense when the space of possible answers is small, like a multiple-choice question; a branching essay outline has no single most-common version to converge on.

Why does tree-of-thought cost so much more than chain-of-thought?

Because it explores instead of committing, and exploration means paying for branches you throw away. The paper is direct about this in its own cost analysis: "Running ToT requires significantly more computations than IO or CoT prompting." On Game of 24 specifically, solving one puzzle with the method used about 5,500 completion tokens, close to the 6,700 tokens spent running 100 independent chain-of-thought attempts, at roughly $0.74 per case against $0.47 for the hundred-sample chain-of-thought baseline (2023 GPT-4 pricing). The paper's general estimate: it "could require 5-100 times more generated tokens than CoT."

That's not a criticism of the method so much as an honest accounting the paper does for itself, closing with its own recommendation: "We recommend using ToT on tasks requiring deliberate reasoning, on which CoT struggles." Most requests don't meet that bar.

Do modern reasoning models already do something like this by default?

Increasingly, yes, at the model level rather than the prompt level, and the three major vendors do not agree on how much of that is still promptable.

OpenAI's own guidance for its reasoning models is unambiguous. It tells developers to avoid chain-of-thought prompts, on the grounds that since these models perform reasoning internally, prompting them to think step by step or explain their reasoning is unnecessary. Google's Gemini 3 migration guide gives matching advice for developers moving off Gemini 2.5, telling them that if they were previously using complex prompt engineering like chain of thought to force the older model to reason, they should switch to a high thinking-level setting on Gemini 3 and simplify the prompt itself. Both vendors are telling users to stop hand-rolling reasoning structure and let the model's internal process handle it.

Anthropic is the outlier, and it's a useful one: rather than treating reasoning as fully internal and unsteerable, it documents the decision as something you can still shape. Its own text: "Whether Claude thinks on a given turn is promptable. Effort sets the overall posture, but you can also shape the decision directly with natural-language guidance, either globally in the system prompt or per message from the user turn." Anthropic even publishes sample wording for both directions:

Extended thinking adds latency and should only be used when it
will meaningfully improve answer quality, typically for problems
that require multistep reasoning. When in doubt, respond directly.

To encourage more of it instead, Anthropic's documented alternative is simply: "This task involves multistep reasoning. Think carefully before responding."

None of this is the tree-of-thought algorithm running inside the model. It's evidence that the specific failure the paper targeted, a model committing to one shallow reasoning path with no way back, is now partly handled by the model itself on hard problems, which narrows the set of cases where hand-built branching prompts still earn their cost.

When does tree-of-thought prompting actually earn its cost?

When three things are all true at once: the task has a real space of distinct next steps (not just wording variations), a partial attempt can be checked or scored before it's finished, and getting it wrong is expensive enough that 5 to 100 times the tokens is a reasonable trade. The paper's own three tasks fit this exactly: Game of 24, a creative-writing plan that has to end in four fixed sentences, and 5x5 mini crosswords, where a wrong letter early on can be checked before the rest of the grid is filled in.

Most everyday requests fail at least one of those tests. A single well-scoped prompt, or a chain-of-thought prompt for anything genuinely sequential, covers the large majority of writing, summarizing, and routine coding work for a fraction of the latency and cost. Reach for something branch-and-evaluate shaped only when a first answer is genuinely a guess among several structurally different approaches, not merely a first draft.

Can you approximate it without building a search algorithm?

Loosely, and it's worth being honest that this is a simplification, not the paper's method. The real algorithm formally scores every partial state and prunes the tree as it goes; a single prompt asking for that in one pass is doing a rough, unscored approximation of it. It's still more than the give-me-a-few-options framing this page opened by rejecting, since it can ask the model to explicitly rule out a branch before picking:

Generate three genuinely different approaches to [task], not
three phrasings of the same approach.

For each one, state its strongest failure mode in one sentence.

Rule out any approach whose failure mode is disqualifying. From
what's left, pick the strongest and explain why in two sentences,
or combine the surviving approaches if that produces a better
result than any single one.

That gets you branching and a form of evaluation in a single request, cheaply. It does not get you real backtracking across multiple steps or a formal search procedure, and it isn't tree-of-thought in the paper's sense: call it a structured-options prompt when you write about it, and save the actual name for the case where you're really running an evaluate-and-search loop, whether by hand or in code. Before you trust whichever approach survives that pass, it's worth red-teaming your own prompt and the answer it produced rather than assuming the elimination step caught everything. If you're deciding how much reasoning depth a task needs before reaching for any of this, post 510 breaks down how vendors let you dial that up or down directly at the model level rather than the prompt level.