束搜索（Beam Search，又称集束搜索）是一种启发式图搜索算法，本质是宽度受限的广度优先搜索（BFS），也是序列生成任务中广泛采用的近似解码策略。它通过在每一步搜索中仅保留概率（或得分）最高的固定数量候选序列（即“束宽”，用k表示），逐步扩展至目标长度，从而在避免穷举搜索（指数级复杂度）的同时，平衡搜索效率与结果质量，解决贪心搜索“目光短浅”、易陷入局部最优的问题。
简单来说，束搜索可看作贪心搜索的扩展——贪心搜索每步仅保留1个最优候选（即束宽k=1），而束搜索每步保留k个最优候选，相当于“不把鸡蛋放在一个篮子里”，通过多路径探索提升找到更优解的概率。当束宽为无穷大时，束搜索等价于最佳优先搜索；当束宽为1时，束搜索退化为贪心搜索（爬山算法）。
一、参数：束宽（Beam Width）
束宽k是束搜索的核心超参数，决定了每一步保留的候选序列数量，直接影响搜索效果与计算成本，具体影响如下：
•小束宽（如k=1~2）：计算成本低、速度快，但搜索范围窄，易陷入局部最优，效果接近贪心搜索，仅适用于对实时性要求极高、对结果质量要求较低的场景。
•大束宽（如k=10~20）：搜索范围广，保留更多潜在最优路径，结果质量更接近全局最优，但计算量和内存消耗会显著增加（需同时维护k个序列的扩展与评分），甚至可能出现冗余计算。
实践中，束宽通常选择3~10，可根据任务复杂度（如序列长度、词汇表大小）灵活调整，实现效率与质量的平衡。
二、工作原理与流程
束搜索的核心逻辑是“逐步扩展、筛选保留”，以序列生成为例（如机器翻译、文本生成），具体流程如下，全程基于累积概率（或对数概率，避免数值过小无法比较）进行评分筛选：
1.初始化
从初始序列（通常为空序列或特殊起始标记）开始，设定束宽k，初始化候选序列集合，此时候选集合仅包含初始序列，累积概率为1（对数概率为0）。
2.迭代扩展
对当前候选集合中的每一个序列，扩展其下一个可能的元素（如文本生成中的词汇、机器翻译中的目标语言单词），生成所有可能的扩展序列，并计算每个扩展序列的累积概率（当前序列累积概率 × 下一个元素的条件概率）。
3.筛选保留
从所有扩展生成的序列中，筛选出累积概率最高的k个序列，作为下一步的候选集合，丢弃其余概率较低的序列，完成一次迭代。
4.终止与输出
重复“迭代扩展-筛选保留”的步骤，直到所有候选序列都生成终止标记（如文本生成中的），或达到预设的最大序列长度，停止搜索；最后从最终的候选集合中，选择累积概率最高的序列作为最终输出结果。
流程示例（束宽k=2）
假设词汇表为{a, b, c, }，初始候选集合为空序列，具体步骤如下：
•第一步扩展：生成所有可能的首个词汇，概率分别为a(0.4)、b(0.3)、c(0.2)、(0.1)，筛选Top-2序列，候选集合变为{a(0.4), b(0.3)}；
•第二步扩展：分别扩展a和b，生成a→a(0.12)、a→b(0.04)、a→c(0.16)、a→(0.08)，以及b→a(0.03)、b→b(0.03)、b→c(0.09)、b→(0.15)，筛选Top-2序列，候选集合变为{a→c(0.16), b→(0.15)}；
•第三步扩展：仅扩展未终止的a→c，生成a→c→a(0.016)、a→c→b(0.032)、a→c→c(0.08)、a→c→(0.032)，筛选Top-1序列（因b→已终止），最终候选集合包含a→c→c(0.08)和b→(0.15)；
•输出结果：选择累积概率最高的b→作为最终输出（或根据任务需求调整终止逻辑）。
三、优点
•平衡效率与质量：相比穷举搜索，大幅降低计算复杂度和内存消耗，可处理大规模序列生成任务；相比贪心搜索，通过多候选保留，减少局部最优陷阱，生成结果更优、更连贯。
•灵活性高：束宽k可灵活调整，可根据硬件资源、任务需求（实时性、质量要求）动态适配，适用场景广泛。
•实现简单：逻辑清晰，无需复杂的剪枝策略，易于工程实现，是序列生成任务的主流解码方法之一。
四、缺点
•非最优性：由于每步仅保留Top-k候选，可能会剪枝掉潜在的全局最优序列，无法保证一定能找到最优解，仅能获得近似最优解。
•计算成本随束宽增加而上升：束宽k越大，每步扩展的序列数量越多，计算量和内存消耗呈线性增长，当k过大时，可能失去效率优势。
•缺乏随机性：生成结果偏向保守、中规中矩，易出现重复输出，不适合需要创造性、多样性的生成任务（如诗歌、故事创作），需结合采样策略（如Top-K、Top-p采样）补充随机性。
•无完整性保证：若全局最优序列被过早剪枝，算法可能无法找到有效解（即使解存在），牺牲了搜索的完整性。
五、适用场景
束搜索主要适用于对结果质量有一定要求、同时需控制计算成本的序列生成任务，核心应用场景包括：
•自然语言处理（NLP）：机器翻译（如将中文翻译为英文，每步保留多个翻译候选，提升翻译准确性）、文本摘要（生成简洁连贯的摘要）、对话生成（基础对话场景，保证回复合理性）、语音识别（从多个可能的词序列中筛选最优识别结果）；
•计算机视觉（CV）：图像描述（为图像生成符合逻辑的文字描述）、目标跟踪（根据传感器读数，筛选最优的目标位置序列）；
•其他场景：代码生成（基础代码片段生成）、约束满足问题（CSPs）求解，用于高效寻找近似最大权重分配方案，避免回溯搜索的高成本。
不适用于场景：需要高随机性、创造性的生成任务（如诗歌、小说创作），以及对结果最优性有严格要求的场景（如精密算法求解）。
六、与其他解码策略对比
束搜索与其他主流解码策略的对比如下：束搜索的核心特点是保留k个候选序列，通过逐步扩展与筛选，平衡局部与全局最优，其计算成本中等且随束宽k递增，结果质量较高（可获得近似最优解），适用于机器翻译、文本摘要、图像描述等场景；贪心搜索每步仅保留1个最优候选且无回溯，计算成本最低、速度最快，但结果质量较低，易陷入局部最优，适合实时响应、简单对话生成等场景；Top-K采样每步从概率Top-K的候选中随机采样，计算成本中等，生成结果具有较高随机性和多样性，适用于诗歌、故事等创造性生成任务；Top-p采样则按概率累积和筛选候选，可自适应调整候选范围，计算成本中等，生成结果多样且可控，适合对话系统、代码生成等场景。
七、关键补充
•评分方式：实际应用中，常使用对数概率累加替代直接概率累乘，避免因概率值过小导致的数值下溢问题，评分逻辑不变（数值越大，序列越优）。
•变体形式：为弥补束搜索的完整性缺陷，可结合深度优先搜索（DFS）形成束栈搜索、深度优先束搜索等变体，成为可随时返回近似解的算法。
•实践技巧：多数序列生成任务中，优先选择束宽k=3~10；需创造性输出时，可结合温度调节、Top-K/Top-p采样，平衡合理性与多样性；强可靠性场景（如医疗问诊、金融报告生成）需构建鲁棒性束搜索子系统。
•历史背景：束搜索最早应用于1976年的Harpy语音识别系统，最初被称为“轨迹搜索模型”，1977年正式被命名为“束搜索”，此后逐步成为序列生成领域的核心解码策略之一。
