第 19 章 · Module 6: 离散与语言扩散

离散扩散:在 token 上加「噪」

Gaussian 噪声不适合 token,怎么办。


19. 离散扩散:在 token 上加「噪」

主源:CMU 10799 S26 Lecture 12(Discrete Diffusion & Masked Diffusion)+ Lecture 13(Discrete Flow Matching & Edit Flow,回顾段)。chunks #1550, #1623–1641,共 20 段。

📌 TL;DR

到目前为止我们做的全部 diffusion 都建立在一个非常隐蔽的假设之上:数据是连续向量、噪声是高斯。但文字、蛋白质序列、分子图——这些都是离散 token。给「the cat sat on the mat」加 $\mathcal{N}(0, \sigma^2)$ 是没意义的:「the」加上 0.3 之后是什么?

离散扩散给出的答案:把"加噪"重新定义为在 K 类 vocabulary 上的马尔可夫链。前向过程不再是连续 SDE,而是一个 $K \times K$ 的转移矩阵 $Q_t$:

$$q(x_t \mid x_{t-1}) = \mathrm{Cat}\!\big(x_t \mid Q_t \, x_{t-1}\big)$$

把 token 写成 one-hot 向量 $x \in \{0,1\}^K$,$Q_t \, x_{t-1}$ 就是"从当前 token 跳到任意 token"的概率向量。多步累乘有闭式:$\bar Q_t = Q_t \cdots Q_1$,于是 $q(x_t \mid x_0) = \mathrm{Cat}(x_t \mid \bar Q_t x_0)$——和 DDPM 的 $q(x_t \mid x_0) = \mathcal{N}(\sqrt{\bar\alpha_t} x_0, (1-\bar\alpha_t) I)$ 长得一模一样,只是把高斯换成 categorical。

$Q_t$ 怎么选,就决定了"噪声"是什么:

  • Uniform:每步以小概率 $\beta_t$ 把 token 替换成均匀随机 token。终点是均匀分布。
  • Absorbing / MASK:每步以 $\beta_t$ 把 token 替换为特殊的 [MASK]。终点是「全 MASK」序列。这是最简单、也是和 BERT 衔接最自然的设计——CMU 讲师称它为"the easiest way to do discrete diffusion"。
  • Argmax / Gaussian-like:把 categorical 嵌入到连续空间、做连续扩散、再 argmax 回来。

反向网络 $p_\theta(x_{t-1} \mid x_t)$ 是 categorical,训练损失依然是 ELBO——但通过重参数化(reparameterization),最后落到一个跨所有 token 的 cross-entropy。讲师反复强调一句话:「在所有 discrete diffusion 论文里,核心套路都是把要学的东西重参数化成可以直接从前向过程和 clean-data 估计出来的形式」。

承上启下:本章是 D3PM(Austin et al. 2021)的核心。下一章 第 20 章会专门讲 Masked Diffusion 与 SEDD(score-entropy 损失);第 21 章把这套机器接到大语言模型(Diffusion-LM、LLaDA、MDLM、DiffuLLaMA)。

一、为什么 Gaussian 噪声救不了 token

前面整本书的 diffusion 都跑在连续数据上:图像像素是 0–255 的实数,加 $\epsilon \sim \mathcal{N}(0, I)$ 自然合理,去噪也只是回归一个连续向量。CMU L12 一开场就把这个问题摆出来:

"so far we have learned about pretty much everything about diffusion models … for image generation specifically." —— 讲师在 L12 第一页就提醒:到目前为止的全部技术,都是为图像这样的连续模态打造的(chunk #1550)。

而 token 是 categorical(类别型)的:

  • 「the」是 vocabulary 第 1729 号 token,「cat」是第 4631 号;这些数字是标签,不是数值。
  • 「the + 0.3 噪声」是什么?1729.3 号 token?没这个东西——这个 id 根本不在词表里。
  • token 之间没有"距离"的概念——「cat」和「dog」在 embedding 空间里靠不靠近,是语义层面的事,不是 token id 上加减能定义的。token id 的排列顺序通常完全是约定俗成的(BPE 频次排序、字母序…),1730 号 token 完全可能是「pneumonia」而不是「they」。
  • 更要命的:图像里"灰度从 0 到 255"是连续渐变,一张图加一点高斯噪声看起来"像是同一张图、有一点雪花"——肉眼分得出。但「the cat sat on the mat」往「the cat sit on the mat」一字之差,已经从"语法正确"跳到"语法错误",状态空间根本没有"轻微抖动"这个区域。

同样的麻烦也出现在蛋白质序列(20 种氨基酸的 categorical 串)和分子图(节点是离散原子类型、边是离散键类型)。这些都不是孤立的小众场景——它们是当今 AI4Science 最热门的几个生成任务。

所以第一步问题就是:在一个有限的、无序的状态空间上,"加噪"到底是什么? 整个第六模块就是在回答这个问题。本章先讲最基础的 D3PM 框架(Austin et al. 2021),它是后面 SEDD、MDLM、LLaDA 的共同祖先。

⚠️ 不要试图"嵌入了再加高斯"草草了事:你确实可以把每个 token 用一个连续向量表示(embedding),然后在向量上跑 DDPM,最后 argmax 回 token。这条路有人走(叫 argmax flow / continuous embedding diffusion),但它把"在 token 上加噪"的问题外包给了 embedding 学习——embedding 学得好就行,学得不好你就毁了语义。本章讲的是直接在离散状态上定义扩散,不绕道。

二、第一性原理:把 token 写成 one-hot,把"加噪"写成矩阵乘法

CMU 讲师在 L12 一开始做的第一件事,是把 categorical 数据变成线性代数。原话:「we talked about how to add noise to text and how to represent it in like a vector slash matrix form, and how we can build a diffusion-esque forward process with this vector and matrix representation of the text」(chunk #1624)。

2.1 token 的向量化

vocabulary 大小为 $K$。把每个 token 写成 $K$ 维的 one-hot 向量:

$x = \texttt{the}$(id 1729)$\Rightarrow x \in \{0,1\}^K$,第 1729 位为 1、其余为 0。

这一步看似平凡,但它把"token"从离散符号变成了 $K$ 维 simplex 上的一个顶点(simplex = 所有概率向量构成的凸集,即所有非负且加起来等于 1 的向量)。一旦进了 simplex,就可以谈"概率分布"、"线性变换"、"期望"——所有连续 diffusion 的工具就能借过来用。可以这么记忆:

  • 「token = simplex 顶点」(确定性、纯净);
  • 「token 上的分布 = simplex 内部一点」(不确定性、混合)。

加噪的过程,就是把状态从顶点 → 内部点 → 慢慢挪到另一个特殊位置(uniform 中心或 MASK 顶点)的过程。

2.2 "加噪"= 在 simplex 上的随机游走

所谓"加噪",就是把 $x$ 从一个 simplex 的顶点挪到 simplex 内部的某个点,再从这个分布里采样得到下一个 token。注意这里"两步":先把状态分布挪到 simplex 内部(线性变换得到一个概率向量),再从这个分布里采样得到下一个 token(重新落到 simplex 顶点)。讲师在 chunk #1629–1630 多次强调:"this transition matrix is a jump"——它代表的是单次"跳"的随机机制,不是某种连续平移。

一步前向定义为:

$$q(x_t \mid x_{t-1}) = \mathrm{Cat}\!\big(x_t \mid Q_t \, x_{t-1}\big)$$

其中 $Q_t \in \mathbb{R}^{K \times K}$ 是 转移矩阵:

  • $(Q_t)_{ji}$ = "在 $t$ 时刻,从 token $i$ 跳到 token $j$ 的概率";
  • 每一列之和为 1(合法的条件概率分布);
  • $Q_t x_{t-1}$ 是 $K$ 维概率向量,第 $j$ 位代表"$x_t$ 是 token $j$ 的概率";
  • $\mathrm{Cat}(p)$ = 以 $p$ 为概率向量的 categorical 分布,采样得到一个 token id。

这里和 DDPM 的一个深层对应:DDPM 用 $\sqrt{\alpha_t} x_{t-1} + \sqrt{\beta_t} \epsilon$ 描述一步前向,本质是"在像素值上做加权混合";D3PM 用 $Q_t x_{t-1}$ 描述一步前向,本质是"在 token 分布上做线性混合"。两者数学上都是"线性变换 + 噪声"——只是噪声从高斯换成了 categorical 采样。

📝 记号约定:不同论文里 $Q_t$ 有的是"行随机"(行和 1)有的是"列随机"(列和 1)。讲师本人也提到「all the columns or all the rows depending on which convention that you choose to use」(chunk #1628)。本章统一用列随机—$Q_t \, x_{t-1}$ 写成矩阵乘列向量。看其它论文时认准这个约定。

2.3 多步累乘:$\bar Q_t$ 闭式

和 DDPM 一样,多步前向也有闭式:

$$q(x_t \mid x_0) = \mathrm{Cat}\!\big(x_t \mid \bar Q_t \, x_0\big), \quad \bar Q_t = Q_t \, Q_{t-1} \cdots Q_1$$

因为马尔可夫链每步的条件概率叠加,等价于转移矩阵相乘。这点直接对应 DDPM 里 $\bar\alpha_t = \prod_{s=1}^t \alpha_s$ —— 一个是连续乘积、一个是矩阵连乘。

💡 结构同源:把 DDPM 的"$\sqrt{\bar\alpha_t} x_0$(保留多少原信号)+ $(1-\bar\alpha_t)$ 噪声"换成"$\bar Q_t x_0$(把 one-hot 经过 $t$ 步矩阵打散后的概率向量)"——同一个故事,换了一个数学对象。本章后面所有推导都是这个替换的具体执行。

三、$Q_t$ 怎么选?「噪声类型」的全部秘密

DDPM 里只有一种"噪声"——高斯——所以前向过程几乎没有设计空间。但 discrete diffusion 里,$Q_t$ 的形状本身就是一个设计空间。不同的 $Q_t$ 给出完全不同的"噪声物理"。讲师在 L13 回顾时点出 (chunk #1637):「You can choose uniform, you can choose all mask, you can choose anything」。下面把三种主流选择讲清楚。

3.1 Uniform 噪声:终点是均匀分布

最朴素的选择:

$$Q_t = (1 - \beta_t) I + \frac{\beta_t}{K} \mathbf{1} \mathbf{1}^\top$$

含义:每步有 $1-\beta_t$ 概率不动,有 $\beta_t$ 概率等概率换成任意一个 token。直觉上就像一台不挑食的"打乱机"——每个时间片随机抽签,抽中就把当前 token 替换成词表里任意一个。$\beta_t$ 是抽签的次数密度(越接近终点抽得越频繁)。

多步极限 $\bar Q_\infty$ = 行列都是 $1/K$ 的矩阵 → $x_T$ 服从 $K$ 类均匀分布。换句话说,"完全加噪后的状态" = 从词表中均匀采一个 token。把这个状态喂给反向网络,它从模型角度看不到任何信息——所有可能 token 等概率。

优点:对称、各 token 平等,理论分析最干净。
缺点:模型最后只能从均匀先验起步生成,提供的信息几乎为零,所以反向第一步几乎全靠"运气";同时,从形式上 $Q_t$ 是稠密的——每一行每一列都有非零元——词表 50K 的话,朴素地存 $Q_t$ 是 $50000 \times 50000$ 即 25 亿浮点数,10 GB 内存。这是讲师在 chunk #1631 里被同学问到的痛点:「it already seems like a very big matrix」,讲师回答「It is」。第 8 节会专门讲怎么避免显式存它。

3.2 Absorbing / MASK:终点是「全 MASK」序列

引入一个特殊 token [MASK](吸收态,absorbing state)。$Q_t$ 设计为:

  • 每步有 $1 - \beta_t$ 概率不动;
  • 每步有 $\beta_t$ 概率跳到 MASK;
  • 一旦跳到 MASK 就永不离开(吸收态:$Q_t \, e_{\text{MASK}} = e_{\text{MASK}}$,也就是 MASK 这一列只有自己那个位置是 1)。

对应的 $Q_t$ 几乎是单位矩阵,只在 MASK 行/列有几个非零元——结构极其稀疏,不需要存 $K \times K$ 矩阵:只要记住 $\beta_t$ 和 MASK 的位置就够了。这就是为什么 absorbing 是实际能跑的方案,它从根上规避了 50K vocabulary 的矩阵爆炸。

多步极限:所有 token 最终都被吸收成 MASK,$x_T$ = 「[MASK] [MASK] [MASK] ... [MASK]」。可以把它想象成一张白纸:信息全部被擦掉了,但结构(句子长度)保留。反向网络从这张白纸出发,一格一格往里填字。

"lastly we talked about like the easiest way to do discrete diffusion which is mask diffusion language modeling. Basically you always you try to interpolate between your clean data and the full mask, and then you just try to construct a discrete diffusion model like that." —— CMU L13 开场回顾(chunk #1625)

讲师反复用 "the easiest way" 形容它。原因:

  1. 转移矩阵稀疏,免去 $K \times K$ 的内存灾难;
  2. 语义直观:从「完全 mask 的句子」一步步填回 clean text,本质上就是 BERT 的 masked language modeling 极限版——BERT 一次性 mask 15%,masked diffusion 在 $t=T$ 时 mask 100%,并把这个过程连续化成 $T$ 步;
  3. 反向网络好学:只需要预测「现在是 MASK 的位置,clean token 是什么」,本质就是一个填空任务。"未被 mask 的位置"提供上下文,模型只对 mask 位置做分类——这正是 BERT 已经被验证非常擅长的目标。
  4. 采样物理直观:反向过程像在写一封"先打草稿、再逐步补字"的信。每一步只需要决定"这一格我现在要不要把 MASK 替换成具体 token"——决策是局部、稀疏的,不需要"改写已经写好的字"。

3.3 Embedding + 高斯 + Argmax

第三条路:把每个 token 嵌入到 $d$ 维连续空间,在 embedding 上跑标准 DDPM(高斯噪声),生成时再 argmax 回最近的 token。讲师没有把它当作主流,因为这本质上是"绕开了"discrete diffusion 的真正问题——它没有在 token 层面定义噪声,而是把 token 替换成了 token 的连续替身。当 embedding 学得不好时,argmax 步骤会丢掉大量信息:高斯噪声把 embedding 推到 "cat" 和 "cot" 中间的位置,argmax 落到哪个完全是巧合,而连续空间里那种"靠近但不等于"的渐变全部丢掉。

本章剩下的部分聚焦在第一、二条路——它们才是 D3PM 框架的本体。

Uniform 噪声:终点 = 均匀分布 Absorbing / MASK:终点 = 全 MASK t=0 t=T/2 t=T the cat sat on mat the xq sat py zk qr wb jx vt uy 每步 β 概率换成
词表里任意 token 终态:均匀随机字符串 t=0 t=T/2 t=T the cat sat on mat the [M] sat [M] mat [M] [M] [M] [M] [M] 每步 β 概率被吸收成 [MASK] 终态:全 [MASK] 序列

四、连续时间版:转移矩阵 → rate matrix

到目前为止 $t$ 是离散的($t = 0, 1, 2, \ldots, T$)。CMU 在 L13 进一步把它推到连续时间,得到 CTMC(Continuous-Time Markov Chain,连续时间马尔可夫链)。讲师原话(chunk #1627):「the continuous time formulation that correspond to this transformation is what we call the continuous time Markov chain or CTMC」。

4.1 从转移矩阵到 rate matrix

在连续时间下,"一步跳 vs 不跳"的概率融成每单位时间的跳变率 $q_t(y \mid x)$(rate matrix,$K \times K$)。两个约束:

  • 非对角元 $q_t(y \mid x) \geq 0$($y \neq x$):从 $x$ 跳到 $y$ 的速率不能为负;
  • 列和为 0:$\sum_y q_t(y \mid x) = 0$,即对角元 $q_t(x \mid x) = -\sum_{y \neq x} q_t(y \mid x)$。

讲师(chunk #1628–1629):「all the columns or all the rows … all the transitions should add up to zero. And this is literally just a conservation of mass.」—— "流出去的"和"流进来的"相抵销,整个 simplex 上概率守恒。

ℹ️ 类比:rate matrix 就是 "velocity"。讲师在 chunk #1630 直接说出来了:「this QT thing is like a transition mixtures that represent a jump essentially. … this QT is is the flow. It's a velocity, right?」——把 CTMC 跟 flow matching 对应起来:连续 flow 的 velocity 在离散 CTMC 里就是 rate matrix。这个对应在第 16 章 flow matching之后看格外亲切。

4.2 Kolmogorov 方程:离散版「连续性方程」

概率分布 $p_t$ 怎么随时间演化?讲师(chunk #1632):

"the infinitesimal change in probability is equal to literally the amount of probability that comes into this particular state, minus the probability that go out of this state."

写成数学:

步骤 1:朴素流入流出 $$\frac{d p_t(x)}{dt} = \sum_{y \neq x} q_t(x \mid y) \, p_t(y) \;-\; \sum_{y \neq x} q_t(y \mid x) \, p_t(x)$$ Why:第一项 = 从所有别的 state $y$ 流入 $x$ 的总速率;第二项 = 从 $x$ 流出到所有别的 state 的总速率。直觉上就是"水槽进水量减出水量"。
步骤 2:用守恒律合并 利用 $q_t(x \mid x) = -\sum_{y \neq x} q_t(y \mid x)$,第二项可写成 $-q_t(x \mid x) \, p_t(x)$,即可把 $y = x$ 也纳入第一项的求和: $$\frac{d p_t(x)}{dt} = \sum_y q_t(x \mid y) \, p_t(y)$$ Why:讲师在 chunk #1633 现场让学生回答的就是这个化简——「this negative sum thing is just qxx … so just sum of all the z's and then qzx ptz」。
步骤 3:写成矩阵形式 $$\boxed{\frac{d p_t}{dt} = Q_t \, p_t}$$ Why:把 $p_t$ 看作 $K$ 维概率列向量,rate matrix $Q_t$ 把它做线性变换。讲师(chunk #1634):「this is a ODE again, right? Amazing. Just like flow matching, we get a simple ODE again.」—— 漂亮:离散扩散在连续时间下就是一个线性 ODE,和 flow matching 在结构上完全对偶。

五、反向网络:$p_\theta(x_{t-1} \mid x_t)$ 是 categorical

有了前向,反向也类似 DDPM:用神经网络参数化每步去噪条件分布。

$$p_\theta(x_{t-1} \mid x_t) = \mathrm{Cat}\!\big(x_{t-1} \mid f_\theta(x_t, t)\big)$$

$f_\theta(x_t, t) \in \mathbb{R}^K$ 是神经网络输出的 logits,softmax 之后得到 categorical 分布。

对一个长度 $L$ 的句子,每个位置独立预测一个 categorical:

$$p_\theta(x_{t-1} \mid x_t) = \prod_{i=1}^L p_\theta(x_{t-1}^{(i)} \mid x_t)$$

这就是为什么 discrete diffusion 天然是非自回归(non-autoregressive)的——每一步所有 token 的去噪可以并行进行,不需要逐字解码。和 GPT 那种"左到右一字一字憋"完全不同,discrete diffusion 是"全句一起 refine、refine 完一轮再 refine 下一轮"。

这里需要小心一个独立性假设:网络在预测每个位置的 token 时给定的是全句的 $x_t$,所以位置之间是"条件独立"——它们各自看到了相同的 noisy context,但各自的预测彼此之间不直接约束。这是 discrete diffusion 在质量上比自回归弱的根源(autoregressive 每步看到全部已生成的 token),但也是它能并行的根本原因。后面 SEDD / MDLM 章会讲怎么用 $T$ 步迭代来弥补这个独立性假设带来的损失。

💡 非自回归的代价与收益:自回归 LM(GPT 那种)逐 token 生成,质量稳但慢;discrete diffusion 一步并行所有 token,快但每步信息少。讲师在第 21 章(forward pointer)里会展开:用 $T$ 步换并行度,是 LM 设计里一个全新的"质量–速度"权衡轴。

六、训练目标:ELBO → 简化损失 → cross-entropy

训练目标和 DDPM 同源:最大化数据 log-likelihood 的 ELBO(下界)。讲师在 chunk #1624 一句话总结:「we can train it using the same ELBO loss from DDPM essentially」。下面把它落到具体形式。

6.1 离散 ELBO

对一个数据点 $x_0$,扩展 $T$ 步:

$$\log p_\theta(x_0) \;\geq\; \mathbb{E}_q\!\left[\log p_\theta(x_0 \mid x_1) - \sum_{t=2}^T D_{\mathrm{KL}}\!\big(q(x_{t-1} \mid x_t, x_0) \,\|\, p_\theta(x_{t-1} \mid x_t)\big) - D_{\mathrm{KL}}\!\big(q(x_T \mid x_0) \,\|\, p(x_T)\big)\right]$$

结构跟 DDPM 完全一致(参见第 7 章),只是这里所有的 $q$ 和 $p$ 都是 categorical 而非 Gaussian。第一项重构、中间一堆 KL 让网络匹配真后验、最后一项是先验匹配。

6.2 真后验 $q(x_{t-1} \mid x_t, x_0)$ 也有闭式

用 Bayes:

$$q(x_{t-1} \mid x_t, x_0) = \frac{q(x_t \mid x_{t-1}) \, q(x_{t-1} \mid x_0)}{q(x_t \mid x_0)}$$

三个分量都是已知 categorical:

  • $q(x_t \mid x_{t-1}) = \mathrm{Cat}(Q_t \, x_{t-1})$;
  • $q(x_{t-1} \mid x_0) = \mathrm{Cat}(\bar Q_{t-1} \, x_0)$;
  • $q(x_t \mid x_0) = \mathrm{Cat}(\bar Q_t \, x_0)$。

逐元素一乘一除,归一化后就得到 $q(x_{t-1} \mid x_t, x_0)$ 的概率向量。每一项的 KL 散度就能解析算出。

6.3 关键操作:重参数化成 $x_0$ 预测

这是讲师在 L13 反复强调的一句话(chunk #1636):

"the core of the story in all the discrete diffusion papers is that no matter what you do try to reparameterize your thing into something that you can directly get from the forward process and the clean data estimation. It's actually not only the discrete diffusion paper. It's actually all diffusion paper."

对应到 DDPM 是 $\epsilon$-prediction 或 $v$-prediction;对应到 discrete 是 $x_0$-prediction。

具体做法:让神经网络不直接输出 $p_\theta(x_{t-1} \mid x_t)$,而是输出 $\hat x_0 = f_\theta(x_t, t)$ 的预测分布("clean token 是什么"),然后用闭式公式拼出 $p_\theta(x_{t-1} \mid x_t)$:

$$p_\theta(x_{t-1} \mid x_t) = \sum_{\tilde x_0} q(x_{t-1} \mid x_t, \tilde x_0) \, f_\theta(\tilde x_0 \mid x_t, t)$$

讲师在 chunk #1636 给出两点理由:

  1. "It saves dimensionality":直接预测 rate matrix 是 $K \times K$ 量级;预测 $\hat x_0$ 只需要 $K$ 维 logits。
  2. "We can literally just use cross entropy to learn this, because we have the ground truth clean data"(chunk #1637)。

6.4 落地的简化损失:cross-entropy

训练时给定真实 $x_0$,从前向闭式采 $x_t \sim q(x_t \mid x_0)$,让网络预测 $\hat x_0$:

$$L_{\text{simple}} = \mathbb{E}_{t, x_0, x_t}\!\left[ -\log f_\theta(x_0 \mid x_t, t) \right]$$

就是一个对每个 token 的交叉熵。讲师(chunk #1637):「we just need to use cross entropy on every single token」。这就是为什么 discrete diffusion 训练 loop 看起来出奇地像 BERT 训练——因为它就是。和 BERT 的区别只有两个:

  1. 每个 batch 采到的 $t$ 是随机的,所以 mask 的比例是连续变化的(BERT 是固定 15%);
  2. 损失会按 $t$ 的某个权重项加权(来自 ELBO 中 $D_{\mathrm{KL}}(q \| p_\theta)$ 的系数),但讲师指出实践中这个权重经常被丢掉直接用 uniform,DDPM 同样的"$L_\text{simple}$ vs $L_\text{vlb}$"的故事在这里复现一遍。

整体的对照:DDPM 把"MSE on $\epsilon$" 当作简化损失,discrete diffusion 把"cross-entropy on $x_0$"当作简化损失。两者都是从复杂 ELBO 里抽出一个"漂亮且能跑"的代理目标。

⚠️ 同学的真实问题(chunk #1639):「You will still be quadratic the number of the vocabulary size, right? Does that make it difficult to predict such a large?」
讲师回答:「No, because you are not predicting Q, right? You're predicting P. You're predicting Sx. And then you multiply by something that you can do in closed form.」
翻译:网络只需要输出 $K$ 维的 $\hat x_0$ logits(vocabulary 大小,跟 GPT 的输出头同量级),$K \times K$ 那一坨闭式计算就好——这是讲师反复强调的工程救命招。

七、D3PM 训练伪代码

把上面所有概念落到代码里,长这样:

import torch
import torch.nn.functional as F

def discrete_diffusion_loss(model, x0, Q_cum, T, vocab_size):
    """
    D3PM-style training step.
    x0:        (batch, seq_len) ground-truth token ids
    Q_cum[t]:  (K, K) cumulative transition matrix  bar Q_t = Q_t ... Q_1
    model:     predicts logits of x0 given x_t, t
    """
    B, L = x0.shape
    # ----- 1. 随机采时间步 -----
    t = torch.randint(1, T + 1, (B,), device=x0.device)

    # ----- 2. 前向采 x_t ~ q(x_t | x_0) = Cat(bar Q_t @ x_0_onehot) -----
    x0_oh = F.one_hot(x0, vocab_size).float()           # (B, L, K)
    # gather 当前 batch 各自的 bar Q_t
    probs = torch.einsum('kj,blj->blk', Q_cum[t.mean().long()], x0_oh)
    xt = torch.distributions.Categorical(probs=probs).sample()  # (B, L)

    # ----- 3. 模型预测 hat_x0 logits -----
    logits = model(xt, t)                                # (B, L, K)

    # ----- 4. 交叉熵损失 -----
    # 关键:损失不是去对 (B, L, K, K) 的 rate matrix,
    # 而是对 (B, L, K) 的 vocab-size logits 做 cross-entropy。
    loss = F.cross_entropy(
        logits.reshape(-1, vocab_size),
        x0.reshape(-1)
    )
    return loss

训完之后采样:从 $x_T$(uniform 或全 MASK)开始,每一步用 $\hat x_0$ 重参数化拼出 $p_\theta(x_{t-1} \mid x_t)$,采一个 categorical,迭代到 $t=0$。

八、$K \times K$ 矩阵的工程现实

第 7 节代码看上去丝滑,但实际写过的人都被一件事卡过:$K$ 是 50 000 起的 vocabulary 大小。$K \times K$ 矩阵单看是 25 亿浮点数,10 GB 内存——这是讲师在 chunk #1631 被同学问到的"big matrix problem"。三种解决思路:

8.1 结构化 $Q_t$

不存全矩阵,只存它的"参数":

  • Uniform:$Q_t = (1-\beta_t)I + \beta_t/K \cdot \mathbf{1}\mathbf{1}^\top$,只需存 $\beta_t$。$Q_t \, v$ 的矩阵向量积可以 $O(K)$ 算($v$ 投到 1 上是平均、加回去就行)。
  • Absorbing:$Q_t$ 几乎是单位矩阵 + 一条 MASK 行,参数也是 $\beta_t$。$Q_t v$ 只需 $O(K)$。

结论:除非你刻意要让任意两个 token 间转移概率都不同,否则永远不要显式存 $K \times K$ 矩阵。这是 discrete diffusion 能在 50K vocabulary 上跑起来的根本原因。

8.2 SEDD 的 score-entropy 视角

讲师(chunk #1624):「we also talked about how we can define the discrete score which is the concrete score and how we can learn it using a better or more stable loss function which is called the score entropy loss」。

SEDD(Score Entropy Discrete Diffusion)把对 $K \times K$ 矩阵的预测进一步压缩成对"score ratio" $p(y)/p(x)$ 的预测,并用一个稳定的 score-entropy 损失替代 cross-entropy。下一章 第 20 章详细展开。

8.3 reparameterization 的本质

讲师在 chunk #1632 把这件事点透:「this is also why we're trying to do reparameterization trick」。所有这些工程花招——$x_0$-prediction、score ratio、结构化 $Q_t$——本质上都是不要让网络去预测 $K^2$ 维东西。永远把要学的对象重写成"$K$ 维 logits + 闭式后处理"的形式。这和 DDPM 里的 $\epsilon$-prediction 同根同源:让网络去回归 $\epsilon \in \mathbb{R}^d$(数据空间维度),而不是去回归 $\mu_\theta \in \mathbb{R}^d$(也是 $d$ 维但带数值漂移)—— 重参数化是一种"把困难任务变成简单任务"的纯代数操作,并不改变损失的极值点。

讲师把这件事看作 diffusion 大家族的一个共同基因,原话(chunk #1636):「It's actually not only the discrete diffusion paper. It's actually all diffusion paper. Right? Basically, you just apply reparameterization trick and then you'll get something that is like nicer to learn. For example, like the epsilon prediction and the v prediction, right? And in this case, this is literally just the x0 prediction or the clean data prediction.」 一旦你脑子里建立这个映射,所有 diffusion 论文的"我们参数化为 X-prediction"这一段就再也不会让你卡住——它们做的是同一件事的不同变种。

九、采样:从噪声/MASK 到 clean text

采样流程(以 absorbing 为例):

  1. 初始化:$x_T = $ 长度为 $L$ 的全 [MASK] 序列;
  2. 对 $t = T, T-1, \ldots, 1$:
    1. 前向网络输出 $\hat x_0$ logits = $f_\theta(x_t, t)$;
    2. 用闭式公式拼出 $p_\theta(x_{t-1} \mid x_t)$;
    3. 对每个位置独立采一个 $x_{t-1}^{(i)} \sim \mathrm{Cat}(\cdot)$;
  3. 最终输出 $x_0$ 就是生成的文本。

讲师(chunk #1638)描述这个流程像 Euler 积分:「you literally just sample from the categorical distribution that is defined by the CTMC … and then you just increment the time and then you do it over and over again until you reach the end point」。这是和连续 DDPM 的 Euler-Maruyama 步对应的离散版本——前者是数值积分 SDE,后者是数值积分 CTMC。

采样的几个工程细节:

  • 采样温度:$\mathrm{Cat}$ 采样前可以对 logits 除以温度 $\tau$,$\tau < 1$ 时趋于 argmax(更确定)、$\tau > 1$ 时更发散。和自回归 LM 的 temperature 技巧完全一致。
  • 步数:$T$ 不必和训练时的 $T$ 相同。可以用更少的 $T$ 步(如 16、32)来加速,代价是质量略降——和 DDIM 的"训练 1000 步、采样 50 步"是一个道理。
  • 位置策略:absorbing 的反向步里,可以选择"只在 MASK 位置采样"或"所有位置都重采"。前者更稳定、更接近 BERT 的 fill-in;后者更接近原始 D3PM 的形式定义。MDLM 等后续工作专门研究这个选择。
💡 非自回归 vs 自回归:上述流程的迭代次数 $T$ 通常远小于 $L$(句子长度)。当 $T = 10$、$L = 1024$ 时,自回归 LM 需要 1024 次串行 forward,discrete diffusion 只需要 10 次。这就是它"用 $T$ 步换并行度"的本质。

十、和已学概念的全景对照

到这里把这一整套机器与前面的工具一一对照:

概念 连续 DDPM 离散 D3PM
数据空间 $\mathbb{R}^d$ $\{1, \ldots, K\}^L$(one-hot 后是 $K$-simplex 顶点)
前向条件分布 $\mathcal{N}(\sqrt{\alpha_t} x_{t-1}, \beta_t I)$ $\mathrm{Cat}(Q_t \, x_{t-1})$
多步闭式 $\mathcal{N}(\sqrt{\bar\alpha_t} x_0, (1-\bar\alpha_t)I)$ $\mathrm{Cat}(\bar Q_t \, x_0)$,$\bar Q_t = Q_t \cdots Q_1$
先验 $p(x_T)$ $\mathcal{N}(0, I)$ 均匀 / 全 MASK
连续时间 SDE CTMC(rate matrix $Q_t$,列和为 0)
参数化 $\epsilon$-prediction / $v$-prediction $x_0$-prediction
最终损失 MSE on $\epsilon$ Cross-entropy on $x_0$
采样 $T$ 步迭代 Gaussian $T$ 步迭代 Categorical

讲师在 L13 末尾用一句话总结这个"撞墙巧合"(chunk #1639):「this is the theme of gen modeling. the community just like seems to kind of you know converge on things that we developed somehow」——生成式建模的整体框架,似乎正在收敛到同一套语言。

十一、和语言模型的关系

把 absorbing discrete diffusion 摆到自然语言处理的脉络里:

  • BERT (2018):单步 mask 一定比例的 token(如 15%)、预测被 mask 的 token。本质是 discrete diffusion with $T=1$ and fixed mask ratio,但它是用 pretraining 思路来用、不是生成思路。
  • Discrete Diffusion / D3PM (2021):把 BERT 的"单步"扩成"$T$ 步",每步 mask 比例随 $t$ 平滑增长,最终全 mask。这是把 BERT 转成生成模型的关键一步——只要训练时见过"100% mask"这种极端情况,采样就可以从全 MASK 启动。
  • SEDD (2024) / MDLM (2024):用 score-entropy 让损失更稳定,开始在小规模 LM 上接近 autoregressive 质量。SEDD 由 Stanford 的 Aaron Lou 等人推出,是 Stanford NLP 第一次把 diffusion LM 推到接近 GPT-2 small 的水平。
  • LLaDA / DiffuLLaMA (2025):把 discrete diffusion 推到 7B+ 规模,开始在某些任务上(特别是双向推理、in-filling)展示出比同规模自回归模型更好的表现。这是 discrete diffusion 第一次进入"大模型主流话题"。

从研究演化的角度看,这条线索其实是BERT 的复仇:BERT 在 2018 年提出后被 GPT 系(autoregressive)的成功盖了风头,但 BERT 一直保留着"双向上下文"和"并行预测"这两个本质优点。discrete diffusion 给了 BERT 一个理论上自洽的"采样接口"——只要把训练目标扩展到全谱 mask ratio,BERT 立刻能变成生成模型。这条路在 2024–2025 年开始真正起飞。

🟡 教材外补充(讲师本讲未展开):
  • D3PM 论文细节:Austin et al. 2021《Structured Denoising Diffusion Models in Discrete State-Spaces》。除了 uniform 和 absorbing,他们还给出"基于 token 距离的"$Q_t$(图像 token 上邻近 token 间转移概率更高)。这一族叫 structured corruption。
  • 非自回归并非新概念:早在 2017 年的 NAT (Non-Autoregressive Transformer) 就在尝试一步并行预测整句话,但质量长期落后于 AR。Discrete diffusion 给了 NAT 一个理论基础:每一步的"refine"对应一次扩散反向步,质量随 $T$ 收敛。
  • 与 BERT 的差别:BERT 的 mask ratio 是固定的,模型只见过"15% 被 mask"的输入;discrete diffusion 在训练里见过"$0\% \to 100\%$ 全谱"的 mask ratio——这让它在采样时能从全 mask 安全启动,而 BERT 不能。

十二、本章的承上启下

  • 承上:DDPM 的 ELBO 推导(第 7 章)、$\epsilon/v$-prediction(第 8 章)、flow matching velocity(第 16 章)—— discrete diffusion 把它们整体平移到 categorical 状态空间。
  • 启下:
    • 第 20 章:Masked Diffusion + SEDD,把 absorbing 这条路深挖到 score-entropy 损失;
    • 第 21 章:Diffusion-LM、LLaDA、MDLM、DiffuLLaMA—— discrete diffusion 在大语言模型层面的真实战场。
    • 讲师在 L13 后半段还会推出 Discrete Flow Matching:把 CTMC + rate matrix 改造成 flow matching 视角,进一步把 ELBO 替换成 conditional flow matching loss。
K-类 categorical simplex 上的随机游走(K=4 示意) the cat sat [MASK] x_0 x_1 x_T = [MASK] 每一步 x_t ~ Cat(Q_t · x_{t-1}):从一个顶点跳到 simplex 内某点,再采样落到下一个顶点
📺 CMU 10799 S26 Lecture 12(1:39 处)—— 讲师介绍"最简单的离散扩散就是 mask diffusion"
📺 CMU 10799 S26 Lecture 13(3:32 处)—— CTMC、rate matrix、列和为 0 的 Kolmogorov 守恒推导

本章要记住的(讲师亲口给的核心)

  1. "token 上加噪 = simplex 上的马尔可夫链"。把 token 变 one-hot,所有 diffusion 工具就能复用:$q(x_t \mid x_{t-1}) = \mathrm{Cat}(Q_t x_{t-1})$。
  2. $Q_t$ 决定"噪声类型":Uniform(终点均匀分布)、Absorbing/MASK(终点全 MASK,讲师叫"the easiest way")、Argmax embedding(绕道连续)。
  3. $\bar Q_t = Q_t \cdots Q_1$,多步闭式与 DDPM 的 $\bar\alpha_t$ 同构。
  4. CTMC = 离散扩散的连续时间版:rate matrix 列和为 0、Kolmogorov 方程 $dp_t/dt = Q_t p_t$ 是一个线性 ODE。讲师原话:「QT is the flow, it's a velocity」。
  5. 训练损失 = $x_0$-prediction 的 cross-entropy。讲师反复强调:「all discrete diffusion papers, the core is to reparameterize into something you can directly get from forward + clean data estimation」。
  6. $K \times K$ 矩阵不要显式存。用结构化 $Q_t$(uniform / absorbing 都是 $O(K)$ 参数),$Q_t v$ 用 closed form 算。这是 50K vocabulary 能跑通的工程救命招。
  7. Discrete diffusion = 非自回归 LM。$T$ 步并行解码替换自回归的 $L$ 步串行。质量–速度 trade-off 的新轴,承接到 第 20 章 SEDD 与 第 21 章 LLaDA/MDLM。