Paper · 2026-10-29 · cs.LG
End-to-End Guarantees for Masked Diffusion Models under Conditional Mixing
Gives an end-to-end KL bound for a learned masked-diffusion denoiser, assuming averaged exponential decay of token influence. Training needs (1/ε')^O(τc log|V|) sequences, independent of length N. A dilated schedule reaches KL ≤ ε+Nε' in O(τc log(N|V|/ε)) steps, versus Ω(N) for random order on an explicit source. Author-reported: MDLM saturates at 24 dilated vs 96 random steps.
Discrete diffusionMasked language modelingDecoding strategiesLooped transformermasked-diffusionsample-complexityparallel-decodinglearning-theoryconditional-mixing
AI-compiled by claude-haiku-5-5 on 2026-11-21, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
In plain words
Masked diffusion language models write text by starting from a sequence of blanks and filling several blanks in each step, rather than producing one word at a time from left to right. Filling many blanks together is fast, but the words filled in the same step can depend on each other, and ignoring that dependence costs quality. Two practical questions follow: how much training data is needed before the model's guesses are good, and how many steps are needed before the filled-in text is close to the true distribution.
The paper answers both for text whose words depend mostly on nearby words. If the effect a distant word has on a blank fades quickly with distance, a model trained on a fixed amount of data is good enough for any order of filling blanks, and that amount does not grow with the length of the text. If each step fills blanks that are far apart, the error from filling them together stays small, and the number of steps can grow with the logarithm of the text length. A random filling order does not get this benefit. The author checks the ordering of these predictions on a released model and on fine-tuned versions of it, and presents the results as supporting the qualitative picture rather than the exact constants.
TL;DR
For masked diffusion with a learned denoiser, the paper bounds the KL divergence of the sampler's output under conditional mixing, a source assumption that the average influence of distant visible tokens on a masked token decays exponentially §3. The denoiser needs (1/\varepsilon')^{O(\tau_c\log|\mathcal V|)} training sequences, independent of length N, and the bound holds for any decoding schedule when the denoiser is trained under that schedule's weighting §4 §5. A dilated schedule reaches \mathrm{KL}\le\varepsilon+N\varepsilon' in O(\tau_c\log(N|\mathcal V|/\varepsilon)) steps, where a random order needs \Omega(N) on an explicit source §5. Relevant if you need a sample budget and a step count for parallel decoding; the constants are loose and the experiments are small.
Problem
Existing sampling bounds for masked diffusion models assume an exact denoiser, or leave the denoiser's error uncontrolled §1. Training bounds cover only the masking distribution used in training, so they do not say what happens at the masking patterns that a parallel decoder visits §1 §4. The paper asks for one guarantee across the masking patterns of any non-adaptive decoder, with a per-token budget independent of both the decoder and N §1. The assumption that makes this possible is conditional mixing §3.
Method
Setting and objective §3. \mathcal V is a finite vocabulary, \bar{\mathcal V}=\mathcal V\cup\{\mathtt{[mask]}\}, z is the set of visible positions and M the masked ones. Training sequences are drawn i.i.d. from \pi, the length-N marginal of a stationary process. The forward process keeps each token with probability \alpha_t, with \alpha_t=1-t in the analysis §3. The analysed loss is the unweighted masked cross-entropy (eq. 1), in which the denoiser f(\cdot\mid i,z,x_z) returns a distribution over \mathcal V and takes no time input §3.
Weightings and excess risk §3. A weighting \omega is a joint law over (i,z,x). It is admissible when x_i given (i,z,x_z) follows \pi(\cdot\mid x_z). For admissible \omega, the excess risk \mathcal E_\omega(f) equals the expected KL between the true conditional and f (eq. 2). Every masking distribution counts as admissible; so does the weighting \omega_\nu that a strategy \nu induces when run on x\sim\pi with teacher forcing app. A.3 (Proposition 3). With uniform masking \omega_{\mathrm u}, the unweighted masked cross-entropy equals \frac{N}{N+1}R_{\omega_{\mathrm u}} (eq. 3), so standard training is empirical risk minimisation at \omega_{\mathrm u} §3.
Sampler and error split §3 §5. The sampler is the monotone sampler of Lavenant and Zanella (2025). It fills one commit set per step, and each position in a set is filled independently given the visible tokens §3. The per-step KL splits exactly into a sum of per-token excess KLs plus the total correlation of the true conditional, which training does not affect (eq. 4) §3. Summing over steps gives \mathrm{KL}(\pi\Vert p_{\mathrm{alg}})\le\mathcal E_{\mathrm{learn}}+\mathcal E_{\mathrm{fact}} (eq. 9), where \mathcal E_{\mathrm{learn}} is N times the per-token excess under the strategy's weighting and \mathcal E_{\mathrm{fact}} is the summed total correlation within commit sets §5. The paper converts between entropy and total variation with an Audenaert–Fannes bound (eq. 11) app. A.1.
Conditional mixing §3. The averaged influence coefficient \bar\kappa(d) (eq. 5) is the largest average total-variation shift in a masked token's conditional when visible tokens farther than d from it are removed, with the supremum over the other arguments §3. Conditional mixing (Assumption 1) requires \bar\kappa(d)\le C_0e^{-d/\tau_c} for all d\ge0 (eq. 6) §3. Strong conditional mixing (Assumption 2) requires the same bound on the worst-case coefficient \kappa(d) (eq. 7) §3. Strong mixing implies mixing with the same constants, but not the reverse §3.
Two source families satisfy strong conditional mixing, with constants given in closed form §3:
- Order-r Markov sources with transition floor q_{\min} (Proposition 1). With \Delta_r=2r\log(1/q_{\min}) and \vartheta_r=\tanh(\Delta_r/4), the correlation length is \tau_c=r/\log(1/\vartheta_r)\le r/(2q_{\min}^r) and C_0=2\Delta_r/\vartheta_r^3.
- Hidden Markov sources whose hidden-state kernel is sandwiched between two multiples of one fixed distribution (eq. 8) (Proposition 2). With \Delta_\Gamma=4\log(1/\gamma_{\mathrm D}) and \vartheta_\Gamma=\tanh(\Delta_\Gamma/4), the correlation length is \tau_c=1/\log(1/\vartheta_\Gamma)\le1/(2\gamma_{\mathrm D}^2) and C_0=2\Delta_\Gamma/\vartheta_\Gamma.
Denoiser class and sample complexity §4 app. A.4. The window class \mathcal F_w (Definition 1) holds denoisers that read only the w positions on each side of the target. Each is a table over the 2w window contexts, mixed with the uniform distribution at weight \lambda=|\mathcal V|p_{\min}, so every output probability is at least p_{\min} and the log-loss is at most \ell_{\max}=\log(1/p_{\min}).
Theorem 1 §4 gives two parts:
- (a) With the constants below, the empirical risk minimiser \hat f over \mathcal F_w, trained under any masking distribution \omega, has \mathcal E_\omega(\hat f)\le\varepsilon' with probability at least 1-\delta whenever n\ge(1/\varepsilon')^{2+2\tau_c\log|\bar{\mathcal V}|+o(1)}\,|\mathcal V|\log(2/\delta).
- (b) Under strong conditional mixing, part (a) holds for every admissible \omega, including weightings induced by adaptive strategies that are fixed before the training sample is drawn.
Proof idea: the excess splits into an approximation term and an estimation term §4. Approximation: truncating the context to the window and mixing with the uniform gives \min_{f\in\mathcal F_w}\mathcal E_\omega(f)\le(\ell_{\max}+1)(\bar\kappa_\omega(w)+\lambda) (Lemma 3) app. A.4. Estimation: a finite cover of the class, Hoeffding, and a union bound over the |\bar{\mathcal V}|^{2w}|\mathcal V| log-probabilities (Lemma 2) app. A.1 app. A.4. For the uniform-masking cross-entropy minimiser the bound holds with a factor (N+1)/N on the estimation terms app. A.1.
Lower bound (Theorem 2) §4: for \tau_c\ge1, C_0\ge16 and |\mathcal V|\ge2, there is a family of sources, each with strong conditional mixing at (\tau_c,C_0), such that for the weighting \omega^* that hides the final position and shows only the d preceding tokens, any learner needs n(N-d)\ge|\mathcal V|^{d-1}/(300\varepsilon') to reach excess \varepsilon'. In the paper's notation this is (1/\varepsilon')^{1+(1-o(1))\frac{\tau_c}{6}\log|\mathcal V|} sequences for N\in\Theta(d) §4. So the exponent's order matches Theorem 1.
Conditional floor (Corollary 5) app. A.4: if the source's masked conditionals are at least q_c, and mean-square conditional mixing holds, the \tau_c coefficient of the exponent halves, giving (1/\varepsilon')^{2+\tau_c\log|\bar{\mathcal V}|+o(1)}. For order-r sources, q_c\ge q_{\min}^{r+1} app. A.4.
Looped class §6.2 app. A.4. On an order-r Markov source, repeated application of one shared kernel recovers the true conditional, with entries in [q,1] and q\le q_{\min}, over \Lambda loops per side (Definition 2, Lemma 4). With \Lambda=\lceil(\tau_c/r)\log(6C_0(\ell_{\max}+1)/\varepsilon')\rceil and n\ge\frac{32\ell_{\max}^2}{\varepsilon'^2}\bigl[|\mathcal V|^{r+1}\log\frac{48L_{\mathrm{cov}}}{\varepsilon'}+\log\frac2\delta\bigr], with L_{\mathrm{cov}}\le4r/q^{r+1}, the empirical risk minimiser over this class reaches excess \varepsilon' with probability 1-\delta for every admissible \omega (Corollary 4) §6.2. The paper analyses an idealised message-passing class, not a transformer.
End-to-end guarantees §5.
- Corollary 1(i): for a non-adaptive schedule \nu chosen independently of the training sample, with the denoiser trained under \omega_\nu, \mathrm{KL}(\pi\Vert p_{\mathrm{alg}})\le\mathcal E_{\mathrm{fact}}(\nu)+N\varepsilon' with probability at least 1-\delta §5.
- Corollary 1(ii), dilated schedule: at step t\in\{1,\dots,b\} commit the positions t, t+b, t+2b,\dots. With b=1+\lceil\tau_c\log(2C_0NL^*/\varepsilon)\rceil and L^*=\log(e|\mathcal V|)+\log(1+2C_0N/\varepsilon) (eq. 19), the schedule takes T=b steps and has \mathcal E_{\mathrm{fact}}\le\varepsilon, so \mathrm{KL}\le\varepsilon+N\varepsilon' §5 app. A.5.
- Corollary 2, random order §5: on the two-state chain with flip probability q\in(0,\tfrac12), for any random-order schedule whose expected KL is at most \varepsilon (with exact conditionals), \mathbb E[T]\ge c_qN/(c_q+2\varepsilon), where c_q=8q^4(1-q)^4(1-2q)^2. A dilated schedule needs O(\tau_c\log(N/\varepsilon)) steps on this source §5.
Block-autoregressive samplers §6.1. The sequence is split into m blocks of size B, generated left to right. Within each block the monotone sampler runs with the earlier blocks visible §6.1. Corollary 3: (i) with the denoiser trained under the induced weighting at the same n, \mathrm{KL}\le\sum_k\mathbb E[\mathcal E^{\mathrm{fact}}_{(k)}]+N\varepsilon', so the sampler adds no error across blocks beyond the factorisation terms; (ii) a dilated schedule at spacing \min\{b^*(\varepsilon),B\} inside each block gives factorisation error at most \varepsilon in T=(N/B)\min\{b^*(\varepsilon),B\} steps, where b^* is the spacing of Corollary 1 §6.1.
Pseudocode below is our reading of the paper's definitions. Positions are 0-indexed here; the paper's t\in[b] is 1-indexed.
# Dilated schedule: step t commits positions t, t+b, t+2b, ... [§5] [app. A.5]
# Takes b steps in total [§5]
def dilated_schedule(num_positions, spacing):
steps = []
for start in range(spacing):
# Positions in one commit set are at least `spacing` apart [§5]
commit_set = list(range(start, num_positions, spacing))
steps.append(commit_set)
return steps# Spacing b for factorisation error eps [app. A.5] [eq. 19]
# Spacing is capped at N: then every step commits one position [app. A.5]
def dilated_spacing(num_positions, eps, tau_c, c0, vocab):
# Log factor L* [eq. 19]
log_factor = log(e * vocab) + log(1 + 2 * c0 * num_positions / eps)
# Spacing [eq. 19]
spacing = 1 + ceil(
tau_c * log(2 * c0 * num_positions * log_factor / eps)
)
return min(spacing, num_positions)# Monotone sampler over a schedule [§3] [§5]
# Each commit set is filled independently given the visible tokens [§3]
def sample(denoiser, schedule, num_positions):
# Start with every position masked [§3]
tokens = [MASK] * num_positions
for commit_set in schedule:
# Read all conditionals before any token of this step is written [§3]
probs = {i: denoiser(i, tokens) for i in commit_set}
for i in commit_set:
# Draw token i from its own conditional [§3]
tokens[i] = sample_categorical(probs[i])
return tokens# Window context of a masked position [app. A.4] [def. 1]
# Offsets -w..w excluding 0; MASK at masked or out-of-range positions
def window_context(tokens, i, w):
offsets = [o for o in range(-w, w + 1) if o != 0]
context = []
for offset in offsets:
j = i + offset
if j < 0 or j >= len(tokens) or tokens[j] == MASK:
context.append(MASK)
else:
context.append(tokens[j])
return tuple(context)# Window denoiser output: learned table mixed with uniform [app. A.4] [def. 1]
# table[context] is a distribution over the vocabulary, learned per context
def window_predictor(table, context, vocab, lam):
uniform = ones(vocab) / vocab
# lam = |V| * p_min keeps every probability at least p_min [app. A.4]
return (1 - lam) * table[context] + lam * uniform# Constants of Theorem 1(a) for a target excess eps [§4]
def theorem1_constants(tau_c, c0, vocab, eps):
# Logarithm of the floor denominator [§4]
s0 = log(10 * vocab / eps)
# Floor on every output probability [§4]
p_min = eps / (10 * vocab * s0)
# Cap on the log-loss [§4]
l_max = log(1 / p_min)
# Window half-width [§4]
w = ceil(tau_c * log(4 * c0 * (l_max + 1) / eps))
return p_min, l_max, wHyperparameters
Constants and schedules used by the theory:
| Name | Value | Where | Notes |
|---|---|---|---|
| masking law in analysis | \alpha_t=1-t, t\sim U[0,1] | §3 | Stated for the loss in eq. 1 and the identity in eq. 3 |
| probability floor p_{\min} | \varepsilon'/(10\lvert\mathcal V\rvert\log(10\lvert\mathcal V\rvert/\varepsilon')) | §4 | Used in Theorem 1(a); \ell_{\max}=\log(1/p_{\min}) |
| window half-width w | \lceil\tau_c\log(4C_0(\ell_{\max}+1)/\varepsilon')\rceil | §4 | Context has 2w positions; the paper's proof adds one to w when substituting |
| mixing weight \lambda | \lvert\mathcal V\rvert p_{\min} | app. A.4 | Definition 1: mix with uniform |
| cover resolution \rho | \varepsilon'/16 (ERM under \omega); \varepsilon'/24 (masked CE) | app. A.4 | Proof of Theorem 1 |
| sample size (explicit) | n\ge\frac{72\ell_{\max}^2}{\varepsilon'^2}\bigl[\lvert\bar{\mathcal V}\rvert^{2w}\lvert\mathcal V\rvert\log\frac{72\ell_{\max}}{\varepsilon'}+\log\frac2\delta\bigr] | app. A.4 (eq. 16) | Before the exponent is simplified |
| dilated spacing b | 1+\lceil\tau_c\log(2C_0NL^*/\varepsilon)\rceil, capped at N | app. A.5 (eq. 19) | T=b steps |
| looped count \Lambda | \lceil(\tau_c/r)\log(6C_0(\ell_{\max}+1)/\varepsilon')\rceil | §6.2 | Corollary 4 |
| order-r Markov constants | \Delta_r=2r\log(1/q_{\min}), \vartheta_r=\tanh(\Delta_r/4), \tau_c, C_0=2\Delta_r/\vartheta_r^3 | §3 (Proposition 1) | |
| Doeblin HMM constants | \Delta_\Gamma=4\log(1/\gamma_{\mathrm D}), \vartheta_\Gamma=\tanh(\Delta_\Gamma/4), C_0=2\Delta_\Gamma/\vartheta_\Gamma | §3 (Proposition 2) |
Settings of the experiments, as reported in the paper's training table:
| Setting | dilated fine-tune | uniform control | looped model | block-AR models |
|---|---|---|---|---|
| Starting point | MDLM checkpoint | MDLM checkpoint | random init, seed 0 | random init, seed 0, shared across B |
| Training data | OpenWebText train, seed 0 | same windows as fine-tune | OpenWebText train | synthetic, 20{,}000 sequences |
| Context | 1024 | 1024 | 1024 | 256 |
| Tokens / steps | 0.25B / 7630 | 0.25B / 7630 | 4B / 7630 | plateau rule, 1500--8000 steps |
| Batch (sequences) | 32 | 32 | 512 | 256 |
| Optimizer | AdamW (0.9,0.999) | AdamW (0.9,0.999) | AdamW (0.9,0.95) | AdamW (0.9,0.999) |
| Learning rate | 10^{-5} | 10^{-5} | 3\times10^{-4} | 3\times10^{-4} |
| Warmup, then | 100, constant | 100, constant | 2500, constant | 500, constant |
| Weight decay | 0 | 0 | 0.1 | 0.01 |
| Gradient clip | 1.0 | 1.0 | 1.0 | none |
| Dropout | 0.1 | 0.1 | 0.1 | none |
| Numerics | bf16 with fp32 loss | bf16 with fp32 loss | bf16 with fp32 head | fp32 throughout |
| Mask schedule | dilated, b\in\{8,16,32,64\} | uniform t\sim U(0,1) | uniform, loop \Lambda\sim U\{1..12\} | block-B prefix |
| Loss | unweighted CE, class k | unweighted CE, all masked | ELBO 1/t | unweighted CE, block k |
Source: tab. 2 app. B.1. The looped model applies weight decay to weight matrices alone tab. 2. Hardware: a single A100-SXM4-40GB; about 130 GPU-hours in total app. B.1.
Measurement settings app. B:
- Influence probe: released MDLM checkpoint; target position uniform on [64,961); visibility i.i.d. Bernoulli with v\in\{0.25,0.5,0.9\}; distances d\in\{1,2,4,8,16,24,32,48,64\}; 1000 configurations per cell; \hat I estimated on 192 windows app. B.2.
- Block experiment: synthetic order-3 chain over four symbols, q_{\min}=0.136, fitted \tau_c=0.977, C_0=2, b^*(1)=10, threshold 4b^*(1)=40; decoding with T=N/4 steps; block sizes B\in\{4,8,16,32,64,128\} app. B.3.
- Forward error: step grid T\in\{1,2,4,8,16,24,32,48,64,96,128\}; saturation tolerance \delta=0.03 (eq. 23); 512 windows; bootstrap intervals over 1000 resamples app. B.4.1.
- Generation: unconditional at N=1024; 14 step counts up to 128 plus \{192,256,384,512\} for MDLM; eight step counts for LLaDA-8B; sampling in fp32 without truncation; MAUVE reference set of 512 windows; the MAUVE setting is printed as "mauve-text 0.40" app. B.4.2.
- Saturation fit: hinge fit \hat T^*=2^{(a-\ell_{\mathrm{floor}})/c} over T\le128 (eq. 24) app. B.4.2.
- Loop experiment: loop count drawn uniformly from \{1..12\} per microbatch; t clamped at 10^{-3}; saturation fit in eq. 25 app. B.5.
Results
Author-reported. All results come from single runs unless stated; the bootstrap intervals are given where the paper reports them §7 app. B. The paper calls the influence measurements qualitative evidence, since they probe a trained model's conditionals rather than the data's own §7.
Table 1 summarises the headline checks tab. 1:
| Prediction | Result |
|---|---|
| Influence measured on the MDLM model | |
| average influence falls off exponentially (Assumption 1) | exp. fit R^2 0.989 vs. power law 0.966 |
| worst-case influence stays large (Assumption 2) | 95th pct. 0.72 at d=64 |
| dilated factorization term \hat I\approx0 by b=16 | yes; random order \ne0 at 64 |
| Block size on a synthetic source (Corollary 3) | |
| held-out excess small at every B | \leq 0.031 nats |
| no degradation for B\ge 4b^*(1)=40 | holds |
| Decoding steps on MDLM and LLaDA-8B (Corollaries 1 and 2) | |
| dilated saturates within [8,32] | fwd. 24 (released), 32 (finetunes); gen. 9.7; LLaDA: none by 128 |
| dilated saturates before random | fwd. 24 vs. 96, 32 vs. 64; gen. 9.7 vs. 44.7 |
| saturation well below b^*(1)\approx860 | 9.7--32 steps |
Influence §7 app. B.2 tab. 3. On MDLM, replacing visible tokens beyond distance d with those of an unrelated window shifts the conditional less and less as d grows, and the mean shift fits an exponential better than a power law. The tail decay scale is about 81 (interval [43, 95]) and the local scale over short distances is about 26. The 95th percentile falls from 0.999 at d=1 to 0.722 at d=64. The dilated term \hat I is indistinguishable from zero at spacing 16, while the random-order term at spacing 64 is still clearly above zero.
Table 3 tab. 3:
| Quantity | Value |
|---|---|
| R^2, mean decay exponential fit | 0.989 |
| R^2, mean decay power-law fit | 0.966 |
| (\hat\tau_c,\widehat C_0) on the tail window; interval for \hat\tau_c | (81.1,\,1); [43,95] |
| local decay scale over the first distances | {\approx}26 |
| 95th percentile of \hat\kappa at d=1 / d=64 | 0.999 / 0.722 |
| \hat I(16), dilated: point / upper interval edge (per summand) | 0.0036 / 0.042 |
| \hat I(64), random order (per summand) | 0.087 |
Block size §7 app. B.3. Six block-autoregressive models that differ only in B are trained on the synthetic source, which has exact conditionals. The held-out excess stays below 0.031 nats for every B. Generation KL shows a factorisation penalty only at B=4, and none at the threshold or above. The paper also notes that the observed saturation is near B=7, below the computed window [20,80], and calls the window conservative by about five times.
Forward sampling error §7 app. B.4.1 tab. 4 fig. 2. Forward error is the teacher-forced cross-entropy of each schedule. At each matched step count T\ge2, dilated decoding has lower error than random order. Its saturation step is 24 on the released model (interval [24, 32]) and 32 on both fine-tunes, against 96 and 64 for random order. The paper calls this inside the predicted band [8,32].
Table 4 tab. 4:
| T | 1 | 2 | 4 | 8 | 16 | 24 | 32 | 48 | 64 | 96 | 128 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| released, dilated | 7.556 | 4.654 | 3.703 | 3.381 | 3.260 | 3.241 | 3.230 | 3.235 | 3.219 | 3.229 | 3.223 |
| released, random | 7.556 | 5.210 | 4.192 | 3.708 | 3.482 | 3.409 | 3.376 | 3.339 | 3.324 | 3.292 | 3.286 |
| dilated finetune, dilated | 7.557 | 4.633 | 3.685 | 3.371 | 3.256 | 3.226 | 3.212 | 3.200 | 3.194 | 3.190 | 3.188 |
| dilated finetune, random | 7.557 | 5.176 | 4.146 | 3.666 | 3.439 | 3.368 | 3.333 | 3.296 | 3.280 | 3.263 | 3.257 |
| uniform control, dilated | 7.556 | 4.618 | 3.664 | 3.347 | 3.231 | 3.201 | 3.186 | 3.174 | 3.167 | 3.164 | 3.161 |
| uniform control, random | 7.556 | 5.162 | 4.130 | 3.644 | 3.415 | 3.344 | 3.309 | 3.272 | 3.256 | 3.236 | 3.230 |
Figure 2 fig. 2 plots the same values, with a zoomed panel for T\ge8. Its series are the dilated schedule on the released checkpoint and on both fine-tunes, and the random schedule on the released checkpoint.
Generation §7 app. B.4.2 tab. 5 fig. 1. Generation NLL is measured under GPT-2-large, and MAUVE uses GPT-2-large features. The dilated fit saturates at 9.7 steps (bootstrap interval [7.9, 18.2]), against 44.7 for random order. All three orders reach their lowest NLL at 512 steps. Dilated decoding's MAUVE peaks at 0.61 at 24 steps and falls to 0.02 at 512. The confidence-greedy order's MAUVE stays at or below 0.013 at every step count. LLaDA-8B keeps improving across its tested range, with no saturation observed by 128 steps under either order §7 fig. 1.
Table 5 tab. 5, MDLM, values with 95% bootstrap intervals over sequences for NLL:
| T | dil. NLL | dil. MAUVE | rnd. NLL | rnd. MAUVE | conf. NLL | conf. MAUVE |
|---|---|---|---|---|---|---|
| 1 | 8.460 [8.45,8.47] | 0.005 | 8.461 [8.45,8.47] | 0.006 | 8.460 [8.45,8.47] | 0.006 |
| 2 | 7.420 [7.41,7.43] | 0.022 | 8.132 [8.12,8.14] | 0.007 | 8.557 [8.55,8.57] | 0.005 |
| 3 | 6.636 [6.62,6.65] | 0.068 | 7.841 [7.83,7.85] | 0.007 | 8.554 [8.54,8.56] | 0.005 |
| 4 | 6.116 [6.10,6.13] | 0.158 | 7.583 [7.57,7.60] | 0.011 | 8.539 [8.53,8.55] | 0.006 |
| 6 | 5.652 [5.63,5.67] | 0.341 | 7.147 [7.13,7.17] | 0.007 | 8.512 [8.50,8.53] | 0.005 |
| 8 | 5.387 [5.37,5.41] | 0.443 | 6.698 [6.67,6.72] | 0.020 | 8.480 [8.46,8.50] | 0.006 |
| 12 | 5.287 [5.26,5.31] | 0.580 | 6.123 [6.10,6.15] | 0.010 | 8.400 [8.38,8.42] | 0.006 |
| 16 | 5.014 [4.99,5.04] | 0.512 | 5.800 [5.77,5.83] | 0.015 | 8.316 [8.29,8.34] | 0.006 |
| 24 | 4.920 [4.89,4.95] | 0.615 | 5.468 [5.44,5.49] | 0.034 | 8.105 [8.07,8.14] | 0.004 |
| 32 | 4.883 [4.85,4.92] | 0.439 | 5.310 [5.29,5.34] | 0.016 | 7.920 [7.88,7.96] | 0.005 |
| 48 | 4.922 [4.89,4.96] | 0.506 | 5.081 [5.05,5.11] | 0.025 | 7.782 [7.74,7.83] | 0.006 |
| 64 | 4.835 [4.79,4.88] | 0.251 | 4.947 [4.92,4.97] | 0.016 | 7.626 [7.57,7.68] | 0.006 |
| 96 | 4.894 [4.84,4.94] | 0.257 | 4.906 [4.88,4.93] | 0.024 | 7.390 [7.32,7.46] | 0.005 |
| 128 | 4.785 [4.73,4.83] | 0.167 | 4.771 [4.74,4.80] | 0.013 | 7.096 [7.00,7.19] | 0.008 |
| 192 | 4.801 [4.73,4.87] | 0.346 | 4.747 [4.72,4.77] | 0.011 | 6.675 [6.55,6.80] | 0.007 |
| 256 | 4.579 [4.51,4.66] | 0.083 | 4.734 [4.71,4.76] | 0.016 | 5.990 [5.83,6.15] | 0.009 |
| 384 | 4.435 [4.34,4.54] | 0.074 | 4.690 [4.67,4.72] | 0.014 | 5.306 [5.12,5.49] | 0.009 |
| 512 | 4.079 [3.96,4.20] | 0.021 | 4.661 [4.63,4.69] | 0.011 | 4.127 [3.92,4.33] | 0.013 |
Loop count §7 app. B.5 tab. 6. A looped MDLM is trained from scratch for 4B tokens, with checkpoints at 1, 2 and 4B tokens. The fitted saturation loop count moves right with training, which is the direction Corollary 4 suggests. The paper calls this experiment qualitative and incomplete app. B.5.
| checkpoint | \hat\Lambda^* (all counts) | \hat\Lambda^* (\Lambda\ge2) | loss minimum at |
|---|---|---|---|
| 1B | 2.419 | 3.16 | \Lambda=6 |
| 2B | 2.528 | 3.42 | \Lambda=6 |
| 4B | 2.621 [2.608,2.635] | 3.61 | \Lambda=7 |
Source: tab. 6.
Paper vs code
No official code.
Search order and results: the arXiv abstract page has a comment naming the workshop but no code or project link; the LaTeX source contains no repository, project or code URL; no project page is linked. GitHub repository searches for "conditional mixing masked diffusion", "masked diffusion conditional mixing" and "Sheriff diffusion" returned no results. A GitHub user search for the author's name returned one account, but neither the paper nor any page it links points to it, and its owner is not confirmed to be the author, so it was not used. No organisation search was run, since the affiliation (MIT) is not a GitHub organisation the paper names.
Pitfalls
- Which estimator you train. Theorem 1 covers a single-token empirical risk minimiser and the unweighted masked cross-entropy minimiser. The second averages over all masked positions and gets the factor (N+1)/N on the estimation terms app. A.1. The bound follows whichever weighting you train under §4.
- Train under the schedule's weighting. A denoiser trained under uniform masking is not covered when it is used with another schedule's weighting; the paper says this explicitly §4. Each schedule's denoiser needs its own training run to get the guarantee §5.
- The window class is exponential in w. It holds a separate distribution for each of the \lvert\bar{\mathcal V}\rvert^{2w} contexts app. A.4. The result is about sample complexity, not a training recipe. The looped class is the paper's route to polynomial sample complexity, and only for order-r Markov sources with a shared kernel §6.2.
- Two exponents appear. Theorem 1 displays 2+2\tau_c\log|\bar{\mathcal V}|+o(1) §4. Corollary 5 gives 2+\tau_c\log|\bar{\mathcal V}|+o(1), but only under a conditional floor and mean-square mixing app. A.4. The abstract and introduction state O(\tau_c\log|\mathcal V|) §1. Use the explicit form for budgets. For text with the GPT-2 vocabulary and a local decay scale of about 26, the paper's estimate puts the exponent in the hundreds §4.
- The o(1) is asymptotic. It is taken as \varepsilon'\to0 at fixed \tau_c, C_0 and \lvert\mathcal V\rvert §4. The paper gives no finite-\varepsilon' version.
- Constants are loose. At the fitted constants, b^*(1)\approx860 at N=1024, which is 27 to 89 times the observed saturation points of 9.7 to 32 steps §7 app. B.2. The paper says the ordering holds while the constants are loose. Do not budget steps from b^*.
- Mixing excludes some sources. Long-range parity constraints force \kappa\equiv1 and \bar\kappa\ge1/2 §3. Text whose pairwise mutual information decays as a power law is excluded. For such a source, if I(x_0;x_b)\ge cb^{-\alpha}, the dilated schedule needs polynomially many steps §5 (Remark 1). The paper's probe of MDLM finds exponential average influence, but worst-case influence that stays large §7.
- Dilated spacing at large b. When b\ge N, use b=N, which means one token per step, zero factorisation error and T=N app. A.5. Note that the formula for b depends on N and \varepsilon.
- The first dilated step has no context. It commits positions with nothing visible, so the chain-rule argument is weakest there. The paper lists schedules that avoid this as future work §8.
- Random-order numbers are per order. The forward-error table scores one fixed random order per window. Averaging over orders would score lower, by convexity app. B.4.1.
- Saturation depends on the fit. Forward saturation uses a tolerance \delta=0.03, which the paper takes as the median half-width of its intervals app. B.4.1. The generation fit is a hinge fit over T\le128 app. B.4.2. Other choices change the reported step counts.
- NLL and MAUVE disagree past 24 steps. Generation NLL keeps falling after 24 steps while MAUVE falls. The paper links the NLL trend to lower effective sampling temperature under fp32 categorical sampling, a point it takes from prior work §7 tab. 5. The saturation fit uses NLL, not MAUVE.
- Scoring details. Out-of-vocabulary tokens are clamped to EOS for NLL. For scoring, LLaDA-8B text is decoded to plain text, re-encoded with the GPT-2 tokenizer and cut to 1024 tokens app. B.4.2. The MAUVE scaling is printed as "mauve-text 0.40" and the card does not interpret it.
- Block experiment. The paper's window for the block-size threshold is [20,80], and its observed saturation is near B=7. The paper calls the window conservative by about five times app. B.3.
- Looped experiment. This is one training run per checkpoint with a loop count drawn at random per microbatch, a 1/t-weighted ELBO and t clamped at 10^{-3} app. B.5. The paper calls it qualitative and incomplete. The fitted points move by about one loop when \Lambda=1 is excluded app. B.5.
- Theorem 2 scope. The lower bound holds for N\in\Theta(d), for a specific family of sources and for the weighting \omega^* §4. It does not show that every learner needs this many samples on every source.
- Notation. \varepsilon is the factorisation budget and \varepsilon' the per-token excess. \mathcal E_{\mathrm{learn}} and \mathcal E_{\mathrm{fact}} are the two terms of eq. 9. Confusing them changes the budget.
- Sampler definition. The monotone sampler is defined by reference to Algorithm 1 of Lavenant and Zanella (2025), which this paper does not reproduce §3. The pseudocode below is our reading of the text.
Lineage
- Builds on: Lavenant and Zanella (2025), whose training–sampling decomposition gives the end-to-end composition §3 §5; strong spatial mixing of Weitz (2006), adapted to masked prediction §3; masked diffusion objectives of Sahoo et al. (2024) §3.
- Relates to: the dilated scheduler of Luxembourg et al. (2026), described as a relative of the constant-spacing schedule here §5; exact-schedule and entropy-bounded results of Ben-Hamu et al. (2025), Wen et al. (2026) and Bansal et al. (2026) §2.
- Compared against: random and confidence-greedy orders (Chang et al., 2022) in experiments §7 app. B.4.2; released MDLM (Sahoo et al., 2024) and LLaDA-8B (Nie et al., 2025) §7.
- Venue: the arXiv comments field describes a NeurIPS 2026 workshop version.
- Superseded by: not stated.
Source and license
Adapted from “End-to-End Guarantees for Masked Diffusion Models under Conditional Mixing” by Fareed Sheriff (arXiv:2610.39444), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.