A Continuous Time Framework for Discrete Denoising Models
Authors: Andrew Campbell
Joe Benton
Valentin De Bortoli
Tom Rainforth
George Deligiannidis
Arnaud Doucet
Venue: NeurIPS 2022 Accept (2022)
Keywords: diffusion
score-based
score
markov chain
markov
continuous time

Abstract: We provide the first complete continuous time framework for denoising diffusion models of discrete data. This is achieved by formulating the forward noising process and corresponding reverse time generative process as Continuous Time Markov Chains (CTMCs). The model can be efficiently trained using a continuous time version of the ELBO. We simulate the high dimensional CTMC using techniques developed in chemical physics and exploit our continuous time framework to derive high performance samplers that we show can outperform discrete time methods for discrete data. The continuous time treatment also enables us to derive a novel theoretical result bounding the error between the generated sample distribution and the true data distribution.

A Continuous Time Framework for Discrete Denoising Models
Andrew Campbell'
Joe Benton'
Valentin De Bortoli²
Tom Rainforth"
George Deligiannidis'
Arnaud Doucet
Department of Statistics, University of Oxford, UK {campbell, benton, rainforth, deligian, doucet) doucet)@stats. @stttstttss......... ox. uk
CNRS ENS Ulm, Paris, France
valentin. doantin.dbbrrto1ggmail...
Abstract
We provide the first complete continuous time framework for denoising diffusion models of discrete data. This achieved by formulating the forward noising process and corresponding reverse time generative process Continuous Time Markov Chains (CTMCs). The model can be efficiently trained using a continuous time version of the ELBO. We simulate the high dimensional CTMC using techniques developed in chemical physics and exploit our continuous time framework to derive high performance samplers that show for discrete data. The continuous time treatment also enables us to derive a novel theoretical result bounding the error between the generated sample distribution and the true data distribution.
outperform discrete time methods
Introduction
are a popular class of generative models that achieve state-of-the-art sample quality with good coverage the data distribution all whilst using stable, non-adversarial, simple to implement training objective. The general framework is define forward noising process that takes in data and gradually corrupts it until the data distribution is transformed into simple distribution that is easy to sample. The model then learns to reverse this process by learning the logarithmic gradient of the noised marginal distributions known as the score.
bww.d//eodddddnggggggg......aag. models 1 2 3
Most previous work on denoising models operates on continuous state space. However, there are many problems for which the data we would like to model is discrete. This occurs, for example, in text, segmentation maps, categorical features, discrete latent spaces, and the direct 8-bit representation of images. Previous work has tried realize the benefits of the denoising framework on discrete data problems, with promising initial results 6 7
12 13
All of these previous approaches train and sample the model in discrete time. Unfortunately, working in discrete time has notable drawbacks. It generally forces the user to pick a partition of the process at training time and the model only learns denoise at these fixed time points. Due the fixed partition, we are then limited to simple ancestral sampling strategy. In continuous time, the model instead learns to denoise for any arbitrary time point in the process. This complete specification of the reverse process enables much greater flexibility in defining the reverse sampling scheme. For example, in continuous state spaces, continuous time samplers that greatly reduce the sampling time have been devised [14] 15] [6] [7] as well as ones that improve sample quality [8]. The continuous time interpretation has also enabled the derivation of interesting theoretical properties such as error bounds 19 in continuous state spaces.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Discrete Data
Denoising Network
t=
t=0
A. A,A,
Generative process
Noising process
atate change
R
p ( (x))
oceur at any
Noise
Figure 1: The forward noising process corrupts data according to R₁, the rate of corruption events at time t. The noising process' time reversal gives the generative process which is defined through Re, the rate of generative events at time 1. fřद is parameterized through the denoising network, P (z)) which outputs categorical probabilities over clean To values conditioned on a noisy Zt.
To allow these benefits to be exploited for discrete state spaces as well, we formulate a continuous time framework for discrete denoising models. Specifically, our contributions are as follows. We formulate the forward noising process as Continuous Time Markov Chain (CTMC) and identify the generative CTMC that is the time-reversal of this process. We then bound the log likelihood of the generated data distribution, giving a continuous time equivalent of the ELBO that can be used for efficient training of parametric approximation to the true generative reverse process. To efficiently simulate the parametric reverse process, we leverage tau-leaping [20] and propose a novel predictor-corrector type scheme that can be used improve simulation accuracy. The continuous time framework allows us to derive a bound on the error between the true data distribution and the samples generated from the approximate reverse process simulated with tau-leaping. Finally, we demonstrate our proposed method on the generative modeling of images from the CIFAR-I0 10 dataset and monophonic music sequences. Notably, we find our tau-leaping with predictor-corrector sampler can provide higher quality CIFAR 10 samples than previous discrete time discrete state approaches, further closing the performance gap between when images are modeled as discrete data or as continuous data.
Proof' for all propositions and theorems are given in the Appendix.
2 Background on Discrete Denoising Models
In the discrete time, discrete state space case, we aim to model discrete data do E X with finite cardinality 5 = |. We assume Pg ~ (Faa( for some discrete data distribution (daa(Fo). We define a forward noising process that transforms (ro)) to some distribution qk (xx) that closely approximates easy sample distribution K)). This is done by defining forward kernels 0c+1|K (I++1 (ar) that all admit Pref as stationary distribution and mix reasonably quickly. For
example, one can use a simple uniform kernel 6 X 4s+11kk ( 1 = 6rn, 1. (1 3) + (1 S (S 1) where is Kronecker delta. The corresponding Pref is the uniform distribution over all states. Other choices include: an absorbing state kernel-wher where for each state there is a small probability that transitions to some absorbing state- or discretized Gaussian serel-wwher only transitions to nearby states have significant probability (valid for spaces with ordinal structure)
After defining Qa++1 [k: have forward joint decomposition follows
go: (xo:K) = Paata (To) I
K
9k+ (**+1/<2))
The joint distribution qu:k (Ro.k) also admits a reverse decomposition:
go:k (To:K) = qK (Ix) I 1 (1 (m=) where (1144((A||T44))) 9h (x (ms)gu
(
Here qu (xx) denotes the marginal of qo:k (mo:)) at time k. If one had access to guj4+1 and could sample (K exactly, then samples from (xa could be produced by first sampling ax ~ qk ( and then ancestrally sampling the reverse kernels, i.c 2g gu (+/24+1).

---

However, in practice, 9c|k+1 is intractable and needs to be approximated with parametric reverse kernel, PoJK+1 This kernel is commonly defined through the analytic 00jk+1,0 distribution and parametric "denoising' model Poju+1
6 g
1 (1+) _ E 1 3o Po ( (x++1))+))
(1o( = Eno (=110[FA+1 (e0 Pojx: Poj (2o(
Though qK (x is also intractable, for large K we can reliably approximate it with Pre((TK). Note that the faster the transitions mix, the more accurate this approximation becomes. Approximate samples from Pdata (To) can then be obtained by sampling the generative joint distribution
Po.k (To:k) (x IL P P (2uk [T+++))
where B is trained through minimizing the negative discrete time (DT) ELBO which is an upper bound on the negative model oollieelihood
E ppan (zo) [- log (zro]] y (so.))
Po (F [- log 91:Kjo((1:xx
CDT(
was shown in that LDT can be re-written as Cor (0) (#0) (lL(oo] (P))lP))((KK))
E (o logr8) (2ro)=1)
K- + + B (1o(
KL (0 20) (xx
where KL is the Kullback-Leibler divergence. The forward kernels q++1/k chosen such that (2o) can be computed efficiently in time independent of k. With this, can be efficiently trained by taking a random selection of terms from Lor in each minibatch and performing a stochastic gradient step.
3 Continuous Time Framework
3.1 Forward process and its time reversal
Our method is built upon a continuous time process from / = 0 to 1. T. State transitions can occur any time during this process as opposed the discrete time case where transitions only occur when one of the finite number of transition kernels is applied (see Figure 1 This process is known as Continuous Time Markov Chain (CTMC), we provide a short overview of CTMCs in Appendix [A] for completeness. Giving an intuitive introduction here, can define a CTMC through initial distribution qo and a transition rate matrix R, E S If the current state is 5. then the transition rate matrix entry R2 (ū, æ) is the instantaneous rate (occurrences per unit time) at which state transitions to state r. Loosely speaking, the next state in the process will likely be one for which R2 xx) is high, and furthermore, the higher the rate is, the less time it will take for this transition to occur.
turns out that the transition rate, R,, also defines the infinitesimal transition probability for the process between the two time points At and f.
Gr|r-ax AI- (x) = 6,,8 Re(2,z)At o(At).
where (At) represents terms that tend to zero at a faster rate than At. Comparing to the discrete time case, see that RG assumes analogous role the discrete time forward kernel 4k+1|K in how define the forward process. Therefore, just as in discrete time, we design R2 such that: i) the forward process mixes quickly towards an easy to sample (stationary) distribution, Prets (e.g. uniform), ii) can analytically obtain (2 (r)) distributions to enable efficient training (see Section 4.1 for how this is done). We initialize the forward CTMC at go (xo) = (da at time t = 0. We denote the marginal at time t T as 9r (IT), which should be close Prr((IT)
We now consider the time reversal of the forward process, which will take us from the marginal qr (XT) back to the data distribution Pdata (2o) through a reverse transition rate matrix, Rt E $x55
de (ū|z) = 6z.r + R2 F)A / + o(At).
In discrete time, one uses Bayes rule to go from (k+1/k to Gk|k+1- We can use similar ideas to calculate RG from RG as per the following result.
3

---

Proposition 1. For a forward in time CTMC, (e(oT)) with rate matrix Rs, initial distribution Pdata (To) and terminal distribution (r(z)), there exists a CTMC with initial distribution (r(TT) ) at t = T. terminal distribution (zo) at t 0 and transition rate matrix R, that runs backwards time and is almost everywhere equivalent to the time reversal of the forward CTMC, { Furthermore, Rs is related to Rs by the following expression
Re Re(ā,x) Exo
9. ((o()) de mm())m)))))) 40 (Folar))) for #
where (00((1220) are the conditional marginals of the forward process and qujs (2)o(z))z) 4: ( (z))/{((z) with qe(x)) being the marginal of the forward process at time t. When x 8. Re(x, x) = =- -. Re(x,x²)) because the rows must sum to zero (see Appendix A
Unfortunately, R₂ is intractable due to the intractabillity of (z) and thus of (z) Therefore, we consider an approximation RG of Rg by approximating Zoje (2olz) with a parametric denoising model. Poje (zo|z))
RC 2)) (F) Ezo
Rejo( (no) gejo(u (oo) Poj. (zular) for x xF
and (( (2, x²) as before. As further analogy the discrete time case, notice that when 2, Ri has the same form the discrete time parametric reverse kernel, Pk defined eq (T) but with the forward kernel, 9k+1/Ks replaced by the forward rate, Rt.
3.2 Continuous Time ELBO
In discrete time, 0 is trained by minimizing the discrete time negative ELBO, Lor, formed from the forward and reverse processes. We mirror this approach in continuous time by minimizing the corresponding continuous time (CT) negative ELBO, LCT, as derived below.
Proposition 2. For the reverse in time CTMC with initial distribution Pre(ZT). terminal dis- tribution p (z)), and reverse rate Re an upper bound on the negative model log- log-likelhhood Epan(2o) || log P (2o)), is given by
(C) = T Ee (1) where C. is constant independent of and z²(x) = Ex' (2,2x²)
[{ En (x, R/
2x(x) (., C.
r=(ā))) = -1, (x, ())2
Here (((x)) gives the probability of transitioning from æ to I, given that we know a transition occurs at time f. We can optimize this objective efficiently with stochastic gradient descent. For gradient update, we sample a batch of datapoints from Panta (rro) noise each datapoint using a random time, t t L(,, T), (x, ā) are a pair of states following the forward in time noising process. Minimizing the second term in Let maximizes the reverse rate for this pair, but going in the backwards direction, ă to This is how Ri learns reverse the noising process. Intuition on the first term and direct comparison to Lor is given in Appendix C.I
1ooo (nj (x(2)) and finally sample an auxiliary 7 from r, (ā(xr) for each æ. Intuitively,
The first argument of îeς is input into ph: we naively require two network forward passes on and to evaluate the objective. We can avoid this by approximating the ge (xr) sample in the first term with á meaning we need only evaluate the network once on f. The approximation is valid because, as we show in Appendix C.4 T is approximately distributed according to gr+5t for öt very small.
Efficient Forward and Backward Sampling
4.1 Choice of Forward Process
The transition rate matrix R, needs to be chosen such that the forward process: i) mixes quickly towards Prefs and ii) the (2)(2) distributions can be analytically obtained. The Kolmogorov

---

differential equation for the CTMC needs to be integrated to obtain 4:)(())2))) This can be done analytically when Rt and Rs commute for all t, t,t', see Appendix E An easy way to meet this condition is to let R2- B(t) where Rg R is user-specified time independent base rate matrix and ((t) E IR is time dependent scalar. We then obtain the analytic expression
f0 j =i] = (Qexp A So $(s)ds QQ )-)),s
where Rs = QAQ-1 is the eigendecomposition of matrix Rs and expl-) the element-wise exponential.
Our choice of | schedule is guided by 3 41 B(t) ab' log(6). The hyperparameters and b are selected such that (r(x) Rs Prer(z)) at the terminal time t = T" while having a steady speed of 'information corruption which ensures that R. does not vary quickly in a short span of time.
We experiment with a variety of Rs matrices, for example, a uniform rate, Rs 11 SId, where 11" I is a matrix of ones and Id is the identity. For problems with heavy spatial bias, e.g. images, we can instead use forward rate that only encourages transitions to nearby states; details and the links to the corresponding discrete time processes can be found in Appendix
4.2 Factorizing Over Dimensions
Our aim is to model data that is D dimensional, with each dimension taking one value from S possibilities. We now slightly redefine notation and say x xI: E X. |X = S. In this setting, calculating transition probabilities naively would require caleulating 5 rate values corresponding to each of the possible next states. This is intractable for any reasonably sized S and D. We avoid this problem simply by factorizing the forward process such that each dimension propagates independently. Since this is a continuous time process and each dimension's 's forward process is independent of the others, the probability two more dimensions transition at exactly the same time is zero. Therefore, overall in the full dimensional forward CTMC, each transition only ever involves a change in exactly one dimension. For the time reversal CTMC, will also be true that exactly one dimension changes in each transition. This makes computation tractable because of the S rate values, only (S 1) + are non-zero those corresponding to transitions where exactly one dimension changes plus the no change transition. Finally, we note that even though dimensions propagate independently in the forward direction, they are not independent in the reverse direction because the starting points for each dimension's 's forward process are not independent for non factorized Pdata- The following proposition shows the exact forms for the forward and reverse rates in this case.
Proposition 3. If the forward process factorizes as Qt)s (a)=(x]) [ (.. Io (11((1111))) t then the forward and reverse rates are of the form
RI: (I xx 1::)
Ei Rd
(i xd Sati (I.Di,,
RI:D(x 1:0 a 1I:) = Ebn (3
((1d,x"))) x ( pan Eng Tope (=flz1:1)) I:D) gyo(= (g
where Rf E RxS and 6 b ai is I when all dimensions except for d are equal.
To find iēg 1:D we simply replace Y0 (= with ph x: which is easily modeled with a neural network that outputs conditionally independent state probabilities in each dimension. In Appendix C.3 we derive the form of LCT when we use this factorized form for RI:DD and N.. I:D.
4.3
Simulating the Generative Reverse Process with Tau-Leaping
The parametric generative reverse process is CTMC with rate matrix RØ I:D Simulating this process from distribution Pre(<=):)) at time = T back to t = 0 will produce approximate samples from Pdata (=)) (=))). The process could be simulated exactly using Gillespic's s Algorithm [2] 22 23) which alternates between i) sampling holding time to remain in the current state and ii) sampling new state according the current rate matrix, Rí I:D (see Appendix F). This is inefficient for large D because we would need to step through each transition individually and so only one dimension would change for each simulation step.
Instead, we use tau-leaping 20 23 a very popular approximate simulation method developed in chemical physics. Rather than step back through time one transition to the next, tau-leaping leaps
5

---

from to t - 7 and applies all transitions that occurred in [t - T, t) simultaneously. To make leap, we assume I2, ief1:D and z!:D remain constant in It T, f]. As we propagate from t to we count all of the transitions that occur, but hold off on actually applying them until we reach such
t-r, such that x remains constant in [t - T. Assuming R7 1:1 and x; remain constant, the number of times transition from ai..D to x 11:D occurs in [,= | is Poisson distributed with mean T R 1.D (...D ..:D). Once we reach т, we apply all transitions that occurred simultaneously 2, I:D + Pi =!:P) where P; is Poisson random variable with mean ( I. D. Note the sum assumes a mapping from X' to Z.
ie. I:D
R 1:D
Using our knowledge of İNς 1: we can further unpack this update. Namely, R 1.D
(a:; (a:..D. ..::D) can only be non-zero when a1.D has a different value to a!.D I.D in exactly one dimension (rates for multi- dimensional changes are zero). Explicitly summing over these options we get 2;- = xx + EE Ex=rve Pas x²)e"" where ed is a one-hot vector with 1 at dimension d and Pas is Poisson random variable with mean T/2 1:D (x: zt. (s- jed). Since multiple Pas can be non-zero, in multiple dimensions in a single step. Figure 2 visualizes this idea. During the it T, t] interval, one jump occurs in dimension 1 and two jumps occur in dimension 2. These are all applied simultancously once we reach т. When our discrete data has ordinal structure (e.g. Section 6.2) our mapping to Z is not arbitrary and making multiple jumps within the same dimension (2 Pde > 1) is meaningful. In the non-ordinal/categorica case (e.g. Section 66.3) the mapping to is arbitrary and so, although taking simultaneous jumps different dimensions meaningful, taking multiple jumps within the same dimension is not, For this type of data, we reject changes to x for RDD" Pas 1. In practice, the rejection rate is very small when R2 is suitable for categorical data (e.g. uniform), see Appendix HH.3 In Section 4..5 our error bound accounts for this low probability of rejection and also the low probability of an out of bounds jump that we observe in practice in the ordinal case.
t-t
see that tau-leaping allows a;::D to change
53
S
Figure 2: 3D visualization of one tau-leaping step from
any d for which >
z7 = {Se, }1} to 2 1:2
Sz). Here, D 2.
| 5, P12 = 1, P22 = 2,
all other Pas =0
The tau-leaping approximation improves with smaller 7, recovering exact simulation in the limit as T Exact simulation is similar to autoregressive model in that only one dimension changes per step. Increasing T and thus the average number of dimensions changing per step gives us a natural way to modulate the "autoregressiveness" of the model and trade sample quality with compute (Figure 4 right). We refer to our method of using tau-leaping to simulate the reverse CTMC as 7LDR (tau-leaping denoising reversal) which formalize Algorithm | in Appendix
We note that theoretically, one could approximate Ñ I:D constant in the interval [t T, f). and construct a transition probability matrix by solving the forward Kolmogorov equation with the matrix exponential Pt-rjt exp(r 1:P). However, for the learned RØ p 5"x"" matrix, it is intractable to compute this matrix exponential so we use tau-leaping for sampling instead.
4.4 Predictor-Correcte
During approximate reverse sampling, we aim for the marginal distribution of samples at time & to be close to (xx) (the marginal at time t of the true CTMC). The continuous time framework allows us to exploit additional information to more accurately follow the reverse progression of marginals, {ge (ze))egzz;o) and improve sample quality. Namely, after a tau-leaping 'predictor' step using rate Rd we can apply 'corrector' steps with rate H& which has qe (xx)) as its stationary distribution. The corrector steps bring the distribution of samples at time t closer to the desired qe (x.) marginal. RG is easy to calculate as stated below
forward rate, R2, and corre- sponding reverse CTMC with rate RG, the rate R Rr RG has qe (xx) as its stationary distribution.
Proposition 4. For a forward CTMC with marginals

---

In practice, we approximate RG by replacing Rg with Ry. This is directly analogous to Predictor- Corrector samplers in continuous state spaces 4 that predict by integrating the reverse SDE and correct with score-based Markov chain Monte Carlo steps, see Appendix F.2 for further discussion.
4.5
Error Bound
Our continuous time framework also allows us to provide a novel theoretical bound on the error between the true data distribution and the sample distribution generated via tau-leaping (without predictor-correcto steps), in terms of the error in our approximation of the reverse rate and the mixing of the forward noising process.
We assume we have time-homogeneous rate matrix R₂ on X, from which we construct the factorized rate matrix R.DD on X' by setting R = R₂ for each d. Note that by rescaling time by factor of 3(t) we can transform our choice of rate from Section 4.1 to be time-homogen momooeoogge,us, We will denote R
x)), and let mix be the (174)-mixing time of the CTMC with rate R (see 24 Chapter 4.5]).
SUP=e(o,TT..re
Theorem 1. For any D 2 and distribution Paata on XD, let (Ie (xtheeu be a CTMC starting in Paata with rate matrix Ri-D as above. Suppose that fe. 1:D: is an approximation to the reverse rate matrix and let )w N be a lau-leaping approximation to the reverse dynamics with maximum step size T. Suppose further that there is some constant M independent of D such that
Σ UIZ
RI.D (z.z)
R
R@1:D
(z. v) S M
for all [0, TV. Then under the assumptions in Appendix B.5 there constants C1 C2 depending on X and Rd but not D such that, if L(y0) denotes the law of yo. we have the total variation bound
(aaii)-PPaalllmaa [| - Paaul/TV S 3MT + {IR))DC))) + +CA(MCGISDII))-- +T {-
{
T Tiog 2 Trms log 4D
The first term of the above bound captures the error introduced by our approximation of the reverse rate fit:D with iłę 1:D The second term reflects the error introduced by the tau-leaping approximation, and is linear in both 7 and 7, showing that as we take our tau-leaping steps to be arbitrarily small, the error introduced by tau-leaping goes to zero. The final term describes the mixing of the forward chain, and captures the error introduced since Pret and gr not exactly equal.
We choose to make the dependence of the bound on the dimension explicit, since we are specifically interested in applying tau-leaping to high dimensional problems where we make transitions in different dimensions simultaneously
single time step. The bound grows at worst quadratically in the dimension, versus e.g. exponentially. The bound is therefore useful in showing us that we do not need to make r impractically small high dimensions. Other than gaining these intuitions, we do not expect the bound to be particularly tight in practice and further it would not be practical to compute because of the difficulty finding M, C₁ and C2.
The assumptions listed in Appendix B.5]hold approximately for tau-leaping in practice when we use spatially biased rates for ordinal data such that jump sizes are small or uniform rates for non-ordinal data such that the dimensional rejection rate is small. These assumptions could be weakened, however, Theorem would become much more involved, obscuring the intuition and structure of the problem.
Related Work
The application of denoising models discrete data was first described in I using a binomial diffusion process for a binary dataset, Each reverse kernel p was directly parameterized without using a denoising model p In (25] an approach for discrete categorical data was suggested using a uniform forward noising kernel, qi++ and a reverse kernel parameterized through a denoising model, though no experiments were performed with the approach. Experiments on text and segmentation [6]. Other forward kernels were introduced in X that are more appropriate for certain data types such as the spatially biased Gaussian kernel. [ apply the approach to discrete latent space modeling using uniform and absorbing state forward
maps were then performed with similar model in
[3
7

---

T
Hellinger Distance
0.40
tau-leaping
exact simulation
0.35
0.30
T
0.25
0.004
0.008 0.016 0.032 0.064 0.128
FT
Figure 3: Left: Hellinger distance between the true training distribution and generated sample distributions with exact simulation or tau-leaping. With 7 small, we simulate the reverse CTMC with the same fidelity the exact simulation. Top Right: Histograms of the marginals during the reverse generative process simulated using tau-leaping with r 0.004. Darker and larger diamonds represent increased density. Bottom Right: The same for 0.1, note the reduced sample quality.
kernels. Whilst link continuous time for the forward process is mentioned in (8) all of these approaches train and sample in discrete time. We show in Appendix G that this involves making an implicit approximation for multi-dimensional data. We extend this line of work by training and sampling in continuous time.
Other works also operate in discrete space but less rigidly follow the diffusion framework. A corruption process tailored to text is proposed in [12), whereby token deletion and insertion is also incorporated. (26) also focus text, creating generative reverse chain that repeatedly applies the same denoising kernel. The corruption distribution is also defined through the same denoising kernel to reduce distribution shift between training and sampling. In (7).
standard masking based forward process is used but the reversal is interpreted from an order agnostic autoregressive perspective. They also describe how their model can interpreted as the reversal of continuous time absorbing state diffusion but do not utilize this perspective in training or sampling.
(27 propose
a denoising type framework that can be used on binary data where the forward and reverse process share the same transition kernel. Finally, in [II], the discrete latent space of a VQVAE is modeled by quantizing an underlying continuous state space diffusion with probabilistic quantization functions.
Experiments
6.1 Demonstrative Example
We first verify the method can accurately produce samples from the entire support of the data distribution and that tau-leaping can accurately simulate the reverse CTMC. To do this, create dataset formed of 2d samples of a state space of 32 arranged such that the histogram the training dataset forms 'T' shape. We train denoising model using the Ler objective with ph parameterized through a residual MLP (full details in Appendix H. We then sample the parameterized reverse process using an exact method (up to needing to numerically integrate the reverse rate) and tau- leaping. Figure 3 top-right shows the marginals during reverse simulation with = 0.004 and we indeed produce samples from the entire support of Puaa- Furthermore, we find that with sufficiently small т, we can match the fidelity of exact simulation of the reverse CTMC (Figure 3 left). The value of dictates the number of network evaluations in the reverse process according to NFE T/5. In all experiments we use T = 1. Exact simulation results in non zero Hellinger distance between the generated and training distributions because of imperfections in the learned Re model.
6.2 Image Modeling
We now demonstrate that our continuous time framework gives us improved generative modeling performance versus operating in discrete time. We show this on the CIFAR- image dataset. Images are typically stored as discrete data, each pixel channel taking one value from 256 possibilities. Continuous state space methods have to somehow get around this fact by, for example, adding discretization function at the end of the generative process
3 adding uniform noise to the data.

---

Table I: Sample quality metrics and model likelihoods for diffusion methods modeling CIFARIO in discrete state space. Diffusion methods modeling CIFARIO 10 in continuous space are included for reference. The Inception Score (IS) and Fréchet Inception Distance (FID) are calculated using 50000 generated samples with respect to the training dataset as is standard practice. The ELBO values are reported on the test set in bits per dimension.
Method
IS (t)
FID (4)
ELBO (1)
Discrete state
D3PM Absorbing
6.78
30.97
-4.40
D3PM Gauss
g
8.56
7.34
-3.44
LDR-0 (ours)
8.74
8.10
-3.59
LDD-10 (ours)
9.49
3.74
-3.59
Continuous state
DDPM 8
9.46
3.17
-3.75
NCSN 4
9.89
2.20
64
TLDR-0
TLDR-3
FID (10k)
32
TLDR-10
16
8-
64
128
256
512
1024
NFE
Figure 4: Left: Unconditional CIFARIO samples from our 7LDR-10 model Right: FID scores for the generated CIFARIO samples versus number of Poj evaluations during sampling (variation induced by varying 7). Calculated with 10k samples, hence the discrepancy with Table 28
Here, we model the images directly in discrete space. We parameterize poj using the standard U-net architecture (3) with the modifications for discrete state space suggested by [8]. We use spatially biased rate matrix and train with an augmented Lcr loss including direct Poje supervision,
full experimental details are in Appendix H.2
Figure|]ee shows randomly generated unconditional CIFARIO samples from the model and we report sample quality metrics in Table We see that our method (rLDR-0) with corrector steps has better Inception Score but worse FID than the D3PM discrete time method. However, our -LDDR-10 method with corrector steps per predictor step at the end of the reverse sampling process (1 < 0.17) greatly improves sample quality, beating the discrete time method in both metrics and further closes the performance gap with methods modeling images as continuous data. The derivation of the corrector rate which gave us this improved performance required our continuous time framework. D3PM achieves the highest ELBO but we note that this does not correlate well with sample quality. In Table [ was adjusted such that both 7LDR-0 and rLDR-10 used 1000 p evaluations in the reverse sampling procedure. We show how FID score varies with number of pojr evaluations for rLDR-(0, 3, 10) in Figure right. The optimum number of corrector steps depends on the sampling budget, with lower numbers of corrector steps being optimal for tighter budgets. This is due to the increased required to maintain fixed budget when a larger number of corrector steps.
Figure/rright.
6.3 Monophonic Music
In this experiment, we demonstrate our continuous time model improves generation quality on ann-ordinal/categoriall discrete data. We model songs from the Lakh pianoroll dataset 29 30). We select all monophonic sequences from the dataset such that at each of the 256 time steps either one from 128 notes is played or it is a rest. Therefore, our data has state space size S 129 and dimension D = 256. We scramble the ordering of the state space when mapping to ž to destroy any ordinal structure. We parameterize pº with a transformer architecture [1 and train using conditional form of Let targeting the conditional distribution of the final 14 bars (224 time steps) given the first 2 bars of the song. We use uniform forward rate matrix, Rg, full experimental details

---

Table 2: Metrics comparing generated conditional samples and ground truth completions. We compute these over the test set showing mean with respect to 5 samples for each test song.
Model
Hellinger Distance
Proportion of Outliers
T TLDR-0 Birth/Death
0.3928 = 0.0010
0.1316 + 0.0012
-LDR-0 Uniform
0.3765 = 0.0013
0.1106 = 0.0010
rLDR-2 Uniform
0.3762 = 0.0015
0.1091 + 0.0014
D3PM Uniform 8
0.3839 = 0.0002
0.1137 = 0.0010
Original
Sample
Sample 2
Song A
E3
G#3
Song
C4
8 Bar
12
16
12
16
8
12
16
Bar
Bar
Figure 5: Conditional completions of an unseen music sequence. The conditioning 2 bars are shown to the left of the black line. More examples and audio recordings are linked Appendix H.3
are given in Appendix H.3 model is able to faithfully complete the piece in the same style as the conditioning bars.
Conditional completions of unseen test songs are shown in Figure 5 The
We quantify sample quality in Table We use two metries: the Hellinger distance between the histograms generated and ground truth notes and the proportion of outlier notes in the generations but not in the ground truth. Using our method, we compare between birth/death and uniform forward rate matrix Rg The birth/death rate is only non-zero for adjacent states whereas the uniform rate allows transitions between arbitrary states which is more appropriate for the categorical case thus giving improved sample quality. Adding corrector steps per predictor step further improves sample quality. We also compare to the discrete time method D3PM ( with its most suitable corruption process for categorical data. We find it performs worse than our continuous time method.
7 Discussion
We have presented a continuous time framework for discrete denoising models. We showed how to efficiently sample the generative process with tau-leaping and provided bound the error of the generated samples. On discrete data problems, we found our predictor-correcto sampler improved sample quality versus discrete time methods. Regarding limitations, our model requires many model evaluations to produce a sample. Our work has opened the door to applying the work improving 17 32] to discrete data problems too. Modeling
sampling speed continuous data [14 15 16 performance on images is also slightly behind continuous state space models, we hope this gap is further closed with bespoke discrete state architectures and corruption process tuning. Finally, note that the ELBO values for the discrete time model on CIFAR 10 are better than for our method. In this work, focused sample quality rather than using our model to give data likelihoods e.g. for compression downstream tasks.
Acknowledgements
Andrew Campbell and Joe Benton acknowledge support from the EPSRC CDT in Modern Statisties and Statistical Machine Learning (EP/S023151//), Arnaud Doucet is partly supported by the EPSRC grant EP/R034710N 10/1. He also acknowledges support of the UK Defence Science and Technology Laboratory (DSTL) and EPSRC under grant EP/R01 3616/1. This is part of the collaboration between US DOD, UK MOD and UK EPSRC under the Multidisciplinary University Research Initiative. This project made use of time Tier 2 HPC facility JADE2, funded by EPSRC (EP/TO22205/1).
10

---

References
[T] Jascha Sohl- Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. International Conference Machine Learning, 2015.
[2] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution, Advances Neural Information Processing Systems, 2019.
[3] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 2020.
[4] Yang Song, Jascha Sohl- fohh-Dic,stein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021.
[5] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat GANs on image synthesis. Advances in Neural Information Processing Systems, 2021.
[6] 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, 2021.
[7] Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. International Conference on Learning Representations, 2022.
[8] Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 2021.
[9] Patrick Esser, Robin Rombach, Andreas Blattmann, and Bjorn Ommer. Imagebart: Bidirectional context with multinomial diffusion for autoregressive image synthesis. Advances in Neural Information Processing Systems, 2021.
[10] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. International Conference on Machine Learning, 2022.
[11] Max Cohen, Guillaume Quispe, Sylvain Le Corff, Charles Ollion, and Eric Moulines. Diffusion bridges vector quantized variational autoencoders. International Conference on Machine Learning, 2022.
[12] Daniel D Johnson, Jacob Austin, Rianne van den Berg, and Daniel Tarlow. Beyond in in-place corruption: Insertion and deletion in denoising probabilistic models. ICML Workshop Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models (INNF+), 2021.
[13] Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to-image synthesis. IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.
[14] Alexia Jolicoeur-Martineauu Ke Li, Rémi Piché-Taillefer Tal Kachman, and loannis Mitliagkas. Gotta go fast when generating data with score-based models. arXiv preprint arXiv:2105.14080 2021.
[15] Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. arXiv preprint arXiv:2204.13902 2022.
[16] Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. International Conference on Learning Representations, 2022.
[17] Hyungjin Chung, Byeongsu Sim, and Jong Chul Ye. Come-closer conditional diffusion models for inverse problems through stochastic contraction. IFFF/CVF Conference Computer Vision and Pattern Recognition, 2022.
Accelerating
11

---

[18] Tim Dockhomn, Arash Vahdat, and Karsten Kreis. Score-based generative modeling with critically-damper Langevin diffusion. International Conference on Learning Representations. 2022.
[19] Valentin De Bortoli, James Thomton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to basee generative modeling. Advances in Neural Information Processing Systems, 2021.
[20] Daniel T Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of Chemical Physics, 115(4))171-11333, 2001.
[21] Daniel T Gillespie. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. Journal of Computational Physics, 22(():403 4444)440-433, 1976.
[22] Daniel T Gillespie. Exact stochastic simulation coupled chemical reactions. The Journal of Physical Chemistry, 8 (155))2340-2361 1977.
[23] Darren Wilkinson. Stochastic Modelling for Systems Biology. Chapman and Hall/CRC, 2018.
[24] David Levin, Yuval Peres, and Elizabeth Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009.
[25] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. International Conference on Learning Representations, 2021.
[26] Nikolay Savinov, Junyoung Chung, Mikolaj Binkowski, Erich Elsen, and Aaron van den Oord. Step-unrolled denoising autoencoders for text generation. International Conference Learning Representations, 2022.
[27] Anirudh Goyal, Nan Rosemary Ke, Surya Ganguli, and Yoshua Bengio. Variational walkback: Learning a transition operator as a stochastic recurrent net. Advances in Neural Information Processing Systems, 2017.
[28] Min Jin Chong and David Forsyth. Effectively unbiased fid and inception score and where to find them. IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
[29] Colin Raffel. Learning-basee methods for comparing sequences, with applications to audio-to- midi alignment and matching. PhD thesis, Columbia University, 2016.
[30] Hao- Wen Dong, Wen-Yr Yi Hsiao, Li-Chia Yang, and Yi-Hsuan Yang. Musegan: Multi-trad sequential generative adversarial networks for symbolic music generation and accompaniment. AAAI Conference on Artificial Intelligence, 2018.
[31] Gautam Mittal, Jesse Engel, Curtis Hawthorne, and Ian Simon. Symbolic music generation with diffusion models. International Society for Music Information Retrieval, 2021.
[32] Fan Bao, Chongxuan Li, Jun Zhu, and Bo Zhang. Analytic-dpm: an analytic estimate of the optimal reverse variance in diffusion probabilistic models. International Conference on Learning Representations, 2022.
[33] David F Anderson. A modified next reaction method for simulating chemical systems with time dependent propensities and delays. The Journal of Chemical Physics, 127(21):114107, 2007.
[34] Chie Furusawa, Shinya Kitaoka, Michael Li, and Yuri Odagiri. Generative probabilistic image colorization. arXiv preprint arXiv: 100.:///0
145/8, 2021.
[35] Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville. Film: Visual reasoning with general conditioning layer. AAAI Conference Artificial Intelligence, 2018.
[36] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
12

---

[37] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. International Conference on Medical Image Computing and Computer-assisted Intervention, 2015.
[38] Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma. Pixelcnn++4: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. International Conference on Learning Representations, 2017.
[39] Xi Chen, Nikhil Mishra, Mostafa Rohaninejad, and Pieter Abbeel. Pixelsnail: An improved autoregressive generative model. International Conference Machine Learning, 2018.
[40] Stefan Elfwing, Eiji Uchibe, and Kenji Doya.
linear units for neural network function approximation in reinforcement learning. Neural Networks, 107:3-11, 2018.
[41] Maximilian Seitzer. pytorch-fid: FID Score for PyTorch. hnttps://githii http://ttttuu..ccom//eieetteeeee pytorch-fie fid, August 2020. Version 0.2.1.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] We detail the continuous time framework in Section 3
show our theoretical result in Section 4.5 and demonstrate improved performance in
Section 6
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix[
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all thcoretical results? [Yes] See Appendix
B.5
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code available at bectps://githee
com/ andrew cr/tauLDR
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix H
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Table
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix H
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the authors of the models and datasets we use in Section 6
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any assets either in the supplemental material URL? [Yes] We include our curated data in the supplement
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zPSY2_P87e9", "reviewer": "Reviewer_JFfK", "summary": "This paper study diffusion models with discrete states. This paper considers continuous time by introducing the transition rate matrix. A relationship between the denoiser q(x0|xt) and the reverse transition rate matrix is built, and the author uses a denoising model p(x0|xt) to approximate q(x0|xt). The author further proposes a continuous time ELBO, which can be used to train p(x0|xt). The author also applies the Tau-Leaping for sampling from the diffusion model, which can be faster than the exact simulation. Experiments show the effectiveness of this method.\n", "questions": "1. It seems directly applying the discrete time diffusion model to high dimensional data needs to model a complex $q_{0|k}(x_0^{1:D}|x_k^{1:D})$, according to $q(x_{k-1}^{1:D}|x_k^{1:D}) = E_{q(x_0^{1:D}|x_k^{1:D})} q(x_{k-1}^{1:D}|x_k^{1:D}, x_0^{1:D})$. However, according to Proposition 3, this work only needs to model a one-dimensional $q_{0|t}(x_0^d|x_t^{1:D})$. What is the intristic reason between this difference? This is important to further understand this work.\n\n2. When discussing improving sampling speed in Section 7, [1] can be cited, which is also an important work on speeding up diffusion models.\n\n[1] Bao et al., Analytic-DPM: an Analytic Estimate of the Optimal Reverse Variance in Diffusion Probabilistic Models.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper develops a continuous time framework for discrete data. This framework includes optimum analysis, training, sampling and error analysis, which are nice. This paper also provides sufficient math pre knowledge to understand this framework, which makes this work more readable.\n\nWeakness:\n1. **Relationship to prior works can be discussed more.** Prior to this work, there are various works on discrete state diffusion models, e.g., as mentioned by the author, uniform kernel and absorbing kernel. The relationship to these works can be discussed more, for example from these aspects: (a) What is the corresponding transition rate matrix of these prior methods; (b) Will the reverse process of prior discrete time methods (between Line 70 and Line 71)  converge to the continuous time reverse process proposed in this paper? (c) Is the sampling method in the discrete time case applicable to the continuous time case? How about comparing Tau-Leaping and discrete time sampling?\n\n2. **More ablation study.** This paper provides various techniques for continuous time diffusion models. For example, discrete time ELBO -> continuous time ELBO, discrete time sampling -> Tau-Leaping sampling. Which one makes the greatest contribution to the performance?\n\n---------------------\n\nWhile there is still a (relatively small) performance gap between this work and continuous diffusion models, I think it is an important work due to its technical contributions. I'd like to further raise my score if my concerns are addressed.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uuWHL-pBNi", "reviewer": "Reviewer_yvGD", "summary": "This paper proposed to extend the continuous-time diffusion/score-based modeling idea (Song et al., 2021) to discrete state space. In discrete state space, there is no SDEs therefore the forward process needs to be replaced by a discrete-state CTMC, which is characterized by the infinitesimal generator (transition rate matrix). Effective parameterizing and optimizing such models are nontrivial and the authors introduce several innovations to tackle these problems, including a continuous time lower bound for discrete state space, computable representations of the rate matrix, and a way to trade off sample speed and quality. Experiment results show it outperforms prior discrete diffusion models despite still lag behind continuous diffusion models. ", "questions": "* Could the authors comment on possible reasons why discrete state modeling is still outperformed by their continuous counterpart? Also related to the limitation question below.", "limitations": "The authors discussed some limitations but I am additionally interested in the above question --- what limits the model to perform as well as continuous state diffusions on discrete image data? Is it because of the flexibility of generator parameterization? or the tradeoff caused by computational cost?", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a nice paper and I have no much complain about it. Particular strong points are\n* Principled characterization of discrete CTMC via the generator (transition rate) matrix\n* A well-thought way to represent the exponentially large rate matrix that is both flexible and computationally cheap. \n* The observation that the sum of forward and backward generator has the marginal distribution at that time as stationary (Proposition 4), which enables the adoption of the predictor-corrector sampling proved effective by Song et al. (2021) in continuous diffusions. \n\nThe only suggestion I have is to improve the readability of section 4.3 by first explaining the canonical way of sampling from a discrete-state CTMC using competing exponential clock (I haven't checked but I suspect this corresponds to the Gillespie's algorithm). The tau-leaping idea could be explained in more detail in appendix and an algorithm box in main text would definitely help. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nPAWYINL9vL", "reviewer": "Reviewer_QzER", "summary": "This paper studies discrete state denoising diffusion-based generative models, where the data to be modelled is discrete, categorical, etc. In these cases, the standard diffusion model approach, which assumes that the data is continuous and can be perturbed in a smooth and continuous manner, breaks down. Previous discrete state diffusion models relied on frameworks that used discrete, step-wise perturbations, this is, in each step, some states are flipped to other states. This paper, in contrast, proposes a continuous-time framework for discrete state diffusion models, leveraging *Continuous Time Markov Chains* (CTMCs). Intuitively, we can think of the approach as a diffusion that runs in continuous time, and at certain times states flip to other states. The frequency how often that happens is described by transition rates (rate matrices $R_t(\\tilde{x},x')$). This seems like a very elegant and appropriate formalism for discrete state diffusion models. The paper shows how, using Bayes rule, a corresponding reverse generative CTMC can be derived. This generative CTMC isn't analytically tractable, but the paper derives an objective, a continuous-time ELBO, that can be used to learn an approximate generative CTMC. To efficiently simulate the learnt generative CTMC, the paper then further suggests to use $\\tau$-leaping, a technique taken from the chemical physics literature. While $\\tau$-leaping makes certain approximations, as a side the paper also derives a corrector scheme to essentially clean up errors made by $\\tau$-leaping. Finally, the paper also derives some error bounds between the generated and ground truth distribution.\n\nExperimentally, the paper analyses the approach on 3 generative tasks (a toy dataset, CIFAR10 image generation, symbolic music generation). The results are favourable compared to previous discrete-state diffusion models and provide insights into the different proposed components, this is, $\\tau$-leaping and its approximations as well as the corrector scheme.", "questions": "I also have a few minor questions and comments:\n- It's nice that the paper derived these errors bound. However, how useful are they in practice? How loose are those bounds? Would it be insightful to compute these bounds for the experiments that are run?\n- It could make sense to add Fig. 4 from the Appendix into the main paper. The main paper doesn't have any larger or nice pipeline figure and this figure is actually quite insightful and helpful for the non-expert reader to get a very quick impression about what is happening in CTMCs.\n- It could be helpful for the reader to provide some more intuitions about the difference between the different transition rate matrices $R(\\tilde{x},x)$ and $r(\\tilde{x}|x)$.\n- While going over the appendix, in Proposition 7, $\\psi_t(\\tilde{\\mathbf{x}}^{1:D}|\\mathbf{x}_0^{1:D})$ in line 765 does not seem to be properly defined anywhere. $\\psi_t(\\tilde{\\mathbf{x}}^{1:D}|\\mathbf{x}_0^{1:D})$ sort of appears in the proposition but is then never really used.", "limitations": "Some limitations have been briefly mentioned at the end of the paper (slow sampling). Ethical considerations and potential negative societal impact are discussed in some detail in the appendix. I think these discussions are satisfactory and appropriate.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- *Novelty and Originality*: As mentioned in the summary the paper proposes, derives, or suggests multiple technical innovations for discrete state diffusion models. This includes the general CTMC framework, the ELBO loss for training, the $\\tau$-leaping sampling, and the error bounds. Some of the derivations are a bit related to similar derivations from regular continuous-time diffusion models, but overall I think the paper presents a lot of methodological novelty and is very original in that regard.\n- *Clarity and Presentation*: The paper is overall well-written and nicely presented. It is a mathematically very dense paper and naturally requires very careful reading, but considering that it is relatively smooth to read. The authors make a good job in providing a lot of details and additional background in the appendix to help with that.\n- *Significance and Impact:* Diffusion models have become a very popular and promising class of generative models, and also discrete state diffusion models are used more frequently. Considering that, I think this is a significant contribution, since the paper shows a fundamentally different, potentially better way, to set up discrete state diffusion models. I believe the method will find further usage and there will be follow-up papers, building on this paper and further improving the method.\n\n**Weaknesses:**\n\nMethodologically, I have no major concerns at all. However, the experimental results, while insightful, are overall not particularly impressive.\n- Performance-wise, the method is still behind standard continuous state diffusion models on image data.\n- It is also still very slow to sample from the learnt CTMC models. In that regard, it also seems $\\tau$-leaping only generates really strong results when combined with the corrector scheme or when doing very small steps $\\tau$.\n- It would be interesting to consider more experiments on other data. The recent paper [1] tackles text generation, a very natural discrete state task. I would be very curious how the model performs here.\n- The ELBO numbers in the CIFAR10 experiments (Table 1) are behind those of D3PM and also generally quite a bit worse than more modern diffusion models such as DDPM++ [2], which also leverage a continuous time framework. This might imply that the models have reduced generation diversity, as evidently some validation data has somewhat low probability under the learnt distribution.\n\n**Conclusions and Summary:**\nOverall, I think this is a high-quality paper that should be accepted. It presents a lot of new ideas and a lot of methodological novelty and demonstrates the advantages of the proposed method. The CTMC approach to discrete state diffusion models seems overall like a very sensible idea, and maybe the way to go in the future for this model class. On the other hand, the experiments seem appropriate to test the method, but the results aren't overly impressive when compared to the broader literature.\n\n[1] Austin et al., \"Structured Denoising Diffusion Models in Discrete State-Spaces\", NeurIPS, 2021\n\n[2] Song et al., \"Score-Based Generative Modeling through Stochastic Differential Equations\", ICLR, 2021", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6Dqa_9V8Dr", "reviewer": "Reviewer_Lc6p", "summary": "The paper proposes a continuous-time (CT) diffusion model for discrete data. In contrast to discrete-time (DT) diffusion models for discrete data, the CT diffusion model replaces the discrete time forward kernel with a transition rate matrix. It is then shown that that there exist a reverse transition matrix which can be used for generation. A CT ELBO to learn said reverse transition matrix is derived. The authors describe different choices of transition rate matrices than can be used. For high-dimensional data, the memory requirement for the transition matrices becomes large, and therefore the authors discuss a factorization technique. The paper proposes to sample from the CT diffusion model via tau-leaping, a well-known technique in chemical physics. The CT framework allows for bounds on the discrepancy between the true data distribution and the sampling distribution induced by tau-leaping. The author test their method on various experiments, outperforming existing DT diffusion models on discrete data.", "questions": "* Experiment 6.1: How many NFEs it the model using for the different values of $\\tau$? I expect $\\tau=0.004$ needing to use significantly more than say $\\tau=0.1$.\n* Experiment 6.2: Are all baseline methods in Table 1 using 1000 NFEs? How well does the model perform when you use significantly less than 1000 NFEs, say 50?\n* Experiment 6.3: What's the intuition that your method outperforms D3PM on CIFAR-10 by a large margin but only slightly (correct me if I am wrong) on the Monophonic Music dataset?  Why do you compare to different versions of D3PM (absorbing/gaussian vs uniform) on the two modalities? ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The proposed method is novel.\n* Using tau-leaping to reduce the NFEs needed for generation is clever.\n* The paper is very detailed and the appendix is complete (as far as I can tell)\n* I like that the paper shows experiments over two modalities. (On that note, I would have been really interested to also see how the method performs on text data. This is just a personal preference and won't influence my review/rating.)\n\nWeaknesses:\n* There are some interesting ablations missing, for example, on the choice of $R_b$, the impact of factorizing over dimensions, and the training approximation described in C.4. I think these experiment would be very valuable.\n* Some details/explanations in the experiment section are missing. See Qs below.\n* The method performs very well when many corrector steps are used but what's the intuition behind that? For continuous diffusion models it seems that one (or no) corrector step(s) is sufficient. This should have been discussed/investigated.\n\nSuggestions:\n* The training approximation in C.4 is interesting/important and I would have liked to see some discussion/intuition in the main paper and not just the appendix.\n* I think the tau-leaping idea is very cool and breaks the stigma that discrete diffusion models are inherently slow at inference time. Given the success of accelerating inference for continuous diffusion models, I think it would be very valuable to have more experiments/investigations/outlooks how to even further improve acceleration? Maybe adapt tau-leaping towards the special use case of sampling from discrete diffusion? \n\nAll in all, I think the paper propose a very interesting method (as well as very good results). I intend to raise my score if weaknesses/questions are sufficiently addressed.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept