/ What Is Series

What Is Beam Search?

A technical guide to Beam Search: sequence scoring, expansion and pruning, beam width, length normalization, stopping criteria, and inference costs.

Jul 22, 20262 minLLM · Decoding · Inference · Beam Search

在机器翻译、语音识别、文本生成和图像描述等任务中，模型需要逐步生成一个序列。**Beam Search（束搜索）**就是一种面向这类问题的启发式搜索算法。

一句话概括：

Beam Search 每一步不只保留一个最优结果，而是保留前 B 个最有希望的候选序列，再继续向后扩展。这里的 B 称为 beam width（束宽）。

它介于两种极端之间：

Greedy Search：每一步只保留 1 条路径，速度快，但容易局部最优；
Exhaustive Search：保留所有可能路径，理论上最充分，但计算量爆炸；
Beam Search：每一步只保留最有希望的 beam_size 条路径，在效果和成本之间折中。

所以，Beam Search 的核心不是随机采样，而是用有限计算量近似寻找整体得分最高的序列。标准 Beam Search 通常是确定性的：给定相同的模型输出、输入和解码参数，它会得到相同结果。

1. 为什么需要 Beam Search#

自回归模型每次只预测下一个 token，但解码的目标通常是让完整序列的联合概率最高。给定输入 $x$ 和输出序列 $y=(y_1,\ldots,y_T)$ ，理想目标是：

y^*=\arg\max_y P(y\mid x)

根据概率链式法则：

P(y\mid x)=\prod_{t=1}^{T}P(y_t\mid y_{<t},x)

局部最优并不等于整体最优。考虑两条只有两步的路径：

路径 A：0.6 * 0.1 = 0.06
路径 B：0.4 * 0.8 = 0.32

路径 A 的第一步概率更高，贪心搜索会立即选择它；但完成两步后，路径 B 的联合概率更高。问题不在模型的概率计算，而在于贪心搜索过早丢弃了暂时落后的候选。

如果词表大小为 $V$ 、最大生成长度为 $T$ ，完整枚举则要面对近似 $V^T$ 条路径，实际系统无法承受。Beam Search 用一个固定搜索预算 $B$ 折中：它允许多条路径继续竞争，但每轮扩展后立即剪枝。

2. Beam Search 怎么做#

假设模型要生成一句话，第一步的候选为：

“我”：   0.5
“今天”： 0.3
“他”：   0.2

令束宽 $B=2$ 。第一步只保留概率最高的两个前缀：

我
今天

2.1 扩展#

模型分别基于每条保留路径预测下一个 token，得到一组更长的候选：

我     -> 我喜欢、我认为、……
今天   -> 今天天气、今天学习、……

若每条 beam 都对词表中的 $V$ 个 token 进行扩展，这一轮最多会产生 $B\times V$ 个候选。工程实现通常不会真的复制 $B\times V$ 条完整字符串，而是计算累计得分并记录父 beam 与新增 token。

2.2 打分#

每个候选的新分数等于父路径的累计分数加上新 token 的对数概率：

s(y_{1:t})=s(y_{1:t-1})+\log P(y_t\mid y_{<t},x)

例如，假设这一轮得到：

今天天气：0.3 * 0.7 = 0.21
我喜欢：  0.5 * 0.4 = 0.20
我认为：  0.5 * 0.3 = 0.15
今天学习：0.3 * 0.2 = 0.06

这里用概率乘积便于展示；实际计算使用对数概率求和，以避免许多小数相乘造成数值下溢。

2.3 剪枝#

把来自所有父 beam 的扩展放在一起排序，只留下累计得分最高的 $B=2$ 条：

今天天气
我喜欢

算法随后重复“扩展—打分—剪枝”。遇到 <eos> 的序列进入已完成集合，不再扩展；当满足终止条件时，再从已完成序列中返回最终得分最高的结果。

3. 和 Greedy Search、穷举搜索的区别#

方法	每一步保留几个候选	优点	缺点
Greedy Search	1 个	快，简单	容易局部最优
Beam Search	`beam_size` 个	通常比贪心搜索更稳	更慢，占更多显存或内存
Exhaustive Search	所有可能	理论上最充分	计算量指数爆炸，不现实

可以把它们想成三种走迷宫的方式：

Greedy Search：每个岔路口都选眼前看起来最好的那条路；
Beam Search：每个岔路口保留几条看起来不错的路线；
Exhaustive Search：所有路线都走一遍，最后选最好的。

Beam Search 的重点就是：它比贪心多看几条路，但不会像穷举那样把所有路都走完。

4. 束宽控制了什么#

束宽 $B$ 是 Beam Search 最重要的搜索预算：

$B=1$ 时退化为 Greedy Search；
$B>1$ 时，同时维护多条活跃路径；
$B$ 足够大时会更接近穷举，但现实中仍受最大长度、候选截断和内存约束。

增大 $B$ 通常能减少“较优路径过早被剪掉”的搜索错误，但不保证下游指标单调提升。模型概率本身可能与 BLEU、WER、事实正确性或人类偏好并不完全一致；更宽的 beam 也可能放大短句偏好和模板化倾向。

若词表大小为 $V$ 、生成长度为 $T$ ，仅考虑候选分数，朴素搜索每一步处理约 $B\times V$ 个扩展，总量约为 $O(TBV)$ 。取 top- $B$ 可以用高效的 top-k 算法完成，但模型前向计算、KV cache 和 beam 重排通常才是系统中的主要成本。

5. 对数概率与长度归一化#

原始序列概率由多个小于 1 的数相乘，序列一长就容易发生数值下溢。因此实现中使用累计对数概率：

L(y)=\log P(y\mid x)=\sum_{t=1}^{T}\log P(y_t\mid y_{<t},x)

因为每一项对数概率通常不大于 0，序列越长， $L(y)$ 往往越小。只按累计对数概率排序，会天然偏爱较早输出 <eos> 的短序列。

常见修正是长度归一化：

S(y)=\frac{L(y)}{T^\alpha}

其中 $\alpha$ 控制长度惩罚强度。另一种常见形式是：

S(y)=\frac{L(y)}{\left(\frac{5+T}{6}\right)^\alpha}

当 $\alpha=0$ 时不做长度修正； $\alpha$ 增大时，相对更愿意保留长序列。具体公式和参数语义因框架而异，因此迁移解码配置时不能只比较 length_penalty 这个参数名。

长度惩罚也带来一个实现细节：活跃序列和已完成序列长度不同，不能只看未归一化累计分数就贸然停止搜索。

6. 结束序列与终止条件#

候选生成 <eos> 后就成为已完成序列。它应该进入单独的 finished 集合参与最终排序，而不再送入模型继续扩展。搜索可以在以下情况下结束：

所有活跃 beam 都已经生成 <eos>；
已达到 max_new_tokens 或最大序列长度；
已完成候选足够多，且活跃候选即使继续扩展也不可能超过当前最佳完成结果。

第三种 early stopping 最高效，但必须根据实际评分函数计算上界。若长度惩罚、最小生成长度或约束解码参与评分，简单地在“已有 $B$ 条完成序列”时停止，可能错过更好的结果。

如果达到最大长度时仍没有 <eos>，实现通常会从剩余活跃 beam 中选取得分最高者，或者把这些 beam 视为截断完成；具体行为同样取决于框架配置。

7. 为什么 Beam Search 会让结果更保守#

Beam Search 追求的是高概率序列。

而语言模型里的高概率表达，往往是更常见、更安全、更普通的表达。

例如写作任务里，Beam Search 可能倾向于生成：

This is a very important issue.

而不是更有创意、更跳脱的表达。

这是因为 Beam Search 本质上不是在“探索多样性”，而是在“搜索高概率”。beam size 越大，它越有机会找到模型认为整体概率更高的句子，而这些句子经常更平均、更模板化。

所以在聊天、创作、开放式生成场景里，更常见的是：

temperature sampling
top-k sampling
top-p sampling

它们通过随机性和截断采样增加多样性。

Beam Search 更常见于：

机器翻译；
语音识别；
摘要生成；
图像描述；
代码或结构化文本生成；
需要稳定、可复现、较少随机性的任务。

简单说：Beam Search 适合追求稳定正确，不适合追求开放创意。

8. 在大模型推理中，Beam Search 为什么更贵#

在推理系统里，如果：

beam_size = B

可以粗略理解为：每个请求会被扩展成 B 条并行候选序列。

例如 batch size 是 8，beam size 是 4，那么 decode 阶段可能近似变成：

8 * 4 = 32 条序列

这会带来几类成本。

8.1 KV cache 占用增加#

每个 beam 都有自己的生成历史。

在 Transformer decode 阶段，生成历史通常对应 KV cache。不同 beam 可以共享提示词和分叉前缀的缓存页，但分叉后的 token 仍需要独立状态。因此 beam 越多，KV cache 占用通常也会增加；具体增幅取决于运行时是否支持前缀共享、copy-on-write 和分页缓存。

这对长上下文、大 batch、多并发请求尤其敏感。

8.2 Decode 计算量增加#

普通 sampling 通常每个请求只继续一条路径。

Beam Search 会同时扩展多条路径，每一步都要计算多个 beam 的下一个 token 分布，并从候选里重新选择 top beams。

所以它的 decode 成本通常接近随 beam_size 增长。

8.3 调度和重排更复杂#

不同 beam 可能在不同时间生成 <eos>。

推理系统需要处理：

beam pruning；
finished beam 和 active beam 的管理；
KV cache 的重排；
batch 内不同请求的 beam 对齐；
最终序列选择和长度惩罚。

这些都会让实现复杂度和调度成本上升。

8.4 吞吐下降#

从系统角度看，一个 beam size 很大的请求，会占用更多 decode slot、显存和调度资源。

所以在大模型推理系统里，Beam Search 通常比单路 sampling 更贵。它不是“只多保存几个候选字符串”这么轻量，而是实实在在增加了推理时的活跃序列数和状态管理成本。

9. Beam Search 的简化伪代码#

可以把 Beam Search 写成下面这个流程：

active = [(prompt, score=0)]
finished = []
 
for step in range(max_new_tokens):
    candidates = []
 
    for beam in active:
        log_probs = model.next_token_log_probs(beam.tokens)
 
        for token in vocabulary:
            candidate.tokens = beam.tokens + [token]
            candidate.score = beam.score + log_probs[token]
 
            if token == EOS:
                finished.append(candidate)
            else:
                candidates.append(candidate)
 
    active = top_b(candidates, key=search_score)
 
    if active is empty or safe_to_stop(active, finished):
        break
 
pool = finished if finished is not empty else active
return best(pool, key=final_normalized_score)

伪代码为了说明逻辑而遍历整个词表；实际实现会使用向量化 top-k，且可能暂时多保留一些 EOS 候选。搜索阶段的 search_score 与最终的 final_normalized_score 也不一定完全相同，取决于实现如何处理长度惩罚。除此之外，真实系统还要处理最小长度、重复惩罚、约束解码、批处理和 KV cache 重排。

10. 常见误区#

误区一：Beam Search 是随机采样#

不是。

标准 Beam Search 是确定性的搜索算法。只要模型输出、输入、参数一致，结果通常是可复现的。

误区二：beam size 越大，效果一定越好#

不一定。

beam size 变大确实会扩大搜索范围，但也可能让输出更普通、更短或更模板化，还会显著增加推理成本。

误区三：Beam Search 一定能找到全局最优#

不能。

Beam Search 每一步都会剪枝，只保留前 beam_size 个候选。如果真正最优路径早期得分不高，被剪掉之后就再也回不来了。

所以 Beam Search 只是近似搜索，不是全局最优搜索。

误区四：Beam Search 适合所有 LLM 场景#

也不是。

对于开放式聊天、创意写作、头脑风暴，sampling 往往更合适；对于翻译、识别、摘要、结构化输出，Beam Search 更常见。

11. 总结#

Beam Search 是一种折中搜索策略：它不像贪心搜索那样只保留一个候选，也不像穷举搜索那样保留所有候选，而是在每一步只保留前 beam_size 个最有希望的序列，从而在生成质量和计算成本之间做平衡。

如果放到大模型推理系统里看，它还有另一个更工程化的含义：

beam size 越大，一个请求就越像被展开成多条并行 decode 路径，质量可能更稳，但 KV cache、计算量和调度复杂度也会一起上升。