Tree of Thought: 不再是 left-to-right 单向思维架构

📝 概念别名

thought: 一个"思考单元", 不是单 token, 也不是一整道解, 而是介于两者之间的中间步骤;
state $s$ : 输入 + 当前已有的 thought 序列 $[z_1, z_2, \dots, z_i]$ ;
thought generator $G(p_\theta, s, k)$ : 在 state $s$ 下产生 $k$ 个候选下一步 thought;
state evaluator $V(p_\theta, S)$ : 给一组 state 打分, 用来指导搜索;

为什么需要 Agent Planning

单纯 CoT 把推理当作"一条链", 一旦中间某一步走错就没机会回头, 也没法在多个候选方案之间挑最好的; 对于需要 explore, lookahead, backtrack 的任务 (数学求解, 写作规划, 字谜填空), 我们需要让 LM 不止一次地, 沿着多条路径思考, 并且在每一步都做出"哪条路更靠谱"的判断;

把这个 idea 形式化, 就得到 Yao 等人的 Tree of Thoughts (ToT) 框架; ToT 把 LM 同时当作 policy (生成 thought) 和 value function (评估 thought) 来用, 在思维树上跑经典的搜索算法; 这套框架是后续所有 agent planning 方案 (Graph of Thoughts, LATS, ReAct + ToT) 的基础;

ToT 的四层架构

整个 framework 可以拆成四个正交的设计维度:

Search (BFS / DFS)            ← 外层循环: 决定 "下一步展开哪个 state?"
  └─ State Evaluator           ← 决定 "这些 state 哪个有前途?"
       └─ Thought Generator    ← 决定 "从这个 state 能生成哪些子 state?"
            └─ Thought Decomposition  ← 定义 "一个 thought 是多大?"

下面逐个拆解;

1. Thought Decomposition: 颗粒度选择

ToT 的第一个关键设计点是 thought 的颗粒度, 这一步决定了整个搜索树的形状; 一个合格的 thought 必须满足:

不能太小 (比如单 token): LM 没办法对它的"前景"做有意义的评估, 评估器会失效;
不能太大 (比如整道完整解): LM 没法在这个粒度下采样出足够多样且 promising 的备选, generator 会失效;

论文里三个任务的颗粒度选择:

任务	thought 是什么	颗粒度
Game of 24	一个中间算术等式 (如 `4 + 9 = 13`)	1-3 步
Creative Writing	一份段落写作 plan (一整段文字)	2 步
5×5 Crosswords	一个 clue 的候选填词 (5-10 字母)	5-10 步

颗粒度的核心约束: 必须让 LM 既能 generate 又能 evaluate;

2. Thought Generator: Sample vs Propose

从一个 state $s$ 产生 $k$ 个候选下一步, 有两种策略:

维度	Sample	Propose
调用方式	同一个 CoT prompt 独立调用 $k$ 次	“propose prompt” 调用 1 次, 输出 $k$ 个
候选之间	i.i.d., 互不知道	后生成的能看到前面的, 自然避免重复
适用空间	大, 连续, 内容丰富 (段落, 计划)	小, 离散, 容易重复 (操作, 单词)

Game of 24 为什么用 Propose

输入 4 9 10 13, 合法操作就那么几个; 用 Sample 独立调 8 次的话:

Call #1 → "4 + 9 = 13 (left: 10 13 13)"
Call #2 → "4 + 9 = 13 (left: 10 13 13)"   ← 重复
Call #3 → "10 - 4 = 6 (left: 6 9 13)"
Call #4 → "4 + 9 = 13 (left: 10 13 13)"   ← 又重复

LM 每次都倾向走最高概率那个, budget 被浪费掉; 用 Propose 让 LM 在一个 response 里枚举所有可能, 它写第 2 行时能看到第 1 行, 就会主动避开重复, 覆盖更多操作分支;

Creative Writing 为什么用 Sample

写作 plan 的空间几乎无限, i.i.d. 调用每次自然产生不同结构 (倒叙, 环境描写, 对话推进…); 如果硬塞进一个 Propose, 单次 response 太长, LM 质量会下滑, 而且后几个 plan 容易模仿前面的结构;

口诀: 空间小用 Propose 枚举, 空间大用 Sample 并行;

3. State Evaluator: Value vs Vote

评估器有两种打分策略, 选择不取决于空间大小, 而取决于有没有客观判据:

维度	Value	Vote
机制	对每个 state 独立打分 / 分类 (sure / likely / impossible, 或 1-10)	把 $k$ 个候选一起给 LM, 投票选最好的
适用场景	state 能单独客观判断	绝对分难定, 但相对好坏可比
例子	Game of 24 “剩下 [6, 9, 13] 能不能拼到 24?”	Creative Writing “A 和 B 哪个更连贯?”

为什么 LM heuristic 比 learned RL value 更 sample efficient

传统 search 需要手工或学到的 heuristic; RL value model 要在该任务上收集大量轨迹 + reward 才能训出来; 而 ToT 直接用 LM 当 heuristic:

0 训练样本: 直接 zero/few-shot prompting, 不需要任务特定数据;
预训练知识迁移: LM 已经吸收了海量世界知识, 可以直接用在新任务的评估上;
可解释: LM 给分时会顺带给推理过程;
通用: 一套机制跨任务, 不需要每个任务重新训一个 value head;

注意论文的 framing 不是说 LM 一定比专用 RL model 更准, 而是说在 sample efficiency 和 generality 两个维度上完胜;

4. Search: BFS vs DFS

最外层用经典搜索算法调度展开顺序; 选择取决于树的形状和是否需要回溯:

Search	适用场景	论文任务
BFS	树浅 + 分支可控, 每层保留 top- $b$ 个 state	Game of 24 ( $b=5$ ), Creative Writing ( $b=1$ )
DFS	树深 + 需要回溯, 沿一条路深入, 遇到 impossible state 就回退	5×5 Crosswords

伪代码骨架

# BFS
frontier = [root]
for step in range(max_depth):
    candidates = []
    for state in frontier:
        children = generator(state, k)   # Sample 或 Propose
        candidates.extend(children)
    scores = evaluator(candidates)       # Value 或 Vote
    frontier = top_b(candidates, scores)

# DFS
def dfs(state):
    if is_goal(state): return state
    children = generator(state, k)       # Sample 或 Propose
    scores = evaluator(children)
    for child in sorted_by(scores):
        if scores[child] > threshold:
            result = dfs(child)
            if result: return result
    return None  # backtrack

可以看到 Generator 和 Search 是两个不同层级: Generator 是"在当前节点产生 $k$ 个候选"的局部操作, Search 是"在整棵树上如何调度展开顺序"的全局策略; 互不替代;

三个维度的正交性: 论文实际配置

任务	Search	Generator	Evaluator
Game of 24	BFS ( $b=5$ )	Propose	Value (sure/likely/impossible)
Creative Writing	BFS ( $b=1$ )	Sample ( $k=5$ )	Vote
5×5 Crosswords	DFS	Propose	Value

可以看到 BFS 既配 Sample 也配 Propose; Generator 和 Evaluator 是独立维度, 不是绑定的; 配置在任务开始时一次性选定, 而非 per-node 自适应; 后续工作 (Graph of Thoughts 等) 在探索动态自适应, 但原版 ToT 是 task-level static config;

用二维矩阵重新组织问题分类

                       Generator
                Propose ←─────────→ Sample
                  │                    │
       ┌──────────┴────────┐ ┌────────┴────────┐
       │ 小 + 客观:          │ │ 大 + 客观:        │
Value  │ Game of 24         │ │ (论文未演示)       │
       │ Crosswords         │ │                  │
       └────────────────────┘ └──────────────────┘
       ┌────────────────────┐ ┌──────────────────┐
       │ 小 + 主观:          │ │ 大 + 主观:        │
Vote   │ (论文未演示)         │ │ Creative Writing │
       │                    │ │                  │
       └────────────────────┘ └──────────────────┘

两个维度正交, 论文只演示了对角线上的两个组合, 但四个象限理论上都成立;

与 CoT 的本质区别

	CoT	ToT
推理结构	一条链	一棵树
决策点	沿链单向, 不可回头	每个 state 都可以分叉 + 评估 + 回溯
LM 角色	仅 policy (生成)	policy + value function (生成 + 评估)
错误恢复	中间错了就废	评估器可以剪掉错误分支
计算成本	$O(\text{depth})$	$O(\text{depth} \times k \times b)$

ToT 用更高的 inference cost 换更强的 deliberate reasoning 能力, 这也是它的 tradeoff: 不适合所有任务, 只适合那些单链 CoT 错误率高, 但有清晰评估信号的任务;

[!ToT 主流观点总结]

如果按论文主线浓缩, ToT 的核心观点可以总结为:

复杂推理任务的瓶颈不是单步生成能力, 而是缺少 explore + evaluate + backtrack 的能力;

把 LM 推理建模成"在思维树上做搜索", 用 LM 同时充当 policy 和 value function;

四个正交维度 (Decomposition, Generator, Evaluator, Search) 配合, 根据任务性质选不同组合;

Generator 的选择取决于候选空间大小: 小 → Propose 枚举, 大 → Sample 并行;

Evaluator 的选择取决于有没有客观判据: 有 → Value 独立打分, 无 → Vote 相对比较;

LM 当 heuristic 的核心卖点是 sample efficiency 和 generality, 而非绝对精度;

延伸: LATS 把 MCTS 焊进第 4 层

ToT 把 Search 这一层设计成可插拔接口, 但只实例化了 BFS / DFS, 并在讨论里明说更复杂的搜索 (A*, MCTS) 可以接进来作为未来工作; LATS (Language Agent Tree Search, ICML 2024) 干的第一件事, 就是把 MCTS 插进这个空着的槽; 但如果只把它理解成"换了个更聪明的搜索算法", 会严重低估它 —— LATS 真正的增量在另外两处: 节点的内容和估值的来源;

原论文 Figure 2: LATS 的六个操作 —— Selection (用 UCT 一路选最有前途的叶子), Expansion (从 LM policy 采样 n 个子节点), Evaluation (LM 给 state 打 value), Simulation (沿最优子节点 rollout 到 terminal), Backpropagation (把 reward 沿路径回传更新 Q 值), Reflection (失败时生成语言反思); 红色路径就是 Selection 选出的那一条, Backpropagation 走的正是它的反向;

delta 1: 节点从 thought 升级成 action + 真实 observation

ToT 树上的节点是纯 thought, 从头到尾不碰外部环境, 是在 LM 脑子里推; LATS 把节点扩成了 ReAct 式的 (action, observation) —— 每个节点要真的发出 action, 调工具, 拿回真实 observation; 所以:

ToT: 在想法空间里搜 + 回溯;
LATS: 在真实交互轨迹里搜 + 回溯;

这一层是 ReAct 的贡献, 不是 MCTS 带来的, 也不是 ToT 本来有的;

delta 2: 估值接真实环境反馈, 而非 RAP 的想象 world model

同样用 MCTS 的还有 RAP (Reasoning via Planning), 但 RAP 把 LM 当 world model: 它既让 LM 提 action, 又让 LM 自己预测执行后的下一个 state, 整个搜索跑在 LM 想象出来的环境里, 根本不执行真实工具; 问题就在这 —— observation 是 LM 编的, 容易幻觉, value 不可靠;

LATS 的修正是把想象的 transition 换成真实执行: action 真的发出去, observation 是环境真实返回的; 节点的 value 仍由 LM 自评分给出 ( $V(s) = \lambda \cdot \text{LM}(s) + (1-\lambda) \cdot \text{SC}(s)$ , SC 是 self-consistency 得分), 但它是 conditioned 在真实 observation 上的, 终局还会拿到环境真实的 reward 一起 backprop; grounding 在真实反馈上, 这才是 LATS 区别于 RAP 的本质分界;

这里的 MCTS 和棋类 MCTS 有什么不同

接着上面 ToT 的搜索讨论往下补两个反直觉的点:

(1) action space 无穷, 靠采样而非枚举收成有限子树; 棋类里每个节点的合法走法有限, 可以枚举; 但 LM 的 action 是"任意自然语言字符串", 空间不可枚举; LATS 在 Expansion 阶段不遍历, 而是从 LM 这个策略分布里采样固定 n 个候选, 只给节点生成 n 个 child; 于是分支因子 = n (超参数), 深度被 max steps 限制, 真正展开的那棵树是有限的, 即使背后空间无穷; 关键洞察: LM 在这里同时是策略先验, 采样出来的就是"它觉得合理的动作", 无穷空间被自动剪枝到一个小而有意义的子集 —— 没有这个先验, 在无穷空间里搜索没有意义; (注意: 让空间有限的是"采样 n 个"这个动作, 不是工具词表 —— 哪怕给一个能输入任意字符串的搜索框, query 空间仍然无穷;)

(2) simulation 用 LM policy, 不是均匀随机 rollout; 经典棋类 MCTS 靠均匀随机走到终局, 用大数定律对海量随机对局求平均出胜率, 随机便宜所以能海量重复; LATS 的 rollout 每步还是用 LM policy 走 (贵), 不可能跑成千上万次, 所以它更依赖 LM 的 value function 给 state 打分, 而不是靠大量随机样本求平均; 别把 LATS 的 simulation 套上棋类那套随机 rollout + 大数定律, 机制不同;

所以一句话给 LATS 定位:

LATS ≈ ReAct (动作 + 真实观察, grounding) + ToT (thought 树结构) + MCTS (插进 ToT 第 4 层的搜索算法) + Reflexion (失败反思 + external memory);

它的创新不在某个单一新机制, 而在把这四件已有的东西第一次统一进一个带 deliberate search 的框架, 并且把搜索 grounding 在真实环境上; MCTS 负责"怎么搜得聪明", ReAct + 真实环境反馈负责"搜的是真东西", 缺一提升都不成立; 所以你"其他没什么创新"的直觉是对的 —— 这是一篇 unification 论文, 卖点就是组合本身;

[!LATS 主流观点总结]

如果按论文主线浓缩, LATS 的核心观点可以总结为:

ToT 把 Search 设计成可插拔但只给了 BFS / DFS, LATS 把 MCTS 焊进这个槽;

但增量主要不在搜索算法: 节点从纯 thought 升级成 ReAct 式 (action, observation);

估值 conditioned 在真实 observation 上 + 终局拿环境真实 reward, 区别于 RAP 用 LM 当 world model 的想象式搜索, 降幻觉;

无穷 action space 靠"每次采样 n 个候选 (LM 作策略先验)"收成有限子树, 不是靠工具词表;

simulation 用 LM policy 而非均匀随机 rollout, 更依赖 LM value function, 不走大数定律那套;

本质是 ReAct + ToT + MCTS + Reflexion 的统一, 创新在组合与真实环境 grounding, 而非单一新机制;