「 breadcrumbs 与闪电：在离散迷宫中找到捷径的人」——GADD如何用Gibbs采样打破离散扩散模型的速度诅咒

"如果一个人不能把事情简化到大学一年级的水平，那说明他自己也没有真正理解。"
——理查德·费曼

"在迷宫中，最聪明的做法不是跑得更快，而是找到 breadcrumbs 的正确用法。"
——我瞎编的，但费曼大概会同意

🌫️ 一、引子：那个从乱码中写诗的盲人

想象一个盲人站在一间巨大的图书馆里。他的手边有一本空白的书，一支笔，以及一个奇怪的规则：他每次只能写一个字母，而且写完之后必须立即判断——这个字母让整个句子"更像一首诗"还是"更像乱码"？

如果像诗，保留。如果像乱码，擦掉重写。

这就是扩散模型（Diffusion Model）在做的事情。只不过这个"盲人"不是人，是神经网络；那间图书馆不是真的，是数学定义的概率空间；而判断"像不像诗"的标准，是一个叫做得分函数（Score Function）的东西——它告诉你，在当前这团模糊的文字中，朝着哪个方向走会让它更接近一首真正的诗。

在连续世界里（比如图像），这个盲人走得相当顺畅。因为图像是实数构成的，每一步微调都像在调色板上轻轻拨动旋钮——亮一点、暗一点、蓝一点、红一点。你可以走得很小步、很优雅，像芭蕾舞演员踮着脚尖旋转。

但在离散世界里（比如文本、分子结构、音乐符号），情况完全不同。

文本不是"稍微改一点"就能变好的。你不能把字母'a'微调成字母'b'的中间态——那既不是a也不是b，只是一团无意义的符号。在离散世界里，每一步都是跳跃：从a跳到b，从"猫"跳到"狗"，从C大调跳到G小调。没有中间地带，没有渐变色，只有非此即彼的决断。

这就是为什么，当扩散模型试图在离散世界中"写诗"时，它经常需要成千上万步才能从完全的乱码（均匀随机噪声）收敛到一首可读的诗歌。就像那个盲人，每次只能凭感觉换掉一个词，然后祈祷这个词让整首诗离目标更近了一点点。

本文要讲的故事，是关于三个数学家如何给这个盲人一把神奇的 breadcrumbs——让他不再在迷宫中随机摸索，而是沿着一条有标记的捷径，以对数级别的步数找到出口。

这把 breadcrumbs 叫做 GADD。

🔢 二、基础：扩散模型到底在扩散什么？

2.1 从热咖啡到冷咖啡

在理解GADD之前，我们需要先理解扩散模型最基本的思想。而理解扩散模型，最好的比喻是一杯热咖啡。

想象你有一杯刚冲好的热咖啡，表面的奶泡形成了清晰的拉花图案——一颗爱心，或者一片叶子。这是你的目标：你想让AI生成的东西，就像这杯拉花咖啡一样精致、有意义。

但扩散模型的训练过程，是让这杯咖啡逐渐冷却、搅拌、扩散，直到拉花图案完全消失，变成一杯均匀、浑浊、毫无特征的褐色液体。这个过程叫做前向扩散（Forward Diffusion）。

然后，模型学习逆向过程：给定一杯浑浊的咖啡，如何一步一步地恢复出原始的拉花图案？这就是反向扩散（Reverse Diffusion）。

训练完成后，模型可以从一杯纯粹的"随机噪声咖啡"（均匀分布的褐色液体）开始，通过多步去噪，最终"生成"一杯有拉花的咖啡。

在连续世界（图像）中，这个"搅拌"和"恢复"的过程用随机微分方程描述，优雅而高效。数学家们已经证明，如果你足够小心地控制每一步的步长，可以用相对较少的步数（比如20-50步）完成整个生成过程。

2.2 但文本不是咖啡

文本生成的问题在于：你不能"稍微搅拌"一个词。

在图像扩散中，每个像素值是0到255之间的实数，你可以把它从100改成101，图像几乎看不出来变化。但在文本中，"猫"和"狗"之间没有任何中间态。你无法"轻微地"把一个token从"猫"变成"狗"——你只能 直接替换。

这就引出了 离散扩散模型 的核心数学框架：连续时间马尔可夫链（Continuous-Time Markov Chain, CTMC）。

想象你有一个长度为 \(d\) 的句子，每个位置 \(i\) 上有一个来自大小为 \(S\) 的词汇表的token（比如 \(S=50257\)，这是GPT的词汇表大小）。整个系统的状态空间是巨大的：\(S^d\) 种可能的句子。对于 \(d=128\) 和 \(S=50257\)，这个空间的大小超过了宇宙中的原子数量。

前向过程定义了一个 速率矩阵 \(R_t(x,y)\)，它描述在时间 \(t\) 时，状态 \(x\) 变成状态 \(y\) 的瞬时概率。对于 均匀速率模型（Uniform-rate model），这个矩阵有一个简洁的形式：

这里的 \(\text{Ham}(x,y)=1\) 表示 \(x\) 和 \(y\) 只在 一个token位置 上不同（汉明距离为1）。也就是说，在任何时刻，每个token都有 \(\frac{1}{S}\) 的概率被随机替换成词汇表中的另一个token。

这个设计的优点是非常对称、数学上很干净。缺点也恰恰来自这个对称性：每个token独立同质地演化，没有任何结构性的先验来指导它们。随着时间推进，所有token逐渐变得完全随机、相互独立，最终收敛到均匀分布——就像一杯被充分搅拌的咖啡，每个分子位置都完全随机。

2.3 反向过程：盲人摸象

反向过程的目标是：给定一个完全随机的句子（每个位置均匀随机），逐步"去噪"，让它恢复成一句有意义的语言。

精确的反向速率由以下公式给出：

其中 \(q_t(x)\) 是在时间 \(t\) 时处于状态 \(x\) 的真实概率。问题是我们不知道 \(q_t(x)\) 的精确值——如果知道，就不需要生成模型了。

所以神经网络被训练来估计这个 密度比 \(\frac{q_t(y)}{q_t(x)}\)，这被称为 得分函数（Score Function）或 Concrete Score：

然后我们用估计的得分来近似反向过程：

这就是 Euler方法 离散化的基础：给定当前状态 \(x_{t_{k+1}}\)，通过估计的反向速率采样下一个状态 \(x_{t_k}\)，逐步回溯到 \(t=0\)。

但这里有一个根本性的问题：在离散世界里，每一步我们只能改变 一个token。而判断改变哪个token、改成什么，需要参考整个句子的上下文。这就像盲人每次只能摸到大象的一个部位，却要判断整头大象的形状。

🐌 三、均匀速率的诅咒：为什么离散扩散像蜗牛爬

3.1 步数的代价

在连续扩散模型（如图像生成）中，20-50步通常就能产生高质量的样本。但在离散扩散中，均匀速率模型通常需要 数百甚至数千步。

为什么会这样？

想象你在玩一个文字版的"二十问"游戏。每次你问一个问题，系统只能回答"是"或"否"——但在离散扩散中，你连提问的资格都没有。你只能随机选一个位置，随机换一个词，然后祈祷这个词让整句话离目标更近。

更糟的是，均匀速率模型的设计意味着：每个token在每一步都有概率被随机打乱。即使有些token已经接近正确了，它们仍然可能被"误伤"而重新变回噪声。这就像你辛辛苦苦拼好了一半的拼图，一阵风吹过，又打乱了几块。

现有的加速方法大致分为两类：

第一类：训练额外的量。 比如训练一个专门的预测器来估计更优的步长，或者学习一个更复杂的采样策略。这些方法有效，但需要额外的计算资源和训练数据。

第二类：Predictor-Corrector框架。 先用一个大胆的预测器大步前进，然后用一个校正器修正误差。比如CTMC Corrector [7]，它通过叠加一个修正速率来减少离散化误差。但这些方法的理论复杂度仍然是 \(O(\text{poly}(\varepsilon^{-1}))\)——也就是说，要达到误差 \(\varepsilon\)，所需步数与 \(\varepsilon\) 的多项式成反比。如果你想让误差从0.1降到0.01（10倍更精确），步数可能要增加100倍。

3.2 复杂度鸿沟

让我们看看理论上的差距有多夸张。

注意到关键区别了吗？

所有现有方法，步数复杂度中 \(\varepsilon\) 都出现在 分母 里——而且是多项式级别。这意味着：精度要求每提高一个数量级，步数就要增加一个多项式倍数。

而GADD的复杂度中，\(\varepsilon\) 出现在对数里——\(\log^2(1/\varepsilon)\)。这意味着：精度要求提高一个数量级，步数只增加一个对数倍数（大约2-3倍，而不是100倍）。

这就像从北京到上海：

• 其他方法是步行，速度固定，距离每增加10倍，时间增加10倍。
• GADD是坐飞机，距离每增加10倍，时间只增加一点点（因为飞机速度也快了）。

从 \(O(\text{poly}(\varepsilon^{-1}))\) 到 \(O(\text{polylog}(\varepsilon^{-1}))\)，这不是渐进意义上的"好一点"——这是质的变化，是从"不可行"到"可行"的跨越。

⚡ 四、GADD的顿悟： breadcrumbs 的秘密

4.1 一个关键的观察

GADD的作者们问了一个简单却深刻的问题：

如果我们已经训练了一个神经网络来估计得分函数 \(s_t(y,x)\)，我们真的需要额外的训练或复杂的校正器来加速采样吗？

答案是不需要。

得分函数 \(s_t(y,x)\) 编码了关于目标分布 \(q_t\) 的完整信息。如果我们能从得分函数中提取出条件后验分布 \(q_t^i(x_i | x^{-i})\)——即在给定其他所有token的情况下，位置 \(i\) 应该是什么token——我们就可以直接在这个条件分布上采样，而不需要小心翼翼地一步步走。

这就是Gibbs采样（Gibbs Sampling）的核心思想。

4.2 什么是Gibbs采样？

想象你在拼一个1000块的拼图。你一块一块地检查，每次只看一块，问自己："给定周围所有已经拼好的块，这块最可能是什么图案？"

你不需要同时考虑所有1000块——你只需要轮流看每一块，在每次只看一块的"局部视图"中做出最优选择。神奇的是，如果你重复这个过程足够多次，最终你会收敛到正确的拼图。

这就是Gibbs采样。它是一个迭代算法，每次只更新一个变量（这里是token），条件于其他所有变量当前值。数学上，Gibbs采样在更新变量 \(i\) 时，从以下分布中采样：

其中 \(x^{-i}\) 表示除位置 \(i\) 以外的所有token。

4.3 GADD的核心创新：从得分构造后验

传统上，Gibbs采样需要你直接知道条件分布 \(q_t^i(\cdot | x^{-i})\)。但在扩散模型中，我们只有得分函数 \(s_t(y,x)\)。怎么办？

GADD的作者们发现了一个惊人的事实：

条件后验 \(q_t^i(x_i | x^{-i})\) 可以直接从得分函数构造出来，无需额外训练！

具体来说，考虑所有与当前状态 \(x\) 汉明距离为1的状态 \(y\)（即只改变一个token的状态）。对于每个位置 \(i\) 和每个可能的token \(a\)，定义 \(y = x^{-i} \oplus_i a\)（将位置 \(i\) 改为 \(a\)）。那么：

这个公式说的是：条件后验概率，正比于得分函数在所有可能替换上的总和的倒数。

另一个等价的估计器（论文中的公式(8)）是：

这两个估计器的关键性质是：它们只使用已经训练好的得分函数，不需要任何额外的网络、额外的训练数据或额外的损失函数。

这就像你发现，你一直拥有的那把钥匙，不仅能开锁，还能当指南针用——只是之前没人注意到这个额外的功能。

4.4 算法全貌

GADD的算法非常简洁：

算法: GADD
─────────────────────────
输入: 随机初始化的句子 x_T
      得分函数估计 s_t
      离散化时间点 {t_k}
      每步校正次数 {L_k}

对于每个时间步 k = N-1 到 0:
    z_0 = Euler更新(x_{t_{k+1}})  // 大胆的预测
    对于 ℓ = 1 到 L_k:            // Gibbs校正循环
        随机选一个位置 i
        用得分函数构造后验 q_t^i(·|z_{ℓ-1}^{-i})
        从后验中采样新token: z_ℓ^i ~ q_t^i
        固定其他位置不变
    x_{t_k} = z_{L_k}             // 校正后的状态
返回 x_{t_0}

这个算法的结构是典型的 Predictor-Corrector 框架：

• Predictor（Euler步）：大胆预测下一步在哪里，像运动员起跳。
• Corrector（Gibbs步）：用小步精细调整，像外科医生缝合。

但和传统Predictor-Corrector不同的是，GADD的Corrector不是修正"离散化误差"，而是直接采样条件后验。这使得校正步骤的理论性质完全不同——它达到了精确Gibbs采样的效果，而不是近似。

4.5 系统扫描变体：一次调用，全部更新

论文还提出了一个更高效的变体：系统扫描GADD（System-Scan GADD）。

关键观察是：现代神经网络的单次前向传播可以输出所有位置的得分——输出形状是 \((B, d, S)\)，其中 \(B\) 是batch大小，\(d\) 是序列长度，\(S\) 是词汇表大小。这意味着：一次前向传播就包含了构造所有位置后验所需的全部信息。

因此，在Gibbs循环的每一步，我们可以：

1. 用一次前向传播获得所有位置的得分。
2. 并行构造所有 \(d\) 个位置的后验。
3. 并行从所有后验中采样新token。

这样，每个Gibbs步只需要一次得分评估（NFE, Number of Function Evaluations），而不是 \(d\) 次。这在实际实现中大大降低了计算开销。

🧮 五、理论的胜利：为什么 polylog 不是魔法，而是数学

5.1 归纳论证的力量

GADD的理论分析之所以能达到 \(O(\text{polylog}(\varepsilon^{-1}))\) 的复杂度，核心在于一个归纳论证（Induction Argument），而不是传统的Girsanov测度变换技术。

让我用人话解释这个证明思路：

目标：证明在每个时间步 \(t_k\)，校正后的分布 \(\hat{p}_{T-t_k, L_k}\) 与真实分布 \(q_{t_k}\) 的总变差距离（TV distance）不超过 \(\varepsilon\)。

归纳假设：假设在下一步 \(t_{k+1}\)，这个条件已经满足（TV距离 ≤ ε）。

需要控制的误差有三部分：

1. 继承误差：从 \(t_{k+1}\) 继承来的误差（归纳假设说这部分 ≤ ε）
2. 移动目标误差：分布 \(q_t\) 本身随时间变化（因为前向过程在持续演化）
3. 预测器步误差：Euler离散化引入的近似误差

证明的关键在于：Gibbs采样的收敛速度是指数级的。

具体来说，如果Gibbs核的谱间隙（Spectral Gap）为 \(\rho_{t_k}\)，那么经过 \(L_k\) 步Gibbs采样后，分布与目标分布的距离呈指数衰减：

要让这个距离 ≤ ε，所需的Gibbs步数大约是：

这里 \(\rho_{t_k}\) 是谱间隙，\(M\) 是得分函数的上界，\(S\) 是词汇表大小，\(\delta\) 是最小时间步长。

对于"良结构"的分布（比如高温Ising模型），谱间隙 \(\rho^* = \Omega(\text{poly}^{-1}(d))\)，即与维度 \(d\) 的多项式成反比。在这种情况下：

关键来了：poly(d) 与 ε 无关，而 polylog(ε^{-1}) 与 d 无关。这意味着：

• 对于固定的维度 \(d\)，提高精度 \(\varepsilon\) 只需要对数级别的额外步数。
• 对于固定的精度 \(\varepsilon\)，增加维度 \(d\) 需要多项式级别的额外步数。

这与现有方法形成鲜明对比：现有方法的复杂度是 \(O(\text{poly}(d) \cdot \text{poly}(\varepsilon^{-1}))\)，精度项是多项式而不是对数。

5.2 为什么CTMC校正器做不到

论文还专门分析了CTMC Corrector [7] 的理论限制。即使在完美得分估计的理想情况下，CTMC校正器的总步数仍然满足：

注意分母中的 \(\varepsilon^2\)——这是多项式依赖，不是对数依赖。

原因在于：CTMC校正器本质上是在离散时间中模拟一个连续时间的马尔可夫过程。这个离散化本身引入了不可忽略的误差，无论你多小地取步长，这个误差都与步长成比例。而要补偿这个误差，你需要更多的步数。

GADD则不同：它直接使用Gibbs采样，而Gibbs采样是离散时间算法的精确实现，没有连续到离散的近似误差。这就是为什么GADD能达到 polylog 而CTMC corrector只能做到 poly。

🎵 六、实验：当理论照进现实

6.1 合成实验：验证理论预测

论文首先在合成数据上验证了理论预测。他们构造了两类数据分布：

1. 自回归型：每个token的概率依赖于前 \(h=2\) 个token，模拟语言的结构依赖性。
2. 混合点模型：稀疏的单例混合，支持集大小 \(O(d)\)，模拟"尖峰"分布（某些特定配置概率极高）。

实验结果（图1）显示：

• 在相同的NFE（函数评估次数）下，GADD的最终误差显著小于Vanilla Euler和\(\theta\)-Trapezoidal。
• 这直接与定理1的理论预测一致：\(O(\text{polylog}(\varepsilon^{-1}))\) 对比 \(O(\text{poly}(\varepsilon^{-1}))\)。
• 在与纯Gibbs采样器的对比中，GADD在尖峰目标分布上表现尤为出色。这是因为纯Gibbs在尖峰分布上混合很慢——就像在一个几乎全是死胡同的迷宫里找出口。而GADD利用反向扩散过程获得了一个"热启动"效应，让Gibbs采样器从一个已经比较接近目标的初始状态开始，大大加速了混合。

6.2 文本生成：让离散扩散写诗

论文在真实文本生成任务上评估了GADD。实验设置：

困惑度（Perplexity）是衡量语言模型生成质量的常用指标——越低越好，表示模型对真实文本的"惊讶程度"更低。

表2的部分数据（从论文提取）：

关键观察：

• 低NFE区域（32-64步）：GADD的优势最为明显。在NFE=32时，其他方法的困惑度还在300以上（接近随机水平），而GADD已经能产生相对合理的文本。
• 高NFE区域（256步）：所有方法都收敛到较好的困惑度，但GADD仍然保持领先。
• 墙上时间：GADD不仅困惑度更低，而且计算效率更高——系统扫描变体让每个Gibbs循环只需一次前向传播。

6.3 零样本条件音乐生成

论文还展示了GADD在零样本条件音乐生成上的应用。这意味着：模型没有专门为音乐生成任务训练，而是直接使用在文本上训练的通用离散扩散模型，通过条件采样生成音乐符号序列。

这展示了GADD的通用性：它不依赖于特定领域的先验知识，而是作为一种通用的加速技术，可以应用于任何使用均匀速率离散扩散模型的场景。

🔮 七、尾声：离散世界的新纪元

7.1 这不是渐进改进，这是范式转换

从技术史的角度看，GADD的意义远不止于"让离散扩散模型快一点"。

回顾扩散模型的发展：

• 2020年：DDPM [15] 在连续图像领域取得突破
• 2022-2023年：离散扩散模型开始出现（D3PM [24], SEDD [29], MDLM [18] 等）
• 2024-2025年：加速方法涌现（CTMC corrector [7], \(\theta\)-leaping [21] 等），但复杂度仍卡在 \(O(\text{poly}(\varepsilon^{-1}))\)
• 2026年：GADD首次达到 \(O(\text{polylog}(\varepsilon^{-1}))\)

这个复杂度上的跨越意味着什么？

意味着 离散扩散模型首次在理论效率上可以与自回归模型竞争。自回归模型（如GPT系列）的生成是 \(O(d)\) 的——生成 \(d\) 个token需要 \(d\) 步。离散扩散模型如果也能做到 \(O(d \cdot \text{polylog}(\varepsilon^{-1}))\)，那它在效率上就不再是劣势。

更重要的是，离散扩散模型有一个自回归模型不具备的优势：并行性。在扩散模型中，所有token在去噪过程中可以同时被考虑（通过得分函数的全局依赖性），而自回归模型必须严格从左到右一个一个生成。

GADD让离散扩散模型在保持并行优势的同时，达到了可接受的步数复杂度。这为未来的大规模并行文本生成、分子设计、代码生成等应用场景打开了大门。

7.2 未解的问题

当然，GADD并非万能。论文坦诚地指出了若干局限：

1. 谱间隙依赖：理论复杂度依赖于分布的谱间隙 \(\rho^*\)。对于某些"病态"分布（低温Ising模型、强多模态分布），谱间隙可能指数级小，导致GADD的效率下降。

2. 得分函数质量：GADD的效果严重依赖于得分函数的估计质量。如果神经网络没有充分训练，或者分布本身就很难建模，GADD的构造后验可能不准确。

3. 维度诅咒的残留：虽然 \(O(\text{polylog}(\varepsilon^{-1}))\) 是关于精度的，但 \(O(\text{poly}(d))\) 的维度依赖仍然存在。对于超长序列（比如整本书），这个多项式依赖可能仍然很重。

4. 与掩码方法的竞争：对于文本等特定领域，掩码离散扩散（如MDM [18]）通过设计"掩码token"来简化结构，在实践中可能更高效。GADD的优势主要在均匀速率模型上最为明显，而均匀速率模型的设计初衷是为了图生成、分子生成等不能简单掩码的领域。

7.3 一个更广阔的视角

GADD的故事，其实是一个关于 "已有工具的隐藏能力" 的故事。

神经网络被训练来估计得分函数——这是它的"本职工作"。但GADD的作者们发现，这个得分函数里还藏着另一层信息：条件后验分布。你不需要训练新网络，不需要设计新损失函数，不需要收集新数据。你只需要换一种方式看同一张地图。

这让我想起费曼的一个故事。他在洛斯阿拉莫斯参与曼哈顿计划时，被要求计算一组复杂的积分。其他物理学家花了几周时间用传统的级数展开方法计算。费曼看了一眼，说："这可以用路径积分做。"然后他花了一个下午就得到了答案。

不是因为他算了更快——而是因为他看到了问题的另一种结构。

GADD也是这样。它没有让计算机跑得更快，而是让问题变得更容易。从 \(O(\text{poly}(\varepsilon^{-1}))\) 到 \(O(\text{polylog}(\varepsilon^{-1}))\)，这不是算力的胜利，这是洞察的胜利。

📚 参考文献

[1] Dongyoon Hahm, Dylan Hadfield-Menell, and Kimin Lee. "Alignment Tampering: How Reinforcement Learning from Human Feedback Is Exploited to Optimize Misaligned Biases." ICML 2026.

[2] Huawei Lin, Peng Li, Jie Song, Fuxin Jiang, and Tieying Zhang. "MUSE-Autoskill: Self-Evolving Agents via Skill Creation, Memory, Management, and Evaluation." arXiv:2605.27366, 2026.

[3] Yuchen Liang, Ness Shroff, and Yingbin Liang. "From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models." arXiv:2605.27352, 2026. (本文)

[4] Jonathan Ho, Ajay Jain, and Pieter Abbeel. "Denoising Diffusion Probabilistic Models." NeurIPS, 2020.

[5] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. "Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions." NeurIPS, 2021.

[6] Aaron Lou, Chenlin Meng, and Stefano Ermon. "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution." ICML, 2024. (SEDD)

[7] Qi Zhang, Yifei Wang, and Yisen Wang. "How to Train Your Discrete Diffusion Model: A Tutorial." arXiv, 2024. (CTMC Corrector)

[8] Alan A. K. Hartmann and Matteo Palassini. " bounds on the running time of gibbs sampler." Physical Review E, 2002. (Gibbs采样谱间隙理论)

[9] Richard Feynman. The Feynman Lectures on Physics. 1963.

#论文 #arXiv #扩散模型 #离散采样 #GADD #Gibbs采样 #复杂度理论 #AI生成 #文本生成 #音乐生成 #小凯