Tree of Thoughts and LATS

In plain words

Solving a hard problem in one straight line is like filling a Sudoku in pen: one early mistake ruins everything after it. Tree of Thoughts lets the agent try several next steps, score each one, and keep only the promising branches. LATS goes further, adding real tool results and short notes on failure to guide that search. It works well, but it costs many times more calls.

How it flows

A tiny example

state = start
for _ in range(depth):
    kids = propose(state)          # policy: K next thoughts
    scored = [(judge(k), k) for k in kids]
    scored.sort(reverse=True)
    state = scored[0][1]           # keep the best, drop the rest
print(state)

Notice that judge() runs on every child, so cost grows with K at each level, not just with depth.

What you will learn

• Why a single line of reasoning breaks the moment the first step is wrong.
• How Tree of Thoughts turns thinking into a tree you can branch and prune.
• How LATS adds tools, scoring and reflection on top of that tree.
• When search is worth the extra cost, and when it quietly makes things worse.

The problem, simply

Think of a Sudoku puzzle in the newspaper. You write a 7 in one box early, feel confident, keep going. Twenty boxes later nothing fits. The mistake was not the twentieth box. It was that 7.

In pen, you are stuck. In pencil, you erase, go back to that box, try a 3, and continue. Same brain, same puzzle. You just allowed yourself to go back.

A model doing chain-of-thought is writing in pen. One step, then the next, in a straight line, with no way back. If step two was wrong, steps three to ten are careful reasoning on a bad start.

There is a classic test for this called Game of 24: combine four given numbers with plus, minus, multiply and divide to make exactly 24. Straight-line reasoning gets it right only about 4 times in 100. Not because the arithmetic is hard, but because it commits to a wrong first move and cannot undo it.

The idea

Reasoning as a tree, not a line

Instead of one chain, generate several candidate next thoughts. Score each one. Keep the good ones, throw away the bad ones, and continue from the survivors.

That is Tree of Thoughts, usually written as ToT. It comes from a 2023 research paper. The name sounds heavy but the structure is simple:

• A node is one coherent intermediate step. Not a word, not a token. A whole small thought, like "6 minus 1 gives 5".
• Each node can expand into K children, K being however many alternatives you ask for.
• The model then scores itself on each child, with a simple prompt: label each option sure / likely / impossible, or mark it out of 10, or make candidates vote.
• A search strategy picks where to go next: breadth first, depth first, or beam search, where you keep only the top few at every level.

With this branching, Game of 24 accuracy goes from about 4 in 100 to about 74 in 100. Same model. Only the shape of the thinking changed.

IMP

Note: The scoring step is what makes this work. If the model cannot tell a promising branch from a hopeless one, a tree is just a more expensive straight line.

A worked example

Suppose Priya gives the agent the numbers 4, 6, 4, 1 and asks for 24.

A straight chain starts with "4 times 6 is 24", feels very happy, then finds a 4 and a 1 still left over and no way to keep 24. Dead end, no way back.

A tree keeps three options alive at the first level: "4 times 6 = 24", "6 minus 1 = 5", "4 plus 1 = 5". It scores each by peeking a little further ahead. The 24 branch scores badly once it looks ahead, so it gets pruned. The "6 minus 1 = 5" branch survives, becomes "4 times 5 = 20", then "20 plus 4 = 24". Solved.

Notice what happened. The winning first move looked less impressive than the obvious one. Only branching found it.

LATS: search that touches the real world

ToT thinks in a tree but never touches a tool. LATS, from a 2024 paper, adds tool use and learning from failure. Read it as search plus tools plus reflection.

In LATS the same model plays three different roles:

• Policy — proposes the possible next actions. This is the ReAct style, where the model alternates between thinking and calling a tool.
• Value function — looks at a half-finished attempt and gives it a score. This is the ToT self-evaluation.
• Self-reflector — when an attempt fails, writes a short note in plain English about why, and that note is fed into the next attempt. This is the Reflexion idea from earlier in this module.

The important part: real tool results go into the score. If the agent ran the unit tests and three failed, that is a fact, not an opinion. Search guided by facts beats search guided by the model's own confidence.

On HumanEval, a standard Python coding benchmark where the model must write functions that pass hidden tests, LATS reported about 92.7 percent pass on the first accepted answer.

The four steps of MCTS

LATS runs on Monte Carlo Tree Search, MCTS for short. It is an old game-playing algorithm, the same family that powered chess and Go engines. Four steps, repeated:

Select walks from the root down to a leaf using a formula called UCT. UCT adds two things: how good this branch has looked so far, plus a bonus for branches you have barely tried. The bonus is scaled by a constant c. Small c means stick to what is working, large c means go explore.

Expand asks the policy for a few children. Simulate plays one attempt to the end and scores it. Backpropagate pushes that score back up, updating every ancestor's visit count and average.

IMPRemember: search is not magic reasoning. It is the same model, called many more times, with a scorekeeper deciding which attempts survive.

The cost, honestly

On Game of 24, ToT burns something like 100 to 1000 times the tokens of a single chain. That is not a typo. LATS is in the same range.

So use search only when all three of these hold:

• One straight attempt genuinely is not enough.
• Correctness matters more than speed.
• You have a cheap and honest scorer — unit tests for code, an exact target for a puzzle.

Warning

Warning: If your task has one right answer and your scorer is noisy, search actively hurts. It will happily hunt down a confidently wrong answer that scores well.

Build it

# Toy "make 24 from 4 6 4 1" search. No API, no internet: the "model" is a function.
import math, random, itertools
random.seed(7)
TARGET, START = 24, (4, 6, 4, 1)
CALLS = [0]

def expand(nums):
    """Policy: propose child states by combining any two numbers once."""
    kids = []
    for i, j in itertools.combinations(range(len(nums)), 2):
        rest = [nums[k] for k in range(len(nums)) if k not in (i, j)]
        a, b = nums[i], nums[j]
        for val, txt in ((a + b, "%d+%d" % (a, b)), (a * b, "%d*%d" % (a, b)),
                         (abs(a - b), "%d-%d" % (max(a, b), min(a, b)))):
            kids.append((tuple(sorted(rest + [val])), "%s=%d" % (txt, val)))
    return kids

def score(state):
    """Value of a finished state: 1.0 means exactly 24."""
    return max(0.0, 1.0 - abs(TARGET - state[0]) / 24.0)
def rollout(state):
    # Simulate: play random moves till one number is left, then score it.
    while len(state) > 1:
        state = random.choice(expand(state))[0]
        CALLS[0] += 1
    return score(state)
def estimate(state, tries=4):
    # Self-evaluation: how promising does this half-done thought look?
    return max(rollout(state) for _ in range(tries))

def tot(width=4, depth=3):
    """Tree of Thoughts: expand, self-evaluate, keep the best `width` branches."""
    frontier = [(START, [])]
    for _ in range(depth):
        pool = [(estimate(k), k, path + [s]) for st, path in frontier for k, s in expand(st)]
        pool.sort(key=lambda t: -t[0])
        frontier = [(k, p) for _, k, p in pool[:width]]
    return max(((score(k), p) for k, p in frontier))

def lats(rounds=60, c=1.0):
    """Toy MCTS: select with UCT, expand, simulate, backpropagate."""
    stats = {}                                   # state -> [visits, total reward]
    best = (0.0, [])
    for n in range(1, rounds + 1):
        state, path = START, []
        while len(state) > 1:
            kids = expand(state)
            def uct(kid):
                v, tot_r = stats.get(kid[0], [0, 0.0])
                if v == 0:
                    return 1e9                   # SELECT: try each child once first
                return tot_r / v + c * math.sqrt(math.log(n) / v)
            state, step = max(kids, key=uct)     # EXPAND
            path.append((state, step))
        reward = score(state)                    # SIMULATE (here the leaf is the answer)
        CALLS[0] += len(path)
        for st, _ in path:                       # BACKPROPAGATE up the branch
            row = stats.setdefault(st, [0, 0.0])
            row[0] += 1
            row[1] += reward
        if reward > best[0]:
            best = (reward, [s for _, s in path])
    return best

s1, p1 = tot(); c1 = CALLS[0]; CALLS[0] = 0
s2, p2 = lats(); c2 = CALLS[0]
print("ToT   best=%.2f  path=%s  model_calls=%d" % (s1, " | ".join(p1), c1))
print("LATS  best=%.2f  path=%s  model_calls=%d" % (s2, " | ".join(p2), c2))
print("One straight answer would have cost 1 call. Search is powerful but expensive.")

Run it with python3 file.py. Look at three things. Both methods score 1.00, meaning they hit exactly 24. Both print the same three-step path, the non-obvious one starting with 6 minus 1. And look at the call counts: hundreds of calls for a puzzle a single answer would attempt in one. That number is the whole trade-off.

Where you will see this

• Coding agents that write several candidate patches, run the tests on each, and keep the one that passes. The tests are the value function.
• Deep-research assistants that fan out into many search queries and drop the threads that look useless.
• Claude Code and Cursor style tools, which mostly run one tool-using loop but branch when a first attempt fails.
• Planning-heavy workflows where a search step sits inside a larger graph as one node.
• Program improvement systems that generate thousands of code variants and let a machine-checkable score decide which survive.

Common mistakes

• Branching without scoring. If every branch gets treated as equally good, you multiply cost and gain nothing. The scorer is the engine, not the tree.
• Trusting the model's own confidence as the score. A model that just failed will still say it did fine. Where you can, score with something real: a test run, a compiler, an exact answer check.
• Using search on easy tasks. For "what is the refund policy", a single answer is correct and instant. Search here means a 100x bill for the same reply.
• Never capping depth or attempts. A tree with no budget explores forever. Always set both limits.
• Forgetting that failures cost money too. Every pruned branch was still generated and still billed. Budget for the whole tree, not just the winning path.

If they ask in an interview

Q: Why does branching help when chain-of-thought fails?

A: Chain-of-thought is one straight walk, so an early mistake corrupts everything after it. Branching keeps several partial answers alive, scores them, and abandons the bad ones. On Game of 24 that takes accuracy from about 4 percent to about 74 percent with the same model.

Q: What are the four phases of MCTS, and what does the exploration constant do?

A: Select, expand, simulate, backpropagate. Select walks down using UCT, which adds the branch's average score to an exploration bonus scaled by a constant c. A small c keeps exploiting the current best branch, a large c pushes the search to try under-visited branches.

Q: When would you refuse to use search in production?

A: When the scorer is noisy and the task has a single right answer, because search then optimises toward whatever the noisy scorer likes and returns a confident wrong answer. Also when latency and cost matter, since a tree can cost hundreds of times a single response.

Try these

• Run the code with the exploration constant set to 0.1 and then to 3.0. See how the path found and the call count change.
• Add a small random jitter to score, simulating a noisy evaluator. Find roughly how much noise it takes before the search stops finding 24.
• Change width in tot from 4 down to 1. At width 1 you have rebuilt plain chain-of-thought. Compare the result.
• Change the starting numbers to a set with no solution, such as 1, 1, 1, 1, and check that the code still finishes instead of hanging.

Words, simply

Quick recap

• One straight chain cannot undo an early mistake, so branch, score, and prune instead.
• ToT is the tree with self-scoring; LATS adds tools, real feedback and written reflections on failure, driven by MCTS.
• Search is worth it only with a cheap, honest scorer and a task where correctness beats cost, because it can cost hundreds of times more.