| Q46 | How does Beam Search improve upon Greedy Search, and what is the role of the beam width parameter
1️⃣ 考察意图
面试官想考察你对解码策略的工程理解深度，而非仅仅背诵概念。这是典型的“工程取舍”题，刁钻点在于：你能否从“搜索空间 vs. 计算成本”的 trade-off 出发，解释 Beam Search 为何比 Greedy 更优，以及 beam width 如何影响质量与多样性。答好了能展示你对序列生成底层机制（如 log-prob 累加、长度归一化）的掌握，以及处理实际推理部署中延迟与质量平衡的硬实力。
2️⃣ 标准答
Beam Search 和 Greedy Search 的核心区别在于搜索策略的广度。Greedy Search 每一步只保留当前概率最高的 token，本质是局部最优的贪心算法；而 Beam Search 维护一个大小为 k（beam width）的候选序列集合，每一步从所有扩展中保留全局 top-k，从而逼近全局最优。
1. Greedy Search 的局限
- 每一步只选 argmax，一旦选错（如“I have a”后选“pen”而非“car”），后续无法纠正。
- 在长序列生成中，早期错误会累积，导致输出质量断崖式下降。
- 实际案例：机器翻译中，Greedy 常产生“流畅但偏离原意”的译文，因为局部最优不等于全局最优。
2. Beam Search 的改进机制
- 维护
k条候选序列，每步对每条序列扩展vocab_size个 token，得到k * vocab_size个候选，再按 log-prob 累加排序，保留 top-k。 - 关键工程细节：log-prob 累加而非概率相乘，避免浮点下溢；同时引入长度归一化（如
score = log_prob / (len^alpha)），防止长序列因累加负值过多被低估。 - 实际落地的坑：当
k较大时，候选序列容易趋同（如翻译“I love you”时，所有候选都以“我爱你”开头），导致输出缺乏多样性。解法是引入“多样性惩罚”（如 Diverse Beam Search），强制候选序列在语义上差异化。
3. Beam Width 的角色与 trade-off
k=1时等价于 Greedy Search。k越大，搜索空间指数级增长（每步计算量约O(k * vocab_size)），质量提升但边际递减。- 经验值：机器翻译中
k=4~8效果最佳；文本摘要中k=2~4足够，因为摘要对流畅性要求更高。 - 过大
k的陷阱：① 计算成本激增，推理延迟可能翻倍；② 引入低概率噪声候选，反而降低 BLEU 分数；③ 输出趋于保守（所有候选都偏向高频短语）。 - 工程取舍：实际部署中，常用
k=4作为默认值，并配合“early stopping”（当所有候选都生成结束符时提前终止）来平衡质量与速度。
4. 与其他解码方法的对比
- Top-k Sampling：从概率最高的
k个 token 中随机采样，增加多样性，但可能牺牲流畅性。 - Top-p (Nucleus) Sampling：动态选择累积概率超过
p的 token 集合，比固定k更灵活。 - Contrastive Search：结合退化惩罚（如 SimCTG），直接优化生成多样性。
- 实际场景：对话生成用 Top-p 更好（需要多样性），翻译/摘要用 Beam Search 更稳（需要准确性）。
3️⃣ 答题模板（30 秒电梯版）
“这个问题我从搜索策略、beam width 的 trade-off、以及实际部署三个层面回答。首先，Greedy Search 是局部最优，Beam Search 通过维护 k 条候选序列逼近全局最优。其次，beam width 越大搜索空间越大，但质量提升边际递减，且过大可能引入噪声和计算瓶颈，机器翻译中 k=4 是常见折中。最后，实际落地要配合长度归一化和 early stopping，避免候选趋同和延迟过高。总结一句：Beam Search 用可控的计算成本换取了显著的质量提升，但需要精细调参。”
4️⃣ 高频追问 & 应对
追问 1：Beam Search 为什么在对话生成中效果不好？你如何改进？
对话生成需要多样性，而 Beam Search 倾向于输出高频、保守的回复，导致“安全但无聊”的结果。改进方法：① 改用 Top-p 或 Top-k Sampling，引入随机性；② 使用 Diverse Beam Search，通过分组惩罚（如每组候选的 n-gram 重叠度）强制差异化；③ 结合温度参数（temperature scaling），在 softmax 前调整概率分布，温度 >1 时分布更平滑，增加低概率 token 被选中的机会。
追问 2：如果 beam width 从 4 增加到 8，推理时间会翻倍吗？为什么？
不会严格翻倍。每步计算量是
O(k * vocab_size)，但实际瓶颈在模型前向传播（计算 logits），而非排序。当 k 增大时，前向传播的 batch size 增大，GPU 并行计算效率提升，所以时间增长是亚线性的。例如，k=4 到 k=8，推理时间可能只增加 30-50%。但 k 继续增大到 16 以上，内存带宽成为瓶颈，时间会接近线性增长。
追问 3：如何评估 Beam Search 的输出质量？除了 BLEU 还有什么指标？
① BLEU/Rouge：衡量 n-gram 重叠，但忽略语义；② BERTScore：基于 embedding 的语义相似度，对同义词更鲁棒；③ 人工评估：流畅性、相关性、多样性（如 Distinct-n 指标）；④ 实际工程中，还会监控“重复率”（如 n-gram 重复比例）和“生成长度分布”，确保输出不坍缩到固定模式。
5️⃣ 避坑 · 常见错误答法
- ❌ “Beam Search 每次保留概率最高的 k 个 token，而不是序列。”→ ✅ 正确说法：保留 k 条完整的候选序列（每个序列包含已生成的所有 token），每步扩展后按序列的累积 log-prob 排序。
- ❌ “beam width 越大越好，因为搜索空间更大。”→ ✅ 正确说法：beam width 过大可能引入噪声、降低多样性，且计算成本激增，需要根据任务（翻译/摘要/对话）和延迟要求做 trade-off。
- ❌ “Beam Search 和 Greedy Search 没有本质区别，只是多保留几个候选。”→ ✅ 正确说法：本质区别是搜索策略从局部最优变为全局近似最优，且 Beam Search 需要处理长度归一化、候选趋同等问题，工程实现更复杂。
6️⃣ 简历呼应
- 如果你有机器翻译项目：从“在 WMT 英中翻译任务中，对比 beam=1/4/8 的 BLEU 分数和推理延迟”切入，展示你对 trade-off 的量化分析能力。
- 如果你只做过文本分类：用“分类任务中的 top-k 预测类比 Beam Search 的候选保留”迁移，强调搜索空间与准确率的平衡。
- 如果你是校招无项目：聚焦“复现论文《Diverse Beam Search》中的分组惩罚机制”，用 PyTorch 实现一个简化版，并分析 k=2/4/8 时的输出多样性变化。
- 《Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models》（AAAI 2018）
- 《The Curious Case of Neural Text Degeneration》（ICLR 2020，分析 Beam Search 的退化问题）
- 《SimCTG: A Contrastive Framework for Neural Text Generation》（ACL 2021，提出 Contrastive Search）
- Hugging Face 官方文档：Generation with Beam Search（含代码示例和超参数调优指南）
- 《Massively Parallel Methods for Deep Learning》（讨论 GPU 上 beam search 的 batch 优化技巧）