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

GATS：用于高效智能体规划的图增强树搜索与分层世界模型

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.

摘要： 大语言模型（LLM）智能体在多步规划任务中展现出了巨大潜力，但现有的方法（如 LATS 和 ReAct）在规划过程中过度依赖 LLM 推理，导致了高昂的计算成本和随机性行为。

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.

我们提出了 GATS（图增强树搜索），这是一种结合了基于 UCB1 的系统化树搜索与分层世界模型的规划框架，旨在消除推理过程中的 LLM 调用，同时实现卓越的规划性能。

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.

我们的三层世界模型集成了以下内容：（L1）精确的符号动作匹配；（L2）从执行日志中学习到的统计数据；以及（L3）针对未知动作的基于 LLM 的预测。

On synthetic planning tasks with branching paths and dead-ends, GATS achieves 100% success rate compared to 92% for LATS and 64% for ReAct.

在具有分支路径和死胡同的合成规划任务中，GATS 实现了 100% 的成功率，而 LATS 为 92%，ReAct 为 64%。

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%.

在涵盖 12 种挑战性场景（包括编码工作流、网页导航和长跨度任务）的全面压力测试中，GATS 保持了 100% 的成功率，而 LATS 下降至 88.9%，ReAct 下降至 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.

GATS 在规划过程中每个任务所需的 LLM 调用次数为零（相比之下 LATS 每个任务需要 37 次），并且能够生成确定性的规划，在多次运行中保持零方差。

Our results demonstrate that systematic search with learned world models can substantially outperform LLM-guided exploration for agent planning.

我们的研究结果表明，结合学习型世界模型的系统化搜索在智能体规划方面可以显著优于 LLM 引导的探索。