Block Diffusion: Interpolating Between Autoregressive and Diffusion Language Models
Authors: Marianne Arriola
Aaron Gokaslan
Justin T Chiu
Zhihan Yang
Zhixuan Qi
Jiaqi Han
Subham Sekhar Sahoo
Volodymyr Kuleshov
Venue: ICLR 2025 Oral (2025)
Keywords: Diffusion Models
Text Diffusion
Generative Models
Primary area: generative models

Abstract: Diffusion language models offer unique benefits over autoregressive models due to their potential for parallelized generation and controllability, yet they lag in likelihood modeling and are limited to fixed-length generation. In this work, we introduce a class of block diffusion language models that interpolate between discrete denoising diffusion and autoregressive models. Block diffusion overcomes key limitations of both approaches by supporting flexible-length generation and improving inference efficiency with KV caching and parallel token sampling. We propose a recipe for building effective block diffusion models that includes an efficient training algorithm, estimators of gradient variance, and data-driven noise schedules to minimize the variance. Block diffusion sets a new state-of-the-art performance among diffusion models on language modeling benchmarks and enables generation of arbitrary-length sequences. We provide the code, along with the model weights and blog post on the project page: https://m-arriola.com/bd3lms/

Published as a conference paper at ICLR 2025
BLOCK DIFFUSION: INTERPOLATING BETWEEN AU- TOREGRESSIVE AND DIFFUSION LANGUAGE MODELS
Marianne Arriola
Aaron Kerem Gokaslan
Justin T. Chiu
Zhihan Yang!
Zhixuan Qi
Jiaqi Han
Subham Sekhar Sahoo
Volodymyr Kuleshov
ABSTRACT
Diffusion language models offer unique benefits over autoregressive models due to their potential for parallelized generation and controllability, yet they lag in likelihood modeling and are limited to fixed-length generation. In this work, we introduce class of block diffusion language models that interpolate between discrete denoising diffusion and autoregressive models. Block diffusion overcomes key limitations of both approaches by supporting flexible-length generation and improving inference efficiency with KV caching and parallel token sampling. We propose recipe for building effective block diffusion models that includes efficient training algorithm, estimators of gradient variance, and data-driven noise schedules to minimize the variance. Block diffusion sets new state-of-the-an performance among diffusion models on language modeling benchmarks and enables generation of arbitrary-length sequences. We provide the code', along with the model weights and blog post on the project page:
https://mm-arroon http://marriolaa.oommdll/ii
INTRODUCTION
Diffusion models are widely used to generate images (Ho et al., 2020; Dhariwal & Nichol, 2021; Sahoo al., 2024b) and videos (Ho al., 2022; Gupta al., 2023), and are becoming increasingly effective generating discrete data such as text (Lou et al., 2024; Sahoo et al., 2024a) biological sequences (Avdeyev et al., 2023; Goel et al., 2024). Compared to autoregressive models, diffusion models have the potential accelerate generation and improve the controllability of model outputs (Schiff et al., 2024; Nisonoff et al., 2024; Li et al., 2024; Sahoo et al., 2024c).
Discrete diffusion models currently face at least three limitations. First, in applications such as chat systems, models must generate output sequences of arbitrary length (e.g., a response to a user's s question). However, most recent diffusion architectures only generate fixed-length vectors (Austin et al., 2021; Lou et al., 2024). Second, discrete diffusion uses bidirectional context during generation and therefore cannot reuse previous computations with KV caching, which makes inference less efficient (Israel et al., 2025). Third, the quality of discrete diffusion models, as measured by standard metrics such as perplexity, lags behind autoregressive approaches and further limits their applicability (Gulrajani & Hashimoto, 2024; Sahoo et al., 2024a).
This paper makes progress towards addressing these limitations by introducing Block Discrete Denoising Diffusion Language Models (BD3-LMs), which interpolate between discrete diffusion and autoregressive models. Specifically, block diffusion models (also known as cemi-autoregressive models) define an autoregressive probability distribution over blocks of discrete random variables (Si et al., 2022; 2023); the conditional probability block given previous blocks is specified by discrete denoising diffusion model (Austin et al., 2021; Sahoo et al., 2024a).
Developing effective BD3-LMs involves two challenges. First, efficiently computing the training objective for block diffusion model is not possible using one standard forward pass of neural
'Correspondence Maainae Arriola: marriola@cs www.ello.....o..ooo.............
'Comell Tech, NY, USA. Stanford University, CA, USA. 1 Cohere, NY, USA.
'Code: https//ghhhh..ommkllleeeeooppppp

---

Published as a conference paper at ICLR 2025
Autoregression:
/ High quality
Arbitrary-lentth
caching
X Not Parallelizable
Generation steps
There categories
average
There are three categories of the average rate There are three catagories of the average rate of...
Diffusion:
X Lower quality
X Fixed-length
X No KV caching
Parallelizable
reusability
continue
Repeal reusability cuts
continue
Repeal reusability cuts prove will continue to reduce the
Block Diffusion (Ours):
/ High quality
Arbitrary-length
caching
Parallelizable
Dn September 17, wo be
On September 17, 2016, we will be giving the release
September 17, 2016,
giving beta-release
server
testing
Block diffusion sequentially generates blocks of tokens by performing diffusion within each block and conditioning on previous blocks. By combining strength from autoregressive and diffusion models, block diffusion overcomes the limitations both approaches by supporting variable-length. higher-quality generation and improving inference efficiency with KV caching and parallel sampling.
Figure I:
network and requires developing specialized algorithms. Second, training is hampered by the high variance of the gradients of the diffusion objective, causing BD3-LMs to under-perform autoregression with a block size of one (when both models should be equivalent). We derive estimators of gradient variance, and demonstrate that it key contributor to the gap in perplexity between autoregression and diffusion. We then propose custom noise processes that minimize gradient variance and make progress towards closing the perplexity gap.
We evaluate BD3-LMs on language modeling benchmarks, and demonstrate that they able to generate sequences of arbitrary length, including lengths that exceed their training context. In addition, BD3-LMs achieve new state-of-the-an perplexities among discrete diffusion models. Compared to alternative semi-autee sum--autoreeressive formulations that perform Gaussian diffusion over embeddings (Han al., 2022; 2023), our discrete approach features tractable likelihood estimates and yields samples with improved generative perplexity using an order of magnitude fewer generation steps. In summary, our work makes the following contributions:
We introduce block discrete diffusion language models, which are autoregressive over blocks of tokens; conditionals over each block are based on discrete diffusion. Unlike prior diffusion models, block diffusion supports variable-length generation and KV caching.
We introduce custom training algorithms for block diffusion models that enable efficiently leveraging the entire batch of tokens provided to the model.
We identify gradient variance as limiting factor of the performance of diffusion models, and we propose custom data-driven noise schedules that reduce gradient variance.
Our results establish a new state-of-the-ar perplexity for discrete diffusion and make progress toward closing the gap to autoregressive models.
2 BACKGROUND: LANGUAGE MODELING PARADIGMS
Notation We consider scalar discrete random variables with V categories as 'one-hot' column vectors in the space V {x 1) Σ, 1} C V for the simplex AV, Let the V-th category denote special [MASK] token, where E is its one-hot vector. We define x1=2 sequence L tokens, where x' E V for all tokens E (I....,L), and use 4 to denote the set of all such sequences. Throughout the work, we simplify notation and refer to the token sequence as x and an individual token as x'. Finally, let Cat(::p) be a categorical distribution with probability p E A..
2

---

Published as a conference paper at ICLR 2025
2.1 AUTOREGRESSIVE MODELS
Consider a sequence of L tokens x gressive (AR) models define factorized distribution of the form
x-] _x'...,,xx drawn from the data distribution ((x). Autore-
log Σ log po (x x x²)
(I)
where cach (x
xx) is parameterized directly with neural network. As a result, AR models may be trained efficiently via next token prediction. However, AR models take steps to generate tokens due the sequential dependencies.
2.2 DISCRETE DENOISING DIFFUSION PROBABILISTIC MODELS
Diffusion models fit model pe (x) to reverse forward corruption process q (Sohl-Dickstee et al., 2015; Ho et al., 2020; Sahoo et al., 2024b). This process starts with clean data x and defines latent variables x, x x fort E 00 1J. which represent progressively noisier versions of x. Given discretization into 7 steps, we define s(j) = (j 1)/T and ((j) j//T. For brevity, we drop from (()) and s(j) below; in general, 8 denotes the time step preceding L.
The D3PM framework (Austin et al., 2021) defines dently on each token xf: g(x x = Cat(xf: Qxx{) where Q E RVV is the diffusion matrix. The matrix Qt can model various transformations, including masking, random token changes, and related word substitutions.
Markov forward process acting indepen-
An ideal diffusion model pe is the reverse of the process q. The D3PM framework defines pe as
(x xx) = II pe (x x()
Σ
II q(*
X x² )o (xf xx))
(2)
where the denoising base model pa (x
xx) predicts clean token xf given the noisy sequence x,, and the reverse posterior gxx", xf, x) is defined following Austin et al. (2021) Suppl. B.3.
The diffusion model pe is trained using variational inference. Let [L[-] denote the Kullback-Leible divergence. Then, the Negative ELBO (NELBO) is given by (Sohl-Dickstein et al., 2015):
T
[(x: 0) Fyg (x) +
Σ
DKL Dkula(xa0) x(o) x)) (X [()))] + DeL (xx[g(((())) (x)oo))))))))
This formalism extends to continuous time via Markov chain (CTMC) theory and admits score-based generalizations (Song & Ermon, 2019; Lou al., 2024; Sun et al., 2022). Further simplifications (Sahoo et al., 2024a; Shi et al., 2024; Ou et al., 2025) tighten the ELOO and enhance performance.
3 BLOCK DIFFUSION LANGUAGE MODELING
We explore class of Block Discrete Denoising Diffusson Language Models (BD3-LMs) that interpolate between autoregressive and diffusion models by defining an autoregressive distribution blocks of tokens and performing diffusion within each block. We provide block diffusion objective for maximum likelihood estimation and efficient training and sampling algorithms. We show that for block size of one, the diffusion objective suffers from high variance despite being equivalent to the autoregressive likelihood in expectation. We identify high training variance as limitation of diffusion models and propose data-driven noise schedules that reduce the variance of the gradient updates during training.
3.1 BLOCK DIFFUSION DISTRIBUTIONS AND MODEL ARCHITECTURES
We propose to combine the language modeling paradigms Sec. 2 by autoregressively modeling blocks of tokens and performing diffusion within each block. We group tokens in into B blocks of
3

---

Published as a conference paper at ICLR 2025
length L' with B L/LL (we assume that B is an integer). We denote each block x 1) from token at positions (b 1)LL to bL' for blocks E {l...., ,...,,B B} as x" for simplicity. Our likelihood factorizes over blocks
po px) = Σ log (x
x )b,,,
(4)
and each (x xx is modeled using discrete diffusion over a block of T/ tokens. Specifically, we define reverse diffusion process in (2), but restricted to block b:
Σ
((2 x2, xx,x"")ooxx"
(po(x")
xx x0
(5)
We obtain a principled learning objective by applying the NELBO (3) to each term (4) obtain
- -lo Po (x) - (xD(x: 0) = Σ [(x x x),,))
(6)
where each L(x², x x= 8) is an instance of (3) applied to log Px conditioned on x=b we make the dependence on x* explicit in L. We denote the sum of these terms LBD(x; x; 0) (itself a valid NELBO).
xxb). Since the model is
Model Architecture Crucially, we parameterize the B base denoiser models pe xx; xb) using single neural network Xg. The neural network X, outputs not only the probabilities pa (x" x2 x <b)). but also computational artifacts for efficient training. This will enable us to compute the loss LBD (x; 0) in parallel for all B blocks in a memory- transformer (Vaswani et al., 2017) with a block-causal attention mask. The transformer to T. tokens, and tokens in block b attend to tokens in blocks b. When X, trained, x (x. x) yields I.' predictions for denoised tokens in block b based on noised xi and clean <b
manner. Specifically, we parameterize x9 using
is applied
In autoregressive generation, it is normal to cache keys and values for previously generated tokens to avoid recomputing them each step. Similarly, we use K², V denote the keys and values at block b, and we define Xg support these as input and output. The full signature of x. is
Xinitss K¹, vb (x Klb-1 Vl:b-1) == xx",
where xfogis are the predictions for the clean x², and Kb, Vb is the key-value cache in the forward pass of Xg. and K 1: V1:b-1 are keys and values cached on a forward pass of Xg over x <b (hence the inputs <b and K l:b V are equivalent).
3.2 EFFICIENT TRAINING AND SAMPLING ALGORITIMMS
Ideally, we wish to compute the loss LBD (x; 0) in one forward pass of Xg. However, observe that denoising x requires forward pass on this noisy input, while denoising the next blocks requires running Xg on the clean version x". Thus every block has go through the model at least twice.
Training Based on this observation, we propose a training algorithm with these minimal computa- tional requirements (Alg. 1). Specifically, we precompute keys and values K 1:8 VI: for the full sequence x in first forward pass (6) K1: 1:73 Vi.)) +- X² (x). We then compute denoised predictions for all blocks using x (x), K Kl:b-1 V1:b-)). Each token passes through Xg twice.
Vectorized Training Naively, we would compute the logits by applying x5 (xc k1:h-1 V ) in loop B times. We propose vectorized implementation that computes LBD(x: 0) in one forward pass on the concatenation Xasisy @ of clean data x with noisy data Xpoisy = x @ 2 to by applying noise level to to each block x We design an attention mask for Xaoisy t x such that noisy tokens attend to other noisy tokens in their block and to all clean tokens in preceding blocks (see Suppl. B.6). Our method keeps the overhead of training BD3-LMs tractable and combines with pretraining further reduce costs.
l:h-1
B obtained
4

---

Published as a conference paper at ICLR 2025
Sampling We sample one block at time, conditioned on previously sampled blocks (Alg 2). We may use any sampling procedure SAMPLE(X). Kl:h1 vlbl) to sample from the conditional distribution pe (x" x x²*), where the context conditioning is generated using cross cross-attention with pre-computed keys and values kl:b-1, Vl.b-1 Similar to AR models, caching the keys and values saves computation instead of recalculating them when sampling a new block.
Notably, block diffusion decoding algorithm enables to sample sequences of arbitrary length, whereas diffusion models are restricted to fixed-length generation. Further, our sampler admits parallel generation within each block, whereas AR samplers are constrained to generate token-by-token.
Algorithm 1 Block Diffusion Training
Algorithm 2 Block Diffusion Sampling
Input: datapoint x, # of blocks B, forward noise process qe (-1x), model X8, loss LBD repeat
Input: # blocks B, model X6, diffusion sam- pling algorithm SAMPLE
K, V + 0
D output & KV cache
Sample 1,,.... ......,,, LB ~ U(0, 1]
vb E [1, ...., B) %/+ 4to (1xx))
for b
B do
x² <- SAMPLE(X K K1:b1 Vl.b1)
9. K VI. xx(x)
KV cache
0, K* V + xx(x²)
4b: logins 0, 0 + xx(x),
, K klbb11 V1:b-1
x + x l:b-1 1 x
Let Xlogi xigi @ logit
( V) < (K (Kidb1g + Kb, Vid-1 @ Vo)
Take gradient step on V LADD Xtogit; 0)
end for return x
until converged
4
UNDERSTANDING LIKELIHOOD GAPS BETWEEN DIFFUSION & AR MODELS
4.1 MASKED BD3-LMS
The most effective diffusion language models leverage a masking noise process (Austin al., 2021; Lou et al., 2024; Sahoo et al., 2024a), where tokens are gradually replaced with special mask token. Here, we introduce masked BD3-LMs, a special class of block diffusion models based on the masked diffusion language modeling framework (Sahoo et al., 2024a; Shi et al., 2024; Ou et al., 2025).
(1 - ar ) for tokens & E (1,.... .....,,)) f.} where is one-hot encoding of the mask token, and
More formally, we adopt a per-token noise process qxx{(x²) = Cat(xf;
[0, 1] is
strictly decreasing function in t, with ag and a = O. We employ the linear schedule where the probability of masking token at time t is 1 a₁. We adopt the simplified objective from Sahoo et al. (2024a); Shi et al. (2024); Ou et al. (2025) (the full derivation provided in Suppl. B.3):
B
of log Po (x (x X0)
- loog S (XD(x; 0) = Σ
R Be
BB 1
(8)
b=1
where of is the instantaneous rate of change of a under the continuous-time extension of (3) that takes T + co. The NELBO is tight for L' = but becomes looser approximation of the true negative likelihodo for L' + L (see Suppl. B.5).
4.2 CASE STUDY: SINGLE TOKEN GENERATION
Our block diffusson parameterization (8) is equivalent expec- tation to the autoregressive NLL. (1) in the limiting case where T' = (see Suppl. B.4). Surprisingly, we find a two point perplexity gap between our block diffusion model for L' = and AR when training both models on the LMIB dataset.
Table 1: Test perplexities for single- token generation (PPL; 4) across 16B tokens on LM1B.
PPL (L)
Although the objectives are equivalent in expectation, show that the remaining perplexity gap is a result of high training variance. Whereas AR is trained using the cross-entropy of L tokens, our block diffusion model for L' only computes the entss-entropy for masked tokens xf m Aε (1,...
AR
22.88
+ random batch size
24.37
BD3-LM L' = tuned schedule
< 25.56
22.88
5

---

Published as a conference paper at ICLR 2025
Train Negative Log-Likelihood (NLL) for Single Token Generation on LM1B
Model
BD3-LM (NELBO) BD3-LM (Tuned schedule) AR AR (random batch size)
4
3.6
3.4
3
50k
100k
150k
200k 250k
Train steps
Figure 2: Train NLLs for modeling the per-token likelihood on LMIB. Models are trained on 16B tokens. Training under the discrete diffusion NELBO, where half of the tokens in batch are masked on average, has similar training variance to an AR model with a random batch size.
so that 1
m m|xx) = 0.5. Thus, training on the diffusion objective involves estimating loss gradients with 2x fewer tokens and is responsible for higher training variance compared to AR.
To close the likelihood gap, we train a BD3-LM for L' = 1 by designing the forward process to fully mask tokens, i.c. q(x; m|x²) 1. Under this schedule, the diffusion objective becomes equivalent to the AR objective (Suppl. B.4). In Table 1, we show that training under the block diffusion objective yields the same perplexity AR training. Empirically,
that this reduces the variance of the training loss in Figure 2. We verify that tuning the noise schedule reduces the variance of the objective by measuring Varx,; [x;D(x; 0)] after training on 328M tokens: while training on the NELBO results in variance of 1.52, training under full masking reduces the variance to 0.11.
4.3 DIFFUSION GAP FROM HIGH VARIANCE TRAINING
Next, formally describe the issue of gradient variance in training diffusion models. Given our empirical observations for single-token generation, we propose an estimator for gradient variance that we use minimize the variance of diffusion model training for 2 While the NELBO is invariant to the choice of noise schedule (Suppl. B.3), this invariance does not hold for our Monte Carlo estimator of the loss used during training. As result, the variance the estimator and its gradients are dependent the schedule. First, express the estimator of the NELBO with a batch
size K. We denote a batch of sequences as = [x(11) x*)),... ,..., x (K)], with each (k) iid
~ g(x). We obtain the batch NELBO estimator below, where t(k:, b) is sampled in sequence and block
K B
= (x; [=)(X:0):=((x00
log pe (x()))b)
(N).b (((k)))
x x0)))0)
(9)
K
(l(k.b)
The variance of the gradient estimator over M batches for each batch n Vm E (1....,.} is:
M
M
2
1
Varx, [Vl((:
Val(X"
Vol(Xm
(10)
M
M m=1
Low- LOw- VARIANCE NOISE SCHEDULES FOR BD3-LMS
5.1 INTUITION: AVOID EXTREME MASK RATES
We aim to identify schedules that minimize the variance of the gradient estimator and make training most efficient. In masked setting, want to mask random numbers of tokens, that the model

---

Published as a conference paper at ICLR 2025
learns undo varying levels of noise, which is important during sampling. However, if mask very few tokens, reconstructing them is easy and does not provide useful learning signal. we mask everything, the optimal reconstruction
the marginals of each token in the data distribution, which easy to learn, and again is not useful. These extreme masking rates lead to poor high-variance gradients: we want to learn how clip them via simple and effective new class of schedules.
5.2 CLIPPED SCHEDULES FOR Low- VARIANCE GRADIENTS
We propose a class of "clipped" noise schedules that sample mask rates 1- at ~ U13, w] for 0 S w I 1. We argue that from the perspective of deriving Monte Carlo gradient estimates, these continuous schedule where the mask probability is approximately before the specified range such that 1 aes = and approximately after the specified range asw A 1 Consequently, of is linear within the range: af Rs 1/(3 w).
schedules are equivalent
5.3 DATA-DRIVEN CLIPPED SCIEDULES ACROSS BLOCK SIZES
As optimal mask rates may differ depending on the block size L', we adaptively learn the schedule during training. While Kingma et al. (2021) perform variance minimization by isolating a variance term using their squared diffusion loss, this strategy is not directly applicable to our variance estimator in Equation 10 since seek to reduce variance across random batches in addition to random ty.
Instead, we optimize parameters 3, to directly minimize training variance. To limit the computa- tional burden of the optimization, use the variance of the estimator of the diffusion ELBO proxy for the gradient estimator to optimize 3.w: minz,, Varx,, [[( 8, 3, [.w]]. We perform a grid search regular intervals during training find the optimal B, w (experimental details in Sec. 6).
In Table 2, we show that variance of the diffusion NELBO is correlated with test perplexity. Under a range of "clipped"" noise rate distributions, find that there exists unique distribution for each block size L' E {4, 16, 128} that minimizes both the variance of the NELBO and the test perplexity.
Table 2: Perplexities (PPLs; 4) and variances of the NELBO Varx, [LDD (X; (Var. NELBO; J). Models are trained on LMIB using a linear schedule for 65B tokens, then finetuned for 10B tokens.
O0, .5]
[[33..8)
U[.5, 1]
24 1]
L'
PPL
Var. NELBO
PPL
Var. NELBO
PPL
Var. NELBO
PPL
Var. NELBO
128
31.72
1.03
31.78
1.35
31.92
1.83
31.78
3.80
16
31.27
7.90
31.19
3.62
31.29
3.63
31.33
7.39
29.23
32.68
29.37
10.39
29.16
8.28
29.23
23.65
EXPERIMENTS
Table 3: Test perplexities (PPL; J) mod- els trained for 65B tokens on LMIB. Best diffusion value is bolded.
We evaluate BD3-LMs across standard language modeling benchmarks and demonstrate their ability to generate arbitrary-length sequences uncondition- ally. We pre-train base BD3-LM using the maxi- mum block size L' = L for 850K gradient steps and fine-tune under varying L' for 150K gradient steps on the One Billion Words dataset (LM1B; Chelba (2014)) and OpenWebTee (OWT; Gokaslan et al. (2019)). Details training and inference are provided in Suppl C.
PPL (4)
Autoregressive
Transformer-X Base (Dai et al., 2019)
23.5
Transformer (Sahoo et al., 2024a)
22.83
Diffusion
D3PM (absorb) (Austin el al., 2021)
< 82.34
SEDD (Lou et al., 2024) MDLM (Sahoo et al., 2024a)
32.68
31.78
To reduce the variance of training on the diffusion NELBO, we adaptively learn the range of masking rates by optimizing parameters 3, w described in Section 5.3. In practice, we do so using a grid search during every validation epoch (after ~5K gradient
Block diffusion (Ours)
BD3-LMs L/ 16
30.60
8
< 29.83
L' =
< 28.23
7

---

Published as a conference paper at ICLR 2025
updates) to identify w, ming,w Varx.1 6, B,)).. During evaluation, report likelihood under uniformly sampled mask rates (8) as in Austin et al. (2021); Sahoo et al. (2024a).
6.1 LIKELIHOOD EVALUATION
On LMIB, BD3-LMs outperform all prior diffusion meth- ods in Table 3. Compared to MDLM (Sahoo et al., 2024a), BD3-LMS achieve up to 13% improvement in perplexity. We observe similar trend on OpenWebText in Table 4.
Table 4: Test perplexities (PPL; 4) on OWT for models trained for 524B to- kens. Best diffusion value bolded.
We also evaluate the ability of BD3-LMs to generalize to unseen datasets in zero-shot setting, following the benchmark from Radford et al. (2019). We evaluate the likelihood of models trained with OWT on datasets Penn Tree Bank (PTB; (Marcus et al., 1993)), Wikitext (Merity al., 2016), LMIB, Lambada (Paperno et al., 2016), AG News (Zhang et al., 2015), and Scientific Papers (Pubmed and Arxiv subsets; (Cohan et al., 2018)). In Table BD3- LM achieves the best zero-shot perpiexity on Pubmed, surpassing AR, and the best perplexity among diffusion models on Wikitext, LMIB, and AG News.
PPL (L)
AR (Sahoo et al., 2024a)
17.54
SEDD (Lou et al., 2024)
S 24.10
MDLM (Sahoo et al., 2024a)
$ 22.98
BD3-LMs L' L' 8
< 22,27
< 21.68
L' 4
X 20.73
Table 5: Zero-shot validation perplexities ()) of models trained for 524B tokens on OWT. All perplexities for diffusion models are upper bounds.
PTB
Wikitext
LMIB
Lambada
AG News
Pubmed
Arxiv
AR
81.07
25.32
51.14
52.13
52.11
48.59
41.22
SEDD
96.33
35.98
68.14
48.93
67.82
45.39
40.03
MDLM
90.96
33.22
64.94
48.29
62.78
43.13
37.89
BD3-LM L' =
96.81
31.31
60.88
50.03
61.67
42.52
39.20
6.2 SAMPLE QUALITY AND VARIABLE-LENGTI SEQUENCE GENERATION
One key drawback of many existing diffusion language mod- els (e.g.- Austin et al. (2021); Lou et al. (2024)) that they cannot generate full-length sequences that are longer than the length of the output context chosen at training time. The OWT dataset is useful for examining this limitation, it contains many documents that are longer than the training context length of 1024 tokens.
Table 6: Generation length statistics from sampling 500 documents from models trained on OWT.
Median # tokens # tokens
Max
OWT train set AR
717 4008
131K 131K
We record generation length statistics of 500 variable-length samples in Table 6. We continue sampling tokens until an end-of-sequence token [EOS] is generated or sample qual- ity significantly degrades (as measured by sample entropy). BD3-LMs generate sequences up to R= 10x longer than those of SEDD (Lou al., 2024), which is restricted to the training context size.
SEDD BD3-LM L' 16
1021
1024
798
9982
We also examine the sample quality of BD3-LMs through quantitative and qualitative analyses. In Table we generate sequences of lengths L = 1024, 2048 and measure their generative perplexity under GPT2-Large To sample I, 2048 tokens from MDLM, we use their block-wise decoding technique (which does not feature block diffusion training as in BD3-L.Ms).
We also compare to SSD-LM (Han et al., 2022), an alternative block diffusion formulation. Unlike our discrete diffusion framework, SSD-LM uses Gaussian diffusion and does not support likelihood estimation. Further, BD3-LM adopts an efficient sampler from masked diffusion, where the number of generation steps (NFEs) is upper-bounded by L since tokens are never remasked (Sahoo et al., 2024a; Ou et al., 2025). For SSD-LM, compare sample quality using T = 1K diffusion steps per block, matching their experimental setting (yielding 240K NFEs), and T 25 where NFEs are comparable across methods.
8

---

Published as a conference paper at ICLR 2025
Table Generative perplexity (Gen. PPL: and number of function evaluations (NFEs; 4) 300 samples of lengths L 1024, 2048. All models are trained on OWT. AR, SEDD, MDLM, BD3-LMs use 110M parameters and are trained on 524B tokens, while SSD-LM uses 400M parameters and pre-trained on 122B tokens. Best diffusion value is bolded. We provide further details in Suppl. C.5.
L = 1024
= 2018
Model
Gen. PPL
NFES
Gen. PPL
NFEs
14.1
13.2
2K
Diffusion
SEDD
52.0
IK
MDLM
46.8
1K
41.3
2K
Block Diffusion
SSD-LM L' 25
37.2
40K
35.3
80K
281.3
1K
281.9
2K
BD3-LMs
33.4
31.5
2K
=
30.4
IK
28.2
2K
L' 25.7
IK
23.6
2K
BD3-LMs achieve the best generative perplexities compared previous diffusion methods. Relative to SSD-LM, our discrete approach yields samples with improved generative perplexity using order of magnitude fewer generation steps. We also qualitatively examine samples taken from BD3-LM and baselines (AR, MDLM) trained on the OWT dataset; report samples in Suppl. D. We observe that BD3-LM samples have higher coherence than MDLM samples and approach the quality AR.
6.3 ABLATIONS
We assess the impact of the design choices in our proposed block diffusion recipes, namely 1) selection of the noise schedule and 2) the efficiency improvement of the proposed training algorithm relative to a naive implementation.
SELECTING NOISE SCHEDULES TO REDUCE TRAINING VARIANCE
Compared the linear schedule used in Lou al. (2024); Sahoo et al. (2024a), training under "clipped" noise schedules is the most effective for reducing the training variance which correlates with perplexity. In Table 8, the ideal "clipped" masking rates, which are optimized during training, specific to the block size and further motivate our optimization.
Relative other standard noise schedules (Chang et al., 2022), "clipped" masking achieves the best perfor- mance. As heavier masking is effective for the smaller block size L' = 4, we compare with logarithmic and square root schedules that also encourage heavy mask- ing. As lighter masking is optimal for L' 16, we compare with square and cosine schedules.
Table 8: Effect of the noise schedule on like- lihood estimation. We finetune BD3-LMs on 3B tokens from LMIB and evaluate on a linear schedule. For clipped schedules, compare optimal clipping for = 4, 16.
Noise schedule
PPL
Var. NELBO
I'=d 4 Clipped
EFFICIRNCY OF TRAINING ALGORITHM
L((0.45, 0.95
29.21
6.24
In the BD3-LM training algorithm (Sec. 3.2), com- pute Xiegit using two options. We may perform two for- ward passes through the network (precomputing keys then computing
24(0.3,0.8 0.8]
29.38
10.33
Linear 24(0,
30.18
23.45
Logarithmic
30.36
23.53
Square root
31.41
26.43
and values for the full sequence denoised predictions), or combine these passes by con- catenating the two inputs into the same attention kernel.
L' 16 Clipped
U/0.45, 0.95
31.42
3.60
We find that a single forward pass more efficient as reduce memory bandwidth bottlenecks by leverag- ing efficient attention kernels (Dao et al., 2022; Dong al., 2024), Suppl. B.7. Instead of paying the cost
V/0.3, 0.8)
31.12
3.58
Linear u100
31.72
7.62
Square
31.43
13.03
Cosine
31.41
13.00

---

Published as a conference paper at ICLR 2025
of two passes through the network, we only pay the cost of a more expensive attention operation. Our vectorized approach has 20-25% speed-up during training relative to performing two forward passes.
DISCUSSION AND PRIOR WORK
Comparison to D3PM Block diffusion builds off D3PM (Austin et al., 2021) and applies it to each autoregressive conditional. We improve over D3PM in three ways: (1) we extend D3PM beyond fixed sequence lengths; (2) we study the perplexity gap of D3PM and AR models, identify gradient variance as a contributor, and design pariance-minimine D3PM models. Our work applies extensions of D3PM (He et al., 2022; Lou al., 2024) including ones in continuous time (Campbell et al., 2022; Sun et al., 2022).
schedules; (3) we improve over the perplexity of
Comparison to MDLM BD3-LMs further make use of the perplexity-enhancing improvements in MDLM (Sahoo et al., 2024a; Shi et al., 2024; Ou et al., 2025). We also build upon MDLM: (1) while Sahoo et al. (2024a) point out that their NELBO is invariant to the noise schedule, we show that the noise schedule has significant effect on gradient variance; (2) we push the -fate-of-the-aee in perplexity beyond MDLM. Note that our perplexity improvements stem not only from block diffusion, but also from optimized schedules, and could enhance standard MDLM and D3PM models.
Comparison to Gaussian Diffusion Alternatively, one may perform diffusion over continuous embeddings of discrete tokens (Li et al., 2022; Dieleman et al., 2022; Chen et al., 2022). This allows using algorithms for continuous data (Song et al., 2020: Ho Salimans, 2022), but yields worse perplexity (Graves et al., 2023; Gulrajani & Hashimoto, 2024).
Comparison to Semi-Autoregressivv Diffusion Han et al. (2022; 2023) introduced a block formu- lation of Gaussian diffusion. BD3-LMs instead extend Austin et al. (2021), and feature: (1) tractable likelihood estimates for principled evaluation: (2) faster generation, as our number of model calls is bounded by the number of generated tokens, while SSD-LM performs orders of magnitude more calls; (3) improved sample quality. AR IR-Diffusion (Wu et al., 2023) extends SSD-LM with a left-to-right noise schedule; Chen al. (2025); Ye et al. (2024) apply to decision traces and videos; Hao et al. (2024); Kong et al. (2025) extend to latent reasoning. PARD (Zhao et al., 2024) applics discrete block diffusion to graphs. In contrast, we (I) interpolate between AR/diffusson performance; (2) support KV caching; (3) perform attention within noised blocks, whereas PARD injects new empty blocks.
Autoregressive diffusion models (Hoogeboom al., 2021b;a) extend any-order AR models (AO- ARMs; Uria et al. (2014)) to support parallel sampling. Zheng et al. (2024) prove equivalence between MDLM and AO-ARM training. Further extensions of ARMs that compete with diffusion include iterative editing (Gu et al., 2019), parallel and speculative decoding (Gu et al., 2017; Santilli al., 2023; Cai et al., 2024; Gloeckle et al., 2024), consistency training (Kou et al., 2024), guidance (Sanchez et al., 2023), and cross-modal extensions (Liu et al., 2023; Tian et al., 2025).
Limitations Training BD3-LMs is more expensive than regular diffusion training. We propose vectorized algorithm that keeps training speed within <2x of diffusion training speed; in our experi- ments, we also pre-train with standard diffusion loss to further reduce the speed gap. Additionally, BD3-LMs generate blocks sequentially, and hence may face the same speed and controllability con- straints as AR especially when blocks are small. Their optimal block size task specific (e.g., larger for greater control). BD3-LMs are subject to inherent limitations of generative models, including hallucinations (Achiam et al., 2023), copyright infringement (Gokaslan al., 2024), controllability (Schiff et al., 2024; Wang et al., 2023) and harmful outputs (Bai et al., 2022).
8 CONCLUSION
This work explores block diffusion and is motivated by two problems with existing discrete diffusion: the need to generate arbitrary-length sequences and the perplexity gap to autoregressive models. We introduce BD3-LMs, which represent a block-wize wise extension of the D3PM framework (Austin et al., 2021), and leverage a specialized training algorithm and custom noise schedules that further improve performance. We observe that in addition to being able to generate long-form documents, these models also improve perplexity, setting new state-of-the-art among discrete diffusion models.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE FUNDING
This work was partially funded by the National Science Foundation under awards DGE-1922551, CAREER awards 2046760 and 2145577, and by the National Institute of Health under award MIRA R35GM151243. Marianne Arriola is supported by NSF Graduate Research Fellowship under award DGE-2139899 and a Hlpper-Dean/Boon
CIS Deans Excellence Fellowship. We thank Databricks MosaicMI. for providing access to computational resources.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint 1rXiv:2303.08744 2023.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17999 2021.
Pavel Avdeyev, Chenlai Shi, Yuhao Tan, Kseniia Dudnyk, and Jian Zhou. Dirichlet diffusion score model for biological sequence generation. In International Conference on Machine Learning, pp. 1276-1301, PMLR, 2023.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, al. Constitutional ai: Harmlessness from ai feedhack. arXiv preprint 2rXiv:22/2.0807) 2022.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple II inference acceleration framework with multiple decoding heads. arXiv preprint arXiv:2401.10774, 2024.
Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 55:28266--22799 2022.
Huiwen Chang, Han Zhang, Lu Jiang, Ce Liu, and William Freeman. Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 1 11315-11 1325, 2022.
Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One billion word benchmark for measuring progress in statistical language modeling, 2014.
Boyuan Chen, Diego Martí Monsó, Yilun Du, Max Simchowitz, Russ Tedrake, and Vincent Sitzmann. Diffusion forcing: Next-token prediction meets full-sequence diffusion. Advances in Neural Information Processing Systems, 17:24081-224225 2025.
Ting Chen, Ruixiang Zhang, and Geoffrey Hinton. Analog bits: Generating discrete data using diffusion models with self self-conditioning arXiv preprint arXiv:2208 04202, 2022.
Arman Cohan, Franck Dernoncourt, Doo Soon Kim, Trung Bui, Seokhwan Kim, Walter Chang, and Nazli Goharian. A discourse-aware attention model for abstractive summarization of long documents. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), 201 8. URL http:// : / / dxx doi. org/ 10. 18653 1a.////vv/in822/2
doi: 10.18653/v 1/19220997
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint arXiv:1901.02860 2019.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35: 35:16344-16359, 2022.
11

---

Published as a conference paper at ICLR 2025
Prafulla Dhariwal and Alex Nichol. Diffusion models beat gans image synthesis, 2021. URL https: //riiv//////v////////e/a/aaaaaa org/ alss 2tlos/2105 2105.000000 05233.
Sander Dieleman, Laurent Sartran, Anman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H Richemond, Arnau Doucet, Robin Strudel, Chris Dyer, Conor Durkan, et al. Continuous diffusion for categorical data. arXiv preprint wiXi:2221.150033 2022.
Juechu Dong, Boyuan Feng, Driss Guessous, Yanbo Liang, and Horace He. Flex attention: A programming model for generating optimized attention kernels. arXiv preprint arXiv:2412.05496,
2024.
Fabian Gloeckle, Badr Youbi Idrissi, Baptiste Rozière, David Lopez-Paz, and Gabriel Synnaeve. Better & faster large language models via multi-token prediction. arXiv preprint arXiv:2404. 19737, 2024.
Shrey Goel, Vishrut Thoutam, Edgar Mariano Marroquin, Aaron Gokaslan, Arash Firouzbakht, Sophia Vincoff, Volodymyr Kuleshov, Huong T Kratochvil, and Pranam Chatterjee. Memdlm: De novo membrane protein design with masked discrete diffusion protein language models. arXiv preprint 167355, 2024.
Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex. Openwebtext corpus. http: //Skylion007 github....... io Corrp 2019.
Aaron Gokaslan, A Feder Cooper, Jasmine Collins, Landan Seguin, Austin Jacobson, Mihir Patel, Jonathan Frankle, Cory Stephenson, and Volodymyr Kuleshov. Commoncanvas: Open diffusion models trained on creative-commons images. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8250-8260, 2024.
Alex Graves, Rupesh Kumar Srivastava, Timothy Atkinson, and Faustino Gomez. Bayesian flow networks. arXiv preprint arXiv:2308.07037, 2023.
Jiatao Gu, James Bradbury, Caiming Xiong, Victor OK Li, and Richard Socher. Non-autoregressive neural machine translation. arXiv preprint arXiv: 111.22211..2211.... 2017.
Jiatao Gu, Changhan Wang, and Junbo Zhao. Levenshtein transformer. Advances in neural informa- tion processing systems, 32, 2019.
Ishaan Gulrajani and Tatsunori B Hashimoto. Likelihood- diffusion language models. Advances in Neural Information Processing Systems, 36, 2024.
Agrim Gupta, Lijun Yu, Kihyuk Sohn, Xiuye Gu, Meera Hahn, Li Fei-Fei, Irfan Essa, Lu Jiang, and Jose Lezama. Photorealistic video generation with diffusion models, 2023. URL https: //a.xxi.org//bb//..........
06662.
Xiaochuang Han, Sachin Kumar, and Yulia Tsvetkov. Ssd-Im: Semi-autoregressive simplex-based diffusion language model for text generation and modular control. arXiv preprint arXiv:2210.17432. 2022.
Xiaochuang Han, Sachin Kumar, Yulia Tsvetkov, and Marjan Ghazvininejad, David helps goliath: Inference-time collaboration between small specialized and large general diffusion Ims. arXiv preprint arXiv:2305. 2023.
Shibo Hao, Sainbayar Sukhbaatar, DiJia Su, Xian Li, Zhiting Hu, Jason Weston, and Yuandong Tian. Training large language models to reason in continuous latent space. arXiv preprint arXiv:2412.06769 2024.
Zhengfu He. Tianxiang Sun, Kuanning Wang, Xuanjing Huang, and Xipeng Qiu. Diffusion- bert: Improving generative masked language models with diffusion models. arXiv preprint arXiv:2211.15029 2022.
Jonathan Ho and Tim Salimans. Classifier free diffusion guidance. arXiv preprint arXiv:2207.12594 2022.
12

---

Published as a conference paper at ICLR 2025
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840- -168800-6851,, 2020.
Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet. Video diffusion models. arXiv:2204.03455 2022.
Emiel Hoogeboom, Alexey Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. arXiv preprint arXiv:2110002037, 2021a.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 14:12444-22455, 2021b.
Daniel Israel, Aditya Grover, and Guy Van den Broeck. Enabling autoregressive models to fill in masked tokens. arXiv preprint arXiv:2502.06901, 2025.
Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Advances in neural information processing systems, 34:21696-21707, 2021.
Deqian Kong. Minglu Zhao, Dehong Xu, Bo Pang, Shu Wang, Edouardo Honig, Zhangzhang Si. Chuan Li, Jianwen Xie, Sirui Xie, et al. Scalable language models with posterior inference of latent thought vectors. arXiv preprint arXiv:2502.00 5677, 2025.
Siqi Kou, Lanxiang Hu, Zhezhi He, Zhijie Deng, and Hao Zhang. CLLMs: Consistency large language models. In Forty-first International Conference Machine Learning, 2024. URL attps://oee /openrev/ ew net / forum? 1000dd0002uuu
Xiang Li, John Thickstun, Ishaan Guirajani, Percy S Liang, and Tatsunori B Hashimoto. Diffusion-Im improves controllable text generation. Advances in Neural Information Processing Systems, 35: 4328 4343, 2022.
Xiner Li, Yulai Zhao, Chenyu Wang, Gabriele Scalia, Gokcen Eraslan, Surag Nair, Tommaso Biancalani, Shuiwang Ji, Aviv Regev, Sergey Levine, et al. Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding. arXiv preprint arXiv:2408.0822 0885.. 2024.
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. Advances in neural information processing systems, 36:34892-34916, 2023.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion modeling by estimating the ratios of the data distribution. In Forty-first International Conference on Machine Learning, 2024. URL https: cpenreview nnt httt://orumiidd-cicooo
Mitch Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of english: The penn treebank. Computational linguistics, 19(2):313-338 1993.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models, 2016.
Hunter Nisonoff, Junhao Xiong, Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete sate-space diffusion and flow models. arXiv preprint 200.0:24006.0572. 2024.
Jingyang Ou, Shen Nie, Kaiwen Xue, Fengqi Zhu, Jiacheng Sun, Zhenguo Li, and Chongxuan Li. Your absorbing discrete diffusion secretly models the conditional distributions of clean data. In The Thirleenth International Conference on Learning Representations, 2025. URL https: dttps://openreviee net forum? iieeindd=sMMxs sMyXP 8Tanm.
Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernandez. The LAMBADA dataset: Word prediction requiring a broad discourse context. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. Berlin, Germany, August 2016. Association for Computational Linguistics. URL http: : /ww. acl web. org/ antaanathheooo www.tnngtohtnaaoooooooooo 1144.
13

---

Published as a conference paper at ICLR 2025
William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1195-42005 2023.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
Subham Sekhar Sahoo, Marianne Arriola, Aaron Gokaslan, Edgar Mariano Marroquin, Alexander M Rush, Yair Schiff, Justin T Chiu, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL https: opwprevieneeveeeeeeeeeeeeeeeeeee net
-
Subham Sekhar Sahoo, Aaron Gokaslan, Christopher De Sa, and Volodymyr Kuleshov. Diffusion models with learned adaptive noise. The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024b. URL /ttattt:://opeereeeeeeeeee /ttp::://///eeeeieeeeee.
wwtpeeiwwwwwweeeeeeee.ee...eee net / forum? iid- 1oMa 9A 4p8.
Subham Sekhar Sahoo, John Xavier Morris, Aaron Gokaslan, Srijeeta Biswas, Vitaly Shmatikov, and Volodymyr Kuleshov. Zero-order diffusion guidance for inverse problems, 2024c. URL
htttps://pperretee hot.:e.neeee..ooumoooooooooonaa 1d-
net/ www.:/nttt/ourme.eeee
Guillaume Sanchez, Honglu Fan, Alexander Spangher, Elad Levi, Pawan Sasanka Ammanamanchi, and Stella Biderman. Stay on topic with classifier-free guidance. arXiv preprint UrXiv:2306.17800 2023.
Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Riccardo Marin, and Emanuele Rodola. Accelerating transformer inference for translation via parallel decoding. In Anna Rogers, Jordan Boyd-Grabe and Naoaki Okazaki (eds.), Proceedings the sl Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 22336-12355, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 10.186533v1/2023.ccu aclp:////o//......ooooo.gg. long.68... URL ht aalaacclantttt aclanthooooyyyy org. www.:/2....cloonn...oo... 689.
Yair Schiff, Subham Sekhar Sahoo, Hao Phung, Guanghan Wang, Sam Boshar, Hugo Dalla-torre, Bernardo P de Almeida, Alexander Rush, Thomas Pierrot, and Volodymyr Kuleshov. Simple guidance mechanisms for discrete diffusion models. arXiv preprint arXiv:2412. 10193, 2024.
Jiaxin Shi, Kehang Han, Zhe Wang, Amaud Doucet, and Michalis Titsias. Simplified and generalized masked diffusion for discrete data. In The Thirtt-eighth Annual Conference Neural Information Processing Systems, 2024. Uttsttss: httprr/v/////eeveeeeeeee eww..w.wwww..................... n forum? d= xcxcs00fftt
Phillip Si, Allan Bishop, and Volodymyr Kuleshow. Autoregressive quantile flows for predictive uncertainty estimation. In International Conference on Learning Representations, 2022.
Phillip Si, Zeyi Chen, Subham Sekhar Sahoo, Yair Schiff, and Volodymyr Kuleshov. Semi- autoregressive energy flows: exploring likelihood training of normalizing flows. In In- ternational Conference on Machine Learning, pp. 31732-31753. PMLR, 2023.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning. pp. 2256 2265.. PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02500 2020.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. arXiv preprint arXiv:2 2021.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous -iim discrete diffusion models. arXiv preprint arXiv:2211.16750 2022.
14

---

Published as a conference paper at ICLR 2025
Keyu Tian, Yi Jiang, Zehuan Yuan, Bingyue Peng. and Liwei Wang. Visual autoregressive modeling: Scalable image generation via sext-scale prediction. Advances in neural information processing systems, 37:84839-84886 2025.
Benigno Uria, lain Murray, and Hugo Larochelle. deep and tractable density estimator. In International Conference on Machine Learning, pp. 467-475. PMLR, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Yingheng Wang, Yair Schiff, Aaron Gokaslan, Weishen Pan, Fei Wang, Christopher De Sa, and Volodymyr Kuleshov. InfoDiffusion: Representation learning using information maximizing diffusion models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 36336-36354. PMLR, 23-29 Jul 2023. URL https: : httpp/ppppccnn...ceecpp httpe/enn.n............eeeeeeeee
press/ /vccessss/222/ wtt.vv2222///// w/wg///gn222///aa//// 3ah html.
Tong Wu, Zhihao Fan, Xiao Liu, Hai-Tao Zheng, Yeyun Gong, yelong shen, Jian Jiao, Juntao Li, zhongyu wei, Jian Guo, Nan Duan, and Weizhu Chen. AR-diffusion: Auto-regressive diffusion model for text generation. In Thirly-seventh Conference on Neural Information Processing Systems, 2023. URL pettpss:/opeereeeeee
Jiacheng Ye, Shansan Gong, Liheng Chen, Lin Zheng. Jiahui Gao, Han Shi, Chuan Wu, Xin Jiang, Zhenguo Li, Wei Bi, al. Diffusion of thoughts: Chain-of-thought reasoning in diffusion language models. arXiv preprint arXiv:2402.07754 2024.
Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In NIPS, 2015.
Lingxiao Zhao, Xueying Ding, and Leman Akoglu. Pard: Permutation invariant autoregressive
Cermutation-invariantt diffusion for graph generation. In The Thirty-eighth Anmual Conference Neural Information Processing Systems, 2024. URL https: / http:///peeeeeeeeeeeeeeeeeee .net/
Kaiwen Zheng, Yongxin Chen, Hanzi Mao, Ming-Yo Yu Liu, Jun Zhu, and Qinsheng Zhang. Masked diffusion models are secretly time-agnostic masked models and exploit inaccurate categorical sampling. arXiv preprint arXiv:2409.02908, 2024.
15

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
2
Background: Language Modeling Paradigms
2.1
Autoregressive Models
2.2
Discrete Denoising Diffusion Probabilistic Models
3
Block Diffusion Language Modeling
3.1
Block Diffusion Distributions and Model Architectures
3.2 Efficient Training and Sampling Algorithms
4
Understanding Likelihood Gaps Between Diffusion & AR Models
4.1
Masked BD3-LMs
4.2
Case Study: Single Token Generation
4.3
Diffusion Gap from High Variance Training
5
Low-Variance Noise Schedules for BD3-LMs
5.1
Intuition: Avoid Extreme Mask Rates
5.2
Clipped Schedules for Low-Variance Gradients
5.3
Data-Driven Clipped Schedules Across Block Sizes
Experiments
6.1
Likelihood Evaluation
8
6.2
Sample Quality and Variable-Length Sequence Generation
6.3
Ablations
7 Discussion and Prior Work
10
Conclusion
10
Block Diffusion NELBO
17
B Masked BD3-LMs
17
B.1 Forward Process..
18
B.2 Reverse Process
18
B.3 Simplified NELBO for Masked Diffusion Processes
18
B.4
Recovering the NLL from the NELBO for Single Token Generation
19
B.5 Tightness of the NELBO
20
B.6
Specialized Attention Masks
20
B.7
Optimized Attention Kernel with FlexAttention
C Experimental Details
24
16

---

Published as a conference paper at ICLR 2025
C.1 Datasets
24
C.2 Architecture
24
C.3 Training
24
C,4 Likelihood Evaluation
24
C.5 Inference
25
Samples
26
A BLOCK DIFFUSION NELBO
Below, provide the Negative ELBO (NELBO) for the block diffusson parameterization. Recall that the sequence x2:2 = x² .x!....,x" x² is factorized over B blocks, which we refer to as x for simplicity, drawn from the data distribution g(x). Specifically, we will factorize the likelihood over B blocks of length T.', then perform diffusion in each block over T discretization steps. Let DRI [-] to denote the
Kullback-Leinn divergence, f, s be shorthand for t(i) = i/T and s(i) (i - 1)/T Vi e [1, We derive the NELBO as follows:
B log po p (x
log pa (x)
B
po (x 2
log F.g
(xxb (xx(()eer))) (xb)
1=1
Pe (xxx(()) 1x <b I pa po(x (x e(1) x((0) x(0))x=0) x=6
log Ray
I (x(% (xb (()))
B
Ey log po (x" bxb a x {b))
+ E Be #.... T-l, B TDKL (g(x)) x x²) x²))) |I po (x x()))
Laithan
+ DEL (x(x)=1xx)) ll pe pe(x (x(
(1I)
Cyii
B MASKED BD3-LMS
We explore specific class of block diffusion models that builds upon the masked diffusion language modeling framework. In particular, we focus on masking diffusion processes introduced by Austin et al. (2021) and derive simplified NELBO under this framework as proposed by Sahoo al. (2024a); Shi et al. (2024); Ou al. (2025).
First, define the diffusion matrix Q, for states {1...., VJ. Consider the noise schedule function a, E [0, which is a strictly decreasing function in t satisfying ag = 1 and a = 0. Denote the mask index
V. The diffusion matrix is defined by Austin et al. (2021) as:
if j m
1Qoly =
at
if = j + m
(12)
1
if = m. á + m
17

---

Published as a conference paper at ICLR 2025
The diffusion matrix for the forward marginal Oris is:
if = j = m
1211dk =
atls
if i = j # m
(13)
1
0///s
jf m, i
where 0tls at/Ox.
B. FORWARD PROCESS
Under the D3PM framework (Austin et al., 2021), the forward noise process applied independently for each token f E (1,... L.} defined using diffusion matrices Qt E RVVV as
(xx[xx)) = Cat (xf: 0,x²), with 22(0 = Q11))(1)) 210)
(14)
B.2 REVERSE PROCESS
Let Qtis denote the diffusion matrix for the forward marginal. We obtain the reverse posterior q(x] x x²) using the diffusion matrices:
(xx1xxxxx) q(x/1x) x (xx((())
x 21px2 ② Q.xx'
Cat
(15)
q(x{[xt)
Ox,xx* Tx
where @ denotes the Hadmard product between two vectors.
B.3 SIMPLIFIED NELBO FOR MASKED DIFFUSION PROCESSES
Following Sahoo et al. (2024a); Shi et al. (2024); Ou et al. (2025), we simplify the NELBO in the case of masked diffusion processes. Below, we provide the outline of the NELBO derivation; the full derivation in Sahoo et al. (2024a); Shi et al. (2024); Ou et al. (2025).
We will first focus simplifying the diffusion loss term Laimussin in Eq. 11. We employ the SUBS- parameterization proposed in Sahoo et al. (2024b) which simplifies the denoising model pa for masked diffusion. In particular, we enforce the following constraints on the design of py by leveraging the fact that there only exists two possible states in the diffusion process x E {x" m) ve E (1...., L).
1. Zero Masking Probabilities. We set (x = m|x() = (as the clean sequence x doesn't contain masks).
2. Carry-Over Unmasking. The true posterior for the case where x + m is g(x; = x/1xf o m) 1 (if token unmasked in the reverse process, it is never remasked). Thus, we simplify the denoising model by setting px( = xf1 x # m) 1.
As a result, we will only approximate the posterior px(x = x x m). Let hh denote a token in the ê-th position in block & E (1...., B}. The diffusion loss term becomes:
Ldittusion
ETETT [DKL [g(x]|>], x²) ) (x²) x x [b]]]
Σ E
Σ DKL
1x xxx")) (x }
Dxr. is simply the discrete-time diffusion loss for the block by hence, from Sahoo et al. (2024a) (Suppl. B.I), we get:
E,E.T
a4 as az
log
x xb
04 0g log (x xg. xxb)))
R2 T
(16)
1 at
1=1
18

---

Published as a conference paper at ICLR 2025
Lastly, obtain tighter approximation of the likelihood by taking the diffusion steps T (Sahoo et al., 2024a), for which T(a ag)) = a;:
B
ae log x xxh)
Liiffusion
R Σ
(0,1
(17)
11-a a4
For the continuous time case, Sahoo et al. (2024a) (Suppl. A.2.4) show the reconstruction loss reduces
to as x(()) ~ -im Cat
(xx+ xxx=+) = Cat(.;; x²). Using this, we obtain:
Lrecoms
Eg log po (x" xx(1); x
poxpox (x (x((1) x², xx)
(18)
The prior loss Cprior = DxL (g(x/=11x)) |l po (o(xx=1)) also reduces to because 0;=1 = which ensures (xx²=1xx") Cat(.; m) and pe (x(x)=1) = Cat(.; m); see Sahoo et al. (2024a) (Suppl. A.2.4).
Finally, we obtain a simple objective that is a weighted average of cross-entropy terms:
B
a/ az log pe(x") xxf x5))
(x: 0)
Σ
(19)
b=1
The above NELBO invariant to the choice noise schedule az see Sahoo al. (2024a) (Suppl. E.1.1).
B.4 RECOVERING THE NLL FROM THE NELBO FOR SINGLE TOKEN GENERATION
Consider the block diffuson NELBO for a block size of I where L' = 1, = L. The block diffusion NELBO is equivalent the AR NLL when modeling single token:
ab
llog p(x) <
E,
log (x 1xf,xx x xx))
1-a at
-1 and = =--t.
[
Enw 1y Σ
xx/ x xx)))) log log po
b=1
Σ E 1o
R. [logpo(x") xx. x50]
Expanding By(-).
1 E,, 1o.1]
t q(xx log x²= m. xb)
+ {((x = x" x log
x², x
(20)
Recall that our denoising model employs the SUBB-parramtterization proposdd in Sahoo et al. (2024b). The "carry-over unmasking" property ensures that log Po xx
x =x xb 0. as an unmasked
token is simply copied over from from the input of the denoising model to the output. Hence, (20)
reduces to following:
1 gx(] mlx") log xx m, <b)
Σ
[0.1]
1' x(x² m|x²) = t, we get:
1
E,-1o.1] (x 1x m,
=m, xbb)
19

---

Published as a conference paper at ICLR 2025
log Pa (x
m. x
(21)
For single-token generation (L' 1) we recover the autoregressive NLL.
B.5 TIGHTNESS OF THE NELBO
For block sizes 1 - K L, show that -log p(x) S Lx I LK+1. Consider K where recover the autoregressive NLL (see Suppl B.4):
ag po(x") x2i x(0)
L1
log 10, Eg
at
log (x m.x50)
(22)
Consider the ELBO for block size =
1/2
oj Cz po(x" xxf,x=00
L2
Σ
log 10, Ey
(23)
We show that L1 < L2, and this holds for all S K S L by induction. Let x correspond the token in position E [1, I'] of block We derive the below inequality:
L/2
log mm xbb)
log 10.10 By po(x" xxf,xx xb)
aq
L/2
Σ
log (0.1 By II
Po(x" x 2h)
1=1
L/2
Σ
log
E Eo, Eg
po
(xcree
x x x0
1 az
1=1
i=1
L/2
2
log E, (o.1 Rg
polxxie
x x0)
(24)
Oz
B.6 SPECIALIZED ATTENTION MASKS
We aim model conditional probabilities pa(x x xb for all blocks b [1, BJ simultaneously by designing an efficient training algorithm with our transformer backbone. However, modeling all B conditonal terms requires processing both the noised sequence x! and the conditional context x for all b.
Rather than calling the denoising network times, we process both sequences simultaneously by concatenating them Xiæll + X2 @ x as input to a transformer. We update this sequence X of length 2L tokens using custom attention mask Miai E {0, 1] 222x2 for efficient training.
The full attention mask is comprised of four L x L smaller attention masks:
MBD
MoBc
Min
MBC
where MBD and MOBc are used to update the representation of x, and MBc is used to update the representation of x. We define these masks as follows:
MBD (Block-diagonal mask): Self-attention mask within noised blocks x;
[MBDly {
if i, in the same block otherwise
20

---

Published as a conference paper at ICLR 2025
MoBc (Offset block-causal mask):
conditional context x <b
[MBBll {
j belongs block before
otherwise
MC (Block-causal mask): Attention mask for updating x² if j belongs in the same block as i, block before otherwise
[MBOlij
We visualize an example attention mask for and block size L' Figure 3.
x
Block Diagonal (MBD)
Offiset Block Causal (MoBc)
Block Causal (MBc)
4
X-1
X2
x-3
X,
x
x²
x
Figure 3: Example of Specialized Attention Mask
B.7 OPTIMIZED ATTENTION KERNEL WITH FLEXATTENTION
As Figure demonstrates, our attention matrix is extremely sparse. We can exploit this sparsity to massively improve the efficiency of BD3-LMs.
FlexAttention (Dong et al., 2024) is compiler-driven programming model that enables efficient implementation of attention mechanisms with structured sparsity in PyTorch. provides a flexible interface for defining custom attention masks while maintaining high performance comparable to manually optimized attention kernels.
Below in Fig. 4 define block-wise attention mask, block diff difffmass mask, based on its definition as Min E {0, (0, 22Lx2 in Suppl. B.6. We fuse the attention operations into a single Attention kernel designed to exploit the sparsity in attention matrix increase computational efficiency. By doing so, we perform the following optimizations:
Precomputed Block Masking: The create_bloct haa__bloookkakkkkkkk utility generates sparse attention mask at compile-time, avoiding per-step computation invalid attention entries. Through sparsity-aware execution, FlexAttention kernels reduce the number of FLOPs in the attention computation.
By leveraging block-level sparsity, the attention mechanism avoids full materialization of large-scale attention matrices, significantly reducing memory overhead. FlexAttention minimizes memory accesses by skipping fully masked blocks.
Reduced Memory Footprint:
Optimized Computation via torch. compile: The integration of torch. compi ile enables kernel fusion and efficient execution GPUs by generating optimized Triton-based kernels. This efficiently parallelizes masked attention computations using optimized GPU execution paths.
21

---

Published as a conference paper at ICLR 2025
def block diff (b, h, iix, kv wix, block size, н**
Constructs the specialized block diffusion attention mask composed of three masks:
++Block Diagonal Mask (M_BD) *x; Self-attention within noised blooks ##0ffset Block Causal Mask (M_BBC) Cross-attention for conditional context **Block Causal Mask (M_BC) xx: Attention to update x0
Args:
b, h: Batch and head indices (ignored for mask logic) Lidx, kv_idx: Query and Key indices. block_size: Defines the block structure.
Sequence length of x_0 and
Returns:
A boolean attention mask.
Indicate whother token bolongs to xt (0) or x0 (1)
x0 x0_flag_q (q_idx >= n)
x0 =0_flag_kv (kv_idx >=
Compute blocs indices block_q = torch. where (x0 flag_q == 1,
(q idx n) // block_size, Lidx // bleck_size)
block_kv torch. where xx0_flag_kv
1,
(kv_idx n) // size,_size, kv_idx // block_siiie
sxI. Block Diagonal Mask (M BD) block_diagonal (block_ block_kv) & (x0_flag_q x0_flag_kv
++2. Offset Block-Causal Mask (M_BCC) **
offset_ brsset_bleck_caae
(block_q block_kv) (x0_flag_s 0)
& (x0 flag kv == 1)
**3, Block-Causal Mask (M_BC) **
block_causal (block_q >= block_kv)
(x0 _ == 1)
(x0_flag_kv
**44 Combine Masks **
return block_diase diacondaa
block_causal
Figure 4: We can adapt the masking strategy from Fig. 3 to a Flex compatible sparse masking function as above. This enables the creation of customized JIT attention operation that uses significantly less memory with up to ==5X speedup over the naive native scaled dot _tr_ddooooo______e wtwpeppoooooeeeee attention implementation PyTorch (> 2.5) on A5000 GPU with 1024 and batch size B 16.
22

---

Published as a conference paper at ICLR 2025
from torch, torch.nn. at.eteniioon flex attention import flex attention, create_block_mast
from functccls import partial
Define block-wise attention mask my my_block diff mask partial bblock_diff mask, len_sensee__ee block_size
=block_size)
Generate optimized sparse block mask block_mask block mask wtt.kllcccck___eaeeee Nene, None, seq_ien=2, seq_ien=2, device=device)
Compute attention using PlexAttention
Use no-cudagraphs to avoid extra copy on small compile le graphs. Use max-autotune if compiling a larger model all at once.
@torch. compile compile (fulgrphhttll def single pass block_ diff a k, v, block_mask) return flex_attention k, block_mask-blook_makkk
Figure 5: Attention computation using FlexAttention with our proposed custom mask.
This implementation exploits FlexAttention's is ability to dynamically optimize execution based on the provided sparsity pattern. By precomputing block-level sparsity and leveraging efficient kernel fusion, it enables scalable attention computation for long sequences.
Overall, this approach provides principled method to accelerate attention computations while preserving structured dependency constraints. End-to-end, replacing FlashAttention kernels using custom mask with FlexAttention kernels leads to 15% speedup in model forward pass. We use 16.
single A5000 for L 1024 and batch size
23

---

Published as a conference paper at ICLR 2025
C EXPERIMENTAL DETAILS
We closely follow the same training and evaluation setup as used by Sahoo et al. (2024a).
C.I DATASETS
We conduct experiments on two datasets: The One Billion Word Dataset (LMIB; Chelba et al. (2014)) and WeenWeeText (OWT; Gokaslan et al. (2019)). Models trained on LMIB use the hert-base-uncase
tokenizer and context length of 128. We report perplexities split of LM Models trained on OWT use the GPT2 tokenizer Radford et al. (2019) and context length of 1024. Since OWT does not have validation split, leave the last 100k documents for validation.
the test
In preparing LMIB examples, Sahoo al. (2024a) pad each example fit the context length of L = 128 tokens. Since most examples consist of only a single sentence, block diffusion modeling for larger block sizes L' 4 would not be useful for training. Instead, we concatenate and wrap sequences to a length of 128. As result, we retrain our autoregressive baseline, SEDD, and MDLM on LMIB with wrapping.
Similarly for OWT. we do not pad or truncate sequences, but concatenate them and wrap them to length of 1024 similar to LM1B. For unconditional generation experiments Section 6.2, we wish to generate sequences longer than the context length seen during training. However, Sahoo et al. and end-of-sequence tokens ([BOS), [EOS] respectively) at the
(2024a) inject meginning-of-sequeme beginning and end of the training context. Thus, baselines from Sahoo al. (2024a) will generate sequences that match the training context size. To examine model generations across varying lengths in Section 6.2, retrain our AR, SEDD, and MDLM baselines without injecting [BOS] and [EOS] tokens in the examples. We also adopt this preprocessing convention for training all BD3-LMs on OWT.
C.2 ARCHITECTURE
The model architecture augments the diffusion transformer (Peebles Xie, 2023) with rotary positional embeddings (Su et al., 2021). We parameterize our autoregressive baselines, SEDD, MDLM, and BD3-LMs with transformer architecture from Sahoo et (2024a) that uses 12 layers, hidden dimension of 768, and 12 attention heads. This corresponds 110M parameters. We do not include timestep conditioning as Sahoo et al. (2024a) show it does not affect performance. We use the AdamW W optimizer with batch size of 512 and constant learning rate warmup from 0 to 3e-4 for 2.5K gradient updates.
C.3 TRAINING
We train a base BD3-LM using the maximum context length L,' = for 850K gradient steps. Then, we fine-tune under varying L' using the noise schedule optimization for 150K gradient steps on the One Billion Words dataset (LMIB) and OpenWebTee (OWT). This translates to 65B tokens and 73 epochs on LMIB, 524B tokens and 60 epochs on OWT. We use 3090, A5000, A6000, and A100 GPUs.
C.4 LIKELIHOOD EVALUATION
We single Monte Carlo estimate for sampling to evaluate the likelihood of token block. We adopt a low-discrppancy sampler proposed Kingma et al. (2021) that reduces the variance this estimate by ensuring the time steps are more evenly spaced across the interval [0,1] following Sahoo
et al. (2024a). In particular, we sample the time step for each block b E (1,..., B} and sequence E
(1...., K} from different partition of the uniform interval t(k: b) 41 (k-1) (R-1)B+b)
KB
This low- www-ddccrepaccy sampler is used for evaluation. For training, each masking probability may be sampled from "clipped" range - a U[[8 w). During training, uniformly sample E (0. under the low- cow-discrepancy sampler. We then apply a linear interpolation to ensure that the masking probability is linear within the desired range: ar (w B),.
24

---

Published as a conference paper at ICLR 2025
When reporting zero-shot likelihoods on benchmark datasets from Radford et al. (2019) using models trained on OWT, we wrap all sequences to 1024 tokens and do not add [EOS] between sequences following Sahoo et al. (2024a).
C.5 INFERENCE
Generative Perplexity We report generative perplexity under GPT2-Large from models trained on OWT using a context length of 1024 tokens. Since GPT2-Large uses context size of 1024, we compute the generative perplexity for samples longer than 1024 tokens using a sliding window with a stride length of 512 tokens.
Nucleus Sampling Following SSD-LM (Han et al., 2022), we employ nucleus sampling for BD3- LMs and our baselines. For SSD-LM, we use their default hy peperaraaeeters p = 0.95 for block size L' 25. For BD3-LMs, AR and MDLM, we use p 0.9. For SEDD, we find that p 0.99 works best.
Number of Diffusion Steps In Table BD3-LMs and MDLM use T 5K diffusion steps. BD3- LMs and MDLM use efficient sampling by caching the output of the denoising network as proposed by Sahoo al. (2024a): Ou al. (2025), which ensures that the number of generation steps does exceed the sample length L. Put simply, once token is unmasked, it is never remasked as result of the simplified denoising model (Suppl. B.3). We use MDLM's block-wise decoding algorithm for generating variable-length sequences, however these models are not trained with block diffusion. We adopt their default stride length of 512 tokens.
SSD-LM (first row in Table 7) and SEDD use T = 1K diffusion steps. Since block diffusion performs diffusion steps for each block b E (l...., B). SSD-LM undergoes BT generation steps. Thus to fairly compare with SSD-LM, we also report generative perplexity for T = 25 diffusion steps that the number of generation steps does not exceed the sequence length (second row in Table 7).
Improved Categorical Sampling of Diffusion Models
We employ two improvements Gumbel- based categorical sampling of diffusion models as proposed by Zheng et al. (2024).
First, the corrected Gumbel-basee based categorical sampling from Zheng et al. (2024) by sampling 64-bit Gumbel variables. Reducing the precision to 32-bit has been shown to significantly truncate the Gumbel variables, lowering the temperature and decreasing the sentence entropy.
Second, Zheng et al. (2024) show that the MDLM sampling time scales with the diffusion steps T, even though the number of generation steps is bounded by the sequence length. For sample length and vocabulary size V, the sampler requires sampling OTLVV) uniform variables and performing logarithmic operations on them.
We adopt the first-hitting sampler proposed by Zheng et al. (2024) that requires sampling O(LV) uniform variables, and thus greatly improves sampling speed especially when T >>>>> L. The first- hitting sampler is theoretically equivalent to the MDLM sampler and leverages two observations: (I) the transition probability independent of the denoising network, (2) the transition probability the same for all masked tokens for given t. Thus, the first timestep where a token is unmasked can be analytically sampled as follows (assuming linear schedule where a; = 11-1-)) f):
l L, 1/n
(25)
where n E (I...., }} denotes the number of masked tokens, 4100 1] and fn corresponds to the first timestep where n tokens are masked.
Variable-Length Sequence Generation For urbitrary-length sequence generation using BD3-LMs and AR in Table 6, we continue to sample tokens until the following stopping criteria are met:
1. [EOS) token is sampled
2. the average entropy of the the last 256-token chunk is below 4
where criterion are necessary to prevent run-on samples from compounding errors (for example, a sequence of repeating tokens). We find that degenerate samples with low entropy result in significantly
25

---

Published as a conference paper at ICLR 2025
low perplexities under GPT2 and lower the reported generative perplexity. Thus, when sample meets criterion 2, we regenerate the sample when reporting generative perplexity in Table 7.
D SAMPLES
<lenooiexii''s architect, lawyer and San Giovanni concerto crilic Paolo Capucotii, gained siiention from fellow gallery members and invited present reteoppctive, publishing
September, Kissi bis Marcus Cullection_ [0] which included Gloggo Asotio Arth und Moscolliso Ohier owaed by the uttss Belzim Massingolo) and Pan Gizzzuglio Romeam-Guesti The businesemun, Giovanni Paletti, an ouistanding collector, owned (he museum and the paining The level of criminal activity several attempts counter contennial runces including the possibllity that museum staff October 2005
reuxpaper interviews
agread
Angelo's
around the museum has continsed to incresse, which is even exposed to Cavello the only full year Francesco Belzinu's (1999),[4] was reported that curfier that evening, gumds had come on dayy began flinging an electric field with umbrellas from the baloory. As the fire continued, some of the guards sparked in apporent sput from the window of the cathodral. They remmined kdlly watched by a pile of trash left after key Pietro folla, who died on 21 October 2005, Just before 3:00 to 3pm Monday, 27 October 2005, strong winds brought the trash books
visiiess tonured
evening
hurled fromt every direction customer Jaeques Monet had beaten the hand of photographer Franco Campetti and in some cuses had stuck broken candle in the doorway of the museurn. Andr Romeam- Guessle responded by laughing when he spoke, Giancio Giuliano, the urtittic direciur of the Museum, even usidd to told joumaliees and that 'hee patient the trisomy machine [sie] carveed
the residence that opened 17 October Some
Some chiimed
corpees four hours into the musoum. but the whole time was the destruction
same press that hours murality" and further stated that 'We are nover saiified with our decision. We made un informed decision to build the museum after destraction, [S] Deaths [dit A littl after 12:00 am 17 Outober 2005 Giuliano and his portner Monica Concerts. notical that the trash was being thrown by presers-hy. and said joking
young man who
2008. Giuliano
truly "wrung
his film would later arresed." When lanienowska arrived. the people question were intersiewed sco-mat man who was initially lying on the scene and whocn lamienowska said was able stop them from passing the vicinity. Iguano proceeded to collect the trash and the police arrived, and closed the door of the muscum [6] During the war. the statue structure was partially removed and its cummons damaged. On the ove of the the U.S Army and Canadian Air Company, who owned a lot the Coepers of Paris Leopold condemaation
Captain lamienowskka leaned
that lannerello, the chair of the Muscoei, Captain Anderson Tularyau.
thief that directur
Frank Nolan
artists, including John DiDiune. [7] returned to the compound sell the museum items fincuding many of them originally stoken over the years more than a million returne);; on 12 October, the sculptor lack Uellein instailed temperary dome on Del Covella, [10] Among the changes over the yeur. Diema (cotured the lion in the middle of other two hulves of dome and the lion the back the Viduccio. [1]] In March 2018. Arvnzo Cissino fourth quarter that 2000s,
sheltered POWs,
were
overworked. This following your
organization
studio
une was completed November number of new structures were constructed by various museums, but most notably by Arvizo Cissino, the brothers soldies, as portaaed by architect Duvois Mayaven the illusion of the El Valleratas Humanities and Cultural Center, reconstructed by architect Davoes Benjamin. Just as the very significant additions to current management masis the del Museum such private three bedroum
studios
between summer
2005
Tradello's Ioss cabin, well the Unqutart, Aiba and
wall. Also new festival beld in the US in 2006. Urquhart was later stedited with establishngg record label Empire Recurds as an infleene on his music. Indlendffesss!
architectural espect from museuassss
rockings performed
during music
Figure 6: Sample from MDLM (Sahoo et al., 2024a) of length L = 1024 and T = 5K diffusion steps. The generative perplexity of this sample under GPT2-Large is 69.26 and its entropy is 5.6.
26

---

Published as a conference paper at ICLR 2025
<eedofleett When her child was platning to travel to Mesico, she thought it could be easy for her to find money to pay the ttp. But that didn't huppen. either. The girl unived on her doonsep the day before after they were scheduled to return to home and despite her own passpert blucked. Ii waon't Even her mother reported a bad visil. keep my passpott und their lees"" At first the police anived, British man
the airpot- the gie and flight insemuttonns were lockod nine 'I had no way the that parents should only
she
The Local. "I like have money for themselives to be fine, bui could never explain the siturion Later. she told her daughter that her parepot had been detained because she wanted to visil her fumily a hotel. She fell embarrasend and confused. Nearly two months later, she said, she lost 35(40) on rent and imugined that the traflic police and custums agents Bangkok would end up delaying flights and forcing to stay home. She was wurried that her father would daughter to spend
days the country. Meanwhile like home for the fins time." said Mahavram Kass, a spokesman for the Ministyy of Foreign Affains He's relerrnng to a tour urranged by the Freach and French foreign ministry, known as Couraee in the Child. That lour cost the region million worth of tickets, and cost the Calzis family about S25 million in lodging expenses, accorling
refuse alloning
police
seanch. wasn' eany them
child feels
statement by both the ministrr's behalf (be told the Portuguese policc spents) and London's is Embassy in 70,000
London told the French ambussador they provided a payment
would used to pay travel costs their visils), In 2011. family from Calais had moved to the UK aged 15, Their sister left to remain in France at years old, Her brother tried to answer that quession Ie explained to reporters at his service station Caluis sirport. "You lake the momnnng It's named after you and your little girls" he said. The last mother was having 19 month Briish Transpon Agency.
with her daughter that night, the police said, The first time she was back hustund took their daughter bost
the said mayur secount at Kathmands Airport a few hour after booking her night She panicked She called the was a Daley's is Nesse iscaal cash register), saying she was getting better, Her doctors visited her when she returned and her boytneend quit his job for four months after the visit, she said. "How do you feel like safe?' test from friend left her the police "She Parts took metro
mean, had plenty cash go
money buroww
she opened am
must go my wallet," sand Asrz Soon after, she booked plane ticket the
Calass. Ose night, French policeman phons and tell her siee knew that she could not leave at least one week without food. The four months her daughter spent in the UK was exhausiing and hard, and it reached the stage where she realioed she could burely stay in Briain, "Now no choice but to go home. Then we regret having a daughter" heart" "loday, daughter and my boyfriend decided security. Shame. Caines' family were put leave. The French police paid for her cur after she rented and her female officer used for the opening ceremnny of her press conference in Thailund, The police are still arrangtng for her family to have their official visit. Although her son back week now and his old job, her daughter needs stay in hospital Algies continue her education. But. linally, her parents will be making their girl home. The danghter case,
the doer local council huilding open
maliman
suid, He thought for minute. "You've 'ee broken hand.
this country
montss"" he wrote in email with daughter
flights cancelled
18 when they opened her was still child. living in Thailand with a small child,
boen two months ago. She doesn't talk about because mother, Anzia Gurdon, came to England as thrre-year old after her brother, Ehab Rahman, was working as British worker in Calais while living in London and stuudyng abroad in Dubai As mother carss 2,000 pounds a month they receive a well puid living secure accommodation, some with public transport buses. they make money, their child stays Other countries sometimess without family, and have furced to leave families As one former refugee fled Syris, his family was in detention, becouse when and their child had arroved, they would be living somewhere. The desemtion centers in Westers burope oftes have a higher rate for asylum seekers. Offec there are higher sty. the fumily that
take of their children. to provide child care. parents are oeten refugees from their home countries, they's to
UK they
up companies with
give butth to paremss
"sade houses" for young people, and then the people the center get older when their child alloowed have childd on, and usually only if they stay six months Childres are also detained and asked to show identification Recomse in most cases the refugees ask only about their identity. they don't 1 have secess to their own decuments, and have no other documentazion. An activist werking for Ireland says isss against offihore processing. He thinks the charity prublem here is like diseases which don't It sufficiaally seek out interational funding. think many conntries UNHCR website shows. good chunk
older
living children landed refugee camps Afrca, where mostly Africun migrants were sending children from Syna and Libya to their camps but those zumbers didn't fare so well. "Ai the moment when met the French. was borriii. they wanted me put my children in van. But was only Eddding It's something called 10-yaar vass." Ankaz said during interview. 'I want to idea
employ "humanitrrim" children. Now the job Before the refugen crisis Calais. 1.825 children
the
keep my childrea she can sloep with her childress whether they wast to take the chance. Is at big deal or not! Only in Caltis She explained what's agreed to so the children cas go homee and can have better future. "I'm vary determined. My childres want to home but it's life's personal decision." she said. "Five montss. I want them to be home. good shout what I've got She foel can just go to the road and provide accommodition
years. That's something It's like Caristmas. The dream
good oppartunity this point, It's much more just ahout "altematives". They now have to decide, at some point.
chance."
they'rr not getting jobs properly. anything to anyone. But have to wadk But they all don't work well because their families have her as a head. 'hhyy want me to have a job in England, but I feel like it's my home, and I'm not scared of work." she snid. " "And I foel that the opposite would he possible. I think in the future that I can have job two there." A Second World money brought up
a poor country. don't childien
their children."
Friday will held ousside Calais Saturday, dounting 100
UNHCK though the Friends and family expessed their "weskness" like many survivars in many coumtrics. "We just don't want to accept back there as soon is poosible." said one man. Her boother, who the son of long term migrant,
the coming
King Walab Samia Globall
what has to happen. We want to put the said: "The story of the refugee not a mother's story. The stary of the refugee childres's is story." "In Calais it's too young for these kids. They play her food sleep, she's young life withou any
ourside work outside, they just right? don't think much chinged. This protection. We don't need any protection at all. We need anything that would be sofer" "dendoftextb>
Figure 7: Sample from BD3-LM for block size L' = 16 of length L = 2031 under T = 5K diffusion steps (trained with a context length of L. = 1024). The generative perplexity of this sample under GPT2-Large is 24.3, and its entropy is 5.5.
27

---

Published as a conference paper at ICLR 2025
<enddofeeils but Wilson look over the program and tumed it around. 'Ile's is done a tremendous job, Caléwell stid. 'Ile's is done a fantastic job. The offense has allaas had un abundance of weapons, but il became evidens that they weren't I poing have a weapon to actuallly go after players from the slot. Now they re two di fffrrent weapons sels The top poop festures Dez Beyant and Mohumed Sanu, and the bottom group features iesortment pass rushens. The job has become mure comples. Sanu is more of classic get to the quariebsck and leave the comer open. Dontari Poe get the job done this year and became one of the more effectivee players at the positionn, even in the passing gime. However, Dallas has got to figure out how get their franchise widnouts contribute on the field. That can be tough. Adding Poe help get the receiving way. "We'v 've gol said, "I think that's is part of the reason why our last two games, especially when you te playing in Washington. D.C. you vo gut be aggressive, make sure you'l re bitting every catch. When you are. you re giving lot of yards." Part of that means taking the quarterback out of the equation and having him best coverage threst that Dallas
weagons
playens can make play un
and get thuse targets higher
CJ Spiller two time Pro Bowler. but if the Cowboys
upgrade their Caldwell
neceiving corps, is' going
step
more aggressive
the type weaponts that
In the NFC West, you want offensive wespons do better job running through covergge. The biggest Beethlisberger. Roethlisberger to his receiver group. Martavis Bryant and Antonio Brown are buth big time receivers, and last year they were in the lup 10 of yards per catch and necetving yunds the lengue. Thas production will nover he ustainuble, but if you re going to be an elite offerse, it's going to take lot of catching up- Rocthlisberger
QB
away the best quantebbck the lesgue.
of credit
go
All Pro reetiver. and he's the most dynamic option. But him the most productive reoeiver on offense.
take something like Bryant Brown better position, and Rotthliserger
a slightly lower price, have 18 games left in his career, but he's been doing it since he was rookie in 1991. But that's not the werst thing in the world. Roethlisbarger's is ability to hit guys on the outside with good movement, vision and running abilit what the Cowbuys need in order to keep with the competition. if he keeps getting betler, could become the best recriver in the league. Follow @walterfonball for updates. Like our Facebook page for mure Cow boys news, cocmmenttrr and conversation.
going be grean. may unly
owner of IHID Free in Charlotte Gardens is taking logal action agaiistt city. Derek Jaman says been forced to eviet his neighbour. Bob, after he look to social media threaten to burn down his neighboe's house. I incrediblly funous with the city." Jarman told 7,30. 'ive been irying keep my eyes on the price"" Thee in Charlotte Gardens suying it had seen '9.000+ people' enjoying great frequently targeted
weekend The company that his concems about the tree when
Bob after bee and said they had had ongoing conversation about my neighbor. called. hung up and he was very threatening" in the 30 days before they turned the free over to him. A neighbour posted the following unline message on October. am shocked about the scrioss problems you are having with your neighbour that has cansed you all (sic). You and the 2 of you making money the expense the good people Charlotte Gardens," " Bob I'm going being lawourt. and called the solicitor i could go court and to cy and get in injunction. "They told me 'you cannet" and the said. we can'l 1, we can't because you 'e sending people to the pulice". Tree in Charkote Candens (Pacebook) lle also said he threatened the city attorney if he didn't It stop the building from burning down. The the tweeted:" neighhoou threatened
IH10
of its
location. suid he had
contacted in October.
furious and said he just off the phone with the city manager. told her, 'no. tried get my phone, just hoping the solicinor would help me out. called again, and asited
after stid "thew this away, here's spot burn'. building stamed burn." down irce. windows,
Charlotte Giadenss
(Facebook) Bob threat," he said. 'Ile was a very strong penson. Ile's s already damaged so many people in this building. It's not going to go away." Tree in Charlotte Gardeas (Facebook) Jarman says tried talk the building owner out of the move, but the building owner's is behaviour had deleted him." "I'm going him by selling him suie have somzone of that." 'ree in Charlons Gardens (Pacebook) Jarman said Bob had pulled him up on social media. calling him a "white zut" and saying: "Hoe God's sake, stop calling me white sut. "I should have shut him up on Farehook.. He said he sent Beb the letter and thanked him for the support. "He should have done one designs buildings. "The building buming down', neighbour says Bob's neugtbburr Michacl Banks, says the "There are ywu black woreen that live nest door to me and they told me you can't do that" and then the fire went up and then the buiking burn: down." he stid. "You con't I barn down a house you don't buns down the house" " Coun-Pete Lawreses, the Narthumberiadd MP for Wood Green, stys he has about Hob's neughbours. 'It's very, very commenttary the and wellameanigg neighhoms who are appurently oblivions the destmaction
living room and his catire backyard. "It was more than
house
he said. "I have three kids, and Bob guing be
house. I need make I'm not going to that get in way
can go in there and protect me. "My son daes a really good job protecting me,
real artist and he's real
soid. declised to
architect of
but says the firm is daughter.
insult
society democracy general" he said. "It's interesting
community that's 50,000-plis people. you've 'v got your regalar their own home. "To me. that's is appalling and is probably a shocking amount of devastation that it's left behind. "I would expect there to be cutrage is well." " Bob Jamman fears for his lite after the tree was torched Bob says he has told the borthubberand Council that he had already received $1,000 in logal from the building legal options. sure we can't it get into into a legal battle with that penson and make that penon change his mind. "We doe't want to do any myythng to cause a scene or aayhody in the strect he upset." Boh Jommnn hopes to have an undarstanding with the builder on its legal options, who have refused to comment. Topies: state saue-pallaamen amokingg-aad and---addddd doubs, blakkwwies-616.. united Kingdon, england Hist postedWhen commercial get you fired up laset a day. They might not he so happy after a comple of days. Have a busch of friends and get ready to keep going. What are you wailing for? Make this long. one- offdendoheett
when told them about incident
his declined Banks," the situation. have uaderstanding with the builder,
haildig
hailder "We"e got make
currently assessing
got soet
other guys away playing, nest work day Once you make home, get a few junkies them They'l IIll be very happy have you, for
short
Figure& 8: Sample from an AR model (Sahoo et al., 2024a) with length T, 2003 (trained with a context length of I. = 1024). The generative perplexity of this sample under GPT2-Large is 10.6 and its entropy is 5.5.
28


Reviews:
[{"review_id": "rNP6YxgDyF", "reviewer": "Reviewer_Wz2T", "summary": "A new generative model on discrete label sequences is proposed: A hybrid between discrete diffusion and auto-regressive model. Specifically, it operates auto-regressively on a block level, and within a block, it uses a diffusion model. This model is called semi-autoregressive denoising discrete diffusion language model (SAD3-LM).\n\nThe model is evaluated on standard language modeling benchmarks. Different noise schedules are compared. For the special case of L'=1, the model also requires a special (no-op) noise schedule to be able to recover the performance of the auto-regressive model, due to the grad variance we get from the noise schedule otherwise.", "questions": "More general: What is the motivation to use diffusion models for language modeling? Maybe potentially even better PPL than auto-regressive models? We don't see that here. Or better speed? I assume this is the case, but this is not shown here. Or what else? Some discussion on this would be good.\n\np3 l143: \"computational artifacts for efficient training\" - unclear what this means.\n\nTable 2, Table 3, Table 4: I think it would be nice to also include L'=1 here for completeness.\n\n\nSec 2.2 \"The marginalization is tractable\" - What exactly do you mean by that? You mean that you can parallelize over the frames in x (L' for SAD3-LM)? But still you can not calculate the full marginalization, or can you? If not, I'm not sure I would call it like that. Maybe better \"the approximation of the marginalization is tractable\"? And how is this calculated then? You sample from p(x|x_t)? Or take the N-best from p(x|x_t)?\n\n\nSec 2.2: You give some examples of what Q_t could be. But what Q_t do you actually use here in this work? How do you compute the q(x_s^b|x_t^b,x^b) exactly? How do you sample from it for the ELBO? I think this should be specified exactly.\n\n\nIn eq 3, you define the loss L via the negative ELBO, but in eq 5, the loss is using the positive ELBO. Thus, something is wrong here. I assume you want to put some negative sign somewhere.\n\n\nSec 3.2: What happens when you do just one forward pass on noisy inputs and directly compute the loss that way? I understand that this is not totally correct, as the auto-regressive model part depends on clean input, but it might still work, and maybe even helps for regularization. It would be interesting to try.\n\n\nSec 4.1 Masked SAD3-LMs: The title of the section suggests that this is a different model (p), but from the text, I understand that only the noise process, only the q is different, right? Ah, but this effectively then changes also the SAD3-LM itself via equation 2? Please clarify this.\n\n\n\n\nSec 4.2 \"Although the objectives are equivalent in expectation\" - can you show this? (maybe just in the appendix)\n\n\nSec 4.2: When you show the variance of the grad, I assume this is the L2 norm? You should write that in the formula, or not? (Same also for equation 9.)\n\nSec 4.2: What about other methods to reduce the gradient variance? E.g. using multiple samples from q for the ELBO, or gradient clipping, or other methods? (Ah, I see that you discuss this further in Sec 5, where you propose some other methods.)\n\nSec 4.2 / Table 1: How exactly is the PPL for SAD3-LM calculated? This uses equation 5 and equation 3? How is x_{t(0)} sampled from q? What is T? How are the other x_t sampled?\n\n\nTable 2, Table 6: The PPL, are they exact or just upper bounds?\nWhat kind of hardware is used for training? How many epochs do you train? How long does it take?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Discrete diffusion is an interesting research direction with potential interesting applications. This work here presents a new way to improve this, allowing to interpolate between auto-regressive and diffusion models by changing the block size.\n\n- Good experiments, good studies.", "weaknesses": "- Some details are unclear (but I think these can be solved quite easily).\n\n- Some discussion on the motivation of such models would be nice.\n\n- No speed measurements (for the different cases: Training, sampling, evaluating log probs for given seqs). Also for the vectorized training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GLC081qBUU", "reviewer": "Reviewer_HEpL", "summary": "In this paper the authors propose a semi-autoregressive model for text generation called SAD3-LM (semi-autoregressive denoising discrete diffusion), which divides the input sequence of length $L$ in $B$ blocks of length $L’$ ($B = L / L’$) and trains a (transformer-implemented) discrete diffusion model (a la D3PM [7], but focusing more on a recent implementation called MDLM [8] that only performs masking) on each block $b$, which is conditioned on the previous blocks $1,…, b-1$. The authors offer an efficient implementation which caches the $K, V$ values of the transformer computations of previous blocks, where training can be parallelized in a single pass (concatenating the clean input $\\textbf{x}$ with a noisy version of the input $\\textbf{x}_{\\text{noisy}}$ and applying a specialised attention mask, and inference proceeds over the blocks sequentially. The authors, focusing on the masking model, additionally propose a theoretical study of the tightness of the NELBO objective varying the block length (showing is tighter when one reduces block length) and show that the semi-autoregressive training increases variance with respect to standard autoregressive training, proposing a way to reduce it by masking in a clipped range of the number of applied mask tokens (which is learned during training). The authors show extensive experimental results comparing with both standard autoregressive models and diffusion models for text data (D3PM [7], SEDD, MDLM [8], SSD-LM) on a wide variety of benchmarks (LM1B, Lambada, AG News, Pubmed, Arxiv) reaching good results in terms of perplexity and number of function evaluations (when comparing to SSD-LM).\n\nReferences:\n\n- [7] Austin, J., Johnson, D. D., Ho, J., Tarlow, D., & Van Den Berg, R. (2021). Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34, 17981-17993.\n- [8] Sahoo, S. S., Arriola, M., Gokaslan, A., Marroquin, E. M., Rush, A. M., Schiff, Y., ... & Kuleshov, V. Simple and Effective Masked Diffusion Language Models. In ICML 2024 Workshop on Efficient and Accessible Foundation Models for Biological Discovery.", "questions": "- Line 212: The authors should define $\\alpha’$, in the main body of the paper not only in the appendix.\n- Table 5: Any idea why results are so bad on AG News? And why AR is worse than diffusion approaches in 3 settings, different than when evaluating on in-distribution settings? Do the author think that discrete diffusion generalises better on out-of-distribution settings?\n- I don’t understand why comparison is SSD-LM is under ablations section. Is SSD-LM the naive implementation?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of a semi-autoregressive model, while not new (there is already a rich literature of models combining autoregression with diffusion, while focusing more on continuous diffusion like SSD-LM (see Weakness point 2), in this paper is developed via discrete diffusion. This is a way of proceeding that is very natural, and shares many parallels with novel methods in the literature focusing on block-wise parallel decoding such as [1] (https://aclanthology.org/2023.acl-long.689). It seems clear that a combination of sequential and parallel inference is a good solution, especially for speeding up the models, but this aspect is not much explored in this work (see Weakness point 4). Also the fact that one can generate sentences of arbitrary length is a big improvement over previous models in terms of usability, paired with the ability to estimate likelihoods (which SSD-LM cannot do).\n2. Showing the tightness of the NELBO (Appendix C) is an interesting theoretical argument that relates the standard autoregressive objective to discrete diffusion objectives.\n3. Good experimental section and good results over previous discrete diffusion approaches. Still one should have done experiments without first pre-training auto-regressively (see Weakness point 3)\n4. The paper is written in a good way, having a good structure, not containing errors and being easy to follow. Still there are two sections (Section 4 and 5) in which some parts are not clear (see Weakness point 1), but apart from those the execution is solid.\n\nReferences:\n\n- [1] Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Riccardo Marin, and Emanuele Rodola. 2023. Accelerating Transformer Inference for Translation via Parallel Decoding. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12336–12355, Toronto, Canada. Association for Computational Linguistics.", "weaknesses": "1. Some aspects of the work, especially Sections 4 and 5, are poorly defined and demonstrated. For example it is not very clear why the variance of the gradient estimator has the formula in Eq. 9, and also not very clear why extreme masking leads to poor variance. Authors should try to re-formulate these parts in a more sound way.\n2. The authors are missing a good number of citations:\n    1. First in [1] (https://aclanthology.org/2023.acl-long.689), the parallel GS-Jacobi decoding algorithm is proposed for text autoregressive models and has a similar structure to the approach proposed by the authors: move on blocks from left to right and perform parallel decoding on each block. The difference between the two approaches is that in [1], parallel decoding is done via Jacobi iterations while here instead one uses discrete diffusion. Even more related, a follow-up [5] (https://arxiv.org/abs/2403.00835), trains a consistency-like model [6] (which is a type of diffusion model) to speed-up the Jacobi iterations on each block. I see many parallels between the presented method and these two methods, especially the second. The authors should cite those papers and especially discuss in how they differ with [5].\n    2. Additionally, apart from other prominent approaches for discrete autoregressive diffusion like [3] (https://openreview.net/forum?id=Lm8T39vLDTE), there is a rich literature on combining autoregression with continuous diffusion, e.g. [2, 4] (http://proceedings.mlr.press/v139/rasul21a.html, https://openreview.net/forum?id=0EG6qUQ4xE), which the authors barely touch (citing SSD-LM and Diffusion-lm). Please integrate some more references from this literature.\n3. Since SAD3-LM is first pre-trained with standard autoregression for 850K steps is it fair to posit it as a semi-autoregressive discrete diffusion model? It can be that it learns representations especially on the pre-training part and the fine-tuning part is more accessory. I think experiments should have been performed also without pre-training as well in order to see how standard autoregressive the pre-training impacts the final model.\n4. One advantage of combining sequential autoregression with parallel decoding, as in [1, 5], is to improve inference speed, given that parallel decoding could be done in less steps than $L’$ steps (the number of steps required for autoregressive decoding on such block). I understand that the goal of this work is not much on improving efficiency with respect to autoregressive models since one does 10K steps instead of 1024 steps (Table 7), and I appreciate the reduced inference burden with respect to SSD-LM, but what is the point on doing discrete diffusion if there isn’t any gain on standard autoregression? I agree it is good to have an alternative to standard autoregression, hence all the efforts in the discrete diffusion area, and maybe improved perplexity will be reached in future, but still I think improved efficiency over standard autoregressive should be the main goal to be sought. I do not think authors need to compare with [1, 5] (which do achieve a speed-up, especially in [5]) but at least point and discuss as future work how to target these goals starting from their proposal and maybe improving via the faster models that are researched in diffusion distillation literature (e.g. the already cited consistency models [6]). \n\nReferences:\n- [1] Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Riccardo Marin, and Emanuele Rodola. 2023. Accelerating Transformer Inference for Translation via Parallel Decoding. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12336–12355, Toronto, Canada. Association for Computational Linguistics. \n- [2] Rasul, K., Seward, C., Schuster, I., & Vollgraf, R. (2021, July). Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. In International Conference on Machine Learning (pp. 8857-8868). PMLR.\n- [3] Hoogeboom, E., Gritsenko, A. A., Bastings, J., Poole, B., van den Berg, R., & Salimans, T. Autoregressive Diffusion Models. In International Conference on Learning Representations.\n- [4] Wu, T., Fan, Z., Liu, X., Zheng, H. T., Gong, Y., Shen, Y., ... & Chen, W. (2023, December). AR-DIFFUSION: auto-regressive diffusion model for text generation. In Proceedings of the 37th International Conference on Neural Information Processing Systems (pp. 39957-39974).\n- [5] Kou, S., Hu, L., He, Z., Deng, Z., & Zhang, H. CLLMs: Consistency Large Language Models. In Forty-first International Conference on Machine Learning.\n- [6] Song, Y., Dhariwal, P., Chen, M., & Sutskever, I. (2023, July). Consistency Models. In International Conference on Machine Learning (pp. 32211-32252). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fIzv4XNHnu", "reviewer": "Reviewer_ix6w", "summary": "This paper describes a diffusion language model that is autoregressive between blocks.  By being semi-autoregressive, the model achieves lower perplexity than other diffusion models.", "questions": "p. 3:\n\nEq. (3) is a negative ELBO.  I think therefore that either Eq. (5) should show -log ptheta(x) <= L_{SAR}, or else it should define L_{SAR} to be the negative of the sum.  If you apply the former solution, I think you need to change the acronym ELBO in the text before and after Eq. (5) to NELBO.\n\nThe meaning of Algorithm 1 is obfuscated by the call x_\\theta(x), in which the argument, x, has no superscript or subscript.  Is this argument the clean sequence (as in a teacher-forcing mode), or the noisy sequence?  The first paragraph of section 3.2 suggests that x is the clean sequence, in that it specifies two calls to x_\\theta: one on the noisy input (which seems to match the line of Algorithm 1 that generates x_{logit}^b), and one on the clean input (which might be the line that generates K^{1:B} and V^{1:B}, but this is the point on which I'm not clear).  On the other hand, Algorithm 2 seems to be defining x, with no superscript or subscript, to be the noisy sequence.\n\np. 4\n\nbased the -> based on the", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The key contribution of this paper is to demonstrate that it is possible to bridge part of the perplexity gap between diffusion-based and autoregressive language models by making a diffusion model partly autoregressive.\n\nThe analysis of gradient variance in section 4 is highly appreciated, and will influence the way in which other investigators conduct research.", "weaknesses": "The statistical significance of performance differences is not specified.  The differences are large enough to appear statistically significant, but it would be nice to have confirmation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ii0E4J5gZa", "reviewer": "Reviewer_ZiXH", "summary": "This paper proposes a semi-autoregressive discrete diffusion model to address the problem that diffusion models cannot perform arbitrary length prediction as autoregressive models.  The paper introduces SAD3-LMs, a class of semi-autoregressive diffusion model, that interpolate between discrete denoising diffusion models and autoregressive models. Compared to existing alternative semi-autoregressive diffusion models with Gaussian diffusion process, the proposed discrete method provides tractable likelihood estimates and yields samples with improved generative perplexity using an order magnitude fewer generation steps.", "questions": "1. What is the computational complexity and time complexity for the sampling algorithm given an arbitrary $L'$ and B?\n\n2. If I understand correctly, the SAD3-LMs is trying to address the limitation of diffusion models while maintaining the flexibility of autoregressive models. However, as in Table 7, SAD3-LM has significantly increased NEFs compared to AR, but only with limited PPL improvement. And as in Table 1, when $L'=1$, the SAD3-LM performs exactly the same as AR. What are the advantages of SAD3-LM compared to AR?\n\n3. According to Table 2, the method with different $L'$ values have unique noise rate distributions, this may require extra time and effort for tuning in real applications. I'm curious about can the masked-and-replace diffusion strategy by [1] solve the problem?\n\n4. The paper could be improved by involving an experiment on controlled text generation as in SSD-LM to further showcase its advantages of integrating diffusion models in AR. \n\nReference\n\n[1] Gu, Shuyang, et al. \"Vector quantized diffusion model for text-to-image synthesis.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is easy to follow. The paper proposes a semi autoregressive discrete denoising diffusion model and provides an efficient training and sampling algorithm compared to the continuous semi-autoregressive DPM (SSD-LM). The method is incrementally novel. As a semi-autoregressive diffusion model, the paper claimed that the method has advantages in generating full-length sequences that are longer than the length of the output context chosen at training time compared to existing diffusion language models. The paper provides a comprehensive ablation study and well-designed experiments to verify the SAD3-LMs.", "weaknesses": "My main concern is the motivation of integrating a discrete diffusion processing in AR. As when $L'=1$, the method performs the same as AR, however, significant higher NFEs, extra tuning required on noise schedules, and complex training and sampling algorithms are involved. The paper can be further improved by showcasing its advantages in real-world applications compared to AR methods.\n\nMoreover, please see Questions for the details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)