Discrete diffusion models have emerged as powerful tools for high-quality data generation. Despite their success in discrete spaces, such as text generation tasks, the acceleration of discrete diffusion models remains under-explored. In this paper, we propose discrete non-Markov diffusion models (DNDM), which naturally induce the predetermined transition time set. This enables a training-free sampling algorithm that significantly reduces the number of function evaluations (i.e., calls to the neural network), making the sampling process much faster. Furthermore, we study the transition from finite to infinite step sampling, offering new insights into bridging the gap between discrete and continuous-time processes for discrete diffusion models. Extensive experiments on natural language generation and machine translation tasks demonstrate the superior performance of our method in terms of both generation speed and sample quality compared to existing methods for discrete diffusion models.
Paper
Similar papers
Peer review
Summary
The paper proposes an accelerated sampling method from standard discrete diffusion models like multinomial diffusion and absorbing-state diffusion, using a non-Markovian forward process where the stochasticity is modelled by sampling a single transition time for each token, after which the process is fully determined. The model is trained similarly as a standard discrete diffusion model, but the formalism allows for a different type of sampler: The transition times are sampled in advance in the beginning, and the denoiser neural network simply parameterizes the transitions that happen at those times in the reverse process. This allows to skip over redundant steps where no transition would occur in the standard discrete diffusion models, speeding up sampling significantly for large step counts. The model provides improved results and faster sampling speeds over a prior accelerated sampling method for sequence-to-sequence generation tasks, and similarly improved results for unconditional language modelling with the text8 and enwik8 data sets when comparing with a prior multinomial diffusion model.
Strengths
+ Clearly improves over a standard multinomial and absorbing-state schedule in sampling speed and results + Improves over a previous published work in accelerating discrete diffusion models + The framework could be a useful conceptual tool for people working with standard discrete diffusion models in the style of D3PM and want to accelerate sampling. Methods like ARDM from Hoogeboom et. al. and the tau-leaping of Campbell et al. are similar in function, but either require reframing the modelling problem differently or only allow for absorbing-state transitions in the case of ARDM. + In contrast, this paper presents a method that allows changing a model in the D3PM framework to a faster one that skips over redundant steps, and shows how it is connected to the original model as a model with transition times as latent variables. + The method is simple and easy-to-use
Weaknesses
- The method is, in practice, somewhat similar to prior work (Campbell et. al. and Hoogeboom et. al.), and in that sense it would be more beneficial for the community if the paper went deeper into analysing potential speed improvements in discrete diffusion models or theoretical connections between their method and other work. - It would be useful if we had results from less steps in Table 3: Seems like the biggest time improvements are obtained with large step counts, but the BLEU scores are not drastically different from low step count BLEU scores. If both methods work quite well with low step counts already, then the results don't seem like the best showcase of the improvements due to increased step counts. Overall, it would be useful to have a clearer picture of the situations in which the method provides practical benefits. [1] "A Continuous Time Framework for Discrete Denoising Models", Campbell et. al. [2] "Autoregressive Diffusion Models", Hoogeboom et. al.
Questions
- Since the accelerated multinomial model now does only one step for each token, I suppose it is not quite equivalent to the standard multinomial diffusion, where multiple transitions per token can happen during the generative process? Could the authors clarify the similarities and differences?
Rating
6
Confidence
4
Soundness
3
Presentation
3
Contribution
2
Limitations
Addressed.
Summary
This paper proposes a new formulation for discrete diffusion models whereby the corruption process is defined as a non-markovian process. At each point, a decision is made as to either stay in the current state or switch to a noise sample however crucially, this noise sample is constant throughout the process thereby only a single transition happens for each dimension. During generation, the model then just needs to step from transition time to transition time and can ignore superfluous simulation steps where no transition happens. The model is trained using an ELBO which the authors derive for their transition time conditional process. The authors test their model on machine translation examining quality versus sample speed and also on unconditional text generation with the text8 dataset.
Strengths
The authors present an original and interesting idea, it is a benefit to the community to point out the fact that standard discrete corruption processes have unnecessary transitions in them and that the same $q(x_t | x_0)$ distribution can be obtained by simply switching between a data token and a noise token. The idea to condition on the transition time itself within the framework also enables some significant simplifications for general styles of corruption whereas in the past this advantage may have only been noticed for absorbing state processes. The paper is well written, it is fairly easy to get a good understanding of the proposed method on a first read of the paper and this is helped by the fact that the authors move some nuances and complexity to the appendix. Effort has been made to make the main text readable and intuitive which is greatly appreciated. I believe the paper will have some impact in the community because it is a quick win when users implement a discrete diffusion model. Instead of the standard sampling procedure of calling the network T times, users can switch to the proposed (quite simple in reality) algorithm and step directly from transition to transition without needing to change much implementation and gain a lot of speed up over the naive algorithm.
Weaknesses
I think there should be some discussion relating to quite a simple baseline that can be implemented for the absorbing state case. One can sample an absorbing state diffusion model in the same way as a standard discrete diffusion model, by stepping from each timestep to the next, however, instead of carrying out a forward pass of the neural network for every timestep, you first check if any tokens perform a transition and only if at least one token transitions, you then do the forward pass. This is possible in the absorbing state case because the unmasking rate is independent of the neural network output. Therefore, this simple algorithm would have the same stated advantages as your method where at most the neural network is called N times but if T is less than N, it will be called T times. I see that for other diffusion styles, your algorithm is fundamentally different due to conditioning on the transition time, however, in the absorbing state case, it seems very similar to this simple method. How can you explain the fact that you have better performance in terms of sample quality than the baselines you compare to? In your method, you propose no methodological advancement that should improve sample quality as your method is to speed up sampling to make sure the neural network is only called an appropriate number of times. Especially for a large number of timesteps, in Tables 2 and 3, you get across the board improvement, but your algorithm should be very similar to a standard discrete diffusion model in this regime but simply with fewer network evals. For your text8 experiment, you say you use a 9e7/5e6/5e5 train/val/test split however I believe this is incorrect because this only adds up to 9.55e7 tokens but the text8 dataset contains 1e8 tokens. This may be inherited from a typo in https://arxiv.org/pdf/2107.03006 pg.25 but in a more recent paper https://arxiv.org/pdf/2308.07037 pg 45, the test set is 5e6 tokens. Please confirm which size of test set you used. The names of the method seem to be slightly confused, for example on Figure 1, a DNDM-T is referenced but this is never actually defined in the full text.
Questions
In the end, do you think it will be possible to move beyond the idea of a time variable altogether? Since the final sampling algorithm steps from transition to transition, it seems that the more important variable is which tokens become denoised, in what order, and how many in one go. This is decoupled from time through your algorithm so perhaps there is even more simplification to be made. Do you think it is possible to learn the transition times on a per dimension basis? This could be useful to train models that can generate tokens in an intelligent ordering rather than currently, the order of generation is completely decided before any tokens have been generated when the transition times are sampled and the ordering is completely uniform over all orderings of the dimensions.
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
The authors adequately discuss the limitations in the appendix.
Thank you for your support and the increased score. We appreciate your positive feedback on our rebuttal.
Summary
This paper presents the non-Markov process for the discrete diffusion to reduce the sampling time. The authors present the transition time to de-randomize the sampling process and study the non-Markov processes from finite to infinite step sampling. The conditional text generation and unconditional text generation results demonstrate the effectiveness of the proposed method.
Strengths
1. The writing of the article is very clear and easy to understand. 2. Compared with the image field, discrete diffusion is more noticeable in the text field. So I think the conditional text generation and unconditional text generation experiments are sufficient.
Weaknesses
**W1**: The authors claim that Eq.(1) and Eq.(6) are different because $w_t$ in Eq.(1) is independently drawn from the noise distribution $q_{noise}$ and $w$ in Eq.(6) is time-invariant. But, $q_{noise}$ is a Dirac distribution for the absorbing diffusion and $w_t=w$ where $t=1, \dots T$. So Eq.(1) and Eq.(6) are equal for the absorbing diffusion, which means the proposed non-Markov process is the same as the Markov process. **W2**: Besides W1, we can further deduce that for the absorbing process, the proposed DNDM sampling algorithm is equivalent to the original sampling algorithm of the Markov process. For the origin Markov process, given $x_t$，we first sample $x_0 \sim p_{\theta}(x_0|x_t)$ and sample $x_{t-1} \sim q(x_{t-1}|x_t, x_0)$ as shown in Eq.(4). I use $[M]$ to represent the absorbing state. \begin{align} q(x_{t-1}|x_t, x_0) = \frac{q(x_t|x_{t-1}, x_0)q(x_{t-1}|x_0)}{q(x_t|x_0)} = \frac{q(x_t|x_{t-1})q(x_{t-1}|x_0)}{q(x_t|x_0)} \end{align} Firstly, if $x_t$ is not the absorbing state, we have that $x_{t-1}=x_t$ because $q(x_t =a| x_{t-1} \neq a) =0$ where $a \neq [M]$. Secondly, if $x_t$ is the absorbing state, based on that $q(x_{t-1}=[M]|x_0)=1- \alpha_{t-1}$, $q(x_{t-1}=x_0]|x_0)=\alpha_{t-1}$, $q(x_t=[M]|x_{t-1}=[M])=1$ and $q(x_t=[M]|x_{t-1} \neq [M]) = 1 - \beta_t = 1 - \frac{\alpha_t}{\alpha_{t-1}}$, we can get: \begin{align} q(x_{t-1}=[M]|x_t=[M], x_0) = \frac{1- \alpha_{t-1}}{1 - \alpha_t}, q(x_{t-1}=x_0|x_t=[M], x_0) = \frac{\alpha_{t-1} - \alpha_{t}}{1 - \alpha_t} \end{align} Based on the above analysis, the sampling process of the absorbing Markov diffusion can be simplified as: we sample starting from an all $[M]$ sequence, and during the sampling, we sample $x_0 \sim p_{\theta}(x_0|x_t)$. If $x_t=[M]$, $x_{t-1}$ will stay the $[M]$ state with probability $\frac{1- \alpha_{t-1}}{1 - \alpha_t}$ and transfer to $x_0$ with probability $\frac{\alpha_{t-1} - \alpha_{t}}{1 - \alpha_t}$. If $x_t \neq [M]$, it will stay unchanged. In order to further illustrate the relationship with DNDM sampling, I denote the first time $x_t$ transitions from $[M]$to a non-$[M]$ state as $\tau$ (consistent with the transition time in this paper). We can deduce that $p(\tau=k) =\frac{\alpha_{k-1} - \alpha_{k}}{1 - \alpha_k} \prod_{t=T}^{t=k+1} \frac{1- \alpha_{t-1}}{1 - \alpha_t}=\alpha_{k-1} - \alpha_{k}$. $p(\tau=k)$ and Theorem 3.5. further verified that the proposed Non-Markov method is the same as the original Markov method for absorbing diffusion. **W3**: The proposed non-Markov method of multinomial diffusion is the same as the method in DDIM[1], Appendix A but with a different formulation. We can use the $p(\tau=k)$ in W2 to further verify it. In conclusion, this paper presents a non-Markov process for the multinomial diffusion and absorbing diffusion to accelerate the sampling of origin method with Markov processes, this is the main contribution of this paper. However, for the multinomial diffusion, the relationship with the DDIM[1] (Appendix A) is not clearly stated. For the absorbing diffusion, the non-Markov processes are the same as the Markov processes. If I misunderstand your approach, please feel free to figure it out, and I will adjust my score. [1] DENOISING DIFFUSION IMPLICIT MODELS, ICLR2021
Questions
1. In line 281~282, the authors denote RDM and RDM-k as the sampling method with and without top-k selection, is this a typo? 2. In the experiment, do you use a pre-trained model or train it yourself? 3. The authors claim that they use a model consisting of an encoder and a decoder. This is confusing, do you remove the causal mask in the transformer decoder? For the unconditional text generation, what is the input of the encoder?
Rating
4
Confidence
4
Soundness
2
Presentation
3
Contribution
1
Limitations
yes
Thank you for your feedback and for acknowledging the resolution of Q1, Q2, and Q3. We address your remaining concerns regarding **W1**, **W2**, and **W3** as follows: *** **W1**. We appreciate the author's emphasis that the proposed methods significantly reduce the number of function evaluations from T to much less than T. However, for Markov diffusion, we can also use far fewer than T steps for sampling as follows: $$p_\theta(x_s|x_t) = \int q(x_s|x_t,x_0)p_\theta(x_0|x_t)$$ where $s < t$. The above expression has been widely used in Markov diffusion without further proof [1, 2]. Therefore, I think that the authors' emphasis on DNDM achieving sampling in fewer than T steps is a minor contribution. **A1**. The method you mention is a standard technique to calculate the reverse transition probability between any two-time steps, $s$ and $t$. While it's true that diffusion models can use $p_\theta(x_s|x_t) = \int q(x_s|x_t,x_0)p_\theta(x_0|x_t)$ to accelerate the sampling process, choosing good s and t rigorously while preserving the sample quality is highly nontrivial. For example, if you do uniformly downsampling to get a set of time steps $0, 2, 4, \dots, T$, you can indeed skip many time steps, but you cannot guarantee the resulting samples are of high quality due to discretization error. Our algorithm for DNDM provides a provable approach to select the sampling steps for each token while maintaining high sample quality. Instead of uniformly skipping time steps across all tokens, we only skip those deemed unimportant, i.e., not in the transition time set. We denote the transition time for the n-th token in the sequence $x_n$ to be $\tau_{n}$ where $\tau_n$ is the transition time for the token $x_n$. And further denote the transition time set $\mathcal{T}:= \\{\tau\_{n}\\}\_{n=1}^{N}$. This set captures the key time step when each token transitions from noise to the target distribution. Given the transition times $\tau_{n} \in \mathcal{T}$, our DNDM can be written as: $x_{t-1,n} = \mathbb{1}(\tau_n=t)x_{0,n} + \mathbb{1}(\tau_{n}\not= t)x_{t,n}$. Our algorithm can be written as ```python def sample(x_t, t, transition_times): # Only update tokens at their specific transition times if t in transition_times: x_0_pred = predict_x0(x_t, t) x_{t-1} = update_tokens(x_t, x_0_pred, t, transition_times) else: x_{t-1} = x_t return x_{t-1} ``` In conclusion, although sampling with fewer than T steps is crucial for accelerating reverse sampling, simply reducing the number of time steps does not necessarily preserve sample quality. Our DNDM offers a rigorous and adaptive method for reducing sampling steps by precomputing transition times and overcoming the limitations of uniform downsampling or other heuristic approaches. ***
**W2**. My main concern is that for the absorbing process, regardless of the number of sampling steps (whether equal to or less than T), the proposed DNDM sampling algorithm is equivalent to the original sampling algorithm of the Markov process, as indicated in W1 and elaborated upon in W2. I believe my main concern has not been directly addressed. **A2**. First of all, let's recall the forward processes of D3PM and DNDM as follows: $$x_{t} = b_{t}x_{t-1} + (1-b_t)w_t, \forall t = 1 \dots T, \qquad \text{D3PM, Eq 1}$$ $$x_{t} = b_{t}x_{t-1} + (1-b_t)w, \forall t = 1 \dots T . \qquad \text{DNDM, Eq 6}$$ The only difference between Equation 1 and Equation 6, is $w_t$ vs. $w$. Since for absorbing diffusion, $w_{t} = w = [Mask]$, D3PM and DNDM are indeed equivalent. However, for multinomial diffusion or other diffusion processes, $w_t \neq w$, D3PM and DNDM are different. In addition, even for absorbing diffusion, our proposed reverse sampling algorithm for DNDM is still different from that for D3PM. To elucidate the key differences between the sampling algorithm in DNDM and that in D3PM for absorbing diffusion, let's directly compare the algorithms: - For the D3PM-Absorb algorithm: We begin with an all [M] sequence. At each time step $t$, we sample $x_0 \sim p_{\theta}(x_0|x_t)$. If $x_t=[Mask]$, $x_{t-1}$ transitions to $[Mask]$ with probability $(1-\alpha_{t-1})/(1-\alpha_t)$ and to $x_0$ with probability $(\alpha_{t-1} - \alpha_t)/(1-\alpha_t)$. If $x_{t}\not= [Mask]$, it remains unchanged. - For the DNDM-Absorb algorithm: We also start with an all $[Mask]$ sequence, but crucially, we first determine the transition time set. During sampling, if $x_t=[Mask]$, the transition probabilities for $x_{t-1}$ are identical to D3PM. However, we only sample $x\_0 \sim p_{\theta}(x\_0|x_t)$ when at least one token needs to change, as determined by our pre-computed transition set. This selective sampling is the key to our algorithm's efficiency. Therefore, you can see that DNDM will skip many steps during the sampling process to avoid function evaluation and save computational cost. A natural question is how many time steps can be skipped. Let's do the calculation as follows. For a specific time t and token position n, the token will change at time $t-1$ only if: - It hasn't already changed (probability: $\Pi_{s=T}^{t}\frac{1-\alpha_s}{1-\alpha_{s+1}} = 1-\alpha_t$) - It will transfer to $x_0$ (probability: $\frac{\alpha_{t-1} - \alpha_t}{1-\alpha_t}$) Thus, the probability of $n$-th token changing at time t-1 is $(1-\alpha_t)\cdot \frac{\alpha_{t-1}-\alpha_t}{1-\alpha_t} = \alpha_{t-1} - \alpha_t$. Consequently, the probability that no tokens change at time t for the entire sequence is $\big(1 - (\alpha_{t-1}-\alpha_{t})\big)^{N}$ where $N$ is the sequence length. These are precisely the time steps that our DNDM algorithm will skip to save computational time, unlike D3PM, which does function evaluation every time step. To sum up, even though the forward process of DNDM is the same as that of D3PM for absorbing diffusion, our DNDM approach introduces a clever and provable algorithm design in the sampling process by pre-computing the transition time set and selectively applying function evaluations. This distinguishes DNDM from D3PM algorithm, offering a more computationally efficient approach to inference in discrete diffusion. ***
**W3**. Regarding the relationship between DNDM and DDIM, my concern remains unresolved. I believe that DNDM is a special case of DDIM (Appendix A). Specifically, when the hyperparameter $\sigma_t = \frac{1-\alpha_{t-1}}{1-\alpha_{t}}$ in DDIM (Appendix A), DDIM and DNDM become equivalent. When $\sigma_t = \frac{1-\alpha_{t-1}}{1-\alpha_{t}}$, the probability that $x_{t-1} = x_t$ is $\frac{1-\alpha_{t-1}}{1-\alpha_{t}}$, while the probability that $x_{t-1} = x_0$ is $\frac{\alpha_{t} - \alpha_{t-1}}{1-\alpha_t}$. In the rebuttal, the authors claim that DDIM and the proposed DNDM are "analogous." But actually, we can prove that they are equivalent based on W2. [1] Bao et al. "Analytic-DPM: an Analytic Estimate of the Optimal Reverse Variance in Diffusion Probabilistic Models." ICLR2022 [2] He et al. "DiffusionBERT: Improving Generative Masked Language Models with Diffusion Models." ACL2023. **A3**. While there are similarities between DNDM and DDIM (Appendix A), they are fundamentally different models, and DNDM is not a special case of DDIM. DNDM introduces a framework specifically designed for discrete spaces, while DDIM was originally developed for continuous diffusion models. Let me clarify the key differences for multinomial diffusion: - DDIM: By eq (19) in Appendix A of DDIM paper, $q(x_{t-1}|x_t, x_0) = \text{Cat}(\sigma_t x_t + (\alpha_{t-1} - \sigma_t \alpha_t)x_0 + ((1 - \alpha_{t-1}) - (1 - \alpha_t)\sigma_t)1_K).$ Even with $\sigma_t = \frac{1-\alpha_{t-1}}{1-\alpha_t}$, the process remains stochastic: $q(x_{t-1}|x_t, x_0) = \text{Cat}(\sigma_t x_t + (1- \sigma_t)x_0 )$. This means at every step, there's a probability of choosing $x_0$, regardless of whether it has transitioned to $x_0$ or not. Unlike Absorbing discrete diffusion, no [Mask] exists in multinomial diffusion. Therefore, DDIM cannot distinguish whether $x_t$ already equals $x_0$. In particular, although the sampling process becomes less stochastic in the DDIM setting, it will still be predicted $x_0$ with high probability $1-\sigma_t = \frac{\alpha_{t-1}- \alpha_t}{1-\alpha_t}$. - DNDM: Achieves full de-randomization using transition time $\tau: x_{t-1} = \mathbb{1}(\tau = t)x_0 + \mathbb{1}(\tau \not= t)x_{t}$ (Equation 8 in our paper). Here, $\tau$ follows $P(\tau = t) = \alpha_{t-1} - \alpha_t < \frac{\alpha_{t-1}- \alpha_t}{1-\alpha_t}$. Such crucial difference allows DNDM to achieve full de-randomization once $\tau$ is sampled, leading to a deterministic evolution that DDIM cannot replicate. - Sanity Check via Concrete Example: For sampling $x_1$ based on $x_2$, consider the probability of calling $\hat{x}\_0 \sim p_{\theta}(\hat{x}\_0|x_t)$. DDIM: P(call $\hat{x}\_0$) = $\frac{\alpha_{1} - \alpha_2}{1-\alpha_2}$. DNDM: P(call $\hat{x}\_0$) = $\alpha_1 - \alpha_2 $. Crucially, $\alpha_1 - \alpha_2 < (\alpha_1 - \alpha_2)/(1-\alpha_2)$, because $\alpha_2 < 1$. The above illustration shows that DNDM is not a special case of DDIM. We say that DNDM is analogous to DDIM because both of them are Non-Markov models. We will add a discussion to clarify this point in the revision to avoid any confusion. ***
Thank you for your response！ I understand that DNDM is not a special case of DDIM (Appendix A), thanks! I believe that a comparison between DNDM and DDIM experiments will be very interesting. For the absorbing process, the author provides a detailed explanation of the differences between the proposed DNDM and the original sampling algorithm of the Markov process. For each sampling step (e.g., $p_{\theta}(x_s|x_t)$, s<t), the DNDM and D3PM methods are consistent. The advantage of the proposed DNDM lies in how it selects which time steps should be omitted. **It's important to emphasize that this advantage of DNDM does not stem from the non-Markov process as claimed by this paper. For the absorbing process, the Markov and non-Markov processes are entirely identical**. In both this paper and references [1, 2], the absorbing process has consistently outperformed the multinomial process and has garnered increasing attention. Therefore, **I hope that the claim in this paper that the non-Markov process can accelerate sampling of absorbing diffusion does not mislead the community, and I remain inclined to reject it.** This paper presents promising experimental results. If the authors can accurately explain the reasons behind the effectiveness of DNDM, which would require substantial revisions, it will undoubtedly significantly enhance the quality of the paper. [1] Austin et al. "Structured denoising diffusion models in discrete state-spaces." NeurIPS 2021. [2] Lou et al. "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution." ICML2024.
Thank you for your further feedback and for acknowledging the technical and empirical contributions of our paper. We're glad that we have resolved all of your misunderstandings and questions. Note that the modifier Non-Markov in our algorithm name refers to both the time-invariant noise $w$ and the predetermined transition time $\tau$ (See Eq. (7) in the paper). To emphasize the importance of the predetermined transition time in DNDM, we will add a sentence in the abstract: "The proposed DNDM model naturally induces the predetermined transition time set, which enables a training-free sampling algorithm that can accelerate a large family of discrete diffusion models." We will also highlight this in the paper. While we believe we have clearly explained the reasons behind the effectiveness of DNDM in Sections 3.1 and 3.2 with comprehensive pseudo-algorithms in the paper (see Algorithms 1-4), we will also incorporate the clarifications from our rebuttal discussion into the final version. Given that we have resolved all of your concerns and questions in your review, and we believe the promised changes would not be a major revision, we would greatly appreciate it if you could consider raising your score in light of these points. In particular, a score of 3 indicates 'technical flaws, weak evaluation, inadequate reproducibility, and/or incompletely addressed ethical considerations.' We believe our paper does not fit this description and deserves a higher rating.
Thank you for incorporating the clarifications from our rebuttal discussion into the final version. I believe this is crucial for clearing up any misunderstandings for the readers. However, I find using the modifier "Non-Markov" completely unacceptable. This term appears frequently in the title, abstract, and throughout the main text. As I have repeatedly emphasized in our previous discussions, the original Markov diffusion and the proposed non-Markov diffusion are identical for the more effective and widely recognized absorbing process. The non-Markov assumption is redundant and misleading. After several days of careful consideration and thoroughly reading the comments from other reviewers, I still lean towards rejecting this paper.
Thank you for your candid feedback and for acknowledging the improvements in our paper. Regarding your remaining concern 'Non-Markov', we would like to provide further clarification on why this terminology is accurate and necessary for our work: - Our model handles a broader set of discrete diffusion models beyond the absorbing process. In general cases, including multinomial diffusion, our forward process is non-Markovian. - The Non-Markov modifier refers to both the time-invariant noise 𝑤 and the predetermined transition time 𝜏 (Eq. 7). Only when w = [Mask], which is deterministic, would the distribution for the absorbing state become Markovian. However, the non-Markovian nature is still fundamental to our DNDM model's full generality, and it provides readers with an accurate understanding of the process's properties and how transition time gets introduced. - The use of 'Non-Markov' in our terminology aligns with similar practices in the field, accurately highlighting key characteristics of our model that deviate from strict Markovian properties, even though DNDM can degenerate to Markovian process under specific settings. In the DDIM framework, for instance, when $\sigma_t = \sqrt{(1-\alpha_{t-1})/(1-\alpha_t)}\sqrt{1-\alpha_t/\alpha_{t-1}}$, the diffusion process becomes Markovian, and the forward/generative process becomes a DDPM. Similarly, our use of 'Non-Markov' emphasizes the general case while acknowledging special conditions where Markovian properties may emerge. The added clarifications in our paper should help readers understand the specific characteristics of our approach and its relationship/differences to Markovian processes. **With that being said, we are open to changing the term 'Non-Markov' if it would persuade you to raise your rating to the acceptance level. If you have any suggestion for the replacement of 'Non-Markov', we would be happy to take it**.
Summary
The paper introduces a discrete non-Markov diffusion model (DNDM) aimed at accelerating the sampling process in discrete diffusion models. The proposed method reduces the number of neural network function evaluations to speed up the sampling process while maintaining sample quality. The paper explores the transition from finite to infinite step sampling, providing new insights into bridging the gap between discrete and continuous-time processes. Experiments on natural language generation and machine translation tasks illustrate the competitive performance of the method in terms of speed and quality compared to existing methods.
Strengths
* The introduction of a discrete non-Markov diffusion model (DNDM) provides a new method for accelerating the sampling process in discrete diffusion models in a training-free manner. It reduces the number of neural network function evaluations, enhancing the efficiency of the sampling process to speedup by 3x for 50 steps. * The authors conducted extensive experiments on natural language generation and machine translation tasks, demonstrating the effectiveness of the proposed method, for both multinomial and absorbing diffusions.
Weaknesses
* The method involves a complex process that might be challenging to easily follow and implement. More details or visualizations on how the transition time distribution is determined and whether it can be adapted for different types of discrete diffusion models will be helpful for a better understanding of the motivation and methodology. * The comparison with other acceleration methods is not very convincing, especially at a practical smaller number of sampling steps. Instead of RDM baseline, how does the proposed method compare with other existing acceleration techniques for discrete diffusion models in terms of both efficiency and quality? * While the method is tested on natural language generation and machine translation tasks, its applicability to other modalities such as image or video generation is not unknown, which might limited the scope of the proposed method.
Questions
Suggest to address concerns in the weakness section.
Rating
5
Confidence
3
Soundness
3
Presentation
2
Contribution
3
Limitations
yes
Thank you for your valuable feedback and for taking the time to consider our response. We sincerely appreciate your acknowledgement of our improvements on the simplicity and ease of implementation of the proposed method, as well as the additional experiments with smaller sampling steps. We would like to address your remaining concerns as follows: - We appreciate your point about the phrasing of our novelty claims during previous discussion. We agree to tone down any perceived claim of being the "first training-free acceleration method". To clarify, we developed a training-free acceleration method specifically designed for finite-step discrete diffusion models. We'd like to note that we didn't include such a phrase as "first training-free acceleration method" in our submission. - Additional Experiment on DDIM Appendix A: Our focus was on accelerating finite-step discrete diffusion models, which differ fundamentally from continuous diffusion models. Techniques primarily designed for continuous diffusion are not directly applicable to discrete diffusion, like multinomial diffusion and absorbing diffusion. While DDIM proposes a version for multinomial diffusion in Appendix A, it doesn't consider the transition time or provide any code or experiments. Inspired by your feedback, we've implemented DDIM Appendix A ourselves and conducted additional experiments. We've included results both with and without top-k sampling (denoted by '-k' in the table headers). Below are the results for IWSLT14 with a wide range of sample steps in multinomial diffusion generation (These could serve as additional results for Table 2 in our submission): | Steps | DDIM-multi BLEU | DDIM-multi Time (s) | DNDM-multi BLEU | DNDM-multi Time (s) | |-------|-----------------|---------------------|-------------------|----------------------| | 5 | 28.88 | 30.2 | 28.04 | 28.1 | | 10 | 30.46 | 55.8 | 30.57 | 44.4 | | 15 | 30.87 | 80.1 | 30.77 | 50.6 | |25 | 31.30 | 130.4 | 30.95 | 52.9| |50 | 31.63 | 257.2 | 31.45 | 83.9| |1000 | 31.79 | 5064.8| 31.82 | 191.3| | Steps | DDIM-k-multi BLEU | DDIM-k-multi Time (s) | DNDM-k-multi BLEU | DNDM-k-multi Time (s) | |-------|-----------------|---------------------|-------------------|----------------------| | 5 | 28.93 | 31.1 | 30.30 | 28.3 | | 10 | 30.69 | 56.7 | 31.79 | 44.3 | | 15 | 30.85 | 81.5 | 32.14 | 50.1 | |25 | 31.38 | 132.7 | 32.30 | 52.6| |50 | 31.64 | 260.1 | 32.80 | 93.2| |1000 | 31.89 | 5121.3 | 33.15 | 191.5| These results suggest that compared with DDIM (Appendix A), DNDM achieves comparable or better performance with reduced computation time across various step sizes, with the advantage becoming more significant as the number of steps increases. This scalability makes our approach particularly valuable for tasks requiring higher quality generation and more computational steps. We appreciate your careful consideration and are open to suggestions on how to better position our work within the broader context of diffusion model acceleration techniques. Thank you again for your valuable feedback.
Please respond to authors' rebuttals
Dear Reviewers, Thanks for writing your reviewers of the paper. Now the authors' rebuttals are in. Please go through them and see if they have addressed your questions. Please start discussions with the authors if you have further comments. Regards, AC
Thank you for your response. I believe Q1, Q2, and Q3 have been resolved, but I think the issues in W1, W2, and W3 still exist. **R1**. I appreciate the author's emphasis that the proposed methods significantly reduce the number of function evaluations from T to much less than T. However, for Markov diffusion, we can also use far fewer than T steps for sampling as follows: \begin{align} p_{\theta}(x_s|x_t) = \int q(x_s|x_t, x_0) p_{\theta}(x_0|x_t) \end{align} where $s<t$. The above expression has been widely used in Markov diffusion without further proof [1, 2]. Therefore, I think that the authors' emphasis on DNDM achieving sampling in fewer than T steps is a minor contribution. **R2**. My main concern is that for the absorbing process, regardless of the number of sampling steps (whether equal to or less than T), the proposed DNDM sampling algorithm is equivalent to the original sampling algorithm of the Markov process, as indicated in W1 and elaborated upon in W2. I believe my main concern has not been directly addressed. **R3**. Regarding the relationship between DNDM and DDIM, my concern remains unresolved. I believe that DNDM is a special case of DDIM (Appendix A). Specifically, when the hyperparameter $\sigma_t = \frac{1-\alpha_{t-1}}{1 - \alpha_t}$ in DDIM (Appendix A), DDIM and DNDM become equivalent. When $\sigma_t = \frac{1-\alpha_{t-1}}{1 - \alpha_t}$, the probability that $x_{t-1}=x_t$ is $\frac{1-\alpha_{t-1}}{1 - \alpha_t}$, while the probability that $x_{t-1}=x_0$ is $\frac{\alpha_t-\alpha_{t-1}}{1 - \alpha_t}$. In the rebuttal, the authors claim that DDIM and the proposed DNDM are "analogous". But actually, we can prove that they are equivalent based on **W2**. [1] Bao et al. "Analytic-DPM: an Analytic Estimate of the Optimal Reverse Variance in Diffusion Probabilistic Models." ICLR2022 [2] He et al. "DiffusionBERT: Improving Generative Masked Language Models with Diffusion Models." ACL2023.
Response to Authors
I appreciate the clear and detailed rebuttal from the authors. The additional experiment exploring token orderings for the corruption is also very interesting and it will be a nice addition to the paper. I will increase my score to 7.
Answer to rebuttal
I thank the authors for the comprehensive answers to the questions. I appreciate the promise to add more discussion on the connections to prior work, and the additional experiments on low step counts. Given that these were the main concerns, I will raise the score, although it would be better if the extended discussions had been in the original paper and if there were some additional speed-up tricks that make the method clearly stand out from previous work on speeding up discrete diffusion. The new theoretical approach is interesting as well.
Thank you for your valuable feedback. We sincerely hope that we have adequately addressed your questions and concerns. Specifically, - We have elaborated on DNDM's simplicity and ease of implementation. As a training-free approach, DNDM integrates seamlessly with existing discrete diffusion models. We've provided comprehensive pseudo-algorithms in the paper and detailed explanations of the transition time distribution in Appendix C and Figure 3. - Regarding DNDM's performance across various step sizes, we've demonstrated its effectiveness for both moderate and high step counts. Our additional experimental results for IWSLT14 with fewer sample steps demonstrate DNDM's capabilities even at lower step counts. - We've added the comparison with other acceleration techniques by highlighting DNDM's unique feature as the first training-free acceleration method specifically designed for finite-step discrete diffusion models. We've also discussed its potential applicability to other discrete data modalities beyond text generation. We sincerely hope our response adequately addresses your questions and provides clarity on our method. Thank you for your time and careful consideration of our work.
Thank you to the authors for the detailed response on the simplicity and ease of implementation of the proposed method, as well as the additional experiments in the small number of sampling step regimes. It would still be interesting to see comparisons with other fast sampling methods beyond the RDM baseline, such as DDIM or others. Additionally, while I appreciate the novelty of the approach, there are already many training-free acceleration methods in the literature, even though they may not have been tested in the specific problem setting of this paper. Therefore, I suggest toning down the claim of being the "first training-free acceleration method." After reading other reviews and careful consideration, I prefer to keep my original rating.
Decision
Accept (poster)