语言代理树搜索统一语言模型中的推理、行动和规划

Source: Dev.to

选定理由

评价点

整合性

B：通过 LLM 对状态价值的评估来解决探索与利用的权衡，业务需求度高。

可靠性

S：Proceedings of Machine Learning Research 2024 采纳。作者曾在 DeepMind 工作。

健全性

S：理论设计（引入 MCTS、利用 LM 评估、整合反思）结构严谨，拥有明确的算法组成。

通用性

A：在 langgraph 中也有实现示例，通用性高，但对超参数敏感且运行成本是挑战。

可发展性

A：有多种扩展可能，但受限于树结构，难以应用于状态难以明确定义的任务。

论文信息

Paper: Language Agent Tree Search (LATS)
使用树结构管理 LLM 的思考，使其能够前瞻，从而在少量试错后得到正确结论。

提议手法

使用蒙特卡罗树搜索（MCTS）探索多个行为候选，LLM 进行价值评估与反思，实现长期且一致的决策。

• 特点
  • 将推理、行动、计划、反思、记忆等所有要素统一（LATS 为首例）。
  • 将 MCTS 与贝尔曼回溯的概念应用于 LLM 推理时的搜索。

效果与挑战

• 效果

  • 由于依赖 LLM 的近似环境预测，偏差容易叠加，初始值敏感性较强。
  • 但 LLM 能捕捉长期结构和语义一致性，即使没有严格的环境模型，也能作为有用的启发式。

• 图 2 的解释

  • 在 belief 空间上近似贝尔曼方程的回溯线图。
  • 节点表示状态（历史），边表示行为选择。

算法全貌

对比表

搜索过程

基于 UCB 的节点选择

从所有节点中依据 UCB（Upper Confidence Bound） 评价选取下一个要展开的节点。平衡状态价值函数 $V(s_t)$ 与访问次数 $N(s_{t+1})$，挑选最有前景的节点。

$$ a_t = \arg\max_{a_t}\Bigl[ V(S_t) + c \sqrt{\frac{\log N(S_t)}{N(S_{t+1})}} \Bigr] $$

$$ N(S_{t+1}) \leftarrow N(S_t) + 1 $$

随后，根据记忆获取观测 $o_{t}$。这不同于 Experience Replay，而是直接复用保存于搜索树中的观测，沿同一路径重新遍历。

节点展开与采样

从选中的节点 $s_t$ 采样 $n$ 个子节点，使用带参数 $\theta$ 的模型 $p_\theta$ 生成。

$$ a_t^{(i)} \sim p_{\theta}(S_t), \qquad S_{t+1} = \text{Env}(S_t, a_t^{(i)}) $$

Evaluation（评估）

对新展开的节点状态价值（标量）进行 LLM 评估。

$$ V(s) = \lambda \cdot \mathrm{LM}(s) + (1-\lambda)\cdot \mathrm{SC}(s) $$

• $\mathrm{LM}(s)$：LLM 的价值预测
• $\mathrm{SC}(s)$：Self‑Consistency（自洽性）

相较于传统的 ToT（Yao 2023）仅评估“思考的合理性”，LATS 在获取外部环境观测后再进行评估，从而能够基于代码执行错误或网页搜索结果作出更准确的价值判断。

Backpropagation（树统计量更新）

将仿真得到的未来价值估计 $\hat{R}(h_t)$ 逆向传播至搜索树的每个节点。

$$ V(h_t) \leftarrow \frac{N(h_t),V(h_t) + \hat{R}(h_t)}{N(h_t) + 1} $$

$$ N(h_t) \leftarrow N(h_t) + 1 $$

Reflection（反思）

Reflection 是回顾已有的思考与行动，让 LLM 指出错误或改进点，从而修正搜索策略的阶段。

• 通用性：无需显式的环境模型或奖励设计，直接利用 LLM 的生成与评估能力进行搜索与价值估计。
• 搜索效率：在最小化真实环境交互的同时，通过树搜索与价值回溯将计算资源集中在有前景的思考路径上。
• 灵活性：只要设计好状态或树结构，即可适配多种环境。

实验

Programming 数据集上的结果

如表 4·5 所示，LATS 在两个数据集上均达到了最先进（SOTA）性能。