1 概览
束搜索是一类用于序列决策与生成任务的近似搜索方法。其核心思想是在每一步扩展候选时，不对所有可能分支做穷举，而是只保留得分最高的若干个候选状态，形成一个“束”（beam）。通过逐步推进并对候选进行裁剪，束搜索在效率与结果质量之间做折中；代价通常是无法严格保证全局最优。
1.1 定义与基本思想
在序列任务中，常见目标是寻找使得整体序列概率（或其对数）最大的输出。若直接穷举，会产生指数级的分支增长。束搜索则采用固定束宽（beam width）K：在第 t 步，只保留当前得分最优的 K 个候选前缀（或状态），并基于它们继续扩展到下一步。
可以将其理解为：从“所有可能的前缀集合”中，反复抽取最值得继续探索的少数者；随着步数增加，束内候选逐渐形成更长的输出前缀，最终从中选出最佳序列。
1.2 与穷举搜索、贪心搜索的关系
- 穷举搜索：不做裁剪，能在给定模型与约束下找到全局最优，但计算成本通常很高。
- 贪心搜索：每一步只选择局部最优的单一路径，相当于束宽 K=1。计算快，但容易陷入局部最优。
- 束搜索：在 K=1 的贪心基础上增加多条备选分支（K>1），以降低错过更优路径的概率；当 K 充分大时，其结果趋近更完整的搜索范围，但仍属于近似。
因此，束搜索可视为“介于贪心与穷举之间”的系统化近似。
1.3 术语：束宽、候选、得分、步长
- 束宽（beam width）：每一步保留的候选数量 K。K 越大，通常探索更充分，但开销也更高。
- 候选：当前已生成的前缀序列或其对应的状态集合，束中的每个候选都代表一种继续扩展的可能性。
- 得分：对候选进行排序的量，常基于概率或对数概率的累计值，并可能附加长度归一化、惩罚项等设计。
- 步长：生成序列的离散位置推进次数，如从第 1 个 token 扩展到第 2 个 token 的过程可视为一步。
2 算法流程
束搜索的流程通常按“初始化—扩展—打分—裁剪—终止”反复进行，直到满足终止条件为止。
2.1 初始化
一般从空序列或起始标记开始。把起始候选加入束集合，初始得分通常设为 0（若使用对数概率累积）或 1（若使用概率累积），并为后续扩展准备候选状态。
2.2 逐步扩展候选
在第 t 步，取出束内每个候选前缀，对其可能的下一步扩展进行枚举或按模型输出进行处理。得到“扩展后的新候选”，其数量通常为 K 乘以上一层可选项数（或在做截断时乘以截断后的候选规模）。
扩展完成后，每个新候选都携带“生成到该步的序列信息”，以便后续对其进行比较。
2.3 得分累积与排序
| 对每个扩展候选计算新的得分。常用做法是对对数概率进行累加：新得分 = 旧得分 + log P(token | 前缀)。随后对所有扩展候选按得分进行排序，为裁剪做准备。 |
|---|
若使用长度归一化或惩罚项，得分计算通常在累加后结合序列长度进行调整，以减少偏置。
2.4 束裁剪（保留Top-k）
从排序后的候选中只保留得分最高的 K 个，作为下一步的束集合。被裁掉的候选即使在更后续可能变得更好，也不会再被探索；这也是束搜索近似性的来源。
2.5 终止条件
常见终止条件包括：
- 达到预设最大长度；
- 束中的所有候选都已经生成结束标记；
- 或者满足提前停止准则（例如束中最高可能得分与次优差距不足以改变最终排序）。
终止后，从束内候选中选取最终得分最优的序列作为输出（若存在结束标记，通常优先考虑已经结束的候选）。
3 关键设计要点
束搜索的效果高度依赖得分函数、长度处理与数值实现。不同任务中，针对偏置与退化行为的修正也很常见。
3.1 得分函数与概率/对数概率
若模型提供的是概率分布，直接用概率相乘会导致数值下溢，因此在实践中常用对数概率累积。对数形式还使得不同步数的比较更方便（配合长度归一化后更稳定）。
此外，得分函数未必只来自“模型概率”。工程上常加入启发式项，例如：
- 对重复 n-gram 的惩罚；
- 对某些非法结构的抑制（如约束束搜索中对违反规则的候选给予极低得分）；
- 对结束过早的候选进行校正。
3.2 长度偏置与长度归一化
如果只使用累计对数概率，较短序列往往更容易获得更高的“平均质量”或更不受惩罚的倾向，导致模型输出偏短。为缓解这一现象，常见做法是长度归一化：把累计得分按长度做缩放，例如除以长度的某种函数，或引入可调的归一化系数。
长度相关的处理需要与任务的期望输出特性匹配：有的任务更偏好简洁，有的任务更偏好展开，归一化系数会影响最终平衡点。
3.3 重复与循环的抑制策略
在生成任务中，模型可能反复输出相同短语，形成重复或“循环”。束搜索由于保留多个候选，也可能把这种局部高概率行为进一步固化。常见抑制策略包括：
- 重复 n-gram 限制：若某候选出现过多重复片段，降低其继续扩展得分；
- 覆盖惩罚/未覆盖惩罚：在摘要、翻译等“覆盖内容”任务中，鼓励关注未被覆盖的信息；
- 去除明显无意义重复：例如过滤掉会导致结构明显退化的候选扩展。
这些策略通常是通过得分或可扩展性约束实现的。
3.4 探索与利用的权衡（束宽选择）
束宽 K 决定了“探索”的强度。K 小则接近贪心，探索不足；K 大则更可能找到更优序列，但计算成本线性或近似线性增加，并且在一些情况下仍可能因得分偏置而忽略多样候选。
实际调参常围绕：
3.5 数值稳定性（如对数域计算）
对数域计算能减少概率连乘带来的数值问题。除此之外，还需注意：
- 对数概率与归一化项的量纲一致；
- 在实现中避免将极小概率转回非对数域导致下溢；
- 裁剪前的比较要使用同一尺度的得分，避免某些项规模过大或过小造成排序失真。
一个常见现象是“得分尺度不一致”，会使排序不再反映真实偏好，从而显著影响输出质量。
4 变体与扩展
束搜索并不是单一公式。为了满足任务需求，研究与工程中提出了多种改造方向。
4.1 约束束搜索（满足特定规则）
约束束搜索在扩展候选时施加额外规则，使候选必须满足某些条件，例如：
- 必须包含指定短语或满足某种结构；
- 禁止某些 token 序列出现；
- 生成必须遵循特定格式或语法模板。
实现方式通常是：对违反约束的候选赋予极低得分或直接不允许其进入下一步束集合，从而在搜索过程中完成约束满足。
4.2 覆盖惩罚与多样性约束
在翻译、摘要或基于注意力机制的任务中，可能出现“反复关注同一部分信息”的现象。覆盖惩罚通过衡量已覆盖内容比例或累计注意力来鼓励候选更均匀地覆盖输入。
多样性约束则旨在避免不同候选过于相似。例如在多样性束搜索中，候选之间通过惩罚共享部分特征（如相同前缀或相同 n-gram）来提升多样性。
4.3 结构化/标注任务中的束搜索
在结构化预测或标注任务中，束搜索可被用于解码序列标签。例如在命名实体识别、序列标注等场景中，束中的每个候选对应部分标签序列，并按模型的局部打分累积与剪枝推进。
此时“步长”往往与位置对齐，得分函数可能结合转移特征或约束状态，从而兼顾局部准确性与全局结构一致性。
4.4 多束与多样性束（diverse beam）
多样性束搜索在常规束搜索之上，引入多个子束（或分组束），并规定它们在生成结果上应尽量不同。常见做法包括：
- 按组分别保留候选；
- 组之间对相似候选施加额外惩罚；
- 或在组内排序前将相似性项纳入得分。
目标是让最终输出在候选集合中更丰富，便于下游选择或提高鲁棒性。
4.5 与其他解码策略的组合（如温度、采样）
束搜索通常是确定性的（给定模型与约束）。但在实践中也会与其他策略结合以增强探索，例如：
这类组合的目的是在保持一定效率的同时，提高输出多样性或更贴合任务目标函数。
5 应用场景
束搜索适用于需要从概率模型中寻找高质量序列输出的任务。其优势往往体现在比贪心搜索更稳健、比穷举搜索更可控。
5.1 自然语言生成与文本解码
在文本生成任务中，束搜索常用于将语言模型的下一个 token 预测转化为完整文本输出。相比贪心，它能减少“某一步选错导致后续无法纠正”的情况。
同时，生成系统往往会引入长度归一化、重复抑制等技巧，以提升可读性与结构完整性。
5.2 机器翻译与序列到序列任务
翻译系统需要在源语言与目标语言的对应关系中寻找最合适的输出序列。束搜索可在保持较高解码速度的同时提升翻译质量。多样性策略也常被用于生成多个候选译文以供人工或后续模型选择。
5.3 语音识别中的序列解码
语音识别通常把音频转换为符号序列（如字/音节/子词）。在解码阶段，束搜索可以结合声学模型与语言模型或使用端到端模型输出分布来推断文本序列。由于识别错误具有连锁效应，束搜索比贪心更能保留备选路径，提升整体准确性。
5.4 其他序列决策问题
除文本与语音外，束搜索还可用于：
- 路径规划中的概率建模与轨迹生成；
- 规则驱动的序列决策（配合约束束搜索）；
- 结构化输出任务的近似求解。
只要问题可表述为“从起点逐步扩展得到一条序列并需要全局打分”，束搜索就具备迁移性。
6 复杂度与性能评估
束搜索的性能主要受束宽与实现方式影响。评估不仅看精度，也看效率与输出特性。
6.1 时间复杂度与束宽关系
在标准设置下，每一步要对束内 K 个候选进行扩展，并对所有扩展候选进行比较与裁剪。若不考虑进一步截断，扩展规模会随 K 增长，整体计算量通常与 K 成正比（或与 K 及候选扩展大小共同增长）。因此束宽越大，解码延迟通常越高。
在某些实现中还会引入额外操作（如 top-k、排序），使得常数因子随实现变化。
6.2 空间复杂度与实现细节
束搜索需要存储：
- 当前步的候选集合；
- 候选对应的序列前缀或回溯指针；
- 以及用于计算和排序的得分张量。
在使用 batched decoding 时，存储规模会随 batch size、束宽和最大长度共同增长。优化方法包括使用回溯索引而不是完整拷贝前缀，并尽量复用中间缓冲区。
6.3 评估指标：准确性、困惑度、覆盖率等
常用评估包括：
- 序列级准确性/任务指标：如翻译的 BLEU、摘要的 ROUGE、识别的词错率等（取决于具体任务）。
- 困惑度（perplexity）：主要反映语言模型本身的预测质量，解码策略也会影响最终表现，但 perplexity 不等同于解码质量。
- 覆盖率/重复率等生成质量指标：覆盖率可用于反映是否遗漏输入信息；重复率用于诊断循环与模板化输出。
对于具体系统，往往需要结合离线指标与线上用户反馈进行综合判断。
6.4 超参数调优经验
常见调参路线：
- 先固定模型输出概率处理方式（对数域、长度归一化形式）；
- 在一组合理束宽范围内尝试 K，观察质量与延迟的折中；
- 若出现输出偏短或偏长，调整长度归一化系数；
- 若发现重复问题，逐步启用重复抑制或覆盖惩罚；
- 对不同输入长度或不同难度样本，考虑动态束宽或分组策略。
调参的目标不是“追求最大束宽”，而是获得可接受的质量提升与工程成本。
7 工程实现要点
在真实系统中，束搜索不仅是算法，还涉及数据并行、终止策略与数值一致性。
7.1 批处理与并行化
为提升吞吐量，常用 batched beam search。由于不同样本的候选完成时间可能不同，工程中通常采用：
- 统一最大长度迭代，但对已结束候选停止扩展；
- 或维护每个样本的束状态与掩码，避免无效计算。
并行化还可通过向量化方式一次性计算多个候选的下一步分布，再统一执行 top-k 裁剪。
7.2 实用的终止与提前停止策略
提前停止能显著减少不必要的计算。常见做法包括：
- 当束中最高得分候选已生成结束标记且其得分上界无法超过其他候选；
- 或当所有候选的可扩展上界低于当前最优完成序列的得分。
这些策略依赖对“上界”的估计，既要保证效率，也要避免过早停止导致质量下降。
7.3 GPU/TPU友好的实现方式
为了适配加速器，通常避免在每一步做大量 Python 级循环。实践中更倾向于：
- 使用张量运算批量计算候选扩展；
- 用高效的 top-k 操作完成裁剪；
- 采用张量重排与索引（gather/scatter）保持候选对应关系。
此外，合理的内存布局可以减少频繁的拷贝与同步开销。
7.4 常见错误与排查（如得分尺度不一致）
常见问题包括：
- 得分尺度不一致：长度归一化、惩罚项与对数概率累加混用时若量纲不同，会导致排序失真。
- 掩码或结束标记处理错误：导致已结束候选仍被扩展，或结束过早被误排除。
- 回溯指针错误：在存储 top-k 的索引时若与候选重排不同步，会生成错位的最终序列。
- 数值域混乱：有的实现对部分项取对数，有的项在非对数域，比较时会产生系统性偏差。
排查通常从“得分计算与排序是否严格一致”以及“候选重排索引是否正确”两条线开始。
8 文化与梗（轻度）
束搜索在一些开发与讨论圈里常被当作“聪明但不保证最优”的折中方案来调侃，下面是轻度的比喻理解。
8.1 “束”到底束的是什么：用比喻理解
“束”可以想成一束手里拿着的线头：你不把所有可能的绳子都拉出来，而是先抓住几根最像要成功的线头继续往前试。被抓住的候选在下一步会更有机会“被看到”，被丢掉的就再也没有机会翻盘。
8.2 束宽的“想得太多会累，想得太少会翻车”
束宽太小，相当于只看一眼就下结论，容易走进局部最优；束宽太大，相当于同时开太多分支思考，计算压力和延迟都上升。工程上常见的态度是：找一个“刚好够用”的 K，而不是无脑加到最大。
8.3 从“贪心一次到位”到“束里多走几步”的心态迁移
贪心像是“一步到位”，觉得当前最优就能一路顺畅；束搜索则更像是“先多留几条可能的路”，在不确定中保持弹性。它不承诺最终一定最优，但通常能让结果更稳、更少踩坑。