Tree of Thoughts
Branch one hard question into a few candidate thoughts, score each one, and keep searching only the winners, walking back when a path dies.
Why Does This Exist?
A single chain of thought writes one line of reasoning and never looks back. You ask for steps, you get steps, and each new token reads everything before it. That is enough for a two hop question. It falls apart when the second step is a guess that decides the rest.
Say you must pack a fragile vase in two moves, or solve a puzzle where one wrong turn poisons the whole path. Pick newspaper instead of foam at step one and step two can't save you. The model still reads that bad step as context, so it keeps going with confidence. You have watched this happen: one shaky line, then smooth nonsense all the way to the answer.
Tree of thoughts flips the job from storytelling to search. From your current state you grow a few different next thoughts, you score each one, you keep the winners and drop the losers, and you walk back when a path dies. You pay for that safety with extra calls, so you don't use it everywhere.
This page covers that loop: growing thoughts, scoring them, and searching with the scores, plus one small run with scores 2, 7, and 9. Voting over finished chains belongs to self-consistency. Keeping token paths alive during decoding belongs to beam search. Training the habit into weights belongs to reasoning models.
Think of It Like This
A cave maze with chalk and string
You walk into a cave maze with chalk and a ball of string. You tie the string at the entrance so you can always find your way back.
At the first fork you peek down three tunnels. The left ends after ten steps, so you chalk a 2 on its wall. The middle bends on but feels tight, so you chalk a 7. The right catches a breeze and keeps going, so you chalk a 9. You follow the 9 first with your string trailing behind you. When the 7 tunnel later hits a rockfall, you don't saw through rock. You follow the string back to the fork and take the 9 you already liked.
Where it stops: in a real cave you see the dead end with your eyes. Here the chalk numbers are another model guess, so a smooth wrong tunnel can still earn a 9. Chalk is also free and model calls are not. Each peek and each score costs you time and money.
How It Actually Works
You search over text. Each node is a state, each edge adds one thought, and scores tell you where to spend your next call.
The four moving parts
- Thought generator. Given , which means your state so far (the question plus the thoughts you kept), propose , which means how many different next thoughts you ask for. Here is 3, so one call returns three candidates. You want variety, not three rewordings of the same idea.
- State evaluator. Given each new state, return , which means a score for how promising it looks. Here scores run 1 to 10. It can be a number, a vote, or a yes or no. The scorer is usually another prompt, so treat it as a guess, not a measurement.
- Search order. Keep , which means how many states survive each depth, and , which means how many thought steps you sit from the root. Here is 2 and the cap on is 2. Breadth first expands every survivor at one depth before going deeper. Depth first dives down the best child and only walks back when it hits a dead end.
- Prune and backtrack. Drop anything under your bar and stop expanding dead ends. Backtracking means returning to the last fork you scored and trying the next best child. No extra math. You already paid for those scores.
Breadth first or depth first
Breadth first suits you when scoring is cheap and you trust it. You expand both survivors, compare their children side by side, and prune once per depth. Depth first suits you when the answer sits deep and each expansion costs a lot. You chase the 9, and you only pay for the 7 branch if the 9 dies.
The trade is direct. Larger and larger cover more of the space, and each extra node costs another generate plus another score. If you batch one generate and one score per node, four expanded nodes cost eight calls. A single chain costs two. You buy coverage with calls and waiting.
Don't use the tree when one chain already works. If the question is one hop, if you must answer now, or if a wrong middle step can't be checked, the tree adds bills without adding wins. Use it when a single chain keeps dying in the same place and you can spot a dead end when you see one.
It rests on two bets. One, your generator makes truly different candidates. Two, your scores point at real progress. When either fails, the search walks with confidence into the wrong tunnel. That is why grounding the scorer matters more than growing the tree.
Worked example
Task: pack a fragile vase in two packing moves. Start from , which means the bare task with no steps yet. Set to 3, to 2, the bar to 5, and the cap on to 2.
Depth 1. You grow three first moves. A is newspaper only, with of 2. B is bubble wrap, with of 7. C is foam and box, with of 9. Sorted, 9 beats 7 beats 2. You keep C and B and prune A. One generate plus one score so far, two calls.
Depth 2. You expand both survivors. B1 is tape shut with the vase touching cardboard, with of 1. It breaks your padding rule, so you mark it dead. C1 is fill gaps, seal, label fragile, with of 8. You keep C1 and drop B1, then walk back from B1 to the fork. Two more nodes, four more calls, six total.
Finish. You expand C1 once into the sealed solution. That is one more generate plus one more score. Four expanded nodes times two calls each is 8 calls. Written out, . A single chain would have cost 2, so you paid four times the calls to avoid committing to newspaper at step one.
Code
This snippet replays the run above with fixed scores, so you can see pruning and backtracking without paying for calls.
from typing import Dict, List
scores: Dict[str, int] = {"A": 2, "B": 7, "C": 9, "B1": 1, "C1": 8}
def keep_top(names: List[str], width: int) -> List[str]: return sorted(names, key=lambda n: scores[n], reverse=True)[:width]
depth1: List[str] = keep_top(["A", "B", "C"], 2)depth2: List[str] = keep_top([n + "1" for n in depth1], 2)alive: List[str] = [n for n in depth2 if scores[n] >= 5]
path: List[str] = ["START", depth1[0], alive[0], "SOLUTION"]calls: int = 2 * 4 # s0, B, C, C1, one generate plus one score each
print(path) # -> ['START', 'C', 'C1', 'SOLUTION']print(alive) # -> ['C1']print(calls) # -> 8Both the path and the count match the hand run: C beats B beats A, C1 is the only child above the bar, and four nodes at two calls each is eight.
Watch Out For
The scorer loves a smooth wrong answer
Symptom: your 9 path reads beautifully and scores high, then ends at a dead end you could have spotted. The search chases fluency because the scorer rewards it. You burn eight calls to reach a polished wrong box.
Fix: ground the scorer before you grow the tree. Give it a short rubric with hard checks, such as whether the vase touches cardboard, and ask for three votes, not one. Keep a branch only when the votes agree it clears the bar. Where you have a hard check, use it. Run the code, check the sum, test the constraint. One deterministic fail beats three fluent 9s.
You pay tree prices for chain questions
Symptom: you spend eight calls and extra waiting on a question a single chain of thought answers in two. The bill climbs, the user waits, and accuracy doesn't move.
Fix: earn the tree. Start from a single chain, and switch only when it keeps failing at the same fork and you can name the dead end rule. Keep at 2 or 3, at 1 or 2, and cap depth at 2. Stop early when every score sits under 5. When branches don't help, fall back to a single chain or to self-consistency.
The Quick Version
- Tree of thoughts grows a few next thoughts, scores each one, and searches only the winners instead of betting on one chain.
- A thought is one intermediate step, and its score is a model guess about promise, not proof the step is right.
- Breadth first keeps the top few states at each depth, while depth first chases the best child and walks back from dead ends.
- With scores 2, 7, and 9 and keep width 2, the 2 is pruned and the 9 branch is finished first through the 8.
- Four expanded nodes at two calls each is eight calls, so the tree costs about four times a single chain on this run.
- Use the tree only when one chain keeps dying at the same fork and dead ends can be checked, and ground the scorer with a rubric or a hard test.