跳转至

1. 背景与前置知识

1.1 这是个什么问题？

想象你在玩 24 点：给你 4 个数字 4 9 10 13，要你只用加减乘除算出 24。

如果你的"大脑"只能从左到右一口气写完答案——写完一个 token 就锁死，不能反悔——这件事会变得异常困难。因为你必须在第一个运算符还没写下来时，就预见到后面的路线能不能走通。

这正是当今 LLM 的状态。它们都是自回归的：每一步基于已生成的前缀采下一个 token。GPT-4 在 Game of 24 上只有 4% 成功率就是这个问题的直接结果——它在前 3 个 token 就把自己锁进死胡同的概率高得吓人。

论文里给的数据：60% 的 CoT 样本在第一步就失败了（生成了通向死胡同的"4 + 9 = 13"这类开头）。

更广泛地说，这篇论文要回答：

既然 LLM 这么强，为什么对需要规划、回溯、试错的问题还是这么脆弱？能不能让它从"想一遍就交卷"升级成"想多种可能、自我评估、必要时回头"？

1.2 现有方法为什么不够？

ToT 的"对手"是这几类已有方法。论文里有完整对比（图 1），这里整理：

方法 思路 决策粒度 能回溯吗 能多分支吗
IO (Input-Output Prompting) 直接 prompt → 答案 token ✗ ✗
CoT (Chain-of-Thought) [Wei 2022] 加入中间步骤 一条思维链 ✗ ✗
CoT-SC (Self-Consistency) [Wang 2022] 采样 \(k\) 条链 + 多数投票 \(k\) 条独立链 ✗ ✗（链之间不交流）
Self-Refine [Madaan 2023] 让 LLM 看自己的答案再改 整段答案 ✓（迭代） ✗
Tree of Thoughts (本文) 树状探索，自评估 + BFS/DFS 一个想法（thought） ✓ ✓

关键观察：

  • IO / CoT / CoT-SC 都没有"局部探索"——你在每一步只看到一条延续，错了就完。
  • Self-Refine 有迭代但没分支——它在一条线上反复改，但不会同时跑多条平行路线。
  • 训练好的 RL 方法（如 AlphaGo 的 MCTS）能做树搜索，但需要专门训练的价值网络，不能即插即用到任意问题。

ToT 的位置是：搜索框架 + LLM 自评估，无需训练，靠 prompt 就把 LLM 当成生成器 + 评估器双用。

1.3 你需要的前置知识

阅读这篇论文需要的"工具箱"：

1.3.1 LLM 推理的形式化记号

论文用一套很简洁的符号：

  • \(p_\theta\) ：参数为 \(\theta\) 的预训练 LLM（GPT-4）
  • \(x, y, z, s\) ：小写字母是语言序列（即一段 token）
  • \(S, \cdots\) ：大写字母是序列集合
  • \(p_\theta(y \mid \texttt{prompt}(x)) = \prod_{i=1}^n p_\theta(y[i] \mid \texttt{prompt}(x), y[1..i{-}1])\)

IO Prompting 形式化为：

\[ y \sim p_\theta^{\,IO}(y \mid x) = p_\theta(y \mid \texttt{prompt}_{IO}(x)) \]

CoT 形式化为采样一串 thoughts \(z_1, \dots, z_n\) 然后拿到 \(y\)：

\[ z_i \sim p_\theta^{\,CoT}(z_i \mid x, z_{1\ldots i-1}), \quad y \sim p_\theta^{\,CoT}(y \mid x, z_{1\ldots n}) \]

注意 CoT 里 thought 的"粒度"\(z_i\) 是模糊的——可能是一个词、一句话、一段。这个模糊性正是 ToT 要明确处理的问题。

1.3.2 状态空间搜索（来自 50 年代的认知科学）

Newell, Shaw, Simon (1959) 把人类解题刻画为：

在一棵"问题空间树"中搜索，每个节点是一个部分解（partial solution / state），每条边是一个算子（operator）。

形式上，一个状态 \(s = [x, z_{1..i}]\) 包含输入 \(x\) 和到目前为止的思维序列 \(z_{1..i}\)。在状态 \(s\) 上，我们要回答 4 个问题：

  1. 思维如何分解（thought decomposition）？
  2. 如何从一个状态生成 \(k\) 个候选思维（generator）？
  3. 如何评估这些状态（state evaluator）？
  4. 用哪种搜索算法（BFS / DFS / A* / MCTS）？

ToT 的整个 Section 3 就是逐个回答这 4 个问题。

1.3.3 经典搜索算法（教科书级）

  • BFS（广度优先）：每一层保留所有节点 → 适合浅而广的问题（如 Game of 24，深度 ≤ 3）
  • DFS（深度优先）：一路走到底，碰墙回退 → 适合深而窄的问题（如 Crosswords，需要 5–10 步）
  • 剪枝（pruning）：当评估器认为某个子树没希望，直接砍掉

ToT 用的就是 BFS 和 DFS 这两个最简单的——不是新算法，是经典算法 + LLM 评估器的组合。

1.3.4 双过程理论（System 1 vs System 2）

来自心理学（Kahneman, 2011）：

  • System 1：快、自动、无意识 —— 类比当前 LLM 的 autoregressive 生成
  • System 2：慢、刻意、有意识 —— 类比 ToT 要补上的"deliberate planning"

论文反复用这个隐喻定位 ToT：它要把 LLM 从纯 System 1 升级成 "System 1 生成候选 + System 2 树搜索 + 评估"。

1.4 小结

  • 我们要解决的问题：让 LLM 从"一口气写完"升级到"想多条路 + 自评估 + 回头"
  • 现有方法（IO / CoT / CoT-SC / Self-Refine）都没有同时具备分支 + 评估 + 回溯
  • 我们需要的工具：LLM 概率记号 + Newell-Simon 状态空间搜索 + BFS/DFS + 双过程理论隐喻

💡 个人见解：

观察：ToT 借助的所有"前置知识"在 LLM 圈外都是至少 50 年的老货——状态空间搜索 1959 年，BFS/DFS 1960s，System 1/2 隐喻在认知科学里已经被讨论了几十年。

判断：这正是这篇论文的强项而非弱点。在 LLM 推理研究普遍"造新词"的潮流里，ToT 选择了一个纯粹是封装层创新的路线——它没发明任何新搜索算法，没训练任何新模型，只是把 GPT-4 当"评估器"插进 BFS。一句话："经典 AI + LLM = 还没被开采的金矿"。

延伸：如果你 2023 年读完这篇还没想过用 A*、MCTS、Beam Search 套同样的 LLM 评估器思路——那么 2024 年的 LATS、Reflexion、RAP（与本文同期独立提出 MCTS+LLM）已经把这个金矿挖走了一大半。

下一章 → 方法详解