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

Jul 16, 2026

Upload by Riley

Large Language Model (LLM) agents can perform multi-step planning, yet common methods such as LATS and ReAct depend on frequent LLM inference, causing high computation and non-reproducible stochastic plans. GATS (Graph-Augmented Tree Search) introduces a planning framework that pairs systematic UCB1-based tree search with a layered world model to remove LLM calls during inference. The layered model uses exact symbolic matching, execution-log statistics, and LLM prediction only for unknown actions, yielding deterministic 100% success on synthetic tasks and strong stress-test performance with zero planning-time LLM calls.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Abstract

Introduction

Related Work

Method

Problem Formulation

arXiv :2607 .08894v 1 [ cs .AI] 9 Jul 2026 GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning Maureese Williams [maureesewilliams@gmail. com](maureesewilliams@gmail. com) Dymitr Nowicki Institute for Cybernetics of NAS of Ukraine [nowicki@nnteam. org. ua](nowicki@nnteam. org. ua) July 13, 2026 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 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) LLMbased prediction for unknown actions. On synthetic planning tasks with branching paths and dead-ends, GATS achieves 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 100% success while LATS drops to 88 .9% and ReAct to 23 .9% . GATS requires 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. 1 Introduction The emergence of Large Language Models (LLMs) as reasoning engines has sparked significant interest in LLM-based agents capable of multi-step planning and tool use [Yao et al., 2022, Shinnet al., 2023, Yao et al., 2023] . These agents must navigate complex decision spaces, often with partial information, dead-ends, and long-horizon dependencies. While LLMs provide powerful semantic understanding, directly using them for planning faces two key challenges: (1) computational cost—each planning step requires expensive LLM inference, and (2) stochasticity—LLM sampling introduces variance that makes plans non-reproducible. Recent work has explored tree search methods for LLM agents. LATS (Language Agent Tree Search) [Zhou et al., 2023] combines Monte Carlo Tree Search with LLM-based action proposal and value estimation. While effective, LATS requires LLM calls at every search node, making it computationally expensive. Tree of Thoughts (ToT) [Yao et al., 2023] similarly relies on LLM evaluation for branch selection. We propose GATS (Graph-Augmented Tree Search), a planning framework that decouples the world model from the LLM, enabling systematic search without inference-time LLM calls. Our key insight is that action effects in many domains can be captured by a layered world model: • L1 (Symbolic) : Exact precondition-effect matching for known actions • L2 (Learned) : Statistical predictions from execution logs • L3 (Generative): LLM-based prediction for novel situations During planning, GATS uses UCB1-based tree search [Kocsis & Szepesvári, 2006] with the world model for state prediction, falling back through layers as needed. The LLM (L3) is only invoked for genuinely unknown actions, which are then cached for future use. Our contributions are: 1. A layered world model architecture that combines symbolic, learned, and generative components for efficient state prediction. 2. A systematic UCB1-based search algorithm that outperforms random LLM-guided exploration. 3. Comprehensive evaluation on 100 synthetic planning tasks and a 12-category stress test (120 tasks), showing GATS achieves 100% success rate with zero LLM calls, compared to 92% for LATS (main) and 88.9%(stress test) with ∼37 LLM calls per task. 4. Ablation studies demonstrating budget scaling and

FAQs

What problem does GATS address in LLM agent planning?

GATS targets two limitations of prior approaches: high computational cost from calling the LLM at many planning steps and stochasticity that makes plans hard to reproduce.

How does the layered world model in GATS work?

GATS uses three layers for state prediction: L1 performs exact symbolic precondition–effect matching for known actions, L2 uses statistics learned from execution logs, and L3 calls an LLM only to predict effects for unknown actions.

What results show GATS is more efficient and reliable than LATS and ReAct?

On synthetic planning tasks, GATS reaches 100% success versus 92% for LATS and 64% for ReAct, while requiring zero LLM calls per task during planning. A broader stress test keeps 100% success for GATS while LATS and ReAct drop substantially, with deterministic plans and zero variance across runs.

Jul 16, 2026

Upload by Riley