Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models

Paper: arXiv:2310.04406 Code: lapisrocks/LanguageAgentTreeSearch Code reference: main @ 853d8161 (2024-07-30)

1. Motivation (研究动机)

现有 LM agent 方法在三条线上各自有进展，但彼此割裂。纯 reasoning 方法如 CoT、ToT、RAP 主要依赖模型内部表征，几乎不看环境反馈；acting 方法如 ReAct、Reflexion 能与外部环境交互，却缺少系统化 planning；而已有 planning 方法即便用上搜索，也经常只是在固定 prompt 上做 BFS/DFS，或者假设 LM 能充当准确 world model。论文第 3 节把问题拆成三个缺陷：Flexibility 不足，无法在中间状态系统探索多条候选 continuation；Sensibility 不足，无法把环境 observation 纳入 value judgement；

Adaptability 不足，不能把试错历史与 verbal reflection 回灌到后续搜索。这篇论文要解决的具体问题是：如何把 reasoning、acting、planning 放进统一的 language-agent 控制框架中，让 LM 在有无环境反馈的场景里都能做 deliberate search，而不是一次性贪心生成单条轨迹。作者特别关注“可回退”的文本环境，因为文本上下文天然允许把历史 state copy-paste 回 prompt，避免传统 MCTS 对可逆 environment model 的强依赖。

这个问题值得研究，因为很多真实 agent 任务都不是一步完成的静态问答，而是多阶段决策：HotPotQA 需要边检索边修正事实链路，programming 需要利用 compiler/test feedback 修补代码，WebShop 需要在大量候选商品和 options 中做长链导航。若能统一处理这三类任务，就意味着 LM agent 可以从“单次 prompt 技巧”升级成“带显式搜索控制的通用 problem-solving interface”。

论文对这个动机的表述还有一层更细的意思：当前很多 agent 失败，并不是因为模型完全不会做最终任务，而是因为它在早期某一步选错后没有便宜的纠错机制。 例如 HotPotQA 中第一次 search[...] 搜错实体，后面整个 supporting facts 链就会被带偏；WebShop 中第一次点击进入错误商品页，后续 option 选择几乎都建立在错误页面上下文上；program synthesis 中第一次生成的函数骨架若方向错误，之后继续局部补丁往往只能越修越乱。线性 prompting 缺的不是“更长输出”，而是对中间状态的重访与重选能力。作者因此把问题从“如何生成更好的答案”重写成“如何管理一组部分完成的语言轨迹”。这一定义变化很关键。

对传统 NLP 任务，大家通常只看最终 answer quality；但对 agent 任务，真正决定成败的是一串 latent 决策：下一步要不要检索、检索什么词、读到结果后是否切换假设、失败后是否回退到前一层。LATS 关心的正是这串中间决策的搜索组织。从 benchmark 选择也能看出作者的动机不是做某个垂类特化器，而是验证一个更广义的 agent hypothesis。HotPotQA 代表“需要外部检索的知识型推理”；HumanEval / MBPP 代表“有程序执行反馈的构造型任务”；WebShop 代表“长 horizon、分支极多、反馈延迟的交互环境”；Game of 24 则拿来检验即便没有真实环境反馈，树搜索本身是否仍有价值。

若同一控制框架能在这四类任务都胜过 CoT / ReAct / Reflexion / ToT / RAP，那么论文就不只是提出一个新 prompt，而是在主张一种更统一的 language-agent 范式。

另一个值得注意的研究动机是成本结构。很多更强的 planning 方法隐含假设是“可以训练一个 value model”“可以学习环境 model”“可以做 domain-specific RL”。但这些假设在 API-based LLM agent setting 往往不成立：研究者手里常常只有 black-box LM 调用权限，没有额外训练预算，也拿不到足够稳定的在线交互数据。LATS 试图证明，即使不额外训练参数，只靠 prompt + search + environment feedback 的组合，也能得到接近“经典规划算法 + 语言模型”融合的收益。

因此，这篇论文真正瞄准的不是某个单点性能差距，而是一个更底层的系统问题：怎样让语言模型在推理过程中拥有显式的“试错-比较-回退-再探索”机制。 这也是为什么作者把标题写成 unifies reasoning, acting, and planning，而不是只强调 MCTS 或某个 benchmark 提升。换句话说，论文的 motivation 不是“再证明一次搜索有用”，而是指出过去这些能力被分散在不同方法族里，导致研究结论难以迁移。一个在纯 reasoning benchmark 上成立的技巧，往往不能直接带到有环境交互的 agent；一个依赖外部反馈的 acting 方法，也未必能给出像样的全局规划。LATS 想填补的正是这条方法论断层。

这也解释了作者为何强调 unifies。统一在这里不是营销措辞，而是指同一套搜索控制变量能够跨任务复用，并把此前分散讨论的 reasoning gain、tool-use gain、planning gain 放到同一实验坐标系下比较。

2. Idea (核心思想)

核心洞察是：把 LM 当成一个可复用的搜索组件，而不只是 final answer generator。 在 LATS 里，同一个 LM 同时扮演 action generator、state evaluator、self-reflection generator；外部环境负责提供 observation 和 terminal reward；MCTS 负责在 exploration 与 exploitation 之间做全局控制。关键创新可以压缩成三点。第一，节点状态不只包含 action history，还显式包含 observation history，因此搜索基于“语言状态 + 环境反馈”的联合空间。

第二，value function 不通过额外训练得到，而是由 LM 自评分数 LM(s) 与 self-consistency 统计 SC(s) 组合为 $V (s) = λ \cdot L M (s) + (1 - λ) \cdot SC (s)$ 。第三，失败轨迹不会被丢掉，而是生成 verbal self-reflection，作为后续扩展和评估的附加上下文。与 ToT 的根本差异在于，ToT 主要在内部 reasoning tree 上搜索，value judgement 基本不利用环境 observation；

与 RAP 的差异在于，RAP 依赖 LM 充当 world model 做前瞻模拟，而 LATS 直接与真实环境交互，不要求模型精确预测未来状态；与 ReAct / Reflexion 的差异在于，LATS 不再线性地沿一条轨迹走到底，而是通过 UCT 在多条候选分支之间有原则地重访高价值节点。如果把论文的核心思想再压缩一层，可以概括成一句话：把“语言轨迹”提升成搜索树上的一等公民。 在 ReAct 里，trajectory 只是顺着 prompt 往下长；在 Reflexion 里，trajectory 失败后会被总结，但下一次 trial 仍是一条新线；在 LATS 里，每条 partial trajectory 都是可评估、可回访、可继续扩展的节点对象。

这样一来，LM 不再只是 token-by-token 续写器，而像是一个为搜索器提供 proposal、critic、verbal debugger 的通用子模块。

这也是论文与“多采样 best-of-k”策略的根本不同。best-of-k 当然也会生成多条候选轨迹，但它们彼此独立，无法共享中间状态信息，更无法在第 3 步发现某条分支好、就在第 3 步继续沿它扩展。LATS 则把预算集中花在“局部 promising 的前缀”上：如果某个 partial state 看起来高价值，算法会在这个 state 周围继续细分搜索，而不是平均地把 token 撒在完全独立的整条样本上。这一点解释了为什么作者在相近甚至更低 sample complexity 下仍能击败 best-of-k ReAct。论文还有一个隐含但重要的设计判断：语言环境里的“状态”可以直接用文本表示，不一定需要专门的 symbolic planner state。传统 MCTS 常依赖显式 simulator 和可复制 world state；LATS 则利用了 LM agent 的天然优势，即历史 thought/action/observation 本来就是文本，可以直接回填到 prompt。作者相当于把 prompt engineering 与 search state representation 合二为一，让“状态复制”退化成“上下文复制”，从而显著降低了把规划算法接到 LLM agent 上的系统门槛。从这个角度看，LATS 的新意不只是把 MCTS 搬进来，而是重新定义了三个角色的边界：

LM 负责提出候选 continuation，并基于语言上下文做语义性判断。
Environment 负责提供外部可验证反馈，纠正 LM 自我想象的偏差。
Search controller 负责统一分配有限调用预算，决定哪里值得继续花 token。

这三者分工清楚后，reasoning、acting、planning 才第一次真正出现在同一闭环里，而不是三套平行技巧。

3. Method (方法)

3.1 Overall framework：把 LM agent 包进 MCTS 控制回路

Figure 1 解读：这张总览图对应论文对 LATS 的定位。核心不是再发明一种新的 action vocabulary，而是把已有 ReAct / CoT agent 作为 base policy $p_{θ}$ ，在每个 state 上采样多个候选动作，再通过 value evaluation、simulation 和 backpropagation 决定下次继续扩展哪一条分支。图里强调的是“同一套控制逻辑”可落到 reasoning、programming、web navigation 三类场景。

Figure 2 解读：图中把 LATS 拆成六步操作：selection、expansion、evaluation、simulation、backpropagation、reflection。selection 用 UCT 从已有树上选下一段最值得扩展的 path；expansion 从当前节点一次采样 $n$ 个 action / thought；evaluation 对新 child 节点打分；simulation 沿高 value child 继续 rollout；如果终点失败，则额外生成 reflection；最后把 reward 反传到祖先节点。作者想强调的是，reflection 不是独立算法，而是嵌入在搜索回路里的失败后处理。

从形式化上，节点状态写成 $s = [x, a_{1 : i}, o_{1 : i}]$ ，其中 $x$ 是原始输入， $a_{1 : i}$ 是动作序列， $o_{1 : i}$ 是观察序列。对于纯 reasoning 任务，observation 可以为空或仅由 internal reasoning 组成；对于 HotPotQA / WebShop / programming，这些 observation 分别对应检索结果、网页反馈、单元测试/编译反馈。这个统一状态定义是论文能“一套方法跨三类任务”的关键。

论文在这里实际上做了一个很实用的抽象：它没有强求所有任务共享同一种 action space，而是只要求它们共享“交替式文本轨迹”的外形。也就是说，某个任务的 action 可以是自然语言 thought、可以是 API call、也可以是一整段程序；observation 可以是检索结果、DOM 文本、失败测试日志。只要这些对象最后都能序列化进 prompt，LATS 的上层控制逻辑就不必改写。这种抽象比很多特化 agent framework 更轻，也更容易迁移到新环境。

3.2 Selection 与 UCT：把 exploration / exploitation 变成显式控制

论文沿用标准 MCTS 的 UCT 选择准则： $UCT (s) = V (s) + w \frac{l n N ( p )}{N ( s )}$ 其中 $p$ 是父节点， $N (s)$ 是访问次数， $V (s)$ 是当前节点 value， $w$ 是 exploration weight。直觉上， $V (s)$ 负责 exploitation，优先重访当前看起来更 promising 的分支；第二项负责 exploration，避免算法过早塌缩到某条局部最优轨迹。这一公式在语言 agent 里有两个非传统含义。第一，visit count 不只是统计学量，而是“此前已经在这个上下文附近花过多少次 LM 调用预算”的代理变量；第二，exploration bonus 不是鼓励物理空间探索，而是鼓励去试不同的 prompt continuation。

换句话说，UCT 在这里控制的是 token 预算的再分配：已经被多次尝试的中间状态，即便当前 value 不低，也会因为 exploration bonus 变小而让出一部分预算给别的候选分支。作者选择 UCT 还有一个工程上的现实理由。和需要学习 tree policy 的方案相比，UCT 几乎零额外训练成本，且不同任务只需改动节点 value 的定义与 expansion/evaluation prompt。论文想证明的是“即便 controller 很朴素，只要把状态、反馈和语言评估接对位置，也能比线性 agent 强”，因此它刻意没有再叠加更复杂的 learned planner。源码里这一层在不同任务上实现得并不完全一致。

hotpot/lats.py 与 webshop/lats.py 都定义了 Node.uct() 并在 select_node() 中递归选择非 terminal child；programming/mcts.py 里的 Node.uct() 类似，但由于 programming 的 action 粒度是“完整解答程序”，其搜索树更浅、每次 expansion 更重。直觉上，UCT 在文本 agent 中最重要的作用不是数学最优性，而是给“下一次应该从哪个 partial context 继续 prompt”提供一个跨轨迹的 global priority。

3.3 Expansion / Evaluation / Simulation：把 LM 从单次解码器变成树搜索部件

在 expansion 阶段，LATS 不是只取一个 greedy continuation，而是从 base policy $p_{θ}$ 采样 $n$ 个候选动作。对于 HotPotQA，这些动作既可能是 search[...] / lookup[...] / finish[...]，也可能是自然语言 thought；对于 WebShop，动作主要是 search[...]、click[...]、think[...]；对于 programming，每个 action 实际上是一份完整代码候选。

论文提出的 value 函数是： $V (s) = λ \cdot L M (s) + (1 - λ) \cdot SC (s)$ 其中 $L M (s)$ 来自 LM 对当前 state 的自评， $SC (s)$ 是 self-consistency heuristic，反映同一 state 下重复采样动作的频率或一致性。作者的论点是，单靠 terminal reward 太稀疏，而纯程序化 heuristic 又不够灵活；LM score 提供语义判断，SC 提供低成本统计先验，两者结合能在不训练 value model 的情况下逼近“expected future reward”。为什么这里需要把 evaluation 单独拿出来，而不是等 rollout 结束再看 reward？因为三个目标任务都有明显的 delayed reward 问题。

HotPotQA 只有 finish[...] 后才能知道答案是否正确；WebShop 通常要经过多次 search/click 组合后才知道买到的商品是否满足约束；programming 也往往要等完整程序生成并运行 tests 后才知道 pass rate。若完全依赖终止奖励，搜索会非常稀疏且昂贵。LM state evaluation 的意义在于给“看起来像好中间状态”的节点一个 dense proxy，提前指导树的生长方向。附录和正文结合起来看，作者默认的 evaluation prompt 其实承担了一个接近“语言版 value head”的角色。

它会读取问题、当前 thought/action/observation history，并输出当前分支前景的自然语言判断或标量分数。这个设计与直接让模型继续生成答案不同，因为它显式切换了 LM 的任务定义：从 actor 切成 critic。也正因为如此，LATS 的关键不是单个 prompt 模板，而是同一个 base LM 在不同阶段被赋予不同 function role。

三类任务的 expansion 粒度也体现了方法设计的弹性。HotPotQA / WebShop 的 expansion 更像局部一步动作提案，树较深、每层分支较窄；programming 的 expansion 则是一整份代码候选，树更浅但每个子节点代价更高。论文没有强行让所有任务使用统一深度或统一 branching factor，而是只保留“先采样多个 child，再基于 value / reward 筛选”的共性。这个选择很重要，因为它说明 LATS 不是 rigid algorithm template，而是一类 controller pattern。 simulation 阶段，算法从当前候选中优先沿最高 value child 继续 rollout，直到 terminal state 或达到 depth limit。这里的关键直觉是：evaluation 不只是给当前 child 排序，还决定了 rollout 的方向，因此 value quality 会直接决定 token 花费和最终成功率。 对 WebShop 这类长程环境，好的 value 可以减少无效页面跳转；对 programming，好的 value 可以减少把时间浪费在明显错误的候选程序上。

3.4 Reflection 与 backpropagation：把失败轨迹变成未来搜索上下文

若 terminal trajectory 成功，则直接停止搜索；若失败，则系统利用轨迹与反馈生成 verbal self-reflection，并把它和失败轨迹一起写入 memory，在后续 expansion/evaluation prompt 中再次注入。论文强调，这种 reflection 相当于给 agent 提供 semantic gradient，而不需要真的做 RL 或反向传播。reflection 在这篇论文里并不是锦上添花的“解释性文本”，而是 failure compression mechanism。没有 reflection 时，失败轨迹只是一大段原始 history，后续 prompt 很难从中抽取“到底错在哪”。

加入 reflection 后，模型会把失败原因压缩成一句或几句可重用的语言约束，例如“不要重复搜索已经证伪的实体”“若测试报类型错误，应先检查函数返回值格式”。这使后续扩展不必完整重演失败，也能继承失败经验。作者把 reflection 接在 terminal failure 之后，而不是每一步都反思，也体现了成本意识。逐步 reflection 虽然可能更细，但会显著增加 LM 调用数，并让上下文快速膨胀；terminal reflection 则只在真正失败时生成一次摘要，既保留经验信号，又避免 search tree 被过多元认知文本污染。对 API-based setting，这个折中是合理的。

backpropagation 使用标准的 visit/value 更新思路。论文给出的更新公式是： $V (s_{i}) \leftarrow \frac{V ( s _{i} ) ( N ( s _{i} ) - 1 ) + r}{N ( s _{i} )}$ $N (s_{i}) \leftarrow N (s_{i}) + 1$ 它的作用是把 terminal reward 向祖先节点传播，使未来 selection 更偏向历史上通往成功的中间状态。这个设计的意义在于，agent 并不是“记住某条完整成功答案”，而是学习哪些 partial context 更值得继续探索。

值得注意的是，backpropagation 更新的是“节点经验价值”，而不是模型参数。也就是说，LATS 的学习发生在单次 test-time search 过程内部，而非跨样本训练阶段。它更接近 classical planning 中的 online improvement：同一个问题里，系统会逐步形成对若干 partial states 的偏好；换一个新问题，又从头开始搜索。这个性质解释了为什么 LATS 很适合零训练预算场景，但也意味着它的收益受每题可分配调用预算强烈影响。

3.5 直觉解释：为什么 LATS 比线性 ReAct/Reflexion 更稳

这篇论文最重要的直觉不是“用上了 MCTS”本身，而是 LM agent 失败往往发生在中间决策点，而不是最终答案点。线性 ReAct 一旦在某个中间 observation 后做错决策，后续整条轨迹就被错误状态污染；Reflexion 虽然能在 trial 之间反思，但仍然一次只走一条轨迹。LATS 把“在关键拐点处分叉尝试多个后继状态”和“用环境反馈重估这些状态”结合起来，因此更像在做 online branch-and-repair，而不是离线事后总结。如果进一步拆解其有效性来源，大致有三层。第一层是 branching：允许多个备选下一步共存，避免单点错误直接锁死整条轨迹。

第二层是 state valuation：并不是所有分支都值得继续花预算，需要一个能读懂上下文的价值近似器来做粗筛。第三层是 experience reuse：失败后不是简单丢弃，而是通过 reflection 把失败压缩成可复用约束。很多 prior agent 方法只具备其中一层，而 LATS 的贡献是把三层放到同一循环里协同工作。这也解释了为什么论文会在 programming 上得到最显著收益。程序执行反馈最精确、最结构化，中间状态好坏也最容易通过测试结果暴露出来，因此“搜索 + 反馈 + 反思”的闭环最完整。

相较之下，WebShop 的反馈更噪声、更延迟，且商品空间巨大，所以 LATS 仍提升明显，但很难像 programming 那样接近饱和性能。换言之，LATS 的效果强弱与环境反馈质量正相关，这也是理解实验结果时的关键方法论线索。

最后，从系统视角看，LATS 可以被理解为一种 test-time compute allocation 策略。它并不改变底层 LM 参数，而是改变“把额外推理预算花在哪里”。同样是多调用几次模型，随机重采样、best-of-k、Reflexion、ToT、RAP、LATS 的区别，本质上都在于预算调度规则不同；LATS 的主张是，最有效的预算分配单位不是整条完整答案，而是带反馈的中间语言状态。

3.6 任务实例化：同一 controller 如何落到三种环境

虽然论文强调统一框架，但它并没有假装三类任务是“完全同构”的。更准确的说法是：LATS 复用了同一个搜索骨架，但让每个任务自定义 action schema、环境执行器、terminal reward 和 reflection prompt。统一的是控制流，不统一的是任务接口。对 HotPotQA，树搜索主要围绕检索决策展开。一个节点通常表示“当前问题 + 已经做过的 search/lookup + 当前读到的 supporting evidence”。这里 branching 的价值在于并行保留多个事实链假设，例如先搜人物、先搜地点、或先搜事件别名。因为 HotPotQA 的错误常来自早期实体歧义，所以能否在前几步同时保留多个检索方向，比最后一步答案表述更关键。

对 programming，节点更像“带测试反馈的候选程序版本库”。每次 expansion 并不是加一个小动作，而是生成一份新代码；环境执行器运行 tests 后，把失败 case 和错误信息当作 observation 回流。此时 tree search 更接近 patch-search：父子节点共享同一道题目，但子节点带着上一版代码和反馈重新生成。这解释了为什么 reflection 在 programming 中特别自然，因为单元测试日志本身就提供了高密度、可操作的错误定位信号。对 WebShop，节点表示“当前购物会话上下文 + 已访问页面 + 已执行 click/search + 当前商品约束满足情况”。

这里最大的难点是动作空间巨大且 reward 延迟。搜索 controller 的作用不只是挑好动作，还要避免在低价值页面上反复打转。论文结果显示 LATS 在该任务上仍落后 fully fine-tuned policy 的 success rate，说明仅靠 test-time search 虽能改善局部决策，但还不足以完全替代长期训练得到的网页操作先验。

这三个实例共同说明，LATS 的泛化性来自一个较弱但更真实的假设：不同 agent 任务不需要共享同一种技能，只需要共享“可把中间状态序列化成文本，并允许在这些中间状态上比较、回退和继续扩展”的接口。作者正是通过这个较弱假设，把 reasoning、acting、planning 的讨论真正放到了同一个算法对象上。还有一个经常被忽略的 method 细节是 搜索预算与提前停止条件本身就是算法设计的一部分。LATS 并不是无界地扩树，而是在固定 iterations、固定 branching factor、固定 depth limit 下运行，并在找到成功 terminal state 时尽早停止。这意味着它优化的不只是最终正确率，也隐含优化“在有限 LM 调用预算下尽快找到成功轨迹”。从方法论上看，这一点很重要，因为它把 LATS 与“更大算力 brute-force sampling”区分开来。若只是无限加大 sample 数，很多 baseline 也会变强；而 LATS 想证明的是，在相似预算约束下，基于中间状态的选择性扩展比均匀重采样更有效。论文后面的 sample complexity 分析正是在验证这一点：好的 tree policy 不只是多想几次，而是把额外思考集中放在更值得继续的 partial states 上。

3.7 PyTorch-style pseudocode：按任务拆开的真实实现轮廓

下面的 pseudocode 不是抽象复述，而是按 released code 的控制流压缩出来的三种具体实现。

def hotpot_lats_step(root, task, args):
    node = select_node(root)
    expand_node(node, args, task)  # sample Thought/Action pairs from LM
    child_values = evaluate_node(node, args, task)  # LM state scoring
    reward, terminal = rollout(
        max(node.children, key=lambda child: child.value),
        args,
        task,
        idx=0,
        max_depth=4,
    )
    if terminal.reward != 1:
        backpropagate(terminal, reward)
    return terminal

def programming_mcts_step(dataset_item, generator, executor, model, tests):
    root_solution = generator.func_impl(dataset_item["prompt"], model, "simple")
    root = Node(root_solution)
    is_passing, feedback, _ = executor.execute(root.solution, tests)
    if not is_passing:
        root.reflection = generator.self_reflection(root.solution, feedback, model)
        root.test_feedback = feedback
 
    for _ in range(max_iters):
        node = root
        while node.children:
            node = node.best_child()
        for _ in range(expansion_factor):
            child_solution = generator.func_impl(
                func_sig=dataset_item["prompt"],
                model=model,
                strategy="mcts",
                prev_func_impl=node.solution,
                feedback=node.test_feedback,
                self_reflection=node.reflection,
                acc_feedback=[],
                acc_reflection=[],
            )
            child = Node(child_solution, parent=node)
            node.children.append(child)
            internal_ok, internal_feedback, _ = executor.execute(child.solution, tests)
            reward = passed_test_ratio(internal_feedback, tests)
            child.update(reward)
            backpropagate_parents(child, reward)

def webshop_lats_step(root, env, task, args, session_id):
    node = select_node(root)
    expand_node(node, args, task, idx=session_id)  # clone env state, sample click/search/think
    evaluate_node(node, args, task, idx=session_id)
    terminal = rollout(
        max(node.children, key=lambda child: child.value),
        args,
        task,
        idx=session_id,
        max_depth=15,
    )
    backpropagate(terminal, terminal.reward)
    return terminal

3.8 代码映射与 paper-vs-code gap

Code reference: main @ 853d8161 (2024-07-30) — pseudocode and mapping based on this commit

Paper Concept	Source File	Key Class/Function
HotPotQA LATS search loop	`hotpot/lats.py`	`lats_search`, `select_node`, `expand_node`, `rollout`, `evaluate_node`, `backpropagate`
HotPotQA experiment launcher	`hotpot/run.py`, `hotpot/lats.sh`	`run`, `parse_args`
WebShop environment-backed search	`webshop/lats.py`	`webshopEnv`, `lats_search`, `generate_new_states`, `evaluate_node`
WebShop experiment launcher	`webshop/run.py`, `webshop/lats.sh`	`run`, `parse_args`
Programming MCTS over code candidates	`programming/mcts.py`	`Node`, `gather_context_from_tree`, `run_mcts`
Programming benchmark entry	`programming/main.py`	`strategy_factory`, `main`
Programming released LATS scripts	`programming/run_lats_gpt3.sh`, `programming/run_lats_gpt4.sh`	concrete launch parameters
Prompt/value wrappers	`hotpot/hotpotqa.py`, `webshop/webshop.py`, `programming/generators/*`	task-specific prompt construction and LM I/O

论文公式与 released code 实现差异：

论文第 4.2 节声明 $V (s) = λ \cdot L M (s) + (1 - λ) \cdot SC (s)$ ，并在附录给出 HotPotQA 的 $λ = 0.5$ 、Programming/MBPP 的 $λ = 0.8$ 。但 released code 的 hotpot/lats.py:evaluate_node() 与 webshop/lats.py:evaluate_node() 只把 get_values(...) 返回的 LM 分数写入 child.value，没有显式实现 self-consistency 加权；programming/mcts.py 更是直接把内部测试通过比例当成 reward 更新，完全没有对应的 $λ$ 组合。这不是文字层面的省略，而是论文方法与公开代码的真实差异。
论文附录算法写 HotPotQA 的最大深度为 6，但 hotpot/lats.py 在 expand_node() 里用 if node.depth >= 7 截断，rollout() 还额外写死 max_depth=4。这使 released code 的实际搜索深度控制和论文 Appendix D 不完全一致。
README 写 programming 目录运行命令是 sh run_lats.sh，但仓库实际存在的是 run_lats_gpt3.sh 与 run_lats_gpt4.sh。这说明 released repo 的说明文档与脚本名并不完全同步。

4. Experimental Setup (实验设置)

4.1 Datasets used and their scale

HotPotQA：论文使用随机抽取的 100 个问题；原 benchmark 含 113k Wikipedia-based QA pairs，需要跨两个及以上 supporting documents 推理。附录 D.1 明确实验子集大小为 100。
HumanEval：164 个手写 program synthesis 问题，平均每题约 7.7 个 tests；论文说明某些 baseline 用 161 题，而 LATS 用全 164 题。
MBPP：原始 benchmark 为 974 个短 Python 题目；论文实验使用随机选取的 397 题子集。
WebShop：环境包含 1.18M real-world products、12k crowdsourced instructions、5 个大类和 113 个子类。
Game of 24：用于 reasoning-only ablation，论文没有在正文重复给出总样本量，但作为 ToT 系列标准 benchmark 使用。

4.2 Baselines compared

Reasoning / acting prompting baselines：Base LM、CoT、CoT-SC、ReAct、Reflexion。
Search baselines：ToT、RAP，以及适配到 acting setting 的 ToT (ReAct)、RAP (ReAct)。
WebShop RL baselines：IL、IL+RL、Fine-tuning，以及 human expert。

这些 baseline 的选择覆盖了三种对照维度：没有 search 的 prompt engineering；有 search 但 mostly internal reasoning 的 methods；以及在 WebShop 上依赖 imitation / RL 训练的 environment-specific agents。

4.3 Evaluation metrics

HotPotQA：Exact Match (EM)。
HumanEval / MBPP：Pass@1，指最终选出的单个解是否通过真实测试集。
WebShop：Score 与 Success Rate (SR)。Score 是购买结果满足用户属性约束的平均百分比，SR 是完全满足全部条件的比例。
Game of 24：Success Rate。
额外分析：Table 9 / 10 统计 sample complexity、成功时平均 expanded nodes、token consumption。

4.4 Training / inference config

这里需要把“论文报告设置”和“released code 真实脚本参数”分开写，因为两者并不完全一致。

论文报告设置

HotPotQA reasoning / acting：正文与附录给出 $n = 5$ 、 $k = 50$ trajectories；HotPotQA depth limit 为 6；使用 3-shot examples；附录 D.1 给出 value-function mixing 的 $λ = 0.5$ 。
Programming (HumanEval / MBPP)：正文第 5.2 节给出 $k = 8$ iterations、每次 expansion 采样 $n = 5$ 个 solutions；GPT-3.5 情况下 internal tests 数量为 4；附录 D.2 进一步写明 HumanEval 用全 164 题、depth limit 8、GPT-3.5 用 6 个 internal tests、GPT-4 用 4 个 internal tests、 $λ = 0.8$ 。
WebShop：正文第 5.3 节给出 50 条 instructions、 $n = 5$ 、 $k = 30$ 。

Released code 实际脚本参数

hotpot/lats.sh：--backend gpt-3.5-turbo --task_start_index 0 --task_end_index 100 --n_generate_sample 5 --n_evaluate_sample 1 --prompt_sample cot --temperature 1.0 --iterations 30 --log logs/tot_10k.log。但该脚本没有传 --algorithm lats，而 hotpot/run.py 的 parse_args() 把 --algorithm 作为必填 choices 参数；因此脚本按当前版本可能无法直接复现实验。
programming/run_lats_gpt3.sh：--strategy mcts --dataset_path ./benchmarks/humaneval-py.jsonl --model gpt-3.5-turbo --pass_at_k 1 --max_iters 4 --expansion_factor 3 --number_of_tests 4。
programming/run_lats_gpt4.sh：--strategy mcts --dataset_path ./benchmarks/humaneval-py.jsonl --model gpt-4 --pass_at_k 1 --max_iters 8 --number_of_tests 2。
webshop/lats.sh：--backend gpt-3.5-turbo --task_start_index 0 --task_end_index 50 --n_generate_sample 5 --n_evaluate_sample 1 --prompt_sample cot --temperature 1.0 --iterations 30 --log logs/new_run.log。

论文未详细说明 GPU type / GPU count；released code 也主要是 API-based prompting 脚本，没有给出本地训练硬件配置，因此这部分不能编造。

5. Experimental Results (实验结果)

5.1 Main benchmark numbers

Figure 3 解读：Table 2 展示 HotPotQA 的 reasoning-only 版本。LATS (CoT) 达到 0.62 EM，高于 Base LM 0.32、CoT 0.34、CoT-SC 0.38、ToT 0.55、RAP 0.60。这里说明即便没有外部 tool action，仅仅把 CoT 放入 tree search 和 value evaluation 框架里，也能继续提升。

Figure 4 解读：Table 3 对应 HotPotQA 的 acting-based 版本。LATS (ReAct) 达到 0.63 EM，优于 ReAct 0.32、ReAct(best of k) 0.38、Reflexion 0.51、ToT(ReAct) 0.39、RAP(ReAct) 0.54；把 CoT 与 ReAct 结合的 LATS (CoT + ReAct) 进一步提高到 0.71。这张表直接支持作者的核心命题：外部检索工具并不会自动带来更强 planning，关键是怎样在环境反馈上组织 search。

在 HotPotQA acting setting（正文 Table 3）中，LATS (ReAct) 达到 0.63 EM，优于 ReAct 0.32、ReAct(best of k) 0.38、Reflexion 0.51、ToT(ReAct) 0.39、RAP(ReAct) 0.54；把 internal 与 external reasoning 结合的 LATS (CoT + ReAct) 进一步达到 0.71 EM。这说明 external feedback 的价值不是简单把 API 接到 prompt 上，而是需要通过 search 控制去有效利用。

Figure 5 解读：Table 4 说明 programming 是 LATS 最有说服力的场景之一。HumanEval 上，GPT-3.5 配置下 LATS (ReAct) 达到 83.8 Pass@1，显著高于 CoT 46.9、ReAct 56.9、Reflexion 68.1、ToT 54.4、RAP 63.1；GPT-4 配置下，LATS 达到 92.7 Pass@1，高于 Base LM 80.1 和 Reflexion 91.0。由于 programming 可以拿到明确的 test feedback，这组结果直接支持作者关于“environment observation 对 complex reasoning 极其关键”的论断。

论文 Table 5 还报告 MBPP：CoT 54.9、ReAct 67.0、Reflexion 70.0、ToT 65.8、RAP 71.4、LATS (ReAct) 81.1。尽管 MBPP 题目更短、更简单，LATS 仍保持明显领先。

Figure 6 解读：Table 6 显示 WebShop 上 LATS 的 improvement 依旧成立，但没有 programming 那样夸张。LATS (ReAct) 达到 75.9 score / 38.0 SR，优于 ReAct 53.8 / 28.0、ReAct(best of k) 59.1 / 32.0、Reflexion 64.2 / 35.0，以及 IL 59.9 / 29.1、IL+RL 62.4 / 28.7。它在 score 上超过 RL baselines，但 success rate 仍低于 Fine-tuning 的 45.0 和 human expert 的 59.6，说明长程网页决策仍然很难。

正文 Table 7 给出 Game of 24：CoT 0.08、Reflexion 0.12、ToT 0.20、RAP 0.40、LATS (CoT) 0.44。这说明即便完全没有外部环境，作者提出的 LM value + self-consistency 版本仍可在纯 reasoning benchmark 上获益。

5.2 Ablation findings

Figure 7 解读：Table 8 是正文最关键的 component ablation。它把完整 LATS (ReAct) 与去掉 LM heuristic、把 MCTS 换成 DFS、去掉 reflection 的版本放在同一张表里，因此可以直接看出各组件的边际贡献大小。最明显的是 No LM Heuristic 从 0.63 降到 0.37，说明 value evaluation 不是锦上添花，而是主导性能的核心组件。

正文 Table 8 的 HotPotQA ablation 给出几条关键结论：

LATS (No LM Heuristic) 只有 0.37 EM，相比完整 LATS (ReAct) 的 0.63 下跌 0.26，说明 LM value function 是核心组件。
LATS (DFS) 为 0.42，说明简单深搜代替 MCTS 会丢掉大量性能。
LATS (No Reflection) 为 0.58，比完整版本低 0.05，说明 reflection 有帮助，但作用小于 value heuristic 和搜索算法本身。
ToT (ReAct) 0.39、RAP (ReAct) 0.54，表明把 reasoning 搜索算法生硬套到 acting 场景并不够，LATS 的环境反馈整合方式才是关键。

附录 Table 11 进一步分析超参：

Figure 8 解读：Table 11 对探索系数 $w$ 、depth $d$ 、以及 CoT-only 版本做更细的超参分析。结果显示浅层搜索 d=4 会明显掉点，而较高探索权重 w=2.0 和默认深度设置能恢复到 0.63。这说明 LATS 的增益并不只是“多采样”，而是需要足够深的树和合理的 exploration/exploitation balance。

w=0.5 时 HotPotQA 为 0.55，w=2.0 为 0.63，说明更积极探索在这个任务上更有利。
depth d=4 时为 0.58，低于默认 d=7 的 0.63，说明过浅搜索会损失跨多步纠错能力。
LATS (CoT) 为 0.62，与正文 reasoning-only 结果一致，说明内部 reasoning 版本本身就很强。

5.3 Efficiency / cost analysis

Figure 9 解读：Table 9 比较同类 tree-search 方法的 sample complexity 与 token consumption。HotPotQA 上 LATS (n=5, k=50) 取得 0.63，与 ToT(ReAct) 0.49、RAP(ReAct) 0.54 相比更高，同时平均 token consumption 为 173,290，低于 ToT 的 210,215 和 RAP 的 176,500。论文据此主张 LATS 不只是更准，还更 sample-efficient。

Figure 10 解读：Table 10 用不同 k 比较成功时平均 expanded nodes。k=10/30/50 时，LATS 在 HotPotQA 上分别达到 0.44 / 0.52 / 0.61，对应平均节点数 28.42 / 34.12 / 66.65；同设置下 ToT 与 RAP 的准确率更低，而 ToT 的节点数明显更高。这说明更好的 value guidance 可以把“探索哪些状态”这件事做得更省。

5.4 Limitations

论文正文与 impact statement 都承认几个限制。第一，方法严重依赖 inference budget；提升通常来自更系统地消耗更多采样与评估调用，而不是学习出更紧凑的 policy。第二，reflection 在复杂环境里并不总有用，WebShop 上作者明确说 generated reflections 常常很 generic，容易把 agent 卡在 local minima。第三，公开代码与论文描述并不完全对齐，尤其是 value function 的 self-consistency 组合和脚本可复现实验性，这会给 reproduction 带来不确定性。第四，长程自主决策能力增强也可能被滥用于更强的 automated exploration / browsing / coding agent。

5.5 Overall conclusion

这篇论文最重要的结论不是“LATS 在几个 benchmark 上赢了”，而是它证明了一个更一般的命题：当 LM agent 能拿到环境反馈时，search 不应该停留在 reasoning tree 的内部自洽，而应把 observation、value estimation、reflection、backtracking 一起纳入控制回路。 在 HotPotQA、programming、WebShop 三类任务上，LATS 都展示了 consistent gain，说明 reasoning、acting、planning 的统一不是口号，而是可以由状态定义、UCT 选择和 environment-aware value function 共同落地的。

Paper Notes

探索

Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models

Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models

1. Motivation (研究动机)

2. Idea (核心思想)

3. Method (方法)

3.1 Overall framework：把 LM agent 包进 MCTS 控制回路

3.2 Selection 与 UCT：把 exploration / exploitation 变成显式控制

3.3 Expansion / Evaluation / Simulation：把 LM 从单次解码器变成树搜索部件

3.4 Reflection 与 backpropagation：把失败轨迹变成未来搜索上下文

3.5 直觉解释：为什么 LATS 比线性 ReAct/Reflexion 更稳

3.6 任务实例化：同一 controller 如何落到三种环境

3.7 PyTorch-style pseudocode：按任务拆开的真实实现轮廓

3.8 代码映射与 paper-vs-code gap

4. Experimental Setup (实验设置)

4.1 Datasets used and their scale

4.2 Baselines compared

4.3 Evaluation metrics

4.4 Training / inference config

论文报告设置

Released code 实际脚本参数

5. Experimental Results (实验结果)

5.1 Main benchmark numbers

5.2 Ablation findings

5.3 Efficiency / cost analysis

5.4 Limitations

5.5 Overall conclusion

目录