Monte Carlo Tree Search for LLM Reasoning

Best-of-N throws away everything about a failed attempt. Search keeps the good prefix and tries a different continuation — which is obviously better and roughly an order of magnitude more machinery. Here is what the machinery consists of.

Why search at all

Sampling twenty complete solutions to a problem regenerates the same correct first three steps twenty times. If steps one to three are right and step four is where attempts go wrong, you have paid for sixty redundant steps and explored the interesting part twenty times without ever comparing those explorations against each other.

Search restructures that. Treat a partial solution as a node; treat possible next steps as its children; spend your sampling budget where the tree looks most promising. The core insight from game-playing systems carries over intact — you do not need to explore uniformly, you need to explore where the value estimate is high and the uncertainty is high.

The catch, and it is the whole difficulty, is that a chess position has legal moves and a terminal score. A partial proof has an unbounded space of next sentences and no score at all until it finishes.

The four phases, translated

Two of those four are the hard ones. Expansion needs a definition of “a step” — a line, a sentence, a paragraph, a tool call — and the choice sets your branching factor and your depth. Simulation needs a value function for an unfinished solution, which is exactly what process supervision produces and outcome supervision cannot.

Step granularity is the choice people underestimate. Too fine — a token, a clause — and the branching factor explodes while adjacent nodes become nearly indistinguishable, so the value estimates carry no signal. Too coarse — a whole solution — and you have reinvented best-of-N with extra bookkeeping. A line of working, a sentence, or a single tool call are the granularities that tend to work, and the test is whether a human could plausibly say that one step was better than another. If they could not, neither can your value function.

The selection rule

The rule that balances exploiting a good branch against exploring an under-visited one is the same PUCT form used by the AlphaZero line of work:

score(child) = Q(child) + c_puct * P(child) * sqrt(N(parent)) / (1 + N(child))

  Q(child)  mean value of simulations through this child, in [0, 1]
  P(child)  prior probability of this step — for an LLM, the sequence
            likelihood of the step under the model, normalised across siblings
  N(x)      visit count
  c_puct    exploration constant; ~1-2 is the usual starting range

The prior is the piece that makes this work for language. In a game you would need a separate policy network to say which moves are worth considering; here the generator already gives you a probability for each step it produced, so the model supplies its own prior for free. That is the single most elegant part of the mapping, and it is why the technique transferred as readily as it did.

Note what happens at the extremes. With c_puct at zero this degenerates into greedy decoding over steps. With an infinite budget and a perfect value function it becomes exhaustive search. Everything interesting is in between, and the constant is a genuine hyperparameter that has to be tuned per task.

What it costs in tokens

This is the section that decides whether you build it. Take a branching factor of 5, a depth of 4, and 200 tokens per step generated. A fully expanded tree has 5 + 25 + 125 + 625 = 780 nodes; MCTS does not expand all of them, but a search that visits even 15% of that tree is 117 node expansions, each generating 5 candidates of 200 tokens, plus a value estimate for each.

If the value estimate is a rollout to completion rather than a PRM call, add several hundred tokens per node again. You are now at a six-figure token count for one question, against maybe 6,000 tokens for a single reasoning-model call — a factor of twenty or more, and all of it on the serial path unless you parallelise the expansions, which the selection rule partly prevents by design.

Compare against the alternative honestly: for the same token spend you could take twenty independent samples and rerank them with a verifier. Search wins when the problem has a long solution with a genuine branch point in the middle and a value function that can see the difference. It loses everywhere else, which is most places.

Latency is the other reason it stays in research. Best-of-N is embarrassingly parallel, so N samples cost one sample’s wall-clock time. Tree search is not: the selection rule needs the results of earlier simulations to decide where to go next, so the expansions are substantially serial. A search that costs twenty times the tokens also costs a large multiple of the time, and that is before anyone has seen a first token.

What survives into practice

The full algorithm is rare outside research. What has transferred is its ideas in cheaper form, and these are worth knowing under their own names.

• Tree of Thoughts. Yao et al. (2023) proposed breadth-first or depth-first search over thought steps with the model itself evaluating states — no rollouts, no visit counts. Their headline example is the Game of 24, where they reported chain-of-thought prompting succeeding on 4% of instances and their tree search on 74% with a breadth of five. Far simpler than MCTS and it captures most of the structural benefit on problems that decompose cleanly.
• Beam search over steps. Keep the best b prefixes at each depth, score them with a PRM, discard the rest. No bandit rule and no backpropagation, and it is the version most likely to be worth your engineering time.
• Search as training, not inference. The most consequential use has been generating training data — running expensive search offline to produce trajectories and step labels, then training a model that reaches similar answers in one pass. The search cost is paid once by the lab rather than per request by you, which is a large part of why trained reasoning models exist at all.