Tree-of-Thoughts & Search-Based Reasoning

Give a strong model this puzzle: using 4, 7, 8 and 8 exactly once each, with only + − × ÷ and brackets, make 24.

Give it to a model without built-in thinking, with ordinary step-by-step prompting, and it nearly always opens the same way:

Let me start with the largest numbers. 8 × 4 = 32. Now I need toget from 32 to 24 using 7 and 8. 32 - 8 = 24 — that works!So the answer is 8 × 4 - 8 = 24.

The 7 is never used. The model noticed nothing: by the time it wrote "that works!" the tokens "8 × 4" were fixed in the context, and every later token was predicted in a world where that opening was correct. It found a valid arithmetic identity and quietly dropped an input.

Sometimes it catches itself: "wait, I haven't used the 7". Then it tries again — but the failed attempt is still in the context, and the next attempt is conditioned on it. Attempts three, four and five drift around the same neighbourhood. Occasionally you get twelve paragraphs of increasingly frantic arithmetic ending in a confident wrong answer.

The answer is $(7 - 8 \div 8) \times 4 = 6 \times 4 = 24$. Finding it requires trying $8 \div 8$ first — a move that looks pointless in isolation, since it turns two numbers into a 1. No greedy heuristic proposes it. You get there by trying it, seeing where it leads, and being willing to abandon it.

The real problem: decoding cannot backtrack

Two mechanical facts explain the failure above, and they explain the fix too.

Every emitted token is permanent. Autoregressive generation appends to a sequence; there is no delete. When the model wrote "8 × 4 = 32" it committed — not by choice, but structurally. It can write "that was wrong", but that correction is additional context, not a rollback. The failed branch keeps influencing every subsequent probability distribution, which is why in-context retries cluster rather than exploring freely.

Each choice gets one token's worth of compute. Selecting the first operation took exactly one forward pass. No lookahead, no evaluation of consequences three moves later. A decision that determines the whole solution gets the same fixed budget as the word "the".

Put those together and you have a system doing greedy search with no evaluation function and no undo. It is remarkable it works as often as it does.

The model is not bad at search. It is not doing search — it is doing one greedy left-to-right pass and hoping. Tree-of-Thoughts does not make the model better at anything; it takes the search away from the model and gives it to a program.

Splitting the job in two

Tree-of-Thoughts (ToT) decomposes the work into three parts, and puts each where it belongs.

The model is used only for short, local, single-judgement calls. Nothing asks it to hold a search frontier in its head, because it cannot: the context is its only memory, and a frontier written into the context is just more text competing for attention.

                        [ start ]                        /    |    \                   8÷8=1  8×4=32  7×4=28      <- model proposes                   score7   score4   score5      <- model evaluates                     |        X        |         <- code prunes                7-1=6      (dropped)  28-8=20                score9                score3                   |                     X             6×4=24  ✓

Search strategies

Once search lives in your code, you choose the algorithm. Three are worth knowing, differing in what they assume about your evaluator.

Breadth-first / beam search

Expand every node at depth $d$, score them all, keep the best $k$, move to depth $d+1$. The retained set is the beam and $k$ is the beam width.

This suits problems with a known, uniform depth — a three-step plan, a four-move puzzle — and is safest when your evaluator is noisy, because keeping $k > 1$ means one bad score does not eliminate the right branch. It parallelises well: every node at a level can be scored concurrently.

Depth-first search

Follow one branch to a terminal state. If it fails a validity check, pop back to the last node with untried children and continue. Memory is $O(\text{depth})$ rather than $O(k \times \text{depth})$.

DFS wins when solutions are deep, failure is cheaply and definitively detectable, and any valid solution will do. The 24 puzzle fits perfectly: a branch is dead the moment you cannot reach 24 from the remaining numbers, and that is a code check, not a model call. DFS is a bad fit without a crisp failure test, because you will descend a doomed branch to full depth.

Best-first search

Keep a priority queue of all frontier nodes across all depths, ordered by score. Always expand the highest-scoring node, wherever it sits in the tree.

The most flexible, and the most dependent on evaluator quality — it chases whatever the evaluator rates highly, so a miscalibrated evaluator sends it somewhere useless. It has a subtle bias too: without depth normalisation, shallow nodes score higher simply because fewer commitments have been made and less can be criticised, so the search spreads sideways instead of going deep. Normalise for depth, or add a small depth bonus.

Writing the two prompts

ToT stands or falls on the proposer and the evaluator. Both are short prompts, and both are usually written badly.

The proposer

BADHere's the current state of the problem. What are some optionsfor what to do next? Give me a few ideas.

"A few ideas" gives no count, so you cannot build a fixed-width beam. Nothing forbids near-duplicates, and the highest-probability continuation after one proposal is a rephrasing of it — three wordings of one idea, a branching factor of 1 dressed as 3. And nothing requires proposals to be legal moves from the current state, so you get suggestions that ignore constraints already committed to.

GOODCURRENT STATE  Numbers remaining: [7, 4, 1]  Operations used so far: 8 ÷ 8 = 1  Target: 24Propose exactly 3 candidate next operations.Each candidate must:  - combine exactly two of the remaining numbers with one of + - × ÷  - be genuinely different from the others, not a rewording  - be a legal move: only numbers currently remaining may be usedOutput exactly 3 lines, nothing else, in this form:  <expression> = <result> | remaining: [<numbers after this move>]

The state is rendered explicitly rather than left implicit in a long transcript. "Exactly 3" fixes the branching factor. "Genuinely different, not a rewording" attacks the duplication failure. The rigid output line makes your parser four lines of code instead of a fragile heuristic. And writing the resulting state alongside the move means the next expansion need not re-derive it — the state is carried in the text, the only place it can be carried.

The evaluator

BADRate this partial solution out of 10.

Two mechanical problems. First, an unanchored 1–10 scale collapses: without definitions, rating tokens are dominated by 7 and 8 for anything coherent, so scores carry almost no ordering information and the beam prunes at random. Second, a score generated first comes from a single forward pass with no analysis behind it, and everything after it is rationalisation of a number already committed.

GOODSTATE  Numbers remaining: [7, 4, 1]  Target: 24Assess whether 24 is still reachable from this state.Write your assessment in this exact order:REACHABLE: one of {yes, maybe, no}EVIDENCE: if yes, give one concrete expression that reaches 24.          If no, say which constraint makes it impossible.          If maybe, name the most promising direction.SCORE: an integer 0-10, using this scale:   0-2  = a constraint is already violated, or the target is          provably out of reach   3-4  = no promising direction identified   5-6  = plausible but no concrete route yet   7-8  = a concrete route exists but needs one more non-obvious step   9-10 = a complete valid solution has been found

The scale is anchored: each band has a stated meaning, so the score token is predicted from a description rather than a vague sense of goodness. The evidence line comes before the score, so the score is conditioned on an actual attempt at a solution — not stylistic, it changes what the score is computed from. And the three-way REACHABLE label gives a cheap categorical prune that does not depend on the numeric scale being calibrated.

Put the reasoning before the score, always. A score emitted first is a guess that the following paragraph then defends.

A worked example: a real planning decision

A seed-stage company has six months of runway and four engineers. What to build next? Here is a depth-3 tree with beam width 2, and the scores the evaluator returned.

Level 1 — three strategies:

Beam width 2 keeps B and C, dropping A. A greedy search — beam width 1, which is what plain chain-of-thought effectively does — would keep only B. Hold that thought.

Level 2 — expand both survivors:

The beam now keeps C1 (8.5) and B1 (6.0). The whole B subtree has collapsed. B scored highest at level 1 and every one of its children scored worse than C's best child.

This is the central phenomenon, not an artefact of the example. At level 1 the evaluator was scoring a slogan — "rebuild onboarding" — against a real, measured problem, and it scored well because the diagnosis is sound. Only at level 2, when the proposal carried a duration, did the binding constraint (four engineers, six months) bite. Shallow evaluation rewards whichever option is easiest to describe attractively; depth converts a slogan into something falsifiable.

Level 3 — expand C1 and B1:

The search returns C1a at 9.0. The greedy path — commit to the best level-1 option and never reconsider — terminates at B1a with 6.0. One extra beam slot, costing three extra evaluations at level 2, changed the recommendation and improved the terminal score by 3.0 points. That is the value proposition of ToT in one number.

Implementing best-first search

1import heapq, itertools, json, anthropic23client = anthropic.Anthropic()4_tie = itertools.count()          # keeps heapq from comparing dicts56def call(prompt, max_tokens=2000):7    resp = client.messages.create(8        model="claude-opus-5", max_tokens=max_tokens,9        output_config={"effort": "low"},   # short, local judgements need little thinking10        messages=[{"role": "user", "content": prompt}],11    )12    # thinking is on by default; skip thinking blocks and keep the text13    return "".join(b.text for b in resp.content if b.type == "text")1415def propose(state, b=3):16    text = call(PROPOSER_TEMPLATE.format(state=state, b=b))17    return [ln.strip() for ln in text.splitlines() if ln.strip()][:b]1819def evaluate(state):20    text = call(EVALUATOR_TEMPLATE.format(state=state), max_tokens=1000)21    reachable = "no"22    score = 0.023    for line in text.splitlines():24        if line.startswith("REACHABLE:"):25            reachable = line.split(":", 1)[1].strip().lower()26        if line.startswith("SCORE:"):27            try:28                score = float(line.split(":", 1)[1].strip())29            except ValueError:30                score = 0.031    return score, reachable3233def best_first(root, max_depth=3, beam=2, node_budget=25,34               prune_below=4.0, is_goal=lambda s: False, is_valid=lambda s: True):35    frontier = [(-10.0, next(_tie), root, [root], 0)]   # negated score = max-heap36    seen, expanded, best = {canonical(root)}, 0, (-1.0, None, None)3738    while frontier and expanded < node_budget:39        neg, _, state, path, depth = heapq.heappop(frontier)40        if is_goal(state):41            return {"solution": state, "path": path, "score": -neg,42                    "nodes_expanded": expanded}43        if depth >= max_depth:44            continue4546        children = propose(state, b=beam + 1)47        expanded += 148        scored = []49        for child in children:50            key = canonical(child)51            if key in seen or not is_valid(child):   # free prunes, done in code52                continue53            seen.add(key)54            s, reachable = evaluate(child)55            if reachable == "no" or s < prune_below:56                continue57            scored.append((s, child))5859        scored.sort(reverse=True, key=lambda t: t[0])60        for s, child in scored[:beam]:               # only the best survive61            heapq.heappush(frontier, (-s, next(_tie), child, path + [child], depth + 1))62            if s > best[0]:63                best = (s, child, path + [child])6465    return {"solution": best[1], "path": best[2], "score": best[0],66            "nodes_expanded": expanded, "note": "budget exhausted, best-so-far returned"}

Four details in that code are load-bearing.

• is_valid is a Python function, not a model call. Check any code-checkable constraint in code: a number reused, a budget exceeded, code that fails to parse. It is free, deterministic and correct, and every node it kills is a model call you did not make.
• seen deduplicates canonicalised states. Different proposal wordings routinely produce the same state, and paying to evaluate the same state twice is pure waste.
• node_budget is a hard cap. Without it, a well-scoring but unsolvable region will absorb an unbounded number of calls.
• The function returns best-so-far when the budget runs out, not an exception. Search under a budget must be anytime: you want the best partial answer, not nothing.

What it costs

Assume an expansion call is roughly 600 input and 350 output tokens, and an evaluation call is 500 input and 150 output, billed at 5 dollars per million input and 25 per million output. Any thinking the model does bills as output on top, which is one reason the code above keeps effort low for these small calls.

• One expansion: $(600 \times 5 + 350 \times 25) / 10^6 = 0.01175$ dollars.
• One evaluation: $(500 \times 5 + 150 \times 25) / 10^6 = 0.00625$ dollars.

Now compare three approaches on a branching factor of 3 and depth of 3:

Read the exhaustive row carefully: at depth 3 with branching 3 there are $3 + 9 + 27 = 39$ nodes, 13 of them internal and needing expansion. Beam width 2 expands the root plus two nodes at each of the next two levels — 5 expansions — and evaluates $3 + 6 + 6 = 15$ nodes. Pruning cut cost by 62% and, in the worked example, cost nothing in quality.

Push depth to 4 and the exhaustive tree has 120 nodes; depth 5 gives 363. Cost is $O(b^d)$ and there is no prompt that changes that. Pruning is not an optimisation you add later; without it, ToT is unaffordable past depth 3.

Pruning rules, cheapest first

Prefer relative rules to absolute ones. "Is this better than that?" is far more reliable than "is this a 7 or a 6?", because ranking needs only the ordering to be right, while thresholding needs the scale itself to mean something.

How it compares to the alternatives

The row that decides applicability is the last-but-one. Voting needs an answer you can compare; ToT needs something stronger: a half-finished attempt you can meaningfully score. If a partial state tells you nothing about whether the finished one will be good, there is nothing to prune on, and the tree degenerates into an expensive way to sample.

Where people get this wrong

What this means when you build something

Start with what has changed since Tree-of-Thoughts was published (Yao et al., 2023, which used this same 24 game). Reasoning models now do a version of propose, evaluate and backtrack inside their own thinking: they try an opening, notice it fails, and try another before writing the answer. A current model at a high effort setting often solves puzzles of this size in one call, so an explicit tree is no longer the default fix for "the model commits too early". It still earns its cost when your code can check partial states (a failing test, a broken constraint), when each step is an expensive or real action rather than a thought, when the search is too large for one context, or when you need the whole tree logged for audit.

Reaching for ToT should follow a specific diagnosis, not a wish for better answers. Ask three questions in order:

1. Does the task decompose into steps where early choices constrain later ones? If the steps are independent there is no tree — just do them.
2. Can I score a partial state? Not the finished answer — a half-built plan, a half-written function, a half-solved puzzle. If not, ToT has nothing to prune with.
3. Is any part of the validity check expressible in code? Every constraint checkable in Python is a free prune, and free prunes are what make the exponential affordable.

If all three are yes, ToT usually pays for itself. If the second is no, sample several complete attempts and pick between them — cheaper and better suited.

Then design for the budget from the start. Fix a node cap before the depth, because the cap bounds your bill. Make the search anytime, so a cap that is hit returns the best partial result rather than failing. Log the whole tree, not just the winning path — when a recommendation looks wrong, the question is almost always what got pruned and on what score, and the winning branch cannot answer it. And build the evaluator first: a mediocre proposer with a good evaluator finds decent answers slowly, while a brilliant proposer with a bad evaluator confidently prunes the right branch and never tells you.

The 24 puzzle is the miniature of all this. The winning move — $8 \div 8 = 1$ — looks like a step backwards and no greedy heuristic proposes it. You find it by being able to try things and take them back. That capability lives in your search loop, not in the model.