Beam search（集束搜索）是一种在生成式 AI 中的搜索策略，常用于编码器-解码器架构。解码器在每一步生成词汇表中每个标记是下一个标记的概率，使用这些概率来评估句子块而非单个单词的概率，并在每一步保留最有可能生成的块。
在一些实验中，如 PromptAgent 论文精读翻译中的基线实现细节，Beam search 与 PromptAgent 使用相同的扩展功能。除根节点外每个节点扩展为 3 个新节点，集束宽度为 3，意味着搜索树的每个深度都有 9 个节点，而最好的 3 个节点会被保留用于下一次扩展，根节点扩展为 9 个新节点，搜索深度为 8，总共有 72 个节点或新提示。
在常用采样策略中，Beam search 是确定性采样的一种。它维护 beam 的大小为 k，对当前 beam 中的所有路径做下个 token 的展开，选取累积概率最高的前 k 个路径作为新的 beam，以此类推。计算量增大，但输出有一定确定性同时更加丰富。当 k=1 时退化成 Greedy Search（贪心搜索）。
解码器在每一步只生成词汇表中每个标记是下一个标记的概率。使用这些概率，您必须选择一个词。贪婪搜索：生成概率最高的标记。波束搜索：使用解码器生成的概率来评估句子块而不是单个单词的概率，并在每一步都保留最有可能生成的块。
我们为实验中的各种基线描绘细节。蒙特卡洛(MC)。MC执行一步采样多次，并选择最佳的一个作为优化提示。它使用与PromptAgent相同的提示采样方法，但将搜索深度限制为一。在搜索消融研究中，我们在每个任务中采样了72个新提示。集束搜索(Beam)。Beam也使用与PromptAgent相同的扩展功能。除根节点外的每个节点都将扩展为3个新节点，集束宽度为3，这意味着搜索树的每个深度都将有9个节点，而最好的3个节点将被保留用于下一次扩展。根节点将扩展为9个新节点。搜索深度为8，因此总共有72个节点或新提示。贪婪搜索(Greedy)。贪婪搜索基于集束搜索，但集束宽度为一，因此算法变为深度优先贪婪搜索。我们进行了两个实验，Greedy-S和Greedy-L，在图4a中，搜索深度相同为8，但扩展宽度不同。Greedy-S的扩展宽度为3，总共有34个提示。Greedy-L的扩展宽度为9，总共有72个节点，这也被称为表4中的Greedy基线。APE(Zhou等，2022)。
确定性采样顾名思义就是输出结果是确定性的，本质上是搜索过程。常见的如贪心搜索(Greedy Search)和集束搜索(Beam Search)。借用[这里](https://link.zhihu.com/?target=https%3A//deci.ai/blog/from-top-k-to-beam-search-llm-decoding-strategies/)的图，如下所示Greedy Search。每次选取概率最高的token输出，非常容易陷入复读机循环。Beam Search。维护beam的大小为k k，对当前beam中的所有path做下个token的展开，选取累积概率最高的前k k个path，作为新的beam，以此类推。计算量增大，但是输出有一定确定性同时更加丰富。容易发现k=1 k=1的时候退化成Greedy Search。