GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning
2026-07-09 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors introduce GATS, a new method for planning that avoids using large language models (LLMs) repeatedly during its decision process, unlike previous methods like LATS and ReAct. GATS combines a structured search technique with a three-layer world model to predict actions without calling an LLM each time. In tests with complex planning tasks, GATS succeeded every time while using no LLM calls during the planning phase, making it faster and more consistent. The authors show that this approach works better than relying heavily on LLMs for each planning step.
Large Language Models (LLMs)Tree SearchUCB1 AlgorithmWorld ModelSymbolic Action MatchingPlanning TasksDeterministic PlanningExecution LogsMulti-step PlanningLLM Inference
Authors
Maureese Williams, Dymitr Nowicki
Abstract
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.