[Paper] 扩散语言模型是可证明的最优并行采样器

发布: 2周前 (2026年1月1日 GMT+8 02:03)

8 min read

原文: arXiv

Source: arXiv - 2512.25014v1

概述

扩散语言模型（DLM）被宣传为一种快速、并行的传统自回归生成器的替代方案。本文首次提供了严格的证明，表明在配备适度的链式思考（CoT）提示时，DLM 可以匹配任何并行采样算法所需的最优顺序步骤数——本质上实现了并行生成速度的理论极限。

正式的并行采样框架 – 引入了一个简洁的数学模型，用于衡量并行令牌生成的顺序深度和内存占用。
DLM + CoT 的最优性证明 – 表明加入多项式长度 CoT 的 DLM 能以最少的顺序步骤模拟任何并行采样器。
空间最优扩展 – 证明加入 重新掩码（将已生成的令牌重新转为掩码）或修订（更改已生成的令牌）后，DLM 也能实现最优的内存使用，而不仅仅是最优深度。
表达能力层次结构 – 展示了严格的区分——带有修订或重新掩码的 DLM 严格强于普通 DLM，确立了这些特性的明确理论优势。
实用设计指南 – 提供了将现有并行采样器（例如块式或分块生成）转化为 DLM 兼容过程的具体算法方案。

Parallel Sampling Model – 作者将 parallel sampler 定义为一系列回合，每个回合同时决定一子集的 token。测量的两个关键资源是：
- Sequential depth（需要多少回合）
- Space footprint（在回合之间必须保持“活跃”的 token 数量）。
Chain‑of‑Thought Augmentation – CoT 是一种确定性的、多项式长度的辅助序列，模型可以在生成主要输出之前读取。作者证明，适当地构造 CoT 可以编码任意 parallel sampler 的控制流，使 DLM 能够遵循相同的逐回合决策。
Remasking & Revision Operators – 通过扩展 diffusion 转移核以允许：
- Remasking：将已揭示的 token 再次变为 mask；
- Revision：用另一个 token 替换已揭示的 token，
  模型可以“撤销”早前的选择，从而减少中间记忆需求。
Simulation Theorems – 通过构造性归约，论文展示了如何将任意 parallel algorithm 映射到遵循最优 depth（并且在额外操作下实现最优 space）的 diffusion 过程。
Expressivity Proofs – 通过归约和反例，作者确立了扩展的 DLM 能表示 vanilla DLM 证明上无法表示的分布。

方面	Vanilla DLM	DLM + CoT	DLM + CoT + Remasking/Revision
顺序深度	可能大于最优值	对任何并行采样器都匹配最优深度	相同的最优深度
空间（中间标记）	可能爆炸（Θ(n) 对于 n‑标记序列）	最坏情况下仍然很大	实现最优空间（Θ(depth)）
表达能力	受限于在没有标记修订的情况下可实现的分布	表达能力没有提升	严格更具表达力（能够实现 vanilla DLM 不可能的分布）

这些定理保证，如果目标分布可以在 k 个并行轮次中生成（例如，块级生成时 k = log n），则配备 CoT（可选地加上 remasking/revision）的 DLM 也恰好需要 k 个顺序扩散步骤——不会引入额外的延迟。

更快的 LLM API – 服务提供商可以用基于扩散的解码取代自回归解码，而不会牺牲延迟，尤其是对已经支持低深度并行算法的工作负载（例如块状生成、前缀引导采样）。
内存受限的边缘设备 – 空间最优的扩展意味着扩散模型可以在 RAM 受限的设备上运行（如手机、嵌入式 AI 芯片），同时仍能并行生成长序列。
CoT 提示工程工具 – 该证明提供了一种系统化构造编码并行控制流的 CoT 提示的方法，为“程序化提示”打开新途径，即提示本身可以调度采样计划。
支持修订的解码器 – 允许对 token 进行覆盖的实现（例如通过第二次扩散或轻量编辑层）可以兼顾速度和更高的表达能力，对代码生成等常需事后编辑的任务具有吸引力。
并行采样器基准测试 – 该理论框架提供了原则性的基准：任何新的并行解码策略都应与 DLM 所证明的最优深度/空间界限进行比较，为进展提供明确的衡量标准。