BeamSearch原理

Beam Search 是一种启发式搜索算法，常用于自然语言处理和其他需要生成序列的任务中，比如机器翻译、自动摘要和语音识别，大模型推理等。它是一种改进的贪心算法，旨在平衡计算效率与搜索质量。相对Greedy search扩大了搜索空间，但远远不及穷举搜索指数级的搜索空间，是二者的一个折中方案。Greedy search 可以看做是 beam size = 1时的 beam search，即每一步都选概率排名Top-1的token，一条路走到黑。

Beam Search通过维护一个有限大小的候选集（称为“beam”），在每一步只选择最有希望的若干个候选项，从而避免了暴力搜索空间的指数级增长。简言之，Beam Search 会在每个时间步上选择最佳的“beam width”（宽度）个候选，而不是总是选择最好的单个候选。

Beam Search有一个超参数beam size（束宽），设为k。第一个时间步长，选取当前条件概率最大的k个词，当做候选输出序列的第一个词。之后的每个时间步长，基于上个步长的输出序列，挑选出所有组合中条件概率最大的k个，作为该时间步长下的候选输出序列。始终保持k个候选。最后从k个候选中挑出最优的。

算法流程

假设要生成一个序列，算法的步骤如下：

初始化：开始时，Beam Search 选择一个初始状态（比如一个空的序列）并评估其可能性。

扩展候选项：每一步，算法生成所有可能的下一个词或状态，并评估这些候选项的得分（通常通过某种概率模型来评估，如语言模型或神经网络的输出）。

选择最佳候选：然后，只保留得分最高的“beam width”个候选项，并丢弃其他候选项。这些候选项将继续向下扩展。

停止条件：直到满足某种停止条件（如生成完毕或达到最大长度）时，算法会停止，最终选择得分最高的候选序列作为结果。

Beam Search 是基于保留每步得分最好的候选项来进行的，但是如果有多个候选项的概率相同，可以选择随机从这些候选中选出若干个，或者可以选择 按顺序 排列所有候选项，并选出得分相同的前 N 个候选项。

算法实例

Beam search是对贪心策略一个改进，在每一个时间步，不再只保留当前分数最高的1个输出，而是保留num_beams个。当num_beams=1时集束搜索就退化成了贪心搜索。

下图是beam search的一个实例，每个时间步有ABCDE共5种可能的输出，图中的num_beams=2，也就是说每个时间步都会保留到当前步为止条件概率最优的2个序列。

• 在第一个时间步，A和C是最优的两个，因此得到了两个结果[A],[C]，其他三个就被抛弃了；
• 第二步会基于这两个结果继续进行生成，在A这个分支可以得到5个候选：[AA]、[AB]、[AC]、[AD]、[AE]，C分支同理也得到5个候选：[CA]、[CB]、[CC]、[CD]、[CE]。此时会对这10个进行统一排序，再保留最优的两个，即图中的[AB]和[CE]。
• 第三步同理，也会从新的10个候选里再保留最好的两个，最后得到了[ABD]、[CED]两个结果。

可以发现，beam search在每一步需要考察的候选数量是贪心搜索的num_beams倍，因此是一种牺牲时间换性能的方法。

BeamSearch的优缺点

优点：
比贪心算法更好：能够考虑多个候选项，避免早期陷入局部最优解。
计算效率较高：相对于暴力搜索，Beam Search 大大减少了搜索空间。
缺点：
计算开销较大：随着 Beam Width 增大，计算的复杂度也会增加。
不能保证全局最优解：由于只保留固定数量的候选项，可能会错过一些较优的解。

参考文献

【CSDN】怎么理解BeamSearch？

【知乎】如何通俗的理解beam search？

Beam Search（束搜索）：优化序列生成的高效算法（代码实现）_算法_2048 AI社区

序列生成算法 --- Beam Search_beam search算法-CSDN博客