GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning
06:00 · July 13, 2026 · arXiv cs.AI RSS
Large Language Model (LLM) agents have shown promise in multi-step planning tasks, but existing approaches like LATS (Language Agent Tree Search) and ReAct rely heavily on LLM inference during planning, leading to high computational costs and stochastic behavior. We present \textbf{GATS} (Graph-Augmented Tree Search), a planning framework that combines systematic UCB1-based tree search with a layered world model to eliminate LLM calls during inference while achieving superior planning performance. Our three-layer world model integrates: (L1) exact symbolic action matching, (L2) statistics learned from execution logs, and (L3) LLM-based prediction for unknown actions. On synthetic planning tasks with branching paths and dead-ends, GATS achieves \textbf{100\% success rate} compared to 92 % for LATS and 64\% for ReAct. On a comprehensive stress test spanning 12 challenging scenarios -- including coding workflows, web navigation, and long-horizon tasks -- GATS maintains \textbf{100\% success} while LATS drops to 88.9 % and ReAct to 23.9%. GATS requires \textbf{zero LLM calls per task} during planning (vs. 37 per task for LATS) and produces deterministic plans with zero variance across runs. Our results demonstrate that systematic search with learned world models can substantially outperform LLM-guided exploration for agent planning.
Summary
GATS addresses the high inference costs and nondeterministic behavior of LLM-driven agents in multi-step planning by separating the world model from the language model itself. Existing methods such as ReAct and LATS invoke an LLM at every decision or search node to propose actions, estimate values, or predict state transitions, which produces both substantial computational overhead and run-to-run variance. GATS instead maintains a three-layer world model that answers transition queries without repeated LLM calls: an L1 symbolic layer performs exact STRIPS-style precondition-effect matching for known actions, an L2 learned layer supplies statistical predictions drawn from execution logs, and an L3 generative layer consults the LLM only for genuinely novel actions whose results are then cached.
Planning proceeds via UCB1-guided tree search over a persistent state-transition graph. Because identical states reached by different paths are merged, visit counts, value estimates, and transition predictions are reused across branches. The graph is retained between planning steps, allowing statistics to accumulate over an entire task rather than being discarded after each expansion. As a result, GATS performs zero LLM calls per task during inference once the cache is populated, while still guaranteeing deterministic output.
On a suite of 100 synthetic planning problems that include branching paths and dead-ends, GATS records a 100 percent success rate. The same figure holds across a 12-category stress test covering coding workflows, web navigation, and long-horizon tasks. By comparison, LATS reaches 92 percent on the synthetic set and 88.9 percent on the stress test, while ReAct achieves 64 percent and 23.9 percent respectively. These gains are obtained with full reproducibility and without variance across repeated runs. The framework is released with open code, targeting domains where reliable multi-step tool use is required.
Why it matters
Provides actionable, reproducible planning methods that reduce compute cost and variance, directly applicable to Dutch SME and research teams building reliable LLM agents. Aligns with NL/EU emphasis on transparent and efficient AI systems.
