2026-07-13 04:00 UTCOriginal source2 min readUpdated: 2026-07-13 08:05 UTC

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

GATS is a new agent planning framework that uses systematic UCB1-based tree search and a layered world model to eliminate LLM calls during planning, achieving 100% success rate. It outperforms LATS and ReAct on synthetic tasks and 12 challenging scenarios with lower computational cost.

SourcearXiv AIAuthor: Maureese Williams, Dymitr Nowicki

-->

[Submitted on 9 Jul 2026]

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

View a PDF of the paper titled GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning, by Maureese Williams and Dymitr Nowicki

View PDF HTML (experimental)

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.

Subjects:

Artificial Intelligence (cs.AI); Machine Learning (cs.LG)

Cite as: arXiv:2607.08894 [cs.AI]

(or arXiv:2607.08894v1 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2607.08894

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Dimitri Nowicki [view email] [v1] Thu, 9 Jul 2026 19:34:29 UTC (17 KB)

Full-text links:

Access Paper:

View a PDF of the paper titled GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning, by Maureese Williams and Dymitr Nowicki

View PDF

HTML (experimental)

TeX Source

view license

Current browse context:

cs.AI

new | recent | 2026-07

Change to browse by:

cs cs.LG

References & Citations

NASA ADS

Google Scholar

Semantic Scholar

Data provided by:

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)