Masked Diffusion Models are Secretly Learned-Order Autoregressive Models

Prateek GargAalto UniversityBhavya KohliNUS, SingaporeSunita SarawagiIIT Bombay · 2025

Read Masked Diffusion Models are Secretly Learned-Order Autoregressive Models by Prateek GargAalto UniversityBhavya KohliNUS, SingaporeSunita SarawagiIIT Bombay (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-2511-19152.txt.

Introduction

Prateek Garg, Bhavya Kohli, and Sunita Sarawagi study masked diffusion models, a leading way to generate text-like data over discrete tokens. Such models learn to fill in masked tokens in a random order, and that order strongly affects quality. The authors ask whether training can instead find and favor a good order on its own.

Working with the continuous-time training objective and multi-part noise schedules, they link each decoding order to a matching schedule. They prove the objective splits exactly into weighted autoregressive losses over those orders. In effect, these diffusion models are autoregressive models whose generation order is learned during training.

Catalog record

CREATORPrateek GargAalto UniversityBhavya KohliNUS, SingaporeSunita SarawagiIIT Bombay
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-19152

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Masked Diffusion Models are Secretly Learned-Order Autoregressive Models Prateek GargAalto UniversityBhavya KohliNUS, SingaporeSunita SarawagiIIT Bombay Abstract Masked Diffusion Models (MDMs) have emerged as one of the most promising paradigms for generative modeling over discrete domains. It is known that MDMs effectively train to decode tokens in a uniformly random order, and that this ordering has significant performance implications in practice. This observation raises a fundamental question: can we design a training framework that optimizes for a favorable decoding order? We answer this in the affirmative, showing that the continuous-time variational objective of MDMs, when equipped with multivariate noise schedules, can identify and optimize for a decoding order during training. We establish a direct correspondence between decoding order and the multivariate noise schedule and show that this setting breaks invariance of the MDM objective to the noise schedule. Furthermore, we prove that the MDM objective decomposes precisely into a weighted auto-regressive losses over these orders, which establishes them as auto-regressive models with learnable orders. \workshoptitle Principles of Generative Modeling (PriGM) 1 Introduction Autoregressive models (ARMs) remain the dominant paradigm for sequential data generation, largely due to their natural alignment with next-token prediction tasks on domains such as text. While text data possesses an inherent left-to-right sequential structure, many other discrete modalities of interest lack such canonical orderings. For example, tabular data ( Zhu et al. 2022 ) , graphs ( Bu et al. 2023 ) , 1D tokenized images ( Yu et al. 2024 ) present ambiguity in how dimensions should be ordered for ARMs. This limitation of ARMs has also motivated research in model classes based on diffusion ( Sohl-Dickstein et al. 2015 ; Ho & Salimans 2022 ; Dhariwal & Nichol 2021 ; Ho et al. 2020 ; Song et al. 2021 ; Kingma et al. 2021 ; Karras et al. 2022 ) . While diffusion models have demonstrated remarkable success in continuous domains–including image synthesis, video generation, and speech processing–their application to discrete structures remains an active research area ( Austin et al. 2021 ; Shi et al. 2025a ; Yu et al. 2025a ; Gat et al. 2024 ; Lou et al. 2024 ; Rütte et al. 2025 ; Sahoo et al. 2025a ) . Extending diffusion-like dynamics to discrete data modalities such as natural language, molecular structures, and protein sequences is a compelling alternative to ARMs which can potentially enable parallel generation and provide trade-offs between quality and sampling speed. Recent research ( Sahoo et al. 2024b ; Shi et al. 2025a ) has positioned one variant of discrete diffusion, Masked Diffusion Models (MDMs) as particularly promising, by extending their formulations to continuous time, combining the theoretical grounding of diffusion processes with the simplicity of masked token modeling. Recent theoretical analyses ( Zheng et al. 2025 ; Ou et al. 2025 ) have revealed a fundamental equivalence: the learning objective of MDMs corresponds exactly to masked language modeling and can be interpreted as any-order autoregressive models (AO-ARMs) ( Hoogeboom et al. 2022 ) . In other words, the MDM training objective optimizes equally over all possible orders. Kim et al. 2025 introduces inference-time heuristics to select a state-dependent ordering which achieves improvements on reasoning tasks such as sudoku. This observation suggests that MDMs possess the capacity to discover and exploit ordering structures during training, with certain orderings proving more advantageous than others even when the training objective weighs each ordering equally. This is an instance of train-test mismatch, while training weighs all the ordering equally, inference does not. This motivates us to extend the MDM objective, which can discover the order during training and thus optimize for that order. Concurrently, recent work ( Wang et al. 2025 ) investigates Learned-Order Autoregressive Models (LO-ARMs) which attempts to learn a state-dependent order distribution. We instead pose a simpler question: Can the masked diffusion training objective be extended in a principled manner to learn optimal state-independent orderings? Our Contributions We prove that when extended with multivariate noise schedules, the masked diffusion objective decomposes exactly as the expectation over possible orderings ( Proposition 3.1 ), where the probability of sampling orders is defined by the noise schedule. We establish an exact correspondence of token ordering and multivariate noise schedule at inference time ( Proposition 3.2 ). In Section 4 , we validate our theoretical claims with experimental results on tabular generative modeling. 2 Background Figure 1: Forward process of masked diffusion, masks variables in a order. While for univariate noise schedules, this order is uniformly random, multivariate noise schedule makes some order more likely than others. Masked diffusion assumes a forward process where a token {\mathbf{x}}_{0} transitions to a special mask state {\mathbf{m}} at a random time defined by a noise schedule \alpha_{t} . For time t\geq s , \displaystyle q({\mathbf{x}}_{t}|{\mathbf{x}}_{s})=\alpha_{t|s}\delta_{{\mathbf{x}}_{s}}+(1-\alpha_{t|s})\delta_{\mathbf{m}} (1) where \alpha_{t}\in[0,1] is a strictly decreasing function in t , with \alpha_{0}\approx 1 , \alpha_{1}\approx 0 , and \alpha_{t|s}=\alpha_{t}/\alpha_{s} . The forward process can be interpreted as follows: Between timestep s and t , we transition to a masked state with probability 1-\alpha_{t|s} . Once masked, a token stays masked with probability 1 . This forward process admits a closed form posterior. For s<t , \displaystyle q({\mathbf{x}}_{s}|{\mathbf{x}}_{t},{\mathbf{x}}_{0})=\begin{cases}\delta_{{\mathbf{x}}_{t}}&{\mathbf{x}}_{t}\neq{\mathbf{m}},\\ \frac{1-\alpha_{s}}{1-\alpha_{t}}\delta_{\mathbf{m}}+\frac{\alpha_{s}-\alpha_{t}}{1-\alpha_{t}}\delta_{{\mathbf{x}}_{0}}&{\mathbf{x}}_{t}={\mathbf{m}}.\end{cases} (2) The reverse process conditioned on {\mathbf{x}}_{0} also has a simple interpretation–if {\mathbf{x}}_{t} is masked, it will jump to the state {\mathbf{x}}_{0} at time s with probability \frac{\alpha_{s}-\alpha_{t}}{1-\alpha_{t}} , and stay masked otherwise. Once {\mathbf{x}}_{t} is unmasked, it remains unchanged until t=0 . To learn a reverse model p_{\theta} , we optimize a variational bound (ELBO) on likelihoods. For a given a number of discretization steps T , we define s(i):=(i-1)/T and t(i):=i/T , then we can write the discrete time ELBO as: \displaystyle-\log p_{\theta}({\mathbf{x}}_{0}) \displaystyle\leq\mathbb{E}_{q}\!\left[-\log p({\mathbf{x}}_{T})-\sum_{i\geq 1}\log\frac{p_{\theta}({\mathbf{x}}_{s(i)}\mid{\mathbf{x}}_{t(i)})}{q({\mathbf{x}}_{t(i)}\mid{\mathbf{x}}_{s(i)})}\right]={\mathcal{L}({\mathbf{x}}_{0})} (3) Under mean-parameterization ( Sahoo et al. 2024a ; Shi et al. 2025a ) , the reverse model learns a distribution over {\mathbf{x}}_{0} given {\mathbf{x}}_{t} ; {\mathbf{x}}_{0}\sim\mathbf{\mu}_{\theta}({\mathbf{x}}_{t},t;\theta) and plugs into the closed form expression ( 2 ). For a sequence {\mathbf{x}}^{1:L} consisting of L tokens, such a reverse model can be optimized with the continuous time loss: \displaystyle{\mathcal{L}({\mathbf{x}}_{0}^{1:L})}=\int_{t=0}^{t=1}\frac{\alpha^{\prime}_{t}}{1-\alpha_{t}}\left(\sum_{\ell}\mathbb{E}_{{\mathbf{x}}_{t}\sim q(\cdot|{\mathbf{x}}_{0})}[\log{\bm{\mu}}^{{\mathbf{x}}^{\ell}_{0}}_{\ell}({\mathbf{x}}_{t},t;\theta)]\right){\text{d}}t (4) where \mathbf{\mu}_{\theta}^{{\mathbf{x}}_{0}} refers to the probability corresponding to the specific token {\mathbf{x}}_{0} from a distribution defined over the space of all possible values of {\mathbf{x}}_{0} . 3 Equivalence of Masked Diffusion and Learned-Order Autoregression In this section, we will explore the behavior of masked diffusion when each position has a different noise schedule \alpha_{t,\ell} , which we refer to as a multivariate noise schedule. 3.1 Reframing ELBO as Loss over Orders Proposition 3.1 The diffusion loss ( Equation 3 ) can be decomposed over the orders as follows: \displaystyle{\mathcal{L}({\mathbf{x}}_{0}^{1:L})} \displaystyle=-\mathbb{E}_{\pi}\left[\sum_{i}\mathbb{E}_{t^{*}_{\pi(i)}|\pi}\left[\log{\bm{\mu}}({\mathbf{x}}_{\pi(i)}|{\mathbf{x}}_{\pi(<i)},t^{*}_{\pi(i)};\theta)\right]\right] (5) where {\bm{\mu}}({\mathbf{x}}_{\pi(i)}|{\mathbf{x}}_{\pi(<i)},t^{*}_{\pi(i)};\theta)={\bm{\mu}}^{{\mathbf{x}}^{\pi(i)}_{0}}_{\pi(i)}({\mathbf{x}}_{\pi(<i)},t^{*}_{\pi(i)};\theta) , {\mathbf{x}}_{\pi(<i)} is a sequence obtained by masking the \pi(\geq i) indices of {\mathbf{x}}_{0} and t^{*}_{\pi(i)} is the transition time of position \pi(i) . Under a time-independent network parameterization, \displaystyle{\mathcal{L}({\mathbf{x}}_{0}^{1:L})} \displaystyle=-\mathbb{E}_{\pi}\left[\sum_{i}\log{\bm{\mu}}({\mathbf{x}}_{\pi(i)}|{\mathbf{x}}_{\pi(<i)};\theta)\right]=-\mathbb{E}_{\pi}\left[LL_{\pi}({\mathbf{x}}_{0},\theta)\right] (6) where LL_{\pi} is the auto-regressive log-likelihood computed under order \pi and expectation is taken over all orders \pi , where the corresponding probabilities are given as \displaystyle P(\pi)=\int_{\Omega_{\pi}}\left(\prod_{\ell}-\alpha^{\prime}_{t,\ell}\right) (7) where \Omega_{\pi}=\{t:t_{\pi(1)}<t_{\pi(2)}<\cdots<t_{\pi(L)}\} This expression can be interpreted as Learning-Order Autoregressive Models ( Wang et al. 2025 ) , with the key difference that our distribution over orders is state-independent ( Equation 25 ) 3.2 Relationship between Decoding Order

Read the complete text