09. LATS：把树搜索和语言反思结合起来

背景：单路径的局限

前几篇讨论的方法（Self-Debugging、Reflexion）基本上都是单路径的：Agent 沿一条线走，失败了修正，再走，再修正。这种线性结构有一个问题：一旦走进了错误的方向，修正只能在这条路上打转，无法退回来换一条路。

树搜索提供了另一种思路：在每个决策点同时探索多个方向，保留好的，剪掉差的。LATS（Language Agent Tree Search，Zhou et al., 2023）把这个思路和 LLM 的生成能力、反思能力结合在了一起。

LATS 的结构

LATS 借鉴了蒙特卡洛树搜索（MCTS）的框架，把它适配到语言 Agent 的场景：

                    根节点（初始状态）
                    /        |        \
               动作A        动作B      动作C
              /    \          |
          AA       AB        BA
         (失败)   (继续)     (失败)
                  /    \
               ABA     ABB
              (成功)   (失败)

每个节点代表 Agent 执行了某个动作后的状态。树的扩展过程：

选择（Selection）：从根节点出发，按照 UCB 等策略选择下一个要扩展的节点，平衡已探索路径的利用和新路径的探索。

扩展（Expansion）：对选中的节点，让 LLM 生成多个候选动作（比如 3-5 个不同的代码实现），每个候选成为一个子节点。

评估（Evaluation）：执行每个子节点对应的动作（运行代码、调用工具等），用执行结果打分。代码测试通过得高分，报错得低分。

反思（Reflection）：对于失败的节点，让 LLM 生成一段反思，解释为什么失败。反思会被附加到该节点，如果之后搜索再经过附近的路径，这段反思会放入上下文，帮助 LLM 避开同样的错误。

回传（Backpropagation）：把节点的评估分数向上回传，更新父节点的统计信息，影响下次选择时的优先级。

和 Reflexion 的区别

Reflexion 是线性的：走一条路，失败，反思，下一条路（仍然是线性的，反思放入上下文）。

LATS 是树状的：同时维护多条路径，反思作用于树的局部区域，失败的子树可以被整体放弃，而不必把所有失败的历史都堆入上下文。

维度	Reflexion	LATS
搜索结构	线性	树状
并行探索	否	是
失败处理	加入上下文重试	剪枝 + 局部反思
计算成本	低	较高（多路径扩展）
适合场景	简单任务、低预算	复杂任务、允许多次尝试

在代码生成上的结果

论文在 HumanEval 上的对比：

方法	pass@1
GPT-4（直接生成）	67.0%
ReAct	72.3%
Reflexion	91.0%
LATS	94.4%

在更难的 HumanEval+ 和编程竞赛题目上，LATS 和 Reflexion 的差距拉得更大——任务越复杂、需要探索的空间越大，树搜索的优势越明显。

计算成本的问题

LATS 的代价是显著更多的 LLM 调用次数。每个节点要生成多个候选，每次失败要生成反思，整棵树可能要展开几十个节点。在实际使用中，这意味着：

延迟更高：一次任务可能需要几分钟甚至更长
费用更高：API 调用次数是单路径方法的数倍

因此 LATS 更适合离线的、对质量要求高的场景，比如生成复杂算法代码、竞赛题目求解等。交互式的、需要快速响应的场景，直接生成加 Self-Debugging 的组合通常更实用。

树搜索在 Agent 里的位置

LATS 是把树搜索引入语言 Agent 较早的系统性工作。它的主要贡献是：

证明了 MCTS 的框架可以直接用在 LLM Agent 上，不需要大改
把反思（Reflection）和树搜索（Tree Search）结合起来，反思不再只是线性历史，而是有结构的局部信息

后来的 o1、o3 等推理模型在内部也使用了类似的多路径搜索机制，但实现细节没有公开。从结果来看，LATS 这个方向的判断是对的：对于复杂推理任务，单路径生成的上限比多路径搜索低。

（采用 CC BY-NC-SA 4.0 许可协议进行授权）

本文标题:09. LATS：把树搜索和语言反思结合起来

本文链接:https://www.sshipanoo.com/blog/ai/code-agent-harness/09-LATS/

本文最后一次更新为天前，文章中的某些内容可能已过时！