Improving Diffusion Language Model Decoding through Joint Search in Generation Order and Token Space¶
会议: EMNLP 2026
论文: ACL Anthology
领域: LLM 其他
关键词: 扩散语言模型, 离散扩散, 联合搜索, 似然估计, 测试时计算
一句话总结¶
针对掩码扩散语言模型(DLM)启发式重掩码陷入探索-利用两难的瓶颈,提出在生成顺序与Token取值联合空间进行搜索与剪枝的Order-Token Search解码算法,凭借基于增量去噪动作的稳定似然评分函数,无需额外后训练即可在多项复杂推理与代码任务中取得显著精度突破。
研究背景与动机¶
离散掩码扩散语言模型(Masked Diffusion Language Models, MDMs)近期在文本生成领域展现出强劲潜力。不同于自回归模型必须受限于从左至右单向生成的因果依赖,MDM在全掩码画布上进行双向并行去噪,允许模型根据上下文以任意顺序自适应填充或修正Token。这种非自回归与顺序无关的性质,在理论上赋予了扩散模型广阔的解码轨迹空间,使得生成顺序的选择成为解码算法设计的核心自由度。
然而,现有的MDM推理方法本质上均受限于“单次运行仅提交一条单一确定性轨迹”的框架。目前主流的解码策略在轨迹多样性与局部可靠性之间呈现出明显的两极分化:低置信度重新掩码(Low-Confidence Remasking)倾向于贪婪固定局部最高置信度Token,只对不确定位置重新掩码,容易过早承诺错误路径而导致轨迹快速坍缩,产生较高的单次采样准确率(pass@1)但随采样量增加时覆盖率(pass@k)增长停滞;相反,训练期采用的随机重新掩码(Random Remasking)虽能探索多样化生成顺序并带来陡峭的pass@k增长,但缺乏在候选间择优的选择机制,导致pass@1表现极其疲软。自回归解码(AR)则完全舍弃了MDM的生成顺序自由度,局限于因果单向搜索。
要将MDM固有的多轨迹采样潜力转化为高可靠的单样本生成质量,核心矛盾在于缺乏一种兼具多轨迹探索与可靠中间状态优选的统一解码框架。传统的序列级全文本似然估计由于未决掩码过多而方差极大,无法用于中间去噪状态的有效打分。核心 idea:将离散扩散解码构建为生成顺序与Token取值联合空间中的束搜索,并提出基于增量去噪动作(结合全序列预测上下文对新揭示Token进行条件重打分)的低方差似然估计器,实现对候选轨迹的高效探索与稳定剪枝。
方法详解¶
整体框架¶
Order-Token Search(OTS)针对离散掩码扩散模型设计,在推理过程中维护大小为 \(K\) 的部分去噪候选束(beam),通过交替进行“联合动作扩展”与“似然估计剪枝”完成全局高质量解的生成。为平衡计算开销与搜索收益,方法依托块级扩散(block diffusion)范式,将整个序列划分为固定大小的块,在块内执行独立的去噪扩散,在块边界处触发束搜索的扩展与剪枝决策,从而将搜索决策次数从全部扩散步数 \(S\) 降低到块数量 \(B\)。
在每个搜索区间,算法对当前候选束中的每个状态提出多个候选去噪动作——这不仅决定了当前步填充哪些位置(顺序维度),还决定了写入什么具体标记(Token空间维度)。随后,算法通过专门设计的似然评估器对各候选的增量去噪动作计算对数似然打分,在轨迹级别累加后仅保留 Top-\(K\) 最佳候选,最终在遍历所有块后输出累积似然得分最高的完整文本。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["初始全掩码候选束<br/>K个全掩码画布状态"] --> B["块边界去噪扩展<br/>在顺序与Token空间提出候选动作"]
B --> C["增量去噪动作似然评估<br/>条件重掩码与对数似然评分"]
C --> D["轨迹级分数累积与剪枝<br/>保留Top-K最优部分轨迹"]
D -->|未达到末尾块| B
D -->|所有块去噪完成| E["最终最佳序列输出<br/>选取累积似然最高的确定解"]
关键设计¶
1. 块边界联合扩展:在生成顺序与Token空间同时分支
传统自回归束搜索仅能在固定因果位置上探索不同的候选Token,而MDM的现有启发式规则又仅沿单条轨迹运行。OTS在每个块边界处同时释放生成顺序与Token取值的双重自由度。设当前搜索区间对应从噪声较大的状态 \(x_t\) 过渡到更少噪声的中间状态 \(x_s\)(\(0 \le s < t \le 1\)),模型首先基于当前局部logits加上Gumbel噪声以温度 \(\tau\) 采样全序列去噪预测 \(x_0 \sim p_\theta(\cdot \mid x_t)\)。随后,算法根据去噪调度确定需要转移的预测Token,并定义新揭示位置集合: $\(\Delta(s, t) = \{i \mid x_{t,i} = \text{MASK} \land x_{s,i} \neq \text{MASK}\}\)$ 通过多次采样引入不同的去噪动作,模型在同一前缀下产生多个相互竞争的轨迹分支,不同分支所决定的揭示位置(顺序)与对应Token取值均可不同,从而从根本上跳出局部贪婪决策陷阱。
2. 增量去噪动作似然估计:低方差、防过度惩罚的局部动作打分
在扩散模型中,直接使用全局序列重构似然 \(p_\theta(x_0 \mid x_t)\) 评估中间候选极其不稳定:当剩余未揭示的MASK占比较大时,模型面临全局困难填空问题,其对数似然方差极大且对远端未决结构产生严重误判。OTS摒弃全序列似然,转而精确度量“当前去噪转移动作本身是否可靠”。算法首先利用当前步采样得到的全局预测 \(x_0\) 作为上下文支撑,但仅将该区间新揭示的位置 \(\Delta(s, t)\) 重新置为掩码,得到重掩码序列 \(\tilde{x}_0 = \text{mask}(x_0, \Delta(s, t))\)。在此基础上,单步动作评分定义为在模型自身预测的上下文支持下、重新预测这些新揭示Token的期望对数概率: $\(s(x_t; x_s) = \mathbb{E}_{x_0} \left[ \log p_\theta(x^{\Delta(s,t)}_0 \mid \tilde{x}_0) \right]\)$ 该设计既利用了模型当前对全局未来的最佳预测以提供上下文语境,又将评估范围严格局限在当前步所做的决策上,显著减小了打分方差,避免了中间候选仅因后续位置尚未生成而遭到全局低分误杀。
3. 轨迹级累积评分与Top-K剪枝:稳定维持全局最优解路径
为了在多阶段探索中持续跟踪最有希望的生成路径,OTS将候选状态在所有已发生的分支区间 \(I\) 上的增量评分进行线性累加: $\(S(\text{candidate}) = \sum_{(s, t) \in I} s(x_t; x_s)\)$ 累积评分反映了整条生成轨迹在每一步所做局部去噪动作的模型支持度。每次扩展产生 \(K^2\) 个潜在分支后,剪枝算法依据累积评分 \(S\) 挑选 Top-\(K\) 状态进入下一个块的去噪处理。得益于块级扩散,全过程额外似然评估前向次数仅与块数量 \(B\) 和 \(K^2\) 呈正比,将计算复杂度从朴素逐步搜索的 \(\mathcal{O}(S \cdot K^2 \cdot L)\) 大幅压缩至 \(\mathcal{O}(S \cdot K \cdot L + B \cdot K^2 \cdot L)\),在计算量与传统5样本多数投票相当的前提下,实现了结构化的高效剪枝。
损失函数 / 训练策略¶
Order-Token Search为完全免训练(training-free)的测试时推理算法,底层完全依赖预训练或后训练完成的掩码扩散语言模型(例如LLaDA-8B-Instruct、LLaDA-1.5、Dream7B)的原生去噪后验 \(p_\theta(x_0 \mid x_t)\) 输出。实验中默认块大小设为 32,束大小 \(K\) 采用 3 至 5,Gumbel噪声采样温度 \(\tau \in [0.2, 1.0]\),在去噪调度上遵循生成长度等于两倍扩散步数(\(\text{gen\_len} = 2 \times \text{diffusion\_steps}\))的标准配置。
实验关键数据¶
主实验¶
主实验在数学推理基准 GSM8K、MATH500、Countdown 以及代码生成基准 HumanEval 上全面评估,采用 LLaDA-8B-Instruct 与强化学习后训练模型 LLaDA-1.5 作为基础底座。
| 数据集 | 指标 (Avg) | 本文 (OTS, LLaDA) | 低置信度重掩码 | 随机重掩码 | 自回归 (AR) | AR + 束搜索 | 之前SOTA (diffu-GRPO, L=512) |
|---|---|---|---|---|---|---|---|
| GSM8K | Accuracy (%) | 70.1 | 67.0 | 54.2 | 62.3 | 68.7 | 81.9 (OTS: 83.3) |
| MATH500 | Accuracy (%) | 32.8 | 29.0 | 20.5 | 26.0 | 31.0 | 39.2 (OTS: 42.4) |
| Countdown | Accuracy (%) | 28.4 | 20.5 | 11.0 | 12.7 | 21.2 | 37.1 (OTS: 25.4) |
| HumanEval | Accuracy (%) | 27.4 | 20.6 | 21.1 | 23.0 | 27.3 | 34.8 (OTS: 37.2) |
| 全任务平均 | Accuracy (%) | 39.7 | 34.3 | 26.7 | 31.0 | 37.1 | - |
在强化学习后训练底座 LLaDA-1.5 上,Order-Token Search 的各任务平均准确率进一步提升至 40.4%(Low-confidence 为 34.5%,Low-conf + MV 为 37.2%,AR + beam-search 为 36.1%)。特别是在序列长度 512 的挑战性设置下,纯推理时的 OTS 甚至超越了依赖复杂强化学习微调的 diffu-GRPO(GSM8K: 83.3% vs 81.9%;MATH500: 42.4% vs 39.2%;HumanEval: 37.2% vs 34.8%)。
消融实验¶
为了验证OTS专属增量似然估计器的不可替代性,作者在相同扩展框架下对比了不同剪枝打分机制(LLaDA模型上的全任务平均准确率及具代表性的细分项):
| 配置 | 全任务平均 (%) | GSM8K (Avg) | MATH500 (Avg) | Countdown (Avg) | HumanEval (Avg) | 说明 |
|---|---|---|---|---|---|---|
| Order-Token Search (Full) | 39.7 | 70.1 | 32.8 | 28.4 | 27.4 | 基于条件增量动作评分(式3) |
| w/ OTS Future Blocks | 33.9 | 66.3 | 29.7 | 17.4 | 22.3 | 掩码未揭示未来块,无预测上下文 |
| w/ OTS All Blocks | 32.6 | 65.1 | 28.5 | 16.2 | 20.4 | 联合评估迄今所有已揭示块的似然 |
| w/ CumProb 剪枝 | 38.0 | 69.9 | 30.6 | 25.5 | 25.8 | 仅按已提交Token的对数概率累加剪枝 |
| AR-style Token Search (3x) | - | 8.5 (L=256) | 3.8 (L=256) | 0.0 (L=256) | 0.6 (L=256) | 仅搜Token且用因果前缀打分,全面崩溃 |
| AR-style Order Search (3x) | - | 79.2 (L=256) | 35.8 (L=256) | 15.2 (L=256) | 32.9 (L=256) | 仅搜顺序且用因果前缀打分,开销大 |
关键发现¶
- 增量动作似然是剪枝成功的基石:消融表明,OTS All Blocks(将所有已揭示块作为一个难任务打分)导致平均分大跌 7.1%,OTS Future Blocks(剥离对未来预测的依赖)掉点 5.8%,在组合搜索任务 Countdown 上两者准确率更是从 28.4% 腰斩至 16.2% 与 17.4%,证明在模型生成的全序列上下文下对局部动作重新评估是提供高信噪比剪枝信号的关键。
- 顺序与Token联合搜索的必要性:将块大小退化为 1 且固定左至右顺序的特例(AR + beam-search),平均精度仅为 37.1%,显著落后于全量 OTS 的 39.7%。而完全脱离MDM特性的AR-style Token Search更是导致数理推理近乎彻底瘫痪(Countdown 准确率为 0%),印证了双向并行模型无法简单套用自回归前缀打分逻辑。
- 算力扩展效率显著优于多数投票:在严格对齐函数评估次数(NFE)的算力开销下,OTS(束大小为6)在 Countdown 上达到 29.3% 准确率,而消耗同等算力的 AR + 多数投票(5样本)与随机重掩码 + 多数投票分别仅有 19.9% 与 18.4%;在束大小 4 时,OTS 耗时仅为单次启发式解码的 2-3 倍,比 5 样本多数投票快近 2 倍。
- 跨架构与更广泛推理泛化:在采用不同预训练范式的 Dream7B 模型上,OTS 依然取得 42.7% 的最高全任务均分(超越 AR+MV 的 42.2% 与 Low-conf 的 39.5%);在多步软文本推理基准 MuSR 上,OTS 达到 56.8% 准确率,大幅领先多数投票基线。
亮点与洞察¶
- 破解扩散模型测试时探索困境:敏锐指出现存启发式解码要么受制于局部置信度导致轨迹坍缩(pass@1 虚高但多采样无增益),要么盲目随机掩码产生高熵噪声(pass@k 虽高但无从拣选),首次将经典束搜索理念无缝移植到多步双向扩散轨迹空间。
- 巧妙的重掩码增量动作估算机制:不采用代价极高或高方差的全局后验评估,而是先由模型生成全序列预估作为背景,再针对当前更新块进行局部掩码反查似然,兼顾了全局语义一致性与局部动作判别力。
- 即插即用媲美强化学习后训练:纯推理期增加计算开销即可实现超越需海量强化微调资源(如 diffu-GRPO)的精度跃迁,为离散扩散模型的测试时计算扩展(Test-Time Compute)确立了全新范式。
局限与展望¶
- 推理端额外算力开销:尽管依靠块扩散控制了复杂度,但由于每个块边界需维护 \(K\) 个候选并执行 \(K^2\) 次评估,在长文本与超大束大小下仍带来 2-3 倍于单次采样的延迟。
- 对模型基础约束感知能力的依赖:在 4×4 数独(Sudoku)等需要全局强硬性约束满足的离散搜索任务中,模型原生似然打分与真实约束违背之间相关性极弱,导致包括 OTS 在内的所有解码策略均退化至接近随机水平(平均准确率仅 9-12%),说明搜索算法无法凭空创造模型本身未学习到的硬约束判别力。
- 评分函数的静态性:当前似然估计直接依赖原始语言模型的前向 logits,未来若能引入轻量级已验证判别器(如流程奖励模型 PRM)或可学习价值函数指导剪枝,有望进一步释放更复杂推理轨迹的选择精度。
相关工作与启发¶
- vs. 启发式低置信度重新掩码 (Low-Confidence Remasking):低置信度策略仅凭单次前向中的局部概率最大化贪婪推进,遇到前期局部合理但全局致命的错误路径无法回溯;OTS 通过多候选束与基于动作似然的全局前向打分,有效识别并保留多步修正路径。
- vs. 自回归束搜索 (AR Beam Search):自回归束搜索受制于因果注意力与严格单向从左到右的时间展开,仅在 Token 取值维度搜索;OTS 充分发挥离散扩散模型无序双向并行特性,在生成顺序(何时填何处)与 Token 内容双重维度联合寻优。
- vs. 多数投票 (Majority Voting / Self-Consistency):多数投票仅在最终答案层面对完全独立生成的样本做表面统计聚合,无法在生成中间阶段介入纠错;OTS 则在轨迹生成演化的关键节点主动剪除劣质分支,以更低的综合算力实现了更高的搜索采样回报率。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次系统性形式化了扩散语言模型的生成顺序与Token联合搜索空间,并设计了专用的增量去噪似然估计器。
- 实验充分度: ⭐⭐⭐⭐⭐ 跨越4个代表性数理/代码基准、涵盖2代LLaDA及Dream7B模型,进行了细致的算力对齐分析、似然诊断、多样性统计与极端边界探究。
- 写作质量: ⭐⭐⭐⭐⭐ 逻辑推导层次清晰,实验论证环环相扣,图表与附录细节详实透彻。
- 价值: ⭐⭐⭐⭐⭐ 为离散扩散语言模型在推理期的高效扩展指明了全新方向,是DLM解码领域具有里程碑意义的基础工作。