Beam Search：序列解码搜索算法

可视化演示

动态演示Beam Search的核心机制，通过开始/执行/监控/完成四种模式展示关键概念与交互流程。

序列生成困境

选秀导演遇到的第一个难题，是“候选歌单”多到离谱。假设参赛选手只能用 10 万个词库接龙，一句 20 个字的歌词，理论上就有 10 万的 20 次方种组合——这个数字比宇宙中的原子还多。导演不可能让所有组合都唱一遍再打分，只能让选手一个词一个词地唱，每唱完一个词就评估一次，这就是“逐步解码”。

在 Seq2Seq 模型中，解码器正是这样工作的：它拿到编码器压缩好的源句语义向量后，从起始符 <SOS> 出发，每步根据“已经生成的词”预测“下一个词的概率分布”，然后挑词、拼接、继续，直到吐出终止符 <EOS>。这个过程本质上是在巨大的组合空间里做一次搜索，而搜索策略的优劣，直接决定了最终句子的质量。


搜索问题的数学本质可以这样看：假设词表大小为 $V$，目标句子的长度为 $L$，那么候选句子总数是：

回到导演的视角：组合爆炸意味着“全部听完再打分”永远不可能。于是导演们退而求其次，设计各种“边走边看”的搜索策略——有的只看眼前，有的多留几条后路。Beam Search 就是其中最有名的一种“多留后路”策略。

贪心搜索的局限

如果导演是个急性子，他会采用最省事的办法：每轮只让当前得分最高的那位选手继续唱，其他选手全部淘汰。这就是“贪心搜索”——每一步都选择当下概率最大的词，不考虑这个词会把整句带向何方。它快、省内存，但常常酿成“一步错、步步错”的悲剧。

比如翻译 “I love you“ 时，第一个词 ”I“ 的候选分布里 ”我“（0.5）和 ”爱“（0.3）分列前二，贪心会毫不犹豫选 ”我“；但如果某一步模型给 ”的“ 打了较高分，贪心就会脱口而出 ”我爱你的“ 这种别扭的句子，而真正合理的 ”我爱的家” 在早期可能因为某步落后被早早淘汰，再也回不了头——因为被淘汰的路径不会重新进入候选池。


贪心搜索的决策规则可以写成：每一步都直接取概率最大的那个词。

所以贪心导演省了心，却输了质量。聪明的导演开始思考：与其孤注一掷，不如每轮同时保留几位有潜力的选手，让他们各自唱下去，最后再整体比较——这正是下一节 Beam Search 的核心思想。

Beam Search 核心机制

导演终于想通了：把选秀改成“多队晋级赛”。每轮比赛结束后，只保留 K 位表现最好的选手（而不是 1 位），让他们各自带着自己的“歌词前缀”进入下一轮，继续接龙。这个 K 就是束宽（beam width），而整场比赛就是 Beam Search。

具体过程是这样的：假设词表有 $V$ 个词，当前有 K 条存活路径。每走一步，每条路径都要尝试接上词表里的每一个词，于是生成 $K \times V$ 个候选；评委团给所有候选打分排序，只留下分数最高的 K 条进入下一轮。如此反复，直到候选句子都以 <EOS> 结尾，或者达到预设的最大长度。


每一条候选路径的分数，是所有已生成词的对数概率之和。

回到选秀现场：K=3 意味着每轮有 3 位选手同时备战，每人试唱 V 个候选词，但最终只有 3 个名额能留下。这份“广撒网”的从容，让最终获胜的歌词往往比贪心导演选出的更连贯、更自然——因为每条路径都完整唱完后，才由总冠军统一加冕。

分数计算与长度惩罚

导演很快发现一个新问题：选手唱得越长，评委打的累计分就越吃亏。这很好理解——每个词的对数概率都是负数，唱 10 个词的歌手累计 -20 分，唱 6 个词的歌手可能只有 -12 分，可这并不代表短歌词更优秀。如果不做处理，Beam Search 会系统性偏爱短句，机器翻译里就会出现“漏译”。

解决思路也很朴素：像田径比赛按体重分级一样，给分数除以一个与句子长度相关的量，让不同长度的句子站在同一起跑线上。这就是“长度惩罚”（length penalty）。


加入长度惩罚后的评分公式为：

有了长度惩罚，评委的记分牌终于公平了：短小精悍的歌词不会因为词少就占便宜，洋洋洒洒的长句也不会因为词多而被误杀。工程实践里，这一项往往是翻译质量提升的“免费午餐”。

束宽调参的艺术

既然 K 越大，同时考察的选手越多，是不是无脑调大 K 就行？导演会告诉你：舞台是有成本的。每轮要试唱的候选数量是 $K \times V$，K 翻倍，计算量和内存几乎也翻倍。更微妙的是，当 K 增加到一定程度后，生成质量的提升会快速饱和，甚至会引入更多“高分但重复”的套话。

经验法则通常是这样：K=1 时退化为贪心搜索；K=5~10 是大多数翻译、摘要系统默认甜区；K 超过 50 以后，质量曲线几乎走平，而推理延迟让用户无法接受。实际工程中还要结合“最大生成长度”和“长度惩罚”一起调，像调音师一样反复试听。


单步扩展的计算量可以写成：

选秀导演的经验是：先调 K，再调 $\alpha$，最后看具体任务。K 不是越大越好，而是“够用就好”——找到那个质量曲线开始走平、开销还能接受的甜蜜点，就是束宽调参的全部艺术。

应用与实战

这套“多队晋级赛”如今是各大 AI 舞台的标配。机器翻译里，Google 神经翻译系统用 Beam Search 解码，配合长度惩罚显著提升译文流畅度；语音识别中，LAS、Whisper 等模型在声学特征上跑束搜索，把“听到的声音”变成“最可能的文本”；文本摘要和对话生成里，BART、T5 也用束搜索从候选摘要中挑出信息最完整的那一条。


在所有这些任务中，最终结果的选择可以统一写成：在所有走完的候选路径（束）中，挑选归一化分数最高的一条。

从选秀舞台到生产环境，Beam Search 的核心逻辑始终如一：不把鸡蛋放在一个篮子里，也不无限扩大篮子。理解了 K、累计分数、长度惩罚这三板斧，你就掌握了 NLP 解码的核心武器，接下来在 Python 演示中亲手实现一个束搜索解码器，一切都会水到渠成。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""Beam Search 解码演示：在模拟概率表上搜索最优序列"""import mathfrom heapq import nlargest VOCAB = ["我", "爱", "你", "的", "家", "<EOS>"]  def next_probs(prefix):    """模拟解码器：根据已有前缀返回下一个词的 log 概率列表"""    table = {        (): [("我", -0.7), ("爱", -1.2), ("你", -1.8)],        ("我",): [("爱", -0.6), ("的", -1.6), ("<EOS>", -2.4)],        ("爱",): [("你", -0.8), ("的", -1.9), ("<EOS>", -1.5)],        ("你",): [("的", -0.5), ("家", -1.4), ("<EOS>", -2.2)],        ("我", "爱"): [("你", -0.4), ("<EOS>", -2.6)],        ("我", "的"): [("家", -0.9), ("<EOS>", -1.3)],        ("爱", "你"): [("的", -0.7), ("<EOS>", -1.1)],        ("爱", "的"): [("家", -1.0), ("<EOS>", -0.8)],        ("你", "的"): [("家", -0.6), ("<EOS>", -1.5)],        ("你", "家"): [("<EOS>", -0.3)],        ("我", "爱", "你"): [("的", -0.5), ("<EOS>", -1.0)],        ("我", "爱", "你", "的"): [("<EOS>", -0.2)],        ("我", "的", "家"): [("<EOS>", -0.3)],        ("爱", "你", "的"): [("家", -0.4), ("<EOS>", -0.9)],        ("你", "的", "家"): [("<EOS>", -0.4)],    }    return table.get(prefix, [("<EOS>", 0.0)])  def greedy_decode(max_len=6):    """贪心解码：每步只选概率最大的词"""    seq = ()    score = 0.0    for _ in range(max_len):        best = max(next_probs(seq), key=lambda x: x[1])        seq = seq + (best[0],)        score += best[1]        if best[0] == "<EOS>":            break    return score, seq  def beam_search(beam_width=3, max_len=6, alpha=0.0):    """Beam Search 解码：每轮保留 beam_width 条最高分路径"""    beam = [(0.0, ())]  # (累计log概率, 已生成序列)    finished = []    for _ in range(max_len):        candidates = []        for log_prob, seq in beam:            for word, lp in next_probs(seq):                new_seq = seq + (word,)                new_score = log_prob + lp                if word == "<EOS>":                    if alpha > 0:                        new_score = new_score / ((len(new_seq)) ** alpha)                    finished.append((new_score, new_seq))                else:                    candidates.append((new_score, new_seq))        if not candidates:            break        beam = nlargest(beam_width, candidates, key=lambda x: x[0])    finished.sort(reverse=True)    return finished[0] if finished else beam[0]  if __name__ == "__main__":    print("贪心解码:         ", greedy_decode())    for k in [1, 3, 5]:        print("Beam K=%d 无惩罚:  " % k, beam_search(k, alpha=0.0))    print("Beam K=3 alpha=0.6:", beam_search(3, alpha=0.6))

1. table = {...}用字典模拟解码器输出的条件概率分布，键是已生成前缀，值是候选词及其对数概率；真实项目中这里是神经网络预测。
2. beam = [(0.0, ())]束的初始状态：起始符前缀为空，累计分数为 0。
3. for word, lp in next_probs(seq):每条存活路径在词表上扩展出所有候选词，对应文中“每步扩展 K×V 个候选”。
4. new_score = log_prob + lp累计对数概率：连乘转为连加，越长的句子分数越负，这就是长句吃亏的原因。
5. if word == "<EOS>":遇到终止符的路径不再参与下一轮扩展，而是进入 finished 决赛名单。
6. new_score = new_score / ((len(new_seq)) ** alpha)长度惩罚：用长度幂次做除法，公平化长短句之后才计入最终比较。
7. beam = nlargest(beam_width, candidates, key=lambda x: x[0])从所有扩展候选中挑出分数最高的 K 条，这就是“每轮只留 K 位选手”。
8. finished.sort(reverse=True)对完整句子按最终分数排序，取第一名作为整场选秀的总冠军。

常见误区

面试题