Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:02:01

Abstract: Discrete diffusion models with absorbing processes have shown promise in language modeling. The key quantities to be estimated are the ratios between the marginal probabilities of two transitive states at all timesteps, called the concrete score. In this paper, we reveal that the concrete score in absorbing diffusion can be expressed as conditional probabilities of clean data, multiplied by a time-dependent scalar in an analytic form. Motivated by the finding, we propose reparameterized absorbing discrete diffusion (RADD), a dedicated diffusion model that characterizes the time-independent conditional probabilities. Besides its simplicity, RADD can reduce the number of function evaluations (NFEs) by caching the output of the time-independent network when the noisy sample remains unchanged in a sampling interval. Empirically, RADD is up to 3.5 times faster while consistently achieving a better performance than the strongest baseline.
Built upon the new factorization of the concrete score, we further prove a surprising result that the exact likelihood of absorbing diffusion can be rewritten to a simple form (named denoise cross-entropy) and then estimated efficiently by the Monte Carlo method. The resulting approach also applies to the original parameterization of the concrete score. It significantly advances the state-of-the-art discrete diffusion on 5 zero-shot language modeling benchmarks (measured by perplexity) at the GPT-2 scale.

Main paper: 
 introduction: 
 Auto-regressive models [1, 2, 3] have dominated the area of language modeling for many years. In particular, such models significantly benefit from large-scale transformers [4] and training data and have achieved remarkable progress [5, 6, 7, 8] . From a probabilistic perspective, the sequential sampling process of auto-regressive models is inefficient and limits the reasoning ability in nonsequential orders [9, 10] . Intrinsically, this is because such models characterize the joint distribution by the chain rule of probability, motivating research on developing other types of generative models for text.Diffusion models [11, 12, 13] generate data in a coarse-to-fine manner efficiently [14, 15, 16, 17, 18] and all dimensions simultaneously, providing an appealing alternative to auto-regressive models.Among other efforts [19, 20, 21, 22, 23, 24, 20, 25, 26, 27, 28, 29] (see Section 5 for a comprehensive discussion), score entropy discrete diffusion (SEDD) [29] has shown promise in text generation. In particular, SEDD has achieved comparable results to auto-regressive models on 5 zero-shot language modeling benchmarks at the GPT-2 scale. Meanwhile, SEDD can reduce the number of function evaluations (NFEs) in sampling and fulfill text conditioned on prompts at different positions.Technically, SEDD employs a discrete-state (absorbing) Markov process that adds noises to data by randomly replacing a token with a mask token [M] and then learns a reverse process to denoise from an entirely masked sentence. The key quantities to be estimated in SEDD are the ratios between the marginal probabilities of two transitive states at all timesteps, called the concrete score. SEDD also Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.proposes a "scaling trick" (see details in Section 3) that scales the output of the score estimation by a factor. The trick has been proven very effective in practice yet not fully understood in theory [29] .One of our main contributions is to reveal that the concrete score in absorbing diffusion can be expressed as conditional probabilities of clean data, multiplied by a time-dependent scalar in an analytic form. Our finding theoretically explains the benefits of the scaling trick as a reparameterization for better optimization. Motivated by the finding, we propose reparameterized absorbing discrete diffusion (RADD), a dedicated diffusion model that characterizes the time-independent conditional probabilities by removing the time embedding from the score estimation in SEDD. Besides its simplicity, RADD can significantly reduce the NFEs by caching the output of the time-independent network when the noisy sample remains unchanged in a sampling interval (see Fig. 1 ).Built upon the new factorization of the concrete score, we further prove a surprising result that the exact likelihood of absorbing diffusion can be rewritten to a simple form (named denoise crossentropy, DCE) and then estimated efficiently by the Monte Carlo method. To establish the theory, we apply a change of variable from the time t to the probability that a single-dimensional token is masked at time t in the forward process. By integrating the probability variable analytically, we show that DCE enumerates all orders to decompose the joint distribution auto-regressively and accumulates log densities of all conditional distributions in every order, finishing the proof. Such theoretical findings enable exact likelihood evaluation and optimization for both the original parameterization of absorbing diffusion [29] and the proposed RADD.Empirically, RADD is up to 3.5 times faster while consistently achieving a better performance than the strongest baseline, i.e. SEDD with the scaling trick [29] . Further, the DCE loss applies to both RADD and SEDD for precise likelihood evaluation. It significantly advances the state-of-the-art discrete diffusion (i.e. SEDD [29] ) on 5 zero-shot language modeling benchmarks (measured by perplexity) at the GPT-2 scale. The empirical evidence validates our theoretical findings.In summary, this paper has several contributions:• Deeper understanding of discrete diffusion: Both the factorization form of the concrete score and DCE loss for the exact likelihood computation reveal important yet overlooked theoretical properties of absorbing discrete diffusion, which explain the mysterious scaling trick, provide practice guidance, and may inspire future work.• Simplification: By removing the time conditions, we reparameterize the model to focus on a time-independent conditional probability, simplifying the existing model.• Efficient sampling: Leveraging the reparameterized form, RADD with a caching strategy is consistently faster while achieving a better performance than the strongest competitor.• Improved likelihood evaluation: The exact likelihood evaluation approach significantly advances the state-of-the-art discrete diffusion on 5 zero-shot language modeling benchmarks (measured by perplexity) at the GPT-2 scale. 
background: 
 In this section, we present preliminaries on continuous-time discrete diffusion models. We start with the one-dimensional case in Section 2.1, followed by the multi-dimensional case in Section 2.2.Let x denote a single dimensional sample with possible values in {1, . . . , N }. A continuous-time discrete Markov chain at time t is characterized by a transition rate matrix Q t as followsEQUATIONwhere Q t (x, x) is the (x, x) element of transition rate matrix Q t , denoting the transition rate from state x to state x at time t. Equivalently, we can directly define Q t (x, x) asEQUATIONGiven the above definition, denote P s→t (x, x) := p t|s (x|x). The following Kolmogorov's forward equation holds [26, 30] :EQUATIONIn practice [26, 29] , Q t is parameterized as σ(t)Q, where σ(t) is a scalar function and Q is a constant matrix. In this case, the solution to Eq. ( 2.3) can be solved analytically as P s→t = exp ((σ(t) -σ(s))Q), where σ(t) = t 0 σ(s)ds and exp is the matrix exponential. Therefore, we can directly sample x t from x s in one step for any t > s.Further, Q is often designed to diffuse towards a uniform distribution or an absorbing state [M] .Recent work [20, 26] suggests that the absorbing matrix achieves better empirical performance.Besides, as detailed in Section 3, the specific structure of the absorbing matrix can be leveraged to improve performance and accelerate sampling. Therefore, we focus on the absorbing matrix as follows:Q absorb =       -1 0 • • • 0 1 0 -1 • • • 0 1 . . . . . . . . . . . . . . . 0 0 • • • -1 1 0 0 • • • 0 0       . (2.4)The time reversal of the forward process is characterized by a reverse transition rate matrix Qt [31, 32] ,whose element from state x to state x is given byEQUATIONSimulating the reverse process requires to learn the reverse transition rate Qt (x, x).As Q t (x t , xt )is known, it is sufficient to estimate the concrete score ] xt∈X [28] . Denoising score entropy (DSE) [29] is an effective objective to train the score networkEQUATION) where K(a) := a log a -a. In particular, the DSE loss in Eq. (2.6) is an evidence lower bound (ELBO) of the negative log-likelihood with an unknown gap. Nevertheless, existing work [29] still employs it for training and likelihood evaluation.After training, sampling from the model can be understood as discretizing the following processEQUATIONwhere dt is an infinitesimal negative timestep and the concrete score is replaced by the score network.Existing samplers include the Euler method, Gillespie method, and Tweedie τ -leaping, as detailed in Appendix D.The multi-dimensional cases consider a state space of size d like X d = {1, . . . , n} d . We denote the sample as a sequence of one-dimensional data, i.e. x = x 1 . . . x d . The transition matrixQ t ∈ R n d ×n dhas an exponential number of possible states, making it expensive to reverse. To alleviate this issue, existing work [26, 29] assumes independence between dimensions and each dimension is a one-dimensional diffusion process with the same transition rate matrixQ tok t ∈ R n×n .Under the independent assumption, Q t assigns zero values [26, 29] for all sequences with a Hamming distance larger than EQUATIONExisting samplers assume that each dimension is independent within a small interval ∆t and update each dimension in parallel for efficiency [29, 26] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss the limitations in the main text.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
reparameterized absorbing discrete diffusion: 
 In Section 3.1, we reveal that the concrete score of absorbing discrete diffusion can be reparameterized as conditional distributions of clean data, which enables efficient sampling by caching the output of time-independent network (see Section 3.2) and exact likelihood computation (see Section 3.3) by applying the change of variable from time to the probability of being masked in a single dimension.A key observation is that only the transition from the masked token to an unmasked token is valid in the reverse process of an absorbing discrete diffusion. In particular, according to the definition of the transition matrix of the absorbing process (see Eq. (2.4)), we have . Also, note that the concrete score always takes the value of one ifQ absorb (x i t , x i t ) = 0 for any unmasked x i t ̸ = [M] and xi t ̸ = x i t .xi t = x i t .Therefore, we only need to characterize the concrete score forx i t = [M] and xi t ̸ = [M].Interestingly, in this case, we discover that the concrete score has a simple analytic form w.r.t. to the conditional distributions of clean data, as summarized in the following Theorem 1.Theorem 1. (Analytic concrete score in absorbing case, proof in Appendix B) Forx t = x 1 t . . . x i t . . . x d t and xt = x 1 t . . . x i t . . . x d t , if x i t = [M] and xi t ̸ = [M],the concrete score at time t can be expressed as a time-independent conditional distribution at time zero multiplied by an analytic time-dependent term:p t x 1 t . . . x i t . . . x d t p t x 1 t . . . x i t . . . x d t = e -σ(t) 1 -e -σ(t) p 0 (x i t |x UM t ),where x UM t is the vector consists of all unmasked tokens of x t .One immediate implication of Theorem 1 is to theoretically explain the benefit of the "scaling trick" in existing work [29] (see Appendix C.2 therein), which significantly improves the practical performance of discrete diffusion (see Table 2 ) but has not been fully understood.In particular, the scaling trick divides the output of the score network s θ by a factor of e σ(t) -1.Equivalently, it reparameterizes s θ (x t , t) as: s θ (x t , t) = 1 e σ(t) -1 sθ (x t , t) = e -σ(t) 1 -e -σ(t) sθ (x t , t), 6DPSOLQJ6WHSV (1)(V l FDFKHGWKHRU\ XQFDFKHG FDFKHGH[SHULPHQWEQUATIONIn practice, we make a minimal modification of the score network in SEDD [29] for simplicity and fairness, detailed in Appendix F.1.Moreover, RADD also enjoys a more efficient sampling process than SEDD [29] (with or without the scaling trick) based on its simplified parameterization, as presented below.For the reverse process of an absorbing discrete diffusion, once a token is generated from [M] to an unmasked token, it never transits to another token. Therefore, for a sequence x t of length d, x t changes at most d times, irrespective of the number of sampling steps D. In the other steps, x t remains in all d dimensions. We highlight that we can cache c θ (x t ) naturally without evaluating the time-independent c θ to reduce the NFE compared to SEDD (see Appendix E for the pseudo-code, ).As shown in Fig. 2 , RADD with the caching strategy is more efficient than SEDD given any number of sampling steps, especially given large sampling steps. This is as expected because the NFE is limited within the generating sequence length.Note that the NFEs with the caching strategy is a random variable. To quantify it, we calculate the expected NFEs (abbr. E-NFEs) required in an analytic form, conditioned on the sampling method, time steps, and noise schedule. Specifically, denote l as the generating sequence length, which does not equal d generally. Given the sampling time steps{t 0 = 0, • • • , t n = T }, let N k ∈ {0, • • • , l}denote the number of changed dimensions of x in [t k-1 , t k ). Since we perform function evaluation in [t k-1 , t k ) only when x changes (i.e. N k ̸ = 0), the NFEs and E-NFEs can expressed as:EQUATIONEQUATIONFor each dimension i, let r k represent the probability that x i changes within the interval[t k-1 , t k ).As the probability is independent in different dimensions (proof in Appendix D.3), N k follows a binomial distribution with parameters l and r k . Therefore, Eq. (3.4) can be further simplified as:EQUATIONwhich applies to all samplers. Further, r k can be analytically expressed w.r.t. the time steps and noise schedule for both Euler and Tweedie τ -leaping samplers, as detailed in Appendix D.3. Taking Tweedie τ -leaping method with log-linear noise schedule [29] for example, its E-NFEs is given by:EQUATIONAppendix D.3 provides the proof. As shown in Fig. 1 , we plot the curve of Eq. (3.6) in blue, which agrees with our experiments (the red stars).As illustrated in Theorem 1, the concrete score can be understood as a rescaled conditional distribution on clean data. From this perspective, it is natural to wonder: is it possible to evaluate and optimize the exact likelihood of the model instead of the ELBO? Surprisingly, the answer is yes for both the original parameterization [29] and our new parameterization.Let q θ (x 0 ) denote the model distribution at time zero defined by s θ , or our c θ , which approximates the true distribution p 0 (x 0 ). Inspired by the cross-entropy loss in auto-regressive models, we define the denoising cross-entropy loss L T DCE (x 0 ) as:EQUATIONEQUATIONCompared with the DSE loss in Eq. (2.6), our DCE loss simply removed the terms s θ ( x, t) y and x|x0) , however, it shows that DCE loss exactly equals the negative log-likelihood of q θ (x 0 )K p t|0 (y|x0) p t|0 (with a sufficiently long process in absorbing discrete diffusion.Theorem 2. Suppose {X t } is a continuous time Markov chain with transition rate matrix Q t = σ(t)Q absorb . For a given data x 0 , if σ(t) satisfies ∞ 0 σ(τ )dτ = ∞, then the denoising cross-entropy loss defined in Eq. (3.8) with T → ∞ exactly equals the negative log-likelihood of x 0 .L ∞ DCE (x 0 ) = -log q θ (x 0 ). (3.9)The proof of Theorem 2 consists of three key steps, detailed in Appendix C.1, Appendix C.2 and Appendix C.3 respectively. In the first step, we apply a change of variable from t to λ(t) =1 -e -σ(t) , which is the probability of a token is masked from 0 to t in the forward process. Further, inspired by the factorization form discovered in Theorem 1, the denoising cross-entropy loss for both parameterizations can then be rewritten as an integral of λEQUATIONwhere p λ ( x|x 0 ) is the joint distribution induced by masking each dimension in x 0 independently with a probability λ.In the second step, we demonstrate that the integral w.r.t. λ in Eq. (3.10) can be integrated analytically, and the DSE loss can be rewritten as expectations over the number and positions of masks as follows:EQUATIONwhere we denote Xk := { x : x ∈ X and x has exact k dimensions masked by [M]} and U (•) as uniform distribution.Finally, in the third step, we prove that Eq. (3.11) enumerates all orders to decompose the joint distribution auto-regressively and accumulates log densities of all conditional distributions in every order. Therefore, it is equivalent to the negative log-likelihood of q θ :L ∞ DCE (x 0 ) = -log q θ (x 0 ). (3.12)Theorem 2 enables exact likelihood computation for both the original model s θ and our c θ , providing a more accurate measure of model performance. Take c θ for example, Eq. (3.8) can be rewritten as a form of expectation on t:L T DCE (x 0 ) = 1 T E t∼U ([0,T ]) E x∼p t|0 (•|x0) y̸ = x Q t ( x, y) - p t|0 (y | x 0 ) p t|0 ( x | x 0 ) log e -σ(t) 1 -e -σ(t) c θ (x) y .(3.13) Naturally, we can take the Monte Carlo estimation of L T DCE (x 0 ) by sampling t to approximate -log q θ (x 0 ) according to Eq. (3.13). In addition, it can be used as an efficient and valid training target for discrete diffusion models, as an alternative to the ELBO (i.e. DSE loss). For pseudo-code of training, see Appendix E. 
experiments: 
 We present the experimental setups in Section 4.1. We then evaluate the performance of accelerated generation in Section 4.2 and zero-shot perplexity on various language datasets in Section 4.3.Model. We use RADD model c θ reparameterzied as described in Section 3.1. Compared with SEDD small model, RADD model has 7M fewer parameters due to the removal of time-condition, which equates to an 8% decrease from the original 90M non-embedding parameters. We trained our RADD model c θ using denoising score entropy and denoising cross entropy, abbreviated as RADD-DSE and RADD-DCE. For SEDD small model, we employed their pre-trained model.In line with the methodology outlined by SEDD, we trained on the OpenWebText [33] dataset and tested on the LAMBADA, WikiText2, PTB, WikiText103, and One Billion Words datasets [34, 35, 36] . For data splits and data processing, we adopted the same settings and techniques as SEDD, which involves packing sentences to generate uniform-length blocks as model input.Training setup. We used the same training setup for RADD and SEDD. Specifically, we used a log-linear noise schedule where the expectation of the number of changed tokens at time t is linear with t. For simplicity, we also used the same optimization configuration as SEDD, which can be suboptimal for our RADD model and DCE loss. For more details see Appendix F.Metric. Following previous work [29] , we conduct experiments on unconditional generation and language modeling tasks. For generation, we use perplexity (PPL) on unconditional samples measured by an additional larger language model (i.e. GPT-2 large) to evaluate sample quality. To access inference efficiency, we computed the inference time on a single NVIDIA 4090 GPU with a batch size of 8 and averaged over 1024 samples. For language modeling tasks, we report the perplexity calculated on the dataset with different models. We further compare the running time for the methods in Table 1 . Across all sampling steps, RADD consistently requires the shortest sampling time and outperforms SEDD with different samplers.Quantitatively, RADD achieves a speed-up of 2.5 ∼ 3.5 times as shown in Table 1 . These results agree with the analysis of the E-NFEs in Fig. 1 , validate the effectiveness of RADD and caching strategy, and demonstrate the practical implications of our Theorem 1.According to Eq. (3.11), we can also use RADD as an auto-regressive model to generate samples in different orders, leading to worse performance as a discrete diffusion, as detailed in Appendix F.4.We present more sampling details in Appendix F.3. and the generated samples in Appendix G.1.Following SEDD, we present zero-shot perplexities on the LAMBADA, WikiText2, PTB, Wiki-Text103, and 1 Billion Words datasets [37] in Table 2 and compare the zero-shot perplexity of our model with other baseline models [20, 38, 29] .Firstly, we conduct an ablation study of the scaling trick in the middle of the Table 2 . With an absorbing process, the perplexity of the scaled version of SEDD outperforms its unscaled version, which matches our theoretical discovery in Theorem 1.Secondly, without any modification of the model, we estimate the exact likelihood of the baseline model SEDD [29] based on Theorem 2 in Table 2 . We observe that perplexity is consistently better than the ELBO of the strongest discrete diffusion models, which validates our Theorem 2.Lastly, we report the maximum likelihood training results of RADD in the last row in Table 2 . We observed that RADD-DCE outperforms RADD-DSE, but their performances are slightly worse than SEDD. This discrepancy could be because we did not search the hyperparameters and directly applied identical optimization configures as SEDD, which may be suboptimal. 
related work: 
 Continouous-state diffusion models for text generation. Several works have been proposed to apply continuous diffusion to text [19, 21, 22, 23] . Li et al. [19] use an embedding layer to map discrete tokens to a latent space and learn a continuous-state diffusion on it. Bit Diffusion [22] learns a continuous diffusion model to generate binary bits of discrete tokens. However, transforming between these continuous representations and discrete tokens by thresholding may lose information. BayesianFlow Network [23] achieves competitive log-likelihood on character-level language modeling tasks and is proven equivalent to continuous stochastic differential equations trained by denoising score matching [24] . Such models underperform auto-regressive models on standard text generation tasks.Discrete-state diffusion models for text generation. Several discrete-state diffusion models have been proposed [11, 39, 20] . D3PM [20] proposed a diffusion framework based on any probability transition matrix and trained with a lower bound of log-likelihood. DiffusionBERT [25] utilizes a pre-trained BERT [40] as an initialization of diffusion. Furthermore, [26] generalizes the framework to continuous time by introducing a rate matrix. It is difficult to apply the score matching in such models because the gradient of the data distribution is undefined. Several works try to generalize the score matching on discrete data [29, 28, 26, 27] . Meng et al. [28] introduce the concrete score and the denoising concrete score matching loss. Furthermore, SEDD bridges the discrete state diffusion and the concrete score by introducing a denoising score entropy loss [29] . By incorporating an absorbing process, SEDD achieves competitive performance with the auto-regressive models, especially, GPT-2. 
conclusion: 
 We introduce RADD, a dedicated discrete diffusion model that characterizes the time-independent conditional probabilities, built upon a new factorization form of the concrete score. RADD is much more efficient by reducing the NFEs with a cache strategy while retaining a better performance than strong baselines. Furthermore, we propose DCE loss and prove it is equivalent to the negative log-likelihood of absorbing diffusion. When applied to SEDD, DCE significantly advances the state-of-the-art discrete diffusion on 5 zero-shot language modeling benchmarks at the GPT-2 scale.Limitaition. Our model has been trained and evaluated primarily on the GPT-2 scale. For broader applicability, it is essential to explore the effects of scaling on the performance [41] , which is left as future work. The success of diffusion transformers on images [42, 43, 44] and videos [45] suggests that diffusion models can be scaled up by incorporating transformers.Another limitation is that our model can only generate full-length outputs, unlike auto-regressive models that can produce variable-length outputs. This restricts the flexibility of our model in certain applications. We leave the investigation on this issue as future work.Social impact. For the current theoretical and experimental scope of this paper, we have not found any direct social impacts. However, considering future developments, the paper potentially contributes to the next-generation large language models. In this context, this work could significantly reduce the inference cost of language models but may also lead to hallucinations, amplify biases and discrimination in the data, and pose risks of misuse. As with other generative models, addressing these issues requires further advancements in the field. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes]Justification: new assets introduced in this paper are well documented and provided alongside the assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Since the different dimensions of the forward diffusion process are independent of each other, we can first analyze the conditional distribution in one dimension. This can be derived directly from Eq. (2.3), but for a better understanding, here we provide a more intuitive proof in the case whenQ t = Q absorb .Lemma 1. (Analytic conditional distribution for absorbing case) Suppose {X t } is a continuous time Markov chain with transition rate matrix Q t = σ(t)Q absorb , given the value x at time zero , the conditional distribution p t|0 (x t |x) has the following analytic form:p t|0 (x t |x) =    e -σ(t) , x t = x, 1 -e -σ(t) , x t = [M], 0. x t ̸ = [M] and x t ̸ = [M]. (A.1)Proof. Given the initial value x ∈ X = {1, • • • , N }, we havex t = x, t < T h , [M], t ≥ T h ,where T h is the holding time before the system transitions to the next state.Based on the properties of the Q absorb :p t+∆t|t (x|x) = 1 -(-σ(t)Q absorb (x, x))∆t + o(∆t). (A.2)Partitioning the interval [0, t] into {s k } n k=0 , make use of Memoryless Property of Continuous-Time Markov Chains:p t|0 (x|x) = n k=1 p s k |s k-1 (x|x) (A.3) = n k=1 (1 -(-σ(t k )Q absorb (x, x))(s k -s k-1 ) + o((s k -s k-1 ))) (A.4) = exp( n k=1 ln(1 -(-σ(t k )Q absorb (x, x))(s k -s k-1 ) + o((s k -s k-1 ))) (A.5) = exp( n k=1 -(-σ(t k )Q absorb (x, x))(s k -s k-1 ) + o((s k -s k-1 ))). (A.6)Let max(s k -s k-1 ) → 0 , we have:p t|0 (x|x) = exp(- t 0 -σ(s)Q absorb (x, x)ds) = exp(-(-Q absorb (x, x)σ(t))). (A.7) As Q absorb (x, x) = -1, we have p t|0 (x|x) = P (T h > t) = e -σ(t) , (A.8) p t|0 ([M]|x) = P (T h > t) = 1 -e -σ(t) , (A.9) p t|0 (k|x) = 0 if k ̸ = [M] and k ̸ = x. (A.10)Proposition 1. (Analytic joint distribution for absorbing case) Suppose {X t } is a continuous time Markov chain with transition rate matrix Q t = σ(t)Q absorb . Forx t = x 1 t • • • x d t with N 1 components as [M] and N 2 = d -N 1 components as specific value, p t (x t )can be expressed as Eq. (A.11):p t (x t ) = [1 -e -σ(t) ] N1 [e -σ(t) ] N2 p 0 (x UM t ), (A.11)wherex UM t := {x k |x k ̸ = [M]} represents unmasked part of x UM t .Proposition 1 shows that the joint distribution p t (x t ) can be expressed as the multiplication of two terms. One is an analytic term only depending on time, the other is a joint distribution of clean data p 0 (x UM t ) with N 2 dimensions independent of time.Proof. Without loss of generality, let's assume that the preceding N 1 terms of x are all [M], and the remaining N 2 terms are fixed at specific values. That is,x t = [M] • • • [M]x N1+1 t • • • x d t ,and here x k is a fixed value in X .Use the law of total probability and Lemma 1, along with independent property:p t ([M] • • • [M]x N1+1 t • • • x d t ) = x0∈X d p t|0 ([M] • • • [M]x N1+1 t • • • x d t |x 0 )p 0 (x 0 ) = x 1 0 ∈X ,••• ,x d 0 ∈X p t|0 ([M] • • • [M]x N1+1 t • • • x d t |x 1 0 • • • x d 0 )p 0 (x 1 0 • • • x d 0 ) = x 1 0 ∈X ,••• ,x d 0 ∈X N1 k=1 p k t|0 ([M]|x k 0 ) d k=N1+1 p k t|0 (x k t |x k 0 )p 0 (x 1 0 • • • x d 0 ) = x 1 0 ∈X ,••• ,x N 1 0 ∈X N1 k=1 p k t|0 ([M]|x k 0 )[e -σ(t) ] N2 p 0 (x 1 0 • • • x N1 0 x N1+1 t • • • x d t ) = x 1 0 ∈X ,••• ,x N 1 0 ∈X [1 -e -σ(t) ] N1 [e -σ(t) ] N2 p 0 (x 1 0 • • • x N1 0 x N1+1 t • • • x d t ) =[1 -e -σ(t) ] N1 [e -σ(t) ] N2 x 1 0 ∈X ,••• ,x N 1 0 ∈X p 0 (x 1 0 • • • x N1 0 x N1+1 t • • • x d t ) =[1 -e -σ(t) ] N1 [e -σ(t) ] N2 p 0 (x N1+1 t • • • x d t ).In the general case, we have:p t (x t ) = [1 -e -σ(t)] N1 [e -σ(t) ] N2 p 0 (x UM t ), which shows that the likelihood of noisy data x at time t equals the likelihood of unmasked part of x at time 0 multiplied by a analytic time-dependent term. p t x 1 t . . . x i t . . . x d t p t x 1 t . . . x i t . . . x d t = e -σ(t) 1 -e -σ(t) p 0 (x i t |x UM t ),where x UM t is the vector consists of all unmasked tokens of x t .Proof. According to Proposition 1, ifx i t = [M] and xi t ̸ = [M], xUM t = (x UM t , xi t ), p t ( xt ) p t (x t ) = [1 -e -σ(t) ] N1-1 [e -σ(t) ] N2+1 p 0 ( xUM t ) [1 -e -σ(t) ] N1 [e -σ(t) ] N2 p 0 (x UM t ) = [1 -e -σ(t) ] N1-1 [e -σ(t) ] N2+1 p 0 (x UM t , xi t ) [1 -e -σ(t) ] N1 [e -σ(t) ] N2 p 0 (x UM t ) = e -σ(t) 1 -e -σ(t) p 0 (x i t |x UM t ).According to definition of Q t we can simplify Eq. (3.8) as:L ∞ DCE (x 0 ) = ∞ 0 E x∼p t|0 ( x|x0)   xi =[M],j̸ =[M] σ(t) - e -σ(t) 1 -e -σ(t) I(x i 0 = j) log e -σ(t) 1 -e -σ(t) c θ ( x)[i, j]   dt = ∞ 0 E x∼p t|0 ( x|x0)   xi =[M] σ(t) - e -σ(t) 1 -e -σ(t) log e -σ(t) 1 -e -σ(t) c θ ( x)[i, x i 0 ]   dt = ∞ 0 E x∼p t|0 ( x|x0)   xi =[M] σ(t) - e -σ(t) 1 -e -σ(t) log e -σ(t) 1 -e -σ(t) q θ (x i 0 | xUM )   dt.Define λ(t) = 1 -e -σ(t) , dλ = σ(t)e -σ(t) dt. As σ(t) = t 0 σ(τ )dτ , we have λ(0) = 0, lim t→∞ λ(t) = 1. By a change of variables for the integration variable from t to λ, we can rewrite the above equation as:1 0 1 λ E x∼p λ ( x|x0)   xi =[M] -log( 1 -λ λ q θ (x i 0 | xUM ))   dλ = 1 0 1 λ E x∼p λ ( x|x0) xi =[M] -log(q θ (x i 0 | xUM )) dλ + 1 0 1 λ E x∼p λ ( x|x0) xi =[M] -log( 1 -λ λ ) dλ.By independence of forward process and Lemma 1,p t|0 ( x|x 0 ) = d i=1 p t|0 (x i |x i 0 ) where p t|0 (x i |x i 0 ) =    1 -e -σ(t) xi = [M], e -σ(t) xi = x i 0 , 0 else. (C.1) Therefore, p λ ( x|x 0 ) = d i=1 p λ (x i |x i 0 ) where p λ (x i |x i 0 ) =    λ xi = [M], 1 -λ xi = x i 0 , 0 else. (C.2)Consider the second term, we have:1 0 1 λ E x∼p λ ( x|x0)   xi =[M] -log( 1 -λ λ )   dλ = 1 0 1 λ E x∼p λ ( x|x0) d i=1 I(x i = [M]) -log( 1 -λ λ ) dλ = 1 0 1 λ d i=1 p λ (x i = [M]|x 0 ) -log( 1 -λ λ ) dλ =d 1 0 -log( 1 -λ λ )dλ =d (λ log λ + (1 -λ) log(1 -λ)) | 1 0 . Note that: lim λ→0 λ log λ = lim λ→1 (1 -λ) log(1 -λ) = 0, therefore, (λ log λ + (1 -λ) log(1 -λ))| 1 0 = 0. L ∞ DCE (x 0 ) = 1 0 1 λ E x∼p λ ( x|x0)   xi =[M] -log(q θ (x i 0 | xUM ))   dλ. (C.3)C.2 Denoising cross-entropy loss by k By Eq. (C.3), we can express the loss in terms of λ. Given x 0 , we denote X := We have:{x 1 0 , [M]} × • • • {x d 0 , [M]}1 0 1 λ E x∼p λ ( x|x0)   xi =[M] -log(q θ (x i 0 | xUM ))   dλ (C.4) = 1 0 1 λ x∈ X p λ ( x|x 0 )   xi =[M] -log(q θ (x i 0 | xUM ))   dλ (C.5) = 1 0 1 λ d k=0 x∈ Xk λ k (1 -λ) d-k   xi =[M] -log(q θ (x i 0 | xUM ))   dλ (C.6) = 1 0 1 λ d k=1 x∈ Xk λ k (1 -λ) d-k   xi =[M] -log(q θ (x i 0 | xUM ))   dλ (C.7) = d k=1 1 0 λ k-1 (1 -λ) d-k dλ x∈ Xk   xi =[M] -log(q θ (x i 0 | xUM ))   (C.8) = d k=1 (k -1)!(d -k)! d! x∈ Xk   xi =[M] -log(q θ (x i 0 | xUM ))   (C.9) = d k=1 1 kC k d x∈ Xk   xi =[M] -log(q θ (x i 0 | xUM ))   . (C.10)This can be reformulated in the form of expectation:d k=1 1 kC k d x∈ Xk   xi =[M] -log(q θ (x i 0 | xUM ))   (C.11) = d k=1 1 k E x∼U ( Xk )   xi =[M] -log(q θ (x i 0 | xUM ))   (C.12) =dE k∼U ({1,••• ,d}) 1 k E x∼U ( Xk )   xi =[M] -log(q θ (x i 0 | xUM ))   . (C.13)Let S d represent the set of all permutations of the integers 1, • • • , d, and let π ∈ S d be one of these permutations. Then, we can express log q θ (x 0 ) as follows:EQUATION).(C. 19) In this context, for a fixed k, the condition x π(<d-k+1) 0 can be understood as the unmasked part ofnoisy data xUM . For r = d -k + 1, • • • , d, x π(r) 0corresponds to the k items of the masked part.Therefore, we have:E π∼U (S d ) d r=d-k+1 log q θ (x π(r) 0 |x π(<d-k+1) 0 ) = E x∼U ( Xk ) xi =[M] log q θ (x i 0 | xUM ). (C.20)Thus, substituting back, we have:-log q θ (x 0 ) = dE k∼U ({1,••• ,d}) 1 k E x∼U ( Xk ) xi =[M] -log q θ (x i 0 | xUM ), (C.21)which is exactly Eq. (C.13).This concludes the proof of the exact negative likelihood, showing the equivalence between the expected negative log-likelihood and the denoising cross-entropy formulation. 1-e -σ(t) c θ (x t ) xt . Eq. (D.5) can be simplified as:P t→s (x t , •) = 1 p t (x t ) P T s→t (x t , •) ⊙ (P T t P -1 s→t ) (D.9) = P T s→t (x t , •) ⊙ ( P T t p t (x t ) P -1 s→t ) ≈ P T s→t (x t , •) ⊙ (s θ (x t , t) T P -1 s→t ). (D.p t-∆t|t (x t |[M]) = σ(t) e -σ(t) 1-e -σ(t) ∆tc θ (x t ) xt if xt ̸ = [M], 1 -σ(t) e -σ(t) 1-e -σ(t) ∆t if xt = [M]. (D.11)For multi-dimension cases, similar results can be obtained:p t-∆t|t (x i t-∆t |x t ) = σ(t) e -σ(t) 1-e -σ(t) ∆tc θ (x t )[i, x i t-∆t ] if x i t-∆t ̸ = [M], 1 -σ(t) e -σ(t) 1-e -σ(t) ∆t if x i t-∆t = [M].(D.12) for allx i t = [M].Tweedie τ -leaping Suppose x t = x 1 t • • • x d t hasp t (x t ) = [1 -e -σ(t) ] N1 [e -σ(t) ] N2 p 0 (x N1+1 t • • • x d t ). (D.14)Similar to the proof in Proposition 1:p t,t-∆t (x t , x i t-∆t ) = x0∈X p (t,t-∆t)|0 p(x t , x i t-∆t |x 0 )p 0 (x 0 ) = x 1 0 ∈X ,••• ,x d 0 ∈X p (t,t-∆t)|0 ([M] • • • [M]x N1+1 t • • • x d t , x i t-∆t |x 1 0 • • • x d 0 )p 0 (x 1 0 • • • x d 0 ) = x 1 0 ∈X ,••• ,x d 0 ∈X p (t,t-∆t)|0 ([M], x i t-∆t |x i 0 ) N1 k=1,k̸ =i p t|0 ([M]|x k 0 ) d k=N1+1 p t|0 (x k |x k 0 )p 0 (x 1 0 • • • x d 0 ) = x k 0 ∈X ,k∈{1,••• ,N1}/{i} p (t,t-∆t)|0 ([M], x i t-∆t |x i t-∆t ) N1 k=1,k̸ =i p t|0 ([M]|x k 0 )[e -σ(t) ] N2 p 0 (x 1 0 • • • x i-1 0 x i t-∆t x i+1 0 • • • x N1 0 x N1+1 t • • • x N1+1 t ) = x k 0 ∈X ,k∈{1,••• ,N1}/{i} (e -σ(t-∆t) -e -σ(t) )(1 -e -σ(t) ) N1-1 [e -σ(t) ] N2 p 0 (x 1 0 • • • x i-1 0 x i t-∆t x i+1 0 • • • x N1 0 x N1+1 t • • • x d t ) =(e -σ(t-∆t) -e -σ(t) )(1 -e -σ(t) ) N1-1 [e -σ(t) ] N2 p 0 (x i t-∆t , x N1+1 t • • • x d t). Note we used the fact that:p (t,t-∆t)|0 ([M], x i t-∆t |x i t-∆t ) = p t|t-∆t ([M]|x i t-∆t )p t-∆t|0 (x i t-∆t |x i t-∆t ) = (1 -e -(σ(t)-σ(t-∆t)) )e -σ(t-∆t) = e -σ(t-∆t) -e -σ(t) , p t|0 ([M]|x k 0 ) = 1 -e -σ(t) ,by dividing the two expressions, we have:p t-∆t|t (x i t-∆t |x t ) = e -σ(t-∆t) -e -σ(t) 1 -e σ(t) p 0 (x i t-∆t |x N1+1 t • • • x d t ) (D.15) ≈ e -σ(t-∆t) -e -σ(t) 1 -e σ(t) c θ (x t )[i, x i t-∆t ]. (D.16)In general, for x i t = [M], we have:p t-∆t|t (x i t-∆t |x t ) ≈ e -σ(t-∆t) -e -σ(t)1-e σ(t)c θ (x t )[i, x i t-∆t ], x i t-∆t ̸ = [M], = 1-e -σ(t-∆t) 1-e -σ(t) , x i t-∆t = [M].(D.17)As discussed in Section Appendix D.2, for both the Euler method and Tweedie τ -leaping, the probability p i t-∆t|t ([M]|x t ) is only a factor of time which is independent of the other dimensions of x t once givenx i t = [M]. By the Law of Total Probability, it is easy to find thatp i t-∆t|t ([M]|[M])is also only a factor of time. Thus, given a specific sampling method and a set of time steps {t 0 = 0, • • • , t n = T }, the NFE can be treated as a random variable with a calculable expected value.Let N k denote the number of dimensions of x which changed in [t k-1 , t k ), so we have:NFEs(n) = n k=1 I(N k ̸ = 0), (D.18) E-NFEs(n) = n k=1 E[I(N k ̸ = 0)] = n k=1 P (N k ̸ = 0). (D.19)For each dimension i, let r k represent the probability that x i changes within the interval [t k-1 , t k ).Consequently, N k follows a binomial distribution with parameters l and r k , denoted as N k ∼ Binomial(l, r k ).E-NFEs(n) = n k=1 P (N k ̸ = 0) = n k=1 (1 -(1 -r k ) l ). (D.20)By definition of r k and property of absorbing diffusion:r k = P (X i t k-1 ̸ = [M], X i t k = [M]|X i tn = [M]) (D.21) = P (X i t k-1 ̸ = [M]|X i t k = [M]) n l=k+1 P (X i t l-1 = [M]|X i t l = [M]) (D.22) = (1 -P (X i t k-1 = [M]|X i t k = [M])) n l=k+1 P (X i t l-1 = [M]|X i t l = [M]). (D.23)Eq. (D.23) can be determined given the sampling method and noise schedule.For the Euler method, based on Equation Eq. (D.12), we can derive that:P (X i t l-1 = [M]|X i t l = [M]) = 1 -σ(t l )e -σ(t l ) 1 -e -σ(t l ) (t l -t l-1 ).(D.24)Therefore, we can express r k as:r k = (σ(t k ) e -σ(t k ) 1 -e -σ(t k ) (t k -t k-1 )) n l=k+1 (1 -σ(t l ) e -σ(t l ) 1 -e -σ(t l ) (t l -t l-1 )). (D.25)For Tweedie τ -leaping, By Eq. (D.17), similarly we have:P (X i t l-1 = [M]|X i t l = [M]) = 1 -e -σ(t l-1 )1 -e -σ(t l ) , (D.26) r k = ( e -σ(t k-1 ) -e -σ(t k ) 1 -e -σ(t k ) ) n l=k+1 (1 - 1 -e -σ(t l-1 ) 1 -e -σ(t l ) ) = e -σ(t k-1 ) -e -σ(t k ) 1 -e -σ(E-NFEs(n) = n k=1 (1 -(1 - 1 n ) l ) = n(1 -(1 - 1 n ) l ).(D.28)We implemented our RADD model based on SEDD architecture, which is an encoder-only transformer model [46, 47] incorporating time conditioning [48] and using rotary positional encoding [49] . The only difference is that we removed all parts related to time conditioning (i.e. TimeEmbedding, adaLN-zero block [48] ) and added a softmax operation at the end of the neural network to ensure the output was a valid conditional distribution. Compared with SEDD small model, this modification led to a reduction of 7M parameters, equating to an 8% decrease from the original 90M non-embedding parameters.Require: Network c θ , noise schedule σ (total noise σ), time range [0, T ], step size ∆t1: t ← T , x T ← [M] . . . [M] d×[M], c cache ← c θ (x t ) x i t-∆t ∼ Cat(p(x i t-∆t |x t )) for all x i t = [M], x i t-∆t ← x i t for all x i t ̸ = [M] 10: if x t-∆t ̸ = x t then 11: c cache ← c θ (x t ) 12:end if x i t-∆t ∼ Cat(p(x i t-∆t |x t )) for all x i t = [M], x i t-∆t ← x i t for all x i t ̸ = [M] 10: if x t-∆t ̸ = x t then 11: c cache ← c θ (x t ) 12:end if x 0 ∼ p data , t ∼ U ([0, T ]).3:construct x t by Z i ∼ Bernoulli(e -σ(t) ), x i t = I(Z i = 1)x i 0 + I(Z i = 0)[M] 4: Calculate L θ (x t , x 0 ) = x i t =[M] -σ(t) e -σ(t) 1-e -σ(t) log e -σ(t) 1-e -σ(t) c θ (x t )[i, x i 0 ] 5:Take gradient descent on ∇ θ L(x t , x 0 ) 6: until converged Following the settings in [29] , we trained our model with the following configuration:• Batch Size:512• Learning Rate: 3 × 10 -4• Exponential Moving Average (EMA):0.9999• Gradient Clipping: Gradient norm clipped to 1• Warmup Schedule: Applied for the first 2500 iterationsWe utilized 16 V100 32G GPUs or 16 A100 40G GPUs for training. For the A100 40G GPUs, we leveraged flash attention to accelerate the training process. For the V100 32G GPUs, which do not support flash attention or bfloat16, we employed float16 precision and used the Memory-Efficient Attention mechanism available in torch.nn.functional.scaled_dot_product_attention. Additionally, we used gradient checkpointing technique to save memory.We used Tweedie τ -leaping method, which has optimal results with fixed NFE. For SEDD small, we directly used their result. For RADD small, we generated 1000 samples to get the average value following [29] .As stated in Theorem 1, c θ can be interpreted as a conditional distribution over clean data. A natural idea is to use it directly to generate samples, which is similar to auto-regressive models. However, there are d! kinds of decomposition from joint distribution to conditional distribution, in which we only tested three representative cases:• forward: p(x 1 • • • x d ) = d k=1 p(x k |x (<k) ) • backward: p(x 1 • • • x d ) = d k=1 p(x k |x (>k) ) • random: π ∼ U (S d ), p(x 1 • • • x d ) = d k=1 p(x π(k) |x π(<k) )Results are shown in Table 3 . The perplexity is calculated on average of 1024 samples. For the random case, we calculate the average perplexity between different randomly generated π. Generally, we find that the perplexity by directly sampling from the conditional distribution is higher than that achieved by Tweedie τ -leaping. Among the different decomposition orders, the random order demonstrated the best performance.In this section, we present the unconditionally and conditionally generated text of RADD-DSE in and human face. "And pretty damn conventional mating, so didn't come to the table like that with me. (As a character), it would be a pretty solid case to have," Andra says. "I saw the way he did it, and I think played a little bit with some of his fans. He wanted me to get cute a little bit too." Advertisement As in the parking lot, Andra was growing frustrated with the way the cars recently fit in nicely.It also makes me feel like some things haven't changed until around this period of time, in the future. It's definitely the future here now -and I'm always dubious about thinking quite long before Toyota ever introduced a new car. "I think something that perfectly well fits all the guys," Andra says. "I therefore could fit more well." -Follow Matt Dyckton on Twitter @Mittington.
Spanish star Christina Rene got away after a teenage girl told to leave India for an unfamiliar place.The Russian woman chose Chelsea to stay home, saying the alternative was to get rid of a condition and die after receiving a medical diagnosis and go back to learning as a nurse.Chelsea was sentenced to the first arrest for a serious mental health conviction in October, and was transferred to a man who had taken his place, a 16-year-old man. The bailee's Appeal Court had appealed to a court to hear the case she learned from the teenagers. The Russian Internal Revenue Service found the woman charged with administering an emergency ward, and although the girl was still waiting for a doctor there, she instead went to visit another clinic for the treatment of female swi-virus virus. The court had not ruled out an in-life medical professional. Chelsea never applied to be a pregnant mother; her formal application assumed she was pregnant, dating from the summer of 2014. Out of sound doubts, when her co-boyfriend Chelsea received a proposal to stay abroad for summer work abroad. Chelsea then applied to win to work and have a place in Russia.The grant of nearly $5000 Chelsea invited Chelsea out to go see a Moscow clinic. It took two weeks to find a doctor. These sors' of Moscow's federal courts confiscated the grant. The 17-year-old did not need to go to the hospital where she says she has received everything she has had in China, of course. Chelsea's lawyers Andre James Irani gave the court the doctors he could plead without permission of the young teenager on a regular basis.The Argentine was put out on bail, prompting a sex psychologist to meet her when she signed her papers, but no family member was present. "First thing I wasn't going to ask three days, but I'm thinking about this months already. "I'm glad to see that they are waiting for her with their services. She's already built a good life. She's interested in her studies. But feel like she is? I want to be the only person who has ever been my friend," she said. "I took a lot of act, but she is more than never." To this day Christina Rene McCourner told the court the situation is between Denmark and Stockholm syndrome. She says Chelsea has refused to come to term. "She says that she is talented at medical school. But she's telling a different story, anyway. There's also a case when you just can't get the CNN-type cowardice yourself going to the doctor," she said. A team of Barcelona has been conducting medical inquiries into both doctors who treat the sick and those not who use medical services. "How has she been following her visit to Russia United States and since arriving unable to do so?" "Each often when she said "All the bills are what may I doctor," I've usually never used my medicine again," Chelsea attorneys say. Life in the wrong world While far-so in the past two weeks though, nearly speaking only three pregnant women in Mexico and Europe have requested that Chelsea stop using medical services at them all. Though many of its applicants have receiving medical assistance in Qatar and other parts of the world, they believe it means they should go elsewhere, according to the health services agency. Chelsea's received from facility staff dealing with financial responsibility say it is those who are vulnerable have been out of money for healthcare their life, not who are suffering from a lack of access. "You might think after you tell that provider is not available, you should give the load to somebody in Russia or Sweden," she Hi, my name is Shade-Rayhelynis-Neelsons. Interviewer: Two days ago, so let me speak to you in brief.Drake: Hi, are you studying for graduate school in late July, and somebody is interviewing you for you for his classes. My first personal quote is: so when they're doing class they're going to a shower, and they expect me to not be part of the shower any way. I have a take, I want to check when something's not right and make sure I spot it so that someone can get it happening. My hair is an important piece of me, and I can be the one complete human being that when I have a shower and say, "Okay, I really like my hair, and this is the thing that I would like and I want to believe something, I should just have an attitude check." Do you think anyone else can have time with me? Do I say I don't?I mean I get to 7 right the time I go to class, I sit back there and I feel like no one knows what to do. So, in my case I am not anxious, I'm just saying, "I feel like I have my hair without letting go from day to day, I've got to feel like I've been like the thing they should all be excited by."So, the days follow me, you start looking at my pictures, and you realize how pretty you are. It was just so big this moment for that office, because that was seeing positive things.I'm starting to grow up and be beautiful too.I mean-I mean it's kind of fun, now seeing beautiful girls, especially really in their 20s, come from unusual backgrounds. Back in the 50s I met people at one of the first places Woosz made mons, asked us to visit charity walks, and he would buy us a suit. And actually he really wanted to, so I know what the inspiration is. It's something that someone could have found out, and where they're from -I think it is like everyone is finding ways to relate.This is one of those things I remember the most about when I went to order the products!For example, it may be taken after the sporting event, and I don't know, but they asked us to choose color for our favorite parts in the group....they asked us to take their favorite color, then they made their eyes for each skin.The one that was the round head, like that one I chose so much, but it was really a really painful transition...and I don't know what touched my skin, so I don't know what I would do with it, I will tell you...that was not what I focused on, but I think I may have pretty much my original o-still darker hair, so I chose to go with the round head which I did really. Anyway, my job was to get the hair done, and I do most of my hair for school because I got married and had so many children while I was So. So, I'm always thinking again not to be confused. I had just been doing niggly since I was a child, and there was no reason to do it like that. The career had got started, and therefore I was really going all over the world no less. So one of the things I did was taking of his shirts so I look at him all in one go, I surprise him.I've got some of the most cool things going with those two of this. You see these all look alike, clean, and awesome-and they used to have a shop in the....a shop like that, they never sells coats, so that was really helpful to those guys, I feel, guys going into shop with these guys, and those guys can have the right color, they can have it that right look.I love my hair, it's like when I was a year old when I see scent in your nursery, to get the grandest response, I keep using the smell. I bring it to its level, honestly, it makes the weight apply.rake: Probably my favorite word to explain, after you explain, it isn't hard-in case that's your thing, I'm already who kind of like going, and I'm able to get access when I'm trying. I've been trying to finish coloring for people, for years, so I would like to work on it's own but the colors there to do color pattern are picked for another reason to put the final color off, that's like the other one for giving glitter or outline.So I'm just going to be looking side by side at coloring over and over again. It's my vision. Each color is my dream.As you know, a color is just simply something tucked into a dye and what makes perfect or tail end to a hair is...and that is why I always shampoo twice a day and shower three times a day. as well. However, she did not sign. Gov. Johnluaj said the Amal effectively took the case to the Supreme Court. There clearly needs to be a criminal justice program on immigration and reform, and we need to recognize those efforts not to start." Holder has also said it is a "real issue" for the constitution if the letter is signed off. He said it was essentially a message, seeking to show the majority "power of respect and the power of institutions." But the attorney general said he hoped it would be a task to figure out how to start safeguarding each of their citizens' rights while restoring their constitutional trust. "The only thing I think we can really do is have the judges to understand the nature of the judiciary, how powerful it is to be involved and to interfere with the government with no accountability on what path they want to move down," he said.
Ex76561 molds at the worst parts of the UK economy will tell in the future -most poorer areas of England have suffered more than any person during the first years of 2008, according to ex-Home Secretary Jeremy Foot. A total of 23,000 people of disposable incomes who have five mortgages -more than 4,000 households -will be considered as home buyers, even though published figures will be different from September, say researchers Residents of more than 3,000 homes will be the third most likely to die because of jobs which fell in average terms home ownership during 2008 until the end of this year. It's a surprising drop, according to the Wall Street Journal, which says the economy and the top 1 Professor Jeremy Foot, Home Secretary and the Information Society, raised concerns about the collapse of the UK's housing market -down from 39 He said: "The measure of who 'invested' at that time, doesn't include the number of people or businesses with the assets. There were only three big cities, New York were the other three? "This year -it was announced that Royal Bank of Scotland would be the first to close in 20 years -it turned out then that the poorer areas, including by 2009 and 2010, were hammered hardest," Professor Foot said. Professor Foot's lecture, which was released today in Our journey with my parents at times had been a combination of things. We were all in pairs, and my brothers were such. Repeatedly we asked them to tell me when we wouldn't last to get that end. And I started missing my trip -never visited neighbors before. And finally one day I lost my patience. I all wanted to wander down to my father's house in76561. On my own, I couldn't see my beautiful mother again. I had an ear tumor that was brainblown away and lost all the ways to make the most of the time again. I took the bed from the entire bear family along with his three children, and fixed him up on one side and led him home through the open of the front door with my honey brother. We were hearing all of the other things I had heard were outlandish stories. Finally, he remained so grateful for his admiration for my dad. What was possible my father really didn't have? On November 2, 2013, my mother still did not show any empathy for my father. The loyalty he had was the only expression he had. On the night where he was arrested, other members of his family noticed that they couldn't bribe a co-worker to walk up from his job. That led to him thinking, "I want you to not be a badexample in your family. You can't serve an individual who will make up his stupid demands for you in order to make a profit." For me, to fulfill the compassion of my own brother, I've become an able example of that, that kids. With this decision, it was freeing that I had allowed him to try to decide how to make a better life for his family. I had allowed the animals to have a day off. This is something he and I can do. His son had thought they could, and it was relief he had been rearranging that reality. The time our family spends on the house was at seven times a day. URL and license for existing assets we used are provided in Table 4 .600 Justification: The main claims made in the abstract and introduction accurately reflect our paper's contributions and scope.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: This work observed the relationship between the discrete score model and the conditional mean of clean data in absorbing discrete diffusion models. Notably, it shows that the conditional mean of clean data is independent of time. These observations are then used to simplify the score entropy loss and accelerate sampling. Reviewer vbN2 pointed out an incorrect claim in the original submission, where the RADD loss was mistakenly identified as the log exact likelihood. During the rebuttal, the authors acknowledged this mistake and agreed to remove the section that repeats findings from the "Autoregressive Diffusion Models" paper. 

Comment by SAC: While the authors did respond appropriately to characterize how to modify the paper, the consequence of this error and removal is that the paper's framing are affected throughout including in the first contribution, and segments of the methodology. This left the paper needing a large enough revision, leaving it ultimately a borderline paper which fell on the side of rejection. Once the changes herein (suggested by the reviewers) are incorporated, I encourage the author to resubmit their work with the updated framing.

Reviews: review: paper_summary: paper_summary: This work derives a new interesting connection between the concrete score and conditional target densities in absorbing diffusion models, which decomposes the time-dependent ratio between marginal probabilities (of two transitive states) as a conditional distribution on clean data scaled by an analytic time-dependent scalar, and hence inspires the commonly-used scaling trick and new re-parameterizations. In addition, it also simplifies the original complicated loss objective (denoising score entropy; DSE) as a more straightforward denoising cross-entropy loss (DCE) that enables the exact log-likelihood computation.
strength_weakness: strength_weakness: 1. Despite that the overall presentation is good, it can be further improved by interpreting or illustrating more about the problem formulation. For example, what is the intuition behind the absorbing matrix $Q^{\text{absorb}}$ (eq. (2.4))? Why do we require a more complicated DSE loss instead of usual score-matching objectives (e.g. MSE)? Note that in eq. (2.6), the score network must be *additionally* positive. 
2. Although the proposed method (RADD) is reported to be superior for efficient sampling, the performance of RADD need further verifications on language modeling tasks (Table 2). The hyper-parameters should be fine-tuned to better demonstrate the capability of RADD.
questions: questions: 1. Please provide more details of questions raised in the weaknesses section above. 
2. Detail 1: Why does Kolmogorov’s forward equation (eq. (2.3)) hold in this time-dependent setting? Note that the studied continuous-time Markov chain with discrete states ($Q$-process) is time-inhomogenous, since the transition rate matrix $Q_t$ is dependent of $t$. 
  - When the Markov chain is time-homogenous, $Q_t\equiv Q$, and Kolmogorov’s forward equation follows from Chapman–Kolmogorov
equation (whose derivation requires the time-homogeneity). 
3. Detail 2: What is the intuition to connect the form of $Q^{\text{absorb}}$ (eq. (2.4)) with the absorbing process? Are there any other forms that also work in practice?
limitations: limitations: As is stated by authors, future explorations include flexible variable-length texts generation and applications to models with larger scales.
paper_summary: paper_summary: This paper proposes a simplified discrete diffusion model to improve upon prior language diffusion models.
strength_weakness: strength_weakness: * Although the method speeds up sampling, especially in the large sample step regime, this is a bit misleading/irrelevant. In particular, under more standard sampling practices, the gain is naturally not as big, so the claim of 3.5x improvement is a bit misleading. Furthermore, this does not really improve the sample quality at a smaller number of steps, which is the critical question. As a comparison, this would be like sampling from a standard diffusion model with 4096 timesteps, showing that you can speed it up in that regime, and then claiming a general improvement.

* The results are ultimately a bit marginal. The improvements on sample quality are nice, but I think there is a mistranslation between figure 2 and table 1 (there is no 15 generative perplexity for RADD in that table). Until this is clarified, I'm trusting the results of table 1 more. Table 2 also shows a slight improvement.

* The exact likelihood computation is never applied. I want table 2 to showcase this exact likelihood instead of just a bound.

* The model size is only small. I want to see a similar improvement for the medium quality.
questions: questions: N/A
limitations: limitations: Yes
paper_summary: paper_summary: This paper proves that the probability ratio that appears when computing the time reverse rate matrix for an absorbing state diffusion model has a simple form composed of the conditional distributions of clean data given partial masking scaled by an analytic time dependent weighting. They exploit this form to simplify the parametrization of absorbing state diffusion models and show this improves performance and sampling speed on text datasets.
strength_weakness: strength_weakness: Theorem 2 is wrong. Line C.14 in the proof is incorrect, it's not an equality but a lower bound. The correct version should read

$q\_\theta(x\_0) = \sum\_{\pi} U(\pi) q\_\theta(x\_0 | \pi)$

$q\_\theta(x_0) = \sum\_{\pi} U(\pi) \prod\_{l=1}^d q\_\theta(x\_0^{\pi(l)} | x\_0^{\pi( <l )} )$

$q\_\theta(x_0) = \mathbb{E}\_{\pi \sim U(S\_d) } [ \prod\_{l=1}^d q\_\theta (x\_0^{\pi(l)} | x\_0^{\pi (<l)}) ] $

$ \log q\_\theta(x\_0) = \log ( \mathbb{E}\_{\pi \sim U(S\_d)} [ \prod\_{l=1}^d q\_\theta(x\_0^{\pi(l)} | x\_0^{\pi(<l)}) ] )$

$ \log q\_\theta(x\_0) \geq \mathbb{E}\_{\pi \sim U(S\_d)} [ \sum\_{l=1}^d \log q\_\theta (x\_0^{\pi(l)} | x\_0^{\pi(<l)} ) ]$

When your generative model is a mixture of different generation paths (which an absorbing state diffusion model is), then you need to apply Jensen's inequality. See https://arxiv.org/pdf/2110.02037 equation (2).

Therefore, the authors should remove Section 3.3. I think this section should be replaced with discussion of Autoregressive Diffusion Models https://arxiv.org/pdf/2110.02037 which the author's model has basically reduced to. Autoregressive diffusion models randomly sample a generation order and gradually infill tokens with no dependence on time. The link between Autoregressive Diffusion Models and absorbing state diffusion should be clearly discussed in this paper and this reference is glaringly missing.

The authors should also remove line SEDD-S* in Table 2 since it is based on Theorem 2. Your models are then really not doing favourably compared to standard SEDD. What is your explanation for this and new narrative for Table 2?

In the paper's current state I cannot recommend acceptance since a large part of the narrative is based around Theorem 2. However, I believe the contributions surrounding Theorem 1 with regards to making models simpler and achieve good speed up stand alone as a worthy contribution. Therefore, if the authors clearly describe how they will adjust the narrative under this new information I will be happy to raise my score.

I think it would also be good to include a baseline against autoregressive diffusion models since they propose additional tricks relating to picking how many tokens to reveal. However, I appreciate this would be difficult in the limited time of the rebuttal period and is not required for an increase in score.
questions: questions: In Figure 2, why is RADD with cache able to achieve such lower perplexity compared to no cache? In the limit of many steps, shouldn't these methods be performing the same? It is then a bit suspicious that with the cache is performing so much better. I think this could have something to do with the fact that generative perplexity should also be given with entropy measurements of the samples e.g. Table 1 in https://arxiv.org/pdf/2211.15089. This is because some models can have low entropy and 'good' generative perplexity which could be happening with your model.
limitations: limitations: The authors adequately discuss the limitations in Section 6.

Comments: title: Response to Authors
Further Discussion
Response to Authors
comment: Thank you for your positive feedback. We will make the necessary revisions in the final version as promised.
Thanks for the reply! I have no further questions and will raise my score to 6.
We're glad our response was helpful and appreciate the positive score adjustment. We'll ensure the final version reflects the promised revisions. Thank you again for your thorough review and valuable feedback.
Thank you for the clarifying comments, I understand better now the consistency of Figure 2. I will raise my score to 6.
Thank you for your follow-up and for appreciating the changes. To directly address your concern: the perplexity (PPL) of RADD small (no cache) at NFE = 65536 steps is equivalent to that of RADD small (cache) at E-NFE = 1016.05 steps. It seems that the confusion regarding Figure 2 may have arisen from a lack of clarity in our experimental setup. Let me clarify a few key points:

Firstly, there are three closely related concepts: the Expected Number of Function Evaluations (E-NFE), the Number of Function Evaluations (NFE), and the the number of sampling steps. When no caching is used, these three concepts are equivalent. However, when caching is enabled, NFE becomes a random variable, and E-NFE is used to represent the time cost in practice. Due to caching, E-NFE is less than the number of sampling steps. 

Secondly, regardless of whether caching is used, the perplexity at the same number of sampling steps remains identical, similar to how KV cache works. As a result, We only conducted one set of experiments with caching, varying the number of sampling steps, and plotted the green line using E-NFE on the x-axis. For the yellow line representing the no-cache scenario, We plotted NFE directly as the x-axis. 

Regarding your specific question about running a 65k-step sampling evaluation without caching, it would indeed take several days to complete. However, since the perplexity remains the same with or without caching at the same number of sampling steps, we can compare results directly using the green line (with cache) to infer the expected performance at higher steps. According to the relationship between steps and E-NFE shown in Table D, the perplexity of RADD small (no cache) at NFE = 65536 steps is equivalent to that of RADD small (cache) at E-NFE = 1016.05 steps.

We hope this explanation clarifies the rationale behind the plots. Reviewer 9MAq also raised similar concerns, so you may refer to our response to them for additional context. We ensure to clarify these points in the revised manuscript. Please let us know if further details are needed or if you have any other concerns.
Thank you for the response, I appreciate the new narrative and removing Theorem 2. The new results with the fixed bug look good and is reassuring to see.

I still have a question regarding Figure 2. I appreciate the investigation into the entropy and it would be good to include this analysis in the paper. But regarding the difference between RADD small (cache) and RADD small (no cache) in Figure 2, I'm still unsure why there is a difference. Have you tried sampling RADD small (no cache) with say 65k steps and does it align with RADD small (cache) at 1024?