Masked Diffusion Models are Secretly Time-Agnostic Masked Models and Exploit Inaccurate Categorical Sampling
Authors: Kaiwen Zheng
Yongxin Chen
Hanzi Mao
Ming-Yu Liu
Jun Zhu
Qinsheng Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: discrete diffusion models
masked models
language modeling
Primary area: generative models

Abstract: Masked diffusion models (MDMs) have emerged as a popular research topic for generative modeling of discrete data, thanks to their superior performance over other discrete diffusion models, and are rivaling the auto-regressive models (ARMs) for language modeling tasks. The recent effort in simplifying the masked diffusion framework further leads to alignment with continuous-space diffusion models and more principled training and sampling recipes. 
In this paper, however, we reveal that both training and sampling of MDMs are theoretically free from the time variable, arguably the key signature of diffusion models, and are instead equivalent to masked models. The connection on the sampling aspect is drawn by our proposed first-hitting sampler (FHS). Specifically, we show that the FHS is theoretically equivalent to MDMs' original generation process while significantly alleviating the time-consuming categorical sampling and achieving a 20$\times$ speedup. In addition, our investigation raises doubts about whether MDMs can truly beat ARMs in text generation. We identify, for the first time, an underlying numerical issue, even with the commonly used 32-bit floating-point precision, which results in inaccurate categorical sampling. 
We show that it lowers the effective temperature both theoretically and empirically, and the resulting decrease in token diversity makes previous evaluations, which assess the generation quality solely through the incomplete generative perplexity metric, somewhat unfair.

Published as a conference paper at ICLR 2025
MASKED DIFFUSION MODELS ARE SECRETLY TIME- AGNOSTIC MASKED MODELS AND EXPLOIT INACCU- RATE CATEGORICAL SAMPLING
Kaiwen Z Chen', Hanzi Mao", Ming- Yu Liu', , Jun Zhu Qinsheng Zhang* DDpartmeet of Computer Science & Technology, Institute for AI, Tsinghua University
2NVIDIA
zkwthu@gmail com; dcszjemail tsinghua. edu. /qinshengz, yongxine, hanzim, mingyul @nvidiii
edw. en;
ABSTRACT
Masked diffusion models (MDMs) have emerged popular research topic for generative modeling of discrete data, thanks to their superior performance over other discrete diffusion models, and rivaling the auto-regressive models (ARMs) for language modeling tasks. The recent effort in simplifying the masked diffusion framework further leads alignment with continuous-space diffusion models and more principled training and sampling recipes. In this paper, how- ever, we reveal that both training and sampling of MDMs are theoretically free from the time variable, arguably the key signature of diffusion models, and are instead equivalent to masked models. The connection on the sampling aspect is drawn by our proposed first-hitting sampler (FHS). Specifically, FHS is theoretically equivalent to MDMs' original generation process while sig- nificantly alleviating the time-consuming categorical sampling and achieving 20x speedup. In addition, our investigation raises doubts about whether MDMs can truly beat ARMs in text generation. We identify, for the first time, underly- ing numerical issue, even with the commonly used 32-bit floating-point precision, which results in inaccurate categorical sampling. We show that it lowers the ef- fective temperature both theoretically and empirically, and the resulting decrease in token diversity makes previous evaluations, which assess the generation quality solely through the incomplete generative perplexity metric, somewhat unfair.
show that the
INTRODUCTION
Speed Quality Trade- off
Likedihoud Bused Principted Training Sampting
There are three primary paradigms of generative models. Diffusion models (Ho et al. 2020 Song al. 2021c) have been the prevalent way for generative modeling of continu- ous data with both theoretical and empirical success. They
Order- Order-Ainoatt Agnoatic
MDM
are SOTA in image, speech, video synthesis (Dhariwal &
Nichol 2021 Karras et al.] [022] [hen et al. [202] Ho
Masked Model
et al.] 2022) and serve as the cornerstone of large-scale
ARM
text-to-image (Rombach et al.) 2022 Balaji et al., 2022
Esser et al. 2024) and text-to- video (Gupta et al. [2023 Bao
et al. 2024) generation systems. Auto-regressive models
Time-Agnostic
(ARMs) have dominated the generation of discrete data
Token-by-Ton bokken
pecially languages (Radford et al. 22018] | 2019: Brown et al.)
We prove: MDM = Masked Model
| [003 Touvron al. (003), due the scalability and generalizability of the straightforward next- token-prediction mechanism based on transformer architec-
2020 Achiam
Figure 1:
Trilemma of generative
modeling for discrete data.
tures (Vaswani et al., 2017). Masked models, such as BERT (Devlin et al. (019) for masked lan-
guage modeling and MaskGIT (Chang et al. 2022) for masked image generation, are trained to
WWrk done during internship NVIDIA;
Thee corresponding author.

---

Published as a conference paper at ICLR 2025
reconstruct randomly masked tokens and sampled by order-agnostic decoding, They are alterna- tive approach to model discrete data while suffering from insufficient theoretical foundations.
Diffusion models have been extended to discrete data spaces with principled training and sam- pling (Austin et al. 202T Campbell et al., 2022, Meng et al. 2022 Lou et al. 2023). Compared to ARMs, they predict all tokens simultaneously and offer favorable trade-off between generation quality and sampling efficiency. Recently, masked diffusion models (MDMs), the leading variant of discrete diffusion formulations, are emerging a promising contender of ARMs (Lou et al.) 2023). Recent works (Shi et al. 2024 Sahoo et al. 2024) have simplified MDMs to align with the design space of diffusion models via continuous- time forward processes. training objectives, and sampling procedures, resulting in a unified view and empirical improvements. Positioned at the in- tersection of diffusion models and masked models, MDMS are considered promising as they inherit both the theoretical principles from diffusion models and the simple mechanism from masked mod- els. Moreover, is believed that MDMs can outperform ARMs in text generation when measured by the common generative perplexity metric (Lou et al. 2023 Shi al. 2024 Sahoo et al. 2024).
However, we argue that the current understanding of MDMs is still quite limited both theoreti- cal and empirical aspects. In this papet" we conduct thorough and comprehensive investigation and demonstrate that MDMs are essentially a theoretically and empirically equivalent form of typical masked models while being complicated, inefficient, and numerically unstable:
1. The training objective of MDMs is equivalent to that of masked models, differing only by nuanced likelihood based loss weighting. The introduction of an additional time variable in the loss function provides little benefit in practice. (Section (3)
2. The sampling process of MDMs, being computationally expensive and inefficient, has theoretically equivalent alternative (our first-hitting sampler) that is up to 20x faster and mirrors the random-order, token-by-token decoding process of masked models. (Section
3. The previously reported superiority of MDMs over ARMs on text generation stems from numerical issues that hack the generative perplexity metric during sampling by lowering the effective temperature, rather than genuine advantages. (Section
Based on these findings, we argue that the community should reconsider investing efforts in MDMs. That being said, MDMs do provide theoretical insights and supplementary perspectives to masked models, but in practice. the simpler masked models are not only sufficient but also free from above inefficiency and numerical instability issues. Moreover, scaling up MDMs on text en- counters fundamental inference inefficiency challenges compared to A ARMs, as the bidirectional attention in masked models is incompatible with KV caching, a crucial technique for accelcrating modern large language models (LLMs) that require long context length. This has been largely over- looked or intentionally downplayed by most existing works on diffusion language model Con- sidering the critical role of infrastructure and cost-effective inference in the deployment of LLMs, MDMs (or masked models) lack a clear and compelling prospect to replace ARMs.
2 BACKGROUND: MASKED DIFFUSION MODELS (MDMs)
Let X' 10 ...,,... Denote Am = { E Rm+11| - n. 1, π 2 0} as the standard m-simplex. For any data token or mask token x E X. denote e₂ E R as the corresponding one-hot vector. Continuous time discrete-space masked diffusion models (MDMs) (Shi al. 2024 (Shhoo et al. 2024) can be defined akin to diffusion models, with a continuous-time forward noising process
1) be the discrete data space, with extra mask token m added X.
(1) where a is the predefined noise schedule function satisfying au R 1, z 0, and Cat(T)) denotes the categorical distribution over the class probabilities π A The forward process has a time reversal for < t given No:
Q: (z (zo)= Cat(avez, + (1 a))mm)
(Cat(ez)), (1 (1-a,)em (a.
8y + m
G (1. ( 12,, vo) =
(2)
Cat
1-ac
82 m
I We present our views in a straightforward manner. The carlier version is available in Appendix Given our findings, may he more appropriate call them masked language models if based MDMs.
2

---

Published as a conference paper at ICLR 2025
Following DDPM (Ho al., 2020), the parameterized model is defined by replacing ero in the reversal with a data prediction model μe : X x R + Am:
(a(2.| = (1 Eza + ns (x),
(3)
and Ma is further parameterized by fe X R 1 as
H (2 t)
[softmax fa (2 0],
= m + m
(4)
so that satisfies (1) the predicted vector contains valid class probabilities sum to 1: (2) the predicted To has zero probability of being the mask token; (3) if token is already unmasked, it no longer changes. When dy + 11,r 01 + and the number timesteps tends to infinity, is proven that the
parameterized model pe has evidence lower bound (ELBO) log pe (2o) Lox, where
0/ Bug ol 1-a, a4
(mo) ((ae
m c log (1 t)] dt
(5)
is a time-weighted cross- cross-entropy loss, af daj and dR,, m is indicator function. We refer to Loo, the training objective, the negative ELBO (NELBO).
di
Multi- Dimensional Case For a token sequence a E X = {0, 10.1....,,. m 1. mm) of length
L, MDMs choose a factorized forward process 4:/0 (zn) I 2: (=t (=(")) over different dimensions, where z(()) denotes the I-th token of æ. As a result, the reversal 1s (x, v0) =
I (s]r,((z3 (1) jar x6 (!1) and the parameterized model (o(a))/a)))) I g( 1 mn +
Hg (1) (z) also factorize. Here the network P40 X2 R + (A A predicts the probabilities
all positions at time, and we use H48 to denote the I-th column of μag The ELBO loss in Eqn. (5) under multi-dimension can be written as
((L)
E. a
ag
(200))
Σ (0:..:mmm _m
11) T log u4 (2), dt
(6)
Context of Discrete Diffusion Models MDMs described above are a simplified version of the best-performing masked (or absorbing) case in discrete-space diffusion models. Discrete diffu- sion models, originated from D3PM (Austin et al.) [202]). rely on discrete-time or continuous-time Markov chains model transitions in discrete space. Notably, concrete score (Meng et al.) (022)) in discrete diffusion acts as an analog of the score function in continuous diffusion, and recent work SEDD (Lou al. 2023) proposes score entropy for robust and scalable learning of the concrete score. The model definition (Markov chain, score parameterization), training objective (diffusion- weighted denoising score entropy) and sampling procedure (Tweedie 7-leaping) of SEDD Absorb can be proven equivalent to the simplified expressions (Eqn. (I)
3 (4) 55) in MDMs. Interested
readers can refer to Appendix D for further details.
REVISITING THE TRAINING OF MDMS
MDMs are defined and trained by the continuous-time forward process (Eqn. I.) time-dependent network parameterization (Eqn. (4) and continuous time ELBO (Eqn. (5)). However, different from continuous- diffusion models (Song et al. 2021c), the evolution of æ; is discrete. The evolution trajectories of (x,, f) are like pairs of "phenotype" and "genotype", where the continuous changes in time may not be reflected on the observable traits of æ;, In this section, we aim to disentangle the internal time variable i and the external traits of the masked sequence æ; in the training of MDMs.
3.1 REFORMULATING THE ELBO WITH THE NUMBER OF MASKED TOKENS
Previous works (Shi et al. 2024 Sahoo et al. 2024 show the invariance of the ELBO to the noise schedule 0₂ by performing the time change-of-ve varriabele y log(1 a4) À log 1-a: following VDM (Kingma et al.) (021). However, this does not get to the essence they still rely internal continuous time. In the following proposition, we show that the sequence NELBO of MDMs can be expressed partition by the number of masked tokens instead of the continuous time.
3

---

Published as a conference paper at ICLR 2025
Proposition 3.1 (ELBO by the Number of Masked Tokens). For Dy with sequence length L, denote In as a sequence with n masked tokens. and q( (T)) as the discrete forward process which ran- domly and uniformly masks tokens zz. Suppose the noise schedule a, satisfies agg = -1 0. The sequence NELBO in Eqn. (6) can be reformulated as
- E
Σ n=1
(en (20)
e
log M4 (xnn)
where
log f. (Z)((n)) = Ban-B(L-nt1. [log (en, (an)).
(8)
a-! is the inverse function of ai satisfying a- (at) t, and B(aa b) denotes the Beta distribution with shape parameters a. b > O.
40-
This expression offers two aspects of theoretical insights:
301
512
Mixture of Experts From Eqn. S the time-dependent net-
work u t) implicitly parameterizes time innneiddeenddnn network (2) by aggregating the logarithm at the same æ but different t, which can be seen as ensemble. The time is sampled unevenly
10-
so that oy follows a Beta distribution B(I- --7----111 1,). This distribu- tion has the mode (peak) 4.=1 and variance n n(L-n++1)
0.0
(I+1))((++2)
4((+2))
With large sequence length L. the variance small and the distri- bution is concentrated around the mode, as illustrated in Figure 2 Moreover, under the performiff linear schedule a, MDMs (Lou et al. 2023 Shi et al. 2024 Sahoo et al. 2024 the mode of t is --1 close to the masked ratio .. Theretore, the time variable t can be seen as continuous relaxation and smoothing of the masked ratio, and we can directly condition the network on the discretely distributed masked ratio instead of the continuous time while yielding similar performance (Appendix J.1
Figure Probability density function (PDF) B( with L = 1024.
t
Discrete ELBO From Eqn. Z. the sequence NELBO can be expressed discretely with the time- agnostic network (z). Therefore, Eqn. (7) can serve NELBO of masked models straight- forward way: uniformly choose the number of masked tokens n from {1,.... L}. uniformly mask random tokens æo to obtain T,,, and compute the average cross-entropy loss of po(x) on these n. positions. The weighting 1 51 in this NELBO resembles the likelihood weighting in diffusion models (Song et al., [202bb] Kingma et al., 202T [u et al. 2022a| Zheng et al.] (2033)), facilitating maximum likelihood training of masked models. Note that early works on order-agnostic auto- regressive models (Uria et al. 2014: Hoogeboom et al. (2221a) already reveal this weighting from different perspective" While in the context of masked models, there are few discussions the ELBO. Discussions on related work are placed in Appendix
3.2 TIME-INDEPENDEN NETWORK PARAMETERIZATION
When the original network 44g is parameterized without the time input, we have fág = 440 in Equ 77. In this case, the training of MDMs is completely free from the time variable and behaves like masked models. The rationality of time-independent network parameterization has been discussed recent works (Ou et al. 2024 [Shhoo et al.] 2024). Here we restate this conclusion with our simplified notations from the perspective of the optimal model.
Proposition 3.2 (Optimal Masked Diffusion Model). Given unlimited model capacity, the optimal network 6* that minimizes the NELBO in Eqn. (6) satisfies
(1) ag (x, t) (
e_m
where N(x) is deterministic function that counts the number of masked tokens in æ, and To (x ()) is the posterior distribution of the discrete forward process (x)0(x..,100))
The relation between BIB of order-agnostic ARMs and MDMs was also mentioned in recent work Ou 2024), while they only consider originally time-agnostic network instead of mixture-of-experts.
4

---

Published as a conference paper at ICLR 2025
From the above expression, the optimal MDM is irrelevant to the time variable, justifying the fea- sibility of removing the time input. Besides, it can be extended to general weighted cross-entropy
(1) (zn) of masked models. ch with loss C - Wn (mja. Er =m (1 log pug
arbitrary positive weights w > O yields the same optimal solution as Eqn. (9) thus acting as a sur- rogate objective the NELBO. This theoretically supports wide range of objectives for training masked models, such as the loss in MaskGIT (Chang et al. 2022).
3.3 PRACTICAL CONSIDERATIONS
While there are theoretically equivalent variants for training MDMs (coniinuou-tiim/ddisccc) time/discrete network), these choices may have practical implications due to differences in network inputs and loss variances. We present some training comparisons and our attempts to improve training (e.g., variance reduction, flow matching) in Appendix J.1 Overall, all options yield similar performance, and the low- low-discrepancy sampler (Kingma et al. 202T). when applied to time or the number of masked tokens, can significantly reduce the loss variance.
ELBO, www.roddittonsttim-iineeeeeeeeee
Note that while several works (Lou et al. 2023 Shi et al. 2024 suggest that MDMs are compet- itive with ARMs in language modeling (beating GPT-2 (Radford et al. 2019) when measured by test/zero-shot perplexity), more fair comparison (retraining ARMs with the same configurations, Appendix J.1 (Sahoo et al., 2024) indicates that MDMs are only advantageous in language under- standing tasks (surpassing ARMs and BERT the GLUE metric (Wang et al. 2018)).
REVISITING THE SAMPLING OF MDMS
In the previous section, we demonstrate how the training of MDMs, both theoretically and empiri- cally, can be disentangled with the continuous time variable and behave like masked models. In this section, we turn our attention to the sampling of MDMs, which is also performed in continuous time and seems distinct from masked models. We aim to address its current inefficiency problem well as establish essential insights into its connection with masked models.
4.1 INEFFICIENCY OF CURRENT SAMPLING
MDMs are sampled in an ancestral way following the parameterized reverse-time process in Specifically, the sampling step æ; F, from time to < can be expressed as
Eqn. 3
z *
x
Cat (a. (w).t) 1-de
for every
(10)
2
Given the number of sampling steps N, the sampling process involves first discretizing the timesteps as 0 to < 1 < < IN = 1, and then performing reverse steps iy - f + ... - to according to Eqn. 10 Notable characteristies of MDM's 's sampling include: (1) Any mask token can only be unmasked once with no further changes. (2) Each sampling step requires forward pass through the network μe and conducting most L times of dimeeninnsio categorical sampling, where T. is the sequence length and | is the vocabulary size. (3) The number of sampling steps N can be significantly larger than I., and single sampling step may result in changes any token in the sequence. (4) As MDMs are trained with the continuous-time ELBO which assumes an infinite number of reverse steps, is theoretically rigorous to employ an equivalently large N.
Recent works propose simple caching strategy (Ou et al. 2024 Sahoo et al. 2024) to speedup the sampling of MDMs: when the network μ40 is parameterized without time inpu and the sequence is not changed in a sampling step t + (i.e., I. = 21), we can reuse the network output at the last step as (a..) ) = p (.:)) As the sequence changes at most I. times during sampling, the number of function evaluations (NFE) can be reduced to no more than L. However, sampling with the caching strategy still suffers from two major inefficiency problems:
'In our practice, the time-dependent network also exhibits no performance degradation with the caching strategy, so this assumption is unnecessary.
5

---

Published as a conference paper at ICLR 2025
fg
fg
Discretization
[M]
(M]
(M))
[M]
DCC
[M]
[PQ
1M
[q]
0.03
First-Hiunng
[M]
(M]
(M]
[M]
[M]
Figure 4: Illustration of the first-hitting sampler in comparison to the original sampling procedure.
Categorical Sampling is Time- Cone-Consuming In diffusion models, NFE is efficient indicator of the sampling speed, as the computation overhead beyond the network forward passes is negligi- ble. However, in MDMs, the Gumbel-based -basedd categorical sampling, which requires sampling total number of ([ uniform variables and performing logarithmic operations on them, can be ex- pensive compared network evaluations. As illustrated in Figure Bal when the number of sampling steps N > L, the sampling time scales with N instead the NFE. Categorical sampling steps that do result token changes are wasted, they contribute no information gain.
Caching Strategy Degrades in Batched Sampling When using the caching strategy in batched sampling, the network output can only be reused directly when all the sequences in the batch re- main unchanged after sampling sterß] Suppose the batch size is B, and the default linear noise schedule ot = 1 - t as well as uniform timesteps to used. The expected NFE under the caching strategy can be derived as I
Topal
botcl con...
Perwort farvard
Tultis sipend
20.00
4300
2300
Sampling Steps
Sampling
(a) Sampling time sequence
(b) NFE (caching strategy)
(caching strategy, batch size=1)
is
Figure 3: Illustration of sampling ineffciency using pre- trained models of MDLM (Sahoo et al. 2024 (L 1024).
N (1- N) BB) (proof in Appendix
E similar to the B case in Ou et al. (2024). As
lim - N(1 - (1-a ))2) BL. the NFE is no longer upper bounded by the sequence length but scales with the batch size (Figure
Algorithm First- First-Hitting Sampling of MDMs
4.2 FIRST-HITTING SAMPLER
the sequence length J., the vocahulary X' (0..... 1,m where the mask token, the noise schedule o, and inverse function a 1, the pretrained masked diffusion model p4g
Require:
The current sampling methods of MDMs. in- cluding the caching strategy, are neither effi- cient nor insightful into the essence of MDMs. To address this, we reexamine the sampling step Eqn. TTP.
1: mg [m
m)]
2: TL +-1
3:
4: Sample ~ 2/(0,
5:
Tn-1 c- 1(1-((11000 w1/m(1 ))..))
6:
pala.. 7n
When the number of sampling steps N + 0c and the maximum step size max S N 14: 4--1 + 0, Eqn. (O) tends to infinitesimal jump. In this case, the reverse sampling pro-
7:
Randomly and uniformly select an index I from {f (0))
mi (i... masked positions in æ..)
8:
was (4)
n-1 + Cal(p()) (*)
9: end for
cess becomes continuous-time Markov chain
Output: iz
(or Markov process), where each mask token unmasked at some moment according to the network prediction. Our key insight involves three folds: (1) Whether mask token will transit not during a time interval [s. f] is independent of the network. The network output only determines which token the transition larget given the condition that the transition happens. (2) The transition probability ou is equal for masked tokens at different positions. Therefore, each mask token has the same probability of being first unmasked. (3) The first-hitting time, which denotes the first moment any of the remaining masked tokens is unmasked, can be analytically sampled:
Proposition 4.1 (Analytic Sampling of First-Hitting Time), Denote TL 1 the initial time. Suppose there are n masked tokens, and the last time token is unmasked happens at Tu then the
We will introduce Gumbel-based categorical sampling in the next section.
We can reuse only the unchanged part of hatch, hut this potentially reduce parallel efficiency.

---

Published as a conference paper at ICLR 2025
12
12-2
M--2
16-2
2-
Te-2 21-2
Tooen-yy-Tllen
Pwolte
Exppolation
Predicioo Connectyy
grESD
Flisc Order
High-Order
Figure Variants the first-hitting sampler. æt denotes the sequence with / remaining mask tokens, and (a T-1) denotes the network prediction the step l.
next time token is unmasked can be analytically sampled by
a - - (1-a))))
~ U(0
(11)
where 1(0,1) the uniform distribution on [0, 1].
As outlined in A by recursively sampling the next time when any of the remaining mask tokens is first unmasked, then uniformly choosing a mask token and unmasking it according to the network output, obtain token-by-token sampling procedure of MDMs. Denote nn as the sequence with n remaining mask tokens. Since the transition 2n, - Øn-1 can be considered to happen in the infinitesimal step Tx-1 + di Ta-1, using the network output p Ta-1) time Tn-1 incurs no approximation errors. Therefore, the first-hitting sampler (FHS) is theoretically equivalent as simulating the continuous time reverse Markov sampling process. We illustrate the comparison between the FHS and the original sampling procedure in Figure
The FHS demonstrates appealing properties:
Tackling the Sampling Inefficiency The FHS can tackle the two inefficiency problems described in Section 4.1 Firstly, as the categorical sampling only conducted for determining the transition target of the single chosen mask token each step, the total computation cost is reduced to ((L Secondly, the first-hitting time Tn can be sampled independently and asynchronously across different samples in batch, avoiding performance degradation in batched sampling.
Connection to the Sampling of Masked Models When the network parameterization inde- pendent of the time, the FHS in Algorithm [ can be completely free from the time and become boken-by-token decoding process akin to masked models. This connection serves supporting ev- idence for the typical sampling procedure of masked models, as it is thcoretically equivalent the more principled reverse Markov sampling process of MDMs.
4.3 PARALLEL DECODING AND HIGH-ORDER VARIANTS
The by-tken decoding process of MDMs can be extended to parallel decoding by unmasking multiple tokens per step, the network μ4I predicts tokens all positions. This enables speed- quality trade-offs similar to diffusion models. As illustrated in Figure parallel decoding essentially reuses the previous network output to reduce the NFE, thus functioning
approximation method.
To reduce the approximation error, we follow the recipes of high-order diffusion solvers (Karras) al. 2022 ZZhag & Chen 2022 [u al. 2022b Zheng al., 2023a) to develop high-order sam- plers of MDMMs. We propose two variants: one based on extrapolating previous network outputs, and the other utilizing predictor-corrector method refine the samples (algorithms in Appendix G.1)
ARE MDMs BETTER THAN ARMs? A CRITICAL FAULT LOW-PRECISION GUMBEL-BASED CATEGORICAL SAMPLING
Before we proceed to verify the effectiveness of our proposed first-hitting sampler, we have to point out critical fault in MDMs' original sampling implementation. As suggested by previous

---

Published as a conference paper at ICLR 2025
There is the following definition:
The "right lane" on the lane lane lane. From the lane lane lane from lane lane lane lane lane in lane lanc on front lanc.
From lane lane lane the lane lane lane on the right lane from lane front lane lane to top lane. From the right lane from lane lane lane with the lane on the lane lane lane. The "that lane lane" on the year lane.
Figure 6: Segment of generated text by SEDD Absorb (Lou et al. 2023 at 50k sampling steps.
Table 1: Maximum Gumbel under different floating boaainng-ponnt precisions.
Structure (bits)
Data Type
Maximum Value (< 1) Representable
Maximum Gumbel
Sign
Exponent
Fraction
float32
1
2-21 x 0.99999994044
log( log(1 2 2--22) Re 16.6355
float64
1
52
1 2
53 9
logl log(1 2 53) 36.7368
works (Lou et al., 2023] Shi et al. 2024; Sahoo et al. 2024), MDMs seem to surpass ARMs with sufficient number of sampling steps when measured by the generative perplexity (Gen PPL as shown in Figure 7a| However, in this section, we identify for the first time a hidden numerical issue existing in previous codebases that makes this observation questionable.
5.1 Low TOKEN DIVERSITY UNDER NUMEROUS SAMPLING STEPS
Empirically, a reduction in Gen PPL observed by increasing the infer- ence budget. In particular, an ex- ceptionally low Gen PPL. (< 15)
All Dutte vor-d)
54
(bach dir.
SED0 Aloueb (latch sibet)
55-
SEDO Absech Shack
MDLM
(sunch senwi))
Camernaa rer
MULN
6.1
w/ caching samr))
MDLM cacrin (brtch vime
HDLM w/ suching (oitch smm-1)
achieved when the number of sam- pling steps approaches 50k.
However, when we check the gen- erated content, we discover that the quality is compromised by low token diversity (an extreme case is shown in Figure (). We further quantify this phenomenon by measuring the sentence entropy (Figure 7b). With the original sampler, the Gen PPL of MDMs surpasses ARMs around 2k steps, but the entropy is always lower and keeps decreasing.
100
1.0
Sampling Time Sensercc (1)
Samplin Time Soparox
(a) Generative Perplexity
(b) Entropy
Figure 7: Comparisons different models (AR, SEDD Ab-
sorb (Lou et al. 2023), MDLM (Sahoo et al.] 2024 trained on Open Tex (Gokaslan et al. (219)) with the same network ar- chitecture and configurations. We generate 64 samples using their original codchase on single NVIDIA RTX A6000 GPU, and vary the sampling steps N E {100, 500, 1 1000, 5000, 10000].
This low generation quality is unexpected, as theory suggests that increasing sampling steps should yield lower discretization еπтогs and more faithfully reflect the true model performance. We there- fore consider this hidden implementation issue and investigate further identify the root cause.
5.2 IDENTIFYING THE NUMERICAL. PRECISION PROBLEM
Our key observation is that, when we alter the floating-pott point precision during sampling from 32- bit to 64-bit, the entropy returns to a normal level similar to ARMs, but with a generative per- plexity > 100. After careful ablations, we identify the root cause as the inaccuracy in previous Gumbel-based categorical sampling. To sample from a categorical distribution with class prob- abilities { K Gumbel-max trick( is used by first sampling K independent uniform variables W; ~ ((0 1), then transforming them into samples from the standard Gumbel distribution G() 1) by 9s --==-oogf log( log u.). and finally obtaining the categorical sample n argmax, (log ग, + 9t)- The operation = - log(- - log u) theoretically maps u E [0, 1] to g E (-x,, +oo). But due to the limited representation ability floating-poin point numbers in implementation, u is constrained to [0. 1 - <) and g is constrained to (-oc, M). as shown in Table [] Therefore, the sample instead follows a truncated Gumbel distribution, denoted (G 1, M), which refers to the Gumbel distri-
Thhe evaluation metrics used in this paper are introduced in Appendix H.1
AA hrief introduction Gumbel tricks is provided in Appendix
8

---

Published as a conference paper at ICLR 2025
def sample categorical, aategordcl__umbclpppeeeeee (prabs::
Lorch. rand(
32-bit
pprobs shape,
devico-prooss.divice dtypes....
torch.rand( hrrp
64-bit
torch.randen strch.ran Fleat64)
B. 9.399999484
64-bit truncation
return (probs/ aargxxxd)nngg
Figure Code for different versions of Gumbel-based categorical sampling. The operation argmax, (log T. log(- - log us)) is simplified to argmax, (T: log u;)) to save computation cost.
bution 9(0, 1) conditioned on g x M. This tricky difference theoretically makes the categorical sampling inaccurate, i.e., argmax, (log क, + 9:) no longer follows the class probabilities {
To verify that truncation the fundamental issue, we conduct abla- tions by only modifying the categorical sampling code. As shown in Figure we manually scale 64-bit uniform samples to match the truncation in the 32-bit case. We then randomly generate 8 sam- ples with 2048 steps and compare the average generative perplexity and entropy in Table 2 The similar results between the 32-bit and truncated 64-bit cases confirm the impact of truncation.
Table Results with different versions categorical sampling.
Version
PPL.
Entropy
32-bit
31.24
5.17
64-bit
126. 11
5.66
64-bit
28.64
5.12
Remark 5.1. Note that auto-regressive LLMs like Llama (Tovrron et al. (023) and Mistral (Jiag ict al.) 2023) use torch. mult innmiiiial al for categorical sampling, which is also implemented with the Gumbel-max trick in the low-level C++ code of PyTorch. In contrast, we find the token-by- token decoding process of A ARMs and MDMs (by our first-hitting sampler) does not suffer from notable numerical issues under 32- precision (illustrations and explanations in Appendix J.2.2
5.3 CATEGORICAL SAMPLING WITH TRUNCATED GUMBEL
In the previous section, we empirically observe that truncated Gumbel-based categorical sampling reduces token diversity. Surprisingly, such effects can be precisely depicted in closed-form.
Proposition 5.2 (Closed-Fort) Form Categorical Sampling with Truncated Gumbel). Suppose the class probabilities are sorted as गा < TK. and gi TG(0, 1, M) are trancated Gumbel samples with muximum value M. Denote To O. For S n < K, we have P(argmax, (log n + +9t)
n) Tn Σ 3(i), where
(K+1-1- Ex mi
c-M
KK+----
Mk
M
1
B(1)
0
(12)
Ek=t
To the best of our knowledge, this formulation has not been revealed in previous works. Intuitively, with truncated Gumbel, the original class probabilities nn shifted to nh n, Σ B(t). This has two main implications: (1) As 3(1) Z and Tn are sorted, if Tmz > Tog. the adjusted class
probabilities satisfy "e1 Kmn, This indicates that relatively larger probabilities are further ampli-
Fig Tang"
fied, creating an effect similar to lowering the temperature. (2) In the sampling step, the probability of unmasking is adjusted based on the network output, resulting in unequal unmasking probabilities at different positions a sequence. This implies that some tokens are prioritized to be unmasked, further reducing the randomness and overall entropy.
In both aspects, the inaccurate categorical sampling deviates from theoretical correctness and re- duces the generation diversity, leading to unfair evaluations of MDMs generative performance.
A FAIR EVALUATION OF MDMS GENERATION
In this section, we will fairly evaluate the generation performance of MDMs and examine the im- pact of our proposed sampler and the temperature. Our experiments
based the codebase of
MDLM (Sahoo et al.) 2024) which is inherited from SEDD (Lou et al. 2023). We fix the categor- ical sampling to 64-bit floating-pote precision that the numerical truncation is negligible. We

---

Published as a conference paper at ICLR 2025
directly use pretrained models (AR, SEDD Absorb, MDLM) provided by MDLM, which share the same network architecture and were trained with the same configuration. Additional experiment details are provided in Appendix H We display some generated text in Appendix J.3.1 to illustrate the token diversity under different sampling strategies.
6.1 ORIGINAL SAMPLER V.S. FIRST-HITTING SAMPLER
5.75
5/73
MDLUM
5.733
All Duarce sire-d)
IED0 Abaora (brch sic
MDUl (banch sic-tt 1]
MD.M wi cackig (luck (oe-3)
5003
MDUM ai cacking (Junc dosill
5/23
MDD fert bittin (jutch (iew8)
40
Mit fou litting ligh warie (lanc cimwa)
(a) Generative Perplexity
(b) Entropy
Figure 9:
Comparisons of different models after fixing the categorical sampling to 64-bit. We addi- tional compare our propose first- first-hitting sampler with steps N E {64, 128, 256, 512, 1024).
Figure 9 compares both the generative perplexity and the entropy of different models. For the base- lines, SEDD is sampled by their analytic sampler (Tweedie r-leaping), and MDLM is sampled with and without the caching strategy. For our first-hitting sampler, the parallel decoding is performed by unmasking the same number of tokens per step. High-order variants employ the extrapolation strat- egy when the number of sampling steps N 128, and the predictor-corrector strategy otherwise.
After the numerical problem is fixed, the entropy returns to a normal level (5.60~5.70) for all mod- els. Besides, terms of the wall-clock time" revealed to be around 100, significantly lagging behind that of counterpart ARMs (< 40).
sampler can be up to 20x faster than previous sampling strategies of MDMs in 5) Despite the notable speedup. the true generative perplexity of MDMs
6.2 TRADING OFF GENERATIVE PERPLEXITY AND ENTROPY VIA TEMPERATURE
The truncation effect of 32-bit poating-point numbers creates trade-off between generative perplexity and entropy by varying the number of sampling steps (Figure 77 This trade-off arises from a tricky interplay of inaccurate categorical sampling and the ap- proximation error limited discretization steps. In Figure [0] we demonstrate that this trade-off can be achieved at a lower time cost by using the correct sampling (our 1024-step high-order sampler) and manually adjusting the temperature within the range [0.8, 1.0]. The trade-off curve of our method slightly better than the original MDM sampling, while still significantly lagging behind ARMs.
56
5.4
6.2
temperatas
4.5
M (1> o2]
MDLM (Ouns josperatree
Gee PPI
Figure 10: Trade-off of genera- tive perplexity and entropy.
7 CONCLUSION
In this work, we advance our understanding of masked diffusion models (MDMs) by revealing their theoretical equivalence to masked models and uncovering a hidden numerical issue that com- promised the faimess of previous evaluations of MDMs' generative performance. Our findings challenge earlier claims that MDMs can surpass ARMs in text generation. Despite these negative results, acknowledge that text-based experiments may inherently favor ARMs, as text nat- urally follows a left-to-right order that ARMs are better suited to model. Nevertheless, we believe that MDMs may hold potential for applications where order-agnostic data structure is key prior, and in practice, simply using masked models may be a better choice.
Thhe efficiency gains (measured by inference wall-clock time) can depend on many factors and may not be large as 20x in other settings (analyzed in Appendix J.3
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The team would like to thank Aaron Lou, Cheng Lu from OpenAI, and Jiaxin Shi from Google DeepMind for their valuable discussions and comments. K. Z and were also supported by the National Natural Science Foundation of China (Nos. 62350080, 62106120 92270001), Tsinghua Institute for Guo Qiang, and the High Performance Computing Center, Tsinghua University; J. was also supported by the XPlorer Prize.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
William J Anderson. Continuous- time Markov chains: An applications- appracch Springer Science & Business Media, 2012.
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, 14:17981-17999 2021.
Yogesh Balaji, Seungjun Nah, Xun Huang, Arash Vahdat, Jiaming Song, Qinsheng Zhang, Karsten Kreis, Miika Aittala, Timo Aila, Samuli Laine, et al. ediff-i: Text-to-image diffusion models with an ensemble of expert denoisers. arXiv preprint urXiv:2211.0133 2022.
Fan Bao, Chendong Xiang, Gang Yue, Guande He, Hongzhou Zhu, Kaiwen Zheng. Min Zhao, Shilong Liu, Yaole Wang, and Jun Zhu. Vidu: highly consistent, dynamic and skilled text-to- video generator with diffusion models. arXiv preprint M.XXiv:2005.4223:: 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1 2020.
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, 35:28266-28279, 2022.
Huiwen Chang, Han Zhang, Lu Jiang, Ce Liu, and William T Freeman. Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 11315-11325, 2022.
Hongrui Chen and Lexing Ying. Convergence analysis of discrete diffuusion model: Exact imple-
mentation through uniformization. arXiv preprint arXiv:2402.08095, 2024.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron Weiss, Mohammad Norouzi, and William Chan. Wave- grad: Estimating gradients for waveform generation. In International Conference on Learning Representations, 2021.
Ting Chen, Ruixiang Zhang, and Geoffrey Hinton. Analog bits: Generating discrete data using diffusion models with self-conditioning. arXiv preprint arXiv:2208 04202, 2022.
Zixiang Chen, Huizhuo Yuan, Yongqian Li, Yiwen Kou, Junkai Zhang, and Quanquan Gu. Fast sampling via de-randomization for discrete diffusion models. arXiv preprint arXiv:2312.09193, 2023.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers), pp. 4171 -17114 2019.
Prafulla Dhariwal and Alexander Quinn Nichol. Diffusion models beat GANs on image synthesis. In Advances in Neural Information Processing Systems, volume 34, pp. 8780-8794, 2021.
11

---

Published as a conference paper at ICLR 2025
Patrick Esser, Sumith Kulal, Andreas Blattmann, Rahim Entezari, Jonas Müller, Harry Saini, Yam Levi, Dominik Lorenz, Axel Sauer, Frederie Boesel, et al. Scaling rectified flow transformers for high-resolution image synthesis. In Forty-first International Conference Machine Learning, 2024.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-prees mask-predict: Parallel decoding of conditional masked language models. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNL.--ICNLPP),, pp. 61 111261221, 2019.
Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex. Openwebtext corpus. http: 2019.
//5kylion007. wtw.:oo0077.gittubb github..hh.....g. io/ wttp///peeeeeeeeeeoeooooeeo
Martin Gonzalez, Nelson Fernandez Pinto, Thuy Tran, Hatem Hajri, Nader Masmoudi, et al. Seeds: Exponential sde solvers for fast high-quality sampling from diffusion models. Advances in Neural Information Processing Systems, 36, 2024.
Emil Julius Gumbel. Les valeurs extrêmes des distributions statistiques. In Annales de l'institut Henri Poincaré, volume 5, pp. 115-158, 1935.
Emil Julius Gumbel. Statistical theory of extreme values and some practical applications: a series of lectures, volume 33. US Government Printing Office, 1954.
Agrim Gupta, Lijun Yu, Kihyuk Sohn, Xiuye Gu, Meera Hahn, Li Fei-Fei, Irfan Essa, Lu Jiang, and José Lezama. Photorealistic video generation with diffusion models. arXiv preprint arXiv:2312.0666 066662, 2023.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked au- toencoders are scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 16000-16009, 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pp. 6840-6851, 2020.
Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, et al. Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv: 10.02303, 2022.
Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. arXiv preprint arXiv:2110.02037, 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, 34:12444-12444 202
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax, arXiv preprint arXiv:1611.01 2016.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models. In Advances in Neural Information Processing Systems, 2022.
Frank P Kelly. Reversibility and stochastic networks. Cambridge University Press, 2011.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
Diederik P Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. In Advances in Neural Information Processing Systems, 2021.
Yaron Lipman, Ricky TQ Chen, Heli Ben- Gen-Hamu, Maximilian Nickel, and Matt Le. Flow matching for generative modeling. arXiv preprint arXiv:2210.027747 2022.
12

---

Published as a conference paper at ICLR 2025
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. arXiv preprint arXiv:2310.16834, 2023.
Cheng Lu, Kaiwen Zheng, Fan Bao. Jianfei Chen, Chongxuan Li, and Jun Zhu. Maximum likelihood training for score- based diffusion odes by high order denoising score matching. In International Conference Machine Learning, pp- 14429-14460. PMLR, 2022a.
Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm-solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps. In Advances in Neural Information Processing Systems, 2022b.
Chenlin Meng, Kristy Choi, Jiaming Song, and Stefano Ermon. Concrete score matching: General- ized score matching for discrete data. Advances in Neural Information Processing Systems, 35: 34532-34545, 2022.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference on Machine Learning, pp.
PMLR, 2021.
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. arXiv preprint arXivv24006.03736. 2024.
William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4195-4205, 2023..
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language under- standing by generative pre-training, 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Robin Rombach, Andreas Blattmann, Dominík Lorenz, Patrick Esser, and Björ Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. arXiv preprint arXiv:2406.07524, 2024.
Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis K Titsias, Simplified and gener- alized masked diffusion for discrete data, arXiv preprint arXiv:2406.0433 04329, 2024.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan. and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learn- ing. pp. 2256-2266662 PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Interna- lional Conference on Learning Representations, 2021a.
Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training score- based diffusion models. In Advances in Neural Information Processing Systems, volume 34, pp. 1415-1428, 2021b.
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021c.
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: En- hanced transformer with rotary position embedding. Neurocomputingg 568: 127063, 2024.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous- time discrete diffusion models. arXiv preprint arX1v22211.16750, 2022.
13

---

Published as a conference paper at ICLR 2025
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXhv:2302.13971, 20233
Benigno Uria, lain Murray, and Hugo Larochelle. A deep and tractable density estimator. In Inter- national 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 informa- tion processing systems, 30, 2017.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint ar XX1v:1804.00466 2018.
Donghha Yang. Jianwei Yu, Helin Wang, Wen Wang, Chao Weng, Yuexian Zou, and Dong Yu. Diffssund: Discrete diffusion model for text-to-sound generation. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 31:1720-1733, 2023.
Jintao Zhang, Haofeng Huang, Pengle Zhang, Jia Wei, Jun Zhu, and Jianfei Chen. Sageatten- tion2: Efficient attention with thorough outlier smoothing and per-thread int4 quantization. arXiv preprint arXiv:2411. 10958, 2024.
Jintao Zhang, Jia Wei, Pengle Zhang, Jun Zhu, and Jianfei Chen. Sageattention: Accurate 8-bit attention for plug-and-pe inference acceleration. In International Conference Learning Rep- resentations (ICLR), 2025a.
Jintao Zhang, Chendong Xiang, Haofeng Huang, Jia Wei, Haocheng Xi, Jun Zhu, and Jianfei Chen. Spargeattn: Accurate sparse attention accelerating any model inference. arXiv preprint M.Xiv:2502.181333 2025b.
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. In The Eleventh International Conference on Learning Representations, 2022.
Kaiwen Zheng, Cheng Lu, Jianfei Chen, and Jun Zhu. Dpm-solver-v3: Improved diffusion ode solver with empirical model statistics. In Thirty-seventh Conference Neural Information Pro- cessing Systems, 2023a.
Kaiwen Zheng, Cheng Lu, Jianfei Chen, and Jun Zhu. Improved techniques for maximum likelihood estimation for diffusion odes. In International Conference on Machine Learning, pp. 42363- 42389. PMLR, 2023b.
Kaiwen Zheng, Guande He, Jianfei Chen, Fan Bao, and Jun Zhu. Diffusion bridge implicit models. arXiv preprint a4Xiv:2405. 15885, 2024.
14

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
2
Background: Masked Diffusion Models (MDMs)
3
Revisiting the Training of MDMs
Reformulating the ELBO with the Number of Masked Tokens
3.2
Time-Independent Network Parameterization
3.3
Practical Considerations
4
Revisiting the Sampling of MDMs
Inefficiency of Current Sampling
4.2
First- Hitting Sampler
Parallel Decoding and High- Order Variants
Are MDMs Better than ARMs? Critical Fault Low- Precision Gumbel-Ban Cat-
egorical Sampling
5.1
Low Token Diversity under Numerous Sampling Steps
5.2
Identitying the Numerical Precision Problem
5.3
Categorical Sampling with Truncated Gumbel
6
Fair Evaluation of MDMs' Generation
6.1
Original Sampler v.s. First-Hitting Sampler
10
6.2
Trading Off Generative Perplexity and Entropy via Temperature
10
Conclusion
10
Notations and Definitions
16
Related Work
18
Proof
20
Proof of Proposition]
20
Proof of Proposition 3.2
21
Proof of Proposition
Proof of Proposition 5.2
23
D Relationship between Masked Diffusion Models and Previous Discrete Diffusion Mod- els
24
D.1
Discrete Diffusion via Continuous- Tiniinuuus-Timee Markov Chains
24
D.2 Score- Score-Entropy Discrete Diffusion (SEDD)
25
D.3 Connection between MDMs and SEDD Absorb
26
15

---

Published as a conference paper at ICLR 2025
D.3.1
Equivalence of Training
26
D.3.2
Equivalence of Sampling
27
Expected NFE in Batched Sampling Using the Caching Strategy
29
Brief Introduction to Gumbel Tricks
29
The Gumbel Distribution
30
F2
Gumbel-Max Trick
30
Gufmel-Softmax Distribution
30
Implementation Details
30
Algorithms
30
G.2
Low-Discres -ow-Discepancc Sampler
32
Experiment Details
32
Evaluation Metries
32
Model and Dataset Details
33
Training Details
33
H.4 Sampling Details
33
Old Version of the Introduction
34
Additional Results
34
Training Results
34
J.1.1
Comparison of Traiing Variants
34
J.1.2
Failed Training Attempts
35
J.2
Sampling Results
36
J.2.1
Comparison of High- Ordh-Order Variants
36
1.2.2
Impact of Numerical Precision on Our Sampler
37
J.3
Anaysis of the Efficiency Gain by Our Sampler
38
J.3.1 Examples of Generated Text
38
A NOTATIONS AND DEFINITIONS
Numbers and Arrays
16

---

Published as a conference paper at ICLR 2025
a
scalar representing discrete token
A vector representing a sequence of discrete tokens
e4)
The I-th element of x The state(s) at time
nn
The sequence with masked tokens
t
The continuous time
m
The mask token The number of masked tokens in a sequence
n
A matrix, where the (-th column represents the predicted transition prob- abilities at the 1-th position in a sequence
The (-th column of The class probabilities The i-th element of
The sequence length
N
The number of sampling steps The batch size
B
0
The neural network parameters
The first-hitting time
Loo
The continuous-timg NELBO loss for single token
c(L)
The continuous-time NELBO loss for sequence of length L
Sets
R
The set of real numbers
X
The discrete data space (vocabulary) {0, 1,..., m] where m the added mask token
m
The standard m-simplex {π 12 Em πI 1, 2 0}
Functions
Or
The pre-defined noise schedule, which is decreasing function of time The derivative of the noise schedule w.r.t. the time
a;
a aa)(a)
The inverse function of the noise schedule satisfying aa aa-+(())
62.9
The indicator function (1 when æ = y and O when x + y)
ex
The one-hot vector of the token
ue (xx t)
The network prediction given the sequence and the time f input
softmax(2)
The Softmax operation to transform logits into class probabilities
log μ
The clement-wise natural logarithm
N(x)
The function counting the number of masked tokens in the sequence
[
The size the vocabulary X
Distributions
17

---

Published as a conference paper at ICLR 2025
9
The continuous time forward process The discrete forward process
po
The parameterized reverse process
U(a,b)
The uniform distribution on the interval [a, 6]
B(a,b)
The Beta distribution with parameters a, b > 0
())
The standard Gumbel distribution
T9(0, 1, M)
The right-truncated standard Gumbel distribution with threshold M
Cat(T))
The categorical distribution over the class probabilities π
Abbreviations
MDMs
Masked Diffusion Models
ARMs
Auto-Regressive Models
(N)ELBO
(Negative) Evidence Lower Bound
NFE
The Number of Function Evaluations
PPL
Perplexity
Gen PPL
Generative Perplexity
B RELATED WORK
Discrete Diffusion Models Diffusion models originally built discrete-time continuous- space Markov chains with Gaussian transition kernels (Sohl-Dickstein et al. 2015 Ho et al.) 2020)) They later extended continuous time with the theory of stochastic processes and score match- ing (Song et al. 2021c).
Discrete diffusion models arise from similar contexts of Markov chains but with discrete data space (Soht-Dickstein et al., (2015) Hoogeboom et al. 2021b). D3PM (Austin et al. [022] con- siders discrete-time Markov chains with several types of transition matrices (uniform, absorbing, discretized Gaussian) and derives the discrete-time variational objective (or ELBO), which is fur- ther extended continuous-time Markov chain (CTMC) and the corresponding EL EL.OO( (Campbell
et al. 2022). They employ the peaattarramttrizzationn to learn the reverse density 201r-
Another line of work (Meng et al. 2022 Lou et al. 2023) argues that D3PM implicitly learns (=
the ratio of the marginal distributions (Z)) which referred to as the concrete score-a discrete analog to the score function in continuous diffusion. This ratio is proposed to be directly learned via a regression objective known as concrete score matching (Meng al. 2022], similar score
matching in continuous diffusion. However, this approach faces challenges in practice due to the
incompatibility of the L2 loss and the fact that the ratio
2x(2) must be positive. To address this
ge(2)
issue, SEDD (Lou et al. (203)) introduces the score entropy objective as theoretically more robust surrogate, which also connects the concrete score with the continuous-time ELBO.
Though SEDD considers two types of transitions (uniform, absorb), the absorbing case (masked diffusion) is much more performant in practice. It involves adding [MASK] token as the absorbing state and modeling the simple transitions between the mask state and unmasked states, akin to the mechanism of masked models. Recent studies (Shi et al., 2024 Sahoo et al., 2024) have further aligned the masked diffusion framework with continuous diffusion, resulting in simple and prin- cipled training and sampling recipes. This not only provides unified understanding of masked diffusion models but also enables both theoretical and empirical advancements through improved parameterization and engineering techniques. We mainly follow their framework in this work.
Masked Models and Order-Agnostic Auto-regressive Models Learning to reconstruct masked tokens (or patches) is an efficient self-super manner for both representation learning and gen- erative modeling. The masked modeling paradigm, originally introduced by BERT (Devlin al.
18

---

Published as a conference paper at ICLR 2025
2019), not initially designed for generative purposes. BERT masks a fixed portion (15%) of tokens at random 10] which supports representation learning and language understanding rather than generating text from scratch. Similarly, the masked autoencoder (MAE) (He et al. 2022) adopts this approach for image representation learning but employs a higher masked ratio (75%).
Masked models can be generative when trained on sequences with range of masked ratios. Mask- Predict (Ghazvininejad et al.] 2019) extends the number of masked tokens seen during training in BERT and uses the following objective to train a language generation model:
Lmask -B (m))(( (mo)
E eJa, log M4 (arm))
(13)
where p(n)) is the uniform distribution over the sequence length L. MaskGIT (Chang et al. 2022)
uses a similar objective for image generation, but selects the number of masked tokens n according
mask scheduling function (t): sample 24(0, 1), and set n = [T] Both
and MaskGIT generate samples by parallel decoding. Compared to MDMs, these methods have less
theoretical grounding in training and sampling. Specifically, there is no discussion of the ELBO (Eqn. (7) where the likelihood weighting is necessary. Nevertheless, discussed in Section 3.2 their objectives can still lead to the same optimal solution.
The ELBO of masked models is instead revealed in the context of order-agnostic auto-regressive models (Uria et al., 2014 Hoogeboom et al.] 2021a). They factorize the model distribution as
(o)) = Eg))(((L) === (a [(7) ( (((*)) in the style of ARMs, but with an additional expecta-
tion over the index permutation sampled from the uniform distribution on the set of L- L-permutations
Sr. By applying Jensen's 's inequality, the ELBO can be derived as:
log logoo()))) 2 (So)(())))
log (1 a (m)
((E)))
n=
(14)
Σ
Σ
Pogpo(ab
(k) 2
((<n))
n
kEO(2n)
(k) o( (<n)) (predicted data probability given known tokens) is an equivalent expres- Here log po p=( mi
sion for the cross-entropy term T
(k) (.) log (1) ( (=g(())) the cross-entropy extracts the wi -th ele- (b)
),(,), from the network prediction p4 (x (<=)))) as po (=0 |2g ( This can ment, Hg (ao
(k) a(<a))
tokens) is known and x ((2)) (the remaining L - n + tokens) is masked and to be predicted. The cross- cross-entropy loss is averaged over the masked positions. As the last L-n -n+ positions in a random permutation are equivalent to I, T--M n + 1 random positions without permutation, this ELBO is equivalent to the ELBO in Eqn. 77)
masked prediction where xi ((<n) (the first
be interpreted
Training and Sampling Improvements of Diffusion Models Since the inception of diffusion models (Ho et al., 2020 Song et al. 2021c). numerous efforts have been undertaken to enhance their performance, leading well-established training and sampling recipes.
Prevalent training improvements include designing noise schedules, modifying the parameterization and applying variance reduction techniques (Nichol & Dhariwal, 202T Kingma al., 2021). No- tably, flow matching (Lipman et al., (022) provides a theoretically equivalent variant of diffusion models by employing the straight-line diffusion paths and velocity parameterization. These tech- niques have been validated in likelihood training of diffusion models, achieving improved density estimation results on image benchmarks (Zheng et al. 2023b). The tfate-of-the-as image diffusion model, EDM (Karras al.) 2002), designs the parameterization according their proposed precon- ditioning and first principles, which is deeply connected to velocity parameterization (Zheng et al.) 20235). When targeted maximum likelihood training with the ELBO, instead of improving gen- eration quality (such as FID of generated images), the design space is relatively limited. This is also the case in discrete diffusion for text generation as the perplexity metric based on likelihood.
Training-free accelerations of diffusion sampling mainly focus on two aspects: reducing stochastic- ity in the sampling process and leveraging higher-order information. DDIM (Song al. 2021a),
10 More specifically, among the 15% tokens, 80% are replaced with the [MASK] token, 10% are replaced with random tokens, and 10% remain unchanged.
19

---

Published as a conference paper at ICLR 2025
along with the extension to diffusion bridges (Zheng al. 2024), generalizes the diffusion process to non-Markovian ones with lower levels of stochasticity, enabling faster sampling. Later works connect it to the probability flow ordinary differential equation (PF-ODE) formulations of diffu- sion models, and build dedicated high-order numerical differential equation solvers (Zhang & Chen 2022
Lu et al.
2022b ZZenng et al. 2023a Gonzalez et. 2024).
However, adapting these sampling recipes to discrete diffusion is not feasible, as the underlying evolution process of discrete data cannot be described by an ODE. Designing effective samplers for discrete diffusion requires specialized inspection of the reverse-time Markov chain. Previous works (Chen Ying 2024 Chen et al. (023) leverage the uniformization convert continuous- time Markov chains into discrete ones, while still requiring time discretizations or approximations of the transition time distribution. Our study is the first demonstrate that the transition time in MDMs can be sampled analytically without hyperparameter tuning approximation errors. Infrastructure improvements, such as quantized or sparse attention (Zhang al. 2025a b) 2024), can also be used to accelerate the inference of discrete diffusion models, which are beyond the scope of this work.
C PROOF
C.1 PROOF OF PROPOSITION 3.1
Proof. Denote n2 N (xx) the number of masked tokens time According to the forward process in Eqn. (I), each token is independently masked with a probability Czs, and ny follows the Binomial distribution BL,, 1 a4). The probability Prtobbbiliiyyyy mass function
(n,) = (1 az)) aa I. n2 = 0, L.
(15)
We can rearrange the sequence NELBO in Eqn. (6) as partition by the number masked tokens:
a
E (ma) Ereeg J log M4 (x t) dt
an
dl
Σ Enengo =m e To log up (x t) dt
Ep. ( (ann)0(ocll)
-
On
Σ
1
al
Pe (n (1))
Eneg fia =m =0
log Mg (cem b) dt
(16)
1 att
n=1
J0
(0)
B mm))
Enagan
c
fo' 1 -
o
pt (n(n) (n)
log po t)dt
time-related term
The time-related term can be further simplified as
a
pc(n)) log (u((xn.. l)dt
at
a
(1 -
(1--a)) aa k- log pa (Zn, t)
1
Ol.
a1
log pw t)dae a --n (1 ar)) 0-1
(17)
(1-a,) an)--aa at log po (x,,, t)da
(n 1)1(L n)! E,,, -BI. -(I. log uo a (ax)))
Pan-B(L-nti.n [log 1o (2 a (ax)))
:oog (x
which completes the proof.
20

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF PROPOSITION 3.2
Proof. We consider minimizing the sequence NELBO (Eqn. distribution go (2ro::
(6) under the expectation of the data
a' (o)(
min E 00 (mo) C(L)
1 at Be (zn))
Σ 1::e(0 =m
T log u6 (I), dt
0/2
(es)
Σ Rarl
ego log My ( 1) dt (18)
1 at
a' (2s))
Σ (::e (
[egg0 log m4 1 (1z4 1) dt
1- 04
The objective is aggregation of cross-entropy terms over different i, 1,, The global minimum achieved when each cross-entropy term is optimal:
(1) log M (xxz, t)
min (mole()) 0
(19)
Note that pgg softmax ( is a set of valid class probabilities that sum to 1, and Beg (mog) ax))
(1)
also sum to 1. Denote them as P and P respectively, we are essentially mini- mizing log DKL(P + H(P) 2 H(P., where D || -) is the Kullback-Leibh (KL) divergence and H.)) is the entropy. According to the property of KL divergence, the equality holds if and only if p = This implies that the optimal 0* satisfies
( Mgg (æx, (maaa() (20
(20)
This expression is similar continuous diffusion, where the optimal data predictor is pag (æ,, Eag (mo m.) [x)]. The key difference is that, the posterior (2))()))); in MDMs only depends on æ and is irrelevant to the time Denote n, as the number of masked tokens at time f, we have
90 (xoo 4o
(00 Ex, (o(20)) (2: En, qo (D B. (m,) ( 10 x [00]
(0 ) (m. ( (0(2)
(xx)
(21)
where Pe (ng) is distribution of n, at time t, and in is the discrete forward process that ran- domly masks tokens. As 2G is known, the number of masked tokens is fixed as N N(x,), and (x,10o 0 for n4 # (xx)). Therefore.
(2))
Cajs (z:)
(22)
Ex, (Nx:)))))
which completes the proof.
C.3 PROOF OF PROPOSITION 4.1
We first present a lemma that enables sequential sampling of order statistics and supports the recur- sive process for sampling the first hitting time.
Lemma C.1 (Uniform Distribution Conditioned on the Maximum). Suppose random variables W1, u2...., Un are independent samples from the uniform distribution (1 0) (0 > 0). Given the condition that max max(un, uu, ... Unn) the remaining variables u, (w; u) follow the distribution U(00u)) u).
Proof. Without loss of generality, we derive the conditional distribution of un. variables follow the same distribution due to symmetry. For x S y < 0, we have
Other remaining
zy" n-1
P(u1 & x, u. 9) P(u1 Ix, u2 S Sy... V....u, un S 3) = P(u S x)
P(u uu S y)
0n
2
(23)
21

---

Published as a conference paper at ICLR 2025
x²
P(un S v. S ylur u) P(u S x) P(u ,.... un 5 II
p(u S x)
(24)
fm
and
P(un = u)
1
n P(un + u)
(25)
n
Therefore,
P(u1 I x, S 1) P(u1 P(u x. <x,u5
P(u1 Ex.usulur # u)
P(u1 7 u)
(26)
ry 2-
1 x²
nm n- 0n n
By taking derivatives w.r.t x and y, we obtain the density p(u1 = I, = y/u1 # u) =
ny"-2
8"
Similarly, P(u S 3) = 3 and the density p(u y) = ny gm
Therefore
p(u1 = 2 y, # u) p(u1 x. u
y/un
+ u)
1
(27)
p(u
y
We conclude that 4n (u1 + u) follows a uniform distribution over the interval [0, u].
Then we prove Proposition below.
Proof. We first consider the case of single token undergoing the reverse process described in Eqn. (10). Starting from time t, when xy = m is the mask token, we denote T as the time at which and Iy # m). The transition time is a random variable, whose cumulative distribution function (CDF) is available:
the unmasking transition occurs (i.c., Zy+dtt
1- Q'
P(T S 5) = pa(x, = m De = m)
(28)
1 Oz
Therefore, using inverse transform sampling, T can be analytically sampled by (1) drawing ~ (0, 1), and (2) solving the equation I-a: u.
1-0,
Next, we consider the case of multiple tokens in sequence of length L. Thanks to the theoretical as- sumptions of MDMs, the transition times of different tokens are independent in the reverse process. However, to enable token-by-token decoding, we need to sample the L transition times in descend- > To- Starting from t = 1 with 0₁ O, each transition time 7 can
ing order, i.c., > TL-1 be sampled by drawing u ~ 24(0, 1) and solving 1 - a = u according to the single token case. In U(0)
order to sample sequentially, we are essentially drawing the order statistics u(L-1) of L independent uniform variables on [0, 1].
According to Lemma C.T this process can conducted in a recursive manner without sorting. Suppose there are currently remaining masked tokens, and the most recent unmasking occurred at time Tn. The transition time Tn corresponds to the n-th smallest uniform variable U(x) through the relation next order statistic ((--1)- By recursively applying Lemma C.1 we know that the remaining n smallest uniform variables follow the distribution (1, (n))). if not considering their relative order.
ar, ((n). To obtain the next transition time Tx-1, we need sample the
Furthermore, ((n-1): as the maximum of these n variables, has the CDF P(u(--1 S z)
x" and
can be sampled by solving Therefore, the next transition time Tn-1 satisfies
"[a-1)
Unz where un 21 1) (using inverse transform sampling).
1 Cr.-1 = ((--1) um) =(1 ar )un
(29)
which is equivalent to Eqn. 100 using the inverse noise schedule function Tn-1 = a aa
n
22

---

Published as a conference paper at ICLR 2025
C.4 PROOF OF PROPOSITION 5.2
Proof. The truncated standard Gumbel distribution (0, 1,M) has the probability density function
(PDF) and cumulative distribution function (CDF) defined as follows:
f(x) = f(x)
F(x) = min F(x)
F(M) IoSM
=mim
(30)
F(M)
where
f(x)= ((0)= F(x) =
(31)
are the PDF and CDF of the standard Gumbel distribution G(0, 1), and M is the right truncation
point. Suppose the class probabilities are sorted as π S ... S Tx. and denote for simplicity. conduct truncated Gumbel-base categorical sampling, i.i.d. samples {g: K are drawn from TG(0, 1, .). The resulting categorical probability of class n is
0, f, = log xr
P(argmax 0, + 9 = n) =
f(9) II k.
P(O + 9h S 0n + g)dg
f(g)
II F(e, + - -x
MM
6 Ke M
e -
min fe - ,e Pn- }dg
(32)
M
Ke-M
C a- e- --iun mintu 9g.Ar)
dg
Ke M
e 9 - ce- e -(-- dg
e
iml
where the integral has a closed-form solution by
A0
1e Ao 'g A +C
(33)
With this, Eqn. 32 can be further simplified to
P(argmaxx(O, O2 + 9,) n)
-EE -0 on 00 - -EE a4 -00 9i-
=6 Ke-M
(i-1)e- -M
Σx -0
Ex R-
-E -M
=e Ke-M M
6 9i-1
c (i-1)e-
(34)
Tn
Σk Tk
1=1
KK [K+I-i-
K+1
Eizi 32 c
Fi
Lk=t Th
Therefore, the original class probabilities { Jk are shifted to { if the Gumbel variables used categorical sampling are right-truncated to M. nT given by
DK 7,
M
(kt1-i-
_ 74 -M
96-1
T
ΣK T
(35)
K-i
>
(K-(i-1)
x 14-1
TT
Rmm Th
23

---

Published as a conference paper at ICLR 2025
We can verify that {Th 1==1
valid class probabilities that sum to 1:
K
K
K-
Ib-+t1
2
e
(K-
K
2 2
7--1
TT
Σk= n
==
n=1
K
K-i -- 4
M
xK m2 M [-
an
(36)
-k n
K
E
12
)
K K-
Σt= -
Σ
-i-1
-
i=1
eKK-K3e KY--M
MM
K c-M
where mo and (K- (k-1)) b O.
D RELATIONSHIP BETWEEN MASKED DIFFUSION MODELS AND PREVIOUS DISCRETE DIFFUSION MODELS
Our framework and notations are based on recent studies of MDMs Shi et al. 2024 Sahoo
(ct al. 2024), which offer a thcoretically simplified and empirically improved version of the best- performing absorbing case in discrete diffusion models (Austin al. 2021 Campbell et al. 2022 Lou et al. 2023). In this section, we present a summary some background information on pre- vious formulations: generative modeling of discrete data via continuous-ting Markov chains (Sec- tion D.I), robust and principled training and sampling with score parameterization (Section D.2 and their equivalence to MDMs (Section D.3
D.1 DISCRETE DIFFUSION VIA CONTINUOUS-TIME TIME MARKOV CIAIINS
Continuous-tims Markov chains (CTMCs) Anderson, 2012) are a fundamental concept in stochastic processes used to model systems that transition between discrete states continuously over time.
Forward Process Denote X' as the state space and X' state. The probability of tran- sitioning from one state x to another state & near time t is governed by the transition rate matrix Q. E | Specifically, denote Qr +) as the transition rate from x to d, the transition probability during small time interval At is
Ptta ($/z) = 6 +
((A)))
(37)
The off-diagonal elements Q+ (x. (ar + i)) are neg-negative, and the diagonal elements Q (2,, a:) = EEtz Qe(x, S O, ensuring that each row of Q. sums to zero (so that Pt does not gain or lose total mass). Equivalently, the transition rate can be defined by the transition probability as
Qe(2, = lim Pe+
(0|x) 82,8
(38)
20-0
At
Denote p. = {=))=)) as the marginal distributions of all states time t. and PA|s X[*|*|
the forward transition matrix from time time t satisfying (x) a (f).r) The Kol- mogorov forward (or Fokker-Planck) equations describe the evolution of both the marginals p. (starting from the data distribution) and the transition matrix Pape
dp: = P:Q: dt
dP dt
Pr
(39)
In practice, the forward process is designed to be simple degradation (Campbell et al. 2022 Lou
et al. 2023), such that p: approaches stationary distribution Plase that is easy sample from as t increases, akin to the Gaussian noising process in continuous diffusion. Specifically, the transition rate matrix Q is set ( where (!) is scalar noise schedule function and Q is constant
24

---

Published as a conference paper at ICLR 2025
matrix with low ranks. In this case, the transition matrix can be solved analytically as P.j. (((()))(()) where (()) = Sn a())dr. Common choices of Q (Lou et al.
2023 include:
0
0
0 -1
0
1
1 - N
Q
uniffrm
Q Rabsorb
(40)
0
-1 1
1- N
The former disturbs the data distribution into a uniform one, and the latter additionally adds [MASK] token as the absorbing state.
Time Reversal Similar to continuous diffusion, discrete diffusion defined above has a time rever-
sal (Klly 2011
Sun et al. 2022) described by the reverse transition rate matrix Q: which satisfies
Pr
Qe(2,
Qx
Pr (2)
(41)
Σntz xイス Q)(,,))
= x
The intractable ratio (. named concrete score iMen et al. 2022). acts as an analog to the score
p.lr) function (Song et al. 2021c in continuous diffusion. The reverse process can be described as
dp. = pp.Q.
dP ds
Q.
(42)
ds
which evolves backward in time with decreasing to and It is sufficient simulate the whole process as long as the concrete score, the only unknown term in Qt, is estimated.
D.2 SCORE- DISCRETE DIFFUSION (SEDD)
SEDD (Lou et al. and sampling of discrete diffusion models.
2023) provides principled, robust and scalable techniques for score-based training
Parameterization
SEDD parameterizes Pe (c sEx
prediction network sæ(x,t) E R to learn the We use sp(x, t)y to denote its y-th element.
unknown concrete score
Training Objective
SEDD proposes the diffusion weighted denoising score entropy (DWDSE)
objective to optimize (a,
(DWDSE(XO) = 1-" (
Σ Qi (#,, (Iz, 1), Pejo (6g xo) #egte
dt
(43)
Pejo (x,, xo)
blog + K(b), and K(b) = b bogg b is normalizing constant function that ensures [(a, b) > 0. Eqn. (43) not only admits the optimal solution as the concrete score, but also serves NELBO for discrete diffusion models by log p (2ra) S LDwDSE(Zn) + DKL (Pri(-(20)
where b)
|| Pbase), where Pbase is the stationary distribution when T + co.
Sampling Procedures Denote 8x(x)
as the ground-truth concrete score, and p((z) SEx
(c(
sx(2), its y-th element. We use (z) demonstrate the sampling process, while in practice is replaced with the learned score s0(2, l). SEDD offers two sampling procedures: Fuler sam- pling and analytic sampling with Tweedie r-Leppinng
Euler sampling applies the Euler discretization to the reverse process (Eqn. 42 producing a re- verse transition similar to the forward transition in Eqn. (37):
Euler Pajt
(1x) 6z,z, Qe(
(44)
25

---

Published as a conference paper at ICLR 2025
It can be expressed by the concrete score 8t
Faler (Iralar) = (t ()Qo (t)) Palt
Is + It
(45)
Evere Buler (ylar):
Je = 1t
The Euler sampling implicitly assumes constant reverse rate matrix Q, Q2 for E [s, producing approximation errors and even resulting in negative probabilities at X = Zt.
Tweedie r-leaping operates similarly the posterior sampling DDPM (Ho et al. 2020), by ana- lytically solving the posterior Pa (2g( given the ground-trute concrete score. Specifically,
Tweedie (x,, (xx) (assss Palt
(46)
P((ae)
Under the special choice Q: = ( described in the previous section, we have
(1(5(1)/(ra) (Pit)) Z0:ZE
= ((((()))(0)))
(47)
and
P=(x,) =(D)),, (piPiTH).
(48)
Therefore,
Twoedie (aceddiexssx1)) (xn()0e) (cl0(0)-(()))))
Pt
e(1010)-(())
Pale
Eastr (2s)
z
(49)
= -c(6(0)-0(01)
(1(())))((
Multi-Dimensional Case For token sequence E XL of length L, we use -l denote the indexes of all tokens except the 1-th one. The concrete score (x(x)) R x is defined between sequences that differ by Hamming distance of I:
(x)),, Pr( (xx)
S.L 500 (-1)) (-1)
(50)
The forward and reverse processes are factorized across dimensions the same manner as in MDMs described in the main text. The parameterized score network s,(x, t) R also predicts the scores at all positions at a time. Consequently, both the training and sampling are conducted simultaneously and independently for all dimensions, except that the network input æ contains the current sequence information.
D.3 CONNECTION BETWEEN MDMS AND SEDD ABSORB
The absorbing case (Q = aaborr) of discrete diffusion has demonstrated both simple formulations and superior performance. As revealed in previous and concurrent works (Shi et al. 2024 Ou al. 2024]. SEDD Absorb is theoretically equivalent to MDMs in multiple aspects. For simplicity, we Tocus the single-token case, the factorization approach used in both MDMs and SEDD Absorb ensures that equivalence in one dimension implies equivalence in multiple dimensions.
D.3.1 EQUIVALENCE OF TRAINING
Relation between Forward Processes The forward transition matrix of SEDD Absorb Pijo
Qattro It can be verified by mathematical induction that Q absorb = (-1)"-1a (1-1)>-QQaboor Qabsorb for any positive integer n. With this identity, Prjo can be simplified as
(t) Q
(+)(
P 0 2 (() abborb = I+
absorb
Qabsorb
M
k!
1=1
1=1
(51)
=I + (1 (1-c -0-0) Q
absorb
This is equivalent to the forward process (Fqn.
11) in MDMs with the relation 04 (t())
26

---

Published as a conference paper at ICLR 2025
For coherence, only need to consider the concrete score st (m) at m, since st (x))) for x o m can converted from We have (mm) by (x)) =+(m)x
Relation between Parameterizations
to denote the [MASK] token. We
(x(
(poP.
84 {m))
(52)
(m(m)
(o Prjo)
Substituting the expression of Pajo in Eqn.
51) into Eqn. 52
for I # m, we have
(poPao) Σ
p0(2o))po((()z)) (1 at)
Po(zo) = Oz
(53)
(m)))((m
(m)
(po
Σ
po(20)Puo(x(200) = po( = (x)pD(x)
(54)
(m)
{m)
and
(po (P00)
{m(m);
pz(
(Epor (eaod)
(55)
(1oP.
ai
Ot
This implies that the score parameterization related to the mean parameterization oe (x. 1) in MDMS (excluding the m-th dimension) by
at s0(2, () = 1 - p0(2 1)
(56)
Equivalence of ELBOs
Substituting this relation between sy and μe into the score entropy ob- we have
jective of SEDD (Eqn. 43
J E Eaixpe (((mm)
Peoo 2o)
(OWDSF(20)) =
Qu (z,
Sa (m,
Pejo (m
xo)
L ((t))zrnpia(t)))
8rim
Σ
(
at
uo (m, f)x 82,00
a+
dt
Cte
(57)
Observing that I(a, 0) = a.
Exfm uo(m, t) = 1, we have
Σ
ne (m, E Exrmo at
at
K
at
at
log
at
ua um 1)20)
+ 1 Ot
at
1)
(58)
ai
Ott
1
aFm
0t
log (m t)
att
Using of = -o (t)ar, the objective (DWDSE(f1o can be simplified to
LDWDSB(#0) = f'' (() 12r.m
at az
log no (m, Dzo dl
(59)
at -i-earppot-ee 10 log ua (2t, t) dt
1- 0t.
As log (2,, D).o and e. log (1 f) are equivalent expressions for the cross entropy, we con- clude that LDWDSE is equal to the NELBO for MDMs (Eqn. (5) when =
D.3.2 EQUIVALENCE OF SAMPLING
Euler Sampler and Tweedie --appnn Sampler in SEDD are equivalent in the absorbing case under the linear noise schedule o; e
-.
27

---

Published as a conference paper at ICLR 2025
On the one hand, the Euler sampler (Eqn.
45 with score parameterization network s6 is
(t (t) (Q (abborb)a... s0 ().,, 1 Eypere Pult (y/mz))
+ It Fg 2t
Buler (wa) Palt
(60)
When 2t, using the identities (2 t)r = 1 and Q absorbb) a. be simplified to
8m,n nn - 8 Sparze
Palt
Faler
can
[0, ((t
It +
Euler (x, Polt
(61)
9) (t)))
It m
When 2is Tiz, from Eqn. (56) know Exedl(m) so(m, Os T-ax
I-o. ExEX
Euler can be calculated as Hence, Pajt
1, 1
3t +
Euler (x,)(t)) =
a(t)e (t-a)
(62)
I-
3t m
Combining Eqn. (61 and Eqn. 62 the Euler sampler is simplified to
3t + m
Pst (xx
Euler
(xt)
(1 - (1) ()a,,
3t = m1 3s + m
(63)
1 ((t) 910 (e-))-s))
o(1)
3t = M, J. = m
On the other hand, the Tweedie r-Lepping sampler (Eqn.
49 is
Pat
Tweedle ( (ra|0;) = (e (0(0)))0()))))))
t)e
(64)
When Q absorb, similar to Eqn. 51 we have
e (00(1) I + (1 - - (1-e-(0(0~0())) Qahsorh
(65)
e (0(1)) -(5)) I + (1 (1)
Qabsorb
Using the identities so(I,t), = and (Qutmorb) 20,2e 6m Eza.ze have
(cl000)0(00)))
=dannte (1 (0-1(((()-0(9)) (Qabsorb),,s
(66)
(0(()))) Searer + (1 c ((())))_a(s)) 8 6m.
and
so(m, t)y somm 1)xr
(x, tm
Σ s0(x f)2
s0(x, 1)m se(m,t)m + Σ mEX)((m)
so t)x
at
BE
vEX
(67)
Therefore,
(so(2 t)e -(0(())
= = t)e, + (1 (1- (())-0())) (so (ooorr,))abbbbbbll aabeorb)),
= so 1)z, + ((())0(()) Σ so( f)x (Qabsort). 2
so (1 ((())
1)x, + 8rymm
- (10)(()))()))
Σ
so(we, 1).r
FEX
1 ((1)-(())
(()) so (0( + 8
so( f
(())
(68)
Substituting Eqn. (66) and Eqn. 688 into Eqn. (64), the Tweedie r r-Lppin sampler is simplified to
ò ((t)) a()) - 1) so(xe, t)
I, +
Palt
Tweedie (7c)
It = m, I + m
(69)
-000
1-p-x(35:
32 m, T, m
28

---

Published as a conference paper at ICLR 2025
Under the linear noise schedule, e e=((t) 1 have ((t) - logg[1 - and ((t) - ea(() Consequently, (t (t) = (()) 1, and the Euler sampler Eqn. (63 is the same as Tweedie r-Leaping sampler in Eqn. (69
Tweedie r-Leaping Sampler in SEDD and the Reverse Sampling Process in MDMs are equiv- alent in the absorbing case. By the relation a; = e e=((t) and se (z t)æ, = r-a; (z t) ( = m, F, + m., the Tweedie r-Leaping sampler in Eqn. (69) is converted to
8 82,
+ m
Paje
Tweedie (22)
(1 t)x,,
m, I +
(70)
02
1-ar"
It
m, J. = m
which is the same as the reverse process in MDMs (Eqn. (3)
E EXPECTED NFE IN BATCHED SAMPLING USING THE CACHING STRATEGY
Suppose the sampling is performed on timesteps 1 = iN + tx-1 + to 0. and denote Tt XL the concatenation of the batched sequences at time f. During the sampling step t, - 1-11, the NFE increases by when Tt;-1 1 # Ft,,, and remains the same otherwise. Therefore, the expected NFE (E-NFE) can be expressed by
N
N
N
E-NFE =
#m
E
T Tar,
Σ
(it # #x11,)
1=1
1=1
(71)
Σ 11 ( =..)))
Σ 1=1
1 P
( (1)
(1)
(1)
; 11 1,2, 1,,, 1.,,...,,BB ,L.)
1/-11 Fi,
As noted in the main text, an unmasked token will no longer change, and whether mask token will change during a sampling step is independent of the network output. Given that the reverse sampling process is factorized across dimensions, and the only interaction between dimensions is through the sequence- snquence-conditione network, which does not affect whether token will change, conclude that the events (x!4) = are independent for different Therefore, the probability
P [ =xt, 10,11 001-1122 1,2,.... BL) can be factorized as II P (ol =z(.) where
(((1)) 14-1 = =1(0) = (1(()) (1) Tt = m P p(((!! T = =m|r// (1) = m) + stz + m
(1
0tt 1 0/4i11 +
Cth
(72)
on 1 - 04;
1 a1
1 (ay; o4:)
The expected NFE is finally simplified to
N E-NFE- Σ
(1- (1-1,,, aa)) al))
BL)
(73)
Using the default linear noise schedule 0; 1 t as well as uniform timesteps t2 No we have att-- at, = n and the expected NFE is N - (1 B1).
F A BRIEF INTRODUCTION TO GUMBEL TRICKS
Gumbel tricks are widely used machine learning and statistics to handle the challenges associated with discrete random variables. Based on the properties of the Gumbel distribution, these techniques offer powerful tools for approximating discrete distributions and optimizing over discrete spaces, facilitating the integration of discrete variables into continuous models.
29

---

Published as a conference paper at ICLR 2025
F.1 THE GUMBEL DISTRIBUTION
The Gumbel distribution (Gumbel 1935 is related to the extreme value theory and is commonly used to model the distribution of the maximum of random variables. The Gumbel distribution (1,, 8), with the location parameter μ and the scale parameter 13, has the following PDF and CDF:
Fl: = e (2/0
fl; 3 (x-w)/B-e (x (e-e1/0
(74)
A widely used special case is the standard Gumbel distribution ( where μ 0 and 8 1. For this distribution, the CDF is given by P(g S x) e Using inverse transform sampling. random variable g following (0, 1) be sampled by drawing 2(0, 1) and performing two negative logarithm operations g = log(- - log u).
F.2 GUMBEL-MAX TRICK
The Gumbel-max trick (Gumbel 1954) allows to sample from categorical distribution using continuous random variables. It leverages the following property of the Gumbel distribution: for
(T1, T22 .... Tx) satisfying samples from ((0, 1), we have
0 and > क. > O, and let 9K be independent
max (9i + log TT) ~ 9 log Σ Te. 1
(75)
and
π
argmax (g. - logm, TT) ~ Cat
(76)
K
This implies that sampling discrete variable from a categorical distribution can be achieved by operating on continuous variables that include the known class probabilities and the sampled Gum- bel variables. Therefore, the Gumbel-max trick acts as the reparameterization trick for categorical sampling, akin to the Gaussian used in variational auto-encoders (Kingma & Welling 2014).
F.3 GUMBEL-SOFTMAX DISTRIBUTION
The Gumbel-Softmax distribution (Jang et al., 2016) introduces a differentiable approximation to the categorical distribution, facilitating gradient-based optimization in neural network training. smooths the non-differenee -in-differentiable ar argmax operation in the Gumbel-max trick by replacing it with the differentiable Softmax function plus a temperature factor T. Specifically, the one-hot random vector Cz2 where x ~ Cat(T), is approximated by continuous vector defined as
m 9:)
y/
clog (l t9,) 1,2, K f=1
(77)
approaches the one-hot representation of the categorical variable when T O, and tends to be uniform when + oc.
G IMPLEMENTATION DETAILS
G.1 ALGORITHMS
For parallel decoding, suppose the sampling step is N and the sequence length is L, we define decoding schedule [ which satisfies Σ Ln = to specify the number of tokens decoded each step. This includes the boken-by-token decoding In practice, we decode the same number of tokens per step so that L is divisible by N.
special case where N L and L,, 1.
We present the parallel decoding procedure in Algorithm which can be interpreted as first- order method. Algorithm 3 and Algorithm describe two types of high-order extensions, inspired by high-order numerical differential equation solvers in diffusion models. Algorithm leverages
30

---

ar,)) Published as a conference paper at ICLR 2025
Lagrange polynomials interpolate the previous network outputs along the time axis, yielding approximate network prediction for the current time step. Our implementation only uses the two most recent predictions, making it second-orde method, methods tend to degrade performance. Algorithm|4emmp emplooy a predictor-correcto approach, refining the first-order decoding result at the last step using the current network prediction, also resulting in a second-orde method. After refining the intermediate sample, we avoid feeding it back into the network for prediction updates, thus preventing extra NFEs.
empirically find that higher-order
First-Hitting Sampling of MDMs (parallel decoding) the sequence length L, the vocabulary X' = (O...., ..... m m) where is the mask token, the noise schedule a, and inverse function o -1, the pretrained masked diffusion model μeo the number of sampling steps N, the decoding schedule {Im])=]
Algorithm 2
Require:
I: æL f Im m m)
2: TL +
3: I I<L
4: for
to do for to L. do
6:
Sample it ~ ~M1 ( 1)
7:
7h-1 t a (1
8:
if then
9:
- [o( 7-1)
10:
end if
Randomly and uniformly select an index from ( x = m) (i.e., masked positions æ.))
12:
Ti-1 +- m. 2 +- x (a)(
13:
1+1-1
14:
end for
15:
end for
Output: T50
Algorithm 3 First-Hitting Sampling of MDMs (extrapolation)
Require: the sequence length L, the vocabulary X' (0.... ....... m) where is the mask token, the noise schedule ar and inverse function -1, the pretrained masked diffusion model μa. number of sampling steps N, the decoding schedule [
I: ær.
m ... m]
2: TL +-1
3: I --1 L
4: for +- N to do
5: for
to T.,, do
Sample ii ~ ~(10 1)
TI-1 f-aaaaa a a u1 1/1
(1 ))
8:
if then
9:
μ pa(x:, T2-) TL-
10:
end if
12:
if
then
13:
j ==
14:
else
A 7-1 7 7-1-7 7-
15:
1e
(Lagrange interpolation)
16:
end if
17:
Randomly and uniformly select an index & from [i -r{") = m) (i.e., masked positions in æi)
18:
#i-1 24, I +- (1))
(4)
19:
1+ 1
20:
end for
21:
Ā+
22:
7+*
23:
end for Output: Ro
31

---

Published as a conference paper at ICLR 2025
Algorithm 4 First-Hitting Sampling of MDMs (predictor-cortecttr)
the sequence length L. vocabulary = (O..... m m) where m the mask token, the noise schedule de and its inverse function 11 the pretrained masked diffusion model pe: the number sampling steps N, the decoding schedule [Tn Jm
Require:
I: æL -
(m m m)
2: TL f-
3: I / L
4: for 4- to do
for 1 to L. do
6:
Sample uj ~ -1, 1)
7:
71-1 - a a1
(1 a.,))
8:
if = then
9:
10:
n N then
at 6
12:
for r f- 1 to La+1 do
13:
Randomly and uniformly select an index from {j 20 m)
14:
2i
(k) <- a (a)(
15:
end for end if à
16:
18:
end
19:
Randomly and uniformly select an index & from (j : =, = m) (i.e., masked positions in æ!))
20:
2:-1 + D1, x (K) + x ~u (a)(
21:
1+1-1
22:
end for
23:
end
Output: T7
G.2 LOW-DISCREPANCY SAMPLER
VDM (Kingma et al. 2021) proposes low-discrepancy sampler for batched sampling of uniformly distributed continuous time variables, which reduces the loss variance in maximum likelihood train-
ing of diffusion models. Specifically, consider batch of B timesteps { B-)
== that needs to be sampled from ((, 1). Instead of sampling them independently, VDM generates correlated samples using the formula {()) = mod( un + i/B, 1), where up ~ ((, 1). This approach ensures that each (()) has the correct marginal distribution over multiple batches, while each batch timesteps more evenly covers the interval (0, 1].
MDLM Sahoo et al. 2024) employs a slightly different low bow-discrepancy sampler where the sam- pled timesteps less correlated within batch. Specifically, B independent uniform samples B-1 from ((( 1) mapped into B bins by +(0) (u, + i)/B. We adopt this approach for sampling continuous timesteps. Additionally, we extend this low-discrepancy sampler to handle dis- crete timesteps (n(() B-1 drawn from 2((0, I...., ., L 1}) (c.g., the number of masked tokens in
{u, 1==0
the discrete ELBO) by mapping the continuous time {(() to n = [Lt(
H EXPERIMENT DETAILS
H.1 EVALUATION METRICS
Perplexity a likelihood-related metric to evaluate how well likelihood model trained. Denote the likelihood (i.e., the probability of the data under the parameterized model) for the data
32

---

Published as a conference paper at ICLR 2025
point zo po())). The log- lilllikeiihodd can be expressed either exactly through an ELBO:
Auto-regressive Models:
logpo (2o)
log (2) a
(m) (())))
(78)
Σ E log po (.n)))
Masked Models:
log (2o)
Big of (ea)
(79)
n=1
Here express the log-likelihood of masked models with our derived discrete ELBO. We log (1 (xn) (predicted data probability given known tokens) as an alternative expression for the cross-entropy term e log M4 (ar,), aligning it with the common formulation in ARMs. The perplexity (PPL) is defined as:
P |- log po ( [3:
PPL exp
(80)
D
where is the data dimension, and Pdata is the data distribution (such as the validation/test set).
Generative Perplexity evaluates model's generation quality by measuring the perplexity of its generated samples under some off-the-shelf model. It is related to both training and sampling. We adopt GPT-2 Large the off-the-shed evaluator following previous works.
Entropy measures the diversity of tokens a sequence. For a sequence of length that contains K distinct tokens, with each token k occurring LA times, the entropy is computed as E where Pk:
k=1 Pk log Ph.
Lx/ represents the probability of occurrence of token kt.
H.2 MODEL AND DATASET DETAILS
Following SEDD (Lou et al. 2023 and MDLM (ahoo et al. 2024), we utilize an encoder-only transformer with DDIT (Peebles Xie 2023) architecture, incorporating RoPE (Su et al., 2024). We use the small-size model variant, which consists of 12 layers, 12 attention heads, hidden dimension of 768, and a timestep embedding dimension of 128, amounting to approximately 170M parameters including the word embedding matrix.
Our experiments are conducted on the Open dataset (Gokaslan et al. 2019), which contains around 8 million documents, with the last 100k reserved for validation. The dataset is tokenized using the GPT-2 tokenizer, resulting in a vocabulary size of 50,257 (excluding the mask token). Sequences are concatenated and wrapped between tokens concatenated sequences set to eos.
length of 1024 tokens, with the first, last, and in-
H.3 TRAINING DETAILS
the AdamW optimizer with a batch size of 512 and a learning rate that is linearly warmed up from 0 to 3e-4 over the first 2,500 steps. We apply a dropout rate of 0.1, clip the gradient norm I, and utilize an exponential moving average (EMA) with a rate of 0.9999. Mixed-precision training is enabled with of fflooale 6.
Following SEDD (Lou et al. 2023) and MDLM (Sahoo et al.) 2024),
All our training experiments are conducted on NVIDIA A100 40GB GPUs for slightly over 100k iterations, which takes around 1.5 days.
H.4 SAMPLING DETAILS
We directly use the pretrained models (AR, SEDD Absorb, MDLM) trained on Open WebTet pro- vided by MDLM These models share the same architecture and size (with the exception of the final layer in AR). SEDD and MDLLM are trained for 1M iterations, while the corresponding AR baseline is trained for half as many steps to ensure comparable number of tokens seen.
For the baselines, SEDD sampled using its analytic sampler (Tweedie 7-leaping). and MDLM is sampled both with and without the caching strategy. Their sampling timesteps are uniformly dis- cretized. In our first-hitting sampler, parallel decoding is achieved by unmasking the same number
httpps:////o thtp://gggtttttoett thub. com wwwpa//wwleshh-gggggee how..//mmmmieeeeeoo-oooomm/mm m/
33

---

Published as a conference paper at ICLR 2025
of tokens each step. Although the pretrained MDLM model is claimed to be time-independent, we find that adding the time condition slightly improves performance in our sampler. All sampling experiments conducted single NVIDIA RTX A6000 GPU, and the reported metrics are averaged on 64 random samples.
I OLD VERSION OF THE INTRODUCTION
We highlight our key findings: (1) MDMs, in both training and sampling, are essentially time- agnostic masked models (or order-agnostic auto-regressive models), enjoying 20x faster sampling and diverging from the design choices of diffusion models. This also justifies the theoretical foun- dation of masked models as they are equivalent and simpler formulations of the more principled MDMs. (2) We challenge previous claims that MDMs can surpass ARMs in text generation by identifying a hidden but critical numerical issue that reduces the token diversity and renders previous evaluations unfair. After fixing we find MDMs significantly lagging behind ARMs in generative perplexity.
For training, we prove that the continuous-time evidence lower bound (ELBO) objective of MDMs can be expressed by the number of masked tokens with an implicitly defined mixture-of-ccperts model. It provides a discrete ELBO for masked models and coincides with the ELBO previously derived for order-agnostic auto-regressive models (Uria et al. Hoogebbom et al. 2021a).
For sampling, by analytically sampling the time when any mask token is first unmasked, we pro- pose theoretically equivalent first-hitting sampler (FHS) to avoid most of the time-consuming categorical sampling and perform decoding token by token with no approximation errors. fur- ther extended to enable parallel decoding and incorporate high-order approximations, achieving x0x speedup compared to previous MDM sampling procedures. When the parameterized model independent of the time variable, recover the sampling of masked models.
For evaluation, we discover that while MDMs exhibit extremely low generative perplexity with numerous sampling steps, the generation quality is compromised by reduced token diversity. By ex- amining the numerical precision during sampling, we identify previously unrecognized issue with Gumbel-baset categorical sampling. Specifically, reducing the floating-point precision from 64-bit to 32-bit significantly truncates the Gumbel variables, which theoretically lowers the temperature and empirically improves the generative perplexity of pretrained models (Lou et al., 2023 Sahoo et al. 2024) from 126.1 11 to 31.24, but with a decreased sentence entropy from 5.66 to 5.17.
J ADDITIONAL RESULTS
J.1 TRAINING RESULTS
J.1.1 COMPARISON OF TRAINING VARIANTS
IB who screoacyy disc upancy
disrrra ELS0 we low discepancy
continusus E150 wis low discrpanky continacus EU5O wi tmmecndition discreca EL50
continuous EL8o AR
40
Velidrtion
30
20-
200.0
40000
60000
80000
150005
20000
43000
60000
80003
100000
Tra Trining Itarations
Training Berazions
(a) Training Loss
(b) Validation Perplexity
Figure 11: Comparison of training variants.
34

---

Published as a conference paper at ICLR 2025
We compare different training variants (continuous- independent network) of MDMs. By default, we condition the network on time for continuous time ELBO and on the masked ratio for discrete ELBO. We also apply the lowdiiscrepancy sampler de- scribed in Appendix G.2 Providing the network with extra conditions as auxiliary information may potentially facilitate the training process.
ELBO, time-conditioned/iime
As shown in Figure I1 all variants exhibit similar performance in both training and validation. Adding the time condition provides slight improvement over the time-independent network, and the discrete ELBO performs marginally worse than the continuous-time ELBO. However, these differences are negligible. The low-discrepancy sampler notably reduces the variance in training loss. though the validation perplexity curve remains relatively stable. likely due to the smoothing effect of the EMA. Nonetheless, MDMs still significantly lag behind the counterpart ARM.
J.1.2 FAILED TRAINING ATTEMPTS
Training MDMs with the ELBO is analogous to maximum likelihood training of diffusion mod- els (Song et al. 20211 Kingma et al. 2021 Lu et al. 2022a| Zheng et al., 2023b). Therefore, we borrow well-established techniques from the SOTA likelihood model i-DODE (Zheng al. 2023b)
within the diffusion literature, including velocity parameterization and variance reduction.
Flow Baaccinn/Precondiiionnngg Different parameterizations are theoretically equivalent but have distinct empirical implications in diffusion models. As an alternative data noise predic- tion, velocity parameterization has proven effective in the maximum likelihood training of diffusion models (Zheng et al. 2023b). It is also related to flow matching (Lipman al. 2022) and the pre- conditioning technique in EDM (Karras et al. 2022). As MDMs employ mean parameterization (or data prediction), exploring alternative parameterizzatins may enhance training performance.
In diffusion models, different parametcrizations can understood as expressing the mean prediction model 1so with a "sskppconnection" style preconditioning:
ne (a () = or Fe (a.,, 1) + b,2r
(81)
where at, by are some specific time-related coefficients, and Fg a free-form network. In MDMs, this general preconditioning can be formulated by the one-hot vector e.
(I,, t) = a.F (I,, t) + b,e_(0)
(82)
However, such a formulation MDMs makes no difference to the training. 14 (1) (It, 1) is only
trained when z (1) m to predict the data probabilities at dimensions 0 (which is 0 dimension ~ m - 1) to the model output does not impact the functional dimensions.
1. Adding e
To tackle this, we attempt to employ a self-conditioning technique (Chen et al. 2022
ne (x,, t) t) == F& (x,,,, t, Fg (xx,,)) t))
(83)
where 0- is the stop-gradient version of 0. For implemmentttio,, the extra condition Fg- (1) is con- catenated to the original input along the feature dimension (2) is replaced by blank with 50% prob- ability during training. and substituted by the earlier model prediction during inference. However, we empirically find this technique highly unstable during training, adding extra model parameters and incurring excessive training costs.
Variance Reduction via Importance Sampling The NELBO for both diffusion models and MDMs can be expressed as an expectation = E, [L,] over uniformly distributed I, where can be either continuous (c.g., the continuous time) or discrete (c.g., the discrete time or the number of masked tokens). Importance sampling (IS) for t can be introduced by rewriting the training loss with proposal distribution Pr:
Er-o, [2...
E,
C. Pt.
(84)
While the overall loss L remains invariant to the choice of pt, the variance of the loss, Var influenced by pt. We can optimize Pt for variance minimization. For continuous I, the density
E
35

---

Published as a conference paper at ICLR 2025
Scmoe EdR
6010
6000
20000
600.0
2010
2082
20030
P000
10000
(a) Training Loss
(b) Validation Perplexity
(c) Importance Weights
Figure 12: Variance reduction methods.
can be parameterized by monotonic neural network and learned by gradient descent (Kingma ct al. 2021 Zheng al. 2023b).
For simplicity, we instead consider the discrete case of (the number of masked tokens in the dis- crete BLBO). We adopt the adaptive IS proposed by Improved DDPM (Nichol Dhariwal 2021).
Specifically, Varz-pu [ = Ex-ps Ex-pa
23 L² the optimal pt is given by pt ε [C]). Given
that E [c]] is unknown in advance and may vary throughout training, we maintain history of the previous 10 values for each loss term and update this dynamically during training. At the beginning of training, we sample uniformly until we have samples for every f.
We visualize the training curves and optimized importance weights at around 100k iterations in Figure 12 Unfortunately, while the adaptive IS technique reduces the variance a level comparable to the low-discrepancy sampler, it also results in degraded performance. We hypothesize that the dynamical updated p. may make the loss estimator biased.
J.2
SAMPLING RESULTS
J.2.
COMPARISON OF HIGHI-ORDER VARIANTS
200
MOLM Setthitting ectopolation
MDLM
5.70
MDL M
MDLM
Big kitting extrandiation on
Big. Hitting
MDLM
fisthitting predictor comoctr
5.72
5.70
Oot PP
100
5.68
5.06
120
5.64
5.00
Sampling
Sampling
(4)
(a) Generative Perplexity
(b) Entropy
Figure 13: Comparisons high-order variants of the first-hitting sampler with steps E {32, 64, 128, 256, 512, 1024).
In Figure 13
we compare the two high-order variants of our proposed first-hitting sampler. In terms of the generative perplexity, The extrapolation strategy performs best when predictor-correctt strategy is more effective when 2 256. We also observe that lower generative perplexity is associated with decreased entropy, indicating inherent trade-off.
N 128. and the
36

---

Published as a conference paper at ICLR 2025
MOLM fint-hitting fnn-ordee (37-bx)
6.74
fisst (32.b))
MULM
Tist fist-hitting secondiorder (32
MOLM Som hirting secondonder (37-
MDLM 54
find-hiting fint-odter (64-bz)
672
Sre--hiiing (54-b2)
liting accond-order (64-bi)
MOLM Argt-itcing second-crde (64
100
5.70
Gel PML
Entrooe
5.08
1.0
5.50
120
5.54
5.00
Sampling Time Soquence (6)
Sampling Time/Sequence (4)
(a) Generative Perplexity
(b) Entropy
Figure 14: Impact of numerical precision the first-hitting sampler with steps N
{32, 64, 128, 256, 512, 1024].
Position
Position
remain Pt-1
Pi-yy
Equal probabiity of unmasking
π
M
M
Shifted
remain Pe-ws
romalnn
Pt-s
Unequal probability of unmasking
B
[M]
[M]
Figure 15: Illustration of prioritized unmasking.
J.2.2 IMPACT OF NUMERICAL PRECISION ON OUR SAMPLER
In Figure 14 examine the impact of numerical precision
first-hitting sampler by varying the floating-point precision in categorical sampling between 32-bit and 64-bit. For the high-order variants, we employ the extrapolation strategy when N 128 and the predictor-corrector strategy when N 2 256. In contrast to the observations under MDM's original sampler, the temperature- lowering effect of the numerical truncation significantly less influential under our sampler. No- tably, the 32-bit recond-orde first-hitting sampler even results in slightly higher entropy compared its 64-bit counterpart when N 512.
Why the numerical issue is not notable in token-by-token decoding With our first-hitting sam- pler, the inference MDMs becomes a token-by-token decoding process, except that the time variable is additionally handled. In this case, the numerical issue becomes negligible, and 32-bit floating-point precision appears sufficient. We also observe that ARMs, which also adopt token-by- token sampling strategy, do not suffer from numerical issues under 32-bit precision. This suggests that the numerical problem distinctive characteristic of the vanilla sampling process of MDMs (Eqn. (10)) thut performs inaccurate categoricul sampling simultaneously on all mask positions.
This phenomenon can be explained as follows. As justified theoretically in Section 5.3 the implica- tion of inaccurate categorical sampling includes two aspects: (1) semperature-lowrrinn effect for single token position and (2) prioritized unmasking for different positions (Figure 15). Both factors reduce the diversity and lower the entropy. However, when altering to token-by-token decoding, all remaining mask tokens have equal probability to first unmasked, and the diversity decrease be- comes less pronounced. This suggests that the prioritized unmasking caused by shifted probabilities at all individual positions is the major factor. This effect accumulates across numerous sampling steps, eventually leading notable diversity issues, under 32-bit floating-point precision.
37

---

Published as a conference paper at ICLR 2025
J.3 ANAYSIS OF THE EFFICIENCY GAIN BY OUR SAMPLER
Due to the theoretical equivalence between the FHS and the original MDM sampling procedure, the correctness of the FHS guaranteed and irrelevant vocabulary size sequence length. However, the efficiency gains (measured by inference wall-clock time) depend on several factors.
Let the sequence length be denoted number of sampling steps (for original MDM sampling) as N, the number of function evaluations NF F, and the number of categorical sampling operations as NCS. As stated in Section 4 our FHS reduces inference time by minimizing NCS. For original MDM sampling with the caching
vocabulary size as [V] (excluding the mask token), the
strategy, NFE= ((1 (1 "), NCS NL(V]. For the FHS, NCS L[V.. The total time cost can be expressed as NFE x ( NCS x l2, where
Li the time for one network call, influenced by model size.
l2 the time categorical sampling. averaged per position and class, which involves two logarithmic operations, and is fixed.
For fair comparison, we evaluate under the same NFE, ensuring similar generation quality. The inference time ratio between original MDM sampling and the FHS is (NFE t + NLLVV(t)) (NFF x 4 + (2)) Therefore, the FHS yields larger speedups under the following conditions:
Smaller Model Size: When the model is smaller, 4 decreases, making categorical sam- pling relatively expensive compared to network evaluation.
Higher values for these parameters increase NCS in original MDM sampling, amplifying the speedup provided by the FHS.
Larger NFE, L, [V:
Examples:
Paper Case: [V| 50,526, L 1024. To match the original MDM sampling N 10,000 steps. NFE = 973. The model size is approximately 600M parameters, with a time ratio of Lt = 1.56. In this case, the inference time ratio is around 17, corresponding to a 20x speedup. N = 2048, the ratio drops to around 5x.
DiffSound (Yang et al. 2023 : This model is 3x larger and uses a much smaller vocabu- lary. Specifically, L 265, V 256, with t1 L 14.6 1. Here, categorical sampling is much cheaper relative to network evaluations. Using fewer steps, N 100, results in NFF FF 93, and the speedup ratio is only around 1.07x.
J.3.1 EXAMPLES OF GENERATED TEXT
38

---

Published as a conference paper at ICLR 2025
</endoftext|> >> the new cars are crossovers. AT&T Insurance Marketing Manager, Megan Maxwell, tells us that Model X was 'reason- ably pricod, effective and inspires strong sentiment among consumers." " She says:
Our GM car for discussion is shown as part of our drive 20 percent around the world and even competitor. Our GM for discussion alt shows as one of our most popular cars in the world. We are in multiple countries introducing firmware for our new vehicles. While we are confident in our prices, we rely upon GM Auto's sales data and know we must adapt this process to meet the needs of all customers.
The proposed pricing is similar to that of the cheaper Range Rover and other cheaper sport utility vehicles, which are primarily offered through its dealerships. Alongside a Volt, Delphi XES includes a plug-in hybrid version called Volt Energy.
'Dynamic pricing is our way to deliver owners of more attractive or more reasonable out- comes or to find more marketable models that appeal to them more than their competitors, notes Maxwell.
Earlier this week, GM analyst Greg Clifford predicted that Intel Global Radical Charge Power Savings (STB) would start at $3,300 over the product lifecycle with an adoption rate of 50 percent by 2025. (eo5s_//nnofott/>TTT Weinstein Company tried to keep the Weinstein Company character Harvey Weinstein out of The Bourne Identity, but now that the character has been ousted the distributor has effectively banned him from the Middle East or North Africa, Caici International Union of Arabic and Al-Ahly Travel Negotiations president Shadi Hamid tweeted Thursday:
Warner Bros. foreign distribution arm The
A merciful Allah lifts my people wherever they are, provided that I am safe and secure. Shadi Hamid (@shadihamid) June 26, 2014
An anonymous official familiar with the matter tells The Hollywood Reporter that the tentative suspension of the sale was prompted by a request by Weinstein's Company that The Weinstein Company not use the #ourreCostabboo hashtag or its photo that appeared in the film. Weinstein's 's studio says he hasn't 't spoken with the history-making movic star after the film was relcased on Nov. 19 but that Trump's 's inauguration had somewhat diminished the company's image abroad. The wwirdngwinning film grossed more than $411 million globally.
EARLIER:
Original Screenplay for 'The Bourne Identity' Is Now Removed Grisly Official Appointments Express for Harvey Weinstein Probing
Bourne Identity Alleged Tarantino Power Grab Shot with $42 Million Spent on Hollywood
Update: is just re-issued The Weinstein Company ban shows nothing.
BREAKING: Mancini exits technicalities in Weinstein's 's sale of Leadville to Columbia pic dir. exec-to-branch.
Reginald Perag (@ReginaldCAeg) June 26, 2014 Leaked From Studio #BourneCostabook
came out with it after #Harvey Em Down.. (at/l//noofexx///ETVVVVe
FINALS: H. REILLARY KREATY & HARDBALL added extra 0.1 to final numbers. UNBELIEV- ABLE INJURY narrowly lost. 0.0 from last. night. NEW MIX TAPF (9P) +11.0, CNN NEWSROOM +10.6, LUTHER KING 5 +8.1, SOUTH PARK MIDDLE FIVE +2.4, DJ Khaled +2.2, WES CRAFT +1.6, HOUSE HUNTERS INTL AROUND FOOD +0.4, TEEN YEARS MOM 2015 +0.1, TINY HOUSE HUNTERS INTL +0.1, MLB TONIGHT +0.1, FLCL +0.0, SEUDAS FAMILY -0.3, ANZE +0.1, TEEN TITANS GO! +0.1. 10/24/15
Reginald Perag (RRegialdCAAe)) June 25,
-0.3 1.49 ANNCOUNTERS. BARRIERE Z PACK +0.1, NYXY +0.0, OTHER VIEWERS (-0.2) +1.0, A&E MOVIE FIXER UPPER -0.0 Broadcast Official Nationals Program Ratings Chart CABLE HIGHLGHTTS: UBS CELEBRATES THE DAY! CLOUD CROSSWITCH was at the top with dramatic 4.121, down 23% over last night (4/27), to #4. Football Night in America was #2 (and barely a night after ending), with TIZARD (2.092, 0.919), MASTERS OF KARMA (2.108, 0.914) and SOUTH
Figure 16: The counterpart ARM.
39

---

Published as a conference paper at ICLR 2025
</endoftext|> >> I was striking out, he got it the third out. know it wasn't really a catch there, but he didn't t consider that at all. knew what it wasn't about. We scored by one run, so it was a difficult thing for mc go to a "get-out," " but being on the board is not an casy fact. I knew it was in play, and went to the third out that it needed to be thrown to. I had nothing appeal that might not come back, and it was the only time he saw that al that moment. And so we continued.
say about it, and it was the only opportunity for me to get, to make an
"So we were sitting in the plus- flus-five--e five- plus- three-at-ninte night, because We were in pinch- hit early in the ninth. looked at a guy and was very nervous and confused, so when I looked at this man - I can't remember what he was doing, but to double dead- se the bases for sure like something had to be wrong with me, and he turned to me and told me, "that's as bad as the rest," " just like that "I bet!" I said calmly. "I bet," :" "Gotta do your best! Do not bet!" " "And when that happens, do you think can be won by one two runs?" He stood there and looked stunned. "You mean that?" "Yes, absolutely." " "Yeah, absolutely." "Well, that a message to you?"u And he looked back to me and said, "So we aren't going out?" "Well, yes," said me, "but I believe so believe." "I bet," " "Yeah, I bet, but when we'ee re on the board, how much time are we gonna lose?" " "Absolutely not." " "I bet," "all right. I'm not going out. It's me, understand." "I bet, believe not." "What happened?" "It happened!" "Did you hear clue?" "I said, "Oh, no! 1-1-1 heard that fifth-dinger Give me the clue!" The players, myself, and the "Man, Man, Man, it's just beyond hell!" murmurs of the players. At the same time, said, myself, "Young man, I've got to say - won't screw you right here." I went on, "You can take it. You're not going to lose." " I smiled. "You know what you got to admit to yoursell? This happened in baseball. I didn't screw you in baseball, it don't. matter, I'll screw you in a way." He took the fifth-dinger and said, "It's the end in baseball, it's the end." "That's correct!" I said, "Yes, you can't an't win in baseball," " I said. "But you're not winning in baseball." He turned me. "No, really, it's alright whether you't 're winning or not." - "I'm sure," he said. "Good money!" - I cut off. "You'n 'r not going to get this out. You do." Those were a fow words. As I were thnnknng, "What an enterprise."
up an inning.
said you'll be the first one up, then I'm out of the ballpark. I felt
"What are you in baseball?"
" "Ah, and it's a game, not a story and a number. If you believe the most in-the-30s stories www-be-dooe-a-cardiinee
are about the
t-they-gel-in story?" I said "suck," " and "We did stop listening to the number, and we had to come off with the number." "Exactly," " said Mike. < </endoftext|>
Figure 17: MDLM with the original sampler (32-bit), 50k steps.
40

---

Published as a conference paper at ICLR 2025
</endoftext/>> |>| know all about generators and that is one way to build an array.
def call () : # calls for (t.length, i) = 0: str += false ",t = (TController person.list
objects) func("call "arraalrlll"""""""""""""l"""ll"" .uro("))for a. = t.length: [T in t.T(n])): # def calls [a,n]: * str str32(T.setUscrrtt
for t & in i): str += str28(n = 1|n=i]# # put in a list of objects: t trre() call [T in T.Tin il array(t. if t.length: [T]i-=[): string d = t stracket3 = True, lake Atempls:: false): if hash = 0: print "failed" call r= slacktrace(): names t.names. relist (chisscc))))gg) def up(xx, mtr) p. stuff array. (x # So they should have this method def (i::(: return "x;0' .iitbbii) #3
e) [modify: True] larring
Mail.ilesPD..prinddee
'-/file) (piling:
Ok, now we want to create simple list. Try. It's just junk moves. This array can have all of the objocts arguments it packed in: [5].add( (instance.
new (instance (instance.new)) (instance (instance.new)) (con- new)) func R[ 3]
In our example, [1, 2]. 22 3, 4, and ... (0, 31', 42" lists contain more elements than in normal arrays and other complex types. It might be significant to say the list includes each engine constant size if it's not slow, but not if it contains no elements. To summarize, we get a list with 3 possible names and divide that list gradually between #3-4.
Now here's how we'll build an array with synthetic element references:
foo = Foo 3:3:4] } observe a variable from (func yout int y) -> nil do (apply (number of)) assert false if not true # make references for foo bar x (map (variable x y = let x x as par y x as par y)) (strip 'uoy) print ("fo bar foo')) " .'ddd bar "** "'.add (print foo')) }any.... observe a tuple from (func (func xs) -> nil do let.add = let clement if (clement == tuple/numberde
0): ".add(_ done if (done == 1) return 'doDone") ".add (f2.resolveffoo), "(What Why.bby , 'Callid somewhere?"). end (waffle(j1, ( of (Re()())))))))
met 'call)(' kilobyms aren't practical with these from a memory perspective. And don't 't ask at the very end where lines are the lowest line when they won't be allocated in memory.
(map? # add integers for Lua Lua? # do arithmetic for Emacs) end Lua? def x() # retrieve a++ list item (fune (func list)) -> nil do (for method "_of,, t) ia puts t'm "-L', (-L)))33) return nil def drop list #5
Added by clip:
Scratch
Now that you know it's adding elements moves again, a lot of other tricks are used in some Perl code. Common Lisp is the lone voice of the Emacs-Stuff should be careful just that Lisp is good and can help out, it is casier to make the code readable even than it is to express the tested is really pretty. Having lot of clause numbers is good enough. Still, you'll find difficulties in extracting and adding the references pretty amazing. You have to look at code get to work. Each line has introduce a name for each variable and its arguments. Combine the arguments with a,1,,,2,3,4,5 those argument arguments is called. When we are functional it's correct to pass in multiple elements from multiple lists:
changing this to one which
(x, d) lestoremove() d1 ... (0, 3, (10, 6, 12) (list(or, r))))function () is identical to the fine</endoftext]
Figure 18: MDLM with the original sampler (64-bit), 50k steps.
41

---

Published as a conference paper at ICLR 2025
</endoftext|> >> tough cases be property/private fields in Base class for example Class or with struct containing member.
-Loose the logic to possible the entry point a spocies troe:
class Terence = 'sum collections. coolections.crcate. prratt__specii treef Age Age(='ab")) # Adult;
Reward Class Pog::lopula ( ("Founded by:'). Biomeeri,, 'Nominal', PPossible inhabit:', Population', "'aiaa""""""""eee"")
To construct a family tree then uses join(members) creating a chain(MONS in a family tree)
Using (leach ( urn (urn_) multi-found 10..12 sequence heads 'Master": 'Maiar': (any mem- ber)? 'M'; members-BBB "BrmbbeesBBBB/AArffeem(pp333 col'y?': export_to<taale to<tablee>>> 12, 'BCG or Un- right'= ("some point: NUMEGatsL') -> X? 'B'; return unright; 1, 0, 3)))) Imple via Funrophy... What we need is our Fugai. Can create tree class that knows couple other methods or the interface and generate its message. That's 's the point. Generate members are using they are ordered in tuple as a of> from>, so that user will be told member entries:
Garage: by an 'H': This #grouup belongs to all mothers. Martin being an infant Martin join (oimmmeeerss)
Slimming the tree
it might look like this:
// Dont break the interface for the popular io servere and DoNot using iauto import strings = new System. werageeeeaaaeer((>>>> 'strings") case latermy new System. geraatmmteer auto) (rest i)
= 0) case latermy new Dystem.getPParmmete
Left String, Group Deleted, Advanced
Identity collection removed because the collection was updated in memory. Its correctness algorithm is to automatically append the family membership:
find(my)= = SaammSSyyymaaaaa
.iind (oddidieees") $ Member
To construct a separate one, say it wants to extract the locations of the following:
struct aity == behavior.shallow(... (haallo(locaaton] (location) (object) any : implicit struet Aggido = this. cre- ato(" Addons") => mmplciit.add"")
You can create the following manifest (RunninSSpparatiee relation:
You should be able to embed an Aggido rule in the Image of the JSONs until You are Aggido queries in json format. Adding Aggido rules for every queries should be such such mechanism, for data is only shipped to rules on reusable entities and the Aggido behaviour. Aggido application needs not register and read. Translation
So now, we have the # required fields, default priority and timestamp. Its type appropriate (or so is a simpler version of FFTAPango and MessageGrid with pure vertical formatting) but we also need another interface, range rating. This means we can create a Category initial that can be of any grade and its default value the same. FFTAPango also allows us to combine use of two content names. For example:
public w ('nggyyes.tur txt')) dolff$$gnatureaassstannnn .get now...,.... dolf == 'heading' p.s (0,_ 'Fuh.) ) p.as low(O,, "dogs ; ", 1.2. 1000'; end addc__f('22.5 0.9, ", 'Content') The simplified FFTAPang that follows has to be named as a tmuple with rvalue or an Array() after the oui' extension at class level:
public string name var nameeme = Long('faju') p.update p.update_tofuamee,
to(name, 'Single Timothy')
p.as right (name,, "The British', V, 0, V 0, 0.7")
Text expression with a .... parameter be used to generate list-expression for the word the following but SQLite syntax is following: Select
column. It follows the same interface a 'word with an Aff' of x class on the top of the x indicate a particular word in the selected word. list expression h[xx, Long['job Ronujjovaemmvll'" 'M..gainfree)..
If named as "wordcolumn" the following image follows:
public string p Vector. Word<letter>> let t; // the second key p. vaalles(("a', like w', t', 'Even though;; p.split("A A better, english", Association of ',, 0, 0.7; end pl pl'word < endoff text|>
Figure 19: MDLM with our first-hitting predictor-correcnt sampler, 1024 steps.
42


Reviews:
[{"review_id": "KvWZIGZf6l", "reviewer": "Reviewer_nW6z", "summary": "This paper has two primary objectives. First, it draws a connection between masked diffusion models and time-agnostic; second, the paper examines various strategies for diffusion model training and examines implications of their choices (in particular, caching, samping techniques, and choice of floating point precision).", "questions": "What do you think is the reason that \"we find the truncation under 32-bit precision not influential in the token-by-token decoding process of ARMs.\"?\n\nIf float32 truncation effectively reduces the temperature of the Gumbel, would comparisons between appropriately temperature set ARM and MDM models be fair?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "There are aspects of the paper I perceive to be strengths. \n\nFor example, empirical evaluations seem by and large well-designed. \n\nThe writing is clear; points are argued; there seem to be extensive details in the Appendices.", "weaknesses": "There are aspects of the paper I perceive to be weaknesses, or at least invitations for further discussion. \n\nParts of the text read more like a text book - useful, but I am left wanting to see the implications drawn out. For example, some claims could be elaborated upon, and might be hard for readers to get. For example, the mixture of experts claims on p. 4 has significance not clearly outlined (why does the observation matter, other than as an observation?). \n\nThe paper is also not particularly \"tight\" in the sense of capturing one primary contribution. It is an investigation into a range of phenomena associated with the training of masked diffusion models. The investigation is also very different in its theoretical exploration and its empirical exploration (with the two not really depending on each other much, at least in the float32 discussion). This might make the paper's contribution a bit difficult for readers to find or grasp. \n\nBecause at least a part of the paper's contributions are about numerical issues, some experiments about how the resulting issues affect performance in programs with other backends could be instructive for the reader (e.g., JAX, MLX). Some of the numerical precision analysis is of course theoretical but the interaction of the multiple layers of approximation and discretization could play out very differently in different settings. \n\nOverall, the work appears solid, but is seems to be weakened by what could seen as lack of connection between different parts of the paper.", "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": "8HNcnzpwmK", "reviewer": "Reviewer_Z3xj", "summary": "In this paper, the authors revealed theoretical essence of MDMs, including: 1) MDMs, in both training and sampling, are essentially time-agnostic masked models. 2) MDMs could be significantly lagging behind ARMs in generative perplexity.", "questions": "1.\tHave you considered modifications to the model architecture that might help close the performance gap with ARMS?\n2.\tWill MDM outperform ARMs on other discrete data like music generation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.\tThe paper provides a comprehensive theoretical analysis of Masked Diffusion Models (MDMs), revealing that both their training and sampling processes are effectively time-agnostic and equivalent to masked models. The theory is novel.\n2.\tThe authors introduce the First-Hitting Sampler, a novel sampling method that is theoretically equivalent to the original MDM sampling process but significantly more efficient, enhancing MDM's computational efficiency.\n3.\tThe structure of the article is well organized, with detailed proofs and a thorough analysis of the core ideas.", "weaknesses": "1.\tThe paper shows that MDMs do not outperform ARMs in text generation. It would be beneficial to propose improvements for MDMs.\n2.\tThe experiments are only conducted on text generation; more discrete data generation should be considered. Image generation could also be extended to discrete diffusion models and other discrete data like music generation.", "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": "isajTiUQJt", "reviewer": "Reviewer_KDgp", "summary": "This work provides a deeper understanding of the recently proposed masked diffusion models for discrete generation. It reveals three issues regarding MDM:\n\n1. A key issue is that MDMs's training is free of the time variable and likely learns as time-agnostic masked models. The NELBO objective for training can be reparametrized as time-independent. According to proposition 3.2, the optimal MDM is irrelevant to time. I did not check the seemingly correct proof in detail, but this could be a valuable observation regarding the limitations of MDMs.\n\n2. The sota sampling strategies are time-consuming. Instead, this paper proposes a first-hitting sampler that can achieve better efficiency.\n\n3. There is a numerical fault regarding the 32-bit Gumbel sampling, causing the previous evaluations to be unfair (positively biased) for the MDM. This work offers a fair evaluation and reveals that MDM cannot effectively model discrete generations, such as texts, compared to autoregressive models.\n\nDisclaimer: My review may change if other reviewers identify any problematic issues in the proofs and I have validated them.", "questions": "1. Can you comment on the limitations of this research and its potential impact on society as well as the research community?\n\n2. Is it possible to mitigate the time-agnostic issue by re-designing or regulating the training objective?\n\nI think this paper offers adequate and solid theoretical insights, and I am inclined to give it a rating of 8. However, I am not entirely confident and would appreciate it if you could address the weaknesses I have mentioned. Thank you.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Novel and recent research problem. MDMs have become popular since 2023, but the theoretical foundations are relatively overlooked. This paper presents key theoretical insights regarding the training and sampling of MDMs.\n\nTechnically solid claims and high potential impact. The proofs in the appendix look good to me. The parametrization of training MDMs using NELBO objective to be time-agnostic could facilitate further research on the fundamentals of MDMs.\n\nSome of the claims are validated with experiment results on the main pages, and a re-evaluation of MDMs is presented.", "weaknesses": "As there are multiple claims and they seem to be disconnected, I felt it hard to follow sometimes, especially when the topic shifts from training to sampling. As there is much content presented in this paper, I would suggest having a paragraph in the introduction commenting on the organization and flow of this paper. \n\nThis paper does not offer detailed experimental validation of the proposed first-hitting sampler compared to existing sampling strategies, like the mentioned works on caching strategies, line 263.\n\nMaybe more experiments can be conducted on the generation quality of different MDM training strategies in Appendix I.2.3, but using the same prompts rather than the current version. Additionally, there seems to be no analysis with a link to I.2.3 anywhere in the main texts or appendix.\n\nI have no idea how to reproduce the results from the paper, and I don't see any supplementary material.\n\nMinor: \n1. Figure 1 is a bit ambiguous. You prove MDM = Masked Model, but MDM falls into the Discrete Diffusion region.\n2. I was confused when looking at the title. The \"Secretly\" in this paper title actually marks a negative result on MDM, but for the reader who knows the source from the DPO paper last year [1], it is easy for them to interpret it as a positive result. Additionally, the numerical fault is not included. I cannot come up with any better candidate, to be honest, but I would suggest reconsidering the paper title.\n\n[1] Direct Preference Optimization: Your Language Model is Secretly a Reward Model. NeurIPS 2023.", "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": "1pPgVUJ6YC", "reviewer": "Reviewer_o25N", "summary": "The paper investigates Masked Diffusion Models (MDMs), which have gained popularity for discrete generative tasks, particularly for language modeling, where they are now competitive with auto-regressive models (ARMs). Recent work has simplified MDMs by aligning them with continuous-space diffusion models, improving training and sampling strategies. However, the authors reveal a key insight: MDMs’ training and sampling processes do not fundamentally rely on time variables (a typical diffusion model feature) and are instead equivalent to masked models. This finding is illustrated through their proposed \"first-hitting sampler\" (FHS), which mirrors MDMs' original sampling process but is up to 20 times faster by avoiding time-intensive categorical sampling.\n\nThe paper also challenges the assumption that MDMs outperform ARMs in text generation. It identifies a numerical limitation, even with 32-bit floating-point precision, that leads to inaccurate categorical sampling. This flaw reduces the effective temperature, thereby lowering token diversity in generated text. Consequently, the authors suggest that previous quality evaluations using perplexity metrics alone may not accurately reflect MDMs' performance.", "questions": "1.Could the authors provide additional insight into how MDMs might perform in non-text generation tasks, specifically in visual or audio data domains?\n2.How sensitive is the First-Hitting Sampler to different vocabulary sizes or sequence lengths? Would the efficiency gains remain consistent across a wider range of data?\n3.Are there scenarios where 32-bit sampling could be advantageous, considering computational resources, or is 64-bit sampling universally superior for maintaining token diversity?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.The paper uncovers MDMs' time-agnostic properties, showing they align closely with masked models, simplifying their conceptual and practical applications.\n2.The First-Hitting Sampler (FHS) reduces categorical sampling inefficiencies, achieving a 20x speedup, beneficial for real-time applications.\n3.Addressing the 32-bit Gumbel sampling precision issue highlights the authors’ rigor, demonstrating 64-bit sampling better preserves entropy and token diversity.\n4.Standardizing precision and sampling provides a fair comparison with ARMs, challenging prior MDM superiority claims in generative tasks.", "weaknesses": "1.While the authors advocate for MDMs' applications in order-agnostic settings, their comparative analysis still favors ARMs in text generation tasks, possibly limiting the generalizability of the claims for broader applications.\n2.The proposed First-Hitting Sampler and high-order sampling extensions add a layer of complexity that might limit accessibility for practitioners less versed in advanced diffusion techniques\n3.The experiments primarily focus on language tasks and lack extensive cross-domain testing (e.g., images, audio), where MDMs might exhibit different performance dynamics, which limits the scope of applicability", "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 (Poster)