所属模块：
M4 · 序列与 Transformer (Sequences & Transformers)| 专题分类：Seq2Seq 与注意力起源 (Seq2Seq & Attention Origins)| 难度等级：Hard
一、核心一句话结论 (One-Sentence Summary)
beam search 保留 top-k 候选序列逐步扩展；因每步累加对数概率，短序列得分天然更高，需长度归一化校正。
Beam search maintains the top-$k$ most probable sequence hypotheses; because joint log-probability decreases monotonically with length, length normalization is required to prevent favoring short outputs.
二、核心考点要义 (Key Insights)
- 📌 贪心每步取最大，beam search 保留 k 条路径
- 📌 对数概率求和使长序列得分单调更负 → 偏好短输出
- 📌 长度惩罚 α 或长度归一化是必需的后处理
English Insights:
– Beam Search: tracks beam width $B$ hypotheses, expanding $B times V$ candidates and pruning to top $B$ by cumulative log-probability
– Length bias: $sum_{t=1}^T log P(y_t mid y_{<t}) le 0$; each additional token adds a negative term, unfairly penalizing longer sentences
– Length normalization: score is divided by length penalty $text{LP}(Y) = frac{(5 + |Y|)^alpha}{(5 + 1)^alpha}$ (typically $alpha sim 0.6-0.8$)
三、核心数学原理与机理推导 (Mathematical Principles & Derivation)
$$text{score}(y)=sum_{t}log p(y_t|y_{<t});qquad text{normalized}=frac{text{score}}{|y|^{alpha}}, alphaapprox0.6text{–}1.0$$
数学机理：贪心解码每步取概率最大的 token，局部最优但可能错过全局更优的序列。beam search 保留 k 条（beam width）当前得分最高的部分序列，每步把它们各自扩展出 V 个候选、再按累计对数概率排序保留前 k 条，直到遇到结束符。长度偏置的根源：score(y)=Σ{t=1}^{|y|} log p(y_t|y{<t})，其中每项 log p≤0；序列越长，累加的负项越多、总分越负。故在’比较不同长度的候选’时，短序列天然占优——beam search 会系统性地偏好短输出（尤其在概率模型不确定时，早停即得高分）。修正：长度归一化 score/|y|^α，或长度惩罚（如 Google NMT 的 lp(Y)=(5+|Y|)^α/(5+1)^α）。α=1 是完全平均、α=0 是不归一化；实践常取 α≈0.6~0.8（GNMT 用 0.6~0.7），在’避免过短’与’不过度鼓励冗长’间平衡。开放式生成的问题——在翻译（目标较确定）上 beam search 有效；但在对话/故事生成等开放式任务上，beam search 常导致’安全但无聊’的输出（因为高概率序列往往是通用套话），此时采样（top-k/top-p/温度）反而更好——这被称为’beam search curse’。
📖 查看英文严格数学推导 (English Mathematical Derivation)
Mathematical Formulation (Wu et al., Google NMT 2016):
Objective: Approximate $argmax_Y log P(Y mid X) = argmax_Y sum_{t=1}^{|Y|} log P(y_t mid y_{<t}, X)$.
– Greedy Search ($B=1$): Takes $y_t = argmax P(y mid y_{<t})$. Misses globally optimal paths hidden behind low-probability initial tokens.
– Beam Search ($B > 1$): Retains $B$ active candidates $mathcal{H}_t = {Y_1, dots, Y_B}$. Expands each to vocabulary size $V$, ranks $B times V$ extensions by cumulative score, and retains the top $B$.
The Length Bias Defect:
Since $P(y_t) le 1$, $log P(y_t) le 0$. The cumulative sum $sum_{t=1}^T log P(y_t)$ is monotonically decreasing with length $T$. Unnormalized beam search heavily favors short or incomplete sentences (e.g., 3-word fragments) over complete 20-word translations.
Google NMT Length Penalty Normalization:
$text{Score}(Y) = frac{sum_{t=1}^{|Y|} log P(y_t mid y_{<t}, X)}{text{LP}(|Y|)}$, where $text{LP}(|Y|) = frac{(5 + |Y|)^alpha}{(5 + 1)^alpha}$.
When $alpha = 0$, no normalization. When $alpha = 1$, standard average log-probability. Default $alpha = 0.6-0.7$ strikes an optimal balance.
四、工业级落地权衡与工程考量 (Industrial Trade-offs)
深度剖析与工程权衡：① beam search 与’最大后验’的关系——beam search 近似求解 argmax p(y|x)（精确求解需指数搜索），但人类对话的目标不是最大后验（而是多样且合理）；这是’解码目标与任务目标错配’的典型案例。② beam width 的收益递减——k 从 1 增到 5~10 收益明显，再增大收益迅速递减且成本线性增长；同时大 beam 会放大长度偏置与’通用化’倾向。③ 多样性与质量的权衡——工程上用 (a) 采样 + 温度、(b) top-k / top-p（nucleus）、(c) diverse beam search / 分组 beam、(d) 对比解码（对比专家与业余模型的对数概率差）来平衡；LLM 时代默认是 top-p 采样而非 beam search。④ 与 RLHF 的交互——RLHF 后的模型分布被’锐化’（偏向高奖励输出），此时采样 + 温度更可控；beam search 在 RLHF 模型上易产生重复与退化。⑤ 长度归一化与业务目标——若业务偏好简洁输出，可把长度惩罚设强；若偏好完整，则设弱或改为’最小长度约束’。长度控制是产品级生成的重要调参项。⑥ 面试要点——被问’beam search 的问题’，应点出’对数概率求和导致长度偏置‘与’开放式生成上的 beam search curse‘，并给出长度归一化与采样替代方案；只答’beam search 比贪心好’是明显不足。
⚙️ 查看英文落地权衡分析 (English Systems & Trade-offs)
Open-Ended Generation Failure: While Beam Search excels in constrained translation and summarization, it causes repetitive, dull, and generic loops in open-ended creative generation. Modern LLMs use stochastic sampling (Top-$p$ / Top-$k$ / Temperature).
五、常见面试避坑陷阱 (Common Pitfalls & Traps)
- ⚠️ 不加长度归一化直接比较不同长度的候选
- ⚠️ 在开放式生成上默认使用 beam search
English Pitfalls:
– Comparing candidate beam sequences of different lengths without length normalization, resulting in premature generation truncation
– Using Beam Search for creative open-ended text generation, producing repetitive degenerate responses
六、高频深度面试追问与预测 (Follow-Up Questions)
- beam search 为什么在开放式生成上反而更差？
- Why does Beam Search produce degenerate repetitive loops in open-ended language generation?
- α 如何选择？
- How does Top-$p$ (nucleus) sampling differ fundamentally from Beam Search?
七、知识图谱对齐 (Knowledge Graph Anchor)
- 🔗 关联底层卡片：
从 Seq2Seq 到 Bahdanau 注意力：信息瓶颈与加性/乘性对齐(Seq2Seq to Bahdanau Attention: Additive & Dot-Product Alignment) - 🗺️ 知识图谱模块：
大语言模型全景图谱
🔬 算法科学家与机器学习深度考察全量题库 (Science Depth)
本题收录于 TalentMe 算法科学家深度考察真题库 (Science Depth)。全库共 856 道硬核考点，深度覆盖数学统计、经典ML、深度学习、Transformer、大语言模型、多模态、推荐系统与 MLOps。支持 Jev 面经智能匹配、一键离线单文件 HTML 手册导出并直连 Obsidian 本地记忆。