Beam Search 在序列生成中如何工作？

简化版

Beam Search 每步保留累计分数最高的 B 条前缀，再分别扩展；它比贪心搜索探索更多序列，但仍是近似搜索。分数通常使用对数概率并配长度惩罚，否则短序列会因少乘概率而占优。

详细版

• beam size 增大提升搜索覆盖，也线性增加解码状态与计算。

• 完成序列与未完成前缀的分数、停止上界和长度惩罚必须使用同一规则，否则会过早停止或偏向短序列。

• EOS、最小长度、重复惩罚和词表约束会改变结果。

• 不同 beam 共享编码器输出，但每条保留独立解码状态。

• 搜索更强不保证任务质量更高，模型概率本身可能偏置。

完整版教学

一、Beam Search 在概率树上做受限宽度的最佳优先扩展

自回归序列概率是各步条件概率乘积；转到 log 空间后变为求和，既防下溢也便于累计。

只保留 B 条前缀意味着被剪掉的路径无法恢复，所以 Beam Search 不保证全局最优；B 是质量、延迟和内存的直接旋钮。

每一步实际比较的是所有存活前缀的联合候选，而不是在每条前缀内部各选一个最好 token；这个全局 Top-B 才能让不同前缀公平竞争。

二、底层机制与公式

score(y_1:T)=sum_t log P(y_t|y_<t,x)
normalized=score/LP(T)  # LP 可取 T^alpha，也常见其他定义

三、带数字的推演

第 1 步候选 A/B 的 log 分数为 -0.1/-0.2，beam size 为 1 时会永久丢掉 B；若 A 下一步最佳 log 概率为 -2.0、B 为 -0.1，则两步累计分数分别为 -2.1 和 -0.3，说明被剪掉的 B 原本可能形成更优序列。

B=2 会保留两条，但每步扩展成本约翻倍。

四、方案对比

方案/对象	核心特点	代价或边界
Greedy	每步取最高	最快、易局部最优
Beam	保留 B 条前缀	更稳但延迟/显存高
Sampling	增加多样性	不以最高似然为目标

五、执行流程

编码输入 -> 初始化 beam -> 扩展 B×V 候选 -> 累加 log 分数
-> 取 Top-B/收集 EOS -> 达停止条件 -> 长度归一后选结果

六、边界条件与工程代价

大 beam 有时偏好模型高概率的平庸句，并放大长度偏差；应按 BLEU、WER 或任务成功率调 B，而非只看似然。

批量 beam 的父索引重排必须同步 hidden state、attention cache 和序列，否则会把不同前缀状态串错。

记忆钩子：记住 Beam Search 是“每层扩展、累计打分、只留 B 条”。

七、常见误区与追问

• 误区：Beam Search 一定找到概率最高序列。 有限 beam 会不可逆剪枝。

• 追问：为什么用 log 概率？ 乘积变求和并避免数值下溢。

• 误区：beam 越大效果一定越好。 模型偏置和长度问题可能被放大。

• 追问：为何需要长度惩罚？ 原始 log 概率求和通常偏向短序列。

• 追问：部署调什么？ 联合调 B、最大长度、停止规则与端到端延迟。

八、加强记忆

Beam Search 每层联合扩展存活前缀、累计 log 概率并只保留 B 条，是有限宽度的近似搜索而非全局最优保证。长度惩罚的具体公式、EOS 收集与停止条件必须一致；批量实现还要按父 beam 索引同步重排隐藏状态或缓存。它只改变搜索，不能修复模型分布本身的偏置。