树搜索与蒙特卡洛

概述

当简单的链式推理不够时，智能体需要更系统的搜索策略。Tree of Thoughts (ToT)、Graph of Thoughts (GoT) 和蒙特卡洛树搜索 (MCTS) 将 LLM 推理从"单链"扩展为"树/图"结构，支持回溯、分支和全局优化。本文深入分析这些方法的原理和实现。

1. 从链到树的演进

1.1 推理结构谱系

graph LR
    IO[Input-Output<br/>直接回答] --> COT[Chain of Thought<br/>线性链]
    COT --> SC[Self-Consistency<br/>多链投票]
    SC --> TOT[Tree of Thoughts<br/>树搜索]
    TOT --> GOT[Graph of Thoughts<br/>图搜索]
    GOT --> MCTS_LLM[MCTS + LLM<br/>蒙特卡洛树搜索]

方法	结构	搜索策略	回溯	评估
IO	点	无	无	无
CoT	链	贪心	无	无
Self-Consistency	多链	采样+投票	无	多数投票
ToT	树	BFS/DFS	有	LLM 评估
GoT	图	拓扑排序	有+合并	LLM 评估
MCTS	树	UCB 引导	有	模拟+回传

2. Tree of Thoughts (ToT)

2.1 核心思想

Yao et al. (2023) 提出的 ToT 将推理过程建模为在思维树中的搜索问题：

\[ \text{ToT}: \text{搜索}(\mathcal{T}, V, \pi_{\text{search}}) \]

其中：

$\mathcal{T}$：思维树（每个节点是一个部分解/中间思维）
$V: \text{Node} \rightarrow \mathbb{R}$：价值函数（评估每个思维状态的前景）
$\pi_{\text{search}}$：搜索策略（BFS 或 DFS）

2.2 ToT 的四个核心组件

graph TD
    subgraph ToT 框架
        DECOMP[1. 思维分解<br/>Thought Decomposition]
        GEN[2. 思维生成<br/>Thought Generator]
        EVAL[3. 状态评估<br/>State Evaluator]
        SEARCH[4. 搜索算法<br/>Search Algorithm]
    end

    DECOMP --> GEN
    GEN --> EVAL
    EVAL --> SEARCH
    SEARCH --> |扩展| GEN
    SEARCH --> |回溯| GEN

组件 1：思维分解

将问题分解为中间"思维步骤"。关键设计决策是粒度：

太细（单词级）：搜索空间过大
太粗（段落级）：缺乏回溯点
适中（句子/段落级）：平衡搜索效率和灵活性

组件 2：思维生成

两种策略：

采样 (Sample)：独立采样 $k$ 个思维 $$t_i \sim P_{\text{LLM}}(\cdot \mid s), \quad i = 1, \ldots, k$$

提议 (Propose)：一次性生成多个候选 $$[t_1, t_2, \ldots, t_k] = \text{LLM}(\text{"列出 k 个可能的下一步"} \mid s)$$

组件 3：状态评估

使用 LLM 评估每个思维状态的前景：

打分方式：

\[ V(s) = \text{LLM}(\text{"评估这个部分解的前景 (1-10 分)"} \mid s) \]

投票方式：

\[ V(s) = \frac{1}{K} \sum_{k=1}^{K} \mathbb{1}[\text{LLM}_k(\text{"这个方向有希望吗？"} \mid s) = \text{"是"}] \]

组件 4：搜索算法

BFS（广度优先搜索）：

维护一个大小为 b 的 beam
每一层：
  对 beam 中每个状态生成 k 个候选
  评估所有候选
  保留得分最高的 b 个进入下一层

DFS（深度优先搜索）：

从根节点开始深度探索
如果当前状态评估值低于阈值 → 剪枝回溯
如果达到最大深度 → 回溯
如果找到解 → 返回

2.3 ToT 示例：24 点游戏

任务：用 4 个数字（1, 5, 6, 10）和四则运算得到 24。

思维步骤 1（生成 3 个候选）：
  (a) 10 - 1 = 9  (剩余: 5, 6, 9)  评估: 有希望 ✓
  (b) 1 + 5 = 6   (剩余: 6, 6, 10) 评估: 有希望 ✓
  (c) 6 / 1 = 6   (剩余: 5, 6, 10) 评估: 有希望 ✓

思维步骤 2（从 (a) 扩展）：
  (a1) 5 + 9 = 14  (剩余: 6, 14)  评估: 不太可能 ✗
  (a2) 6 - 5 = 1   (剩余: 1, 9)   评估: 不太可能 ✗
  (a3) 9 - 5 = 4   (剩余: 4, 6)   评估: 4×6=24! ✓✓✓

最终解: (10-1) × (6-5+1) → 不对，回溯...
实际: 10-1=9, 9-5=4, 4×6=24 ✓

2.4 ToT 的效果

任务	CoT 准确率	ToT 准确率	提升
24点游戏	7.3%	74%	+10x
创意写作	基准	+显著改善	-
字谜	16%	60%	+3.75x

3. Graph of Thoughts (GoT)

3.1 从树到图

Besta et al. (2024) 提出的 GoT 将推理从树结构扩展为有向无环图（DAG）：

graph TD
    S[初始状态] --> T1[思维 1]
    S --> T2[思维 2]
    S --> T3[思维 3]
    T1 --> T4[精化 1]
    T2 --> T4
    T2 --> T5[精化 2]
    T3 --> T5
    T4 --> T6[合并+精化]
    T5 --> T6
    T6 --> ANS[最终答案]

关键新增操作：

操作	描述	ToT中有?
生成 (Generate)	生成新的思维节点	有
评估 (Evaluate)	评估节点质量	有
聚合 (Aggregate)	合并多个思维为一个	无
精化 (Refine)	基于反馈改进思维	无
回溯 (Backtrack)	回到之前的节点	有

3.2 GoT 的优势

信息合并：不同推理分支的信息可以合并
迭代精化：节点可以被多次改进
更灵活的控制流：不限于树结构

4. 蒙特卡洛树搜索 (MCTS) for LLM

4.1 经典 MCTS

MCTS 在 AlphaGo 中大放异彩，其核心是 UCB1 公式：

\[ UCB1(j) = \bar{X}_j + C \sqrt{\frac{\ln n}{n_j}} \]

其中：

$\bar{X}_j$：节点 $j$ 的平均奖励（利用项）
$C \sqrt{\frac{\ln n}{n_j}}$：探索奖励（探索项）
$n$：父节点的总访问次数
$n_j$：节点 $j$ 的访问次数
$C$：探索常数，控制探索-利用平衡

4.2 MCTS 的四个阶段

graph LR
    SEL[1. 选择<br/>Selection<br/>UCB1 引导] --> EXP[2. 扩展<br/>Expansion<br/>添加新节点]
    EXP --> SIM[3. 模拟<br/>Simulation<br/>随机/启发式]
    SIM --> BP[4. 反向传播<br/>Backpropagation<br/>更新统计量]
    BP --> SEL

选择：从根节点开始，按 UCB1 选择子节点，直到到达叶节点
扩展：为叶节点添加一个或多个子节点
模拟：从新节点开始，模拟到终局（随机走法或快速策略）
反向传播：将模拟结果沿路径回传，更新每个节点的统计量

4.3 MCTS + LLM

将 MCTS 应用于 LLM 推理：

MCTS 组件	棋类游戏	LLM 推理
状态	棋盘局面	部分推理链
动作	落子位置	下一个推理步骤
扩展	生成合法走法	LLM 生成候选思维
模拟	随机对局	LLM 快速补全推理
评估	胜负结果	LLM 评估答案正确性
反向传播	更新胜率	更新节点得分

MCTS-LLM 算法：

function MCTS_LLM(question, n_iterations):
    root = Node(state=question)

    for i in 1..n_iterations:
        # 1. 选择：UCB1 引导
        node = select(root)

        # 2. 扩展：LLM 生成候选思维步骤
        children = llm.generate_thoughts(node.state, k=3)
        node.add_children(children)

        # 3. 模拟：LLM 快速补全到最终答案
        for child in children:
            answer = llm.fast_complete(child.state)
            reward = evaluate(answer, ground_truth)

            # 4. 反向传播
            backpropagate(child, reward)

    # 返回最佳路径
    return best_path(root)

4.4 AlphaGo 的启发

AlphaGo 使用策略网络引导 MCTS 搜索：

\[ a^* = \arg\max_a \left[ Q(s, a) + c_{\text{puct}} \cdot P(s, a) \cdot \frac{\sqrt{N(s)}}{1 + N(s, a)} \right] \]

其中 $P(s, a)$ 是策略网络的先验概率，$Q(s, a)$ 是行动价值。

类比到 LLM：

策略网络 → LLM 的先验概率（哪些推理步骤更可能正确）
价值网络 → LLM 的评估（当前推理状态离正确答案有多远）
MCTS 搜索 → 系统地探索推理空间

5. BFS vs DFS 策略对比

5.1 适用场景分析

策略	优点	缺点	适用场景
BFS	不会错过浅层解，beam search 效率高	内存消耗大，深度受限	解在浅层、需要比较多个方案
DFS	内存高效，能探索深层	可能陷入死胡同	解在深层、搜索空间大
MCTS	探索-利用平衡，渐进最优	需要大量迭代	评估函数不确定、需要全局优化
Best-First	总是扩展最有希望的	启发函数可能误导	有可靠的启发函数

5.2 搜索可视化

graph TD
    subgraph BFS - 广度优先
        R1[根] --> A1[A]
        R1 --> B1[B]
        R1 --> C1[C]
        A1 --> D1[D]
        A1 --> E1[E]
        B1 --> F1[F]
    end

BFS 逐层扩展：根 → A,B,C → D,E,F → ...

DFS 深度探索：根 → A → D → (回溯) → E → (回溯) → B → F → ...

6. 实践考量

6.1 计算成本分析

设每次 LLM 调用成本为 $c$，搜索参数为：

方法	LLM 调用次数	总成本
CoT	1	$c$
Self-Consistency (K=5)	5	$5c$
ToT-BFS (d层, b beam, k候选)	$d \times b \times k + d \times b \times k$ (评估)	$O(dbk) \cdot c$
MCTS (N次迭代)	$N \times (\text{expand} + \text{simulate} + \text{evaluate})$	$O(N) \cdot 3c$

6.2 何时使用树搜索？

值得使用的场景：

问题有明确的评估标准（数学题、代码题）
需要创造性探索（写作、设计）
解空间大但有结构（规划、策略）

不值得使用的场景：

简单的事实查询（直接回答即可）
评估函数不可靠（主观问题）
延迟要求高（交互式应用）

7. 前沿发展

RAP (Reasoning via Planning)：Hao et al. (2023) 将 MCTS 应用于 LLM 推理
Everything of Thoughts (XoT)：统一 CoT、ToT、GoT 的框架
语言智能体树搜索 (LATS)：结合 ReAct 和 MCTS 的智能体搜索
过程奖励模型 (PRM)：为推理的每一步提供细粒度奖励信号

参考文献

Yao, S. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS 2023.
Besta, M. et al. (2024). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. AAAI 2024.
Hao, S. et al. (2023). Reasoning with Language Model is Planning with World Model. EMNLP 2023.
Silver, D. et al. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529, 484-489.
Browne, C. et al. (2012). A Survey of Monte Carlo Tree Search Methods. IEEE TCIAIG, 4(1), 1-43.
Zhou, A. et al. (2023). Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models. arXiv:2310.04406.

方法	LLM 调用次数	总成本
CoT	1	\(c\)
Self-Consistency (K=5)	5	\(5c\)
ToT-BFS (d层, b beam, k候选)	\(d \times b \times k + d \times b \times k\) (评估)	\(O(dbk) \cdot c\)
MCTS (N次迭代)	\(N \times (\text{expand} + \text{simulate} + \text{evaluate})\)	\(O(N) \cdot 3c\)