Non-Markovian Discrete Diffusion with Causal Language Models
Yangtian Zhang, Sizhuang He, Daniel Levine, Lawrence Zhao, David Zhang, Shiyang Zhang, Emanuele Zappala, Rex Ying, David van Dijk, [email protected] · 2025
Read Non-Markovian Discrete Diffusion with Causal Language Models by Yangtian Zhang, Sizhuang He, Daniel Levine, Lawrence Zhao, David Zhang, Shiyang Zhang, Emanuele Zappala, Rex Ying, David van Dijk, [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09767.txt.
Introduction
Yangtian Zhang and co-authors loosen a core limit on diffusion models that write text. Such models build sequences step by step, but each step sees only the current draft, so early slips can never be fixed. Their model, CaDDi, instead conditions each step on the whole path the draft has taken so far.
One transformer then handles both the step-by-step logic of language models and the revise-and-refine logic of diffusion. Standard language models fall out as a special case of the design. Pretrained language model weights drop in with no change to the architecture. On language benchmarks, CaDDi beat the best discrete diffusion rivals. The result narrows much of the gap to large autoregressive transformers.
Catalog record
| CREATOR | Yangtian Zhang, Sizhuang He, Daniel Levine, Lawrence Zhao, David Zhang, Shiyang Zhang, Emanuele Zappala, Rex Ying, David van Dijk, [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-09767
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-Markovian Discrete Diffusion with Causal Language Models Yangtian Zhang, Sizhuang He, Daniel Levine, Lawrence Zhao, David Zhang, Shiyang Zhang, Emanuele Zappala, Rex Ying, David van Dijk, [email protected] Abstract Discrete diffusion models offer a flexible, controllable approach to structured sequence generation, yet they still lag behind causal language models in expressive power. A key limitation lies in their reliance on the Markovian assumption, which restricts each step to condition only on the current state, leading to potential uncorrectable error accumulation. In this paper, we introduce CaDDi ( Ca usal D iscrete Di ffusion Model), a discrete diffusion model that conditions on the entire generative trajectory, thereby lifting the Markov constraint and allowing the model to revisit and improve past states. By unifying sequential (causal) and temporal (diffusion) reasoning in a single non-Markovian transformer, CaDDi also treats standard causal language models as a special case and permits the direct reuse of pretrained LLM weights with no architectural changes. Empirically, CaDDi outperforms state-of-the-art discrete diffusion baselines on natural-language benchmarks, substantially narrowing the remaining gap to large autoregressive transformers. 1 Introduction Autoregressive transformers have become a dominant approach for sequence modeling [ 60 , 12 , 56 ] , achieving state-of-the-art performance in many natural language and biological tasks. Their left-to-right decoding paradigm simplifies training via next-token prediction and is supported by large-scale pretraining, unlocking broad linguistic (or domain) knowledge. However, these models can be less flexible for bidirectional or partially specified generation, such as text infilling or prompting from arbitrary locations. By contrast, discrete diffusion models [ 17 , 2 , 24 , 21 ] naturally accommodate controllable generation scenarios where tokens can be iteratively refined and sampled in a bidirectional manner [ 47 ] . Recent advances have extended discrete diffusion to continuous time [ 5 , 48 ] , improved its training objectives [ 48 , 37 , 44 , 46 ] , and accelerated inference [ 41 , 36 ] . Yet, these models often lag behind autoregressive approaches in generation quality [ 66 ] , due in part to their reliance on a single latent state for denoising—leading to fragile inference where small decoding errors can accumulate over time [ 63 , 66 , 32 ] . To address this limitation, in this work, we explore a non-Markovian diffusion framework to discrete sequences by allowing each denoising step to condition on the entire generative trajectory, rather than a single latent state. While prior work such as DART [ 23 ] has investigated non-Markovian diffusion for continuous data, its formulation relies on continuous kernels and smooth transitions that do not directly translate to the discrete setting. Notably, when instantiated for discrete sequences, non-Markovian diffusion naturally mirrors the structure of token-level autoregressive models—highlighting a close connection between the two. Leveraging this insight, we propose CaDDi, a causal discrete diffusion model that unifies sequential (left-to-right) and temporal (multi-step) dimensions in a single decoder-only transformer architecture. As a result, CaDDi can be trained efficiently via a simple next-block/next-token prediction loss—similar to a causal language model—while preserving the bidirectional control and iterative refinement of diffusion. Additionally, we show that its token-level variation CaDDi-AR can be viewed as a generalization of traditional autoregressive models ( T=1 is the special case), making it straightforward to fine-tune a pretrained LLM for discrete diffusion. Such adaptation unlocks flexible generation modes (e.g., text infilling) without sacrificing the rich knowledge encoded by large-scale pretraining. In summary, our key contributions are as follows. • We introduce a non-Markovian discrete diffusion framework where each denoising step incorporates the full generative trajectory, improving inference robustness. • We propose CaDDi, a causal discrete diffusion model that unifies sequential and temporal modeling within a non-Markovian diffusion framework. Its further variation CaDDi-AR generalizes traditional causal language models as a special case and can seamlessly adopt pretrained LLMs for discrete diffusion, enabling more controllable and structured generation. • Quantitative results show that CaDDi outperforms recent discrete diffusion models, achieving lower generative perplexity on language datasets and stronger reasoning capabilities when leveraging a pretrained LLM. 2 General Discrete Diffusion Recently, discrete diffusion models [ 2 ] have emerged as a powerful framework. In contrast to their continuous counterparts, which corrupt data by adding Gaussian noise in a real-valued space, discrete diffusion models operate on categorical variables, gradually corrupting tokens before reconstructing them through a learned denoising process. Forward Process. Let \mathbf{x}_{0}=(\mathbf{x}_{0}^{1},\mathbf{x}_{0}^{2},\ldots,\mathbf{x}_{0}^{L}) be a sequence of discrete tokens from a vocabulary \mathcal{V} of size |\mathcal{V}| . The forward (noising) process produces latent variables \mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{T} by iteratively corrupting each token according to a time-dependent transition matrix \mathbf{Q}_{t} : \displaystyle q\bigl(\mathbf{x}_{t}\mid\mathbf{x}_{t-1}\bigr) \displaystyle=\operatorname{Cat}\Bigl(\mathbf{x}_{t};\,\mathbf{x}_{t-1}\,\mathbf{Q}_{t}\Bigr), (1) where \operatorname{Cat}(\cdot;\,\pi) denotes the categorical distribution with parameter \pi , and [\mathbf{Q}_{t}]_{ij} gives the probability of transitioning from state i to state j at time t . Due to the Markovian assumption, the marginal distribution at any timestep can be computed in closed form: q(\mathbf{x}_{t}\mid\mathbf{x}_{0})=\operatorname{Cat}(\mathbf{x}_{t};\mathbf{x}_{0}\bar{\mathbf{Q}}_{t}),\quad\text{where}\quad\bar{\mathbf{Q}}_{t}=\mathbf{Q}_{1}\mathbf{Q}_{2}\dots\mathbf{Q}_{t}. (2) Common choices for the transition kernel \mathbf{Q}_{t} include uniform kernel \mathbf{Q_{t}}=(1-\beta_{t})\mathbf{I}+\beta_{t}\mathbf{1}\mathbf{1}^{T}/|\mathcal{V}| of size |\mathcal{V}|\times|\mathcal{V}| and absorbing kernel \mathbf{Q}_{t}=\left(1-\beta_{t}\right)\mathbf{I}+\beta_{t}\mathbf{1}e_{m}^{\top} of size (|\mathcal{V}|+1)\times(|\mathcal{V}|+1) , where \mathbf{1} is an all-one vector and e_{m}^{\top} represents a one-hot vector where element at index m=|\mathcal{V}|+1 is 1. Reverse Process. The reverse (denoising) model p_{\theta}\bigl(\mathbf{x}_{t-1}\mid\mathbf{x}_{t}\bigr) is commonly parameterized in form of posterior distribution , which is learned to reverse the corruption process p_{\theta}\bigl(\mathbf{x}_{t-1}\mid\mathbf{x}_{t}\bigr)=q\bigl(\mathbf{x}_{t-1}\mid\mathbf{x}_{t},\mathbf{x}_{0}=\boldsymbol{\mu}_{\theta}\left(\mathbf{x}_{t},t\bigr)\right)=\operatorname{Cat}\left(\mathbf{x}_{t-1};\frac{\mathbf{x}_{t}\mathbf{Q}_{t}^{\top}\odot\boldsymbol{\mu}_{\theta}\left(\mathbf{x}_{t},t\right)\bar{\mathbf{Q}}_{t-1}}{\boldsymbol{\mu}_{\theta}\left(\mathbf{x}_{t},t\right)\bar{\mathbf{Q}}_{t}\mathbf{x}_{t}^{\top}}\right) (3) where \boldsymbol{\mu}_{\theta}\left(\mathbf{x}_{t},t\right)=p_{\theta}(\mathbf{x}_{0}\mid\mathbf{x}_{t}) is a time-dependent denoiser ( x 0 -parameterization ) mapping \mathbf{x}_{t} back to the mean distribution of clean data. Error During Inference. During inference, discrete diffusion models can potentially encounter a variety of sources of error, including inaccuracies arising from heavy-tailed per-token sampling distributions, and independent factorization in denoising distribution p_{\theta}\left(\mathbf{x}_{0}\mid\mathbf{x}_{t}\right)=\Pi_{i}p_{\theta}\left(\mathbf{x}_{0}^{i}\mid\mathbf{x}_{t}\right)=\Pi_{i}\boldsymbol{\mu}_{\theta}^{i}\left(\mathbf{x}_{t},t\right) , which prevents the model from fully capturing the true posterior q\left(\mathbf{x}_{0}\mid\mathbf{x}_{t}\right) that inherently exhibits dependencies across token dimensions [ 63 ] . Although each individual source of error may be moderate, they can propagate and accumulate across reverse steps. Specifically, incorrectly predicted \mathbf{x}_{t} will not only impact the immediate denoiser output \boldsymbol{\mu}_{\theta}\left(\mathbf{x}_{t},t\right) , but also affect subsequent predictions, leading to further deviations as the trajectory progresses. Even when denoiser predictions are accurate, the constrained form of the approximated posterior can limit the model’s ability to self-correct earlier mistakes. 1 1 1 One illustrative case of such limited self-correction is the failure-to-remask phenomenon under absorbing diffusion kernels, See Appendix Figure 1 : (a). Inference paradigm for a standard causal language model versus CaDDi-AR. In CaDDi-AR, each timestep first autoregressively denoises the tokens into \widetilde{\mathbf{x}}_{0} , then re-applies noise via the diffusion kernel to obtain {\mathbf{x}}_{t-1} . A traditional autoregressive model emerges as the special case of T=1 , which can be adapted to discrete diffusion by fine-tuning. (b). Extending 1D to 2D Rotary Positional Encoding. Standard rotary encodings for token positions are seamlessly generalized to also encode diffusion timesteps, remaining fully backward-compatible with existing language model architectures. 3 Non-Markovian Discrete Diffusion 3.1 Is the Markovian Assumption Necessary? Diffusion models can be viewed as a special class of hierarchical variational autoencoders (HVAEs) with a Markovian assumption, where the latent variables consist of progressively corrupted versions of the original data. Let \mathbf{x}_{0} be the original data and \mathbf{x}_{1:T} be the latent variables at timesteps 1,\dots,T . The ELBO objective of HVAE can be written as: \displaystyle\max_{\theta,\phi}\;\;\mathcal{L}_{\theta,\phi}^{\mathrm{ELBO}} \displaystyle=\mathbb{E}_{\mathbf{x}_{1:T}\sim q_{\phi}(\mathbf{x}_{1:T}\mid\mathbf{x}_{0})}\Bigg[\sum_{t=1}^{T}\log p_{\theta}\bigl(\mathbf{x}_{t-1}\mid\mathbf{x}_{t:T}\bigr)+\log p_{\theta}\bigl(\mathbf{x}_{T}\bigr)\;-\;\log q_{\phi}\bigl(\mathbf{x}_{1:T}\mid\mathbf{x}_{0}\bigr)\Bigg], (4) where q_{\phi}(\mathbf{x}_{1:T}\mid\mathbf{x}_{0})