GATS：把 LLM 从搜索循环里赶出去，用分层世界模型做确定性的 Agent 规划

一句话引子

你有没有这种感觉——LATS 这类"用 LLM 当搜索大脑"的方法，跑起来是真猛，账单也是真疼。一个 100 步的任务，光 LLM 调用就能堆到几百次，跨种子复现还时不时给你飘一飘。GATS 这篇论文干的事，就是把 LLM 从规划循环里彻底摘出来，让搜索归搜索、推理归推理。

核心摘要

GATS（Graph-Augmented Tree Search）想解决的问题是：LLM 引导的树搜索（LATS、ToT 这类）推理成本高、跨 run 方差大。核心做法是把"世界模型"从 LLM 身上拆下来，做成三层分层的预测器——L1 符号匹配、L2 执行日志统计、L3 才轮到 LLM 兜底，并且 LLM 的预测结果会被缓存复用。规划阶段用 UCB1 在状态转换图上做系统化搜索，零 LLM 调用完成整个 episode。

效果是有点吓人的：合成多步任务 100% 成功率（LATS 92%、ReAct 64%），12 类压力测试 120 任务上 100% vs 88.9% vs 23.9%。我的判断是——这是一篇思路漂亮但评估偏理想化的工作，核心贡献在于"把 LLM 从规划器降级为一次性引导器"这个工程姿态，而不是算法本身有多新颖。值得读，但别急着搬到生产。

论文信息

  • 标题：GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning
  • 作者：Maureese Williams, Dymitr Nowicki
  • arXiv：2607.08894（v1，2026 年 7 月 9 日提交）
  • 代码：https://github.com/MMWilliams/gats
  • 领域：cs.AI / cs.LG

问题动机：LATS 这类方法到底哪里不 work

先把痛点摆清楚。当前 LLM Agent 做多步规划的主流路子大致三条：

方法 怎么干 代价
ReAct LLM 边推理边选动作，每步一次调用 没有搜索，撞了南墙才回头
ToT BFS/DFS 探索多条推理路径，LLM 评估每个分支 分支评估全是 LLM，节点一多就炸
LATS MCTS + LLM 动作提议 + LLM 价值估计 每个搜索节点都要喂 LLM，5-20 倍 ReAct 的调用量

LATS 在 HumanEval 上能干到 94.4% pass@1，确实漂亮。但工业落地的人看一眼就知道这事不靠谱——每个候选动作要 LLM 生成、每个候选状态要 LLM 打分、回溯一次又是一次调用。论文里给的实测数字是 LATS 在合成任务上每任务 371 次 LLM 调用（预算 b=10）。这还只是个 5-7 步的合成任务。

更让人头疼的是随机性。LLM 采样本身就有方差，跨种子跑一遍，相同输入能给你吐出不同的规划。复现实验的时候特别崩溃。

GATS 作者的洞察其实不复杂：

大多数 Agent 任务的"状态-动作"转移，并不真的需要 LLM 来预测。已知动作有精确的符号规则，半已知动作有执行日志可以统计，只有真正未知的新动作才需要 LLM 兜底。

于是分层世界模型就出来了。

方法核心：三层世界模型 + UCB1 + 图记忆

直觉上 GATS 干了三件事：

  1. 把世界模型从 LLM 身上拆下来——分层降级 L1→L2→L3，能符号就符号，能统计就统计，实在不行才 LLM
  2. 用 UCB1 替代 LLM 价值估计——经典多臂赌博机做动作选择，不依赖 LLM 打分
  3. 状态转换图跨步骤持久化——同一状态不同路径到达就合并节点，搜索统计能复用

三层世界模型

世界模型 \(\mathcal{W}(s, a) \rightarrow (s', p)\)，输入当前状态和动作，输出下一状态和置信度。

L1：符号匹配层——对已知 STRIPS 风格的动作规格，前提满足就确定性转移：

\[\mathcal{W}_1(s, a) = \begin{cases} (s', 1.0) & \text{if } \text{prec}(a) \subseteq s \\ (s, 0.0) & \text{otherwise} \end{cases}\]

其中 \(s' = (s \cup \text{add}(a)) \setminus \text{del}(a)\)。这是经典 STRIPS 规划里的转移定义，置信度恒为 1.0。

L2：学习统计层——对在执行日志里见过但没有正式规格的动作，返回最频繁的效果：

\[\mathcal{W}_2(s, a) = \left( \text{argmax}_e \text{count}(a \rightarrow e), \min\left(\frac{\text{count}(a)}{10}, 1.0\right) \right)\]

置信度随观察次数线性增长，10 次后饱和到 1.0。这块的设计挺朴素，但够用——大多数半已知动作的转移效果就那么几种。

L3：LLM 预测层——对从没见过的新动作，调一次 LLM 预测转移结果，置信度固定 0.5：

\[\mathcal{W}_3(s, a) = (\text{LLM}(s, a), 0.5)\]

关键设计：L3 的预测结果会被缓存到 Cache[k(s), a] = (s', p)，下次同样的 (状态, 动作) 对就直接命中缓存，不再调 LLM。

层选择规则就是按优先级降级：

\[\mathcal{W}(s, a) = \begin{cases} \mathcal{W}_1(s, a), & \text{if } p_1(s,a) \geq \tau_1 \\ \mathcal{W}_2(s, a), & \text{if } p_2(s,a) \geq \tau_2 \\ \mathcal{W}_3(s, a), & \text{otherwise} \end{cases}\]

三层成本满足 \(c_1 \ll c_2 \ll c_3\)——符号查找是常数时间，统计查找也是常数时间，LLM 推理是几百毫秒加 token 成本。

期望成本：\(\mathbb{E}[C_\mathcal{W}] = P(L_1)c_1 + P(L_2)c_2 + P(L_3)c_3\)。只要 L1+L2 的覆盖率够高，期望成本就接近常数。论文给的实测是合成任务上 L1 达 100% 覆盖，规划时 L3 调用为 0。

UCB1 替代 LLM 价值估计

LATS 用 LLM 给每个候选状态打分，GATS 直接用 UCB1 在每个节点的可用动作集上做多臂赌博机选择：

\[a_t = \arg\max_{a \in A_{\text{app}}(s)} \left[ Q(s,a) + c\sqrt{\frac{2 \ln N(s)}{N(s,a)}} \right]\]

第一项是经验均值（利用），第二项是探索奖励（探索）。\(N(s,a) = 0\) 时 UCB 值为 \(+\infty\)，保证每个可用动作至少被评估一次——这是个挺重要的细节，避免初始动作被忽略。

价值回传融合了世界模型的置信度：

\[v = p \cdot \text{StateValue}(s') - \lambda(1-p)\]

\(p=1\) 时退化为经典规划里的确定性价值回传；\(p\) 低则惩罚，避免低置信度预测带偏搜索。

状态价值用图上到目标的最短预测距离估计：

\[\text{StateValue}(s) = \begin{cases} \frac{\alpha}{d_\mathcal{G}(s,G) + 1}, & \text{if a goal is reachable from } s \\ 0, & \text{otherwise} \end{cases}\]

\(\alpha = 10\)，离目标越近价值越高，不可达直接归零。这块有个隐患——\(d_\mathcal{G}(s,G)\) 需要在转换图上跑 BFS，最坏复杂度 \(O(|A|^d)\)，动作空间一大会爆炸。作者在局限性里也承认了，\(|A| \approx 20\) 且 \(d > 10\) 就需要剪枝。

状态转换图记忆：跨步骤持久化

这是 GATS 区别于普通 MCTS 的关键差异。搜索过程维护一张有向图 \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\)：

  • 节点 = 规范化状态键 \(k(s)\)
  • 边 = \((k(s), a, k(s'))\)，存储动作、后继、置信度、所用层、访问计数、累积价值

状态合并：\(k(s_i) = k(s_j) \Rightarrow v_i = v_j\)。不同动作序列到达同一状态时合并节点，搜索统计跨路径复用。这在工具使用场景特别有用——同一个中间配置可能由多种动作组合到达，没必要各自独立搜索。

跨规划步骤持久化：执行完一个动作后，搜索统计不丢弃，从对应图节点继续规划。整个 episode 摊销搜索成本。

死胡同检测：当从某节点在当前转换图下无路径到达目标时，标记为死胡同，后续搜索中通往死胡同的动作被赋予低价值。

算法伪代码

Algorithm 1：GATS 单步搜索

输入: 状态 s, 可用动作 A_app, 图 G, 预算 b, 探索常数 c
1:  u ← k(s)
2:  若 u 不在 G 中则添加
3:  for i = 1 to b do
4:    选择 a* = argmax_{a∈A_app} UCB(u, a)
5:    if 边 (u, a*) 不在 G 中 then
6:      预测 (s', p) = W(s, a*)
7:      u' ← k(s')
8:      添加节点 u' 和边 (u, a*, u') 到 G
9:    else
10:     从边 (u, a*) 检索 (s', p)
11:   end if
12:   估计 v = p · StateValue(s') - λ(1-p)
13:   更新 N(u, a*) ← N(u, a*) + 1
14:   用新值 v 更新 Q(u, a*)
15: end for
16: Return: argmax_{a∈A_app} Q(u, a)

Algorithm 2：GATS 完整规划循环

输入: 初始状态 s0, 目标 G, 动作集 A, 预算 b
1:  s ← s0, π ← [], G ← (∅, ∅)
2:  while G ⊈ s and |π| < max_steps do
3:    A_app ← {a ∈ A : prec(a) ⊆ s}
4:    if A_app = ∅ then Return: Failure
5:    a* ← GATSSearch(s, A_app, G, b)
6:    预测或检索 (s', p) = W(s, a*)
7:    s ← s'
8:    将 a* 追加到 π
9:  end while
10: Return: π if G ⊆ s, else Failure

注意第 6 行——执行阶段也是用世界模型预测，不调真实环境也不调 LLM（除非 L3 兜底）。这是 GATS 能做到"零 LLM 调用"的关键，但也是评估被人诟病的地方——下面实验分析会展开。

实验结果：数据漂亮，但基准选择有点巧妙

主实验：100 个合成多步规划任务

任务分三档：Easy（20 任务，3 步，1 个死胡同）、Medium（55 任务，5 步，2 个分支点，资源管理）、Hard（25 任务，7+ 步，多个死胡同，误导路径）。5 个随机种子（42, 123, 456, 789, 1000），LLM 方法用 Llama 3.2 via Ollama，最大规划长度 20 步。

Table 1：合成任务主结果

方法 Success Rate Optimality LLM Calls/Task Variance
Greedy (Oracle) 100.0% 1.00 0 0%
ReAct 64.0% ± 5.0 0.54 135.0 —
LATS (b=5) 70.7% ± 2.0 0.99 172.0 —
LATS (b=10) 92.0% ± 1.0 0.99 371.0 —
GATS (b=5) 84.0% 1.00 0 0%
GATS (b=10) 100.0% 1.00 0 0%
GATS (b=20) 100.0% 1.00 0 0%

几个关键观察：

  1. GATS 在匹配预算 b=10 下比 LATS 高 8 个点（100% vs 92%），同时 LLM 调用从 371 降到 0。这个对比是论文最核心的卖点，确实能打。
  2. Optimality 上 GATS 是 1.00，LATS 也是 0.99——两者找的解都接近最优，差距主要在成功率。
  3. ReAct 的 Optimality 只有 0.54——它经常找一条次优的弯路绕过去，所以即便成功也走了远路。
  4. Variance 上 GATS 是 0——这是确定性搜索的直接好处，跨种子复现完全一致。LATS 虽然方差小（±1%），但仍然不是 0。

McNemar 检验 \(p < 0.01\)，统计显著。

消融 1：搜索预算

Table 2：预算消融

预算 SR (%) Optimality Nodes
b=1 (贪心) 0.0 0.00 5
b=5 84.0 1.00 84
b=10 100.0 1.00 167
b=20 100.0 1.00 334

b=1 时 0% 成功率——这是个挺有意思的点，说明纯贪心选择（没有探索项）在分支+死胡同的任务上会直接栽跟头。b=10 后饱和，节点扩展线性增长。对工程上的启发是 b=10 是个甜点，再大没收益纯浪费。

消融 2：世界模型层

Table 3：世界模型层消融

配置 SR (%) Optimality 描述
GATS (full) 100.0 1.00 L1 + L2 + L3
GATS no_l1 100.0 1.00 L2 + L3 only
GATS no_l3 100.0 1.00 L1 + L2 only

在合成任务上移除任一层无影响——L2 提供足够覆盖。这其实有点尴尬：合成任务的 L1 已经 100% 覆盖，L2 和 L3 根本没机会上场。消融的设计就有点弱——你想证明每层都有用，但实验设置让某些层用不上。

Table 4：世界模型层使用统计（这块才是真信息）

阶段 L1 Hit Rate L2 Hit Rate L3 Calls
Bootstrapping (一次性) 0% 0% ~50
Planning (每任务) 100% 0% 0
Open-domain (投影) ~60% ~30% ~10%

看 Table 4 才明白：合成任务上 L1 100% 命中，规划时根本不用 L2/L3。~50 次 L3 调用是一次性引导成本（建图阶段）。开放域投影里 L1 ~60%、L2 ~30%、L3 ~10%——这才反映了三层架构的真实价值。

消融 3：UCB1 探索常数

Table 7：UCB1 探索常数 c 的敏感性

c SR (%)
0.5 100.0
1.0 100.0
2.0 100.0

在 b=10 充足预算下对 c 鲁棒。这也是预期内的——预算够大时探索项的影响被摊薄了。

压力测试：12 类挑战场景

这是论文最有说服力的部分。12 类场景 × 10 任务 × 3 种子 = 120 任务/方法。场景覆盖 coding workflow、web navigation、long-horizon、trap-heavy、deceptive、no-backtrack 等。

Table 6：压力测试结果（部分类别）

类别 GATS b=20 LATS b=20 ReAct Δ (GATS-LATS)
coding_task 100.0% 63.3% 0.0% +36.7%
deep_horizon 100.0% 63.3% 0.0% +36.7%
web_navigation 100.0% 63.3% 0.0% +36.7%
resource_puzzle 100.0% 86.7% 16.7% +13.3%
trap_heavy 100.0% 96.7% 16.7% +3.3%
memory_limit 100.0% 96.7% 20.0% +3.3%
critical_choice 100.0% 100.0% 63.3% 0.0%
deceptive 100.0% 100.0% 63.3% 0.0%
no_backtrack 100.0% 100.0% 0.0% 0.0%
very_long_horizon 100.0% 100.0% 3.3% 0.0%
Overall 100.0% 88.9% 23.9% +11.1%

几个挺有意思的点：

  1. GATS 在所有 12 类上都是 100%——这个均匀性反而让我有点警觉。任何方法在异质场景上完全不翻车，要么是方法真的强到没朋友，要么是场景设计上偏向了方法的优势区。
  2. GATS 大幅领先 LATS 的类别都是"长视野 + 强结构"——coding_task、deep_horizon、web_navigation。这些场景里动作的前后依赖明确、状态可符号化，正好踩中 L1 符号匹配的甜区。
  3. LATS 在长视野上挣扎——coding_task 只有 63.3%，跟 LATS 在 HumanEval 上 94.4% 的印象差距大。原因是 LATS 的 LLM 价值估计在长序列上累积误差，越往后越偏。
  4. ReAct 几乎全灭——23.9% 的总成功率，说明无搜索的线性规划在这种结构化任务上根本不够看。

我的批判性判断

说实话，看到 Table 6 那 12 个 100% 的时候我有点皱眉。原因有二：

第一，评估基准偏理想化。合成任务的"动作"都是 STRIPS 风格的符号化操作，前提和效果明确——这天然就是 L1 符号匹配的主场。现实里大部分 API 调用的副作用是模糊的、有副作用的、状态依赖的，符号匹配根本覆盖不到。Table 4 的"Open-domain 投影"那一行（L1 ~60%、L2 ~30%、L3 ~10%）才是更真实的分布，但论文没在这个分布上做主实验。

第二，"零 LLM 调用"的成立条件苛刻。GATS 之所以能做到规划时零 LLM 调用，是因为合成任务的 L1 覆盖率 100%。开放域里 L3 一上场，LLM 调用就回来了——虽然有缓存摊销，但首次遇到新动作还是要调。论文里给的"~50 次 L3 引导成本"是在 100 任务上摊销的数字，单任务来看仍然是几十次 LLM 调用。

第三，世界模型的来源没讲清楚。L2 是从执行日志学的，但日志从哪来？L1 的符号规格谁写？论文里说"从生产系统执行轨迹中学习世界模型"是未来工作，那当前实验的 L1 规格其实是手工构造的。这相当于把 LLM 的负担转移到了人工标注上。

但话说回来——GATS 的核心姿态是对的。把 LLM 从规划循环里赶出去、用确定性搜索替代随机采样、用缓存摊销 LLM 调用，这个方向我认可。工业落地的人看完至少能拿走三个具体的工程启发：

  1. 能符号化就符号化——别让 LLM 做它能不做的活
  2. 状态合并比树展开更省——同一状态不同路径到达就复用搜索统计
  3. 缓存是 LLM Agent 的命门——任何 LLM 调用都该问一句"这个能缓存吗"

跟同期工作的对比

GATS 的定位其实挺微妙。它不是第一个用世界模型做规划的——RAP（Hao et al., 2023）就用 LLM 当世界模型跑 MCTS，但每次状态转移都调 LLM，没解决成本问题。GATS 的差异是把世界模型分层降级，让 LLM 只在最底层兜底。

跟 LATS 比，GATS 牺牲了动作提议的灵活性——LATS 可以让 LLM 在搜索中生成新的候选动作，GATS 则只能在预先定义的 \(A\) 中选择。这是一个挺大的限制：开放域里动作空间本身是动态的，GATS 的设定假设动作集已知且有限。

跟经典 STRIPS 规划比，GATS 多了 L2/L3 两层处理"动作规格不完整"的情况。但代价是引入了 LLM 这个不确定组件。经典规划器（如 Fast Downward）在完全已知的符号域上效率比 GATS 高得多，GATS 的价值在于处理"部分已知"的中间地带。

我的整体判断

GATS 是一篇思路漂亮、姿态正确、评估偏理想化的论文。

亮点：

  • 三层世界模型的分层降级是个挺优雅的工程模式，可以直接迁移到任何有"已知-半已知-未知"动作分布的 Agent 系统
  • 状态转换图记忆 + 跨步骤持久化比纯 MCTS 的树展开更省搜索预算
  • UCB1 替代 LLM 价值估计消除了随机性，跨种子方差为零
  • 缓存 L3 预测把 LLM 从循环内推理变成一次性引导，工程上可复用

问题：

  • 评估基准过于偏向 L1 优势区——12 类场景全部 100% 成功率反而削弱了说服力
  • 世界模型来源没讲清楚——L1 规格谁写？L2 日志从哪来？这是把 LLM 负担转嫁到人工标注
  • BFS 价值估计的最坏复杂度\(O(|A|^d)\) 在大动作空间上会爆炸
  • 动作集固定的假设限制了开放域适用性，跟 LATS 的"LLM 动作提议"比是个退步

适合什么人读：在做 Agent 规划系统、对 LLM 推理成本敏感的工程师/研究者。可以拿走分层世界模型和图记忆的设计模式，但别指望直接搬代码到生产。

不适合什么人：想在开放域 Agent（比如浏览器自动化、通用工具调用）上找即插即用方案的人。GATS 当前形态需要前置的符号化工作，这在开放域里本身就是个硬骨头。

最后说一句——这篇论文最大的贡献可能不是算法本身，而是它明确把"LLM 推理成本"和"规划性能"放在同一张表里对比。LATS 类方法长期以来只比成功率不比成本，GATS 把这件事摆到台面上：100% 成功率 + 0 LLM 调用这个组合，哪怕是理想化条件下的，也足够刺激这个领域重新思考"什么是一个好的 Agent 规划算法"。

复现命令

# 合成任务主实验
python run_gats_eval.py --n-tasks 100 \
    --seeds 42 123 456 789 1000 --backend mock

# 压力测试
python run_stress_test.py --n-per-category 10 \
    --seeds 42 123 456

代码仓库：https://github.com/MMWilliams/gats

觉得有启发的话，欢迎点赞、在看、转发。跟进最新 AI 前沿，关注我