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. 现有自回归模型推理速度慢，扩散语言模型（DLM）作为并行生成方案有潜力加速推理。
  2. 论文提出增强思维链（CoT）的DLM，证明其能以最优步骤模拟任何并行采样算法。
  3. 引入重掩码或修订机制，使DLM在模拟并行采样算法时达到最优空间复杂度，并提升表达能力。

📝 摘要（中文）

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

🔬 方法详解

问题定义：现有自回归语言模型在生成文本时依赖顺序解码，速度较慢。扩散语言模型（DLM）旨在通过并行生成token来加速推理过程。然而，DLM在并行采样方面的理论优势和能力边界尚不明确，尤其是在处理复杂推理任务时，如何保证效率和表达能力是一个挑战。

核心思路：论文的核心思路是通过理论分析，证明带有思维链（CoT）的DLM可以模拟任何并行采样算法，并且通过引入重掩码或修订机制，可以进一步优化DLM的空间复杂度。这种设计旨在充分发挥DLM并行计算的优势，同时保证其在复杂任务中的表达能力和效率。

技术框架：论文构建了一个并行采样的理论模型，并在此基础上分析了DLM的计算能力。主要框架包括：1) 形式化定义并行采样算法；2) 证明带有CoT的DLM可以模拟任何并行采样算法；3) 分析DLM在没有重掩码或修订机制时的空间复杂度瓶颈；4) 证明引入重掩码或修订机制可以解决空间复杂度问题，并提升表达能力。

关键创新：论文的关键创新在于：1) 首次从理论上证明了带有CoT的DLM可以作为最优的并行采样器；2) 提出了重掩码和修订机制，并证明其可以显著提升DLM的空间复杂度和表达能力；3) 建立了DLM表达能力的严格差距，证明了带有修订或重掩码的DLM比没有这些机制的DLM具有更强的表达能力。

关键设计：论文的关键设计包括：1) 使用多项式长度的CoT来增强DLM的推理能力；2) 引入重掩码机制，允许将已生成的token重新转换为掩码，以便后续步骤可以修改这些token；3) 引入修订机制，允许将已生成的token修改为其他token。这些机制的设计旨在解决DLM在并行采样过程中可能遇到的空间复杂度和表达能力瓶颈。

📊 实验亮点

论文通过理论证明，增强了思维链（CoT）的扩散语言模型（DLM）能够以最优的顺序步骤模拟任何并行采样算法。此外，论文还证明了启用重掩码或修订机制可以使DLM以最优的空间复杂度模拟任何并行采样算法，并建立了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.