arXiv AI

Masked diffusion as random sequential adsorption: an exactly solvable model for parallel decoding

Masked diffusion models generate text by reversing a stochastic masking process, allowing many tokens to be revealed in parallel at the cost of errors due to independent token draws. The paper maps this trade‑off onto driven many‑particle systems, showing that for Markov data the process is a solvable random sequential adsorption model and that the error equals entropy production relative to the reversed masking. For many steps, the error corresponds to dissipation in a slowly driven system, with optimal schedules being geodesics of a thermodynamic metric derived from token mutual information, revealing how text correlations influence error concentration and output quality.

arXiv Machine Learning
Oct 9

The Lattice of Transition Laws

The paper introduces a framework that unifies diffusion and autoregressive (AR) generative models as paths on a corruption lattice, defining a cost for decoding schedules based on discarded parallel steps. It shows that the minimal number of steps for a zero‑cost schedule is determined by the data’s geometry—specifically, the graph’s treedepth for Markov data—providing a theoretical limit for both token and continuous field models. By estimating pairwise dependencies from pretrained weights, the authors predict the ranking of decoding schedules before execution, and validate these predictions across text, image, and video generation tasks.

By T. Y. Tsui, Jiatao Gu, Lingjie Liu
arXiv Machine Learning
Sep 18

Parallelism, critical windows, and separations among diffusion language models

The paper compares the parallelism capabilities of three diffusion large language model paradigms—masked, uniform, and Gaussian diffusion. It proves that uniform and Gaussian diffusion can sample with a number of forward passes scaling with the dual total correlation of the distribution, potentially much less than the context length, whereas masked diffusion may require more passes. The study establishes a provable separation in parallelism, showing that masked diffusion’s critical windows are asymptotically narrower than those of the other two approaches.

By Sitan Chen, Liye Wang
Hugging Face Trending Papers
Oct 8

The Lattice of Transition Laws

The paper investigates how to predict the performance of decoding schedules for generative models that blend diffusion and autoregressive (AR) approaches. By modeling diffusion, AR, and hybrid models as paths on a corruption lattice, the authors define a schedule cost based on discarded parallel steps and show that the minimal zero‑cost schedule is determined by the data’s geometry, such as the treedepth of a Markov graph. They further demonstrate that schedules with fewer steps than the treedepth incur a positive cost, which can be ranked in advance using a kernel derived from pretrained weights, and validate these predictions across text, image, and video generation tasks.

arXiv Computation and Language
Aug 27

Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

The paper introduces a new framework for adaptive parallel sampling of discrete vectors, where a deterministic policy reveals coordinates round‑by‑round based on previously observed values and samples the remaining coordinates from their exact conditional marginals. The authors prove an exact identity linking the forward Kullback‑Leibler divergence of any policy to the expected conditional total correlation accumulated during the sampling process, establishing conditional total correlation as the precise information cost of within‑round parallelism. Using this identity, they derive zero‑error schedules for finite‑order Markov chains, characterize the serial depth of Bernoulli walks, and demonstrate separations between different reveal orders, permutation strategies, and string structures, thereby revealing how conditional dependence governs parallelizability. whyItMatters":"The results provide a principled, information‑theoretic measure of parallel sampling efficiency that can guide the design of decoding rules for masked diffusion models and other generative systems."

By Chuling Wen, Weijie Liang, Jian Lu
arXiv Computation and Language
Oct 22

Hierarchical Masked Diffusion Language Models

arXiv:2610.29255v1 Announce Type: new Abstract: Masked diffusion language models have emerged as an alternative to autoregressive models, enabling parallel token generation. However, standard masked...

By Parul Gupta, Satwik, Avni Aggarwal, Bhavesh Gurnani, Arnab Kumar Mondal, Dinesh Khandelwal, Dinesh Garg, Parag Singla
arXiv AI
6d ago

When Should Diffusion Language Models Reconsider Their Commitments?

Masked Diffusion Models (MDMs) generate text quickly through parallel decoding but can commit to inconsistent predictions. The paper introduces PURL, a training framework that unifies parallel generation with selective token revision by learning a joint transition over edit selection, unmask selection, and token prediction. Experiments on logic puzzles, mathematical reasoning, and code generation show PURL improves accuracy by up to 47.4% and reduces decoding rounds by up to eightfold, while revealing that effective revisions depend on timing and context.

By Haoyang Zheng, Yidong Ouyang, Blake Jianhang Chen, Tian Tan, Ziqian Lin, Liqian Peng, Alec Go, Guang Lin
arXiv AI
Jul 17

Token Time Continuous Diffusion for Language Modeling

arXiv:2607. 14106v1 Announce Type: cross Abstract: In this paper we introduce token time continuous diffusion (TTCD), a new diffusion language model which (a) operates in continuous space, deterministically mapping Gaussian noise to a final token canvas with no further sampling, and crucially (b) incorporates a new notion of per-token times, with some tokens proceeding from noise to token at a faster rate than others.

By Parikshit Bansal, Sujay Sanghavi