Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution

通过估计数据分布比值做离散扩散建模

Aaron Lou Affiliation:  Stanford University Correspondence to: aaronlou@stanford.edu    Chenlin Meng Affiliation:  Stanford University Affiliation:  Pika Labs    Stefano Ermon Affiliation:  Stanford University

Abstract

摘要

Despite their groundbreaking performance for many generative modeling tasks, diffusion models have fallen short on discrete data domains such as natural language. Crucially, standard diffusion models rely on the well-established theory of score matching, but efforts to generalize this to discrete structures have not yielded the same empirical gains. In this work, we bridge this gap by proposing score entropy, a novel loss that naturally extends score matching to discrete spaces, integrates seamlessly to build discrete diffusion models, and significantly boosts performance. Experimentally, we test our Score Entropy Discrete Diffusion models (SEDD) on standard language modeling tasks. For comparable model sizes, SEDD beats existing language diffusion paradigms (reducing perplexity by $25$-$75$%) and is competitive with autoregressive models, in particular outperforming GPT-2. Furthermore, compared to autoregressive mdoels, SEDD generates faithful text without requiring distribution annealing techniques like temperature scaling (around $6$-$8\times$ better generative perplexity than un-annealed GPT-2), can trade compute and quality (similar quality with $32\times$ fewer network evaluations), and enables controllable infilling (matching nucleus sampling quality while enabling other strategies besides left to right prompting).

尽管扩散模型在许多生成建模任务上表现突破，在自然语言等离散数据域上却一直逊色。关键在于：标准扩散依赖成熟的分数匹配理论，而把该理论推广到离散结构的努力并未带来同等实证收益。本文提出分数熵（score entropy），自然把分数匹配延伸到离散空间，可无缝接入离散扩散模型并显著抬升表现，从而弥合这一差距。实验上，我们在标准语言建模任务上检验 Score Entropy Discrete Diffusion 模型（SEDD）。同等规模下，SEDD 大幅胜过既有语言扩散范式（困惑度降低 $25$–$75$%），并与自回归模型相当，尤其超过 GPT-2。此外，相对自回归模型，SEDD 无需温度缩放等分布退火即可生成忠实文本（生成困惑度约优于未退火 GPT-2 的 $6$–$8\times$），可在算力与质量间权衡（网络评估少约 $32\times$ 仍可比质量），并支持可控填空（在匹配 nucleus 采样质量的同时，允许非从左到右的提示策略）。

1 Introduction

1 引言

Keywords:

Many recent advances in deep learning have centered around generative modeling. Here, a model learns how to generate novel samples from unstructured data. With the powerful capabilities of modern neural networks, these “generative AI” systems have developed unparalleled capabilities, such as creating images given only text (Ramesh et al., 2022) and answering complex questions (Brown et al., 2020).

关键词：

深度学习近年许多进展围绕生成建模：模型从无结构数据中学会生成新样本。借助现代神经网络的能力，这些「生成式 AI」系统具备前所未有的能力，例如仅凭文本生成图像（Ramesh et al., 2022）、回答复杂问题（Brown et al., 2020）。

The crucial part for any deep generative model is the probabilistic modeling technique. For discrete data such as natural language, autoregressive modeling (Yule, 1971)–arguably the simplest modeling type since it derives from the probabilistic chain rule–has remained the only competitive method for decades. Although modern autoregressive transformers have produced stunning results (Vaswani et al., 2017; Radford et al., 2019), there are limits. For example, the sequential sampling of tokens is slow, hard to control, and often degrades without distribution annealing techniques like nucleus sampling (Holtzman et al., 2019).

深度生成模型的关键在于概率建模技术。对自然语言等离散数据，自回归建模（Yule, 1971）——或许是最简类型，因其直接来自概率链式法则——数十年来仍是唯一有竞争力的方法。尽管现代自回归 transformer 成果惊人（Vaswani et al., 2017；Radford et al., 2019），仍有局限。例如 token 串行采样慢、难控制，且常需 nucleus 采样（Holtzman et al., 2019）一类分布退火，否则质量下降。

To alleviate these issues, researchers have sought alternative approaches to generating text data. In particular, inspired by their success in the image domain, many works have extended diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song et al., 2021c) to language domains (Li et al., 2022; Austin et al., 2021). Yet, despite considerable effort, no such approach yet rivals autoregressive modeling, as they are not competitive on likelihoods, are slower to sample from, and do not generate comparable samples without resorting to heavy annealing and empirical alterations.

为缓解这些问题，研究者寻找文本生成的替代路径。尤其受图像域成功启发，大量工作把扩散模型（Sohl-Dickstein et al., 2015；Ho et al., 2020；Song et al., 2021c）扩展到语言（Li et al., 2022；Austin et al., 2021）。然而投入虽大，尚无方法真正挑战自回归：似然不具竞争力、采样更慢，且不靠重度退火与经验改动就难生成可比样本。

In our work, we challenge the longstanding dominance of autoregressive models by introducing Score Entropy Discrete Diffusion models (SEDD). SEDD parameterizes a reverse discrete diffusion process using the ratios of the data distribution. These are learned using score entropy, a novel loss that is analogous to score matching for standard diffusion models (Hyvärinen, 2005; Song & Ermon, 2019) and results in several empirical benefits[^†]:

本文引入 Score Entropy Discrete Diffusion 模型（SEDD），挑战自回归长期主导地位。SEDD 用数据分布的比值参数化离散扩散的反向过程；这些比值由分数熵学习——一种类似于标准扩散分数匹配（Hyvärinen, 2005；Song & Ermon, 2019）的新损失，并带来若干实证收益[^†]：

1. On core language modeling tasks, SEDD outperforms all existing language diffusion models (Li et al., 2022; Austin et al., 2021; Gulrajani & Hashimoto, 2023; He et al., 2022) by large margins and is competitive with autoregressive models of the same size (beating GPT-2 on its zero-shot perplexity tasks (Radford et al., 2019)).
2. SEDD generates high quality unconditional samples and enables one to naturally trade off compute for quality. When measuring the generative perplexity (given by large models) of unconditional and un-annealed samples from similarly sized models, SEDD beats GPT-2 by $6$-$8\times$ and can match performance using $32\times$ fewer function evaluations.
3. By directly parameterizing probability ratios, SEDD is highly controllable. In particular, one can prompt SEDD from arbitrary positions without specialized training. For both standard (left to right) and infilling, SEDD outperforms language diffusion models and is comparable with autoregressive models with nucleus sampling (as measured by MAUVE score (Pillutla et al., 2021)).

1. 在核心语言建模任务上，SEDD 大幅胜过所有既有语言扩散模型（Li et al., 2022；Austin et al., 2021；Gulrajani & Hashimoto, 2023；He et al., 2022），并与同规模自回归模型相当（在 GPT-2 的零样本困惑度任务上超过 GPT-2（Radford et al., 2019））。
2. SEDD 能生成高质量无条件样本，并自然地在算力与质量间权衡。用大模型度量同规模模型无条件、未退火样本的生成困惑度时，SEDD 优于 GPT-2 约 $6$–$8\times$，且用少约 $32\times$ 的函数评估即可匹配表现。
3. 因直接参数化概率比，SEDD 高度可控。尤其可从任意位置提示而无需专门训练。标准（从左到右）与填空设定下，SEDD 胜过语言扩散模型，并与带 nucleus 采样的自回归模型可比（以 MAUVE 分数衡量（Pillutla et al., 2021））。

2 Preliminaries

2 预备知识

2.1 Discrete Diffusion Processes

2.1 离散扩散过程

We will be modeling probability distributions over a finite support $\mathcal{X}=\{1,\dots,N\}$. As the support is discrete, note that our probability distributions can be represented by probability mass vectors $p\in\mathbb{R}^{N}$ that are positive and sum to $1$. To define a discrete diffusion process, we evolve a family of distributions $p_{t}\in\mathbb{R}^{N}$ according to the a continuous time Markov process given by a linear ordinary differential equation (Campbell et al., 2022; Anderson, 2012):

我们在有限支撑 $\mathcal{X}=\{1,\dots,N\}$ 上建模概率分布。因支撑离散，概率分布可用正且和为 $1$ 的概率质量向量 $p\in\mathbb{R}^{N}$ 表示。定义离散扩散时，按连续时间马尔可夫过程对应的线性常微分方程演化一族分布 $p_{t}\in\mathbb{R}^{N}$（Campbell et al., 2022；Anderson, 2012）：

$$\frac{dp_{t}}{dt}=Q_{t}p_{t}\quad p_{0}\approx p_{\rm data} \tag{1}$$

Here, $Q_{t}$ are the diffusion matrices $\mathbb{R}^{N\times N}$ and have non-negative non-diagonal entries and columns which sum to zero (so that the rate $\frac{dp_{t}}{dt}$ sums to $0$, meaning $p_{t}$ does not gain or lose total mass). Generally, $Q_{t}$ are simple (e.g. a simple scalar factor $Q_{t}=\sigma(t)Q$) so $p_{t}$ approaches a limiting distribution $p_{\rm base}$ as $t\to\infty$.

其中 $Q_{t}$ 是扩散矩阵 $\mathbb{R}^{N\times N}$，非对角元非负、各列和为零（从而速率 $\frac{dp_{t}}{dt}$ 总和为 $0$，即 $p_{t}$ 总质量守恒）。一般 $Q_{t}$ 很简单（例如标量因子 $Q_{t}=\sigma(t)Q$），使 $t\to\infty$ 时 $p_{t}$ 趋向极限分布 $p_{\rm base}$。

One can simulate this process by taking small $\Delta t$ Euler steps and randomly sampling the resulting transitions. In particular, the samples are defined by transition densities which come from the columns of $Q_{t}$:

可用小 $\Delta t$ 的 Euler 步并随机采样所得转移来模拟该过程。样本由 $Q_{t}$ 各列给出的转移密度定义：

$$p(x_{t+\Delta t}=y|x_{t}=x)=\delta_{xy}+Q_{t}(y,x)\Delta t+O(\Delta t^{2}) \tag{2}$$

Finally, this process has a well known reversal (Kelly, 1980; Sun et al., 2023) given by another diffusion matrix $\overline{Q}_{t}$:

该过程有著名的时间反转（Kelly, 1980；Sun et al., 2023），由另一扩散矩阵 $\overline{Q}_{t}$ 给出：

$$\frac{dp_{T-t}}{dt}=\overline{Q}{T-t}p{T-t}\quad\overline{Q}{t}(y,x)=\frac{p{t}(y)}{p_{t}(x)}Q_{t}(x,y)\
\overline{Q}{t}(x,x)=-\sum{y\neq x}\overline{Q}_{t}(y,x) \tag{3}$$

This reverse process is analogous to the time reversal for typical diffusion processes on $\mathbb{R}^{n}$, with the ratios $\frac{p_{t}(y)}{p_{t}(x)}$ (which are collectively known as the concrete score (Meng et al., 2022)) generalizing the typical score function $\nabla_{x}\log p_{t}$ (Song & Ermon, 2019) [^1]

这一反向过程类似于 $\mathbb{R}^{n}$ 上典型扩散的时间反转；比值 $\frac{p_{t}(y)}{p_{t}(x)}$（合称 concrete score（Meng et al., 2022））推广了通常的分数函数 $\nabla_{x}\log p_{t}$（Song & Ermon, 2019）[^1]

2.2 Discrete Diffusion Models

2.2 离散扩散模型

The goal of a discrete diffusion model is to construct the aforementioned reverse process by learning the ratios $\frac{p_{t}(y)}{p_{t}(x)}$. Unlike the continuous diffusion case, which has settled around (up to minor scaling variations) the theoretical framework given by score matching (Hyvärinen, 2005), there currently exist many competing methods for learning discrete diffusion models. In particular, these tend to produce mixed empirical results, which spurs the need for a reexamination.

离散扩散模型的目标是通过学习比值 $\frac{p_{t}(y)}{p_{t}(x)}$ 构造上述反向过程。连续扩散已基本收敛到（至多差小幅缩放）分数匹配给出的理论框架（Hyvärinen, 2005）；离散情形则存在多种相互竞争的学习方法，实证结果参差，值得重新审视。

Mean Prediction. Instead of directly parameterizing the ratios $\frac{p_{t}(y)}{p_{t}(x)}$, Austin et al. (2021); Campbell et al. (2022) instead follow a strategy of Ho et al. (2020) to learn the reverse density $p_{0|t}$. This actually recovers the ratios $\frac{p_{t}(y)}{p_{t}(x)}$ in a roundabout way (as shown in our Theorem 4.2), but comes with several drawbacks. First, learning $p_{0|t}$ is inherently harder since it is a density (as opposed to a general value). Furthermore, the objective breaks down in continuous time and must be approximated (Campbell et al., 2022). As a result, this framework largely underperforms empirically.

均值预测。 与直接参数化比值 $\frac{p_{t}(y)}{p_{t}(x)}$ 不同，Austin et al.（2021）；Campbell et al.（2022）沿用 Ho et al.（2020）的策略学习反向密度 $p_{0|t}$。这其实能迂回恢复比值（见我们的定理 4.2），但有若干缺点。第一，学习 $p_{0|t}$ 本质上更难，因为它是密度（而非一般数值）。第二，目标在连续时间下崩溃，必须近似（Campbell et al., 2022）。因此该框架实证上大体偏弱。

Ratio Matching. Originally introduced in Hyvärinen (2007) and augmented in Sun et al. (2023), ratio matching learns the marginal probabilities of each dimension with maximum likelihood training. However, the resulting setup departs from standard score matching and requires specialized and expensive network architectures (Chen & Duvenaud, 2019). As such, this tends to perform worse than mean prediction.

比值匹配。 最早由 Hyvärinen（2007）提出、经 Sun et al.（2023）加强，比值匹配用最大似然学习各维边际概率。但所得设定偏离标准分数匹配，并需要专门且昂贵的网络架构（Chen & Duvenaud, 2019），表现往往不如均值预测。

Concrete Score Matching. Meng et al. (2022) generalizes the standard Fisher divergence in score matching, learning $s_{\theta}(x,t)\approx\begin{bmatrix}\frac{p_{t}(y)}{p_{t}(x)}\end{bmatrix}_{y\neq x}$ with concrete score matching:

Concrete Score Matching。 Meng et al.（2022）推广分数匹配中的标准 Fisher 散度，用 concrete score matching 学习 $s_{\theta}(x,t)\approx\begin{bmatrix}\frac{p_{t}(y)}{p_{t}(x)}\end{bmatrix}_{y\neq x}$：

$$\mathcal{L}_{\rm CSM}=\frac{1}{2}\mathbb{E}_{x\sim p_{t}}\left[\sum_{y\neq x}\left(s_{\theta}(x_{t},t)_{y}-\frac{p_{t}(y)}{p_{t}(x)}\right)^{2}\right] \tag{4}$$

Unfortunately, the $\ell^{2}$ loss is incompatible with the fact that $\frac{p_{t}(y)}{p_{t}(x)}$ must be positive. In particular, this does not sufficiently penalize negative or zero values, leading to divergent behavior. Although theoretically promising, Concrete Score Matching struggles (as seen in Appendix D).

可惜 $\ell^{2}$ 损失与 $\frac{p_{t}(y)}{p_{t}(x)}$ 必须为正这一事实不兼容：对负值或零惩罚不足，导致发散行为。理论虽诱人，Concrete Score Matching 表现挣扎（见附录 D）。

3 Score Entropy Discrete Diffusion Models

3 分数熵离散扩散模型

In this section, we introduce score entropy. Similar to concrete score matching, we learn the collected concrete score $s_{\theta}(x,t)\approx\begin{bmatrix}\frac{p_{t}(y)}{p_{t}(x)}\end{bmatrix}_{y\neq x}$ ($s_{\theta}:\mathcal{X}\times\mathbb{R}\to\mathbb{R}^{|\mathcal{X}}|$). We design the score entropy loss to incorporate the fact that these ratios are positive and evolve under a discrete diffusion.

本节引入分数熵。与 concrete score matching 类似，我们学习汇集的 concrete score $s_{\theta}(x,t)\approx\begin{bmatrix}\frac{p_{t}(y)}{p_{t}(x)}\end{bmatrix}_{y\neq x}$（$s_{\theta}:\mathcal{X}\times\mathbb{R}\to\mathbb{R}^{|\mathcal{X}}|$）。分数熵损失被设计为纳入这些比值为正、且在离散扩散下演化这一事实。

Definition 3.1.

The score entropy $\mathcal{L}_{\rm SE}$ for a distribution $p$, weights $w_{xy}\geq 0$ and a score network $s_{\theta}(x)_{y}$ is

定义 3.1。

对分布 $p$、权重 $w_{xy}\geq 0$ 与分数网络 $s_{\theta}(x)_{y}$，分数熵 $\mathcal{L}_{\rm SE}$ 为

$$\mathbb{E}_{x\sim p}\left[\sum_{y\neq x}w_{xy}\left(s_{\theta}(x)_{y}-\frac{p(y)}{p(x)}\log s_{\theta}(x)_{y}+K\left(\frac{p(y)}{p(x)}\right)\right)\right] \tag{5}$$

where $K(a)=a(\log a-1)$ is a normalizing constant function that ensures that $\mathcal{L}_{\rm SE}\geq 0$.

其中 $K(a)=a(\log a-1)$ 是保证 $\mathcal{L}_{\rm SE}\geq 0$ 的归一化常数函数。

Remark.

Instead of building off of Fisher divergences, score entropy builds off of the Bregman divergence $D_{F}\left(s(x)_{y},\frac{p(y)}{p(x)}\right)$ when $F=-\log$ is the convex function. As such, score entropy is non-negative, symmetric, and convex. It also generalizes standard cross entropy to general positive values (instead of simplex-valued probabilities), inspiring the name. The weights $w_{xy}$ are used primarily when combining score entropy with diffusion models.

注。

分数熵不以 Fisher 散度为根基，而以凸函数 $F=-\log$ 时的 Bregman 散度 $D_{F}\left(s(x)_{y},\frac{p(y)}{p(x)}\right)$ 为根基。因而分数熵非负、对称、凸。它也把标准交叉熵推广到一般正值（而非单纯形上的概率），由此得名。权重 $w_{xy}$ 主要用于把分数熵与扩散模型结合。

While this expression is more complex than the standard score matching variants, it satisfies several desiderata for a discrete diffusion training objective:

该表达式虽比标准分数匹配变体更复杂，却满足离散扩散训练目标的若干期望性质：

3.1 Score Entropy Properties

3.1 分数熵的性质

First, score entropy is a suitable loss function that recovers the ground truth concrete score.

第一， 分数熵是合适的损失函数，可恢复真实 concrete score。

Proposition 3.2(Consistency of Score Entropy).

Suppose $p$ is fully supported and $w_{xy}>0$. As the number of samples and model capacity approaches $\infty$, the optimal $\theta^{}$that minimizes Equation 5 satisfies$s_{\theta^{}}(x){y}=\frac{p(y)}{p(x)}$for all pairs$x,y$Furthermore,$\mathcal{L}{\rm SE}$will be$0$at$\theta^{}$.*

命题 3.2（分数熵的一致性）。

设 $p$ 全支撑且 $w_{xy}>0$。当样本数与模型容量趋于 $\infty$ 时，最小化式 5 的最优 $\theta^{}$满足对所有对$x,y$有$s_{\theta^{}}(x)_{y}=\frac{p(y)}{p(x)}$。进而在$\theta^{}$处$\mathcal{L}_{\rm SE}$为$0$。*

Second, score entropy directly improves upon concrete score matching by rescaling problematic gradients. For the weights $w_{xy}=1$, $\nabla_{s_{\theta}(x)_{y}}\mathcal{L}_{\rm SE}=\frac{1}{s_{\theta}(x)_{y}}\nabla_{s_{\theta}(x)_{y}}\mathcal{L}_{\rm CSM}$, so the gradient signals for each pair $(x,y)$ are scaled by a factor of $s_{\theta}(x)_{y}$ as a normalization component. As such, this forms a natural log-barrier which keeps our $s_{\theta}\geq 0$.

第二， 分数熵通过对问题梯度重新缩放，直接改进 concrete score matching。对权重 $w_{xy}=1$，$\nabla_{s_{\theta}(x)_{y}}\mathcal{L}_{\rm SE}=\frac{1}{s_{\theta}(x)_{y}}\nabla_{s_{\theta}(x)_{y}}\mathcal{L}_{\rm CSM}$，故每对 $(x,y)$ 的梯度信号被 $s_{\theta}(x)_{y}$ 缩放作归一化。这构成自然的对数障碍，保持 $s_{\theta}\geq 0$。

Third, similar to concrete score matching, score entropy can be made computationally tractable by removing the unknown $\frac{p(y)}{p(x)}$ term. There are two alternative forms, the first of which is analogous to the implicit score matching loss (Hyvärinen, 2005):

第三， 与 concrete score matching 类似，可通过去掉未知的 $\frac{p(y)}{p(x)}$ 项使分数熵可计算。有两种替代形式，第一种类似于隐式分数匹配损失（Hyvärinen, 2005）：

Proposition 3.3(Implicit Score Entropy).

$\mathcal{L}_{\rm SE}$is equal up to a constant independent of $\theta$ to the implicit score entropy

命题 3.3（隐式分数熵）。

$\mathcal{L}_{\rm SE}$在差一个与 $\theta$ 无关的常数意义下等于隐式分数熵

$$\mathcal{L}_{\rm ISE}=\mathbb{E}_{x\sim p}\left[\sum_{y\neq x}w_{xy}s_{\theta}(x)_{y}-w_{yx}\log s_{\theta}(y)_{x}\right] \tag{6}$$

Unfortunately, a Monte Carlo estimate would require sampling an $x$ and evaluating $s_{\theta}(y)_{x}$ for all other $y$. For high dimensions, this is intractable, which means we have to sample $y$ uniformly, but this introduces additional variance analogous to that introduced by the Hutchinson trace estimator (Hutchinson, 1989) for sliced score matching (Song et al., 2019). As a result, implicit score entropy is impractical for large-scale tasks. Instead, we work a denoising score matching loss (Vincent, 2011) variant of score entropy:

可惜蒙特卡洛估计需要采样一个 $x$ 并对所有其他 $y$ 评估 $s_{\theta}(y)_{x}$。高维时不可行，只能均匀采样 $y$，但这引入额外方差，类似于切片分数匹配（Song et al., 2019）中 Hutchinson 迹估计（Hutchinson, 1989）带来的方差。因此隐式分数熵对大规模任务不实用。我们转而使用分数熵的去噪分数匹配（Vincent, 2011）变体：

Theorem 3.4(Denoising Score Entropy).

Suppose $p$ is a perturbation of a base density $p_{0}$ by a transition kernel $p(\cdot|\cdot)$, ie $p(x)=\sum_{x_{0}}p(x|x_{0})p_{0}(x_{0})$. The score entropy $\mathcal{L}_{\rm SE}$ is equivalent (up to a constant independent of $\theta$) to the denoising score entropy $\mathcal{L}_{\rm DSE}$ is

定理 3.4（去噪分数熵）。

设 $p$ 是基密度 $p_{0}$ 经转移核 $p(\cdot|\cdot)$ 扰动所得，即 $p(x)=\sum_{x_{0}}p(x|x_{0})p_{0}(x_{0})$。分数熵 $\mathcal{L}_{\rm SE}$ 在差一个与 $\theta$ 无关的常数意义下等价于*去噪分数熵 $\mathcal{L}_{\rm DSE}$*

$$\underset{\begin{subarray}{c}x_{0}\sim p_{0}\
x\sim p(\cdot|x_{0})\end{subarray}}{\mathbb{E}}\left[\sum_{y\neq x}w_{xy}\left(s_{\theta}(x){y}-\frac{p(y|x{0})}{p(x|x_{0})}\log s_{\theta}(x)_{y}\right)\right]\
\tag{7}$$

$\mathcal{L}_{\rm DSE}$ is scalable since Monte Carlo sampling only requires the evaluation of one $s_{\theta}(x)$, which gives us all $s_{\theta}(x)_{y}$, and the variance introduced by $x_{0}$ is manageable. Additionally, it is particularly appealing for discrete diffusion since the intermediate $p_{t}$ are all perturbations of the base density $p_{0}$ (resulting from Equations 1, 2), enabling us to train with $\mathcal{L}_{\rm DSE}$ using the diffusion transition densities $p_{t|0}(\cdot|x_{0})$ (which we can make tractable).

$\mathcal{L}_{\rm DSE}$ 可扩展：蒙特卡洛只需评估一次 $s_{\theta}(x)$ 即可得到全部 $s_{\theta}(x)_{y}$，$x_{0}$ 引入的方差也可控。此外对离散扩散特别合适，因为中间 $p_{t}$ 都是基密度 $p_{0}$ 的扰动（由式 1、2 得到），可用扩散转移密度 $p_{t|0}(\cdot|x_{0})$（可使之可计算）以 $\mathcal{L}_{\rm DSE}$ 训练。

3.2 Likelihood Bound For Score Entropy Discrete Diffusion

3.2 分数熵离散扩散的似然界

Fourth, the score entropy can be used to define an ELBO for likelihood-based training and evaluation.

第四， 分数熵可用于定义基于似然的训练与评估的 ELBO。

Definition 3.5.

For our time dependent score network $s_{\theta}(\cdot,t)$, the parameterized reverse matrix is $\overline{Q}_{t}^{\theta}(y,x)=\begin{cases}s_{\theta}(x,t)_{y}Q_{t}(x,y)&x\neq y\\ -\sum_{z\neq x}\overline{Q}_{t}^{\theta}(z,y)&x=y\end{cases}$ found by replacing the ground truth scores in Equation 3. Our parameterized densities $p_{t}^{\theta}$ thus satisfy the following differential equation:

定义 3.5。

对时间相关分数网络 $s_{\theta}(\cdot,t)$，参数化反向矩阵为 $\overline{Q}_{t}^{\theta}(y,x)=\begin{cases}s_{\theta}(x,t)_{y}Q_{t}(x,y)&x\neq y\\ -\sum_{z\neq x}\overline{Q}_{t}^{\theta}(z,y)&x=y\end{cases}$，由式 3 中用真实分数替换得到。因而参数化密度 $p_{t}^{\theta}$ 满足如下微分方程：

$$\frac{dp_{T-t}^{\theta}}{dt}=\overline{Q}_{T-t}^{\theta}p_{T-t}^{\theta}\quad p_{T}^{\theta}=p_{\rm base}\approx p_{T} \tag{8}$$

The log likelihood of data points can be bounded using an ELBO based off of Dynkin’s formula (Hanson, 2007), which was derived for discrete diffusion models in Campbell et al. (2022). Interestingly, this takes the form of our denoising score entropy loss weighted by the forward diffusion:

数据点的对数似然可用基于 Dynkin 公式（Hanson, 2007）的 ELBO 界定；Campbell et al.（2022）已为离散扩散模型导出该形式。有趣的是，它恰是用前向扩散加权的去噪分数熵损失：

Theorem 3.6(Likelihood Training and Evaluation).

For the diffusion and forward probabilities defined above,

定理 3.6（似然训练与评估）。

对上述扩散与前向概率，

$$-\log p_{0}^{\theta}(x_{0})\leq\mathcal{L}_{\rm DWDSE}(x_{0})+D_{KL}(p_{T|0}(\cdot|x_{0})\parallel p_{\rm base}) \tag{9}$$

where $\mathcal{L}_{\rm DWDSE}(x_{0})$ is the diffusion weighted denoising score entropy for data point $x_{0}$

其中 $\mathcal{L}_{\rm DWDSE}(x_{0})$ 是数据点 $x_{0}$ 的扩散加权去噪分数熵

$$\int_{0}^{T}\mathbb{E}{x{t}\sim p_{t|0}(\cdot|x_{0})}\sum_{y\neq x_{t}}Q_{t}(x_{t},y)\Bigg(s_{\theta}(x_{t},t){y}-\
\frac{p{t|0}(y|x_{0})}{p_{t|0}(x_{t}|x_{0})}\log s_{\theta}(x_{t},t){y}+K\left(\frac{p{t|0}(y|x_{0})}{p_{t|0}(x_{t}|x_{0})}\right)\Bigg)dt \tag{10}$$

Crucially, this result allows us to directly models based on their likelihood values (and the related perplexity scores), the core metric for language modeling tasks. In particular, we can train and evaluate an upper bound.

关键地，该结果让我们能直接按似然值（及相关困惑度）比较模型——这正是语言建模的核心指标。特别地，我们可训练并评估上界。

Remark.

The DWDSE (and the implicit version) can be derived from the general framework of Benton et al. (2022) assuming a concrete score parameterization. In particular, the implicit version coincides with the likelihood loss introduced in Campbell et al. (2022).

注。

DWDSE（及其隐式版本）可在假设 concrete score 参数化时由 Benton et al.（2022）的一般框架导出。特别地，隐式版本与 Campbell et al.（2022）引入的似然损失重合。

3.3 Practical Implementation

3.3 实用实现

Fifth, score entropy can be scaled to high dimensional tasks.

第五， 分数熵可扩展到高维任务。

In practice, our state factorizes into sequences $\mathcal{X}=\{1,\dots,n\}^{d}$ to form sequences $\mathbf{x}=x^{1}\dots x^{d}$ (e.g. sequences of tokens or image pixel values). As a general $Q_{t}$ would be of exponential size, we instead choose a sparse structured matrix that perturbs tokens independently with a matrix $Q_{t}^{\rm tok}$. In particular, the nonzero entries of $Q_{t}$ are given by

实践中，状态分解为序列 $\mathcal{X}=\{1,\dots,n\}^{d}$，形成序列 $\mathbf{x}=x^{1}\dots x^{d}$（例如 token 序列或图像像素值）。一般的 $Q_{t}$ 规模指数级，故改用稀疏结构化矩阵，以矩阵 $Q_{t}^{\rm tok}$ 独立扰动各 token。具体地，$Q_{t}$ 的非零元由下式给出

$$\hskip-5.69046ptQ_{t}(x^{1}\dots x^{i}\dots x^{d},x^{1}\dots\widehat{x}^{i}\dots x^{d})=Q_{t}^{\rm tok}(x^{i},\widehat{x}^{i}) \tag{11}$$

Since $\mathcal{L}_{\rm DWDSE}$ weights the loss by $Q_{t}(x,y)$, this token level transition $Q_{t}$ renders most ratios irrelevant. In particular, we only need to model all ratios between sequences with Hamming distnace $1$, so we can build our score network $s_{\theta}(\cdot,t):\{1,\dots,n\}^{d}\to\mathbb{R}^{d\times n}$ as a seq-to-seq map:

由于 $\mathcal{L}_{\rm DWDSE}$ 以 $Q_{t}(x,y)$ 加权损失，这种 token 级转移使多数比值无关。特别地，只需建模 Hamming 距离为 $1$ 的序列之间的全部比值，因而可将分数网络 $s_{\theta}(\cdot,t):\{1,\dots,n\}^{d}\to\mathbb{R}^{d\times n}$ 建为 seq-to-seq 映射：

$$(s_{\theta}(x^{1}\dots x^{i}\dots x^{d},t))_{i,\widehat{x}^{i}}\approx\frac{p_{t}(x^{1}\dots\widehat{x}^{i}\dots x^{d})}{p_{t}(x^{1}\dots x^{i}\dots x^{d})} \tag{12}$$

To fully compute $\mathcal{L}_{\rm DWDSE}$, we just need to calculate the forward transition $p_{t|0}^{\rm seq}(\cdot|\cdot)$. Luckily, this decomposes as each token is perturbed independently:

要完整计算 $\mathcal{L}_{\rm DWDSE}$，只需算出前向转移 $p_{t|0}^{\rm seq}(\cdot|\cdot)$。幸好各 token 独立扰动，因而可分解：

$$p_{t|0}^{\rm seq}(\mathbf{\widehat{x}}|\mathbf{x})=\prod_{i=1}^{d}p_{t|0}^{\rm tok}(\widehat{x}^{i}|x^{i}) \tag{13}$$

For each $p_{t|0}^{\rm tok}(\cdot|\cdot)$, we employ the previously discussed strategy and set $Q_{t}^{\rm tok}=\sigma(t)Q^{\rm tok}$ for a noise level $\sigma$ and a fixed transition $Q^{\rm tok}$. This avoids numerical integration as, if we define $\overline{\sigma}(t)$ as the cumulative noise $\int_{0}^{t}\sigma(s)ds$, we have:

对每个 $p_{t|0}^{\rm tok}(\cdot|\cdot)$，采用前述策略，取 $Q_{t}^{\rm tok}=\sigma(t)Q^{\rm tok}$，噪声水平 $\sigma$、固定转移 $Q^{\rm tok}$。这避免数值积分：若定义累积噪声 $\overline{\sigma}(t)=\int_{0}^{t}\sigma(s)ds$，则有：

$$\displaystyle p_{t|0}^{\rm tok}(\cdot|x)=x\text{-th column of }\exp\left(\overline{\sigma}(t)Q^{\rm tok}\right) \tag{14}$$

There are some practical consequences that render most $Q^{\rm tok}$ unusable for large scale experiments (e.g. for GPT-2 tasks, $n=50257$). In particular, one is not able to store all edge weights $Q_{\rm tok}(i,j)$ since this takes around $20$ GB of GPU memory and is extremely slow to access. Furthermore, one must be able to compute the columns $\exp(\overline{\sigma}(t)\cdot Q^{\rm tok})$ to get the transition ratios, but this must avoid matrix-matrix multiplication again can’t be stored in memory.

若干实践后果使多数 $Q^{\rm tok}$ 无法用于大规模实验（例如 GPT-2 任务 $n=50257$）。尤其无法存储全部边权 $Q_{\rm tok}(i,j)$——约占 $20$ GB GPU 显存且访问极慢。此外必须能计算列 $\exp(\overline{\sigma}(t)\cdot Q^{\rm tok})$ 以得转移比，又须避免矩阵–矩阵乘，且结果也无法存进内存。

To sidestep these issues, we follow prior work (Austin et al., 2021; Campbell et al., 2022) and use two standard matrices with special structures. They arise, respectively, from considering a fully connected graph structure and from introducing a MASK absorbing state (similar to the BERT language modeling paradigm (Devlin et al., 2019)):

为绕开这些问题，我们沿用先前工作（Austin et al., 2021；Campbell et al., 2022），采用两种具有特殊结构的标准矩阵。它们分别来自全连接图结构，以及引入 MASK 吸收态（类似 BERT 语言建模范式（Devlin et al., 2019））：

$$\displaystyle Q^{\rm uniform}=\begin{bmatrix}1-N&1&\cdots&1\
1&1-N&\cdots&1\
\vdots&\vdots&\ddots&\vdots\
1&1&\cdots&1-N\end{bmatrix} \ \displaystyle Q^{\rm absorb}=\begin{bmatrix}-1&0&\cdots&0&0\
0&-1&\cdots&0&0\
\vdots&\vdots&\ddots&\vdots&\vdots\
0&0&\cdots&-1&0\
1&1&\cdots&1&0\end{bmatrix} \tag{15}$$

With such a structured $Q$, one can quickly and cheaply compute all values in $\mathcal{L}_{\rm DWDSE}$. As such, our training iteration is about as fast and uses a similar amount of memory as standard autoregressive training. In particular, our training algorithm is given in Algorithm 1.

有了这种结构化 $Q$，即可快速廉价地计算 $\mathcal{L}_{\rm DWDSE}$ 中全部量。因而训练迭代速度与显存占用约与标准自回归训练相当。具体训练算法见算法 1。

4 Simulating Reverse Diffusion with Concrete Scores

4 用 Concrete Scores 模拟反向扩散

Given our scores $s_{\theta}$, we now derive various strategies for simulating a path $\mathbf{x}_{t}=x_{t}^{1}x_{t}^{2}\dots x_{t}^{d}\sim p_{t}$ of the reverse diffusion process. Notably, the additional information that we gain from $s_{\theta}$ being an approximate ratio of $p_{t}$ can be used to enhance the sampling process.

有了分数 $s_{\theta}$，我们推导多种策略来模拟反向扩散路径 $\mathbf{x}_{t}=x_{t}^{1}x_{t}^{2}\dots x_{t}^{d}\sim p_{t}$。值得注意的是，$s_{\theta}$ 作为 $p_{t}$ 近似比值所带来的额外信息，可用于增强采样过程。

4.1 Time-Reversal Strategies

4.1 时间反转策略

To simulate the diffusion in Definition 3.5, one may be tempted to use the Euler strategy from Equation 2. However, as noted in Campbell et al. (2022), this is inefficient because the structure of $Q_{t}^{\rm seq}$ only allows one position to be modified per step. Instead, a natural alternative has been to use $\tau$-leaping (Gillespie, 2001), which performs an Euler step at each position simultaneously. In particular, given a sequence $\mathbf{x}_{t}$, we construct $\mathbf{x}_{t-\Delta t}$ by sampling each token $x_{t-\Delta t}^{i}$ (independently) from the corresponding probability

要模拟定义 3.5 中的扩散，或许会想用式 2 的 Euler 策略。但如 Campbell et al.（2022）所指出，这低效，因为 $Q_{t}^{\rm seq}$ 的结构每步只允许改一个位置。自然替代是 $\tau$-leaping（Gillespie, 2001）：对各位置同时做 Euler 步。具体地，给定序列 $\mathbf{x}_{t}$，通过（独立地）从相应概率采样每个 token $x_{t-\Delta t}^{i}$ 来构造 $\mathbf{x}_{t-\Delta t}$

$$\delta_{x_{t}^{i}}(x_{t-\Delta t}^{i})+\Delta tQ_{t}^{\rm tok}(x_{t}^{i},x_{t-\Delta t}^{i})s_{\theta}(\mathbf{x}_{t},t)_{i,x_{t-\Delta t}^{i}} \tag{17}$$

While $\tau$-leaping is a viable simulation strategy, it is agnostic to fact that our $s_{\theta}$ approximates the true concrete score. In particular, knowing all $\frac{p_{t}(y)}{p_{t}(x)}$ enables optimal denoising, analogous to Tweedie’s theorem (Efron, 2011):

虽 $\tau$-leaping 可行，但它无视 $s_{\theta}$ 近似真实 concrete score 这一事实。特别地，知道全部 $\frac{p_{t}(y)}{p_{t}(x)}$ 即可最优去噪，类似于 Tweedie 定理（Efron, 2011）：

Theorem 4.1(Discrete Tweedie’s Theorem).

Suppose that $p_{t}$ follows the diffusion ODE $dp_{t}=Qp_{t}$. Then the true denoiser is given by

定理 4.1（离散 Tweedie 定理）。

设 $p_{t}$ 服从扩散 ODE $dp_{t}=Qp_{t}$。则真实去噪器由下式给出

$$p_{0|t}(x_{0}|x_{t})=\left(\exp(-tQ)\begin{bmatrix}\frac{p_{t}(i))}{p_{t}(x_{t})}\end{bmatrix}_{i=1}^{N}\right)_{x_{0}}\exp(tQ)(x_{t},x_{0}) \tag{18}$$

Unfortunately, we do not know all of the ratios (only ratios between Hamming distance 1 sequences). However, we can use this intuition to build a Tweedie denoiser analogue of $\tau$-leaping. In particular, we replace the token transition probabilities (for $x_{t-\Delta t}^{i}$) with the values

可惜我们不知道全部比值（仅知 Hamming 距离 1 的序列之间的比值）。但可用该直觉构造 $\tau$-leaping 的 Tweedie 去噪器类比。具体地，把（对 $x_{t-\Delta t}^{i}$ 的）token 转移概率替换为

$$\displaystyle\hskip-14.22636pt\big(\exp(-\sigma_{t}^{\Delta t}Q)s_{\theta}(\mathbf{x}_{t},t)_{i}\big)_{x_{t-\Delta t}^{i}}\exp(\sigma_{t}^{\Delta t}Q)(x_{t}^{i},x_{t-\Delta t}^{i}) \\ \displaystyle\text{where }\sigma_{t}^{\Delta t}=(\overline{\sigma}(t)-\overline{\sigma}(t-\Delta t)) \tag{19}$$

This generalizes the theorem but enforces the tau-leaping independence condition and, in fact, is optimal:

这推广了定理，同时强制 $\tau$-leaping 的独立性条件，且事实上是最优的：

Theorem 4.2(Tweedie $\tau$-leaping).

Let $p_{t-\Delta t|t}^{\rm tweedie}(\mathbf{x}_{t-\Delta t}|\mathbf{x}_{t})$ be the probability of the token update rule defined by Equation 19. Assuming $s_{\theta}$ is learned perfectly, this minimizes the KL divergence with the true reverse $p_{t-\Delta t|t}(\mathbf{x}_{t-\Delta t}|\mathbf{x}_{t})$ for all $\tau$-leaping strategies (i.e. token transitions are applied independently and simultaneously).

定理 4.2（Tweedie $\tau$-leaping）。

令 $p_{t-\Delta t|t}^{\rm tweedie}(\mathbf{x}_{t-\Delta t}|\mathbf{x}_{t})$ 为式 19 定义的 token 更新规则概率。假设 $s_{\theta}$ 学得完美，则该规则在所有 $\tau$-leaping 策略（即 token 转移独立且同时施加）中，最小化与真实反向 $p_{t-\Delta t|t}(\mathbf{x}_{t-\Delta t}|\mathbf{x}_{t})$ 的 KL 散度。

These simulation algorithms are unified in Algorithm 2.

这些模拟算法统一于算法 2。

4.2 Arbitrary Prompting and Infilling

4.2 任意提示与填空

Our concrete score can also be used to enable greater control over the generative process. This is due to the fact that we are modeling a function of the probability, allowing us to include conditional information through Bayes’ rule. In particular, we consider the infilling problem

Concrete score 还可用于增强对生成过程的控制。因我们建模的是概率的函数，可通过贝叶斯规则纳入条件信息。具体考虑填空问题

$$p_{t}(\mathbf{x}^{\Omega}|\mathbf{x}^{\overline{\Omega}}=\mathbf{y})\quad\Omega\text{ unfilled indices}\quad\overline{\Omega}\text{ filled} \tag{21}$$

As an example, a standard autoregressive conditional generation would have $\overline{\Omega}=\{1,2,\dots,c\}$ and $\Omega=\{c+1,c+2,\dots,d\}$. By Bayes’ rule, the conditional scores can be recovered exactly from the unconditional score.

例如，标准自回归条件生成对应 $\overline{\Omega}=\{1,2,\dots,c\}$、$\Omega=\{c+1,c+2,\dots,d\}$。由贝叶斯规则，条件分数可从无条件分数精确恢复。

$$\frac{p_{t}(\mathbf{x}^{\Omega}=\mathbf{z}^{\prime}|\mathbf{x}^{\overline{\Omega}}=\mathbf{y})}{p_{t}(\mathbf{x}^{\Omega}=\mathbf{z}|\mathbf{x}^{\overline{\Omega}}=\mathbf{y})}=\frac{p_{t}(\mathbf{x}=\mathbf{z}^{\prime}\oplus_{\Omega}\mathbf{y})}{p_{t}(\mathbf{x}=\mathbf{z}\oplus_{\Omega}\mathbf{y})} \tag{22}$$

where $\oplus_{\Omega}$ is concatenation along $\Omega$ and $\overline{\Omega}$. Since the unconditional and conditional scores coincide, we can use our $s_{\theta}$ (learned unconditionally) for conditional sampling (given arbitrary $\overline{\Omega}$). For a $\tau$-leaping update rule (Equation 17 or 19), one would only modify by changing the values at $\Omega$. An explicit pseudocode of this is given in Algorithm 3.

其中 $\oplus_{\Omega}$ 表示沿 $\Omega$ 与 $\overline{\Omega}$ 拼接。由于无条件与条件分数重合，可用（无条件学到的）$s_{\theta}$ 做条件采样（对任意 $\overline{\Omega}$）。对 $\tau$-leaping 更新规则（式 17 或 19），只需改 $\Omega$ 上的值。显式伪代码见算法 3。

5 Experiments

5 实验

We now empirically validate that our score entropy discrete diffusion (SEDD) model on a variety of language modeling tasks. We measure both perplexity (i.e. likelihood estimation capabilities) as well as generation quality, finding that our method performs quite well in both aspects.

我们在多种语言建模任务上实证验证分数熵离散扩散（SEDD）模型。同时度量困惑度（即似然估计能力）与生成质量，发现方法在两方面都表现良好。

5.1 Model and Training Setup

5.1 模型与训练设置

Size	Model	LAMBADA	WikiText2	PTB	WikiText103	1BW
Small	GPT-2	45.04	42.43	138.43	41.60	75.20
	SEDD Absorb	$\leq$50.92	$\leq$41.84	$\leq$114.24	$\leq$40.62	$\leq$79.29
	SEDD Uniform	$\leq$65.40	$\leq$50.27	$\leq$140.12	$\leq$49.60	$\leq$101.37
	D3PM	$\leq$93.47	$\leq$77.28	$\leq$200.82	$\leq$75.16	$\leq$138.92
	PLAID	$\leq$57.28	$\leq$51.80	$\leq$142.60	$\leq$50.86	$\leq$91.12
Medium	GPT-2	35.66	31.80	123.14	31.39	55.72
	SEDD Absorb	$\leq$42.77	$\leq$31.04	$\leq$87.12	$\leq$29.98	$\leq$61.19
	SEDD Uniform	$\leq$51.28	$\leq$38.93	$\leq$102.28	$\leq$36.81	$\leq$79.12

Table 1: Zero-shot unconditional perplexity ($\downarrow$) on a variety of datasets. For a fixed size, the best perplexity is bolded. Our SEDD model with absorbing transition beats GPT-2 (Radford et al., 2019) on a majority of the tasks and entirely outperforms prior language diffusion models (Austin et al., 2021; Gulrajani & Hashimoto, 2023).

规模	模型	LAMBADA	WikiText2	PTB	WikiText103	1BW
Small	GPT-2	45.04	42.43	138.43	41.60	75.20
	SEDD Absorb	$\leq$50.92	$\leq$41.84	$\leq$114.24	$\leq$40.62	$\leq$79.29
	SEDD Uniform	$\leq$65.40	$\leq$50.27	$\leq$140.12	$\leq$49.60	$\leq$101.37
	D3PM	$\leq$93.47	$\leq$77.28	$\leq$200.82	$\leq$75.16	$\leq$138.92
	PLAID	$\leq$57.28	$\leq$51.80	$\leq$142.60	$\leq$50.86	$\leq$91.12
Medium	GPT-2	35.66	31.80	123.14	31.39	55.72
	SEDD Absorb	$\leq$42.77	$\leq$31.04	$\leq$87.12	$\leq$29.98	$\leq$61.19
	SEDD Uniform	$\leq$51.28	$\leq$38.93	$\leq$102.28	$\leq$36.81	$\leq$79.12

表 1：多种数据集上的零样本无条件困惑度（$\downarrow$）。固定规模下最优困惑度加粗。带吸收转移的 SEDD 在多数任务上超过 GPT-2（Radford et al., 2019），并全面胜过先前语言扩散模型（Austin et al., 2021；Gulrajani & Hashimoto, 2023）。

Our core model is based on the diffusion transformer architecture (Peebles & Xie, 2023), which incorporates time conditioning into a standard encoder-only transformer architecture (Vaswani et al., 2017; Devlin et al., 2019), although we make some minor modifications such as employing rotary positional encoding (Su et al., 2021).

核心模型基于扩散 transformer 架构（Peebles & Xie, 2023），把时间条件并入标准仅编码器 transformer（Vaswani et al., 2017；Devlin et al., 2019），并做少量修改，例如采用旋转位置编码（Su et al., 2021）。

We construct SEDD Absorb and SEDD Uniform, which correspond to the matrices $Q^{\rm uniform}$ and $Q^{\rm absorb}$ respectively. We tested a geometric noise schedule (that interpolates between $10^{-5}$ and $20$), as well as a log-linear noise schedule (the number of changed tokens for total noise $\overline{\sigma}(t)$ is approximately $td$ for both transitions), which helps SEDD Absorb for perplexities. Outside of this, we did not systemically explore noise schedules or alternative loss weightings, although these could likely improve generation quality.

我们分别构造对应矩阵 $Q^{\rm uniform}$ 与 $Q^{\rm absorb}$ 的 SEDD Absorb 与 SEDD Uniform。测试了在 $10^{-5}$ 与 $20$ 之间插值的几何噪声日程，以及对数线性噪声日程（对两种转移，总噪声 $\overline{\sigma}(t)$ 下约改变 $td$ 个 token），后者有助于 SEDD Absorb 的困惑度。除此之外未系统探索噪声日程或替代损失加权，尽管它们可能改进生成质量。

When training, we employ sentence packing to create uniform length blocks to feed to our model, which is done typically for language modeling tasks. The only exception to this rule is our experiment on text8, which randomly samples contiguous subsequences to match prior work (Austin et al., 2021) (although we found that this did not substantially change results). We also matched architecture hyperparameters with prior work (including number of layers, hidden dimension, attention heads, etc…), although our models have slightly more parameters ($\approx 5-10\%$) than a typical transformer due to time conditioning. We also use the same tokenizers as prior work (which otherwise could be a source of artifacts) as well as the same data splits.

训练时用句子打包构造等长块喂给模型，这是语言建模常见做法。唯一例外是 text8 实验：为匹配先前工作（Austin et al., 2021）而随机采样连续子序列（我们发现这不实质改变结果）。架构超参也与先前工作对齐（层数、隐藏维、注意力头等），但因时间条件，参数量比典型 transformer 略多（约 $5$–$10\%$）。分词器与数据划分亦与先前工作相同（否则可能引入伪影）。

5.2 Language Modeling Comparison

5.2 语言建模比较

We begin by evaluating our model on core language modeling (effectively likelihood-based modeling) on three common datasets across a variety of scales.

首先在三个常用数据集、多种规模上评估核心语言建模（实质是基于似然的建模）。

5.2.1 Text 8 Dataset

We compare on the text8 dataset, a small, character level language modeling task. We follow Austin et al. (2021) for network hyperparameters and dataset splits and compare with methods that employ a similar model size.

5.2.1 Text8 数据集

我们在 text8——小型字符级语言建模任务——上比较。网络超参与数据划分遵循 Austin et al.（2021），并与采用相近模型规模的方法对比。

We report bits per character (BPC) in Table 2. SEDD outperforms other non-autoregressive models and is only beaten by an autoregressive transformer and the discrete flow (which incorporates an autoregressive base distribution) (Tran et al., 2019). Furthermore, SEDD substantially improves upon D3PM (Austin et al., 2021), despite both being built from the same discrete diffusion principles.

表 2 报告每字符比特数（BPC）。SEDD 胜过其他非自回归模型，仅输给自回归 transformer 与离散流（后者含自回归基分布）（Tran et al., 2019）。此外，尽管同基于离散扩散原理，SEDD 相对 D3PM（Austin et al., 2021）有大幅改进。

5.2.2 One Billion Words Dataset

Type	Method	BPC ($\downarrow$)
Autoregressive Backbone	IAF/SCF	1.88
	AR Argmax Flow	1.39
	Discrete Flow	1.23
	Autoregressive	1.23
Non-autoregressive	Mult. Diffusion	$\leq$ 1.72
	MAC	$\leq$ 1.40
	BFN	$\leq$ 1.41
	D3PM Uniform	$\leq$ 1.61
	D3PM Absorb	$\leq$ 1.45
Ours (NAR)	SEDD Uniform	$\leq$ 1.47
	SEDD Absorb	$\leq$ 1.39

Table 2: Bits Per Character on text8. Our SEDD models achieve second-best overall result (best for non-autoregressive), only being beaten out by the autoregressive model and a discrete flow (which uses an autoregressive model as a backbone) by a small margin. SEDD also substantially improves upon prior the discrete diffusion model D3PM (Austin et al., 2021).

5.2.2 One Billion Words 数据集

类型	方法	BPC（$\downarrow$）
自回归骨干	IAF/SCF	1.88
	AR Argmax Flow	1.39
	Discrete Flow	1.23
	Autoregressive	1.23
非自回归	Mult. Diffusion	$\leq$ 1.72
	MAC	$\leq$ 1.40
	BFN	$\leq$ 1.41
	D3PM Uniform	$\leq$ 1.61
	D3PM Absorb	$\leq$ 1.45
本文（NAR）	SEDD Uniform	$\leq$ 1.47
	SEDD Absorb	$\leq$ 1.39

表 2：text8 上的每字符比特数。SEDD 整体第二（非自回归最佳），仅以小幅差距输给自回归模型与以自回归为骨干的离散流。相对先前离散扩散模型 D3PM（Austin et al., 2021）亦有大幅改进。

We also test SEDD on One Billion Words, a more medium sized and real world dataset. We follow He et al. (2022) for the tokenization, training, and model size configurations. In particular, our baselines are all around the size of GPT-2 small. Following He et al. (2022), we compare primarily against other language diffusion models, although we also train a standard autoregressive transformer as a benchmark.

我们也在更中等规模、更贴近真实的 One Billion Words 上测试 SEDD。分词、训练与模型规模配置遵循 He et al.（2022）。基线约 GPT-2 small 规模。按 He et al.（2022），主要与其他语言扩散模型比较，同时训练标准自回归 transformer 作基准。

We report perplexity values in Table 3. Our SEDD model outperforms all other diffusion language modeling schemes by $50$-$75\%$ lower perplexity (in particular D3PM). Furthermore, SEDD is within $1$ perplexity of the autoregressive model, likely matching since we only report an upper bound.

表 3 报告困惑度。SEDD 相对所有其他扩散语言建模方案困惑度低约 $50$–$75\%$（尤其相对 D3PM）。此外 SEDD 与自回归模型相差不到 $1$ 个困惑度，因我们只报告上界，实际可能持平。

Type	Method	Perplexity ($\downarrow$)
Autoregressive	Transformer	31.98
Diffusion	D3PM Absorb	$\leq$ 77.50
	Diffusion-LM	$\leq$ 118.62
	BERT-Mouth	$\leq$ 142.89
	DiffusionBert	$\leq$ 63.78
Ours (Diffusion)	SEDD Uniform	$\leq$ 40.25
	SEDD Absorb	$\leq$ 32.79

Table 3: Test perplexities on the One Billion Words Dataset. The autoregressive result is an exact likelihood, while the diffusion results are upper bounds. SEDD beats all other discrete diffusion models (by at least $2\times$) while matching the autoregressive baseline.

类型	方法	困惑度（$\downarrow$）
自回归	Transformer	31.98
扩散	D3PM Absorb	$\leq$ 77.50
	Diffusion-LM	$\leq$ 118.62
	BERT-Mouth	$\leq$ 142.89
	DiffusionBert	$\leq$ 63.78
本文（扩散）	SEDD Uniform	$\leq$ 40.25
	SEDD Absorb	$\leq$ 32.79

表 3：One Billion Words 测试困惑度。自回归结果为精确似然，扩散结果为上界。SEDD 胜过所有其他离散扩散模型（至少 $2\times$），并匹配自回归基线。

GPT-2 S	a hiring platform that ”includes a fun club meeting place,” says petitioner’s AQQFredericks. They’s the adjacent marijuana-hop. Others have allowed 3B Entertainment
GPT-2 M	misused, whether via Uber, a higher-order reality of quantified impulse or the No Mass Paralysis movement, but the most shamefully universal example is gridlock
SEDD S	As Jeff Romer recently wrote, “The economy has now reached a corner - 64% of household wealth and 80% of wealth goes to credit cards because of government austerity
SEDD M	Wyman worked as a computer science coach before going to work with the U.S. Secret Service in upstate New York in 2010. Without a license, the Secret Service will have to

(a) Generative Perplexity $(\downarrow)$ vs. Sampling Iterations.

GPT-2 S	一家招聘平台「含有趣俱乐部聚会点」，申请人 AQQFredericks 称。他们旁边是大麻跳点。其他人已允许 3B Entertainment
GPT-2 M	被滥用，无论经由 Uber、量化冲动的高阶现实，还是「无大规模瘫痪」运动，最可耻的普遍例子是交通堵塞
SEDD S	如 Jeff Romer 近日所写，「经济已走到拐角——因政府紧缩，家庭财富的 64% 与财富的 80% 流向信用卡
SEDD M	Wyman 曾任计算机科学教练，2010 年赴纽约州北部与美国特勤局共事。没有执照，特勤局将不得不

（a）生成困惑度（$\downarrow$）相对采样迭代次数。

5.2.3 GPT-2 Zero Shot Tasks

Finally, we compare SEDD against GPT-2 (Radford et al., 2019). We train on OpenWebText as the original WebText dataset has not been made available (this is typical practice and does not meaningfully affect results in practice) (Gokaslan & Cohen, 2019) and test on the LAMBADA, WikiText2, PTB, WikiText103, and One Billion Words datasets (which were all of the GPT-2 zero-shot tasks that measured perplexity). We recompute baseline likelihoods for all datasets except 1BW, where we encountered unexpected behavior with the public implementations. Our likelihood computation changes from the original setting since we evaluate unconditionally (i.e. without a sliding window), and this results in higher values than originally reported.

5.2.3 GPT-2 零样本任务

最后将 SEDD 与 GPT-2（Radford et al., 2019）比较。因原始 WebText 未公开，我们在 OpenWebText 上训练（常见做法，实践中不实质影响结果）（Gokaslan & Cohen, 2019），并在 LAMBADA、WikiText2、PTB、WikiText103 与 One Billion Words 上测试（均为 GPT-2 零样本中度量困惑度的任务）。除 1BW 外重算全部基线似然——1BW 上公开实现出现意外行为。似然计算相对原设定改为无条件评估（即无滑动窗口），因而数值高于原报告。

Our results are reported in Table 1. Our SEDD Absorb beats GPT-2 on a majority of the zero-shot tasks across both sizes. To the best of our knowledge, this is the first time where a non-autoregressive language model has matched a modern, reasonably sized, and well-known autoregressive model for perplexities. We also compare against the most competitive continuous (Gulrajani & Hashimoto, 2023) and discrete (Austin et al., 2021) diffusion baselines, seeing a large improvement over both.

结果见表 1。SEDD Absorb 在两种规模的多数零样本任务上超过 GPT-2。据我们所知，这是非自回归语言模型首次在困惑度上匹配现代、规模合理且广为人知的自回归模型。我们也与最有竞争力的连续（Gulrajani & Hashimoto, 2023）与离散（Austin et al., 2021）扩散基线比较，相对两者均有大幅改进。

5.3 Language Generation Comparison

5.3 语言生成比较

With our trained models, we compare against prior work in terms of generation quality. In particular, we compare GPT-2 with our SEDD Absorb on a variety of scales. Results for SEDD Uniform are given in Appendix D.

用训练好的模型，在生成质量上与先前工作比较。具体在多种规模上将 GPT-2 与 SEDD Absorb 对比。SEDD Uniform 结果见附录 D。

5.3.1 Unconditional Generation

We first compare the quality of unconditional samples between GPT-2 and SEDD. As most language metrics are meant for comparing conditional generations (Pillutla et al., 2021), we instead measure the generative perplexity of sampled sequences (using a GPT-2 large model for evaluation). This is a simple and common metric (Han et al., 2022; Dieleman et al., 2022) but can easily be “hacked” by simple distribution annealing methods. So, we compare analytically sampled generations (i.e. no temperature scaling).

5.3.1 无条件生成

先比较 GPT-2 与 SEDD 的无条件样本质量。多数语言指标面向条件生成（Pillutla et al., 2021），故改用采样序列的生成困惑度（以 GPT-2 large 评估）。该指标简单常见（Han et al., 2022；Dieleman et al., 2022），但易被简单分布退火「刷分」。因此我们比较解析采样的生成（即无温度缩放）。

For SEDD, we simulate using 32 to 2048 steps, which approximates the learned distribution with minimal error for a large number of steps (the sequences are length 1024). Our results (both the measured generative perplexity and some samples) are shown in Figure 1. SEDD matches GPT-2 quality using 32$\times$ fewer network evaluations and outperforms by $6$-$8\times$ when using the full 2048 steps. Furthermore, SEDD forms a predictable log-log linear pareto frontier between the number of sampling steps and generative perplexity. However, each network evaluation is different due to the KV-cache, which introduces a cost benefit tradeoff that we discuss more in Section 6.

对 SEDD，用 32 到 2048 步模拟；步数大时对学到的分布近似误差很小（序列长 1024）。结果（测得的生成困惑度与部分样本）见图 1。SEDD 用少约 32$\times$ 的网络评估即可匹配 GPT-2 质量；用满 2048 步时优于约 $6$–$8\times$。此外 SEDD 在采样步数与生成困惑度之间形成可预期的对数–对数线性帕累托前沿。不过因 KV-cache，每次网络评估成本不同，第 6 节再讨论成本收益权衡。

A bow and arrow is a traditional weapon that enables an attacker to attack targets at a range within a meter or maybe two meters. They have a range far longer than a human can walk, and they can be fired …
$\dots$ skydiving is a fun sport that makes me feel incredibly silly. I think I may’ve spent too much, but it could’ve been amazing! While sky diving gives us exercise and fun, scuba diving is an act of physical fitness, …
$\dots$ no one expected the results to much better than last year’s one-sided endorsement. Nearly 90 percent of the results were surveyed as ”independent,” an promising result for school children across the country.
$\dots$ results show that Donald Trump and Hillary Clinton are in 38 states combined with less than 1% of the national vote. In a way, it’s Trump and Hillary Clinton who will work overtime to get people to vote this $\dots$

Table 4: Conditionally Generated Text. Prompt tokens are given in blue. Our model is able to generate meaningful text with prompt tokens in the front, the end, the middle, or even split up. Additional samples are given in Appendix D.3.

弓箭是传统武器，使攻击者可在一米或两三米范围内打击目标。射程远长于人步行距离，并可被发射……
$\dots$ 跳伞是有趣运动，让我感觉特别傻。我想也许花太多了，但本可以很棒！跳伞带来锻炼与乐趣，而潜水是体能活动……
$\dots$ 无人料到结果会比去年一边倒的背书好得多。近 90% 的结果被调查为「独立」，对全国学童是可喜结果。
$\dots$ 结果显示 Donald Trump 与 Hillary Clinton 合计在 38 州得票不到全国选票的 1%。某种意义上，正是他们加班加点动员人们投票……

表 4：条件生成文本。提示 token 以蓝色标出。模型能在前部、尾部、中部甚至拆分提示下生成有意义文本。更多样本见附录 D.3。

5.3.2 Infilling Conditional Generation

Finally, we showcase SEDD’s ability for conditional generation. We generate samples conditioned on a fixed amount of input text (from the WebText dataset) and compare their MAUVE scores (Pillutla et al., 2021). For SEDD, we consider two prompting strategies: standard generation given the beginning and infilling using the beginning and end, although obviously more sampling strategies exist (and several are visualized in Table 4).

5.3.2 填空式条件生成

最后展示 SEDD 的条件生成能力。在固定数量输入文本（来自 WebText）条件下生成样本，并比较 MAUVE 分数（Pillutla et al., 2021）。对 SEDD 考虑两种提示：给定开头的标准生成，以及用开头与结尾填空；显然还有更多采样策略（表 4 可视化若干）。

We compare against GPT-2 and SSD-LM (Han et al., 2022), a competitive language diffusion model built for this task (all models are medium sized). Interestingly, a critical component for both baselines is distribution annealing: nucleus sampling for autoregressive modeling (Holtzman et al., 2019) (which clips the token probability) and thresholding for diffusion (Li et al., 2022; Lou & Ermon, 2023) (which constrains generation to disallow paths in low probability spaces). As introducing similar annealing methods for SEDD is out of scope for this paper, we compare against both the annealed and un-annealed baselines samples.

我们与 GPT-2 以及专为此任务设计的有竞争力语言扩散模型 SSD-LM（Han et al., 2022）比较（模型均为 medium）。有趣的是，两条基线的关键组件都是分布退火：自回归用 nucleus 采样（Holtzman et al., 2019）（裁剪 token 概率），扩散用阈值（Li et al., 2022；Lou & Ermon, 2023）（约束生成、禁止低概率路径）。为 SEDD 引入类似退火超出本文范围，故同时与退火与未退火基线样本比较。

Our results are given in Table 5. SEDD is highly competitive with the best configuration for both baselines, in fact beating both when using standard prompting. This is rather notable since SEDD does not use distribution annealing and does not explicitly encode left to right prompting as an architectural inductive bias (while GPT-2 and SSD-LM were trained explicitly for autoregressive-like generation).

结果见表 5。SEDD 与两条基线的最佳配置高度竞争，标准提示下甚至超过两者。尤其值得注意：SEDD 未用分布退火，也未把从左到右提示作为架构归纳偏置显式编码（而 GPT-2 与 SSD-LM 专为类自回归生成训练）。

Method	Annealing	Mauve ($\uparrow$)
GPT-2	Nucleus-0.95	0.955
	None	0.802
SSD-LM	Logit Threshold-0.95	0.919
	None	0.312
SEDD Standard	None	0.957
SEDD Infill	None	0.942

Table 5: Evaluation of conditionally generated text. SEDD with standard prompting beats both GPT-2 and SSD-LM. SEDD also offers more flexibility (enabling infilling generation with comparable performance) and does not require distribution annealing techniques for good generation.

方法	退火	Mauve（$\uparrow$）
GPT-2	Nucleus-0.95	0.955
	无	0.802
SSD-LM	Logit Threshold-0.95	0.919
	无	0.312
SEDD 标准	无	0.957
SEDD 填空	无	0.942

表 5：条件生成文本评估。标准提示下 SEDD 超过 GPT-2 与 SSD-LM。SEDD 也更灵活（可填空且表现可比），且无需分布退火即可良好生成。

6 Related Work

6 相关工作

Continuous Diffusion Models for Text Data. Initially proposed by Li et al. (2022), continuous language diffusion models embed tokens in a latent space, learn a diffusion model there, and take the nearest neighbor to dequantize. While initial versions struggled, these models have achieved significant results by iterating on several empirical components. For example, prior works improve downstream performance with alternative loss functions (moving away from likelihood-based score matching) (Han et al., 2022; Mahabadi et al., 2023) and explicitly encoding conditional information (e.g. inputting an infilling mask) (Gong et al., 2023; Dieleman et al., 2022). Additionally, distribution annealing methods like thresholding (Li et al., 2022) and classifier-free guidance (Ho, 2022) can further improve generation quality, although recent work has shown that methods like self-conditioning (Strudel et al., 2022) and designing a less sparse embedding space (e.g. based on bits) (Chen et al., 2022) can obviate the need for such methods. Finally, Gulrajani & Hashimoto (2023) showed that, with many surgical changes to the training paradigm, it is possible for language diffusion models to begin approaching autoregressive performance for likelihoods.

面向文本的连续扩散模型。 最初由 Li et al.（2022）提出：把 token 嵌入潜空间，在潜空间学扩散，再取最近邻反量化。早期版本挣扎，后续靠迭代若干经验组件取得显著结果。例如，先前工作用替代损失函数（离开基于似然的分数匹配）改进下游表现（Han et al., 2022；Mahabadi et al., 2023），并显式编码条件信息（例如输入填空掩码）（Gong et al., 2023；Dieleman et al., 2022）。此外，阈值（Li et al., 2022）与无分类器引导（Ho, 2022）等分布退火可进一步改进生成质量；近期工作表明自条件（Strudel et al., 2022）与设计更不稀疏的嵌入空间（例如基于比特）（Chen et al., 2022）可削弱对此类方法的依赖。最后，Gulrajani & Hashimoto（2023）表明：经对训练范式做大量手术式改动，语言扩散模型开始在似然上逼近自回归表现。

Discrete Diffusion Models. Most discrete diffusion works follow the framework set out by D3PM (Austin et al., 2021) which mimics “mean prediction” (Ho et al., 2020). These discrete diffusion methods are largely applied to fields other than language (e.g. images), likely due to empirical challenges. Despite this, some works have shown strong performance on language, particularly for seq-to-seq tasks and more efficient generation (Zheng et al., 2023; Chen et al., 2023; Ye et al., 2023). Notably, from these works discrete diffusion has tended to be advantageous over continuous diffusion in reducing network evaluations.

离散扩散模型。 多数离散扩散工作遵循 D3PM（Austin et al., 2021）框架，模仿「均值预测」（Ho et al., 2020）。这些方法大多用于语言以外领域（如图像），或因实证挑战。尽管如此，仍有工作在语言上表现强劲，尤其是 seq-to-seq 与更高效生成（Zheng et al., 2023；Chen et al., 2023；Ye et al., 2023）。值得注意的是，这些工作中离散扩散往往在减少网络评估方面优于连续扩散。

SEDD vs Prior Work. SEDD is a discrete diffusion model that focuses on score matching, the crucial ingredient for continuous diffusions (Song & Ermon, 2019; Ho et al., 2020). Many such works also focus on reversing a discrete diffusion process (Campbell et al., 2022; Benton et al., 2022; Sun et al., 2023), so score entropy is naturally related with prior training objectives. However, SEDD focuses on a principled, scalable, and performant objective (namely denoising score entropy), filling in shortcomings found in previous works. In particular, prior methods train either with the equivalent of implicit score entropy (which is intractable and high variance) or propose alternate losses that suffer from other issues. These critical differences enable large improvements for language tasks, where prior discrete diffusion models have conspicuously struggled on.

SEDD 与先前工作。 SEDD 是聚焦分数匹配的离散扩散模型——连续扩散的关键要素（Song & Ermon, 2019；Ho et al., 2020）。许多工作也聚焦反转离散扩散过程（Campbell et al., 2022；Benton et al., 2022；Sun et al., 2023），因而分数熵与先前训练目标自然相关。但 SEDD 聚焦有原则、可扩展且表现好的目标（即去噪分数熵），填补先前工作的短板。特别地，先前方法要么用等价于隐式分数熵的训练（不可行且方差高），要么提出有其他问题的替代损失。这些关键差异带来语言任务上的大幅改进——先前离散扩散在此明显挣扎。

Furthermore, SEDD achieves better results (for both perplexity and generation) than even continuous diffusion models (without resorting to empirically driven heuristics). This is desirable since discrete data should necessitate a novel approach. Future work could adapt empirical designs from continuous diffusion, further improving performance.

此外，SEDD 在困惑度与生成上甚至优于连续扩散模型（且不诉诸经验启发式）。这是可取的，因为离散数据本应需要新方法。未来工作可吸收连续扩散的经验设计，进一步改进表现。

Finally, SEDD challenges autoregressive models, achieving competitive perplexities (beating GPT-2) and generation quality (beating nucleus sampling). While there is still a large gap with modern large language models, we believe that future work can bridge this using SEDD as a backbone.

最后，SEDD 挑战自回归模型：困惑度具竞争力（超过 GPT-2），生成质量超过 nucleus 采样。与现代大语言模型仍有大差距，但我们相信未来可以 SEDD 为骨干弥合差距。

SEDD vs Autoregressive Sampling Iterations. SEDD and autoregressive models have significantly different sampling procedures due to the introduction of the KV-cache for standard decoder-only transformer models. In particular, this complicates the inference code (as each network pass changes from being a standard full batch forward) and trades off speed with memory. For example, for our (known) unoptimized codebase and the existing huggingface transformers library (Wolf et al., 2020), we observed that SEDD matches autoregressive inference time when using around 100 steps but can increase the batch size by roughly $4-6$ times by removing the KV-cache memory. Future work will likely decrease the steps required for optimal generation (similar to existing work in standard diffusion (Song et al., 2021a)) which can improve this tradeoff.

SEDD 与自回归采样迭代。 因标准仅解码器 transformer 引入 KV-cache，SEDD 与自回归的采样流程差异显著。这使推理代码更复杂（每次网络前向不再是标准整批前向），并在速度与显存间权衡。例如，在我们（已知）未优化的代码库与现有 huggingface transformers 库（Wolf et al., 2020）上，观察到约 100 步时 SEDD 匹配自回归推理时间，但去掉 KV-cache 显存后批大小约可增 $4$–$6$ 倍。未来工作或会降低最优生成所需步数（类似标准扩散既有工作（Song et al., 2021a）），从而改进该权衡。

7 Conclusion

7 结论

We have introduced score entropy discrete diffusion (SEDD) models, a discrete diffusion model that is parameterized by the concrete score and can be trained efficiently with our novel score entropy loss. SEDD beats previous language diffusion models and rivals autoregressive models for both perplexity and quality. We hope that future work can build off our framework to defines alternatives to the modern autoregressive language modeling paradigm.

我们提出分数熵，一种为离散扩散设计的新型分数匹配损失。所得 SEDD 模型在标准语言建模任务上取得强结果，尤其在困惑度与样本质量上超过 GPT-2。我们希望这些发现能激励未来工作，在离散数据域上推进生成建模。

Impact Statement

影响声明

This paper proposes work that advances the field of natural language generation. Outside of existing ethical questions for this area (e.g. bias, toxicity, fake content), our approach does not present any specific danger as the core work is largely theoretical and not at the scale to pose a specific problem.

本文提出分数熵离散扩散模型（SEDD），推进离散域生成建模。潜在社会影响与其他语言生成模型类似，包括误用风险与偏见传播；我们未引入超出标准语言模型的新危害面。代码与模型检查点将公开以促进可复现研究。

Acknowledgements

致谢

This project was supported by NSF (#1651565), ARO (W911NF-21-1-0125), ONR (N00014-23-1-2159), CZ Biohub, a Stanford HAI GCP grant. AL is supported by a NSF Graduate Research Fellowship.

我们感谢匿名审稿人的建设性意见。本研究部分得到 NSF、ONR 与其他资助支持；详细致谢见正式会议版本。

References

参考文献

Anderson (2012) Anderson, W. J. Continuous-time Markov chains: An applications-oriented approach . Springer Science & Business Media, 2012.

Austin et al. (2021) Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and van den Berg, R. Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems , 2021.

Benton et al. (2022) Benton, J., Shi, Y., Bortoli, V. D., Deligiannidis, G., and Doucet, A. From denoising diffusions to denoising markov models. ArXiv , abs/2211.03595, 2022. URL https://api.semanticscholar.org/CorpusID:253384277 .

Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Advances in Neural Information Processing Systems , volume 33, 2020.

Campbell et al. (2022) Campbell, A., Benton, J., Bortoli, V. D., Rainforth, T., Deligiannidis, G., and Doucet, A. A continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems , 2022.

Chen & Duvenaud (2019) Chen, R. T. Q. and Duvenaud, D. K. Neural networks with cheap differential operators. In Neural Information Processing Systems , 2019.

Chen et al. (2022) Chen, T., Zhang, R., and Hinton, G. Analog bits: Generating discrete data using diffusion models with self-conditioning. arXiv preprint arXiv:2208.04202 , 2022.

Chen et al. (2023) Chen, Z., Yuan, H., Li, Y., Kou, Y., Zhang, J., and Gu, Q. Fast sampling via de-randomization for discrete diffusion models. arXiv preprint arXiv:2312.09193 , 2023.

Dao et al. (2022) Dao, T., Fu, D. Y., Ermon, S., Rudra, A., and R’e, C. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Neural Information Processing Systems , 2022.

Devlin et al. (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) . Association for Computational Linguistics, 2019.

Dieleman et al. (2022) Dieleman, S., Sartran, L., Roshannai, A., Savinov, N., Ganin, Y., Richemond, P. H., Doucet, A., Strudel, R., Dyer, C., Durkan, C., Hawthorne, C., Leblond, R., Grathwohl, W., and Adler, J. Continuous diffusion for categorical data. ArXiv , abs/2211.15089, 2022.

Efron (2011) Efron, B. Tweedie’s formula and selection bias. Journal of the American Statistical Association , 106:1602 – 1614, 2011. URL https://api.semanticscholar.org/CorpusID:23284154 .

Gillespie (2001) Gillespie, D. T. Approximate accelerated stochastic simulation of chemically reacting systems. Journal of Chemical Physics , 115:1716–1733, 2001. URL https://api.semanticscholar.org/CorpusID:5109777 .

Gokaslan & Cohen (2019) Gokaslan, A. and Cohen, V. Openwebtext corpus. http://Skylion007.github.io/OpenWebTextCorpus , 2019.

Gong et al. (2023) Gong, S., Li, M., Feng, J., Wu, Z., and Kong, L. Diffuseq: Sequence to sequence text generation with diffusion models. In The Eleventh International Conference on Learning Representations , 2023.

Graves et al. (2023) Graves, A., Srivastava, R. K., Atkinson, T., and Gomez, F. Bayesian flow networks. arXiv preprint arXiv:2308.07037 , 2023.

Gulrajani & Hashimoto (2023) Gulrajani, I. and Hashimoto, T. Likelihood-based diffusion language models. In Advances in Neural Information Processing Systems , 2023.

Han et al. (2022) Han, X., Kumar, S., and Tsvetkov, Y. Ssd-lm: Semi-autoregressive simplex-based diffusion language model for text generation and modular control. arXiv preprint arXiv:2210.17432 , 2022.

Hanson (2007) Hanson, F. B. Applied Stochastic Processes and Control for Jump-Diffusions: Modeling, Analysis and Computation . Society for Industrial and Applied Mathematics, Philadelphia, PA, 2007. doi: 10.1137/1.9780898718638 . URL https://epubs.siam.org/doi/abs/10.1137/1.9780898718638 .

He et al. (2022) He, Z., Sun, T., Wang, K., Huang, X., and Qiu, X. Diffusionbert: Improving generative masked language models with diffusion models. In Annual Meeting of the Association for Computational Linguistics , 2022.

Ho (2022) Ho, J. Classifier-free diffusion guidance. ArXiv , abs/2207.12598, 2022. URL https://api.semanticscholar.org/CorpusID:249145348 .

Ho et al. (2020) Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems , 2020.

Holtzman et al. (2019) Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y. The curious case of neural text degeneration. In International Conference on Learning Representations , 2019.

Hoogeboom et al. (2021) Hoogeboom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems , 34:12454–12465, 2021.

Hutchinson (1989) Hutchinson, M. F. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics - Simulation and Computation , 18:1059–1076, 1989. URL https://api.semanticscholar.org/CorpusID:120969358 .

Hyvärinen (2005) Hyvärinen, A. Estimation of non-normalized statistical models by score matching. J. Mach. Learn. Res. , 6:695–709, 2005.

Hyvärinen (2007) Hyvärinen, A. Some extensions of score matching. Comput. Stat. Data Anal. , 51:2499–2512, 2007. URL https://api.semanticscholar.org/CorpusID:2352990 .

Kelly (1980) Kelly, F. Reversibility and stochastic networks. 1980. URL https://api.semanticscholar.org/CorpusID:125211322 .

Li et al. (2022) Li, X., Thickstun, J., Gulrajani, I., Liang, P. S., and Hashimoto, T. B. Diffusion-lm improves controllable text generation. In Advances in Neural Information Processing Systems , 2022.

Lou & Ermon (2023) Lou, A. and Ermon, S. Reflected diffusion models. In International Conference on Machine Learning . PMLR, 2023.

Mahabadi et al. (2023) Mahabadi, R. K., Tae, J., Ivison, H., Henderson, J., Beltagy, I., Peters, M. E., and Cohan, A. Tess: Text-to-text self-conditioned simplex diffusion. arXiv preprint arXiv:2305.08379 , 2023.

Meng et al. (2021) Meng, C., He, Y., Song, Y., Song, J., Wu, J., Zhu, J.-Y., and Ermon, S. Sdedit: Guided image synthesis and editing with stochastic differential equations. In International Conference on Learning Representations , 2021. URL https://api.semanticscholar.org/CorpusID:245704504 .

Meng et al. (2022) Meng, C., Choi, K., Song, J., and Ermon, S. Concrete score matching: Generalized score matching for discrete data. In Advances in Neural Information Processing Systems , 2022.

Øksendal (1987) Øksendal, B. Stochastic differential equations : an introduction with applications. Journal of the American Statistical Association , 82:948, 1987.

Peebles & Xie (2023) Peebles, W. S. and Xie, S. Scalable diffusion models with transformers. In International Conference on Computer Vision , 2023.

Pillutla et al. (2021) Pillutla, K., Swayamdipta, S., Zellers, R., Thickstun, J., Welleck, S., Choi, Y., and Harchaoui, Z. Mauve: Measuring the gap between neural text and human text using divergence frontiers. Advances in Neural Information Processing Systems , 34:4816–4828, 2021.

Radford et al. (2019) Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsupervised multitask learners. 2019. URL https://api.semanticscholar.org/CorpusID:160025533 .

Ramesh et al. (2022) Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., and Chen, M. Hierarchical text-conditional image generation with clip latents. ArXiv , abs/2204.06125, 2022. URL https://api.semanticscholar.org/CorpusID:248097655 .

Shih et al. (2022) Shih, A., Sadigh, D., and Ermon, S. Training and inference on any-order autoregressive models the right way. Advances in Neural Information Processing Systems , 35:2762–2775, 2022.

Sohl-Dickstein et al. (2015) Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning , 2015.

Song et al. (2021a) Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models. In International Conference on Learning Representations , 2021a. URL https://openreview.net/forum?id=St1giarCHLP .

Song & Ermon (2019) Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. In Neural Information Processing Systems , 2019.

Song et al. (2019) Song, Y., Garg, S., Shi, J., and Ermon, S. Sliced score matching: A scalable approach to density and score estimation. In Conference on Uncertainty in Artificial Intelligence , 2019.

Song et al. (2021b) Song, Y., Durkan, C., Murray, I., and Ermon, S. Maximum likelihood training of score-based diffusion models. In Neural Information Processing Systems , 2021b.

Song et al. (2021c) Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations , 2021c. URL https://openreview.net/forum?id=PxTIG12RRHS .

Strudel et al. (2022) Strudel, R., Tallec, C., Altché, F., Du, Y., Ganin, Y., Mensch, A., Grathwohl, W. S., Savinov, N., Dieleman, S., Sifre, L., et al. Self-conditioned embedding diffusion for text generation. 2022.

Su et al. (2021) Su, J., Lu, Y., Pan, S., Wen, B., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding. ArXiv , abs/2104.09864, 2021.

Sun et al. (2023) Sun, H., Yu, L., Dai, B., Schuurmans, D., and Dai, H. Score-based continuous-time discrete diffusion models. In The Eleventh International Conference on Learning Representations , 2023.

Tran et al. (2019) Tran, D., Vafa, K., Agrawal, K., Dinh, L., and Poole, B. Discrete flows: Invertible generative models of discrete data. Advances in Neural Information Processing Systems , 32, 2019.

Vaswani et al. (2017) Vaswani, A., Shazeer, N. M., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In NIPS , 2017.

Vincent (2011) Vincent, P. A connection between score matching and denoising autoencoders. Neural Computation , 23:1661–1674, 2011.

Wang & Cho (2019) Wang, A. and Cho, K. Bert has a mouth, and it must speak: Bert as a markov random field language model. arXiv preprint arXiv:1902.04094 , 2019.

Wolf et al. (2020) Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Le Scao, T., Gugger, S., Drame, M., Lhoest, Q., and Rush, A. Transformers: State-of-the-art natural language processing. In Liu, Q. and Schlangen, D. (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations , pp. 38–45, Online, October 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.emnlp-demos.6 . URL https://aclanthology.org/2020.emnlp-demos.6 .

Ye et al. (2023) Ye, J., Zheng, Z., Bao, Y., Qian, L., and Wang, M. Dinoiser: Diffused conditional sequence learning by manipulating noises. arXiv preprint arXiv:2302.10025 , 2023.

Yule (1971) Yule, G. U. On a method of investigating periodicities in disturbed series with special reference to wolfer’s sunspot numbers. Statistical Papers of George Udny Yule , pp. 389–420, 1971.

Zheng et al. (2023) Zheng, L., Yuan, J., Yu, L., and Kong, L. A reparameterized discrete diffusion model for text generation. ArXiv , abs/2302.05737, 2023.

Ziegler & Rush (2019) Ziegler, Z. and Rush, A. Latent normalizing flows for discrete sequences. In International Conference on Machine Learning , pp. 7673–7682. PMLR, 2019.

Appendix A Proof of Main Results

附录 A 主要结果的证明

Proof of Prop 3.2.

Given infinite samples, the loss becomes equivalent to minimizing

命题 3.2 的证明。给定无穷多样本，损失等价于最小化

$$\min_{\theta}\sum_{x,y\neq x}p(x)w_{xy}\left(s_{\theta}(x)_{y}-\frac{p(y)}{p(x)}\log s_{\theta}(x)_{y}\right) \tag{23}$$

where we have removed constants not depending on $\theta$. This is minimized when

其中已去掉不依赖 $\theta$ 的常数。该式在满足下式时取最小

$$s_{\theta}(x)_{y}-\frac{p(y)}{p(x)}\log s_{\theta}(x)_{y} \tag{24}$$

is minimized for all $x,y$. Taking a derivative with respect to $s$ and setting to $0$, we see that this occurs when $s_{\theta}(x)_{y}=\frac{p(y)}{p(x)}$, which can be easily checked to be optimal as the function is convex as a function of $s$. One can check that the loss is $0$ at the minimum. ∎

对所有 $x,y$ 取最小。对 $s$ 求导并令其为零，得到 $1-\frac{p(y)/p(x)}{s}=0$，因而 $s_{\theta^{*}}(x)_{y}=\frac{p(y)}{p(x)}$。代入后损失恰为 $0$（因 $K$ 项抵消）。

Proof of Prop 3.3.

The trick is the categorical equivalent of the divergence theorem. In particular, we have

命题 3.3 的证明。技巧是散度定理的范畴等价物：

$$\displaystyle\mathbb{E}_{x\sim p}\sum_{y\neq x}\frac{p(y)}{p(x)}f(x,y) \\ \displaystyle=\sum_{x,y:x\neq y}\frac{p(y)}{p(x)}p(x)f(x,y) \\ \displaystyle=\sum_{x,y:x\neq y}p(y)f(x,y) \\ \displaystyle=\mathbb{E}_{y\sim p}\sum_{x\neq y}f(x,y) \\ \displaystyle=\mathbb{E}_{x\sim p}\sum_{y\neq x}f(y,x)$$