cond-mat.stat-mechNov 5, 2026

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

Authors: Adrian Baule

Organizations: School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, UK

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Masked diffusion models generate text by reversing a stochastic masking process. Unlike autoregressive LLMs, which generate text one token at a time, they can reveal many tokens in parallel, at the price of an error, since tokens revealed together are drawn independently. We show that this trade-off maps onto the statistical physics of driven many-particle systems. (i) For any data, the error of parallel generation is the entropy production of the generation process relative to the reversed masking process. (ii) For Markov data, generation is a random sequential adsorption process with labelled gaps, which we solve exactly for any number of steps. (iii) For many steps, the error becomes the dissipation of a slowly driven system: the unmasking schedule plays the role of the driving protocol, the number of steps that of its duration, and the error is set by a thermodynamic metric that we obtain in closed form from the mutual information between tokens. Optimal schedules are geodesics of this metric. The exact solution shows how correlations in the text shape both the error and the quality of the output. The longer the correlations, the more the error concentrates at the start of generation. Schedules that start with small steps then gain more, both in path error and in perplexity, and need fewer steps to reach their asymptotic behaviour.

Figures & tables

Figure 1: (a) A labelled gap (a,ℓ,c)(a,\ell,c) of masked sites M\mathsf{M} . Revealing the selected sites k<k′k<k^{\prime} with tokens v,uv,u splits it into three conditionally independent labelled gaps, as a deposition does in RSA. (b) The late-stage error mechanism for data with a single correlation length (binary tokens ±\pm ). A gap whose boundaries disagree contains one switch (domain wall). Two sites revealed in the same step can be drawn in the impossible order (−,+)(-,+) , which creates two spurious switches that would not occur under exact sampling.
Figure 2: Binary chain with L=4096L=4096 and NN up to 20482048 . (a) The metric G(p)G(p) , Eq. ( 30 ), for ξ=2,5,10,20,50\xi=2,5,10,20,50 (dark to light): for long correlations it is concentrated at small pp . (b) Path error NB/LNB/L against ξ\xi for the uniform, cosine and optimal schedules. Symbols: exact values from Eq. ( 22 ) at N=2048N=2048 ; solid lines: the large- NN results UU , Eq. ( 45 ), ∫01p˙2G dτ\int_{0}^{1}\dot{p}^{2}G\,d\tau and Λ2\Lambda^{2} computed from GG . (c) NB/LNB/L against NN at ξ=50\xi=50 ; dotted lines mark the large- NN asymptotic results, see (b). (d) Excess cross-entropy per token, NΔCE/LN\Delta\mathrm{CE}/L , from the master equation ( 20 ) at N=2048N=2048 , against ξ\xi .
Figure 3: Character-level English bigram model for L=1024L=1024 and NN up to 512512 . (a) The metric G(p)G(p) , normalised by G(0)G(0) , compared with the binary chain at the same correlation length, ξ=ξ1=0.76\xi=\xi_{1}=0.76 , and at ξ=50\xi=50 . (b) Path error NB/LNB/L against NN for the uniform, cosine and optimal schedules; dotted lines mark the large- NN coefficients UU , Eq. ( 45 ), ∫01p˙2G dτ\int_{0}^{1}\dot{p}^{2}G\,d\tau and Λ2\Lambda^{2} computed from GG .
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

chainLLscheduleNNδP\delta\mathcal{P}δB\delta BBB
binary, ξ=2\xi=28uniform44×10−154\times 10^{-15}5×10−165\times 10^{-16}0.3068
binary, ξ=2\xi=28cosine42×10−152\times 10^{-15}6×10−166\times 10^{-16}0.3442
binary, ξ=5\xi=58uniform48×10−158\times 10^{-15}1×10−151\times 10^{-15}0.5501
binary, ξ=5\xi=58cosine41×10−141\times 10^{-14}2×10−152\times 10^{-15}0.5405
binary, ξ=20\xi=208uniform42×10−142\times 10^{-14}<10−16<10^{-16}0.7634
binary, ξ=20\xi=208cosine42×10−142\times 10^{-14}2×10−162\times 10^{-16}0.6063
Appendix
Table 1: Exact enumeration of all generation histories, at the largest NN enumerated. δP\delta\mathcal{P} is the largest deviation of the pair counts of the master equation from enumeration, and δB\delta B the relative deviation of Eq. ( 22 ) from the enumerated path relative entropy BB .
chainscheduleNNmaster equationsimulation
binary, ξ=2\xi=2uniform80.051370.05147±0.000190.05147\pm 0.00019
binary, ξ=10\xi=10uniform40.349690.35036±0.000400.35036\pm 0.00040
binary, ξ=10\xi=10uniform160.077540.07735±0.000260.07735\pm 0.00026
binary, ξ=10\xi=10cosine640.012610.01280±0.000220.01280\pm 0.00022
binary, ξ=50\xi=50uniform160.149280.14978±0.000340.14978\pm 0.00034
three-statecosine80.020220.02024±0.000190.02024\pm 0.00019
Appendix
Table 2: Direct simulation of the parallel sampler ( L=1024L=1024 , 10410^{4} samples per row) against the master equation: excess cross-entropy per token, ΔCE/L\Delta\mathrm{CE}/L , with the standard error of the simulation. The last row simulates the exact sampler, for which ΔCE=0\Delta\mathrm{CE}=0 .
More in this topic

Masked Diffusion Models

Masked diffusion models generate sequences by repeatedly predicting and revising masked tokens, using bidirectional context for parallel sampling.

See all 194 papers

Explore similar work

CardsList

  1. Edit-Based Refinement for Parallel Masked Diffusion Language Models

    May 10, 2026Houxing Ren, Mingjie Zhan, Zimu Lu +5Masked Diffusion ModelsParallel Decoding

    CUHK MMLab · SenseTime Research · Shenzhen Loop Area Institute +1

  2. NAVIRA: Decoupled Stochastic Remasking for Masked Diffusion Language Models

    Jun 4, 2026Andrey Fomenko, Maksim Kryzhanovskiy, Svetlana Glazyrina +1Non-Autoregressive Text GenerationMasked Diffusion Models

    Lomonosov Moscow State University, Moscow, Russia · Institute for Artificial Intelligence, Lomonosov Moscow State University, Moscow, Russia

  3. Reliable Parallel Decoding in Masked Diffusion Language Models

    Sep 29, 2026Zhenghao He, Bohan Liu, Guangzhi Xiong +1Masked Diffusion ModelsDiffusion Language Model Decoding

    Department of Computer Science, University of Virginia