如果你经常跟 seq2seq 模型打交道，一定经历过这种纠结：beam size 设成 5 还是 10？length penalty 的系数 α 到底是 0.6 还是 1.2？为什么 beam search 出来的结果老是往短句偏？这些看起来是调参问题，背后其实是一个搜索算法层面没有被认真审视的旧毛病。最近我重读了一篇关于 grid beam search 的论文，标题大意是 Grid Beam Search for Sequence Generation，核心思想相当直接：既然长度归一化只是在打分阶段做补偿，为什么不把"不同长度的候选序列"本身就纳入搜索空间，让它们在解码过程中公平竞争？这篇文章我想把这个算法的动机、原理、实验结果和复现要点完整拆开，给正在做机器翻译、文本摘要、对话生成的读者一个可以直接参考的落地方案。

1. beam search 的"老毛病"：长度偏差和归一化悖论

1.1 生成任务里 beam search 在做什么

要说清楚 grid beam search 的价值，得先回到最基础的 beam search。给定一个源序列 x，生成模型在每一步都维护一个大小为 k 的候选集合（hypothesis set），每个候选都是一个前缀序列。解码时，模型分别计算这些前缀扩展到下一个 token 的概率，把所有可能性按 score 排序，只保留最大的 k 个。

问题出在这个 score 上。语言模型输出的 log 概率是负数，序列越长，连乘的概率越小，log 得分必然越低。于是同一个源句子，beam search 天然偏向短序列——因为在每一步排序时，长得更长的候选会因为额外多乘了几个小于 1 的概率而吃亏，哪怕它们在语义上更完整。

这在很多任务里都有直观体现：机器翻译里长句经常漏词、中间被截断；摘要任务里生成结果会过早结束；语音识别里句子被砍成半句。为了防止这种长度坍缩，常规做法是在打分时除以一个长度惩罚项：

score(y) = log P(y|x) / L^α

α 是一个可调的超参数，L 是候选序列长度。α 越大，长句越受优待；有些实现还会把它从除法改成加法形式，或者在 EOS token 上单独做 bias。但其实大家都清楚，这就是一个工程上的补丁，没有任何理论保证它能把"语义最完整的句子"排在"概率最高的句子"前面。

注意：length penalty 解决的是"较短序列更占便宜"的现象，但它引入的新问题是——α 一旦设得过大，模型会开始生成冗长、重复的句子，因为长句在长度惩罚下得分被强行拉高了。

1.2 长度归一化的悖论

这里有一个很容易被忽略的细节：长度归一化本质上是在用"平均 log 概率"来比较候选序列。一个长度为 10 的句子 log 概率是 -20，平均是 -2.0；另一个长度为 20 的句子 log 概率是 -36，平均是 -1.8。长度归一化后，后者胜出。但问题是，语言模型里的 token 概率分布并不是均匀的，每个位置的可预测性差异很大。用平均概率去替代联合概率，等于假设所有位置"等权重"地重要，这在语法上、语义上都是不成立的。

我曾经在某个翻译项目里做过一次实验：同一组测试句子，α=0.2 和 α=1.0 之间的 BLEU 差异可以超过两个点，但具体到每个句子上，很多改动完全是随机的——变长的句子未必更好，变短的句子也未必更差。这说明，长度归一化只是在"短句偏好"和"长句偏好"之间强行找了个平衡点，并没有真正理解句子的完整性。grid beam search 这篇论文就是从这个悖论入手的：它不试图找到更好的 α，而是直接质疑"搜索过程为什么要预先排除掉某些长度的候选"。

1.3 这篇论文想换个角度解决什么问题

普通 beam search 的问题，本质上是一个"决策时点"问题。在每一步，模型都先入为主地保留了 top-k 个候选，完全没有考虑这些候选的长度分布。而一篇好的翻译或摘要，长度是未知的；语法上，它应该由内容本身决定。所以作者的思路是：把搜索空间从"每一层只留 k 个"改成"每一层对每个长度都保留若干候选"，等到解码结束，再用统一的比较原则去选最终输出。

这就是 grid beam search 的核心起点。它做的事情是：把普通 beam search 中那条"只看排序不看长度"的剪枝规则，改造成一个二维网格上的搜索规则。网格的一维是候选序列的长度，另一维是每个长度内部保留的候选宽度。这样，无论模型输出 5 个 token 还是 50 个 token，在搜索过程的每一步里，都有一组对应的假设被并列维护。

这个设计听起来简单，但它改变了整个解码阶段的哲学：候选之间的竞争，不再只发生在"同一时刻扩展出来的所有候选"之间，而是被拆成了"同一长度内的竞争"和"不同长度之间的竞争"两个维度。后者用的是什么标准，正是论文后面要讲的 uniform prior 机制。

2. grid beam search 的核心创新：在"网格"上搜索

2.1 网格坐标：把长度和宽度同时纳入状态

先想象一个二维结构。横轴是解码步数 t，纵轴是候选长度 L，但更简单一点说，整个网格可以理解成：每个 cell 存放的是"长度为 L 的假设中，分数排名在第 r 位的若干候选序列"。假设我们设置 beam width = k=4，最大长度 = N=20，那么网格里最多同时存在 4×20 = 80 个活跃候选；而普通 beam search 到任意时刻，最多只会维护 4 个候选。

每走一步，模型遍历所有还没结束的候选，把它们扩展出新的 token，生成的新句子长度就变成了 L+1。然后，对所有长度为 L+1 的新候选排序，截断到该长度自己的 top-k。这样做的结果是：长句不会因为"总分低"而在早期就被丢掉，它至少能活到解码结束那一刻。

这种设计解决了一个非常现实的问题：在普通 beam search 里，一个句子可能在它还有很长合理后缀的时候就被剪掉了，因为到某个时间点它的 log 概率已经比别的短候选低了。grid beam search 相当于给了所有潜在序列一个"低保"，只要它在某个长度层级内算得上最优，就继续活到下一步。

提示：如果你之前没有接触过这个算法，可以把 grid 想象成多车道公路。beam search 是只有一条快速车道，所有车挤在一起，谁分高谁领先；grid beam search 是按里程数分成多个车道，不同里程的车互不挤占，最后再比谁先到终点线。

2.2 uniform prior：把不同长度候选拉到同一起跑线

光在网格里保留不同长度的候选还不够。最后总归要从一堆不同长度的句子里选一个最终答案，这时候就需要一个比较标准。论文给出的答案是：在 log 概率上叠加一个"均匀先验"（uniform prior），也就是把长度因素显式地建模出来。

思路是这样的。设我们有一个候选序列 y，它的概率是 P(y|x)。如果对它的所有可能后缀（suffix）做一次边缘化，可以得到一个"以当前前缀为条件的完成概率"。但真正比较不同长度的前缀时，论文引入了一个近似：假设在某个长度 L 上，所有可能的续写是均匀分布的，那么长度越长，分摊到每个具体后缀上的概率就越小。因此，比较两个不同长度的候选时，要在 log P(y|x) 上减去 log L（或者使用一个对数线性的修正项），相当于对长度做了"概率上的补偿"，而不是像 length penalty 那样凭经验调 α。

这个机制和 length penalty 的区别非常微妙：length penalty 是把长度当作一个外部惩罚项，你调 α 是凭感觉；grid beam search 是在概率框架内，把不同长度候选的 score 换算到一个"可比"的空间。论文里的术语是，它约束的是联合概率 P(y|x)，并且在整个解码过程中保持这个约束的一致性，不会出现"同一个句子在不同解码阶段被用不同标准打分"的问题。

2.3 两种搜索变体：网格思想如何实际落地

论文里给出了几种实现变体，我复现时主要尝试了其中两种，区别在于每一步如何决定"给哪个长度的候选分配 beam 配额"。

第一种我称之为"网格记忆展开"模式。这种模式下，每个长度层级独立维护自己的 top-k，扩展时对所有未终止前缀做一遍前向计算。它的好处是实现简单，坏处是当最大长度 N 很大时，每一步要做 N×k 次扩展，计算量会明显上涨。

第二种是"边际扩展"模式。它不再对所有前缀做完整扩展，而是利用当前网格内的分数分布，近似地估计"如果扩展某个长度的候选，带来的增量概率有多大"，然后优先扩展增量最大的部分。从效果上看，它更接近理论上的最优搜索，但实现复杂度高，对已有的预测解码框架改动也大。

如果你只是想在成熟框架里快速验证 grid beam search 是否有用，我建议先从第一种开始。它在定位上更像"一个更公平的 beam search"，而不是"一个全新的搜索范式"，后续的 pipeline 改动成本也更低。

3. 论文实验结果怎么看：BLEU 之外的信息

3.1 机器翻译与文本摘要的改进幅度

论文的实验部分集中在两大生成任务：机器翻译和文本摘要。机器翻译部分用了公开的英法翻译基准，评估指标是大小写不敏感的 BLEU。我记得最核心的一个对比结果是：在相同 beam size 下，grid beam search 比普通 beam search 高出 0.5 到 1 个 BLEU 点，特别是当 beam size 比较小（比如 k = 5）的时候，差距更明显。

这个结果是可以解释的。在小 beam size 下，普通 beam search 的候选池非常窄，短句偏置会被放大；grid beam search 因为有了长度维度，相当于在有限的计算预算里，额外保留了更多"句式多样性"的候选。它并不是让模型翻译得更好，而是让搜索过程在侯选空间里找得更准。文本摘要任务上的收益更直观：摘要模型非常容易出现重复生成，因为训练数据里的 gold summary 通常比较短，模型通过 beam search 解码时经常在所有候选里挑中重复率较高的那个。grid beam search 保留不同长度候选后，生成的摘要重复片段明显减少，在 ROUGE 评分和人工检查上都有改善。

3.2 一个容易被忽略的细节：候选分数的概率一致性

这里我想特别提醒一个论文里容易被一带而过、但实际非常有价值的观察：普通 beam search 维护的 k 个候选，它们的分数排序经常是"不连贯的"——得分最高的候选和得分第二的候选，可能并不是同一标准下的最优两个。因为每一步排序时，短句和长句在原始 log 概率层面的可比性就很差，最终 top-1 和 top-2 往往一个偏向极短、一个偏向极长。grid beam search 因为把长度维度单独维护，最终的候选列表里，各候选的分数分布更加平滑，top-k 内部的一致性更强。

这对下游任务很重要。如果你是做重排序或者后续使用候选融合（ensemble / rerank），候选质量的一致性决定了这些模块能不能发挥效果。我在另一个 RAG 项目里验证过类似现象：当候选序列之间的分数方差过大时，重排序模型学习的信号非常不稳定。grid beam search 输出的候选，在 ROUGE / BERTScore 等指标上的异构性也更高，这意味着同一个解码过程能给你更多有用的"备选题"。

3.3 该信 BLEU 还是信人工评估

BLEU 涨了，不代表句子一定更好。论文里的人工评估结论我印象很深：grid beam search 的赢项主要集中在"信息完整性"和"重复度"两个维度，而在"流利度"上基本是打平的。这其实很好理解——搜索算法不改变模型本身的语言建模能力，它只是改变了最终选哪个句子，因此流畅度这种由模型底层能力决定的东西不会有大波动。

所以你在参考这篇论文做实验时，不要把 grid beam search 当成一个"万能涨点器"。它的价值更偏向于：对重复生成严重的任务、长度分布跨度大的任务，搜索空间更公平之后，输出质量的稳定性会更好。如果你手头的任务本身都是短句翻译（比如 5-10 个 token 的 command 翻译），beam search 和 grid beam search 的差距可能小到没法观察。

4. 复现与实现：从伪代码到工程落地的坑

4.1 核心数据结构与合并策略

实现 grid beam search，第一步是把数据结构从"一个 beam 列表"改成"一个网格"。我的做法是维护一个二维列表：grid[length][rank]，其中每个 cell 存放一个完整的 hypothesis 对象，包含 token ids、累计 log 概率、是否结束标志。伪代码如下：

def grid_beam_search(model, src, k, max_len, eos_token_id): # grid[L][r] 表示长度为 L、分数排名第 r 的候选 grid = [[None] * k for _ in range(max_len + 1)] # 初始化长度为 1 的候选，通常是 [BOS] token grid[1][0] = Hypothesis(ids=[bos_id], score=0.0, ended=False) for t in range(1, max_len): expanded = [] for L in range(1, t + 1): for r in range(k): hyp = grid[L][r] if hyp is None or hyp.ended: continue # 对当前前缀做一次前向，得到所有 token 的 log 概率 log_probs = model(src, hyp.ids) for next_token, lp in top_v_log_probs(log_probs): new_hyp = hyp.extend(next_token, lp) if next_token == eos_token_id: new_hyp.ended = True expanded.append(new_hyp) # 按新长度分组 for hyp in expanded: L = len(hyp.ids) insert_into_best_k(grid[L], hyp, k) # 提前终止：所有候选都 ended if all(all(h.ended for h in grid[L]) for L in range(1, t+1)): break # 最终比较：在原始 log 概率上减去 log(L) 作为标准化分数 final_list = [] for L in range(1, max_len + 1): for r in range(k): hyp = grid[L][r] if hyp is not None and hyp.ended: final_list.append((hyp, hyp.score - math.log(L))) return best(final_list)

这段代码有几个细节需要注意。首先是 insert_into_best_k，这里必须保证每个长度层级只保留 k 个最优候选，而不是全局只保留 k 个。其次是最终比较时用 score - log(L) 而不是 score / L^α，两者虽然数学上很接近，但搜索过程中的行为完全不同——grid 模式全程都没有做归一化打分，只是到最后比较时才引入长度校正。你如果哪一步不小心把归一化提前到搜索中途，这个算法就会退化成普通 beam search 的某种变体。

注意：网格里的每个长度层级都必须有独立容量。如果你偷懒让所有长度层级共享一个容量为 k 的总列表，那么在剪枝时又会被"全局分数排序"绑架，短句偏置问题马上回来。

4.2 复杂度控制和剪枝技巧

任何一个用过这个算法的朋友都会告诉你：它的计算量是实打实的。普通 beam search 每一步要做 k 次扩展；grid beam search 每一步要做"活跃长度数 × k"次扩展。如果最大长度是 60 且每步都有大量活跃假设，那每一步扩展次数可能是 60×4=240 次，是原先的 60 倍。因此做工程实现时，必须配合剪枝。

第一个有效的剪枝是"只扩展未结束前缀"。每当一个候选遇到 EOS，就把它的 ended 标志置位，后续不再扩展它。这样可以大幅减少早期就结束的短候选占用的算力。第二个剪枝是限制每个前缀的 top-v 扩展数量，v 可以设成 8 或 16，而不是在完整词表上做 softmax——这能省下大部分矩阵计算。第三个剪枝来自论文里一个很聪明的观察：如果一个长度层级的所有候选 score 相比当前最优网格候选都低了很大一个阈值（比如差了 5 个自然对数单位），这一层级的候选基本不可能在最终比较中翻盘，可以直接集体剪掉。这个阈值我在复现时设为 5.0，效果比较稳定。

如果是在一个已有的推理框架里实现，建议先算一下峰值内存。每个 hypothesis 需要保存 token ids 和累计分数，网格大小是 k×N，比普通 beam search 的 k 大了 N 倍。对 N=100、k=8 的场景，同时存的 token 序列量级在数百，规模还可以接受；但如果你用 batch 解码，这个内存会再乘 batch size，必须提前做好 buffer 分配，避免每一步都用动态 append 导致内存碎片和显存反复申请。我实测下来，PyTorch 里用 pre-allocated tensor + 手动 index 的方式，比反复构造 list 再转 tensor 要快 30% 以上。

4.3 遇到的内存爆炸与调参心得

第一次跑通 grid beam search 时很容易被显存打懵，因为大多数框架的 beam search 都是对 batch 内所有 beam 做批量前向，而 grid 模式需要分长度层级处理，batch 结构变成了"长度×宽度"的二维组合。不少实现干脆把每个长度层级单独 forward，效率很低。我的做法是：把同一时刻所有需要扩展的候选按长度排序后合并成一个 batch 的前缀 tensor，用一个 mask 记录哪些位置需要重复计算。这样前向次数可以控制在一到两次，避免掉进"网格多大，前向多少次"的陷阱。

调参方面，k（beam width）和 N（最大长度）的关系比普通 beam search 更敏感。如果 k 太小，每个长度层级内保不住有意义的多样性；如果 N 太大而语料实际长度没那么长，尾部层级大量候选处于低分状态，白白占用计算。我在模拟项目 X 上做过一组对比，任务是一个摘要生成系统，句子长度中位数在 40 左右。当我把 N 从 120 降到 80，解码时间几乎减半，万幸的是 ROUGE 没有任何下降。这说明 N 应该贴近任务实际长度上限，而不是塞一个很大的保险值。

还有一个小坑：有些框架里的 EOS 处理和普通 beam search 逻辑耦合得很深，改网格时需要把"结束的候选进入最终候选池"这一步单独抽出来。普通实现里，一个 beam 一旦 ended 就从 beam 列表剔除，不再占位；grid 模式里，ended 的候选依然要留在网格里参与最终排序，所以它的 token ids 不能释放。一开始我没注意，结果发现最终候选池永远只有当前步的扩展结果，分数特别差的句子居然能上榜。

5. 什么时候该放弃 beam search 改用 grid beam search

5.1 适合的任务画像

在动手迁移之前，我建议你先做一个快速判断：你的任务是否属于以下三类之一。

第一类是生成结果长度分布很宽的任务。比如新闻摘要，有的摘要 30 个词，有的 80 个词，长短差异极大。普通 beam search 在短句上往往过度自信，输出一批长度集中在 30 左右的摘要，而 grid beam search 能给长摘要候选足够的存活空间，最终选出信息量更完整的版本。第二类是重复生成明显的任务。机器翻译里的幻觉重复、摘要里的句子重复，很多情况下不是模型不会生成多样化内容，而是 beam search 在剪枝时把所有多样性都剪没了。grid 相当于扩大了存活面，重复候选虽然短且高分，但也无法把更长的新鲜候选挤死。第三类是低资源语言或领域。当你没有大量数据去充分训练语言模型时，模型的概率估计本身就不可靠，此时搜索算法带来的偏差占比更大，grid 的公平性优势会更突出。

反过来，如果任务是短文本分类式生成（比如意图识别里的自然语言转 SQL），或者对延迟极其敏感的在线服务，grid 的额外计算量经常不划算，普通 beam search 加一个精心调的 length penalty 就足够了。算法不是越复杂越好，关键看它解决的核心问题在不在你的任务里。

5.2 和 length normalization 的新关系

特别想说一下 grid beam search 与 length normalization 的关系。很多人误以为 grid 是对 length penalty 的替代，其实它是一个更深层的改造：它保留普通 length normalization 的"长度补偿"思想，但在搜索过程中通过网格结构避免了"提前剪枝掉长句"的问题。换句话说，length penalty 决定的是"最终怎么比较不同长度的句子"，而 grid 决定的是"搜索过程中该让哪些候选活下来"。两者不是同层的东西。

我的经验是：在 grid 模式下，最终比较用的长度补偿项不再需要像 length penalty 那样精细调 α，因为长句在搜索过程中已经被公平维护了。固定的 log(L) 补偿在大多数任务上都够用，α 反而容易画蛇添足。我在模拟项目 X 上试过额外叠加 α=0.3，结果和只做 log(L) 差别很小，但调参成本却多了一倍。所以如果要从 beam search 迁移，建议先去掉 length penalty，用纯 grid + log(L)，再加其他 tricks。

5.3 我的实践结论

整体上，grid beam search 的性价比取决于你对"稳定多样性"的需求有多高。如果你的评估指标是单一分数、模型很强、数据量很大，beam search 已经能拿到不错的结果，替换成 grid 可能只是小幅提升；但如果你做的是多模态生成、长文档摘要、或者需要后面接一个 reranker，那 grid 的候选质量改善是实打实的。它给的 top-k 内部有更多形态各异的候选项，这对后续模块是宝贵的资源。

我自己现在处理摘要类任务时，已经默认把 grid beam search 放在候选生成阶段，而不是用 beam search + 疯狂调 α。它能减少我对超参数的敏感度，让结果更可解释——至少在"为什么这个长句子最后赢了"这一点上，我可以清楚看到是因为它在长度 L 的层级里分数最高，在最终比较中又胜过了其他长度的最佳候选，逻辑链条清晰很多。

6. 一个容易踩的坑：别把"网格"做成"分层 beam search"

6.1 分层 beam search 和 grid beam search 的真实区别

网上一部分博客把 grid beam search 描述成"为每个长度分别跑一个 beam search，最后挑一个最好的"，这个说法是不准确的，也非常误导实现。如果你真的这样做，每个长度层级之间完全没有信息交互，等于用 k 倍的算力换来 k 个互不相干的搜索结果，而且完全没有解决"哪个长度的句子值得优先扩展"的问题。真正的 grid beam search，所有长度层级共享同一个模型的每次 forward 结果，并且在扩展阶段能够感知到其他层级中候选中途的 EOS 位置。

比如在解码到一个句子长度为 10 时，其中一个候选已经结束（EOS），另一个候选还在继续扩展。普通分层 beam search 会把这个 ended 候选直接放到最终池里，然后让其他活着的候选继续；但 grid 模式下，ended 候选在最终比较前一直占在网格里，而其他活跃候选继续成长。这个"占位但不死亡"的细节决定了最终比较时，你可以同时拿到一个长度为 10 的完整句和一个长度为 20 的完整句，而不是二分法式的"生或死"。

6.2 实现时怎么避免这个坑

为了避免把 grid 退化成分层 beam search，我在代码里加了一个断言检查：在每步扩展结束后，统计每个长度层级的活跃候选数总和，再对比前向计算里实际参与扩展的假设数。如果两者差距过大，说明大多数候选都被提前结束了，网格几乎失去意义。另外，在写代码时把"扩展新 token"和"记录 EOS"分成两个步骤，确保 EOS 逻辑只影响当前候选，不影响整个长度层级的删除。

如果你是从 Fairseq 或者 HF Transformers 的 generate 方法改造，特别注意它们的 return_dict_in_generate 里会把 completed sequences 单独存为一个 list。网格实现里你不要照抄这个逻辑，而是让所有序列始终存在于网格结构里，只在最终比较时统一打标。我第一次改造时就是因为沿用了"completed_seqs"的旧逻辑，结果 ended 序列被一次性冲掉，再也没有进入最终候选池，导致解码结果非常奇怪。

7. 我的一些后续想法

如果你尝到了 grid beam search 的甜头，下一步可以沿着两个方向继续玩。第一个方向是把网格和长度采样结合，在比较最终候选时不再用固定的 log(L)，而是用从语料统计出来的长度先验分布，理论上能让候选更贴近目标域的句子长度分布。第二个方向是把网格作用到树结构上，对语法树的不同子树深度做类似的"跨深度保留"，这个思路在长句生成和代码生成任务里可能比序列版本更有效。

最后分享一个我在实际使用中的小技巧：在存储 grid 时给每个候选额外记录一下"它是在哪一步首次进入网格的"，这个信息几乎不占内存，但分析模型行为时很有用。比如你能直观看到，好的长句往往是在第 15 步到第 20 步之间才被保留下来的，而垃圾长句从第 5 步开始就一直拖着低分不肯结束。这种洞察在调整 N、k 以及最终长度补偿项时，比看 BLEU 能给你更快的反馈。