Tree- & Graph-of-Thought Planning

Chain-of-thought (CoT) asks the model to think step by step, but it writes one chain top to bottom. If the third step is a wrong turn, every step after it inherits the mistake — there is no going back. For a creative essay that's fine. For a puzzle with a hidden solution path, it's fatal: the model commits to a guess before it can tell whether the guess leads anywhere.

Tree-of-Thoughts (ToT) removes the commitment. Instead of one chain, the model explores a tree of partial solutions. At each step it generates several candidate next thoughts, evaluates how promising each one looks, keeps the good branches, and prunes the rest. When a branch dead-ends, it backtracks and tries another. This is just classic state-space search — BFS, DFS, beam — with the language model standing in for both the move generator and the evaluator.

The mental model: CoT is writing your answer in pen; ToT is sketching several options in pencil, crossing out the bad ones, and following the best. The model already contains the knowledge to solve hard problems; ToT gives it a way to search for the path instead of betting on the first one it sees.

ToT was introduced by Shunyu Yao and colleagues at Princeton (NeurIPS 2023). A thought is a coherent chunk of text — one intermediate step — and the tree is searched by an external orchestrator (Python), not inside a single prompt. Four design choices define a ToT system:

1. Thought generation — propose (generate dependent next steps sequentially; good for Game of 24) or sample (generate independent thoughts in parallel; good for creative writing).
2. State evaluation — value (score each state independently, e.g. 1–10 or sure/maybe/impossible) or vote (have the model compare states and vote for the best).
3. Search algorithm — BFS keeps the top b states per level (beam search); DFS dives deep and backtracks on failure.
4. Limits — branching factor, beam width, and max depth to keep the search finite.

Every generation and evaluation is a separate LLM call; the search logic lives in code.

def tot_bfs(x, gen, evaluate, steps, b=5, k=3):
    states = [""]  # frontier of partial solutions
    for _ in range(steps):
        # 1. GENERATE: expand each state into k candidate next thoughts
        cands = [s + step for s in states for step in gen(x, s, k)]
        # 2. EVALUATE: score each candidate (a separate LLM call)
        scored = [(c, evaluate(x, c)) for c in cands]
        # 3. SELECT: keep the best b (prune the rest = backtracking)
        states = [c for c, _ in sorted(scored, key=lambda t: -t[1])[:b]]
    return states[0]

The headline result: on Game of 24 (combine four numbers with +−×÷ to make 24), GPT-4 with standard CoT prompting solved just 4% of puzzles. The same model wrapped in ToT solved 74% — roughly an 18x jump, with no change to the model's weights.

What changed wasn't knowledge; it was search. Game of 24 has a large combinatorial space and a clear failure signal at each step (a partial result that can't reach 24 is dead). CoT picks one arithmetic path and usually picks wrong. ToT generates several, prunes the impossible ones early, and backtracks — so it reliably finds the narrow path that exists.

That tells you exactly when ToT pays off. The ingredients are: (a) a large search space with hidden solution paths, (b) a strong intermediate evaluation signal — you can tell a good partial state from a bad one — and (c) value in lookahead and backtracking. Mathematical puzzles, constraint satisfaction, crosswords, and planning problems fit. Open-ended writing, summarization, and most everyday tasks do not — their evaluation signal is weak or subjective, so the extra branches just burn tokens.

A tree has one limitation built in: every thought has exactly one parent. You can branch, but you can never combine two branches. Graph-of-Thoughts (GoT) — Maciej Besta et al., ETH Zurich, AAAI 2024 — drops that constraint. Thoughts become vertices in an arbitrary directed graph, and edges express dependencies, so the orchestrator can do things a tree forbids:

• Aggregate / merge — fuse several partial thoughts into one stronger thought (e.g. merge independently-sorted sub-lists).
• Refine — loop a thought back through the model with feedback to improve it in place.
• Distill — collapse a sprawling subgraph into a compact result.

The classic example is sorting: split the list, sort the pieces in parallel branches, then merge them — a move a tree literally cannot represent. GoT reports a 62% quality improvement over ToT on sorting tasks while cutting cost by over 31%, precisely because merging avoids redundant re-derivation.

The trade-off is engineering complexity. A tree is a clean recursive search; a graph is a workflow you design — decide which thoughts merge, where feedback loops close, and how to avoid cycles. GoT is most worth it when sub-problems are independent and recombinable.

Structured search is expensive by construction. Each node expansion is generation plus evaluation, and depth times branching multiplies fast: a beam of 5 across 3 steps can mean 5–10x more LLM calls than CoT, with matching latency and dollars. You manage this with the levers in your code:

• Beam width / branching — fewer candidates per level.
• Pruning — discard hopeless states immediately (the impossible value).
• Early stopping — quit a branch or the whole search once a solution is verified.
• Cheaper evaluator — score states with a smaller, faster model than the generator.

A decision rule that holds up in practice:

If you can't articulate a good evaluation signal for partial solutions, ToT has nothing to steer with — and you're paying 10x for noise. Start with CoT; reach for search only when a measurable evaluation signal and a real search space are both present.

The biggest 2025–2026 question: didn't o3 and DeepSeek-R1 make this obsolete? No — they're a different thing. The simplest way to see it: ToT/GoT put the search outside the model, in your Python; reasoning models put the search inside the model, in its weights. Concretely, ToT/GoT are prompt-level external frameworks — no training, search orchestrated in your code, one LLM call per thought. Trained reasoning models (OpenAI o1/o3, DeepSeek-R1, Claude extended thinking) have internalized sequential search via reinforcement learning on long chain-of-thought traces. They explore alternatives implicitly, inside a single stream of tokens — there's no tree in your orchestrator.

Each has an edge. Reasoning models are simpler to use (one call) and often match or beat hand-built ToT on math and code. But they can't explicitly parallelize independent branches or expose an interpretable decision tree with a real tool call at each node — which is exactly what an agent sometimes needs. So ToT survives as an orchestration pattern for branching, tool-using agentic search.

The research is converging the two. LATS (ICML 2024) fuses Monte Carlo Tree Search with LLM agents (92.7% pass@1 on HumanEval). Adaptive Graph-of-Thoughts (Feb 2025) unifies chain/tree/graph as a dynamic DAG at test time — up to 46.2% gains on GPQA with no training. ToTRL (May 2025) trains the tree into the weights. The direction is clear: make structured search both cheaper and trainable.