如果你经常跟 seq2seq 模型打交道一定经历过这种纠结beam size 设成 5 还是 10length 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 k4最大长度 N20那么网格里最多同时存在 4×20 80 个活跃候选而普通 beam search 到任意时刻最多只会维护 4 个候选。每走一步模型遍历所有还没结束的候选把它们扩展出新的 token生成的新句子长度就变成了 L1。然后对所有长度为 L1 的新候选排序截断到该长度自己的 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], score0.0, endedFalse) 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, t1)): 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×4240 次是原先的 60 倍。因此做工程实现时必须配合剪枝。第一个有效的剪枝是只扩展未结束前缀。每当一个候选遇到 EOS就把它的 ended 标志置位后续不再扩展它。这样可以大幅减少早期就结束的短候选占用的算力。第二个剪枝是限制每个前缀的 top-v 扩展数量v 可以设成 8 或 16而不是在完整词表上做 softmax——这能省下大部分矩阵计算。第三个剪枝来自论文里一个很聪明的观察如果一个长度层级的所有候选 score 相比当前最优网格候选都低了很大一个阈值比如差了 5 个自然对数单位这一层级的候选基本不可能在最终比较中翻盘可以直接集体剪掉。这个阈值我在复现时设为 5.0效果比较稳定。如果是在一个已有的推理框架里实现建议先算一下峰值内存。每个 hypothesis 需要保存 token ids 和累计分数网格大小是 k×N比普通 beam search 的 k 大了 N 倍。对 N100、k8 的场景同时存的 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 记录哪些位置需要重复计算。这样前向次数可以控制在一到两次避免掉进网格多大前向多少次的陷阱。调参方面kbeam 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 search5.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 search6.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 能给你更快的反馈。