🤖 AI

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

该论文介绍了 GATS，这是一个通过分层世界模型和基于 UCB1 的树搜索来取代昂贵的 LLM 推理的规划框架，旨在实现多样化复杂任务下的 100% 成功率以及确定性的零调用规划，其性能显著优于 LATS 和 ReAct 等现有方法。

原作者： Maureese Williams, Dymitr Nowicki

发布于 2026-07-13

📖 1 分钟阅读☕ 轻松阅读

原作者： Maureese Williams, Dymitr Nowicki

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图解决一个巨大的、棘手的迷宫。你有一个超级聪明的伙伴（一个大型语言模型，简称 LLM）可以和你交谈并建议你该往哪转弯。但这里有个限制：每当你向你的伙伴寻求建议时，他们都必须进行长时间的午睡来思考，而且有时当你询问同一个问题时，他们的回答也会有所不同。如果迷宫中有死胡同或者需要长序列的转向，每一步都向你的伙伴求助会变得既昂贵又混乱。

这就是研究人员 Maureese Williams 和 Dymitr Nowicki 用他们的系统 GATS（图增强树搜索）所解决的问题。他们找到了一种极其高效的导航方式，几乎不需要唤醒他们的超级聪明伙伴。

旧方法：“每步一问”法

以往的方法，比如 ReAct 和 LATS，有点像是一个徒步旅行者在每一个岔路口都会停下来问向导：“我该往哪走？”

ReAct 只是问一次然后就出发。它很快，但经常会走进死胡同。在测试中，这种方法在这些棘手的迷宫场景中仅有 64% 的成功率。
LATS 更聪明一些；它先询问向导，然后针对下一步再次询问，再询问下一步，从而构建出一棵可能性的树。但因为它需要为树上的每一个分支都询问向导（LLM），所以它会变得很累且成本很高。在测试中，LATS 的成功率为 92%，但它在每个任务中需要询问向导大约 37 次。此外，因为向导有时会随机猜测，如果你两次尝试同一个迷宫，你可能会得到不同的路径。

新方法：GATS（“制图者”策略）

GATS 改变了游戏规则。GATS 不再为每一次转向都询问向导，而是使用一个分层世界模型（Layered World Model）来构建自己的内部地图。你可以把这张地图看作拥有三个知识层：

第一层（精确规则手册）： 对于系统已经完全掌握的行为（例如“如果我按下这个按钮，门就会打开”），它使用简单的、即时的检查。无需思考。这就像知道 2+2 永远等于 4。
第二层（经验日志）： 如果系统以前见过某个行为发生，但没有完美的规则，它会检查自己的旅行日记。“上次我这样做时，成功了 9/10 次。”这是从数据中学习到的，而不是靠猜测。
第三层（超级天才伙伴）： 只有当系统遇到全新的、未知的事务时，才会唤醒 LLM 向导。但神奇之处在于：一旦向导给出了答案，GATS 就会将答案记录在地图中。下次遇到相同的情况时，G只看地图即可。它永远不会再为那个特定的事物询问向导。

结果：速度、确定性与成功率

研究人员在 100 个合成规划任务上测试了它，这些任务设计得非常复杂，具有分支路径和死胡同。

GATS 达到了 100% 的完美成功率。
LATS 为 92%。
ReAct 为 64%。

但真正的关键点是？GATS 在实际规划这些任务期间零次调用 LLM。它完全利用自己的地图和规则完成了所有思考。因为它不依赖于 LLM 的随机猜测，所以 GATS 每次运行都能产生完全相同的完美计划。它的方差为零。

他们还进行了大规模的“压力测试”，涵盖了 120 个任务，分布在 12 个困难类别中，如编码工作流、预订机票和复杂的迷宫导航。

GATS 依然保持了 100% 的成功率。
LATS 降至 88.9%。
ReAct 则大幅跌落至 23.9%。

为什么有效（秘诀所在）

论文指出，GATS 之所以获胜，是因为它使用了系统化搜索（称为 UCB1），而不是随机猜测。想象一个侦探在有条不紊地检查每一个线索，而不是仅仅凭直觉行动。

系统化 vs. 随机性： LATS 依赖 LLM 来猜测哪条路径看起来更好。如果 LLM 的“直觉”错了，整个计划就会失败。GATS 系统地检查所有选项，确保不会仅仅因为向导那天状态不好就错过了正确的路径。
确定性 vs. 随机性： 因为 GATS 在大多数步骤中都使用自己的地图，所以结果始终是一致的。而依赖 LLM 的 LATS，如果你两次运行同一个任务，它可能会给你不同的答案。

这意味着什么（以及它不意味着什么）

作者非常明确地说明了他们成功的局限性。这些结果是基于模拟和合成任务的，在这些受控环境中，游戏的规则（“动作规范”）是预先已知的。在这些受控环境中，GATS 是冠军。

然而，论文明确排除了 GATS 目前是解决一切问题的“万灵药”这一观点。如果你把 GATS 扔进一个完全荒野、开放式、没有任何规则或过去日志可供学习的世界，它将不得不更多地依赖 LLM（第三层），这会使其变慢且效率降低。作者建议，为了让 GATS 在现实世界中大放异彩，我们需要先建立更好的地图（世界模型），例如通过学习人类如何实际使用工具的日志。

简而言之，这篇论文表明，对于可以定义规则的规划任务，我们不需要在每一步都向超级智能 AI 求助。我们可以构建一张智能的、自动更新的地图，从而以 100% 的成功率、零成本和零混乱来应对复杂的难题。

技术摘要：GATS（基于分层世界模型的图增强树搜索）

问题陈述

大语言模型（LLM）智能体在多步规划和工具使用方面展现出了潜力，但目前的方案（如 ReAct 和 LATS）面临两个关键局限性：

计算成本： 现有方法在每个规划步骤或搜索节点都需要进行昂贵的 LLM 推理，导致高延迟和高资源消耗。
随机性： LLM 采样引入了方差，导致计划不可复现，且在多次运行之间表现出性能不一致。

核心挑战在于开发一种既能保持 LLM 推理能力，又能消除状态预测阶段推理调用，从而实现确定性、高效且可扩展的智能体规划框架。

方法论：GATS 框架

作者提出了 GATS（图增强树搜索），这是一种将世界模型与 LLM 解耦的规划架构。GATS 将系统的 UCB1 树搜索与分层世界模型以及持久化的状态转移图相结合。

1. 分层世界模型 ( $W$ )

世界模型用于预测给定当前状态 ( $s$ ) 和动作 ( $a$ ) 后的下一个状态 ( $s'$ ) 及置信度 ( $p$ )。它按计算成本和泛化程度递增的顺序查询三个层级：

L1（符号层）： 对具有已知 STRIPS 式规范的动作进行精确的前置条件-效应匹配。该层提供确定性预测（ $p=1.0$ ），计算成本极低（符号查找）。
L2（学习统计层）： 从执行日志中提取的统计预测。对于在执行过程中观察到但缺乏正式规范的动作，它返回出现频率最高的效应，置信度为 $p = \min(\text{count}(a)/10, 1.0)$ 。
L3（生成/LLM 层）： 针对真正新颖或模糊的动作进行基于 LLM 的预测。至关重要的是，来自 L3 的预测会被缓存，以避免对相同转换进行重复的推理调用。

系统优先使用 L1 和 L2 以最大化覆盖范围，仅在必要时调用 L3。这种方式“摊销”了 LLM 的成本，将其从每一步的推理需求转变为一次性的引导（bootstrapping）成本。

2. 持久化状态转移图

与独立扩展节点的传统树搜索不同，GATS 维护一个显式的图 $G = (V, E)$ ，其中节点代表规范的状态键 $k(s)$ 。

状态合并： 如果不同的动作序列到达相同的状态，它们会合并为一个节点。这允许在不同路径间复用转换预测、访问计数和价值估计。
持久性： 该图在规划步骤之间保持持久。在执行动作后，规划从对应的图节点恢复，而不是重新开始搜索，从而在整个回合中摊销价值估计和搜索统计数据。
死路检测： 没有路径通向目标的节点会被标记为死路，允许规划器为导致进入这些区域的动作分配低价值。

3. 基于 UCB1 的搜索

GATS 在图边上采用 UCB1（上置信界）选择策略。

动作选择： 在每个状态下，算法选择使 $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ 最大化的动作 $a$ 。这确保了在提交高价值路径之前，对所有适用动作进行系统的探索。
价值估计： 状态的价值是通过基于 BFS（广度优先搜索）的启发式方法，根据预测的到目标的最短距离 ( $d_G$ ) 推导出的： $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ 。
置信度集成： 回溯价值结合了世界模型的置信度： $v = p \cdot StateValue(s') - \lambda(1-p)$ ，从而惩罚不确定的预测。

核心贡献

分层世界模型架构： 一种新型的符号、学习和生成组件集成方式，能够在最小化 LLM 依赖的同时实现高效的状态预测。
带有图记忆的系统化 UCB1 搜索： 一种通过利用持久化图来复用搜索证据并确保确定性结果，从而超越随机 LLM 引导探索的规划算法。
全面的评估： 在 100 个合成规划任务和涵盖编码、网页导航及长程任务的 12 类压力测试（120 个任务）上进行了广泛测试。
规划期间零 LLM 调用： 证明了 GATS 在规划阶段可以实现 0 次 LLM 调用即可达到 100% 的成功率，这与每个任务需要数十次调用的基准方法形成鲜明对比。

实验结果

合成规划任务 (100 个任务)

成功率： GATS 在预算 $b=10$ 时实现了 100% 的成功，优于 LATS (92%) 和 ReAct (64%)。
效率： GATS 在规划期间每个任务需要 0 次 LLM 调用，而 LATS 大约需要 37 次调用。
确定性： GATS 生成的计划在随机种子下的方差为 0%，而 LATS 和 ReAct 由于 LLM 的随机性表现出 1–5% 的方差。
最优性： GATS 达到了 1.00 的最优比，与 Oracle（先知）持平。

压力测试 (12 个类别, 120 个任务)

压力测试包括具有挑战性的场景，如编码工作流、网页导航、深层时界任务和不可逆决策（死路）。

整体性能： GATS 在所有类别中均保持了 100% 的成功率。
对比性能： LATS 的整体成功率降至 88.9%，在编码 (63.3%)、网页导航 (63.3%) 和深层时界 (63.3%) 任务中表现挣扎。ReAct 在这些任务中表现极差，仅为 23.9%。
具体提升： 与 LATS 相比，GATS 在编码、网页导航和深层时界任务中的提升最为显著（+36.7%）。

消融实验

搜索预算： 性能在预算 $b=10$ 时达到饱和；进一步增加带来的收益递减。
世界模型层级： 在合成任务中，单独移除 L1 或 L3 均不会影响成功率（因为 L2 提供了足够的覆盖），这验证了系统的优雅降级能力。在开放领域投影中，预计 L3 (LLM) 将处理约 10% 的新颖动作。

重要性与主张

论文认为，带有学习型世界模型的系统化搜索可以显著优于 LLM 引导的探索。GATS 的主要意义在于其能够：

消除推理时的 LLM 成本： 通过缓存预测并依赖符号/学习层，GATS 消除了重复 LLM 调用带来的计算瓶颈。
确保可复现性： 分层世界模型和 UCB1 搜索的确定性特征消除了 LLM 采样固有的随机方差。
处理复杂规划： 该框架成功地应对了分支路径、死路和长程依赖，而纯 LLM 方法 (ReAct) 和重 LLM 树搜索 (LATS) 在这些场景下会失败或表现不佳。

作者将 GATS 定位为适用于动作语义可以形式化（例如 API、结构化工具使用）领域的优化解决方案，为更高效、更可靠的自主智能体提供了一条路径。他们也承认，在动作效应未知的开放领域中，对 L3 层的依赖会增加，从而降低但不会完全消除相对于 LATS 的效率优势。