Beam Search（束搜尋）
3 秒看懂
Beam Search 是一種截斷式寬度優先搜尋解碼演算法：在生成序列的每一步只保留得分最高的 k 條候選路徑（k 即束寬 beam width），其餘剪枝。它是貪心搜尋（k=1）與窮舉搜尋（k=∞）之間的連續折中，是機器翻譯、語音識別、LLM 推論解碼等場景中最經典的解碼策略之一。
3 分鐘產業解釋
在大語言模型（LLM）的推論部署中，模型輸出的 token 機率分佈只是”半成品”——真正決定輸出質量的，是解碼策略。Beam Search 正是這條”最後一公里”上最廣泛使用的確定性解碼演算法。
為什麼重要？ 以機器翻譯為例，如果用貪心搜尋（每步只選機率最高的 token），全域性最優序列往往被錯過；但如果窮舉所有可能序列，計算量指數爆炸。Beam Search 用一條固定寬度的搜尋束把指數級空間壓縮為多項式級，同時保留足夠多的”好苗子”以逼近全域性最優。
產業地位演進：
| 時代 | 主要解碼策略 | 典型場景 |
|---|---|---|
| 2014-2017（Seq2Seq/NMT 盛期） | Beam Search 統治 | 機器翻譯、摘要 |
| 2018-2020（預訓練+微調興起） | Beam Search 仍主流，但開放式生成開始引入取樣 | 翻譯、問答（確定性任務） |
| 2020-2023（ChatGPT/Instruct 時代） | 開放對話轉向 nucleus sampling / top-k 取樣；結構化/約束任務仍用 Beam Search | 程式碼生成（受限解碼）、語音識別、翻譯 |
| 2023-至今 | Beam Search 與約束解碼（Constrained Beam Search）、投機解碼（Speculative Decoding）結合，在確定性、合規性要求高的工業場景不可替代 | 醫療文本、合規摘要、ASR 後處理 |
一句話產業定位： Beam Search 不是”過時的老演算法”，而是確定性序列生成場景的工業基線，在任何需要”唯一正確答案”的任務中仍是首選。
15 分鐘專家深入
演算法核心
給定一個自迴歸語言模型 P(y_t | y_{<t}, x)，Beam Search 維護一個大小為 $k$ 的候選集（beam），在每個時間步：
- 擴充套件（Expand）：對每條 beam 中的序列，用模型計算下一個 token 的機率分佈；
- 合併（Merge）：將所有 beam × V（詞表大小）個候選拼在一起；
- 剪枝（Prune）：按累積對數機率排序，只保留 top-k；
- 終止檢查：如果所有 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 個被剪枝)關鍵變體
| 變體 | 核心思想 | 典型應用 |
|---|---|---|
| Diverse Beam Search (Vijayakumar et al., 2018) | 在不同 beam group 間施加多樣性懲罰，避免 beam 間高度重複 | 視覺描述、摘要多候選 |
| Constrained Beam Search | 強制輸出序列包含特定 token/子序列 | 命名實體必須出現、合規關鍵詞 |
| Length-Normalized Beam Search | 對累積 log-prob 做長度歸一化 | 幾乎所有工業場景的標準配置 |
| Beam Sampling (Stochastic Beam Search) | 在 beam 選擇中引入隨機性（Gumbel-Softmax 等） | 解碼多樣性需求 |
| Blockwise Beam Search | 分塊解碼，每塊內部做 beam search | 長文本生成 |
技術演進史
| 年份 | 里程碑 | 意義 |
|---|---|---|
| ~1977 | Beam Search 最早由 Lowerre 提出（Harpy 語音識別系統） | 將搜尋複雜度從指數降到多項式 |
| 1990s | 廣泛應用於統計機器翻譯（SMT）phrase-based 模型 | 成為 SMT 解碼標配 |
| 2014 | Seq2Seq (Sutskever et al.) + Attention (Bahdanau et al.) | Beam Search 進入神經序列生成 |
| 2016 | Google NMT (Wu et al.) 系統性闡述 length penalty | Beam Search 實踐規範確立 |
| 2017 | Transformer (Vaswani et al.) | 自迴歸+Beam Search 成標準範式 |
| 2018 | Diverse Beam Search; 質疑 Beam Search 在對話中多樣性不足 | Beam Search 在開放式生成中的侷限性被正視 |
| 2019-2020 | Nucleus Sampling (Holtzman et al., 2020) 被提出 | 開放式生成轉向取樣 |
| 2022-2024 | Constrained Beam Search + Speculative Decoding 興起 | Beam Search 與新範式融合，在工業合規場景重獲重視 |
技術路線對比（量化表）
| 維度 | Greedy (k=1) | Beam Search (k=N) | Nucleus Sampling (top-p) | Speculative Decoding |
|---|---|---|---|---|
| 確定性 | ✅ 確定 | ✅ 確定 | ❌ 隨機 | ✅/❌ 取決於驗證策略 |
| 搜尋寬度 | 1 | k（典型 4~20） | 1（每步取樣） | 1（驗證批） |
| 最優性逼近 | 差（區域性最優） | 中-好（k 越大越好） | N/A（不追求最優） | 取決於草稿模型 |
| 推論延遲 | 基準 T 步 | T 步 × k 倍計算 | T 步 | T 步 ÷ 加速比 |
| GPU 利用率 | 低（單序列） | 中（k 路並行） | 低-中 | 高（批驗證） |
| 輸出多樣性 | 極低 | 低（beam 間可能高度相似） | 高 | 中 |
| 適用場景 | 對延遲極敏感 | 翻譯、ASR、摘要、結構化生成 | 對話、創意寫作 | 低延遲推論加速 |
| 典型 BLEU 提升（vs greedy） | 基準 | +1~4 BLEU（k=5, 翻譯任務） | 不適用 | N/A |
注：BLEU 提升範圍為基於標準 WMT 翻譯基準的典型經驗區間，非單點資料 [學術文獻綜合]。
上下游
上游（解碼器依賴什麼） 下游（誰在用 Beam Search）
┌──────────────────────┐ ┌──────────────────────────┐
│ 語言模型 │ │ 機器翻譯（Google Translate）│
│ - Transformer decoder│ │ 語音識別（Whisper 等） │
│ - RNN/LSTM (legacy) │ ──→ │ 文本摘要 │
│ - CTC decoder (ASR) │ │ OCR 後處理 │
│ │ │ 程式碼生成（受限解碼） │
│ 詞表設計 (BPE/SentencePiece) │ │ 結構化輸出（JSON/SQL） │
│ Logits / 機率分佈 │ │ 蛋白質序列設計 │
└──────────────────────┘ └──────────────────────────┘關鍵指標
| 指標 | 含義 | 量級參考 |
|---|---|---|
| 束寬 k | 搜尋寬度 | 4~10 常用 |
| Length Penalty α | 長度歸一化係數 | 0.6~1.0 |
| BLEU / ROUGE / WER | 輸出質量（翻譯/摘要/ASR） | Beam vs Greedy 典型提升 1~4 BLEU |
| 推論延遲倍數 | 相比 Greedy 的延遲開銷 | 約 k 倍 |
| n-best 列表多樣性 | 前 n 條候選之間的差異度 | 原始 Beam Search 較低，Diverse Beam 較高 |
| 覆蓋率 (Coverage) | beam 中至少含一條高質量序列的機率 | k≥5 時通常 > 95% [經驗估算] |
供需與市場資料
市場定位： 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 的關係 | 關注點 |
|---|---|---|
| Beam Search 在 Google Translate、Gemma 等產品中核心使用；Google 是 length penalty 規範化的重要推動者 | NMT 解碼效率最佳化 | |
| OpenAI | ChatGPT 推論中 temperature=0 近似貪心；結構化輸出（function calling）場景可能使用約束搜尋 | 開放對話用取樣，結構化場景用確定性解碼 |
| Meta (Fairseq/NLLB) | Fairseq 提供了標準化 Beam Search 實現；NLLB 多語言翻譯大規模應用 | 多語言翻譯解碼 |
| Hugging Face (Transformers) | model.generate() 預設使用 Beam Search，提供 num_beams, length_penalty, num_beam_groups 等引數 | 開源生態標準實現 |
| DeepMind / Google Brain | Diverse Beam Search 論文來源；Constrained Beam Search 在 T5X 中有實現 | 研究前沿變體 |
| NVIDIA (FasterTransformer/vLLM) | Beam Search 的 GPU 高效實現，含 beam-level KV Cache 管理最佳化 | 推論引擎最佳化 |
投資邏輯
Beam Search 的投資啟示
-
Beam Search 不直接創造投資標的——它是公開演算法，無護城河。但理解它有助於判斷推論基礎設施的技術路線。
-
推論成本視角： 如果一個 AI 應用大量依賴 Beam Search（k>1），其 GPU 算力需求顯著高於貪心/取樣解碼，利好推論晶片和推論最佳化公司。
-
確定性解碼 vs 隨機解碼的分化：
- 企業級/合規場景（翻譯、醫療、法律、金融摘要）偏好 Beam Search 等確定性方法 → 推動約束解碼引擎需求
- C 端對話/創意偏好取樣 → 推動低延遲隨機解碼最佳化
-
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 推論棧解碼層的基礎。
延伸閱讀與來源
- Lowerre, B. (1976). The HARPY Speech Recognition System. PhD Thesis, CMU. —— Beam Search 最早出處。
- 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 規範化）。
- Vijayakumar, A. et al. (2018). Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models. AAAI 2018. —— Beam Search 多樣性改進。
- Holtzman, A. et al. (2020). The Curious Case of Neural Text Degeneration. ICLR 2020. —— Nucleus Sampling 提出，對比 Beam Search 的不足。
- Meister, C. et al. (2020). If Beam Search is the Answer, What was the Question? EMNLP 2020. —— 對 Beam Search 目標函式錯配問題的深刻分析。
- Hugging Face Transformers 文件 —
model.generate()引數說明，Beam Search 實踐指南。 - vLLM / FasterTransformer 原始碼 — Beam Search 的 GPU 高效實現細節。