🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

The paper introduces GATS, a planning framework that replaces costly LLM inference with a layered world model and UCB1-based tree search to achieve 100% success rates and deterministic, zero-call planning across diverse complex tasks, significantly outperforming existing methods like LATS and ReAct.

Original authors: Maureese Williams, Dymitr Nowicki

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maureese Williams, Dymitr Nowicki

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, tricky maze. You have a super-smart friend (a Large Language Model, or LLM) who can talk to you and suggest which way to turn. But here's the catch: every time you ask your friend for advice, they have to take a long nap to think, and sometimes they guess differently each time you ask the same question. If the maze has dead ends or requires a long sequence of turns, asking your friend for help at every single step gets expensive and confusing.

This is the problem researchers Maureese Williams and Dymitr Nowicki tackled with their new system, GATS (Graph-Augmented Tree Search). They found a way to navigate the maze so efficiently that they barely need to wake up their super-smart friend at all.

The Old Way: The "Ask-Every-Step" Approach

Previous methods, like ReAct and LATS, were a bit like a hiker who stops at every single fork in the road to ask a guide, "Which way should I go?"

ReAct just asks once and goes. It's fast, but it often walks into dead ends. In their tests, this method only succeeded in 64% of the tricky maze scenarios.
LATS is smarter; it asks the guide, then asks again about the next step, and again, building a tree of possibilities. But because it asks the guide (the LLM) for every single branch of that tree, it gets tired and expensive. In the tests, LATS succeeded 92% of the time, but it had to ask the guide about 37 times per task. Plus, because the guide guesses randomly sometimes, you might get a different path if you try the same maze twice.

The New Way: GATS (The "Map-Maker" Strategy)

GATS changes the game. Instead of asking the guide for every turn, GATS builds its own internal map using a Layered World Model. Think of this map as having three layers of knowledge:

Layer 1 (The Exact Rulebook): For actions the system already knows perfectly (like "if I press this button, the door opens"), it uses a simple, instant check. No thinking required. It's like knowing that 2+2 always equals 4.
Layer 2 (The Experience Log): If the system has seen an action happen before but doesn't have a perfect rule for it, it checks its diary of past trips. "Last time I did this, it worked 9 out of 10 times." This is learned from data, not guessed.
Layer 3 (The Super-Genius Friend): Only when the system encounters something totally new and unknown does it wake up the LLM guide. But here's the magic: once the guide answers, GATS writes the answer down in the map. Next time that same situation comes up, GATS just looks at the map. It never asks the guide again for that specific thing.

The Results: Speed, Certainty, and Success

The researchers tested this on 100 synthetic planning tasks that were designed to be tricky, with branching paths and dead ends.

GATS got a perfect 100% success rate.
LATS got 92%.
ReAct got 64%.

But the real kicker? GATS made zero calls to the LLM during the actual planning of these tasks. It did all the thinking using its own map and rules. Because it didn't rely on the LLM's random guessing, GATS produced the exact same perfect plan every single time it ran. There was zero variance.

They also ran a massive "stress test" with 120 tasks across 12 difficult categories, like coding workflows, booking flights, and navigating complex mazes.

GATS still hit 100% success.
LATS dropped to 88.9%.
ReAct crashed down to 23.9%.

Why It Works (The Secret Sauce)

The paper suggests that GATS wins because it uses a systematic search (called UCB1) instead of random guessing. Imagine a detective who checks every single clue methodically rather than just following a hunch.

Systematic vs. Random: LATS relies on the LLM to guess which path looks good. If the LLM's "hunch" is wrong, the whole plan fails. GATS checks all options systematically, ensuring it doesn't miss the right path just because the guide had a bad day.
Deterministic vs. Stochastic: Because GATS uses its own map for most steps, the result is always the same. LATS, relying on the LLM, can give you a different answer if you run the same task twice.

What This Means (And What It Doesn't)

The authors are very clear about the limits of their success. These results are based on simulations and synthetic tasks where the rules of the game (the "action specifications") were known ahead of time. In these controlled environments, GATS is a champion.

However, the paper explicitly rules out the idea that GATS is a magic bullet for everything right now. If you throw GATS into a completely wild, open-ended world where it has no rules and no past logs to learn from, it would have to rely more heavily on the LLM (Layer 3), which would make it slower and less efficient. The authors suggest that for GATS to shine in the real world, we need to build better maps (world models) first, perhaps by learning from logs of how humans actually use tools.

In short, the paper shows that for planning tasks where we can define the rules, we don't need to ask a super-smart AI for help at every single step. We can build a smart, self-updating map that lets us navigate complex problems with 100% success, zero cost, and zero confusion.

Technical Summary: GATS (Graph-Augmented Tree Search with Layered World Models)

Problem Statement

Large Language Model (LLM) agents have demonstrated potential in multi-step planning and tool use, yet current approaches like ReAct and LATS (Language Agent Tree Search) face two critical limitations:

Computational Cost: Existing methods rely on expensive LLM inference at every planning step or search node, leading to high latency and resource consumption.
Stochasticity: LLM sampling introduces variance, resulting in non-reproducible plans and inconsistent performance across runs.

The core challenge is to develop a planning framework that maintains the reasoning capabilities of LLMs while eliminating inference-time LLM calls for state prediction, thereby achieving deterministic, efficient, and scalable agent planning.

Methodology: GATS Framework

The authors propose GATS (Graph-Augmented Tree Search), a planning architecture that decouples the world model from the LLM. GATS combines systematic UCB1-based tree search with a Layered World Model and a persistent State-Transition Graph.

1. Layered World Model ( $W$ )

The world model predicts the next state ( $s'$ ) and confidence ( $p$ ) given a current state ( $s$ ) and action ( $a$ ). It queries three layers in order of increasing generality and computational cost:

L1 (Symbolic): Exact precondition-effect matching for actions with known STRIPS-style specifications. This layer provides deterministic predictions ( $p=1.0$ ) with minimal computational cost (symbolic lookup).
L2 (Learned Statistics): Statistical predictions derived from execution logs. For actions observed during execution but lacking formal specifications, it returns the most frequent effect with confidence $p = \min(\text{count}(a)/10, 1.0)$ .
L3 (Generative/LLM): LLM-based prediction for genuinely novel or ambiguous actions. Crucially, predictions from L3 are cached to avoid repeated inference calls for the same transition.

The system prioritizes L1 and L2 to maximize coverage, invoking L3 only when necessary. This "amortizes" the LLM cost, transforming it from a per-step inference requirement into a one-time bootstrapping cost.

2. Persistent State-Transition Graph

Unlike traditional tree search which expands nodes independently, GATS maintains an explicit graph $G = (V, E)$ where nodes represent canonical state keys $k(s)$ .

State Merging: If different action sequences reach the same state, they merge into a single node. This allows the reuse of transition predictions, visit counts, and value estimates across paths.
Persistence: The graph persists across planning steps. After an action is executed, planning resumes from the corresponding graph node rather than restarting the search, amortizing value estimation and search statistics over the entire episode.
Dead-End Detection: Nodes with no path to a goal are marked as dead ends, allowing the planner to assign low values to actions leading into these regions.

3. UCB1-Based Search

GATS employs a UCB1 (Upper Confidence Bound) selection strategy over the graph edges.

Action Selection: At each state, the algorithm selects the action $a$ that maximizes $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ . This ensures systematic exploration of all applicable actions before committing to high-value paths.
Value Estimation: The value of a state is derived from the shortest predicted distance to the goal ( $d_G$ ) using a BFS-based heuristic: $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ .
Confidence Integration: The backup value incorporates the world model's confidence: $v = p \cdot StateValue(s') - \lambda(1-p)$ , penalizing uncertain predictions.

Key Contributions

Layered World Model Architecture: A novel integration of symbolic, learned, and generative components that enables efficient state prediction while minimizing LLM reliance.
Systematic UCB1 Search with Graph Memory: A planning algorithm that outperforms random LLM-guided exploration by leveraging a persistent graph to reuse search evidence and ensure deterministic outcomes.
Comprehensive Evaluation: Extensive testing on 100 synthetic planning tasks and a 12-category stress test (120 tasks) covering coding, web navigation, and long-horizon scenarios.
Zero LLM Calls During Planning: Demonstrated that GATS can achieve 100% success rates with zero LLM calls during the planning phase, contrasting sharply with baselines requiring dozens of calls per task.

Experimental Results

Synthetic Planning Tasks (100 Tasks)

Success Rate: GATS achieved 100% success (with budget $b=10$ ), outperforming LATS (92%) and ReAct (64%).
Efficiency: GATS required 0 LLM calls per task during planning, whereas LATS required ~37 calls.
Determinism: GATS produced plans with 0% variance across random seeds, while LATS and ReAct exhibited 1–5% variance due to LLM stochasticity.
Optimality: GATS achieved an optimality ratio of 1.00, matching the Oracle.

Stress Test (12 Categories, 120 Tasks)

The stress test included challenging scenarios such as coding workflows, web navigation, deep horizon tasks, and irreversible decision-making (dead-ends).

Overall Performance: GATS maintained 100% success across all categories.
Comparative Performance: LATS dropped to 88.9% overall, with significant struggles in coding (63.3%), web navigation (63.3%), and deep horizon (63.3%) tasks. ReAct failed catastrophically at 23.9%.
Specific Gains: GATS showed the largest improvements (+36.7%) in coding, web navigation, and deep horizon tasks compared to LATS.

Ablation Studies

Search Budget: Performance saturated at a budget of $b=10$ ; increasing further provided diminishing returns.
World Model Layers: Removing L1 or L3 individually did not impact success rates on synthetic tasks where L2 provided sufficient coverage, validating the system's graceful degradation. In open-domain projections, L3 (LLM) is expected to handle ~10% of novel actions.

Significance and Claims

The paper argues that systematic search with learned world models can substantially outperform LLM-guided exploration for agent planning. The primary significance of GATS lies in its ability to:

Eliminate Inference-Time LLM Costs: By caching predictions and relying on symbolic/learned layers, GATS removes the computational bottleneck of repeated LLM calls.
Ensure Reproducibility: The deterministic nature of the layered world model and UCB1 search eliminates the stochastic variance inherent in LLM sampling.
Handle Complex Planning: The framework successfully navigates branching paths, dead-ends, and long-horizon dependencies where purely LLM-based methods (ReAct) and LLM-heavy tree search (LATS) fail or underperform.

The authors position GATS as an optimized solution for domains where action semantics can be formalized (e.g., APIs, structured tool use), offering a path toward more efficient and reliable autonomous agents. They acknowledge that in open-ended domains with unknown action effects, reliance on the L3 layer would increase, reducing but not eliminating the efficiency advantage over LATS.