Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

Experimentally, 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.
strengths_and_weaknesses: **Strengths:**
- *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.
- *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.
- *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.

**Weaknesses:**

Methodologically, I have no major concerns at all. However, the experimental results, while insightful, are overall not particularly impressive.
- Performance-wise, the method is still behind standard continuous state diffusion models on image data.
- 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$.
- 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.
- 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.

**Conclusions and Summary:**
Overall, 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.

[1] Austin et al., "Structured Denoising Diffusion Models in Discrete State-Spaces", NeurIPS, 2021

[2] Song et al., "Score-Based Generative Modeling through Stochastic Differential Equations", ICLR, 2021
questions: I also have a few minor questions and comments:
- 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?
- 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.
- 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)$.
- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: This is a nice paper and I have no much complain about it. Particular strong points are
* Principled characterization of discrete CTMC via the generator (transition rate) matrix
* A well-thought way to represent the exponentially large rate matrix that is both flexible and computationally cheap. 
* 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. 

The 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. 
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?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths:
1. 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.

Weakness:
1. **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?

2. **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?

---------------------

While 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.
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.

2. When discussing improving sampling speed in Section 7, [1] can be cited, which is also an important work on speeding up diffusion models.

[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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
* The proposed method is novel.
* Using tau-leaping to reduce the NFEs needed for generation is clever.
* The paper is very detailed and the appendix is complete (as far as I can tell)
* 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.)

Weaknesses:
* 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.
* Some details/explanations in the experiment section are missing. See Qs below.
* 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.

Suggestions:
* 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.
* 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? 

All 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.
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$.
* 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?
* 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
review_title: null

Meta-review: metareview: The work proposes a continuous-time generalization of diffusion models on a discrete space. The description uses continuous-time Markov chain (CTMC), in parallel to the existing stochastic differential equation description for continuous space. Reverse CTMC and modeling and ELBO objective are described. Some practical considerations and inspirations are also discussed, including avoiding exponentially large model in high dimensions, efficient reverse (generation) process simulation, and a corrector technique that further exploit the model to improve simulation (generation) quality. An error bound on the learned data distribution is also presented that shows a mild dependency on data dimensionality.

All the reviewers agree that this work presents the very right way to describe the continuous-time version of diffusion model on discrete space, and thereafter inspired techniques make a desired contribution to the community. Some concerns are raised, including still inferior performance than the continuous counterpart, and on the independence among dimensions. The authors provide reasonable remarks on them. Hence, I recommend accept to this paper.

One minor point: In Sec. 4.2, it would be clearer if the independence is specified both among the random variables $x^{1:D}$ in “output” and between each $x^d$ in “output” and $x^{1:D\backslash d}$ in “input”. Conventionally independence refers to the former, in which case the size is only reduced to $S^D \times D S^2$.

confidence: Certain
Decision: Accept