跳转至

Improving Diffusion Language Model Decoding through Joint Search in Generation Order and Token Space

会议: EMNLP 2026
论文: ACL Anthology
领域: LLM 其他
关键词: 扩散语言模型, 离散扩散模型, 轨迹搜索, 解码算法, 似然估计

一句话总结

针对扩散语言模型启发式重掩码陷入单一轨迹或盲目探索的困境,本文提出联合搜索生成顺序与 Token 取值的 Order-Token Search 算法,通过增量去噪动作似然估计器实现稳定剪枝,在数学推理与代码基准上显著超越现有解码策略及 GRPO 后训练。

研究背景与动机

离散掩码扩散模型(Masked Diffusion Models, MDMs)近年来作为自回归架构的关键替代方案迅速崛起。与传统自回归模型严格受限于从左至右的因果生成顺序不同,MDMs 在去噪生成时具备独特的“顺序无关性”(order-agnostic decoding):模型在每个去噪步并行预测所有被掩码位置的分布,并自适应决定先揭示哪些位置、保留哪些掩码。这种天然的灵活性赋予了扩散模型广阔的轨迹探索空间,解码过程中生成顺序与 Token 赋值的选择因而成为决定最终输出质量的核心变量。

然而,现有的 MDMs 解码策略在生成时均固守单条轨迹,在探索与利用(exploration-exploitation)之间呈现出严重割裂。以低置信度重掩码(Low-confidence Remasking)为代表的贪心策略过早固化高置信度 Token,仅反复修改不确定位置,极大压缩了解码轨迹的多样性,导致模型容易陷入局部次优错误,表现为 pass@1 尚可但随采样次数 \(k\) 增加 pass@k 增长停滞;相反,训练所用的随机重掩码(Random Remasking)虽大幅提升了生成轨迹的多样性并取得了极高的 pass@k 上限,却缺乏可靠的质量判别机制,单次生成质量(pass@1)表现极差。

这暴露出当前解码机制的核心矛盾:模型潜在具备解决复杂问题的多轨迹潜力,但单一固定轨迹解码要么过度利用陷入死胡同,要么盲目探索缺乏甄别。核心 idea:通过维护部分去噪状态的 Beam 集合,在生成顺序与 Token 取值的联合空间中显式分支探索,并设计针对增量去噪动作的条件似然估计器进行稳定剪枝,将 MDMs 丰富的采样空间潜力转化为确定性更高的单次高精度输出。

方法详解

Order-Token Search(OTS)借鉴束搜索(Beam Search)思想,但专门针对离散扩散模型的并行、去中心化去噪动态进行重构。算法在每个离散生成阶段同步探索“更新什么位置”与“填入什么 Token”,并交替执行动作展开与轨迹剪枝。

整体框架

OTS 从完全被掩码的状态开始,维护包含 \(K\) 个候选状态的 Beam 集合。在预设的搜索区间内,算法并行对候选序列进行多步去噪展开,采样多种不同的去噪动作生成扩增候选集;随后,借助增量动作似然估计器计算每条局部轨迹的累积置信度得分,剪枝保留 Top-\(K\) 候选,最终在所有去噪块完成后输出累计似然最高的完整序列。为了平衡搜索效果与计算复杂度,算法基于分块扩散(Block Diffusion)机制在块边界处触发联合搜索。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入 Prompt 与全掩码序列<br/>初始化 K 个 Beam 候选"] --> B["分块扩散推进<br/>Block Diffusion 逐步去噪"]
    B --> C["联合动作分支展开<br/>采样生成顺序与 Token 赋值"]
    C --> D["增量去噪动作似然评估<br/>条件重掩码似然打分"]
    D --> E["局部轨迹累计剪枝<br/>保留 Top-K 优质候选"]
    E -->|未达到序列终点| B
    E -->|生成全部块| F["输出全局最高似然生成序列"]

关键设计

1. 联合动作分支展开:在生成顺序与 Token 空间的同步搜索

传统自回归 Beam Search 只能沿从左至右的固定顺序枚举候选词表,而现有 MDM 解码器要么固定从左至右、要么贪心锁定置信位置,无法兼顾顺序灵活性与赋值多样性。OTS 在搜索展开步利用模型在当前掩码状态下预测的分布,加入 Gumbel 噪声进行多样化采样,一次性确定一组被揭示位置(生成顺序)及其对应的预测 Token 值(Token 空间),派生出 \(K^2\) 个竞争性的局部候选状态。这一机制从根本上打破了启发式单轨迹假设,使得算法能够同时评估多条截然不同的解题路径。

2. 增量去噪动作似然评估:消除全局不确定性干扰的局部打分器

在剪枝阶段,直接计算未完成状态到最终干净序列的全局对数似然会导致极大方差,因为当序列中存在大量 MASK 时,模型面对的是极其困难的全局填空任务,与其训练时擅长的小步去噪目标严重失配。OTS 放弃了整体序列似然,转为对产生该状态的增量去噪动作(Denoising Action)进行打分。对于从噪声较多状态 \(x_t\) 到较少状态 \(x_s\) 的转移,记新增揭示的位置集合为 \(\Delta(s, t)\),将该步全序列预测样本 \(x_0\) 在 \(\Delta(s, t)\) 处重新掩码得到 \(\tilde{x}_0\),其评分函数定义为:

\[s(x_t; x_s) = \mathbb{E}_{x_0 \sim p_\theta(\cdot \mid x_t)} \left[ \log p_\theta \left( x_0^{\Delta(s,t)} \mid \tilde{x}_0 \right) \right]\]

该函数衡量了模型在自身预测的上下文支持下,重新预测出这些新揭示 Token 的自信程度。由于它仅评估当前区间内的局部微小改动,方差极小且跨候选具有严格可比性。

3. 局部轨迹累计剪枝与分块控制:线性可控的计算开销优化

若在离散扩散的每一个扩散步 \(S\) 上都执行全量分支展开,时间复杂度将达到 \(\mathcal{O}(S \cdot K^2 \cdot L)\),计算开销极其昂贵。OTS 结合分块扩散技术(Block Diffusion),仅在块边界处(共 \(|B|\) 个块)执行分支与剪枝,在块内部则独立执行贪心去噪。候选状态通过累加各个搜索区间的增量分数构建轨迹总得分:

\[S(\text{candidate}) = \sum_{(s,t) \in \mathcal{I}} s(x_t; x_s)\]

这一设计将算法复杂度大幅压降至 \(\mathcal{O}(S \cdot K \cdot L + |B| \cdot K^2 \cdot L)\)。在标准实验设定下(\(S = L/2, |B| = L/32, K = 4\)),OTS 的函数评估次数(NFE)约为 \(2.5 L^2\),与广泛使用的 5 样本多数投票(Majority Voting)处于同等算力预算,但换来了显著更高的单次推理精度。

实验关键数据

主实验

在代表性开源扩散大模型 LLaDA-8B-Instruct 与强化学习后训练模型 LLaDA-1.5 上,评估 GSM8K、MATH500、Countdown 与 HumanEval 四大基准(取各序列长度的平均精度):

模型 / 方法 GSM8K (Avg) MATH500 (Avg) Countdown (Avg) HumanEval (Avg) 全任务平均 (Avg)
LLaDA (8B)
Low-confidence 67.0 29.0 20.5 20.6 34.3
Low-conf + MV (5 samples) 70.7 29.7 20.7 20.9 35.5
Random remasking 54.2 20.5 11.0 21.1 26.7
Random + MV (5 samples) 68.6 26.8 12.7 22.7 32.7
AR + beam-search 68.7 31.0 21.2 27.3 37.1
diffu-GRPO (Post-training) - 36.6* (len=256) 31.3 (len=256) 39.0 (len=256) -
Order-Token Search (本文) 70.1 32.8 28.4 27.4 39.7
LLaDA-1.5
Low-confidence 67.7 28.8 19.8 21.7 34.5
Low-conf + MV (5 samples) 73.0 31.3 22.5 22.0 37.2
AR + beam-search 71.3 29.9 18.1 24.9 36.1
Order-Token Search (本文) 72.2 33.8 28.0 27.6 40.4

消融实验

在 LLaDA 与 LLaDA-1.5 上对剪枝似然估计器进行系统消融(评估不同打分机制对最终平均性能的影响):

| 剪枝评分机制 | LLaDA 总体平均 | LLaDA Countdown | LLaDA-1.5 总体平均 | LLaDA-1.5 Countdown | 说明 | |---|---|---|---|---| | Order-Token Search (本文) | 39.7% | 28.4% | 40.4% | 28.0% | 基于预测上下文评估增量动作 \(\Delta(s, t)\) | | OTS Future Blocks | 33.9% | 17.4% | 35.3% | 19.2% | 掩码所有未揭示未来块,仅依前文打分 | | OTS All Blocks | 32.6% | 16.2% | 34.0% | 18.4% | 联合计算历史全部已揭示块的全局填空似然 | | CumProb (累积 Token 概率) | 38.0% | 25.5% | 38.7% | 26.3% | 仅累加已提交 Token 的单步对数概率 |

关键发现

  • 显著超越单轨迹基准与自回归解码:在 LLaDA-8B 上,OTS 总体平均精度达到 39.7%,相较最优基准 AR + beam-search(37.1%)提升 2.6%,相比扩散基础 Low-confidence(34.3%)大幅提升 5.4%,在 MATH500、Countdown、HumanEval 等多步约束推理任务上全面刷新 SOTA。
  • 优于昂贵的 RL 后训练:OTS 纯推理端算法在 512 序列长度下达成了超越 diffu-GRPO 的性能表现(GSM8K: 83.3% vs 81.9%, MATH500: 42.4% vs 39.2%),证明了测试期结构化搜索的巨大收益。
  • 增量动作似然是剪枝基石:消融表明,若退化为全历史评估(All Blocks)或缺少预测未来上下文(Future Blocks),总体性能急剧下滑 5-7 个百分点,在强搜索任务 Countdown 上精度暴跌近 12%,证实了增量条件打分器的低方差特性至关重要。

亮点与洞察

  • 将扩散模型解码形式化为顺序与 Token 联合搜索:敏锐指出了离散扩散模型在生成顺序上的特有自由度,跳出自回归束搜索的左至右枷锁,实现了兼顾次序探索与候选选择的高维搜索框架。
  • 巧妙的重掩码动作似然设计:通过对局部被揭示 Token 进行单步重掩码与条件概率校验,绕开了全局未决序列似然评估的高方差陷阱,为并行生成模型提供了可靠的剪枝梯度。
  • 等算力下更高的效率转化率:不同于简单粗暴的独立多采样多数投票,OTS 将算力用于竞争性假设检验与早剪枝,在相同 NFE 下实现了显著更优的性能曲线。

局限与展望

  • 推理时间算力开销:尽管分块策略控制了复杂度,但相较于单次贪心解码仍需 2-3 倍的 Wall-clock 时间,在严苛低延迟场景下存在权衡。
  • 强全局硬约束任务的边界效应:论文在数独(Sudoku)测试中发现各解码方法均无法超越随机猜测基线,表明当底层模型本身无法捕捉全局行列互斥约束时,仅靠推理期搜索无法无中生有,依赖模型底层先验的准确度。
  • 静态评分器可学习化:当前剪枝打分器采用固定的无监督似然,未来可探索训练轻量级判别器或强化学习奖励模型进行协同导向。

相关工作与启发

  • vs Low-confidence Remasking / Random Remasking: 传统重掩码策略只产生单一固定轨迹,Low-confidence 过早收敛导致低 pass@k,Random 盲目发散导致低 pass@1。OTS 结合两方长处,以 Beam 多样化采样驱动探索,以动作似然剪枝实现精确收敛。
  • vs Autoregressive Beam Search: 自回归搜索将顺序锁定为一维从左到右,本质是 block_size = 1 的特例;OTS 释放了解码顺序与位置选择的自由度,充分激发了扩散模型双向全序列注意力的潜力。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 首次针对离散扩散模型提出顺序与 Token 联合维度的解码搜索算法并解决打分难题
  • 实验充分度: ⭐⭐⭐⭐⭐ 覆盖代码与数学四大评测集,横跨不同基座模型、消融实验、计算复杂度分析及失败案例剖析
  • 写作质量: ⭐⭐⭐⭐⭐ 动机阐述清晰透彻,图表直观,公式与算法逻辑严密自洽
  • 价值: ⭐⭐⭐⭐⭐ 为扩散语言模型的推理期计算缩放(Test-time Scaling)树立了极具参考价值的基准范式