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

# GATS：基于图增强的树搜索与分层世界模型的高效智能体规划
来源：https://arxiv.org/html/2607.08894
Maureese Williams maureesewilliams@gmail\.com
Dymitr Nowicki
乌克兰国家科学院控制论研究所 nowicki@nnteam\.org\.ua

###### 摘要

大型语言模型（LLM）智能体在多步骤规划任务中展现了潜力，但现有方法如LATS（语言智能体树搜索）和ReAct在规划过程中严重依赖LLM推理，导致计算成本高昂且行为随机。我们提出 **GATS**（图增强树搜索），一种将基于UCB1的系统性树搜索与分层世界模型相结合，从而在推理过程中消除LLM调用并实现更优规划性能的规划框架。我们的三层世界模型整合了：（L1）精确的符号化动作匹配，（L2）从执行日志中学习到的统计数据，以及（L3）针对未知动作的基于LLM的预测。在具有分支路径和死胡同的合成规划任务上，GATS实现了 **100%** 的成功率，而LATS为92%，ReAct为64%。在覆盖12个具有挑战性场景（包括编码工作流、网页导航和长时域任务）的全面压力测试中，GATS保持 **100%** 成功率，而LATS降至88.9%，ReAct降至23.9%。GATS在规划期间每个任务需要 **零次** LLM调用（相比之下，LATS每个任务需要37次），并且产生的计划在多次运行中方差为零。我们的结果表明，结合学习型世界模型的系统性搜索可以显著优于LLM引导的探索，用于智能体规划。

## 1 引言

大型语言模型（LLM）作为推理引擎的出现，激发了人们对能够进行多步骤规划和工具使用的基于LLM的智能体的浓厚兴趣（Yao et al., 2022 (https://arxiv.org/html/2607.08894#bib.bib12); Shinn et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib8); Yao et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib13)）。这些智能体必须在复杂的决策空间中导航，通常面临信息不完整、死胡同和长时域依赖性问题。虽然LLM提供了强大的语义理解，但直接将其用于规划面临两个关键挑战：(1) **计算成本**——每个规划步骤都需要昂贵的LLM推理，以及(2) **随机性**——LLM采样引入的方差使得计划不可复现。

近期工作探索了用于LLM智能体的树搜索方法。LATS（语言智能体树搜索）（Zhou et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib14)）将蒙特卡洛树搜索与基于LLM的动作提议和价值估计相结合。虽然有效，但LATS在每个搜索节点都需要LLM调用，计算成本高昂。思维树（ToT）（Yao et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib13)）类似地依赖LLM进行分支选择。

我们提出 **GATS**（图增强树搜索），一种将世界模型与LLM解耦的规划框架，从而能够在无需推理时LLM调用的情况下进行系统性搜索。我们的关键洞察是，许多领域中的动作效果可以通过一个**分层世界模型**来捕捉：
- •**L1（符号化）**：针对已知动作的精确前提-效果匹配
- •**L2（学习型）**：从执行日志中得到的统计预测
- •**L3（生成式）**：针对新情况的基于LLM的预测

在规划过程中，GATS使用基于UCB1的树搜索（Kocsis & Szepesvári, 2006 (https://arxiv.org/html/2607.08894#bib.bib5)）和世界模型进行状态预测，并根据需要逐层回退。LLM（L3）仅在处理真正未知的动作时被调用，然后这些动作被缓存以备将来使用。

我们的贡献如下：
1. **分层世界模型架构**，结合了符号化、学习型和生成式组件，用于高效状态预测。
2. **系统性基于UCB1的搜索算法**，优于随机的LLM引导探索。
3. **全面评估**：在100个合成规划任务和12个类别的压力测试（120个任务）上，显示GATS实现了100%的成功率且零LLM调用，而LATS（主要测试）为92% 和（压力测试）88.9%，每个任务约需∼37次LLM调用。
4. **消融研究**，展示了预算缩放和世界模型各层的贡献。

## 2 相关工作

#### 基于LLM的智能体
ReAct（Yao et al., 2022 (https://arxiv.org/html/2607.08894#bib.bib12)）将推理和行动交织在一起，使用LLM基于观察选择动作。Reflexion（Shinn et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib8)）增加了自我反思以从失败中学习。Voyager（Wang et al., 2023a (https://arxiv.org/html/2607.08894#bib.bib9)）在Minecraft中展示了使用LLM驱动的技能获取进行开放式探索。DEPS（Wang et al., 2023b (https://arxiv.org/html/2607.08894#bib.bib10)）提出了描述-解释-规划-选择的方法用于复杂任务分解。这些方法在每一步决策中都依赖LLM，限制了可扩展性。

#### LLM的树搜索
思维树（ToT）（Yao et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib13)）使用BFS/DFS结合LLM评估来探索多个推理路径。LATS（Zhou et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib14)）应用MCTS与基于LLM的动作提议和价值估计。RAP（Hao et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib4)）使用世界模型进行MCTS，但状态转换仍需LLM调用。关于LLM推理的近期工作（Lightman et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib11)）展示了基于过程验证的价值。我们的工作不同之处在于使用了预计算的分层世界模型，消除了对推理时LLM的依赖。

#### 世界模型
世界模型在强化学习中取得了成功（Ha & Schmidhuber, 2018 (https://arxiv.org/html/2607.08894#bib.bib2); Hafner et al., 2019 (https://arxiv.org/html/2607.08894#bib.bib3)）。近期工作探索了基于LLM的世界模型（Hao et al., 2023 (https://arxiv.org/html/2607.08894#bib.bib4)），但这些模型每次预测仍需要LLM推理。我们的分层方法仅使用LLM进行引导，然后依赖符号化和学习型组件。

#### 经典规划
GATS从经典人工智能规划中汲取灵感（Ghallab et al., 2004 (https://arxiv.org/html/2607.08894#bib.bib1)），特别是STRIPS风格的动作表示和启发式搜索。我们将其与现代LLM的能力相结合，以处理新动作。

## 3 方法

### 3.1 问题形式化

我们考虑由以下要素定义的规划问题：
- •**状态空间** \(\mathcal{S}\)：命题（事实）的集合
- •**动作空间** \(\mathcal{A}\)：具有前提和效果的动作
- •**初始状态** \(s_0 \in \mathcal{S}\)
- •**目标条件** \(G \subseteq s\) 对于目标状态

一个动作 \(a \in \mathcal{A}\) 在状态 \(s\) 中**可应用**，如果 \(\text{prec}(a) \subseteq s\)。应用 \(a\) 产生状态 \(s' = (s \cup \text{add}(a)) \setminus \text{del}(a)\)。目标是找到一个动作序列 \(\pi = (a_1, \ldots, a_n)\)，使得从 \(s_0\) 执行 \(\pi\) 到达一个目标状态。

### 3.2 分层世界模型

世界模型 \(\mathcal{W}\) 根据当前状态和动作预测下一个状态和置信度：\(\mathcal{W}(s, a) \rightarrow (s', p)\)。我们的三层架构按顺序查询各层，直到获得置信度足够的预测：

#### L1：符号化匹配
对于具有已知STRIPS风格规范的动作：
\[
\mathcal{W}_1(s, a) = \begin{cases}
(s', 1.0) & \text{如果 } \text{prec}(a) \subseteq s \\
(s, 0.0) & \text{否则}
\end{cases}
\quad (1)
\]
其中 \(s' = (s \cup \text{add}(a)) \setminus \text{del}(a)\)。

#### 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)
\quad (2)
\]
这一层维护来自执行日志的转换统计，返回最频繁的效果，置信度 \(c = \min(\text{count}(a)/10, 1.0)\)，在10次观察后饱和为1.0。

#### L3：LLM预测
对于新动作，我们查询LLM：
\[
\mathcal{W}_3(s, a) = (\text{LLM}(s, a), 0.5)
\quad (3)
\]
预测被缓存以避免重复的LLM调用。在实践中，当L1/L2有足够覆盖时，L3很少被调用。

#### 层选择与成本模型
各层按通用性和计算成本递增顺序排列。设 \(c_1\)、\(c_2\) 和 \(c_3\) 表示查询L1、L2和L3的成本，且 \(c_1 \ll c_2 \ll c_3\)。在实践中，\(c_1\) 是一次符号查找，\(c_2\) 是一次统计查找，\(c_3\) 是一次LLM推理调用。对于一个转换查询 \((s,a)\)，分层世界模型的期望成本为：
\[
\mathbb{E}[C_{\mathcal{W}}] = P(L_1)c_1 + P(L_2)c_2 + P(L_3)c_3.
\quad (4)
\]
由于L3对应一次LLM调用，主要效率目标是最大化L1和L2的覆盖，并仅对真正新颖或模糊的转换调用L3。我们将层选择规则写为：
\[
\mathcal{W}(s, a) = \begin{cases}
\mathcal{W}_1(s, a), & \text{如果 } p_1(s, a) \ge \tau_1, \\
\mathcal{W}_2(s, a), & \text{如果 } p_2(s, a) \ge \tau_2, \\
\mathcal{W}_3(s, a), & \text{否则}.
\end{cases}
\quad (5)
\]
这里 \(p_i(s, a)\) 是层 \(L_i\) 赋予的置信度，\(\tau_i\) 是接受该层预测所需的最小置信度。在我们的实验中，L1预测的置信度为：动作可应用时 \(p_1 = 1\)，否则 \(p_1 = 0\)。L2置信度根据观察到的转换计数估计：
\[
p_2(a) = \min\left(\frac{n(a)}{n_0}, 1\right),
\quad (6)
\]
其中 \(n(a)\) 是动作 \(a\) 被观察执行的次数，\(n_0\) 是饱和阈值。这种基于计数的估计器反映了重复一致的观察应增加对学习到的转换模型的信任。

#### LLM调用摊销
设 \(B\) 为每个规划步骤的搜索预算，\(D\) 为规划时域。在每次节点评估时调用LLM的规划器成本约为：
\[
C_{\mathrm{LLM\text{-}search}} = O(BD \cdot c_3).
\quad (7)
\]
相比之下，GATS缓存L3预测：
\[
\mathrm{Cache}[k(s), a] = (s', p),
\quad (8)
\]
其中 \(k(s)\) 是状态 \(s\) 的规范表示。因此，GATS进行的LLM调用次数受限于L1和L2失败且未缓存的唯一转换查询数：
\[
N_{\mathrm{LLM}}^{\mathrm{GATS}} = \left| \{ (k(s), a): L_1 \text{ 失败}, L_2 \text{ 失败}, (k(s), a) \notin \mathrm{Cache} \} \right|.
\quad (9)
\]
这改变了LLM的角色：从反复的规划器循环推理转变为一次性的转换模型引导。

### 3.3 状态转换图记忆

GATS的图组件被显式表示为一个持久的状态转换图：
\[
\mathcal{G} = (\mathcal{V}, \mathcal{E}).
\quad (10)
\]
每个节点 \(v \in \mathcal{V}\) 对应一个规范状态键 \(k(s)\)，每条有向边对应一个预测的转换：
\[
e = (k(s), a, k(s')) \in \mathcal{E}, \quad (s', p) = \mathcal{W}(s, a).
\quad (11)
\]
边存储动作 \(a\)，预测的后继状态 \(s'\)，世界模型置信度 \(p\)，用于生成预测的层，以及搜索统计如访问次数和累积价值。

这个图表示与普通树搜索在一个重要方面不同：如果两个不同的动作序列到达同一状态，它们会被合并：
\[
k(s_i) = k(s_j) \Rightarrow v_i = v_j.
\quad (12)
\]
因此，转换预测、价值估计和访问次数在不同路径之间被重用。这在工具使用领域尤其有用，因为不同的动作序列可能达到相同的中间配置。

图在规划步骤之间保持。执行一个动作并移动到新状态后，GATS不会丢弃之前的搜索统计；而是从对应的图节点继续规划。这使得世界模型预测和价值估计在整个回合中被摊销。图还可以支持死胡同检测。当从该节点出发，在当前已知转换图中没有任何路径到达目标节点时，该节点被标记为死胡同。导致死胡同区域的动作在后续搜索中被赋予低价值。

与为每个动作序列创建单独节点的普通树搜索不同，状态转换图只存储每个可达状态一次。如果两个不同的部分计划导致相同的规范状态，它们的节点被合并，规划器重用相同的出边、转换预测、访问次数和价值估计。在树搜索中，这两个历史将被独立扩展，重复进行世界模型查询和下游价值估计。在GATS中，规范状态键 \(k(s)\) 充当了一个换位表：所有到达 \(s\) 的路径共享同一个图节点，因此共享累积的搜索证据。

该图在规划步骤之间也是持久的。在规划器选择并执行一个动作后，它不会丢弃上一步构建的搜索结构。相反，规划从对应新状态的图节点继续，而 \(\mathcal{G}\) 的其余部分保留供未来重用。这种持久性在多步骤工具使用问题中很重要，其中相似状态可以在不同的动作序列之后或从次优选择中恢复后反复遇到。因此，GATS不仅摊销了基于LLM的转换预测，还摊销了符号转换查找、基于BFS的价值估计以及UCB统计，这些是在整个回合上摊销的，而非仅在单次局部搜索调用中。

### 3.4 图边上的UCB选择

在给定状态 \(s\)，每个可应用的动作 \(a \in A_{\mathrm{app}}(s)\) 被视为一个有限臂老虎机问题中的臂。拉一个臂对应于扩展或重用图边 \((k(s), a, k(s'))\)，使用分层世界模型预测后继状态，并评估结果状态。

设 \(N(s, a)\) 是动作 \(a\) 从状态 \(s\) 被评估的次数，\(Q(s, a)\) 是其经验平均价值：
\[
Q(s, a) = \frac{1}{N(s, a)} \sum_{i=1}^{N(s, a)} v_i.
\quad (13)
\]

GATS使用UCB规则选择动作：
\[
a_t = \arg\max_{a \in A_{\mathrm{app}}(s)} \left[ Q(s, a) + c \sqrt{\frac{2 \ln N(s)}{N(s, a)}} \right],
\quad (14)
\]
其中
\[
N(s) = \sum_{a \in A_{\mathrm{app}}(s)} N(s, a).
\quad (15)
\]

对于未访问的动作，我们定义：
\[
N(s, a) = 0 \Rightarrow \mathrm{UCB}(s, a) = +\infty.
\quad (16)
\]
这保证了在算法将预算投入看似高价值的动作之前，每个可应用的动作至少被评估一次。