1.1 CoT 的线性困境#

Chain of Thought 让大模型在给出答案前先展示推理步骤，极大提升了复杂任务的准确率。然而，CoT 本质上是一种左到右的线性生成过程：

核心问题在于：CoT 没有探索和回溯的能力。 一旦模型在某个推理步骤上做出了错误选择，后续所有步骤都会被拖累。

1.2 人类是如何解决问题的#

认知科学研究表明，人类在解决复杂问题时，通常会：

1. 探索多种可能的方案，而不是只考虑一条路径
2. 评估每个方案的可行性，在继续深入前先做判断
3. 在发现死胡同时回溯，转向其他有希望的方向
4. 在多个可行方案中选择最优的，而非随意挑选一个

ToT 正是受此启发，试图让 LLM 模仿这种”深思熟虑”的决策过程。

1.3 论文信息#

1
论文：Tree of Thoughts: Deliberate Problem Solving
2
      with Large Language Models
3
作者：Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran,
4
      Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan
5
机构：Princeton University, Google DeepMind
6
发表：NeurIPS 2023 (Oral)
7
引用：1500+ 次

2.1 从链到树的范式升级#

ToT 将推理过程从线性链条扩展为树状结构。在树中，每个节点代表一个思维状态（Thought），模型可以：

• 分支：从一个状态生成多个候选下一步
• 评估：对每个候选状态打分或判断是否可行
• 搜索：通过 BFS 或 DFS 策略在树中搜索最优路径
• 回溯：在发现某条路径不通时，返回上一层继续探索

2.2 四个关键组件#

每个组件都可以根据任务特点进行定制。好的思维分解应该让每个步骤足够小以便评估，但又足够有意义以避免搜索空间过于庞大。

2.3 Thought 生成策略#

ToT 提供了两种生成候选思维的方式：

策略一：独立采样（i.i.d. Sampling） — 从同一状态独立生成多个思维，每个互不影响。适合创意生成等需要多样性的任务。

策略二：顺序提出（Sequential Propose） — 根据已有的候选依次提出新思维，避免重复。适合有明确约束的任务（如填字游戏）。

2.4 状态评估#

状态评估是 ToT 的关键创新之一：

• 独立评估：模型对每个状态打分（如 1-10 分），选择得分最高的继续探索
• 投票评估：多次 LLM 调用对多个状态投票，得票最多的被选中

1
示例 — Game of 24 的状态评估：
2
State: 1 + 2 = 3, remaining: 3, 4 → Score: 3 (不太可能达到 24)
3
State: 1 × 2 = 2, remaining: 3, 4 → Score: 8 (2 × 3 = 6, 6 × 4 = 24 )

3.1 广度优先搜索（BFS）#

BFS 逐层扩展搜索树，每一层保留最优的 b 个候选：

BFS 适合解的深度有限且每步选择较少的任务，如 Game of 24。

3.2 深度优先搜索（DFS）#

DFS 沿着一条路径深入探索，在遇到死胡同时回溯到上一层。DFS 适合搜索空间大但解可能很深的任务，如填字游戏。

1
def dfs_search(state, max_depth, evaluate, threshold):
2
    if is_solution(state):
3
        return state
4
    if depth(state) >= max_depth:
5
        return None
6

7
    for candidate in generate_thoughts(state):
8
        score = evaluate(candidate)
9
        if score >= threshold:  # 只探索有希望的路径
10
            result = dfs_search(candidate, max_depth, evaluate, threshold)
11
            if result is not None:
12
                return result
13
        # score < threshold → 剪枝
14
    return None  # 回溯

3.3 BFS vs DFS 对比#

4.1 Game of 24#

任务：给定 4 个数字，使用 +、−、×、÷ 使结果等于 24，每个数字只用一次。

1
输入：1, 2, 3, 4 → 输出：(1 + 2 + 3) × 4 = 24
2
输入：4, 5, 6, 7 → 需要仔细搜索才能找到解

ToT 使用 BFS 搜索：每步选两个数字做一次运算，生成 5 个候选，评估后保留最优的继续。

ToT 的准确率是 CoT 的 18 倍以上。这说明 GPT-4 完全具备解决这类问题的能力，只是线性 CoT 无法释放这种能力。

4.2 Creative Writing（创意写作）#

任务：给定约束条件，生成满足约束的创意文本，用另一个 LLM 打分评估。

ToT 的方法：生成 5 个不同开头 → 评估质量 → 选择最优 2-3 个继续展开 → 生成完整短文。

1
任务：以"那天晚上，月光格外明亮"开头，写一个悬疑故事
2
  开头 A: "...李探长站在废弃仓库前..."     → 7.0
3
  开头 B: "...她从未想过，这个约定会..."   → 7.5
4
  开头 C: "...抽屉里的信封在银色光芒下..." → 8.0
5
  开头 D: "...老钟停在三点十七分..."       → 8.5
6
→ 选择 D 继续展开

ToT 生成的文本在人工评估中获得了显著更高的连贯性和创意度评分。

4.3 Mini Crosswords（迷你填字游戏）#

任务：在 5×5 填字游戏中填写单词，满足横向和纵向的交叉约束。

ToT 使用 DFS 策略：选择约束最强的提示词 → 生成候选答案 → 检查兼容性 → 深入或回溯。

5.1 方法演进图谱#

5.2 详细对比表#

5.3 Self-Consistency 的局限#

Self-Consistency 通过多次采样 CoT 并投票选择最一致的答案，但根本局限在于：

• 路径间无交互：每条路径独立采样，无法共享信息
• 无过程评估：只能在最终答案层面投票
• 无法回溯：每条路径一旦生成就无法修改

ToT 解决了这些问题：路径通过树结构关联，中间状态可评估，死胡同可回溯。

6.1 从显式搜索到隐式搜索#

2024 年 9 月，OpenAI 发布 o1 推理模型。ToT 与 o1 之间存在深层联系：

6.2 Test-Time Compute Scaling#

核心洞察：ToT 证明了”搜索式推理”的巨大价值，o1 将这一洞察融入模型本身，通过 RL 让模型自动学会何时搜索、何时回溯。

7.1 Graph of Thoughts（GoT）#

2023 年底，研究者进一步将树结构推广为图结构。GoT 新增了三个关键能力：

• 思维融合：将多个推理路径的结果合并为新的思维节点
• 思维精炼：对已有思维节点进行迭代改进
• 循环连接：允许后期思维回溯影响前期思维

这使得 GoT 特别适合需要迭代优化和全局信息的任务。

7.2 Tree of Thoughts+ 与其他改进#

• ToT+：工程优化版本，支持一次 LLM 调用评估多个候选、自适应分支因子、缓存和并行化
• RAP（Reasoning via Planning）：将推理转化为 MDP，通过蒙特卡洛树搜索寻找最优策略
• Agent 集成：ToT 思想深刻影响了 LLM Agent 框架，在规划、工具选择等环节应用树状搜索

8.1 计算成本#

ToT 的最大局限是计算成本。一次推理可能需要 数十到数百次 LLM 调用：

1
CoT: 1 次 | Self-Consistency (k=40): 40 次 | ToT (BFS, b=5, d=3): ~155 次

8.2 适用范围#

ToT 最适合：多步规划、创意生成、约束满足、复杂决策。对于简单单步任务或搜索空间极其庞大的任务，效果可能有限。

8.3 评估器的可靠性#

ToT 效果高度依赖状态评估器质量。如果评估器将差的路径标记为好的，整个搜索可能被误导。

8.1 核心论文#

• Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al., 2023) — 本文解读的核心论文
• Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (Wei et al., 2022) — CoT 基础
• Self-Consistency Improves Chain of Thought Reasoning in Language Models (Wang et al., 2022) — 多路径投票
• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., 2023) — 从树到图

8.2 相关工作#

• Reasoning via Planning in Large Language Models (Hao et al., 2023) — RAP，LLM 作为世界模型
• Large Language Models are Zero-Shot Reasoners (Kojima et al., 2022) — “Let’s think step by step”
• Reflexion: Language Agents with Verbal Reinforcement Learning (Shinn et al., 2023) — 自我反思与改进

8.3 推理模型#

• Learning to Reason with LLMs — OpenAI o1 (OpenAI, 2024) — o1 推理模型
• DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via RL (DeepSeek Team, 2025) — GRPO 训练推理

8.4 实现资源#

• Tree of Thoughts — 官方实现 — Princeton NLP 官方代码库
• Reasoning in LLMs: A Survey — LLM 推理能力综述