扩散语言模型之间的并行性、临界窗口和分离

扩散大型语言模型 (dLLM) 的一个流行卖点是其并行能力：能够比自回归模型更有效地生成文本序列，自回归模型需要每个标记一次前向传递。然而，在 dLLM 的许多竞争范式中，从掩模到均匀到高斯扩散，对这些不同提案如何并行比较的原则性理解仍然有限。在这项工作中，我们对这三种主要方法之间的并行能力进行了细粒度的比较，并证明了以下内容： - 均匀和高斯扩散可以在许多前向传递中进行采样，这些前向传递与底层分布的对偶总相关性成比例，这是一种内在复杂性的度量，可以比上下文长度小得多。此前，人们只知道如何使用掩模扩散来实现这一点。 - 对于某个随机经验测量系列，我们表明 $\widetildeθ(\sqrt{d})$ 前向传播对于使用均匀或高斯扩散进行采样是必要且充分的，但存在近似分数预言，其中掩蔽扩散需要 $\widetildeΩ(d)$ 前向传播。这在三种流行的 dLLM 范式之间建立了第一个可证明的并行分离。与流行的直觉相反，即掩蔽扩散更难并行化，因为它们必须致力于标记值，后者的分离来自这样一个事实：掩蔽扩散采样中的关键窗口比均匀和高斯扩散采样中的临界窗口渐近更窄。