Beam Search（束搜索）

3 秒看懂

Beam Search 是一种截断式宽度优先搜索解码算法：在生成序列的每一步只保留得分最高的 k 条候选路径（k 即束宽 beam width），其余剪枝。它是贪心搜索（k=1）与穷举搜索（k=∞）之间的连续折中，是机器翻译、语音识别、LLM 推理解码等场景中最经典的解码策略之一。

3 分钟产业解释

在大语言模型（LLM）的推理部署中，模型输出的 token 概率分布只是”半成品”——真正决定输出质量的，是解码策略。Beam Search 正是这条”最后一公里”上最广泛使用的确定性解码算法。

为什么重要？ 以机器翻译为例，如果用贪心搜索（每步只选概率最高的 token），全局最优序列往往被错过；但如果穷举所有可能序列，计算量指数爆炸。Beam Search 用一条固定宽度的搜索束把指数级空间压缩为多项式级，同时保留足够多的”好苗子”以逼近全局最优。

产业地位演进：

一句话产业定位： Beam Search 不是”过时的老算法”，而是确定性序列生成场景的工业基线，在任何需要”唯一正确答案”的任务中仍是首选。

15 分钟专家深入

算法核心

给定一个自回归语言模型 P(y_t | y_{<t}, x)，Beam Search 维护一个大小为 $k$ 的候选集（beam），在每个时间步：

1. 扩展（Expand）：对每条 beam 中的序列，用模型计算下一个 token 的概率分布；
2. 合并（Merge）：将所有 beam × V（词表大小）个候选拼在一起；
3. 剪枝（Prune）：按累积对数概率排序，只保留 top-k；
4. 终止检查：如果所有 beam 都已生成 <eos> 或达到最大长度，停止。

伪代码（简化）:

beams = [{"tokens": [], "score": 0.0}]

for t in range(max_len):
    all_candidates = []
    for beam in beams:
        if beam.tokens[-1] == :
            all_candidates.append(beam)   # 已结束的直接保留
            continue
        log_probs = model.forward(beam.tokens)  # shape: (V,)
        topk_indices = argtopk(log_probs, k)
        for idx in topk_indices:
            all_candidates.append({
                "tokens": beam.tokens + [idx],
                "score": beam.score + log_probs[idx]
            })
    # 全局 top-k
    beams = sorted(all_candidates, key=lambda c: c.score, reverse=True)[:k]

return beams[0]  # 最优序列

长度归一化（Length Normalization）

原始 Beam Search 存在短序列偏好偏差——更短的序列累积对数概率天然更高（每个 token 贡献负值，越加越小）。业界标准修复方案：

\text{score}(Y) = \frac{\log P(Y)}{|Y|^\alpha}

其中 \alpha \in [0.6, 1.0] 是长度惩罚系数（Wu et al., 2016, Google NMT 论文提出）。\alpha = 0 即无归一化，\alpha = 1 即按长度取均值。

束宽 k 的选取

• k = 1：退化为贪心搜索
• k = 4~10：机器翻译、ASR 常用区间（BLEU/WER 收益在此区间快速饱和）
• k = 20~50：摘要、受限解码等复杂任务可能需要
• k → ∞：退化为穷举 BFS（不实际）

经验值：k 从 1 增到 4 的增益远大于从 4 增到 40 的增益，存在明显的边际递减。

计算复杂度

• 时间复杂度：O(T \times k \times V)，其中 $T$ 为序列长度，$V$ 为词表大小
• 空间复杂度：O(k \times T)（存储候选序列）
• 与贪心搜索相比，计算量约增加 k 倍

技术原理（深入机制 + 关键参数）

与相关搜索策略的关系

                    ┌─────────────────────────────────────┐
                    │         搜索空间视图                   │
                    │                                     │
                    │  完全搜索 (k=∞)                       │
                    │    ╔═══════════════════════╗         │
                    │    ║                       ║         │
                    │    ║   Beam Search (k)     ║         │
                    │    ║    ┌─────────────┐    ║         │
                    │    ║    │             │    ║         │
                    │    ║    │  Greedy     │    ║         │
                    │    ║    │  (k=1)      │    ║         │
                    │    ║    └─────────────┘    ║         │
                    │    ║                       ║         │
                    │    ╚═══════════════════════╝         │
                    │                                     │
                    │  采样 (stochastic): 正交维度           │
                    │  (top-k, nucleus, temperature)       │
                    └─────────────────────────────────────┘

关键区分：Beam Search 是确定性的（给定 k，输出固定），采样是随机性的。 这是两者最根本的区别，也是为什么在需要一致性和可复现性的场景（翻译、ASR）偏好 Beam Search。

核心公式：累积得分

Y^* = \arg\max_{Y = (y_1, ..., y_T)} \sum_{t=1}^{T} \log P(y_t | y_{<t}, x)

Beam Search 是该精确优化问题的近似求解器——当 $k$ 足够大时逼近精确解，但不保证找到全局最优（NP-hard 问题的启发式）。

Beam Search 在 Transformer 自回归解码中的执行细节

时间步 t=3 示意（k=3, V=5）:

Beam 1: [I, love, you]  score=-2.1
Beam 2: [I, love, it]   score=-2.3
Beam 3: [I, like, you]  score=-2.5

模型输出各 beam 的 next-token log_probs:

Beam 1 → { very: -0.5, so: -1.2, too: -1.8, ... }
Beam 2 → { very: -0.3, much: -1.0, a: -2.0, ... }
Beam 3 → { very: -0.7, it: -0.9, this: -2.1, ... }

扩展后 3×5=15 个候选，取 top-3:
  Beam 1 + very → score=-2.1+(-0.5)=-2.6  ← 保留
  Beam 2 + very → score=-2.3+(-0.3)=-2.6  ← 保留
  Beam 3 + it   → score=-2.5+(-0.9)=-3.4  ← 保留
  (其余 12 个被剪枝)

关键变体

技术演进史

技术路线对比（量化表）

注：BLEU 提升范围为基于标准 WMT 翻译基准的典型经验区间，非单点数据 [学术文献综合]。

上下游

上游（解码器依赖什么）                    下游（谁在用 Beam Search）
┌──────────────────────┐           ┌──────────────────────────┐
│ 语言模型              │           │ 机器翻译（Google Translate）│
│  - Transformer decoder│           │ 语音识别（Whisper 等）     │
│  - RNN/LSTM (legacy)  │    ──→    │ 文本摘要                   │
│  - CTC decoder (ASR)  │           │ OCR 后处理                 │
│                      │           │ 代码生成（受限解码）         │
│ 词表设计 (BPE/SentencePiece) │    │ 结构化输出（JSON/SQL）     │
│ Logits / 概率分布      │           │ 蛋白质序列设计             │
└──────────────────────┘           └──────────────────────────┘

关键指标

供需与市场数据

市场定位： Beam Search 本身是开源算法（无专利壁垒），其”市场价值”体现在嵌入其的产品与服务中：

• 机器翻译市场：全球 NMT 市场规模估算在数十亿美元量级 [行业报告估算]，几乎所有主流翻译引擎的解码层均使用 Beam Search 或其变体。
• ASR（自动语音识别）：CTC/Attention-based ASR 的解码阶段广泛使用 Beam Search（如 Whisper 的默认解码模式）。
• LLM 推理服务：在结构化输出、合规摘要等场景，Beam Search + 约束解码是主要方案。推理服务中 Beam Search 的额外计算成本 ≈ k 倍 single-sequence 推理，这直接影响 GPU 算力消耗和成本。

成本敏感点： 大 k 值意味着更多的 KV Cache 开销和计算量。在大模型（如 70B+ 参数）部署中，k 从 1 增到 5 可能使每请求推理成本增加 3~5 倍 [定性估算]。

代表公司与资本映射

投资逻辑

Beam Search 的投资启示

1. Beam Search 不直接创造投资标的——它是公开算法，无护城河。但理解它有助于判断推理基础设施的技术路线。

2. 推理成本视角： 如果一个 AI 应用大量依赖 Beam Search（k>1），其 GPU 算力需求显著高于贪心/采样解码，利好推理芯片和推理优化公司。

3. 确定性解码 vs 随机解码的分化：

   • 企业级/合规场景（翻译、医疗、法律、金融摘要）偏好 Beam Search 等确定性方法 → 推动约束解码引擎需求
   • C 端对话/创意偏好采样 → 推动低延迟随机解码优化

4. Speculative Decoding 可能部分替代 Beam Search： 在延迟敏感场景，投机解码用小模型草稿+大模型验证，可能取代部分 Beam Search 应用（牺牲少量质量换大幅提速）。

常见误读纠偏

❌ 误读 1：“Beam Search 总能找到最优序列”

纠偏： Beam Search 是启发式算法，不保证全局最优。因为每步做局部 top-k 剪枝，可能在早期就剪掉了通向全局最优解的路径。存在大量案例：即使是 k=10 的 Beam Search，输出质量也低于穷举搜索（但穷举不实际）。此外，“最优”取决于评估指标——Beam Search 优化的是 token-level log-prob 之和，这与 BLEU/ROUGE 等句级指标并不完全对齐。

❌ 误读 2：“Beam Search 已经被采样方法淘汰了”

纠偏： 这是混淆了开放式对话生成和确定性序列任务。在机器翻译、语音识别、结构化输出等任务中，Beam Search 仍是事实标准。GPT 类模型用采样是因为对话需要多样性，而非采样”更好”。Google Translate 至今使用 Beam Search 解码。Whisper ASR 的默认解码也是 Beam Search（num_beams=5）。

❌ 误读 3：“增大 beam width k 总是能提升质量”

纠偏： 存在明显的边际递减甚至过拟合效应。k 从 1 到 4 通常有显著提升，但 k 增到 20 以上时，BLEU/WER 增益可能接近零甚至下降（因为长度归一化不完美、或者高 k 导致选择了过于”安全”但不自然的翻译）。实际部署中需在质量和成本间权衡。

❌ 误读 4：“Beam Search 和 Sampling 是同一维度上的两种选择”

纠偏： 它们不是简单的”确定 vs 随机”对立。Beam Search 的核心是搜索（search）——在多步决策空间中做全局优化；Sampling 的核心是随机抽取（sampling）——每步独立采样。它们解决的问题不同：Beam Search 逼近 \arg\max，Sampling 逼近 $P(Y|X)$ 的分布。可以组合使用（如 Stochastic Beam Search / Beam Sampling）。

学习路径

Level 1 · 入门
  ├── 理解贪心搜索 → Beam Search → 穷举搜索的递进关系
  ├── 手动实现一个 k=3 的 Beam Search（词表 < 100）
  └── 推荐阅读：CS224N Lecture (Stanford NLP) 相关内容

Level 2 · 应用
  ├── 使用 Hugging Face Transformers 的 generate() 调参
  │   (num_beams, length_penalty, early_stopping, no_repeat_ngram_size)
  ├── 对比不同 k 值在翻译/摘要任务上的 BLEU/ROUGE
  └── 推荐论文：Wu et al. 2016 "Google's NMT System" (length penalty)

Level 3 · 进阶
  ├── 实现 Diverse Beam Search
  ├── 理解 Beam Search 在 CTC 解码中的特殊处理（prefix beam search）
  ├── 学习 Constrained Beam Search（用于强制输出包含特定 token）
  └── 推荐论文：Vijayakumar et al. 2018 "Diverse Beam Search"

Level 4 · 前沿
  ├── Beam Search 与 Speculative Decoding 的关系与替代
  ├── 在 vLLM / FasterTransformer 中阅读 Beam Search 的 GPU 优化实现
  ├── 非自回归解码（NAT）对 Beam Search 范式的挑战
  └── 推荐论文：Leviathan et al. 2023 "Fast Inference from Transformers
      via Speculative Decoding"

一句话总结

Beam Search 是序列生成解码的”瑞士军刀”——在确定性、可复现性优先的任务（翻译、ASR、结构化输出）中至今不可替代，而在开放式对话中让位于采样方法；理解它是理解 LLM 推理栈解码层的基础。

延伸阅读与来源

1. Lowerre, B. (1976). The HARPY Speech Recognition System. PhD Thesis, CMU. —— Beam Search 最早出处。
2. Wu, Y. et al. (2016). Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation. arXiv:1609.08144. —— 工业级 Beam Search 实践（length penalty 规范化）。
3. Vijayakumar, A. et al. (2018). Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models. AAAI 2018. —— Beam Search 多样性改进。
4. Holtzman, A. et al. (2020). The Curious Case of Neural Text Degeneration. ICLR 2020. —— Nucleus Sampling 提出，对比 Beam Search 的不足。
5. Meister, C. et al. (2020). If Beam Search is the Answer, What was the Question? EMNLP 2020. —— 对 Beam Search 目标函数错配问题的深刻分析。
6. Hugging Face Transformers 文档 — model.generate() 参数说明，Beam Search 实践指南。
7. vLLM / FasterTransformer 源码 — Beam Search 的 GPU 高效实现细节。