Classical search plus a three layer world model (symbolic matching, statistical lookup, and LLM fallback) can match LLM based agent planning accuracy at lower cost
Today's AI "agents" usually work the same way: a large language model gets prompted, returns text, and gets prompted again. The result is software that costs real money per action and behaves differently every time it runs.
A new arXiv preprint called GATS argues that this is a design choice the field made, not a law of agent design. The paper, "Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning," swaps the per-step language-model call for classical search over a structured world model. On a self-curated 12-scenario stress test covering coding workflows, web navigation, and long-horizon tasks, GATS reports finishing every scenario, against 88.9% for the prior tree-search method LATS and 23.9% for the older ReAct baseline.
The mechanism is a three-layer world model. The first layer, L1, checks for an exact symbolic match between the agent's current state and a known action. The second layer, L2, pulls statistics from execution logs to estimate how a partly-seen action is likely to behave. The third layer, L3, is the only place a large language model appears: it predicts outcomes for actions nothing in L1 or L2 recognizes. A UCB1 tree search, a classical upper-confidence-bound algorithm, walks this model step by step, picking the branch most likely to lead to a goal.
On synthetic planning tasks with branching paths and dead-ends, GATS reports 100% success against 92% for LATS and 64% for ReAct. Across the same 12-scenario stress test, it reports 100% versus 88.9% and 23.9%. GATS requires zero LLM calls per task during planning, where LATS averages 37.
GATS plans are also deterministic. The same input produces the same plan on every run, which makes the system easier to test and debug than a stochastic LLM agent.
The evaluation is a synthetic planning suite plus a 12-scenario stress test the authors built themselves. The paper is an arXiv preprint, not a peer-reviewed publication. The "zero LLM calls" claim is conditional: GATS's L3 layer still leans on a language model to predict outcomes for actions it has not seen before. The planning loop runs without an LLM in the common case, not in principle. Authors and affiliations are not visible in the abstract excerpt, and broader third-party or production deployment evidence is not part of the source.
GATS demonstrates that for tasks where the world can be described as a graph of states and actions, classical search plus a layered model can plan deterministically and cheaply at the same accuracy as LLM-based methods. Whether the rest of the agent stack can follow the same pattern is the open question. The parts that touch real software, real browsers, and real APIs are next.