Skip to content

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

🕒 Published (v1): 2026-07-09 19:34 UTC · Source: Arxiv · link

Why this paper was selected

Graph-augmented tree search with world models cuts LLM calls vs LATS/ReAct; concrete efficiency vs strong baselines

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

GATS decouples the world model from LLM inference by using a three-layer (symbolic → learned statistics → LLM) architecture paired with UCB1-based tree search over a persistent state-transition graph, achieving 100% planning success on synthetic benchmarks with zero LLM calls during execution versus 37 calls per task for LATS. The core insight is that action effects in structured domains can be precomputed and cached, reducing the LLM's role from a per-step oracle to a one-time bootstrapper for novel transitions.

Problem

Existing LLM agent planners (ReAct, LATS, Tree of Thoughts) invoke LLM inference at every planning step, incurring (1) high per-task compute cost and (2) stochastic, non-reproducible behavior due to sampling variance. No prior approach systematically eliminates inference-time LLM dependence while maintaining or improving planning quality.

Method

GATS comprises two interacting components:

Layered World Model \(W(s,a) \to (s', p)\) queries three layers in priority order: - L1 (Symbolic): STRIPS-style exact precondition/effect matching; returns confidence \(p=1.0\) if \(\text{prec}(a) \subseteq s\), else \(p=0\). - L2 (Learned): Transition statistics from execution logs; confidence \(p_2(a) = \min(n(a)/n_0,\, 1.0)\), saturating after \(n_0=10\) observations. - L3 (Generative): LLM query for novel actions, fixed at \(p=0.5\); results are cached so each \((k(s), a)\) pair is queried at most once.

State-Transition Graph \(G=(V,E)\) stores canonical state keys as nodes and predicted transitions as edges. States reached via different action sequences are merged (transposition table), allowing visit counts, value estimates, and world-model predictions to be shared and reused across the full episode. The graph is persistent across planning steps.

UCB1 Search selects actions via: $\(a_t = \arg\max_{a \in A_\text{app}(s)} \left[ Q(s,a) + c\sqrt{\frac{2 \ln N(s)}{N(s,a)}} \right]\)$ with value backup \(v = p \cdot \text{StateValue}(s') - \lambda(1-p)\), where \(\text{StateValue}(s) = \alpha / (d_G(s,G)+1)\) for reachable goals (set to 0 otherwise), computed via BFS on the current graph.

Key Contributions

  • Three-layer world model architecture separating symbolic, statistical, and generative prediction with principled confidence-gated fallthrough.
  • Persistent state-transition graph that merges equivalent states (transposition table) and amortizes world-model queries and UCB statistics over full episodes.
  • Formal bound on LLM calls: \(N_\text{LLM}^\text{GATS} = |\{(k(s),a) : \text{L1 fails} \wedge \text{L2 fails} \wedge (k(s),a) \notin \text{Cache}\}|\), reducing cost from \(O(BD \cdot c_3)\) to a one-time bootstrapping cost.
  • Deterministic, zero-variance planning (identical plans across all seeds) versus 1–5% variance in LATS/ReAct.
  • Synthetic benchmark with branching paths, dead-ends, and resource constraints that differentiates planning methods (unlike single-step API-Bank benchmarks).

Results

  • Synthetic planning tasks (100 tasks, 3 seeds): GATS b=10 achieves 100% SR vs. LATS b=10 92% and ReAct 64%; GATS requires 0 LLM calls/task vs. LATS 37.
  • Budget ablation: GATS degrades gracefully — b=1: 0%, b=5: 84%, b=10: 100%; 167 nodes expanded at b=10.
  • Stress test (120 tasks, 12 categories, 3 seeds): GATS 100% overall vs. LATS 88.9% vs. ReAct 23.9%; largest GATS gains on coding_task, deep_horizon, web_navigation (+36.7% each over LATS).
  • Optimality: GATS achieves ratio 1.00 (optimal plans) at b≥5; LATS 0.99; ReAct 0.54.
  • World model coverage (synthetic): L1 handles 100% of planning transitions; ~50 one-time L3 bootstrapping calls amortized across all tasks.
  • Statistical significance of GATS vs. LATS: McNemar test \(p < 0.01\).

Limitations

  • Benchmark scope: All evaluations use synthetic tasks with pre-specified action semantics (complete L1 coverage); the efficiency advantage shrinks in open-ended domains where L3 must handle a significant fraction of transitions.
  • BFS scalability: Value estimation via BFS has worst-case complexity \(O(|A|^d)\); impractical beyond \(|A| \approx 20\) with \(d > 10\) without learned value approximators or pruning.
  • L2 initialization: The no-L1 ablation pre-initializes L2 from execution traces on the same task distribution — this may not reflect realistic cold-start conditions.
  • No real-world API benchmark evaluation: ToolBench and similar benchmarks with partial or unknown specifications are listed as future work; current results cannot generalize to those settings.
  • Asymmetric comparison: GATS is given action specifications unavailable to LATS's LLM, which the authors acknowledge but frame as a design-choice rather than a confound.

Relevance to Agentic AI / LLM Agents

GATS directly addresses the inference-cost bottleneck in LLM agent planners by showing that separating the world model from the LLM — using it only as a last-resort bootstrapper — can eliminate per-step LLM calls without sacrificing (and in fact improving) plan quality. This positions GATS in a growing line of work (RAP, LATS, ToT) on structured search for agents, but uniquely argues that systematic search with a learned world model dominates LLM-guided exploration. The persistent transposition-table graph is directly applicable to tool-use agents operating over APIs with known schemas, where action effects can be formalized. For researchers building agents that must plan over long horizons or recover from dead-ends (coding agents, web automation, multi-step tool pipelines), GATS offers a concrete architectural pattern for achieving determinism and cost efficiency.