Diffusion Language Models are Provably Optimal Parallel Samplers

📄 arXiv: 2512.25014v1 📥 PDF

作者: Haozhe Jiang, Nika Haghtalab, Lijie Chen

分类: cs.LG, cs.CC

发布日期: 2025-12-31

💡 一句话要点

提出基于思维链的扩散语言模型，实现最优并行采样并提升空间复杂度。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 扩散语言模型 并行采样 思维链 重掩码 修订 空间复杂度 文本生成 理论分析

📋 核心要点

  1. 现有自回归模型推理速度慢，扩散语言模型并行生成token具有潜力，但缺乏理论基础。
  2. 论文提出带思维链的扩散语言模型，证明其能以最优步骤模拟并行采样算法，提升效率。
  3. 通过引入重掩码或修订机制，进一步优化扩散语言模型的空间复杂度，并验证了其有效性。

📝 摘要（中文）

扩散语言模型(DLMs)作为一种通过并行token生成加速推理的有前景的自回归模型的替代方案而出现。本文通过形式化并行采样模型，为这种优势提供了严格的基础，并表明增强了多项式长度思维链(CoT)的DLM可以使用最优数量的顺序步骤来模拟任何并行采样算法。因此，每当目标分布可以使用少量顺序步骤生成时，就可以使用DLM以相同数量的最优顺序步骤生成该分布。然而，在没有修改先前显示的token的能力的情况下，带有CoT的DLM仍然会产生较大的中间占用空间。本文证明，启用重掩码(将未掩码的token转换为掩码)或修订(将未掩码的token转换为其他未掩码的token)以及CoT，可以使DLM以最佳空间复杂度模拟任何并行采样算法。本文进一步通过建立严格的表达性差距来证明修订的优势：具有修订或重掩码的DLM比没有修订或重掩码的DLM具有更强的表达能力。本文的结果不仅为DLM作为最有效的并行采样器的前景提供了理论依据，而且提倡在DLM中启用修订。

🔬 方法详解

问题定义：现有自回归语言模型在生成文本时，需要串行生成每个token，推理速度较慢。扩散语言模型(DLMs)通过并行生成token，有望加速推理过程。然而，DLMs的并行采样能力缺乏理论支撑，且在处理复杂任务时可能面临空间复杂度过高的问题。

核心思路：论文的核心思路是证明带有思维链(CoT)的DLM可以有效地模拟任何并行采样算法，从而为DLM的并行推理能力提供理论基础。此外，通过引入重掩码(remasking)和修订(revision)机制，优化DLM的空间复杂度，使其能够以更少的资源完成任务。

技术框架：论文构建了一个并行采样的理论模型，并证明了带有CoT的DLM可以模拟该模型。具体来说，DLM首先生成一段CoT，然后基于CoT并行生成目标token。为了优化空间复杂度，论文提出了两种增强机制：重掩码允许将已生成的token重新掩盖，而修订允许修改已生成的token。

关键创新：论文的关键创新在于：1) 提供了DLM作为并行采样器的理论证明，表明其在一定条件下可以达到最优的采样效率；2) 提出了重掩码和修订机制，有效降低了DLM的空间复杂度；3) 证明了带有重掩码或修订的DLM比没有这些机制的DLM具有更强的表达能力。

关键设计：论文中CoT的长度设置为多项式级别，以保证DLM能够模拟复杂的并行采样算法。重掩码和修订的具体实现方式取决于具体的DLM架构，但其核心思想都是允许模型在生成过程中动态调整已生成的token，从而优化资源利用率。损失函数的设计需要考虑CoT和目标token的生成质量，以及重掩码和修订操作的合理性。

📊 实验亮点

论文通过理论分析证明，带有思维链的扩散语言模型可以模拟任何并行采样算法，并达到最优的采样效率。此外，通过引入重掩码和修订机制，显著降低了DLM的空间复杂度，使其在处理复杂任务时更具优势。论文还证明了带有重掩码或修订的DLM比没有这些机制的DLM具有更强的表达能力。

🎯 应用场景

该研究成果可应用于各种需要快速文本生成的场景，例如机器翻译、文本摘要、对话系统等。通过利用DLM的并行采样能力，可以显著提升生成速度，从而改善用户体验。此外，该研究提出的重掩码和修订机制，有助于降低DLM的计算资源消耗，使其能够在资源受限的设备上运行。

📄 摘要（原文）

Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive models for faster inference via parallel token generation. We provide a rigorous foundation for this advantage by formalizing a model of parallel sampling and showing that DLMs augmented with polynomial-length chain-of-thought (CoT) can simulate any parallel sampling algorithm using an optimal number of sequential steps. Consequently, whenever a target distribution can be generated using a small number of sequential steps, a DLM can be used to generate the distribution using the same number of optimal sequential steps. However, without the ability to modify previously revealed tokens, DLMs with CoT can still incur large intermediate footprints. We prove that enabling remasking (converting unmasked tokens to masks) or revision (converting unmasked tokens to other unmasked tokens) together with CoT further allows DLMs to simulate any parallel sampling algorithm with optimal space complexity. We further justify the advantage of revision by establishing a strict expressivity gap: DLMs with revision or remasking are strictly more expressive than those without. Our results not only provide a theoretical justification for the promise of DLMs as the most efficient parallel sampler, but also advocate for enabling revision in DLMs.