Tree-of-Thought Reasoning
Beyond a single linear chain of thought
Chain-of-thought prompting asks a model to reason step by step within a single linear sequence, and self-consistency improves on that by sampling several independent full chains and voting. Tree-of-Thought (ToT) reasoning (Yao et al., 2023) goes further by explicitly structuring the reasoning process as a tree: at each step, the model generates several candidate 'next thoughts,' evaluates how promising each one is, and chooses which branches to continue exploring — allowing deliberate search, backtracking, and lookahead, rather than committing to one path from the start or only comparing complete, independent attempts.
The four components of a ToT system
A Tree-of-Thought framework is built from four pieces: (1) thought decomposition — breaking the problem into discrete intermediate steps small enough to evaluate individually; (2) thought generation — prompting the model to propose several candidate next steps from the current state, either by sampling independently or by proposing a structured list; (3) state evaluation — scoring each candidate thought's promise, either by asking the model to rate it directly, or by a heuristic/voting scheme; (4) search algorithm — a strategy (breadth-first search, depth-first search, or beam search over thoughts) that decides which branches to expand, prune, or backtrack from, using the evaluation scores from step 3.
def tree_of_thought_bfs(problem, llm, breadth=3, depth=3, beam_width=2):
"""Breadth-first search over reasoning states, keeping the top beam_width
states at each depth, similar to beam search but over 'thoughts' not tokens."""
frontier = [{"state": problem, "history": []}]
for level in range(depth):
candidates = []
for node in frontier:
next_thoughts = llm.propose_thoughts(node["state"], n=breadth)
for thought in next_thoughts:
score = llm.evaluate_thought(node["state"], thought)
candidates.append({
"state": thought,
"history": node["history"] + [thought],
"score": score,
})
candidates.sort(key=lambda c: c["score"], reverse=True)
frontier = candidates[:beam_width]
if any(llm.is_solution(n["state"]) for n in frontier):
break
best = max(frontier, key=lambda n: n["score"])
return best["history"]Evaluation is the hard part, not generation
Chain-of-thought vs self-consistency vs tree-of-thought
| Method | Structure | Backtracking | Relative cost |
|---|---|---|---|
| Chain-of-thought | Single linear path | No | 1x |
| Self-consistency | N independent linear paths, vote at the end | No | ~Nx |
| Tree-of-thought | Branching tree, evaluated and pruned per step | Yes | Highest, varies with breadth/depth |
Where it earns its cost
Tree-of-Thought shows its biggest gains on problems that genuinely require search and backtracking — puzzles like Game of 24, crossword-style constraint satisfaction, and planning tasks where an early wrong commitment dead-ends the whole attempt and a model would otherwise have no way to recover within a single linear chain. For tasks that are more about reliable execution of a known procedure than exploration, the extra search overhead usually isn't worth it over simpler chain-of-thought or self-consistency.
Cost grows fast with breadth and depth
What's Next?
Search-based reasoning methods like this push harder on what a model can do purely from its own internal knowledge and generated text. The next way to push further is giving the model access to external, up-to-date knowledge during the reasoning process itself, rather than relying solely on what it already knows.
I build these systems professionally.
Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.