算法分析与设计

Appearance

5.5 LLM 推理与搜索策略的同构性 ​

问题情境：LLM 的推理困境 ​

三个奇怪的现象 ​

现象 1：LLM 陷入重复输出

让 GPT-4 解释一个复杂概念：

输入：解释"递归"

输出：
递归是一种编程技巧...
（重复段落 A）
递归是一种编程技巧...
（重复段落 A）
...

困惑：为什么 LLM 会"卡住"在同一个答案？

现象 2：CoT 一步错全错

让 GPT-4 计算数学题：

输入：(123 + 456) × 789

CoT：
123 + 456 = 579 ✓
579 × 789 = 45,711 ✗（应该是 456,231）
后续计算全错...

困惑：为什么早期一步错误会导致全盘失败？

现象 3：ToT 评估依赖

Game of 24：用 4 个数字得到 24。

  • CoT 成功率：4%
  • ToT 成功率：74%

困惑：为什么 ToT 的评估函数质量这么关键？

第一次尝试：贪心解码 ​

小明研究 LLM 的生成机制，发现：每步选择概率最高的 token。

python
def greedy_decode(model, prompt):
    """贪心解码"""
    tokens = []
    for _ in range(max_length):
        logits = model(prompt + tokens)
        next_token = argmax(logits)  # 最高概率
        tokens.append(next_token)
    return tokens

小明意识到：贪心解码就是爬山法——每步选"最优"，但可能困在局部最优。

直观思路：搜索策略的映射 ​

从搜索到 LLM ​

小红做了一个惊人的发现：LLM 推理策略和搜索策略是同构的。

搜索策略LLM 推理核心机制局限性
贪心解码每步最高概率局部最优重复陷阱
CoT线性推理DFS（单路径）一步错全错
ToT多候选探索回溯+剪枝评估依赖
GoT思想聚合A*（全局）启发依赖

为什么这个对应关系重要？ ​

三个理由：

  1. 诊断失败：看到 LLM 重复 → 知道是贪心陷阱 → 用 sampling 解决
  2. 设计改进：搜索策略有成熟改进 → 直接迁移到 LLM
  3. 评估成本：ToT 的额外计算 = 回溯的搜索树规模

规范定义：四对策略映射 ​

1. 贪心解码 = 局部搜索 ​

机制：每步选择最高概率 token。

对应：爬山法——每步选最优邻居。

局限：重复陷阱（类似困在局部山峰）。

改进：Temperature sampling（类似模拟退火）。

python
def temperature_sample(logits, T=1.0):
    """Temperature sampling"""
    probs = softmax(logits / T)
    return sample(probs)

2. CoT = DFS ​

机制：线性展开推理路径，一步一步。

对应：DFS——单路径深度探索，无回溯。

局限：一步错全错（类似 DFS 已选路径无法回退）。

改进：ToT（引入回溯）。

3. ToT = 回溯 + 剪枝 ​

机制：

  • Thought Generation：生成 $k$ 个候选
  • Thought Evaluation：评估每个候选
  • DFS + Backtracking：探索高分，回溯低分

对应：

  • Generation = construct_candidates
  • Evaluation = 剪枝判断
  • DFS = 回溯框架

局限：评估函数质量关键（类似剪枝判断依赖外部验证）。

改进：引入外部验证器（类似 Sudoku 用规则验证）。

4. GoT = A* ​

机制：

  • 思想聚合：多思想合并
  • 反馈循环：迭代改进
  • 全局视角：$f(n) = g(n) + h(n)$ 评估

对应：

  • 聚合 = A* 的路径合并
  • 反馈 = 下界动态更新
  • 全局 = 启发函数指导

局限：启发函数质量关键（类似 A* 需可容许启发）。

案例：Game of 24 的搜索过程 ​

CoT（失败） ​

输入：4, 8, 8, 8

第一步：4 + 8 = 12（错误选择！）
后续：12 + 8 + 8 = 28 ≠ 24
无法回溯 → 失败

对应 DFS：已选路径无法回退。

ToT（成功） ​

输入：4, 8, 8, 8

生成 3 个第一步：
  1. 4 + 8 = 12（剩余 8, 8）→ 评估：6/10
  2. 8 / 8 = 1（剩余 4, 8）→ 评估：2/10（剪枝！）
  3. 8 * 8 = 64（剩余 4, 8）→ 评估：4/10

选择高分（12）：
  探索：12 × (8/8) = 12 ≠ 24
  回溯，尝试：12 + 8 = 20
    探索：20 + 4 = 24 ✓ 成功

对应回溯+剪枝：

  • 评估函数剪掉低分分支
  • 回溯机制允许纠正错误

正确性与局限分析 ​

正确性 ​

关键前提：评估函数/启发函数质量。

  • ToT：评估准确 → 剪枝有效 → 搜索高效
  • GoT：启发可容许 → 保证最优（或近似最优）

局限性转移 ​

搜索局限LLM 局限原因
贪心困局部LLM 卡重复局部最优陷阱
DFS 无回溯CoT 一错全错已选路径固定
剪枝需判断ToT 评估依赖需外部验证
A* 需启发GoT 启发依赖下界质量关键

Self-Correct 论文启示：LLM 无法自我修正（无外部反馈）→ 类似剪枝需要外部验证（Sudoku 规则）。

常见错误诊断 ​

错误 1：ToT 评估不准确 ​

python
# 错误示例：凭直觉评估
def evaluate_wrong(thought):
    return random()  # 随机评分！

后果：剪枝无效 → 搜索效率低。

错误 2：温度调度不当 ​

python
# 错误示例：温度太低
T = 0.01  # 接近贪心

后果：LLM 仍陷入重复。

错误 3：忽视外部验证 ​

python
# 错误示例：只用 LM 自评
def evaluate_only_lm(thought):
    return lm_score(thought)  # 可能不准

后果：Self-Correct 失效 → 无法纠正错误。

练习 ​

基本理解 ​

  1. 概念解释：为什么贪心解码对应爬山法？

  2. 对比分析：CoT 和 DFS 的相似之处是什么？

  3. 直觉验证：为什么 ToT 需要好的评估函数？

方法应用 ​

  1. 策略对比：让 LLM 用 CoT 和 ToT 求解同一问题，对比成功率。

  2. 评估函数设计：为 Sudoku 设计 ToT 的评估函数。

  3. 温度调参：测试不同温度对 LLM 输出的影响。

错误诊断 ​

  1. 诊断失败：给定 LLM 重复输出案例，分析是哪种策略的局限。

  2. 评估错误：分析 ToT 评估不准确导致的后果。

方案比较 ​

  1. CoT vs ToT vs GoT：对比三种策略的效率和成本。

  2. 搜索策略演进：分析从贪心到 GoT 的改进路径。

开放设计 ​

  1. 策略选择 Agent：设计一个 Agent，自动选择推理策略。

  2. 自适应搜索：设计动态调整温度/深度的策略。

  3. 综合应用：用 ToT 风格解决 Sudoku。

思考题 ​

为什么理解搜索策略能帮助理解 LLM 推理？

因为它们是同构的——同一计算思想的不同实例：

  • 局限性完全对应
  • 改进技术可以直接迁移
  • 复杂度评估方法相通

如何设计好的评估函数？

从剪枝经验迁移：

  • 使用外部验证（如规则检查）
  • 给部分信用（如距离目标的差距）
  • 先粗略评估，聚焦后精细

LLM 推理的终极改进方向是什么？

Test-Time Compute：在推理时间分配更多计算，换取更好结果。

  • 对应：分支限界的自适应分配（难问题多探索）
  • 效率：比 Best-of-N 提升 4x

结束语：搜索策略和 LLM 推理是一体两面。理解前者的局限，就是理解后者的边界；掌握前者的改进，就是掌握后者的优化。从 DFS 到 A*，从回溯到模拟退火——我们看到的不是不同的算法，而是同一思想的演进。

参考文献：

  • Yao S, Yu D, Zhao J, et al. Tree of Thoughts[C]//NeurIPS. 2023.
  • Besta M, et al. Graph of Thoughts[C]//AAAI. 2024.
  • Huang J, et al. LLMs Cannot Self-Correct Reasoning[C]//ICLR. 2024.
  • Snell C, et al. Scaling LLM Test-Time Compute[J]. 2024.

新时代的算法课程