Monte Carlo Tree Search in Large Language Models: How Selection, Expansion, Simulation, and Backpropagation Guide Deliberate Reasoning

Standard autoregressive language models generate text token by token via left-to-right greedy decoding or stochastic sampling. While this System 1 approach suffices for fluency and single-turn synthesis, it struggles with complex mathematical reasoning, multi-step logical deduction, and long-horizon planning. Because autoregressive decoders lack native backtracking mechanisms, an error introduced at step t persists and compounds across all subsequent steps t+1 through T.

To overcome this structural limitation, researchers have integrated classical search algorithms into the inference phase of large language models. Among these methods, Monte Carlo Tree Search (MCTS) has emerged as a principled framework for test-time compute scaling. By coupling language model policies with step-level value estimation, MCTS balances exploration against exploitation, isolates erroneous reasoning branches, and navigates combinatorial search spaces without requiring parameter updates.

The four iterative phases of Monte Carlo Tree Search for LLM reasoning

Formulating Language Generation as a Search Problem

In traditional game playing such as Go or chess, MCTS operates over a discrete board state s in S and a bounded action space a in A. Applying MCTS to natural language processing requires formalizing sequence generation as a Markov Decision Process (MDP):

State Space (S): A state s_t = (x, a_1, a_2, ..., a_t) represents the initial prompt x concatenated with the sequence of intermediate reasoning thoughts or actions generated up to step t.
Action Space (A): An action a_{t+1} represents a discrete reasoning chunk, such as a single sentence, mathematical transformation, sub-question decomposition, or Python execution block.
Transition Function (T): Because natural language concatenation is deterministic, the state transition is defined as s_{t+1} = T(s_t, a_{t+1}) = s_t + a_{t+1}.
Reward Function (R): A reward signal evaluates the validity of the trajectory. Terminal rewards R(s_terminal) in [0, 1] measure final answer accuracy, while intermediate rewards r(s_t, a_{t+1}) measure the step-by-step correctness provided by a Process Reward Model (PRM) or self-evaluation prompt.

Unlike token-level decoding where the branching factor equals the vocabulary size |V| (roughly 32,000 to 128,000 tokens), language MCTS groups tokens into semantic steps. This reduces tree depth and bounds the effective branching factor to K candidate actions per node.

The Four Stages of LLM Tree Search

Each MCTS iteration consists of four sequential stages: Selection, Expansion, Simulation (Evaluation), and Backpropagation.

       [Root State s0]
             /   \
            /     \  (Selection: PUCT / UCB1)
      [Node s1]  [Node s2]
         /
    [Selected Leaf]
         |
    [Expansion] (Sample K reasoning actions from LLM)
         |
    [Simulation / PRM Evaluation] (Rollout or value head score)
         |
    [Backpropagation] (Propagate Q-values and visit counts upward)

1. Selection

Starting from the root node s_0, the search algorithm traverses existing nodes in the tree until it reaches a leaf node that has not yet been fully expanded. At each node s, child selection is governed by a tree policy designed to balance exploitation of high-value paths with exploration of less-visited branches.

Modern LLM implementations commonly adapt the Predictor Upper Confidence Bound for Trees (PUCT) formula:

a* = argmax_{a in A(s)} [ Q(s, a) + c_puct * P(a|s) * (sqrt(N(s)) / (1 + N(s, a))) ]

In this formulation:

Q(s, a): The running estimated action value, calculated as the mean reward of all simulated trajectories passing through branch (s, a).
P(a|s): The prior probability of action a assigned by the base policy model.
N(s): The total visit count of the parent state s, equal to the sum of visits across all child actions.
N(s, a): The number of times action a has been selected from state s.
c_puct: An exploration constant governing the balance between exploitation of high Q-values and exploration of high-prior, low-visit branches.

When N(s, a) = 0, the exploration term dominates, ensuring that promising actions under prior P(a|s) are evaluated before over-allocating compute to known branches.

2. Expansion

Once the selection phase identifies a leaf state s_L, the policy model generates K candidate actions {a_1, a_2, ..., a_K} conditioned on the context s_L.

To maximize diversity across candidate branches, generation uses stochastic sampling (temperature between 0.6 and 1.0) or structured prompt variations that encourage alternative proof strategies, algebraic manipulation, or sub-problem decomposition.

3. Simulation and Value Estimation

To assess the quality of a newly expanded state s' = s_L + a_k, the algorithm requires a value estimate V(s'). Two primary paradigms exist for state evaluation:

Monte Carlo Rollouts: The policy model samples a fast, greedy, or stochastic completion from s' until a terminal answer state is reached. The final answer is evaluated against deterministic constraints, programmatic unit tests, or an Outcome Reward Model (ORM) to yield a binary reward R in {0, 1}.
Process Reward Models (PRMs) and Value Networks: Rather than running costly multi-step rollouts to termination, a learned PRM or value head directly assigns an expected success probability V(s') in [0, 1] to the intermediate state. This eliminates the high variance and latency associated with full rollouts.

4. Backpropagation

The estimated value V obtained during simulation or PRM evaluation is propagated backward along the trajectory path from s' back to the root s_0. For every visited state-action pair (s, a) along the path, visit counts and action values are updated:

N(s, a) <- N(s, a) + 1
Q(s, a) <- Q(s, a) + (V - Q(s, a)) / N(s, a)

This incremental running average guarantees that Q(s, a) converges to the expected return of the sub-tree rooted at (s, a) as the number of search iterations increases.

Key Architectures and Implementations

Several frameworks have adapted MCTS to different reasoning domains:

Reasoning via Planning (RAP)

Introduced by Hao et al. (2023), RAP repurposes a single LLM to serve three distinct roles simultaneously:

Agent Policy: Generating candidate action steps.
World Model: Predicting intermediate environment states and state transitions.
Reward Model: Providing self-evaluation scores for action confidence and task completion.

By maintaining explicit world states alongside reasoning traces, RAP demonstrates that structured tree planning substantially outperforms standard chain-of-thought prompting on block-world manipulation and multi-hop logical deductions.

rStar and rStar-Math

Qi et al. (2024) developed rStar (Self-play muTuAl Reasoning), which decouples reasoning into mutual generation and discrimination phases. During generation, target models sample actions from human-like reasoning primitives:

Proposing the next intermediate step.
Proposing sub-questions.
Proposing candidate answers directly.
Writing and executing Python code.
Verifying previous calculations.

Guan et al. (2025) expanded this into rStar-Math, demonstrating that small language models (such as 7B parameter base models) executing deep MCTS search guided by an evolved step-level PRM can match or surpass larger frontier reasoning models on competition mathematics benchmarks like MATH-500 and AIME.

MCT Self-Refine (MCTSr)

Zhang et al. (2024) introduced MCTSr, combining MCTS with iterative self-refinement. Instead of branching purely on new deduction steps, MCTSr nodes represent complete answer drafts, and actions represent targeted critical revisions. An evaluator prompt scores draft quality across mathematical accuracy, completeness, and clarity, using modified Upper Confidence Bound equations to focus compute on refining the most promising candidate solutions.

AlphaMath Almost Zero

Chen et al. (2024) implemented AlphaMath, showing that process supervision for math reasoning can be bootstrapped without manual step annotations. By using MCTS rollouts to automatically assign step-level value targets based on terminal correctness, AlphaMath trains policy and value networks through iterative reinforcement cycles analogous to AlphaGo Zero.

Search Space Granularity Trade-Offs

The choice of action granularity determines both search efficiency and compute overhead:

Token-Level Granularity: Branching factor equals vocabulary size (|V| ~ 10^5), with search depth reaching hundreds or thousands of steps. Sparse credit assignment makes value estimation highly unreliable, rendering token-level MCTS computationally intractable.
Step-Level (Chain-of-Thought): Branching factor is bounded to K = 3 to 8 candidates per step, with search depth between 5 and 20 steps. Process Reward Models can score intermediate steps accurately, providing a balanced trade-off between search breadth and compute cost.
Sub-Goal and Plan Level: Branching factor is small (K = 2 to 4), with shallow search depth (2 to 5 steps). Verification criteria are explicit, offering high reliability for long-horizon agent planning.
Full Trajectory (Best-of-N): Flat sampling with no internal branching. Evaluation is coarse and outcome-based, scaling linearly with sample count but failing to isolate intermediate errors.

Comparing Test-Time Search Topologies

Greedy Decoding: Follows a single linear trajectory by selecting the highest-probability token at each step. No backtracking or alternative path exploration is possible.
Best-of-N Sampling: Generates N complete, independent solutions in parallel and selects the best outcome via majority voting or reward scoring. It cannot repair a flawed step without regenerating the entire sequence.
Beam Search: Maintains a fixed buffer of the top-B highest-scoring sequences at each expansion layer. Once a promising candidate falls outside the top-B beam width, it is permanently pruned.
Tree of Thoughts (ToT): Explores tree structures using standard Breadth-First Search (BFS) or Depth-First Search (DFS) guided by heuristic evaluation prompts. It lacks formal exploration-exploitation bounds.
Monte Carlo Tree Search (MCTS): Constructs asymmetric search trees using PUCT or UCB1 selection. High-value branches receive exponential compute allocation while unpromising paths are abandoned naturally without hard pruning thresholds.

Serving Bottlenecks and Engineering Challenges

Deploying MCTS in production inference systems introduces distinct infrastructure bottlenecks:

KV Cache Thrashing: Standard autoregressive serving relies on linear prefix caching. In MCTS, the engine repeatedly switches between disparate branches of the search tree. Efficient serving frameworks must utilize tree-structured or radix-based KV caches (such as RadixAttention in SGLang or PageManager trees in vLLM) to reuse shared prefix context across parent nodes without redundant prefill computation.
Value Model Inaccuracy (Reward Hacking): If the Process Reward Model exhibits systematic bias or false positives, MCTS will exploit these scoring flaws, over-allocating search compute to logically invalid reasoning trajectories.
Inference Latency: Executing 50 to 200 MCTS iterations on a complex reasoning prompt can require dozens of seconds per query. System architectures balance this compute tax by reserving MCTS for high-value tasks (such as code generation, mathematical theorem proving, and critical planning) while routing simpler queries to standard autoregressive decoders.