扩散语言模型可实现最优并行采样，理论证明其效率上限。
Diffusion Language Models are Provably Optimal Parallel Samplers
- 通过多项式长度思维链，实现最优序列步数的并行采样。
- 引入重掩码或修订机制后，空间复杂度也达最优。
- 首次证明带修订的扩散模型表达力更强，适合高效生成场景。
扩散语言模型（DLMs）作为一种新兴范式，可通过并行生成令牌实现比自回归模型更快的推理。本文通过形式化并行采样模型，证明：当DLM结合多项式长度的思维链（CoT）时，可使用最优序列步骤模拟任意并行采样算法。因此，只要目标分布可用少量序列步骤生成，DLM即可用相同数量的最优步骤生成。然而，若无法修改已揭示的令牌，带CoT的DLM仍会产生较大中间占用。我们进一步证明，启用重掩码（将未掩码令牌转为掩码）或修订（将未掩码令牌转为其他未掩码令牌）与CoT结合后，可实现最优空间复杂度的任意并行采样模拟。我们还建立严格表达力差距：具备修订或重掩码能力的DLM严格强于无此能力者。结果不仅为DLM作为最高效并行采样器提供理论支撑，更倡导在DLM中引入修订机制。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。