01

60 秒回答模板

Beam Search 是一种在生成任务里保留多个候选路径的近似搜索。它不会像 greedy 每步只选一个最高概率 token，也不会像穷举保留所有路径，而是维护 beam_size 个当前最优序列。实现时先用起始 token 初始化 beams，每个 beam 记录序列、累计 log probability 和是否结束。每一轮对未结束 beam 调模型拿到下一 token 的 log probabilities，扩展 top-k 个 token，生成新的候选；对已经遇到 EOS 的 beam 不再扩展，直接保留。然后把所有候选按累计分数排序，取前 beam_size 个作为下一轮 beams。循环到达到最大长度，或所有 beam 都结束。最后返回分数最高的完整序列，实际系统还常加长度惩罚、重复惩罚和 batch 化。手写题的关键是三个动作：扩展候选、top-k 剪枝、EOS 停止。

考点 候选维护
难度 真实面经题
回答目标 讲清手写实现和边界条件
02

深入解析

01

先说明 Beam Search 的定位

Beam Search 是介于 greedy 和穷举之间的解码策略。greedy 每步只保留一个当前最优选择，容易早期选错；穷举搜索空间指数爆炸。Beam Search 每步保留 beam_size 个高分候选，用有限计算提高找到好序列的概率。

02

候选状态要记录三类信息

每个 beam 至少包含 token 序列、累计 log probability 和 ended 标记。使用 log probability 是为了把每步概率相乘变成相加，避免数值下溢，也方便排序。ended 标记用于处理 EOS 后不再继续扩展。

03

每轮扩展未结束候选

对每个未结束 beam，把当前序列喂给模型，得到下一 token 的 log probabilities。通常只取每个 beam 的 top-k token 参与扩展，避免一次性展开整个词表造成计算和内存浪费。

04

全局排序后剪枝

扩展后会得到 beam_size*k 个候选，再加上已经结束的候选。要按累计分数做全局排序，保留前 beam_size 个，而不是每个旧 beam 各自保留一个。这样才能让高质量路径占据更多 beam 名额。

05

EOS 和最大长度是停止条件

当某条序列生成 EOS 后，应标记 ended 并停止扩展；当所有 beams 都 ended，或生成长度达到 max_len，循环结束。最后可以从 ended 候选中选最好结果，如果没有 ended，就从当前 beams 中选最高分。

06

实际系统会补充分数修正

基础 Beam Search 偏好短句，因为 log probability 累加越长通常越小。实际生成常加入 length penalty、重复惩罚、最小长度、禁止 n-gram 重复和 batch 化缓存。手写题先写清基础流程，再说明这些工程增强即可。

python

最小 Beam Search

def beam_search(next_log_probs, start_id, eos_id, beam_size=3, max_len=20):
    # next_log_probs(tokens) -> list of (token_id, log_prob) for the next step
    beams = [([start_id], 0.0, False)]

    for _ in range(max_len):
        candidates = []
        for tokens, score, ended in beams:
            if ended:
                candidates.append((tokens, score, True))
                continue

            for token_id, log_p in sorted(
                next_log_probs(tokens),
                key=lambda item: item[1],
                reverse=True,
            )[:beam_size]:
                new_tokens = tokens + [token_id]
                candidates.append((
                    new_tokens,
                    score + log_p,
                    token_id == eos_id,
                ))

        candidates.sort(key=lambda item: item[1], reverse=True)
        beams = candidates[:beam_size]

        if all(ended for _, _, ended in beams):
            break

    best_tokens, best_score, _ = max(beams, key=lambda item: item[1])
    return best_tokens, best_score
  • 每轮只扩展未结束 beam，遇到 EOS 的候选直接保留。
  • 扩展后对所有候选做全局排序，再剪到 beam_size。
03

易错点

  • 每一步只保留一个 token，把 Beam Search 写成 greedy。
  • 对每个旧 beam 各保留一个候选，没有做全局 top-k 剪枝。
  • 概率直接相乘，长序列下容易数值下溢。
  • 遇到 EOS 后还继续扩展，生成多余 token。
  • 没有最大长度限制，可能死循环。
  • 忽略长度惩罚，导致结果过度偏向短序列。
  • 把 beam_size 和每个 beam 扩展的 top-k 混为同一个概念，无法解释候选数量。
04

面试官追问

Beam Search 和 greedy search 的区别是什么？

greedy 每步只保留一个最高分 token，Beam Search 保留多个候选路径，能纠正部分早期局部最优，但计算量更高。

为什么用 log probability 累加？

序列概率是各步概率相乘，直接相乘容易下溢；取 log 后变成加法，排序等价且更稳定。

为什么需要长度惩罚？

累计 log probability 通常会偏向短序列。长度惩罚可以让较长但合理的序列不被天然压低。

EOS 候选还要参与排序吗？

要参与。EOS 候选不再扩展，但它可能已经是完整高分答案，应该保留并和其他候选一起比较。