Tree of Thoughts 与 LATS：刻意搜索
单条思维链轨迹没有回溯的余地。ToT（Yao 等人，2023）把推理变成一棵树，每个节点上做自评。LATS（Zhou 等人，2024）在蒙特卡洛树搜索之下统一了 ToT、ReAct 和 Reflexion。Game of 24 从 4%（CoT）涨到 74%（ToT）；LATS 在 HumanEval 上拿到 92.7% 的 pass@1。
类型： Build 语言： Python（标准库） 前置要求： 阶段 14 · 01（Agent 循环）、阶段 14 · 03（Reflexion） 预计时间： ~75 分钟
学习目标
- 把推理框定为搜索：节点是「思考」，边是「展开」，价值是「有多大希望」。
- 用标准库实现一个 ToT 式的 BFS 树搜索，带自评打分。
- 扩展成一个玩具版 LATS MCTS 循环，含 select / expand / simulate / backpropagate。
- 判断搜索什么时候值得那个 token 倍数（Game of 24、代码生成），什么时候单条轨迹就够（简单问答）。
问题背景
思维链是一次线性行走。如果第一步错了，后面每一步都在一个坏前提上干活。在 Game of 24（用四个数字加 + − × ÷ 凑出 24）上，GPT-4 CoT 只有 4% 准确率。模型早早挑错了子表达式，再也回不来。
推理需要的是：提出多个候选、评估它们、挑有希望的、遇到死路就回溯的能力。这就是搜索。Tree of Thoughts 和 LATS 是两个标准表述。
核心概念
Tree of Thoughts（Yao 等人，NeurIPS 2023）
每个节点是一个连贯的中间步骤（「一个思考」）。每个节点可以展开成 K 个子思考。LLM 用一个打分 prompt 给每个节点自评。搜索遍历这棵树 —— BFS、DFS 或 beam。
(root: "find 24 from 4 6 4 1")
/ | \
("6 - 4 = 2") ("4 + 1 = 5") ("4 * 6 = 24") <- Score: HIGH
/ \ | |
... ... ... finish自评是承重部件。论文给出三种变体：sure / likely / impossible 分类、1..10 数值打分、以及候选间投票。在 Game of 24 上这三种都大幅打败 CoT（GPT-4 从 4% -> 74%）。
LATS（Zhou 等人，ICML 2024）
LATS 在 MCTS 之下统一了 ToT、ReAct 和 Reflexion。LLM 扮演三个角色：
- Policy：提出候选的下一步动作（ReAct 式）。
- Value function：给一条部分轨迹打分（ToT 式自评）。
- Self-reflector：失败时，写一段自然语言反思（Reflexion 式），用它给未来的 rollout 重新播种。
环境反馈（观察）混进价值函数，于是搜索是被真实工具结果引导的，而不只是模型的意见。论文发表时的结果：HumanEval pass@1 用 GPT-4 达 92.7%（SOTA），WebShop 用 GPT-3.5 平均 75.9（逼近基于梯度的微调）。
MCTS，极简版
每次迭代四个阶段：
- Select —— 用 UCT（树的置信上界）从根走到一个叶子。
- Expand —— 通过 policy 生成 K 个子节点。
- Simulate —— 用 policy 从一个子节点做 rollout，用价值函数（或环境奖励）给叶子打分。
- Backpropagate —— 沿路径向上更新访问计数和价值估计。
UCT 公式：Q(s, a) + c * sqrt(ln N(s) / N(s, a))。第一项是利用；第二项是探索。按任务调 c。
成本的现实
搜索让 token 爆炸。ToT 在 Game of 24 上用的 token 是 CoT 的 100–1000 倍。LATS 类似。这不是免费的；把搜索留给：
- 单条轨迹明显不够的任务（Game of 24、复杂代码）。
- 墙钟时间没正确性重要的任务。
- 有一个廉价、可靠价值函数的任务（代码用单元测试、数学用显式目标）。
如果你的任务只有一个正确答案、评估器又有噪声，搜索往往把事情搞得更糟 —— 它会找到一个「评分很高」的错误答案。
2026 年的定位
大多数生产 agent 不跑 LATS。它们跑带工具锚定验证的 ReAct（CRITIC，第 05 课）。搜索出现在一些专门的细分领域：
- 把测试当价值函数跑的编码 agent（HumanEval 式）。
- 探索多条查询路径的深度研究 agent。
- LangGraph 子图里规划密集的工作流。
AlphaEvolve（第 11 课）是 2025 年的极端：在代码上做演化搜索，机器可校验的适应度，前沿级收益（56 年来首次 4x4 矩阵乘法改进）。
tree-of-thoughts动手构建
code/main.py 实现：
- 一个在风格化「挑算术运算」任务上的迷你 ToT BFS。
- 在同一任务上的玩具 LATS MCTS 循环（Select / Expand / Simulate / Backpropagate），带 UCT 选择。
- 一个把符号分数加自评分数组合起来的价值函数。
运行它：
python3 code/main.py轨迹展示 ToT 用 BFS 在每个节点展开三个候选，对比 LATS 通过 MCTS 收敛到最佳 rollout。两者都打印 token 数。
实际使用
LangGraph 把 ToT 式探索作为子图模式提供；LangChain 团队关于 LATS 的博客（2024 年 5 月）是参考教程。LlamaIndex 提供一个 TreeOfThoughts agent。对 2026 年大多数生产 agent 来说，这个模式藏在一个 if task_complexity > threshold: use_search() 的门后 —— 见第 05 课的 evaluator-optimizer 模式。
拿去用
outputs/skill-search-policy.md 在给定任务形态、预算和评估器保真度的情况下，在线性 ReAct、ToT、LATS 和演化搜索之间做选择。
练习
- 用 UCT c=0.1 对比 c=2.0 跑玩具 LATS。轨迹里有什么变化？
- 把价值函数换成更有噪声的打分器（加随机抖动）。MCTS 还能找到最佳叶子吗？它能容忍的最小信噪比是多少？
- 实现 beam-search 版 ToT（每层保留 top-k），和 BFS 对比。在紧张的 token 预算下哪个更好？
- 读 LATS 第 5.1 节。复现 HumanEval 的轨迹数：要多少次 rollout 才能达到报告的 pass@1？
- 读 LATS 论文里关于「LATS 什么时候帮助更小」的讨论。写一段决策规则，把任务形态映射到搜索策略。
关键术语
| 术语 | 大家怎么说 | 它实际是什么 |
|---|---|---|
| Tree of Thoughts | 「分支式 CoT」 | Yao 等人 —— 带自评的思考节点树 |
| LATS | 「给 LLM 用的 MCTS」 | Zhou 等人 —— 在 MCTS 之下统一 ToT + ReAct + Reflexion |
| UCT | 「置信上界」 | 平衡利用（Q）和探索（ln N / n）的选择公式 |
| Value function | 「这个状态有多好」 | prompt 出来的 LLM 分数或环境奖励；喂给 backprop |
| Policy | 「动作提议器」 | ReAct 式生成器；吐出候选的下一步思考/动作 |
| Rollout | 「模拟轨迹」 | 用 policy 从一个节点走到叶子，用价值函数打分 |
| Backpropagate | 「更新祖先」 | 把叶子的奖励沿路径上推，更新访问计数和 Q |
| Search cost | 「token 爆炸」 | Game of 24 上是 CoT 的 100-1000 倍；采用前先算预算 |
延伸阅读
- Yao et al., Tree of Thoughts (arXiv:2305.10601) —— 那篇标准论文
- Zhou et al., LATS (arXiv:2310.04406) —— 带 Reflexion 反馈的 MCTS
- LangGraph overview —— 用于搜索的子图模式
- AlphaEvolve (arXiv:2506.13131) —— 带程序化评估器的演化搜索