Confidence-Based Decoding is Provably Efficient for Diffusion Language Models¶

会议: NeurIPS 2026
arXiv: 2603.22248
领域: LLM 其他
关键词: 扩散语言模型, 置信度解码, 迭代复杂度, 采样加速, 信息论

一句话总结¶

本文首次为扩散语言模型（DLMs）的置信度自适应解码建立了严格的理论分析框架，证明了基于累积熵和阈值截断的解码策略能在 KL 散度 $\varepsilon$ 误差下以 $\widetilde{O}(H(X_0)/\varepsilon)$ 的期望迭代步数实现对数据分布内在复杂度的自适应采样加速。

研究背景与动机¶

离散扩散语言模型（Diffusion Language Models, DLMs）作为自回归（AR）范式的重要替代方案，通过引入吸收态掩码（Mask）构建正向破坏与反向去掩码过程，具备打破从左到右严格顺序限制以及多 token 并行生成的双重优势。在大规模预训练中，掩码预测器利用因式分解假设，在单次前向传播中独立输出所有待去掩码位置的条件边缘分布。然而，这种因式分解近似在推理采样阶段带来了不可忽视的分布偏差：如果在单步内同时揭示多个相互强依赖的 token，模型将完全忽略它们在给定已揭示上下文下的联合统计依赖性；而若退化为逐个揭示 token，虽消除了偏差却彻底丧失了并行采样的吞吐优势。

因此，决定每轮迭代中去掩码哪些位置以及批次大小的解码策略成为 DLMs 采样效率与生成质量的核心决定因素。虽然业界广泛使用的均匀随机解码方案近期已有一系列理论收敛性刻画，但工程实践中展现出卓越加速性能的置信度驱动解码（例如基于预测概率、预测熵或置信度预算自适应展开）却长期缺乏理论基础。这种自适应解码的根本分析难点在于其强耦合的随机动力学：每一步究竟揭示哪些 token、揭示多少 token，完全取决于此前已生成 token 在掩码预测器上诱导出的实时置信度，导致总迭代轮数变为未知随机停时。学术界亟待解答：基于置信度的自适应解码是否具备可证明的高效性？其采样步数能否自动自适应于目标数据分布的内在低维/低熵结构？

针对这一长期的理论空白，本文切入的角度是建立自适应揭示轨迹与信息论度量之间的对偶分析框架。核心 idea：针对累积条件熵和驱动的自适应解码策略，通过将联合分布与边缘乘积的 KL 采样误差沿随机解码轨迹分解为条件互信息之和，并构造几何倍增尺度包络消除动态停时与排列位置的统计耦合，首次证明其以 $\widetilde{O}(H(X_0)/\varepsilon)$ 期望迭代步数达成 $\varepsilon$-准确采样，实现无需超参数调优的低熵数据分布内在复杂度自适应加速。

方法详解¶

整体框架¶

本文针对掩码扩散语言模型的反向生成过程，系统分析了基于预测不确定性（熵）驱动的自适应解码机制。从全掩码序列 $Y_0 = (\mathsf{M}, \dots, \mathsf{M})$ 出发，算法在每轮迭代中通过掩码预测器评估剩余掩码位置的预测置信度，自适应动态扩展或收缩当前轮次的去掩码批次 $\mathcal{D}_t$。当处理低不确定性（低熵）区域时，算法自动贪婪打包大量 token 并行输出；遇到高不确定性分支时则自动收缩揭示数量甚至单步回退，从而在严格控制累积预测偏差的前提下实现全局采样加速。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["全掩码初始序列<br/>Y0 = (M, ..., M)"] --> B["1. 累积熵和停止准则<br/>按置信度/随机排列顺序扫描候选位置"]
    B --> C["2. 轨迹 KL 误差分解与极值隔离<br/>分离单步最大熵 token，控制互信息累积"]
    C --> D["3. 倍增尺寸包络与排列平均<br/>消除动态批次大小与插入位置的统计耦合"]
    D --> E["4. 数据熵守恒与复杂度自适应界<br/>总熵与阈值比值导出收敛迭代期望"]
    E -->|未全部去掩码| B
    E -->|所有位置完成去掩码| F["最终生成目标文本序列 YT"]

关键设计¶

1. 累积熵和停止准则：动态平衡单步并行规模与预测不确定性 为了克服固定批次大小启发式策略对上下文难度缺乏感知的问题，本文设计并重点分析了基于累积条件熵的停止机制。在第 $t$ 轮迭代中，给定前序已去掩码集合 $\mathcal{W}_{t-1}$ 及对应 token 序列 $Y_{t-1}$，算法沿候选位置遍历（分析中考虑均匀随机排列 $\Pi$ 以提供对称性），对于每个遍历到的位置 $\Pi_k$，计算模型预测的逐点条件边缘分布熵 $\mathtt{H}(p_\theta^{\Pi_k}(\cdot \mid Y_{t-1}))$。算法持续将位置纳入当前去掩码批次 $\mathcal{D}_t$，并实时累加该熵值： $$k_t \coloneqq \min \left\{ i > W_{t-1} : \sum_{k=W_{t-1}+1}^i \mathtt{H}\big(p_\theta^{\Pi_k}(\cdot \mid Y_{t-1})\big) > \eta \right\} \wedge L$$ 其中 $\eta$ 为预设的熵和预算阈值。这一设计的机制在于：在文本语义确定性极高的片段（如常见固定搭配或强因果约束），各位置预测熵极小，累加至 $\eta$ 需跨越大量 token，因而批次自动扩展实现大幅并行；而在语义分叉点或高信息量核心词处，单 token 即具有可观熵值，使得批次迅速截断，有效规避了在不确定性强时强行并行导致的错误级联与独立性假设失真。

2. 轨迹 KL 误差分解与极值隔离：单步多 token 依赖向条件互信息的转化 在分析反向采样分布 $p_{Y_T \mid \Pi}$ 与真实目标数据分布 $p_{X_0}$ 之间的 KL 散度时，核心障碍在于每轮独立生成的 token 联合边缘分布 $\prod_{i \in \mathcal{D}_t} p^i(\cdot \mid X^{\mathcal{W}_{t-1}})$ 无法捕获真分布的跨 token 依赖。本文利用信息论链式法则建立展开恒等式：对任意划分中的极值索引 $j_t \coloneqq \arg\max_{i \in \mathcal{D}_t} \mathtt{H}(X^i \mid \mathcal{W}_{t-1}, X^{\mathcal{W}_{t-1}})$，将单步批次内的联合散度放缩为剔除极值点后的互信息求和： $$\mathsf{KL}\Big(p^{\mathcal{D}_t}(\cdot \mid X^{\mathcal{W}_{t-1}}) \,\big\|\, \prod_{i \in \mathcal{D}_t} p^i(\cdot \mid X^{\mathcal{W}_{t-1}})\Big) \leq \sum_{i \in \mathcal{D}_t \setminus \{j_t\}} \mathtt{I}(X^i; X^{\mathcal{D}_t \setminus \{i\}} \mid \mathcal{W}_{t-1}, X^{\mathcal{W}_{t-1}}, \Pi)$$ 由于累积熵停止机制在累计和首次超出 $\eta$ 时立即中断，批次内最多仅允许存在一个条件熵超过 $\eta$ 的 token（即 $j_t$）。因此，对于其余所有 $i \in \mathcal{D}_t \setminus \{j_t\}$，其条件熵均受到严格的一致上界约束 $\mathtt{H}(X^i \mid \mathcal{W}_{t-1}, X^{\mathcal{W}_{t-1}}) \leq \eta$。通过将极值项从累加中隔离，确保了后续剩余项的互信息均能被严格的截断熵所均匀控制。

3. 倍增尺寸包络与排列平均：解耦动态停时与排列插入位置的统计耦合 将全局误差对各个 token 重新求和后，第 $i$ 个 token 的互信息项 $\mathtt{I}(X^i; X^{\mathcal{D}_{t_i} \setminus \{i\}})$ 与其在排列中的具体插入位置 $\Pi^{-1}_i$ 以及其实际所属的动态批次大小 $D_{t_i} = |\mathcal{D}_{t_i}|$ 存在极其复杂的相互依赖。为解耦该依赖，本文引入了辅助消除序列 $\Pi_{\smallsetminus i}$，并递归定义了几何二倍增长的尺寸包络序列 $(\overline{D}_t)_{t=1}^L$： $$\overline{D}_1 = 0, \quad \overline{D}_t = \begin{cases} \overline{D}_{t-1}, & D_{t-1} < \overline{D}_{t-1} \\ 2 D_{t-1}, & D_{t-1} \geq \overline{D}_{t-1} \end{cases}$$ 该设计的巧妙之处在于：对随机插入位置 $\Pi^{-1}_i$ 进行平均后，原本复杂的互信息期望被严格放缩为截断条件熵与包络跨越事件的乘积 $2 \mathbb{E}[(\mathtt{H}(X^i \mid \cdot) \wedge \eta) \cdot \mathbb{I}\{D_{t_i} \geq \overline{D}_{t_i}\}]$。由于尺寸包络每次触发均发生翻倍，整个采样生命周期中跨越包络的迭代步数在确定性意义下被几何增长所限制，满足 $\sum_{t=1}^L \mathbb{I}\{D_t \geq \overline{D}_t\} \leq \log_2 L + 1$。由此彻底消除了非平衡并行步长带来的累积方差膨胀，证明了全局总期望 KL 散度不超过 $4 \eta (\log_2 L + 1)$。

4. 数据熵守恒与复杂度自适应界：从信息守恒定律推导亚线性迭代上界 在保证了采样精度（通过令 $\eta = \varepsilon / [4(\log_2 L + 1)]$ 使期望 KL 散度 $\leq \varepsilon$）之后，本文利用真实数据分布的总熵分解定律对算法的总迭代步数期望 $\mathbb{E}[T]$ 建立了刚性下界支撑。根据条件熵的链式法则与抽样更新轨迹： $$H(X_0) = \mathbb{E}\left[ \sum_{t=1}^T \sum_{i \in \mathcal{D}_t} \mathtt{H}(X^i \mid \mathcal{W}_{t-1}, X^{\mathcal{W}_{t-1}}, \Pi) \right] - \mathsf{KL}(p_{X_0} \parallel p_{Y_T \mid \Pi})$$ 因为除最后一轮迭代外，前 $T-1$ 轮迭代每轮吸收的条件熵和均强制达到或超过阈值 $\eta$，代入后直接获得不等式 $H(X_0) \geq (\mathbb{E}[T] - 1)\eta - \varepsilon$。移项后立即解出期望迭代次数： $$\mathbb{E}[T] \leq 4 \left(\frac{H(X_0)}{\varepsilon} + 1\right) (\log_2 L + 1) + 1 = \widetilde{O}\left(\frac{H(X_0)}{\varepsilon}\right)$$ 这一理论界表明，当真实数据具有低熵结构（$H(X_0) \ll L$，如自然语言高度冗余的语法结构与语境约束）时，扩散语言模型的置信度解码在迭代复杂度上天然呈现对序列长度 $L$ 的亚线性甚至对数级依赖；更重要的是，这一加速完全是数据分布自适应的，无需事先预知 $H(X_0)$ 的具体数值。

实验关键数据¶

主实验¶

本文通过理论构造对比了不同解码策略在达到目标采样误差 $\varepsilon$ 时的迭代复杂度理论上界与核心结构性质对比。

解码策略类别	代表方法 / 准则	期望迭代复杂度 $\mathbb{E}[T]$	对序列长度 $L$ 依赖	是否需要预知数据分布参数
自回归解码 (AR)	Standard Autoregressive	$\Theta(L)$	严格线性 $\mathcal{O}(L)$	否（固定从左至右）
均匀随机平衡调度	Li & Cai (2025)	$O(L \cdot \sum_i I(X^i; X^{\smallsetminus i}) / \varepsilon)$	线性 $\mathcal{O}(L)$	否（均匀分配步长）
相关性最优调度	Chen et al. (2025b)	$O(\mathrm{TC}(X_0) / \varepsilon)$	亚线性至线性	是（需预估全相关性 TC/DTC）
最大单熵截断策略	Algorithm 2 (Max-Entropy)	$O\left(\sqrt{\frac{H(X_0) L}{\varepsilon}}\right)$	次线性 $\mathcal{O}(\sqrt{L})$	是（依赖 $H(X_0)$ 调节阈值与上限 $S_{\max}$）
累积熵和自适应策略	Algorithm 1 (Ours, Entropy-Sum)	$\mathbf{\widetilde{O}\left(\frac{H(X_0)}{\varepsilon}\right)}$	仅对数依赖 $\mathcal{O}(\log L)$	否（全分布自适应，免调参）

消融实验¶

为了进一步明晰不确定性度量方式对采样理论边界的影响，本文对基于最大单点熵（Algorithm 2）与基于累积熵和（Algorithm 1）的两种设计进行了严格的理论消融与性质对比分析。

解码准则配置	迭代终止判定准则	批次容量显式上限 $S_{\max}$	理论收敛上界	参数自适应性
累积熵和机制 (Full)	$\sum_{i \in \mathcal{D}_t} \mathtt{H}(X^i) > \eta$	无需显式设定上限（由熵和自然截断）	$\widetilde{O}\left(\frac{H(X_0)}{\varepsilon}\right)$	完全自适应，阈值仅依赖目标容差 $\varepsilon$ 与 $\log L$
单点最大熵机制	$\max_{i \in \mathcal{D}_t} \mathtt{H}(X^i) > \eta$	必须引入强制上限 $S_{\max} = \lfloor\sqrt{\varepsilon L / H(X_0)}\rfloor$	$O\left(\sqrt{\frac{H(X_0) L}{\varepsilon}}\right)$	不具备自适应性，超参配置必须精确已知 $H(X_0)$
无极值隔离分解 (消融)	直接使用链式互信息上界	无	边界放大至与字典大小及 $L$ 强相关	理论上界严重松弛，无法保证低熵下的收敛加速

关键发现¶

累积熵机制相比单点熵机制的理论优越性：单点最大熵策略虽然能够避免高不确定性 token 的引入，但在遭遇连续多个“中等不确定性” token 时，单点准则无法察觉误差累加，必须人为添加硬性批次上限 $S_{\max}$ 进行防御，从而引入了对序列长度 $L$ 的 $\sqrt{L}$ 显式惩罚；而累积熵和准则直接约束整批的总不确定性容量，完全摆脱了对 $L$ 的多项式依赖。
无须先验知识的天然自适应性：相较于此前优化调度工作（如 Chen et al. 2025b 依赖全相关性估计、Zhao & Cai 2026 依赖特定相关性界），累积熵和算法的超参配置 $\eta = \varepsilon / [4(\log_2 L + 1)]$ 完全与数据真实分布未知量解耦，在工程实践中极具普适性与鲁棒性。

亮点与洞察¶

将动态解码动力学映射至信息论守恒：巧妙地将离散扩散语言模型反向推理中复杂的随机停时过程与目标数据分布的固有信息熵 $H(X_0)$ 建立等式关联，从而直接从信息论第一性原理导出了迭代次数的严密下界与上界。
倍增尺寸包络（Dyadic Size Envelopes）分析工具：针对随机排列与自适应批次大小之间非对称耦合导致期望难以计算的问题，创造性地提出了二倍增长包络序列，用确定性的 $\log_2 L + 1$ 次翻倍事件优雅约束了任意非均匀批次扩张轨迹的累积方差。
对现代 DLM 启发式工程的理论奠基：为 Fast-dLLM、Entropy-bounded Unmasking 等近期在工程界表现优异的置信度贪婪采样算法提供了最直接坚实的理论合法性证明。

局限与展望¶

依赖理想掩码预测器假设：当前收敛性证明基于最优预测器假设（$p_\theta = p_{\mathrm{true}}$），尚未计入实际神经网络训练所带来的逼近误差与泛化误差传播。
分析针对随机遍历顺序而非纯贪婪排序：为了数学分析上的可积性与对称性，算法在遍历候选位置时引入了均匀随机排列 $\Pi$，而工程实践（如 Ben-Hamu et al., 2025）中通常采用完全按熵升序排序的确定性扫描。
置信度度量仅限于条件熵：目前框架主要基于香农熵建立，如何扩展至最大预测概率（Top-1 probability）、Top-2 概率裕度（Margin）等其他常用置信度指标，仍有待进一步拓展。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破 DLM 自适应置信度解码的理论分析瓶颈，填补了离散扩散自适应采样的理论空白。
实验充分度: ⭐⭐⭐⭐☆ 理论推导严密完备，虽然偏重纯理论分析未包含大规模经验实验评测，但在理论消融与对比维度上论证极为详实。
写作质量: ⭐⭐⭐⭐⭐ 概念引出自然清晰，数学符号体系严谨，证明主线中的直觉与技术技巧展现非常高超。
价值: ⭐⭐⭐⭐⭐ 为离散扩散语言模型高效推理架构的设计提供了坚实的信息论指导原则。

解码策略类别	代表方法 / 准则	期望迭代复杂度 \(\mathbb{E}[T]\)	对序列长度 \(L\) 依赖	是否需要预知数据分布参数
自回归解码 (AR)	Standard Autoregressive	\(\Theta(L)\)	严格线性 \(\mathcal{O}(L)\)	否（固定从左至右）
均匀随机平衡调度	Li & Cai (2025)	\(O(L \cdot \sum_i I(X^i; X^{\smallsetminus i}) / \varepsilon)\)	线性 \(\mathcal{O}(L)\)	否（均匀分配步长）
相关性最优调度	Chen et al. (2025b)	\(O(\mathrm{TC}(X_0) / \varepsilon)\)	亚线性至线性	是（需预估全相关性 TC/DTC）
最大单熵截断策略	Algorithm 2 (Max-Entropy)	\(O\left(\sqrt{\frac{H(X_0) L}{\varepsilon}}\right)\)	次线性 \(\mathcal{O}(\sqrt{L})\)	是（依赖 \(H(X_0)\) 调节阈值与上限 \(S_{\max}\)）
累积熵和自适应策略	Algorithm 1 (Ours, Entropy-Sum)	\(\mathbf{\widetilde{O}\left(\frac{H(X_0)}{\varepsilon}\right)}\)	仅对数依赖 \(\mathcal{O}(\log L)\)	否（全分布自适应，免调参）

解码准则配置	迭代终止判定准则	批次容量显式上限 \(S_{\max}\)	理论收敛上界	参数自适应性
累积熵和机制 (Full)	\(\sum_{i \in \mathcal{D}_t} \mathtt{H}(X^i) > \eta\)	无需显式设定上限（由熵和自然截断）	\(\widetilde{O}\left(\frac{H(X_0)}{\varepsilon}\right)\)	完全自适应，阈值仅依赖目标容差 \(\varepsilon\) 与 \(\log L\)
单点最大熵机制	\(\max_{i \in \mathcal{D}_t} \mathtt{H}(X^i) > \eta\)	必须引入强制上限 \(S_{\max} = \lfloor\sqrt{\varepsilon L / H(X_0)}\rfloor\)	\(O\left(\sqrt{\frac{H(X_0) L}{\varepsilon}}\right)\)	不具备自适应性，超参配置必须精确已知 \(H(X_0)\)
无极值隔离分解 (消融)	直接使用链式互信息上界	无	边界放大至与字典大小及 \(L\) 强相关	理论上界严重松弛，无法保证低熵下的收敛加速