Non-Markovian Discrete Diffusion with Causal Language Models

We thank the reviewer for their thoughtful and constructive feedback. We are pleased that the reviewer found our core methodology interesting and sound, and appreciated our secondary innovations, including 2D rotary positional encoding, semi-speculative decoding, and leveraging pre-trained language models. We summarize and address each of the raised weaknesses/limitation below.

1. Novelty and comparison with [1]

We appreciate the reviewer bringing [1] to our attention. While both works share the term "non-Markovian", we wish to emphasize that the two are conceptually distinct frameworks and that our contributions are novel and independent, and should not be overshadowed due to similarities merely in terminology. Key distinctions and novelties of our approach compared to [1] and other related works include:

• Reverse Process Formulation: The key difference lies in how the reverse process is formulated. While [1] constructs non-Markovian forward kernels as $q(x_t | x_{t-1}, x_0)=q(x_t | x_0)$, their reverse kernel $p_\theta(x_{t-1} \mid x_t)$ remains "Markovian". In contrast, a core insight of CaDDi is that under the assumption of an independent non-Markovian forward process, incorporating history into the reverse process $p_\theta(x_{t-1} \mid x_{t:T})$ yields a strict mutual information gain $I(x_{t-1};x_{t+1:T}|x_t) > 0$. This result highlights that conditioning on the generative trajectory strictly reduces the uncertainty about $x_{t−1}$ compared to conditioning on $x_t$ alone. As a result, only coupling the non-Markovian forward process with a non-Markovian reverse process can fully leverage the structure of the data. CaDDi is explicitly designed with a non-Markovian reverse process, which enables it to consistently outperform baselines across a wide range of experiments. This architectural and theoretical distinction is central to our contribution and sets our framework apart from [1].
• Unification with Causal Language Models: Another central and novel contribution of CaDDi is its unification of sequential (causal) and temporal (diffusion) reasoning within a single non-Markovian transformer architecture. We demonstrate that CaDDi-AR with 2D Rotary Positional Encoding treats standard causal language models as a special case (T=1), enabling the direct reuse of pretrained LLM weights with no architectural changes. This is a practical advantage that allows us to leverage the vast knowledge encoded in large-scale pretrained LLMs for discrete diffusion as shown in experiments in Table 3. This specific unification and the ability to fine-tune pretrained LLMs for non-Markovian discrete diffusion is not explored in [1].

PS: We also note that the simple iterative denoising in [1] can also be considered a special case of ReMDM (where all tokens are remasked in the subsequent step). We have already detailed the key differences between our approach and the more general ReMDM work in Appendix Section B. We appreciate this valuable feedback and will further expand it with [1] and clarify this discussion in the revised manuscript to explicitly highlight these distinctions.

2. Clarification on Positioning and Related Work

• Compounding Denoising Errors Issue: We acknowledge compounding denoising errors as a known issue in discrete diffusion, discussed in prior works like [2]. Our paper mentions this in the Introduction (Page 1, Section 1, paragraph 2) and Section 2 ("Error During Inference"). We will explicitly cite [2] and other relevant works. Our contribution is not identifying the problem, but proposing a fundamentally different architectural solution (non-Markovian conditioning on the full trajectory) to mitigate it, unlike predictor-corrector or sampling strategies.

• Other Mitigation Strategies [3-7]: Thanks for referring to these work, some of them are already cited in Appendix Section B. While these works also aim to alleviate the compounding error problem, we notice that all of them focus on inference techniques, which are orthogonal to our model's core contribution. For instance, in [3], the improvement comes from an adaptive Gillespie algorithm replacing tau-leaping. [2,4] adopts additional corrector steps. In [5,6], they address the problem through additional planning (position choosing). Similarly, [7] uses a confidence score to bias the position for unmasking. All these methodologies are inference-time techniques. In contrast, our model uniquely defines a totally different non-Markovian discrete diffusion framework that inherently learns more robust dependencies across the generative trajectory to solve the same problem. Crucially, these techniques are orthogonal to our approach and can be combined with CaDDi. For example, we can integrate low-confidence remasking from [7] and additional planning using Top-K probability margin from [5] into our CaDDi model, deciding which tokens need to be remasked again from the logits. Experiments have shown that these combinations can further benefit our model, proving their orthogonality as sampling tricks. We thank the reviewer for raising these sampling techniques, as the suggestion helped improve the quality of our work.

• Relationship between Semi-Speculative Decoding and Prior Decoding Strategies: It is important to emphasize that semi-speculative decoding is a speedup technique for AR-like models, specifically CaDDi-AR, without performance sacrifice. It is fundamentally different from the sampling/decoding techniques in [2-7], and thus not comparable. We will expand this explanation.

3. Clarification on the Benefit of Conditioning on the Whole Sequence Rather than just $x_t$ As discussed in point 1, our model uniquely conditions on the generative trajectory in the reverse process, thereby allowing the model to "revisit past states" and maintain a comprehensive view of the generation process, which significantly benefits performance. If the reviewer is referring to an ablation study concerning this non-Markovian reverse process, our Experiment Table 1 already provides this comparison, where MDLM can be considered a strong Markovian counterpart to CaDDi. CaDDi consistently outperforms MDLM across various metrics, demonstrating the benefits of our non-Markovian reverse process.

Furthermore, if the reviewer is seeking an ablation study with models like [1], where the forward process is defined as non-Markovian but the reverse process remains Markovian (conditioning only on $x_t$), we have additionally run experiments to address this. Results with GPT2 generative perplexity show that conditioning on the generative trajectory in the reverse process offers more robust and effective inference:

4. Computational Cost and Additional Analysis

• Overhead of Conditioning on Full Sequence: The reviewer correctly identifies that conditioning on the entire sequence $x_{t:T}$ can introduce computational overhead. In Appendix Section C.1 ("Context Window and Latent Compression," Page 28), we discuss this practical limitation and introduce latent truncation and trajectory re-composition as strategies to compress the latent trajectory to fit within a bounded context window. Specifically, latent truncation (Section C.1.1) limits the conditioning to the most recent m timesteps, which directly controls the computational cost. We have already performed an ablation study on the context window size (Section G.2, Table 5, Figure 9), showing that a moderate window size offers a favorable balance between performance and computational cost.
• Quantitative Evaluation of Computational Cost: Thanks for your suggestions! Below is a detailed quantitative evaluation of this cost on the LM1B dataset during generation. Speculative decoding is a dynamic speed-up technique, so the NFE has some randomness between different runs. As shown in the table below, semi-speculative decoding significantly reduces the NFE for CaDDi-AR while maintaining competitive performance, highlighting its effectiveness as a speedup technique. It's also worth noting that the non-AR version of CaDDi with 64 steps already achieves better performance than MDLM with 1000 NFE (and with larger FLOPs), which demonstrates that the improvement does not purely benefit from scaling up the computation, but also from the methodology (non-Markovian formulation, 2D ROPE, unification with LLMs).

5. Theoretical Clarity about the first equality in Equation (6) The first equality, $p_{\theta}(x_{t-1}|x_{t:T}):=q(x_{t-1}|x_{t:T}, x_0=\mu_{\theta}(x_{t:T},t))$, is a definition (as stated in line 68) based on the standard practice of parameterizing the reverse diffusion process using a prediction of the clean data $x_0$, which is widely used in prior work like D3PM, MDLM, ...In diffusion models, the true posterior $q(x_{t-1}|x_t,x_0)$ is often used as a target for the learned reverse process $p_{\theta}(x_{t-1}|x_t)$. In our non-Markovian setting, we extend this by conditioning on the future trajectory $x_{t:T}$.

6. Discussion of Potential Negative Societal Impacts: We acknowledge the omission of a discussion on potential negative societal impacts and will add a dedicated section.

Thanks again for your suggestions! We are confident that addressing these points will significantly strengthen our paper. We are committed to incorporating these revisions and providing any further clarifications needed.

We also want to kindly remind you the motivaion of $x_0$-parametrization (both original D3PM and our non-Markovian discrete diffusion process). If we go back to the original definition of latent variable models. Suppose we have a fixed forward process $q$ resulting in a series of latent variables $x_{1:T}$, the ELBO can then be written in form of

This can be rewritten as:

Note that the above equation holds generally and is not under any specfic assumption. $p_\theta$ here is a learned reverse process. It can actually adopt any form or even directly use a neural network to output the value

1. Now we consider the Marokvian discrete diffusion case, which means that $q(x_{t} | x_{0:t-1}) = q(x_t | x_{t-1})$. Under this assumption, one can show that $q(x_{t-1} | x_{t:T}, x_0) = q(x_{t-1} | x_t, x_0)$ ($x_{t-1}$ and $x_{t+1:T}$ are conditionally independent when given $x_t$ and $x_0$). Then the above ELBO can be further simplified as

In that case, a natural definition of $p\_{\theta}({x}\_{t-1}|{x}\_{t:T})$ is to make it Markovian and align with $q$, resulting $p\_{\theta}({x}\_{t-1}|{x}\_{t:T}) := p\_{\theta}({x}\_{t-1}|{x}\_{t}) := q({x}\_{t-1}|{x}\_{t}, x_0 = \mu\_\theta(x\_t, t))$. So we only need to train a denoiser $\mu\_\theta(x\_t, t)$ to predict $x\_0$. This is the hidden motivation of $x\_0$-parameterization of D3PM. Note that this is a definition instead of a derivation, one can still use other forms (e.g. directly predicting $x\_{t-1}$). It's just empirical results indicating it's better.

2. Now we consider our non-Markovian discrete diffusion case: In our case, the forward kernel is designed to be non-Markovian, so $q(x_{t} | x_{0:t-1}) = q(x_t | x_{t-1})$ does not hold anymore. Instead, since we use an independent noising kernel across timesteps, we have $q(x_{t-1} | x_{t:T}, x_0) = q(x_{t-1} | x_0)$. In this case, we have ELBO as

So correspondingly, a natural extension is to define $p\_\theta$ as $p\_{\theta}({x}\_{t-1}|{x}\_{t:T}):=q(x\_{t-1} | x\_0=\mu\_\theta(x\_{t:T}, t))$. Here the reverse process $p$ is kept non-Markovian (containing history $x_{t+1:T}$), as in case of non-Markovian forward kernel, $x\_{t-1}$ and $x\_{t+1:T}$ are not conditionally independent when given $x_t$ and $x_0$. This suggests that trajectory $x_{t+1:T}$ also contain information about $x\_{t-1}$

So generally, imagine $p_\theta$ as a learned reverse process we want to maximize ELBO. There is never a derivation to get its strict form. It's just intuitively and empirically $x_0$-parameterization works better.

We hope the above has helped your understanding why $x_0$-parameterization is a practical design for the definition of $p\_\theta$ in D3PM and our Non-Markovian discrete diffusion. If you still have confusion in understanding anything related to variational inference, ELBO in discrete diffusion, $x_0$-parametrization, we are happy to elaborate.

If reviewers still have doubts about the formulation of D3PM, also feel free to reach out to any author of these established prior work (e.g. D3PM, MDLM, MD4) anonymously to verify all of the above statements. From our experience, they are open and friendly about discussing these technical details.

Thank you once again for your feedback!

No need to apologize! As authors, we are alway pleasant to clarify and help reviewers understand in rebuttal stage. As for the issue, we respectively maintain our position that that Eq. 4 in D3PM represents a definition of x0-paramerization instead of a derivation. We reached out (anonymously) to the authors of D3PM, who confirmed the following about D3PM:

"...I would say that equation 4 is a definition rather than a derivation. there are other forms. And we pick this posterior integrated form because it turns out to work better. DDPM also does someting similar in continious space...",

This aligns with our original explanation. We notice in your latest reply you state that $p_{\theta}(x_{t-1}|x_t) = \sum_{\hat{x}}q(x_{t-1}|x_t, \hat{x})p_{\theta}(\hat{x}|x_t)$ holds, which lead you to a conclusion that it's a derivation. But this is generally not true. The equation only hold when $p_{\theta}=q$. This equation is a definition instead of a direct derivation. We doubt it is still this part causing your confusion.

3b. Thank you for the clarification

We thank the reviewer for their constructive feedback. We appreciate that they recognize the core idea of CaDDi, and we are grateful for their positive remarks on the architectural design, the semi-speculative decoding strategy, and the experiments.

1. Time efficiency of CaDDi-AR

We thank the reviewer for highlighting the issue of CaDDi’s time efficiency. We agree that, due to the iterative refinement nature of the diffusion process, multiple passes are unavoidable—this being a key distinction from autoregressive (AR) models. Similarly, CaDDi-AR, which interpolates between the diffusion and AR paradigms, also inherits this increased time complexity. To address this, we proposed a semi-speculative decoding strategy, which significantly accelerates sampling and mitigates the computational overhead.

We would like to highlight that CaDDi-AR is a special case within the broader CaDDi framework, which is designed as a flexible interpolation between discrete diffusion and autoregressive (AR) modeling. CaDDi can be tuned to lean more toward the diffusion paradigm or the AR paradigm, depending on the application needs. This flexibility reflects an inherent trade-off between sampling efficiency and modeling expressiveness, allowing practitioners to balance performance and speed according to their specific use case.

Finally, to demonstrate the time complexity of CaDDi, we include below the Number of Function Evaluations (NFE) comparison between different versions of CaDDi and MDLM with varying diffusion steps, together with their performance on the LM1B dataset. We see that while CaDDi-AR uses a high number of NFEs, semi-speculative decoding strategy reduces the numer to a reasonable regime without a significant drop in performance. Also, CaDDi with 64 steps already achieves better performance than MDLM with 1000 NFE (and with larger FLOPs). Therefore, practitioners are safe to choose the specific CaDDi model they could afford based on their need and resources.

2. Context length

We appreciate the reviewer for highlighting a key distinction of our method: conditioning on the full history trajectory rather than a separate time step. Indeed, without special treatment, the context length would grow with the timestep t, potentially making it computationally expensive or unstable for large T. In Appendix C.1 ("Context Window and Latent Compression"), we discuss this practical limitation and introduce latent truncation and trajectory re-composition as strategies to compress the latent trajectory to fit within a bounded context window. Specifically, latent truncation (Section C.1.1) limits the conditioning to the most recent m timesteps, which directly controls the computational cost. We have performed an ablation study on the context window size (Section G.2, Table 5 and Figure 9), showing that a moderate window size offers a favorable balance between performance and computational cost.

We sincerely thank the reviewer for their thorough and insightful feedback on our paper. The comments are highly valuable and will help us significantly improve the clarity, completeness, and impact of our work. We are encouraged that the reviewer found our 2D positional encoding and semi-speculative decoding to be novel and appreciated the performance improvements and the ability to reuse pretrained LLMs.

Below, we address each of the reviewer's points and detail our planned revisions.

1. & 2. Novelty and Referencing of Non-Markovian Discrete Diffusion DNDM Thank you for highlighting the need for a more prominent comparison with DNDM. Actually we did include a discussion of related work including DNDM in our 22-page appendix (in supplementary material), but we understand that supplementary material can be easily missed and agree that this comparison is crucial for the main paper. We appreciate the opportunity to clarify the distinction and re-emphasize our specific contributions.

• Regarding DNDM: While both CaDDi and DNDM are non-Markovian, they address different goals with distinct methodologies. DNDM's primary contribution is achieving fast, training-free sampling by derandomizing the generation process with a predetermined transition time. In contrast, CaDDi leverages the non-Markovian structure to improve generative quality and robustness by explicitly conditioning the denoiser on the generative trajectory. Therefore, the conceptual overlap is limited to the relaxation of the Markovian assumption. Our core contributions are orthogonal to theirs and focus on a novel modeling paradigm:
  1. A unified causal framework that models both sequential and temporal dimensions in a single transformer.
  2. A novel 2D Rotary Positional Encoding (RoPE) designed for this unified structure.
  3. A direct method for adapting pretrained LLMs to the discrete diffusion paradigm.

Thanks again for your suggestions. We will move the discussion of DNDM from the appendix to the main body of the paper, expanding the explaination.

• Regarding DDIM: DDIM is a foundational work for non-Markovian sampling in continuous diffusion models. Our paper is focused on the discrete domain, where the challenges and solutions are fundamentally different (e.g., operating on categorical variables, different kernel designs, and no direct equivalent of an ODE formulation).

3. Inference Speed and Computational Overhead (Complexity L×T) & Quantifying Computational Cost (Training and Inference): We acknowledge the reviewer's point regarding the inference complexity and the need for a more detailed quantification of computational cost. While the theoretical complexity for naive CaDDi-AR's token-level autoregressive generation within each diffusion step is indeed L×T, our semi-speculative decoding strategy is designed to significantly reduce this in practice. The exact degree of reduction cannot be theoretically derived as it's an algorithm that dynamically skips steps; however, it consistently results in a substantially lower effective number of function evaluations (NFE) than L×T. To further quantify the inference computational cost, we provide the following table on the LM1B dataset during generation:

As shown, semi-speculative decoding significantly reduces the NFE for CaDDi-AR while maintaining competitive performance, highlighting its effectiveness as a speedup technique. It is also worth noting that the non-AR version of CaDDi (with complexity O(L)) with 64 steps already achieves better performance than MDLM with 1000 NFE (and with larger FLOPs). CaDDi-AR is a strategy to further enhance performance, which inherently entails a higher computational cost, and semi-speculative decoding is specifically designed to alleviate this additional overhead.

Regarding the overall overhead of computation in training, we discuss this practical limitation in Appendix Section C.1 ("Context Window and Latent Compression") and introduce latent truncation and trajectory re-composition as strategies to compress the latent trajectory to fit within a bounded context window. Specifically, latent truncation (Section C.1.1) limits the conditioning to the most recent m timesteps, which directly controls the computational cost in both training and inference. We have already performed an ablation study on the context window size (Section G.2, Table 5, Figure 9), showing that a moderate window size offers a favorable balance between performance and computational cost. These strategies ensure that CaDDi achieves better performance while not excessively sacrificing computational cost.

4. Terminology Clarification of "VERIFY" and "CORRECT" in Algorithm 2: "VERIFY" and "CORRECT" refer to the standard operations within speculative decoding, adapted for CADDi-AR. Specifically:

• VERIFY($p_0$, $\mathbf{x}\_{1:T}$, ${\hat{x}}\_0^{\text{prev}}$): This step takes the model $p_0$, the current latent trajectory $\mathbf{x}\_{1:T}$, and the draft sequence $\hat{x}_0^\text{prev}$ (which is the predicted clean sequence from the previous timestep). It evaluates the probability of each token in ${\hat{x}}_0^\text{prev}$ given the context and determines the longest prefix of ${\hat{x}}_0^\text{prev}$ for which the tokens are accepted based on a specified confidence threshold (In this work, we use a criterion similar to Nucleus Sampling, rejecting samples based on the probability of choosing the same token between this timestep and the prior timestep. If the probability is higher, no rejection happens). The output $\tilde{i}$ is the index of the first token that is rejected or where the draft ends.
• CORRECT($p_0$, $\mathbf{x}\_{1:T}$, ${\hat{x}}\_0^{\text{prev}}$): This step takes the same inputs. It returns the accepted prefix of $\hat{x}\_0^\text{prev}$ (i.e., ${\hat{x}}\_0^{0:\tilde{i}-1}$) and prepares the model to resume autoregressive sampling from the position $\tilde{i}$. This process is analogous to how speculative decoding "corrects" a proposed draft by either accepting it fully or partially and then continuing generation from the point of divergence. We will ensure these operations are precisely described in Section 4.2 to enhance clarity.

5. Typo in Algorithm Reference (Line 216): Thanks for pointing this out! We will fix it in the next revision.

Q1.Further Quantification about the Computational Cost of CaDDi and CaDDi-AR See Point 3.

Q2. What's the Sequence Length in Experiment and How Does it Scale on Longer Sequences? The sequence length used for the LM1B dataset is 128 tokens, and for the Text8 dataset, it is 256 tokens. These dataset configurations are standard, consistent with prior discrete diffusion work such as D3PM and MDLM.

For CaDDi specifically, the primary factor affecting memory and computation for longer sequences is the transformer's self-attention mechanism, which scales quadratically with sequence length. To address this, Appendix C (Model Implementation Details) discusses "Latent Truncation" and "Trajectory Re-composition" as strategies to manage the context window and handle longer generative trajectories. These techniques effectively compress $x_{t:T}$ to fit within the model's context. These strategies allow CaDDi to scale to longer sequence.

It is also important to note that most existing standard discrete diffusion models focus on limited sequence length generation due to their encoder structures. However, recent work, such as Block Diffusion [1], has been proposed to extend beyond these limitations. Integrating such ongoing efforts with our framework to further scale to longer sequences presents an interesting future direction.

[1]. Arriola M, Gokaslan A, Chiu J T, et al. Block diffusion: Interpolating between autoregressive and diffusion language models[J]. arXiv preprint arXiv:2503.09573, 2025.

We thank the reviewer once again for their valuable feedback! We believe these revisions will significantly strengthen the paper by addressing the reviewer's concerns comprehensively and transparently.

We sincerely thank Reviewer qCqR for their thoughtful and encouraging review. We are glad that the reviewer recognizes the novelty, significance, and technical quality of our work. We appreciate the comment regarding practical use cases where CaDDi outperforms standard causal LMs or existing discrete diffusion models. While such examples are constrained by space in the current submission, we agree this is an important direction and will add some additional illustrative use cases in the manuscript.

We thank the reviewer for their thoughtful feedback and insightful comments. We appreciate the recognition of our semi-speculative decoding sampler as an interesting contribution. We address each of the raised weaknesses below.

1. "In masked diffusion models, the state $x_t$ inherently encodes the entire trajectory $x_{t:T}$, making the decoding sequence largely irrelevant. As shown in Table 2, CaDDi clearly lags behind MDLM in terms of perplexity, suggesting that the additional engineering to incorporate the entire trajectory does not provide a clear benefit."

We respectfully disagree with the assertion that $x_t$ inherently encodes the entire trajectory $x_{t:T}$ in non-Markovian masked diffusion models. In CaDDi, noise is added independently at each timestep, conditioned only on the original data $x_0$. In this case, from the very nature of how trajectories are created, the state $x_t$ itself does NOT encode the entire trajectory before it.

Now, we explain why the above formulation is necessary and helpful. As discussed in Section 3.1 and further elaborated in Appendix A.4 ("Failure to Remask Issue"), traditional Markovian discrete diffusion models, including MDLM, suffer from a "failure to remask" problem. Once a token is unmasked (i.e., $x_t \neq e_m$), it is deterministically copied to $x_{t-1}$ regardless of the model's prediction. This means the model cannot revise early mistakes, leading to error accumulation.

Our non-Markovian approach ensures that each state $x_t$ in the latent trajectory contains unique and complementary information, rather than being a mere compression of the subsequent trajectory. This fundamental difference in the forward process is key to our non-Markovian formulation, which then allows the reverse process to condition on the historical trajectory $x_{t:T}$ (as described in Section 3.3 and Algorithm 1). This explicit conditioning enables the model to effectively revisit past states, thereby lifting the restrictive Markov constraint and leading to a more robust inference process that can self-correct errors.

Regarding the perplexity comparison in Table 2, the reviewer states that CaDDi lags behind MDLM. We believe this observation may stem from an unfair comparison across different time discretizations, and we wish to clarify the following:

• Performance at Same Discretization (Table 2): We wish to emphasize that the reviewer might be wrongly comparing across different time discretizations. As noted in Appendix Section E.3, likelihood estimation for diffusion models is sensitive to the number of discretization steps. As clearly shown in Table 2 (rows shaded in gray), when comparing models at the same 64-step discretization, CaDDi achieves a BPD of $<1.41$ and Perplexity of $<2.66$, which is indeed the best performance among all discrete diffusion models evaluated at 64 steps (MDLM at 64 steps has BPD $\leq1.46$ and Perplexity $\leq2.75$). This demonstrates a clear benefit of our approach within comparable settings. Some baselines report results under continuous-time settings or with 1000-step discretizations, which are not directly comparable to our 64-step discrete evaluation. Since MDLM (and other continuous-time models) are trained in a continuous-time framework while our model operates in a discrete-time framework, there isn't a strict one-to-one correspondence for continuous frameworks. However, to further demonstrate our model's consistent superiority, here we trained an additional model with 256-step discretization (which is the same as the sequence length in the Text8 dataset). This model achieves a BPD of ≤1.37 (better than MDLM even with $\infty$ time), further solidifying CaDDi's competitive performance.
• LM1B Results (Table 1): On the larger and more representative LM1B dataset, both CaDDi and CaDDi-AR consistently outperform MDLM in generative perplexity across all three language model oracles (GPT-2, Llama-2-7B, and Llama-3.2-3B) and various sampling temperatures. This demonstrates a clear benefit of our approach on a more challenging and widely used benchmark.
• Ablation Study on Robustness (Figure 4 and G.3): Our ablation study on inference robustness (Figure 4 and Figure 10 in Appendix G.3) clearly shows that CaDDi exhibits significantly stronger resilience to manually injected noise compared to MDLM and D3PM. This directly supports our argument that conditioning on the historical trajectory improves inference robustness and self-correction, which is a key benefit not captured solely by perplexity on Text8. Therefore, the overall empirical evidence, especially when fairly comparing at the same discretization on Text8, on LM1B, and in terms of robustness, strongly supports the benefits of our non-Markovian approach.

2. "It is unclear why the perplexity of the models on LM1B is not reported."

Thanks for raising this point. Our primary intention with the Text8 experiments was to demonstrate the likelihood modeling ability of our model, and we considered reporting additional perplexity metrics on LM1B to be somewhat redundant in that regard. Instead, we established the LM1B dataset as a generative task to evaluate the direct generative ability and quality of samples across different models.

However, we appreciate your suggestion for including these results for completeness. We are pleased to provide the perplexity results for the LM1B dataset here

3. Clarification Regarding Table 1

We sincerely acknowledge the reviewer for raising concerns. In the meantime, we highly recommend the reviewer to also refer to our comprehensive 22-page appendix in the supplementary material. This supplementary material has already covered most of the following concerns in greater detail. But thanks to the suggestions, we recognize that some details might not have been sufficiently clear in the main text and will move relevant information from appendix to the main text in the next revision to improve clarity and accessibility.

• (a) What does T refer to? Is it the sampling temperature or the number of time discretizations?: In Table 1, "T" refers to the sampling temperature (e.g., T=1, T=0.7, T=0.5). This is explicitly stated in the caption of Table 1. The number of time discretizations (diffusion steps) for CaDDi and CaDDi-AR is consistently 64 for the reported LM1B experiments, as stated in Appendix Section E.1 line 923. For baselines, Section E.1 notes: "Note that models such as MDLM and SEDD are trained in continuous time, whereas our models operate in discrete time." For evaluation, "All diffusion-based models use 64 denoising steps during inference."
• (b) What discretizations were used for the baselines such as MDLM, D3PM, and UDLM? As mentioned above and in Appendix Section E.1, MDLM and SEDD are trained in continuous time. For evaluation, all diffusion-based models (including MDLM, D3PM, UDLM, SEDD, DFM) were evaluated using 64 denoising steps during inference for fair comparison on LM1B (Section E.1). For Text8 (Table 2), we explicitly state the steps/discretization for each model
• (c) What sampler was used for each method? If CaDDi uses the proposed semi-speculative decoding sampler, it would be helpful to report the sample quality from CaDDi using the ancestral sampler as well. For CaDDi, we use the ancestral sampler as described in Algorithm 1. For CaDDi-AR, we employ the semi-speculative decoding sampler (Algorithm 2) to accelerate inference. We agree that disentangling the improvements is valuable. The performance reported for "CaDDi" in Table 1 uses the ancestral sampler (Algorithm 1), while "CaDDi-AR" uses the semi-speculative decoding sampler (Algorithm 2). The comparison between "CaDDi" and "CaDDi-AR" in Table 1 directly showcases the impact of the token-level autoregressive factorization and the semi-speculative decoding. CaDDi (block-level autoregressive) already outperforms MDLM, demonstrating the benefit of the non-Markovian trajectory. CaDDi-AR, with its token-level factorization and semi-speculative decoding, further improves performance, indicating the combined benefit.

4. "Table 4 is missing major baselines. The authors should compare their method against MDLM, UDLM [2], and an autoregressive (AR) model trained with the same transformer architecture and a similar number of training steps. They can follow the steps in [2]."

Table 4 focuses specifically on conditional text generation on the Amazon Polarity dataset, a task where we demonstrate the flexibility of CaDDi for text infilling and classifier-free guidance. For this task, we compare against a fine-tuned GPT-2, a strong autoregressive baseline for conditional generation that uses the same 12-layer transformer architecture as CaDDi.

While MDLM and UDLM are general discrete diffusion models, their application to conditional generation with text infilling (as opposed to unconditional generation or simple prefix conditioning) is not their primary focus or demonstrated strength in prior work.

To further address the request for additional baselines, we have conducted an experiment with UDLM on the Amazon Polarity dataset. The results are as follows:

It is important to note that this is not a standard benchmark, as the sentiment accuracy metric can be unstable due to the inherent biases in the dataset. Therefore, these UDLM results should be considered as a reference to demonstrate the general ability of conditional generation rather than a definitive comparison.

5. "Algorithm 2 is being incorrectly referenced Algorithm 3 in line 216." Thanks for pointing this out! We will revise this typo.

Dear Reviewer CSEv,

We really hope our responses have addressed your remaining concerns and help you understand the value of the work. We would appreciate it if you could let us know whether any concerns remain in advance, so we can address them before the review period closes in one day.