wikillm

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

arXivPDFMarkdown19 min read

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.

Pseudocode
# 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
Pseudocode
# 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)
Pseudocode
# 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
Pseudocode
# 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)
Pseudocode
# 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
Pseudocode
# 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, w

Hyperparameters

Constants and schedules used by the theory:

NameValueWhereNotes
masking law in analysis\alpha_t=1-t, t\sim U[0,1]§3Stated 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'))§4Used 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§4Context has 2w positions; the paper's proof adds one to w when substituting
mixing weight \lambda\lvert\mathcal V\rvert p_{\min}app. A.4Definition 1: mix with uniform
cover resolution \rho\varepsilon'/16 (ERM under \omega); \varepsilon'/24 (masked CE)app. A.4Proof 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 b1+\lceil\tau_c\log(2C_0NL^*/\varepsilon)\rceil, capped at Napp. A.5 (eq. 19)T=b steps
looped count \Lambda\lceil(\tau_c/r)\log(6C_0(\ell_{\max}+1)/\varepsilon')\rceil§6.2Corollary 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:

Settingdilated fine-tuneuniform controllooped modelblock-AR models
Starting pointMDLM checkpointMDLM checkpointrandom init, seed 0random init, seed 0, shared across B
Training dataOpenWebText train, seed 0same windows as fine-tuneOpenWebText trainsynthetic, 20{,}000 sequences
Context102410241024256
Tokens / steps0.25B / 76300.25B / 76304B / 7630plateau rule, 1500--8000 steps
Batch (sequences)3232512256
OptimizerAdamW (0.9,0.999)AdamW (0.9,0.999)AdamW (0.9,0.95)AdamW (0.9,0.999)
Learning rate10^{-5}10^{-5}3\times10^{-4}3\times10^{-4}
Warmup, then100, constant100, constant2500, constant500, constant
Weight decay000.10.01
Gradient clip1.01.01.0none
Dropout0.10.10.1none
Numericsbf16 with fp32 lossbf16 with fp32 lossbf16 with fp32 headfp32 throughout
Mask scheduledilated, b\in\{8,16,32,64\}uniform t\sim U(0,1)uniform, loop \Lambda\sim U\{1..12\}block-B prefix
Lossunweighted CE, class kunweighted CE, all maskedELBO 1/tunweighted 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:

PredictionResult
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=16yes; 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)=40holds
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 randomfwd. 24 vs. 96, 32 vs. 64; gen. 9.7 vs. 44.7
saturation well below b^*(1)\approx8609.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:

QuantityValue
R^2, mean decay exponential fit0.989
R^2, mean decay power-law fit0.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=640.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:

T1248162432486496128
released, dilated7.5564.6543.7033.3813.2603.2413.2303.2353.2193.2293.223
released, random7.5565.2104.1923.7083.4823.4093.3763.3393.3243.2923.286
dilated finetune, dilated7.5574.6333.6853.3713.2563.2263.2123.2003.1943.1903.188
dilated finetune, random7.5575.1764.1463.6663.4393.3683.3333.2963.2803.2633.257
uniform control, dilated7.5564.6183.6643.3473.2313.2013.1863.1743.1673.1643.161
uniform control, random7.5565.1624.1303.6443.4153.3443.3093.2723.2563.2363.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:

Tdil. NLLdil. MAUVErnd. NLLrnd. MAUVEconf. NLLconf. MAUVE
18.460 [8.45,8.47]0.0058.461 [8.45,8.47]0.0068.460 [8.45,8.47]0.006
27.420 [7.41,7.43]0.0228.132 [8.12,8.14]0.0078.557 [8.55,8.57]0.005
36.636 [6.62,6.65]0.0687.841 [7.83,7.85]0.0078.554 [8.54,8.56]0.005
46.116 [6.10,6.13]0.1587.583 [7.57,7.60]0.0118.539 [8.53,8.55]0.006
65.652 [5.63,5.67]0.3417.147 [7.13,7.17]0.0078.512 [8.50,8.53]0.005
85.387 [5.37,5.41]0.4436.698 [6.67,6.72]0.0208.480 [8.46,8.50]0.006
125.287 [5.26,5.31]0.5806.123 [6.10,6.15]0.0108.400 [8.38,8.42]0.006
165.014 [4.99,5.04]0.5125.800 [5.77,5.83]0.0158.316 [8.29,8.34]0.006
244.920 [4.89,4.95]0.6155.468 [5.44,5.49]0.0348.105 [8.07,8.14]0.004
324.883 [4.85,4.92]0.4395.310 [5.29,5.34]0.0167.920 [7.88,7.96]0.005
484.922 [4.89,4.96]0.5065.081 [5.05,5.11]0.0257.782 [7.74,7.83]0.006
644.835 [4.79,4.88]0.2514.947 [4.92,4.97]0.0167.626 [7.57,7.68]0.006
964.894 [4.84,4.94]0.2574.906 [4.88,4.93]0.0247.390 [7.32,7.46]0.005
1284.785 [4.73,4.83]0.1674.771 [4.74,4.80]0.0137.096 [7.00,7.19]0.008
1924.801 [4.73,4.87]0.3464.747 [4.72,4.77]0.0116.675 [6.55,6.80]0.007
2564.579 [4.51,4.66]0.0834.734 [4.71,4.76]0.0165.990 [5.83,6.15]0.009
3844.435 [4.34,4.54]0.0744.690 [4.67,4.72]0.0145.306 [5.12,5.49]0.009
5124.079 [3.96,4.20]0.0214.661 [4.63,4.69]0.0114.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
1B2.4193.16\Lambda=6
2B2.5283.42\Lambda=6
4B2.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.