LATS: Monte Carlo Tree Search for LLM Agent Decisions

Tree-of-thought explores alternative reasoning paths but makes each decision based on a single LLM call's evaluation. Reflexion retries a whole trajectory after failure, but the retries are full restarts rather than local corrections. Both patterns leave performance on the table: tree-of-thought cannot revise its value estimates as exploration reveals new information, and Reflexion cannot backtrack within a single attempt.

LATS (Language Agent Tree Search), introduced by Zhou and colleagues in 2023, addresses both gaps by importing Monte Carlo Tree Search from game-playing AI (Zhou et al., 2023). MCTS is the algorithm behind AlphaGo and its descendants; it balances exploration and exploitation using the Upper Confidence Bound for Trees (UCT) formula and updates value estimates as more of the tree is explored. LATS applies the same machinery to agent decisions: the tree is a tree of candidate actions, the nodes are states, and the value function is an LLM evaluator. The paper reports 94.4 percent pass-at-1 on HumanEval with GPT-4, exceeding Reflexion's 91 percent on the same benchmark. The cost is real: LATS uses roughly five to ten times more LLM calls than a baseline ReAct agent, and the pattern is best suited to high-stakes tasks where correctness matters more than cost.

Five steps adapted from MCTS

MCTS runs a loop of five steps; LATS applies the same loop with LLMs filling each role.

Selection. Starting from the root, descend to a leaf by picking the child with the highest UCT score at each level. UCT balances exploitation (pick the child with the highest average value) with exploration (pick a child that has been tried fewer times). The result is that well-performing branches get deeper investigation without abandoning unexplored alternatives entirely.

Expansion. At the selected leaf, use an LLM to generate n candidate next actions. Each candidate becomes a new child node in the tree.

Evaluation. An LLM value function scores each new node. The score estimates how likely a trajectory rooted at that node is to succeed. For coding tasks, the value can be augmented with concrete signals like whether test cases pass.

Simulation (optional). From a candidate node, roll out to completion by continuing to act greedily. The terminal reward gives a stronger signal than the static evaluation alone. Simulation is expensive in LLM calls; many LATS implementations skip it or run it only on promising nodes.

Backpropagation. The reward or value from the simulation (or from the static evaluator if simulation was skipped) propagates up the tree, updating the average value and visit count at every ancestor. The next selection step reads these updated statistics.

The loop repeats until a success criterion is met or a budget is exhausted. The final answer is the best terminal state discovered.

The tree

flowchart TD
    R[Root state] --> C1[Child 1: n_visits=3, value=0.6]
    R --> C2[Child 2: n_visits=1, value=0.8]
    R --> C3[Child 3: n_visits=5, value=0.4]
    C2 --> GC1[Grandchild]
    GC1 --> SIM{Simulate to terminal}
    SIM -.reward.-> GC1
    GC1 -.backprop.-> C2
    C2 -.backprop.-> R

The diagram captures the loop in motion: a lightly visited but high-value child is selected, expanded, evaluated by simulation, and the reward propagates back. Child 2 accumulates visits; if its value holds, it will continue to be selected.

A sketch in code

A full LATS implementation is substantial. The excerpt below is a compact sketch that captures the selection-expansion-evaluation-backpropagation loop without simulation. The focus is on the structure; production implementations add numerous optimizations.

from math import sqrt, log
from openai import OpenAI
from pydantic import BaseModel, Field
from dataclasses import dataclass, field
from typing import Optional

client = OpenAI()

@dataclass
class Node:
    state: str
    parent: Optional["Node"] = None
    children: list["Node"] = field(default_factory=list)
    value: float = 0.0
    visits: int = 0

class Value(BaseModel):
    score: float = Field(ge=0.0, le=1.0)

class Actions(BaseModel):
    next_states: list[str]

def uct(node: Node, c: float = 1.4) -> float:
    if node.visits == 0 or node.parent is None: return float("inf")
    return (node.value / node.visits +
            c * sqrt(log(node.parent.visits) / node.visits))

def select(root: Node) -> Node:
    node = root
    while node.children:
        node = max(node.children, key=uct)
    return node

def expand(node: Node) -> None:
    r = client.responses.parse(
        model="gpt-4o-mini",
        instructions="Propose 3 next states.",
        input=node.state, text_format=Actions,
    )
    for s in r.output[0].content[0].parsed.next_states:
        node.children.append(Node(state=node.state + "\n- " + s, parent=node))

def evaluate(node: Node) -> float:
    r = client.responses.parse(
        model="gpt-4o-mini",
        instructions="Score how promising this state is toward the goal.",
        input=node.state, text_format=Value,
    )
    return r.output[0].content[0].parsed.score

def backprop(node: Node, value: float) -> None:
    while node is not None:
        node.visits += 1
        node.value += value
        node = node.parent

def lats(root_state: str, iterations: int = 20) -> str:
    root = Node(state=root_state)
    for _ in range(iterations):
        leaf = select(root)
        expand(leaf)
        for child in leaf.children:
            v = evaluate(child)
            backprop(child, v)
    best = max((c for c in root.children), key=lambda c: c.value / max(c.visits, 1))
    return best.state

The LangGraph equivalent wires the same loop into a graph with a state that holds the tree, the visit counts, and a reference to the best node seen so far. Implementation is longer than will fit here; the runnable version lives at github.com/subodhjena/agentic-patterns under examples/15_lats.py and examples/15_lats_langgraph.py.

Key difference from Reflexion

Reflexion retries a whole task on failure; LATS explores branches within a single attempt. The difference matters because the unit of correction is different. Reflexion's unit is a trajectory; LATS's unit is a node in the tree. A Reflexion retry discards everything learned in the failed attempt except the textual critique; a LATS backtrack keeps every value estimate the search accumulated.

Neither is strictly better. Reflexion is cheaper and simpler; LATS is more sample-efficient on problems where the value function is informative enough to guide the search. Applications with cheap evaluation (code with tests) favor LATS; applications with expensive evaluation (open-ended writing with no ground truth) favor Reflexion or simpler patterns.

Where LATS earns its premium

The pattern is the most expensive in this series. It earns its cost on a specific problem class.

High-stakes correctness. Code generation for production, formal proof search, medical diagnosis assistance, and other tasks where a wrong answer is expensive justify the premium. Benchmarks the paper cites all share this property.

Cheap value signals. If the evaluator can score a partial state in one LLM call (or better, with a deterministic check), the search is efficient. If each evaluation itself requires a long chain of reasoning, LATS loses its advantage.

Branching decisions with exploration-exploitation tension. When the best-looking action might still be wrong and under-explored alternatives might pay off, UCT's balance is load-bearing. Problems with a single obvious path do not benefit.

Budget permits 5-10x more LLM calls. This is the honest constraint. Teams that need answers in real time or on thin margins rarely use LATS in production; it is more common in batch evaluation or in research settings.

Where the pattern goes wrong

LATS has more knobs than any pattern in this series. The failures map cleanly onto the knobs.

Uninformative value function. If the evaluator's scores do not correlate with eventual success, the tree explores randomly. Measure the evaluator on labeled partial states before trusting it to guide the search.

UCT parameter miscalibration. The exploration constant c (typically around 1.4) controls how aggressively the search tries under-visited branches. Too low and promising branches get over-exploited; too high and the search wanders. Calibrate on a held-out set.

Insufficient iterations. MCTS is a loop that improves with compute. Cutting it off early produces estimates with high variance. LATS papers typically report results at 10, 20, and 50 iterations.

Over-branching. A branching factor that is too high at expansion produces a shallow tree that never reaches a satisfying depth. Keep the factor small (three to five) and rely on multiple iterations to explore.

Simulation cost. Rolling out to terminal states is expensive. Skip simulation when a static evaluator suffices, or run simulation only on high-value nodes.

State representation. LATS requires a notion of "state" that the evaluator can score. When states are free-text, two different textual representations of the same semantic state confuse the search. Canonicalize states when possible.

Trade against the rest of the Reasoning stage

LATS sits at the top of the reasoning stage in both capability and cost. The table names where each pattern wins.

Axis	CoT	ToT	Reflexion	LATS
Structure	Single chain	Tree search	Outer-loop retry	Tree search with MCTS
Value updates	None	Static evaluator	Text critique	Backpropagated value estimates
Backtracking	None	Within tree	Across attempts	Within tree, budgeted
LLM calls vs ReAct baseline	1x	2-5x	2-4x per task	5-10x
Best-fit tasks	Multi-step reasoning	Search with winners	Retry scenarios	High-stakes correctness

Neighbors in the series

Tree-of-thought, earlier in this stage, is the non-MCTS tree search LATS generalizes. Reflexion, the previous article, is the outer-loop cousin that LATS subsumes in many high-stakes applications. ReAct, in the Agents stage, is the baseline against which LATS is typically compared. The harness design article, in the Production stage, covers the planner-generator-evaluator architecture that makes LATS-style search practical at scale. Agent evaluation, also in Production, covers the evaluators that LATS depends on for its value function.

References

1. Zhou, Andy, et al. Language Agent Tree Search: Unifying Reasoning, Acting, and Planning in Language Models. ICML 2024.
2. Silver, David, et al. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature 2016.
3. Yao, Shunyu, et al. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS 2023.
4. Shinn, Noah, et al. Reflexion: Language Agents with Verbal Reinforcement Learning. NeurIPS 2023.
5. LangChain. LATS implementations in LangGraph. 2024.