Tree-of-thoughts

Overview

Tree-of-thoughts, often shortened to ToT, is a method that lets a language model explore several lines of reasoning instead of following only one. The problem is broken into intermediate steps called thoughts. At each step the model proposes a few possible next thoughts, judges how promising each one is, keeps the best and drops the rest. If a branch turns into a dead end, the search goes back and tries another. The result is a search over a tree of partial solutions, guided by the model's own evaluations.

This matters because ordinary step-by-step reasoning, known as chain-of-thought, commits to its first idea at every step. One early mistake can ruin the whole answer, and the model has no way to go back. Tree-of-thoughts adds the ability to look ahead, compare options and backtrack, which helps on problems where early choices matter and wrong paths are common.

An everyday comparison is solving a maze on paper. One person draws a single line and hopes it reaches the exit. Another person, at each fork, glances down each path, rules out the ones that clearly hit a wall, follows the most promising one, and returns to an earlier fork if it fails. The second person uses more pencil, but reaches the exit far more often. Tree-of-thoughts is the second person.

What it is

Tree-of-thoughts is a reasoning framework that sits around a language model. The model is used for two jobs, generating thoughts and evaluating them, while a search algorithm decides what to explore.

The size of a "thought" is a design choice. For a maths puzzle it may be one equation. For writing it may be a paragraph plan. For a crossword it may be one filled word.

Where it came from

Tree-of-thoughts was introduced in the paper "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" by Shunyu Yao and colleagues from Princeton University and Google DeepMind, posted in May 2023 and presented at NeurIPS 2023. A separate paper by Jieyi Long, also in May 2023, proposed a similar tree-based idea with a controller and memory.

The Yao paper tested three tasks designed to need planning or search: the Game of 24, creative writing and mini crosswords. In the Game of 24, where four numbers must be combined with arithmetic to make 24, GPT-4 with chain-of-thought prompting solved 4 per cent of the test puzzles, while tree-of-thoughts solved 74 per cent.

The work built on chain-of-thought prompting (2022) and self-consistency, which samples several reasoning chains and takes a majority vote. Later work generalised the tree into a graph, as in Graph of Thoughts (2023), and combined tree search with learned value models. The rise of reasoning models, which are trained to explore and check alternatives inside a long internal reasoning process, has reduced the need for explicit tree-of-thoughts prompting in many tasks, but the idea of search over partial solutions remains influential.

How it works

Step 1: Decompose the problem

Decide what one thought is. It should be small enough that the model can propose several good options, and large enough that the model can judge whether it helps.

Step 2: Generate candidate thoughts

From the current state, the model proposes several next thoughts. Two styles are common. Sampling asks the model independently several times, which works when the space of thoughts is rich, such as writing. Proposing asks for several distinct options in one prompt, which avoids duplicates when the space is constrained, such as arithmetic steps.

Step 3: Evaluate states

The model judges each new state. It can give a value, such as "sure", "likely" or "impossible" to reach the goal, or a score. Or it can vote across several states for the most promising. Where possible, add cheap checks in code; for example, a partial arithmetic expression can be checked exactly.

Step 4: Search

The search algorithm uses the evaluations:

• Breadth-first search keeps the best few states at each depth and expands them all, level by level. It suits problems with a small, known number of steps.
• Depth-first search follows the most promising branch to the end, backtracking when an evaluation says the branch cannot succeed. It suits deeper problems.

More advanced variants use beam search or Monte Carlo tree search.

Step 5: Stop and answer

The search stops when a state is judged a complete, valid solution, or when the budget runs out. The best solution found is returned. Logging the explored tree helps debugging.

Key concepts and terms

A worked example

This scenario is illustrative and uses the Game of 24 from the original paper. The numbers are 4, 9, 10 and 13.

1. Thought size. One thought combines two of the remaining numbers with one operation.
2. Depth 1. The model proposes candidates, such as 13 - 9 = 4 (left: 4, 4, 10), 10 - 4 = 6 (left: 6, 9, 13), 9 + 13 = 22 (left: 4, 10, 22) and 4 × 9 = 36 (left: 10, 13, 36).
3. Evaluate. For each remaining set, the model judges whether 24 can still be reached. It rates (4, 10, 22) "impossible" and (10, 13, 36) "unlikely". It rates (6, 9, 13) and (4, 4, 10) "likely".
4. Breadth-first, keep the best 2. From (6, 9, 13), the model tries 13 - 9 = 4, leaving (4, 6). From (4, 4, 10), it tries 10 - 4 = 6, leaving (4, 6).
5. Final step. From (4, 6), it proposes 4 × 6 = 24. A code check confirms the result.
6. Answer: (10 - 4) × (13 - 9) = 24.

A single chain-of-thought attempt that began with 9 + 13 = 22 would have had no way back. The tree found the solution by comparing branches early. The cost was many more model calls than a single chain, which is the central trade-off.

Strengths and limitations

Strengths:

• Recovers from early mistakes through backtracking.
• Large gains on puzzles and problems where wrong paths are common.
• Works with existing models through prompting, without training.
• Modular: thought size, evaluator and search can be tuned per task.
• The explored tree gives an inspectable record of reasoning.

Limitations:

• Much more expensive than a single reasoning chain, often by an order of magnitude or more in model calls.
• Slower, because of many sequential steps.
• Depends on a good evaluator; if the model misjudges states, search goes wrong.
• Needs task-specific design of thoughts and prompts.
• Brings little benefit on tasks the model already solves in one pass.
• Modern reasoning models capture some of the same benefit internally.

How it compares with alternatives

Practical guidance and best practices

1. Try plain chain-of-thought, a reasoning model or self-consistency first; use ToT only if they fall short.
2. Define thoughts at a size the model can both propose and judge.
3. Replace model evaluation with code checks wherever an exact check is possible.
4. Keep the branching factor and beam width small, such as 3 to 5.
5. Set hard limits on depth and total calls; see cost and latency budgets.
6. Use breadth-first search for shallow, fixed-depth problems and depth-first for deeper ones.
7. Cache evaluations of repeated states.
8. Measure accuracy and cost against simpler baselines on the same test set with evals.

Common mistakes

• Using tree-of-thoughts for simple tasks where one pass already works.
• Letting the tree grow without a budget, causing huge costs.
• Making thoughts too large to evaluate, or too small to matter.
• Trusting the model's state evaluations where an exact check exists.
• Comparing ToT with a weak baseline instead of a strong reasoning model.
• Forgetting to log the tree, which makes failures hard to understand.

Frequently asked questions

What is tree-of-thoughts?

It is a reasoning method where a language model generates several possible next steps, evaluates them, keeps the promising ones and backtracks from dead ends, searching a tree of partial solutions.

Who invented it?

The best-known version comes from Shunyu Yao and colleagues at Princeton University and Google DeepMind, in a May 2023 paper presented at NeurIPS 2023. A similar idea was published by Jieyi Long the same month.

How much does it help?

It depends heavily on the task. In the original paper, on the Game of 24, GPT-4 solved 4 per cent of puzzles with chain-of-thought and 74 per cent with tree-of-thoughts. On tasks without many dead ends the gain is much smaller.

Is it the same as self-consistency?

No. Self-consistency samples several complete reasoning chains and votes on the final answer. Tree-of-thoughts evaluates partial solutions during reasoning and can abandon or extend branches.

Do reasoning models make tree-of-thoughts obsolete?

Not entirely, but they reduce the need for it. Reasoning models are trained to explore alternatives internally. Explicit tree search remains useful when you can add exact checks or need a visible, controllable search.

How is it used in agents?

Agents can apply the idea to planning: propose several candidate plans or next actions, evaluate them, and pursue the best, backtracking if results are poor. See plan-and-execute.

Glossary

• Thought: one intermediate reasoning step.
• State: the problem plus the thoughts chosen so far.
• Branch: one path through the tree.
• Evaluator: the judge of how promising a state is.
• Breadth-first search: level-by-level exploration.
• Depth-first search: deep exploration with backtracking.
• Beam width: number of states kept per level.
• Pruning: removing weak branches.
• Backtracking: returning to an earlier choice.

Summary

Tree-of-thoughts turns reasoning into a search. A language model proposes several next thoughts, evaluates partial solutions and, guided by breadth-first or depth-first search, keeps the best branches and backtracks from dead ends. Introduced in 2023, it delivered large gains on puzzles such as the Game of 24, at a high cost in model calls. Use it when early choices matter and simpler methods fail, add exact checks where you can, and keep a strict budget.

Related

It belongs to Patterns in my stack, under Agentic AI. Others in the same group: