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

📄 arXiv: 2607.08894v1 📥 PDF

作者: Maureese Williams, Dymitr Nowicki

分类: cs.AI, cs.LG

发布日期: 2026-07-09

💡 一句话要点

提出GATS以解决LLM代理规划中的高计算成本问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 图增强树搜索 分层世界模型 多步骤规划 大型语言模型 自动化决策 机器人规划 智能助手

📋 核心要点

  1. 现有方法如LATS和ReAct在多步骤规划中高度依赖LLM推理，导致计算成本高且结果不稳定。
  2. GATS通过结合系统的UCB1树搜索与分层世界模型，消除了对LLM的依赖，从而提高了规划效率。
  3. 在多项实验中，GATS在复杂场景下实现了100%的成功率，显著优于LATS和ReAct，且无需LLM调用。

📝 摘要（中文）

大型语言模型（LLM）代理在多步骤规划任务中展现出潜力，但现有方法如LATS和ReAct在规划过程中依赖LLM推理，导致计算成本高且行为不确定。本文提出了GATS（图增强树搜索），该规划框架结合了基于UCB1的系统树搜索与分层世界模型，消除了推理过程中的LLM调用，同时实现了更优的规划性能。GATS在合成规划任务中取得了100%的成功率，相较于LATS的92%和ReAct的64%。在涵盖编码工作流、网页导航和长时间任务的12个挑战场景的综合压力测试中，GATS保持100%的成功率，而LATS降至88.9%，ReAct降至23.9%。GATS在规划过程中每个任务无需LLM调用，且生成的计划在多次运行中具有零方差。

🔬 方法详解

问题定义：本文旨在解决现有LLM代理在多步骤规划中面临的高计算成本和不确定性问题。现有方法如LATS和ReAct依赖于频繁的LLM调用，导致效率低下和结果波动。

核心思路：GATS的核心思路是通过引入分层世界模型，结合系统的UCB1树搜索，消除对LLM的依赖，从而实现高效且确定性的规划。该设计旨在利用已知信息和执行日志来增强决策过程。

技术框架：GATS的整体架构包括三个主要模块：第一层（L1）进行精确的符号动作匹配，第二层（L2）利用执行日志学习统计信息，第三层（L3）则使用LLM进行未知动作的预测。通过这种分层结构，GATS能够在不调用LLM的情况下进行有效规划。

关键创新：GATS的主要创新在于其分层世界模型的设计，使得系统能够在规划过程中完全不依赖LLM调用，从而实现了100%的成功率和零方差的计划生成。这一创新与现有方法的本质区别在于其系统性和确定性。

关键设计：在设计中，GATS采用了UCB1算法进行树搜索，确保了探索与利用的平衡。同时，分层模型的每一层都经过精心设计，以确保信息的有效传递和利用，特别是在处理未知动作时的LLM预测部分。整体架构的设计使得GATS在多种复杂场景下表现出色。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

GATS在合成规划任务中实现了100%的成功率，相比之下，LATS的成功率为92%，ReAct为64%。在12个复杂场景的压力测试中，GATS同样保持100%的成功率，而LATS降至88.9%，ReAct降至23.9%。此外，GATS在每个任务中无需LLM调用，显著降低了计算成本。

🎯 应用场景

GATS的研究成果在多种应用场景中具有潜在价值，包括自动化决策系统、机器人规划、智能助手等领域。其高效的规划能力和确定性输出能够显著提升这些系统的性能和用户体验，未来可能在复杂任务的自动化处理上发挥重要作用。

📄 摘要（原文）

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.