Beam Search是一种启发式的序列搜索算法，专门用于解决自回归模型的序列生成问题。它通过在每一步保留最有希望的”k”个候选路径，在生成质量和计算效率之间取得了极佳的平衡，是机器翻译、摘要生成和早期大模型中最常用的解码算法。
一、为什么叫做”Beam Search”？
这个名字来源于一个非常形象的物理比喻：
- Beam（光束/束）：算法在搜索过程中，每一步都只保留固定数量（k个）的最优候选序列。这些候选序列就像一束束平行的”光束”一样，沿着各自的路径向前延伸。
- Search（搜索）：算法的本质是在所有可能的序列空间中，搜索概率最高的那个序列。
直观理解：想象你在黑暗的森林里找出口，手里拿着k个手电筒。每个手电筒照亮一条可能的路径。每走一步，你都会关掉那些看起来通向死胡同的手电筒，只保留最有希望的k个继续照亮前方。这就是Beam Search的工作方式。
二、核心问题：为什么我们需要Beam Search？
自回归模型生成序列时，面临一个根本性的难题：
词汇表大小通常是几万甚至几十万，生成一个长度为n的序列，可能的组合数是词汇表大小的n次方。这是一个天文数字，不可能穷举所有可能的序列来找到全局最优解。
2.1 贪心搜索的缺陷
最简单的解码方法是贪心搜索（Greedy Search）：每一步只选择概率最高的那个token。但它有一个致命的缺点：局部最优不等于全局最优。
经典反例： 假设我们要生成句子”我正在吃饭”，模型的概率分布如下：
- 第一步：“我”(0.6) > “正在”(0.3) > “吃饭”(0.1)
- 如果选”我”，第二步：“正在”(0.4) > “吃饭”(0.3) > “是”(0.2)
- 如果选”正在”，第二步：“吃饭”(0.9) > …
贪心搜索会选择”我正在…”，总概率0.6×0.4=0.24 但全局最优解是”正在吃饭”，总概率0.3×0.9=0.27
贪心搜索因为第一步选择了局部最优的”我”，错过了全局最优的序列。
2.2 Beam Search的解决方案
Beam Search的核心思想是：不把所有鸡蛋放在一个篮子里。
- 每一步，对当前所有的k个候选序列，分别生成所有可能的下一个token
- 计算所有扩展后序列的总概率
- 只保留总概率最高的k个序列，进入下一步
- 重复这个过程，直到所有序列都生成结束符或达到最大长度
三、Beam Search完整工作流程（带实例）
我们用一个简单的机器翻译例子来演示Beam Search的完整过程，设置束宽k=2。
任务：将英文”I love you”翻译成中文
词汇表：我、爱、你、他、喜欢、
步骤1：初始化
- 初始状态：只有一个空序列""，概率1.0
- 候选列表：[("", 1.0)]
步骤2：第一步生成
对空序列生成第一个token的概率：
- “我”: 0.7
- “他”: 0.2
- “爱”: 0.08
- 其他: 0.02
扩展后得到所有可能的序列：
- (“我”, 0.7), (“他”, 0.2), (“爱”, 0.08), …
保留前2个最优：
- 候选列表：[(“我”, 0.7), (“他”, 0.2)]
步骤3：第二步生成
对每个候选序列分别生成下一个token：
-
对”我”生成：
- “爱”: 0.8
- “喜欢”: 0.15
- 其他: 0.05
- 扩展序列：(“我爱”, 0.7×0.8=0.56), (“我喜欢”, 0.7×0.15=0.105)
-
对”他”生成：
- “爱”: 0.7
- “喜欢”: 0.2
- 其他: 0.1
- 扩展序列：(“他爱”, 0.2×0.7=0.14), (“他喜欢”, 0.2×0.2=0.04)
现在有4个扩展序列，按总概率排序：
- “我爱”: 0.56
- “他爱”: 0.14
- “我喜欢”: 0.105
- “他喜欢”: 0.04
保留前2个最优：
- 候选列表：[(“我爱”, 0.56), (“他爱”, 0.14)]
步骤4：第三步生成
对每个候选序列分别生成下一个token：
-
对”我爱”生成：
- “你”: 0.9
- “他”: 0.08
: 0.02 - 扩展序列：(“我爱你”, 0.56×0.9=0.504), (“我爱他”, 0.56×0.08=0.0448), (“我爱
”, 0.56×0.02=0.0112)
-
对”他爱”生成：
- “你”: 0.8
- “我”: 0.15
: 0.05 - 扩展序列：(“他爱你”, 0.14×0.8=0.112), (“他爱我”, 0.14×0.15=0.021), (“他爱
”, 0.14×0.05=0.007)
现在有6个扩展序列，按总概率排序：
- “我爱你”: 0.504
- “他爱你”: 0.112
- “我爱他”: 0.0448
- “他爱我”: 0.021
- “我爱
”: 0.0112 - “他爱
”: 0.007
保留前2个最优：
- 候选列表：[(“我爱你”, 0.504), (“他爱你”, 0.112)]
步骤5：第四步生成
对每个候选序列生成下一个token，此时模型大概率会输出
- “我爱你
”: 0.504×0.95=0.4788 - “他爱你
”: 0.112×0.9=0.1008
步骤6：最终选择
所有候选序列都已生成结束符，选择概率最高的那个：
- 最终输出：“我爱你”
四、关键参数：束宽（Beam Size）
束宽k是Beam Search最重要的超参数，它直接决定了算法的性能和质量：
| 束宽k | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 1 | 计算最快，内存最小 | 就是贪心搜索，质量最差 | 对速度要求极高的场景 |
| 4-10 | 质量显著提升，计算量适中 | 有少量重复和短句子倾向 | 大多数生成任务的默认值 |
| 20-50 | 质量接近最优，重复减少 | 计算量和内存消耗大幅增加 | 机器翻译、摘要生成等高质量需求 |
| 词汇表大小 | 理论上能找到全局最优 | 计算量爆炸，完全不可行 | 仅存在于理论中 |
经验法则：在大模型中，束宽通常设置为4-8。超过10之后，质量提升会非常缓慢，但计算量会线性增加。
五、Beam Search的优缺点
5.1 优点
- 质量远高于贪心搜索：通过保留多个候选，有效避免了局部最优问题
- 效率远高于穷举搜索：将指数级复杂度降低到线性复杂度O(k×n)
- 生成结果确定性强：相同输入会得到相同输出，适合需要可复现性的场景
- 生成文本连贯性好：倾向于生成语法正确、逻辑通顺的句子
5.2 缺点
- 存在重复生成问题：容易出现”我我我”或”非常非常非常”这样的重复内容
- 倾向于生成短句子：长句子的概率会因为多次乘法而变得很小
- 缺乏多样性：总是生成最可能的结果，缺乏创造性和惊喜感
- 计算量仍然较大：比采样方法慢k倍，不适合实时交互场景
六、与其他解码方法的对比
| 解码方法 | 核心思想 | 生成质量 | 多样性 | 速度 | 确定性 | 代表应用 |
|---|---|---|---|---|---|---|
| 贪心搜索 | 每步选概率最高的token | 差 | 无 | 最快 | 是 | 早期简单模型 |
| Beam Search | 每步保留k个最优候选 | 好 | 低 | 中 | 是 | 机器翻译、T5、BART |
| 温度采样 | 按概率分布随机采样 | 中 | 高 | 快 | 否 | ChatGPT、GPT-4、LLaMA |
| Top-k采样 | 只在概率最高的k个token中采样 | 中 | 高 | 快 | 否 | 大多数现代大模型 |
| Top-p（核）采样 | 只在累积概率达到p的token中采样 | 中 | 高 | 快 | 否 | 所有主流聊天机器人 |
七、常见误区澄清
-
误区：Beam Search是大模型的标准解码方法
- 纠正：现在几乎所有的聊天机器人（ChatGPT、Claude、文心一言等）默认使用的都是Top-p采样，因为它生成的文本更自然、更有多样性。Beam Search主要用于需要高质量确定性输出的场景。
-
误区：束宽越大，生成质量一定越好
- 纠正：当束宽超过一定阈值（通常是10）后，质量提升会非常有限，甚至可能因为引入过多低概率候选而导致质量下降。
-
误区：Beam Search能找到全局最优解
- 纠正：Beam Search是一种启发式算法，它只能找到近似最优解。如果全局最优解在某一步没有进入前k个候选，就会被永远丢弃。
八、总结
Beam Search之所以被称为”束搜索”，是因为它像一束束平行的光束一样，在序列空间中探索最有希望的路径。它通过在每一步保留固定数量的候选，在生成质量和计算效率之间取得了完美的平衡，成为了自然语言处理领域最经典的解码算法之一。
虽然现在采样方法在大模型中占据了主导地位，但Beam Search在机器翻译、代码生成、摘要生成等需要高质量确定性输出的场景中，仍然发挥着不可替代的作用。
需要我为你生成一份纯Python实现的Beam Search代码，可以直接用于自回归文本生成吗？