wikillm

Paper · 2026-10-29 · cs.LG, stat.ML

An ODE-based Sampler for Discrete Diffusion Models

Exponential residual flows sample a discrete diffusion model from one random start, with no later noise. An ODE moves one exponential residual per position and token between jumps; a token changes when its residual reaches zero. Marginals are preserved. Author-reported quality is close to ancestral sampling at matched model calls; the deterministic paths enable consistency distillation.

Discrete diffusionDiffusion modelsKnowledge distillationProbability-flow ODEsamplingdiscrete-diffusiondistillationodetext-generation

arXivPDFMarkdown15 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

Discrete diffusion models generate sequences of tokens by changing several positions over a series of steps. The usual samplers make fresh random choices at every change, so there is no single fixed path that a faster model could learn to copy. This paper takes a different route. It draws random numbers once at the start, one per position and per possible replacement token. After that, a fixed rule moves those numbers over time, and a token changes at the moment its number runs out. The authors show that the states produced this way still have the same overall distribution as the original model. Because the path is fixed once the start is drawn, a student model can be trained to jump along it in fewer steps, which is how the authors use the idea.

TL;DR

  • Ancestral and Gillespie-style samplers draw new randomness at each jump, so they give no deterministic path to distil along §1 §3.
  • Exponential residual flows (ERF) attach one Exp(1) residual to each position and token pair. An ODE moves the residuals, and a token changes when its residual reaches zero §3 §3.1.
  • The marginals are preserved at every time under stated assumptions §3.1 app. H.
  • A practical sampler freezes the leave-one-out denoiser over each step and gives closed-form jump times for masked diffusion and for net-flux uniform diffusion §3.2 app. A.
  • Author-reported: sampling quality close to ancestral sampling at matched model calls, and consistency-distillation gains that are largest for uniform diffusion §6.

Problem

Discrete diffusion can update several positions in parallel, which is one route to faster decoding §1. Exact simulation of the reverse chain (Gillespie's method) and ancestral sampling both draw fresh randomness at every jump §1 §3. A deterministic map on a finite state space cannot split probability mass, so any deterministic analogue of the continuous probability-flow ODE needs continuous auxiliary randomness at initialisation. Masked diffusion is the hardest case, because its terminal distribution is a point mass §1. Without a deterministic trajectory, consistency distillation has no fixed target to match §4.

Method

Forward and reverse chains

Sequences have length L over a vocabulary of K tokens. The forward CTMC moves each position toward a reference distribution π with a monotone schedule α_t, where α_0 = 1 and α_1 ≈ 0. For masked diffusion the mask token is index K §2, eq. 1. The reverse rates are the forward rates weighted by marginal ratios §2, eq. 6. Sampling uses a factorised model: a denoiser D̂ that approximates the leave-one-out posterior for each position given all other positions §2.

Exponential residual flow

The augmented state is (X_t, E_t). Each residual E_t^{ℓj} is non-negative, one per position ℓ and token j §3. Start from X_1 ~ p_1 and E_1 iid Exp(1) §3.1. Between jumps X is constant and the residuals follow the ODE in eq. 9 §3.1, eq. 9.

\frac{\mathrm{d}}{\mathrm{d}t} E_t^{\ell j} = \begin{cases} \overleftarrow{Q}_t(X_t, j)[\ell], & j \neq X_t^\ell \\ -\lambda_t^\ell(X_t^\ell), & j = X_t^\ell \end{cases} eq. 9

Here the first case is the reverse rate for a change to token j, and λ is the forward exit rate of the current token §3.1, eq. 9. Running time backward from t = 1, active residuals (for other tokens) shrink and the passive residual of the current token grows. The first residual to reach zero fixes the jump time, its position and its new token §3 fig. 1.

Theorem 3.1 says that, under the assumptions in app. H, the process has finitely many jumps almost surely, and that for every deterministic time u the pair (X_u, E_u) has law p_u ⊗ Exp(1)^{⊗LK} §3.1 app. H. The state X alone is generally not Markov §1.

Gillespie's construction and the passive-residual rule

Gillespie's first-reaction method draws fresh exponentials after every jump §3 alg. 1. The next-reaction variant keeps the unused residuals. ERF keeps every residual and updates the passive ones deterministically, by the integrated exit rate, instead of resampling them §3 alg. 1 §3.1, eq. 9.

Practical discretisation

Use a grid 0 = t_0 < ... < t_K = 1. On each interval [s, t] freeze the leave-one-out denoiser D̂ evaluated at the state at t. Replace the reverse rate by the frozen rate in eq. 13, a ratio of one-position forward transition probabilities applied to D̂, times the forward rate §3.2, eq. 13. The forward exit rates are kept from the original process. Unfrozen exit rates can lead to infinitely many jumps, while the frozen version is the exact time reversal of a factorised start, so it has finitely many jumps §3.2.

Jump times come from solving, for each active pair, the equation that equates the integrated frozen rate from u to r with the residual §3.2 app. A.

  • Masked diffusion has a closed form, with the candidate time given by app. A:

T^{\ell j} = \alpha^{-1}\!\Big(1 - (1 - \alpha_r)\exp\!\big\{-E_r^{\ell j} / \hat D^{\ell j}\big\}\Big) app. A

The candidate exists only if D̂^{ℓj} > 0 and E_r^{ℓj} ≤ D̂^{ℓj} log((1 − α_r)/(1 − α_s)). Otherwise it is −∞ app. A.

  • Uniform diffusion with canonical rates has no closed-form inverse. The experiments solve it by bisection with 40 iterations §6.1 app. F.
  • Uniform diffusion with net-flux rates §3.2, eq. 15 has a closed form, with z the current token at ℓ and D̂ the frozen denoiser app. A:

T^{\ell j} = \alpha^{-1}\!\left( \frac{\big(1 + (K\hat D^{\ell z} - 1)\alpha_r\big) \exp\!\Big\{\frac{(K\hat D^{\ell z} - 1)E_r^{\ell j}}{\hat D^{\ell j} - \hat D^{\ell z}}\Big\} - 1} {K\hat D^{\ell z} - 1}\right) app. A

It applies when D̂^{ℓj} > D̂^{ℓz} and the active integral at s is at least E; otherwise it is −∞ app. A. The paper's U-NetFlux sampler uses this form §6.1.

Positions can be processed in parallel for masked diffusion, uniform diffusion and U-NetFlux, because the frozen rate at position ℓ depends only on the state at ℓ §3.2 app. A.

Algorithm 2 gives the per-interval loop with frozen rates app. A alg. 2:

Pseudocode
# One ERF interval with leave-one-out frozen rates  [alg. 2] [app. A]
# Input:  tokens (L,), residuals (L, K) at time t, interval [s, t]
# Output: tokens and residuals at time s

def erf_interval(tokens, residuals, t, s, denoiser):
    # Freeze the leave-one-out denoiser at the start of the interval  [§3.2]
    frozen = denoiser(t, tokens)                    # (L, K)
    for position in range(L):                       # parallel over positions
        now = t
        while now > s:
            # Candidate firing time of each other token  [app. A]
            fire = fire_times(position, tokens, residuals, now, s, frozen)
            # The event closest to `now` happens first  [alg. 2]
            best = argmax(fire)
            new_now = max(s, fire[best])
            # Other tokens' residuals fall by their integrated rate  [eq. 9]
            residuals[position, others] -= integrated_rate(
                new_now, now, frozen)
            # The current token's residual grows by its exit integral  [eq. 9]
            residuals[position, tokens[position]] += exit_integral(
                new_now, now, tokens[position])
            if fire[best] >= s:
                tokens[position] = best
            now = new_now
    return tokens, residuals

Distillation

The teacher's ERF map is deterministic given the augmented state: it sends (X_t, E_t) at time t to (X_s, E_s) at s = t − δ §4. The student predicts, for each position, a distribution over the clean token given (X_t, E_t) §4. The student does not predict the residuals at the endpoint §4.

The consistency loss (eq. 16) is an expectation of a divergence between the frozen target at (X_s, E_s) and the student at (X_t, E_t), with t drawn uniformly from (δ, 1) and s = t − δ §4, eq. 16. The target is a frozen EMA copy of the student that is refreshed between training rounds §4 app. D. Algorithm 4 gives the round-based loop app. D alg. 4:

Pseudocode
# Consistency distillation with per-round target refresh  [alg. 4] [app. D]
# Input: teacher, student, gap delta, rounds, updates per round

def train_consistency(teacher, student, delta, rounds, updates):
    ema = copy(student)
    for round in range(rounds):
        # Freeze the target for this round  [alg. 4]
        target = copy(ema)
        for step in range(updates):
            # Sample a clean state and noise it to a random time  [alg. 4]
            t = uniform(delta, 1)
            s = t - delta
            x_0 = sample_data()
            x_t = forward_sample(x_0, t)
            # Fresh Exp(1) residuals, independent of x_t  [alg. 4]
            e_t = exponential(size=(L, K))
            # Teacher ERF transport from (x_t, e_t) to time s  [alg. 4]
            x_s, e_s = erf_transport(teacher, x_t, e_t, t, s)
            # Student at time t matches the frozen target at time s  [§4]
            # Argument order as written in alg. 4; see Pitfalls
            loss = divergence(student(x_t, e_t), target(x_s, e_s))
            student = gradient_step(student, loss)
            ema = decay_average(ema, student)
    return student

The student for ERC is conditioned on −log E_t through a learned projection §6.2. For uniform diffusion, the student's leave-one-out output is converted to a mean-denoising distribution before the loss app. D. The joint-refresh variant also refreshes the rollout teacher from the frozen student after the first round app. D alg. 5.

Multi-step sampling with a distilled student alternates two operations: predict the clean state, then re-noise it to the next time either by the forward kernel (refresh) or by the bridge conditioned on the current state (bridge). Fresh residuals are drawn after each step §4 app. D alg. 6. Refresh is valid in general. The bridge is exact for masked diffusion and not in general for uniform diffusion app. D.

Hyperparameters

Values below are those stated in the paper. Items not in the paper are marked "not stated".

NameValueWhereNotes
BackboneDDiT, 170M (OpenWebText), 168M (TinyGSM) parameters§6Teacher trained with the standard ELBO §6.2
OpenWebText sequence length1,024§6Unconditional generation
TinyGSM canvas512 tokens, question tokens fixed§6GSM8K answers scored
Evaluation setsTinyGSM: 1,319 test questions (sampling), first 1,024 (distillation); OWT: GPT-2 Large perplexity and 1-gram entropy§6
Noise schedule for trained modelsnot stated§2Only monotone with α_0 = 1, α_1 ≈ 0
Uniform grid for samplinguniform time grid§6.1
Bisection iterations (uniform, canonical)40§6.1 app. FPer crossing-time solve
Terminal time1e-6 (Uniform), 0 (U-NetFlux)app. F
Residual clock precisionfloat64app. F
Model precisionbfloat16 autocastapp. F
Uniform substeps (bounded variant)1, 2, 4, 8, 16, 32app. FAt most one jump per position per substep
Distillation batch size128§6.2 app. F
Distillation budget50 GPU-hours (TinyGSM), 100 (OpenWebText)§6.2 app. FExcludes queue and evaluation time
Training rounds4 equal rounds§6.2
Target / teacher refreshat 25%, 50% and 75% of budgetapp. F
Gap δ grid1/8, 1/16, 1/32, 1/64§6.2 app. F
Selected δmasked TinyGSM 1/64; uniform TinyGSM 1/8; masked OWT 1/64; uniform OWT 1/16app. F
Divergenceforward KL (OWT), reverse KL (TinyGSM)§6.2 app. FSee Pitfalls on argument order
Learning rate, optimiser, EMA decay for ERCnot statedapp. DAlgorithms use symbols η and ρ only
Number of substeps in joint refreshnot statedapp. D
Sampling temperature grid, TinyGSM0.1, 0.23, 0.36, 0.49, 0.61, 0.74, 0.87, 1app. F
Sampling temperature grid, OWT0.8, 0.85, 0.9, 0.95, 1, 1.05, 1.1, 1.2app. F
Distillation NFE grid2, 4, 8, 16, 32, 64app. F
Seedstraining seed 1; sampling seed 101 (distillation); 101 and 303 (Sudoku)app. F
DiffusionGemma evaluation48 NFEs, temperature 1, canvas ≤ 256 tokens, 140 MMLU-Pro questions, 3 seedsapp. GModel: 26B total, about 4B active
Sudoku data81-cell puzzles, 40 / 35 / 30 clues; 48,000 train and 2,000 validation per difficultytab. 3Generated with seed 42
Sudoku modelDiT-style, 8 blocks, hidden 512, 8 heads, conditioning 128, sequence 164, vocabulary 15, dropout 0.1, 28,562,191 trainable parameterstab. 4Same for MDM and UDM
Sudoku teacher training20,000 steps, batch 256, bfloat16, AdamW (β₁ 0.9, β₂ 0.999, ε 1e-8), peak lr 3e-4, 2,500 warmup then constant, weight decay 0, clip norm 1, ELBO loss, antithetic time sampling, sampling ε 1e-3, EMA 0.9999, seed 1tab. 5Applied to all six runs

Results

Author-reported. Setup: OpenWebText and TinyGSM with DDiT backbones of 170M and 168M parameters §6. Baselines are the authors' own re-implementations trained from the same teacher checkpoint §6.2. Results on TinyGSM and OpenWebText are shown only as figures, so they are summarised in words.

Sampling quality (ERF vs ancestral). At matched model calls, ERF uniform and ancestral sampling give similar GSM8K accuracy on TinyGSM and overlapping entropy-perplexity curves on OpenWebText fig. 2 §6.1. The same holds for masked diffusion. Appendix F extends this to all eight NFE budgets app. F.

DiffusionGemma, MMLU-Pro (26B, about 4B active; 48 NFEs, temperature 1). Accuracy with 95% question-cluster bootstrap intervals, and seconds per question tab. 1 app. G:

SamplerAccuracy (%)s / questionSource
Ancestral57.4 [50.5, 64.3]59.4tab. 1
ERF Uniform56.7 [49.8, 63.6]61.1tab. 1
ERF U-NetFlux57.1 [50.2, 64.0]60.4tab. 1

The native procedure stops after 11.1 forward evaluations on average, while the custom samplers use 48 each, so the timings are not compute-matched app. G.

Sampler efficiency, 8 NFEs (uniform vs U-NetFlux). Seconds per sequence and token changes per generated position tab. 2 §6.1:

DatasetSamplerTime (s)JumpsSource
TinyGSMUniform0.3686.90tab. 2
TinyGSMU-NetFlux0.1301.02tab. 2
OpenWebTextUniform0.6477.11tab. 2
OpenWebTextU-NetFlux0.3231.04tab. 2

The paper reports speedups of 2.83 (TinyGSM) and 2.00 (OpenWebText) at 8 NFEs §6.1. Across NFE budgets the speedup shrinks (see tab. 6).

Runtime across NFE budgets, one AMD MI210, batches of four tab. 6 app. F:

DatasetNFEUniform (s)U-NetFlux (s)SpeedupUniform jumpsU-NetFlux jumps
TinyGSM80.3680.1302.836.901.02
TinyGSM641.5861.0281.546.871.01
TinyGSM5129.4078.1541.156.901.11
OpenWebText80.6470.3232.007.111.04
OpenWebText642.8621.8991.517.001.01
OpenWebText51216.54415.0051.106.981.01

Distillation, TinyGSM. The authors report that, at 2 and 4 NFEs, UDM ERC reaches about twice the accuracy of the best rival baseline. It is also higher at 8 and 16 NFEs and approaches the teacher by 32 NFEs. It is the only method above the teacher at some budgets fig. 3 §6.2. For MDM, ERC roughly matches the second-best baseline fig. 3 §6.2.

Distillation, OpenWebText. UDM ERC has lower generative perplexity at matched entropy than the other baselines across the frontier. MDM ERC roughly matches the second-best baseline fig. 4 §6.2.

Sudoku exact-grid accuracy (%), teacher and ERC rows only. Values are the highest two-seed mean over samplers and temperatures, as the paper selects them tab. 7 tab. 8 app. F. Baselines (SDTT, D-MMD, iDLM for MDM; DCD, D-MMD for UDM) and the sampler and temperature subscripts are omitted here; see the source tables.

FamilyDifficultyMethod1248163264
MDMEasyTeacher79.2884.9891.0895.0897.0898.2099.20
MDMEasyERC81.0886.1592.8895.8597.4598.4598.90
MDMMediumTeacher39.4050.1866.5376.8884.3389.9392.65
MDMMediumERC41.4351.8568.2878.6084.8888.9892.53
MDMHardTeacher2.687.2320.7536.1047.8857.3066.35
MDMHardERC3.708.1022.2336.5847.7557.3866.43
UDMEasyTeacher74.5092.8596.8398.0598.7099.3599.63
UDMEasyERC74.6593.2896.9598.2598.9399.5599.58
UDMMediumTeacher40.0374.3885.9590.7894.0095.5597.00
UDMMediumERC40.9575.7886.8891.2393.9395.8596.98
UDMHardTeacher7.8039.7857.5568.3574.7880.2585.73
UDMHardERC7.5040.8058.8867.3874.6380.4086.20

The UDM teacher row is the mean-parameterised teacher; the LOO-parameterised rows are not in the compiled tables tab. 8. The paper calls the Sudoku gains "modest but consistent" in many settings §6.2.

Paper vs code

No official code. The arXiv abstract page links no code or project page. A GitHub repository search for "exponential residual flow" returned one unrelated flow-matching sampler (glasgow233/AREX), and searches for "discrete diffusion ODE sampler" and for the author surnames gourevitch and janati returned no repositories. The paper cites no code URL in its source §6 app. D.

Pitfalls

  • Divergence argument order. Eq. 16 writes KL(target ‖ student) §4, eq. 16. Algorithm 4 calls the divergence with the student first, which reads as KL(student ‖ target) app. D alg. 4. The text says forward KL on OpenWebText and reverse KL on TinyGSM §6.2 app. F. The paper does not say which argument order produced those results, so check the forward/reverse labels against a small run before comparing.
  • Two names for one algorithm. The paper calls Algorithm 1 "next-reaction" in its caption and "first-reaction" in the body §3 alg. 1. The implementation difference is the passive-residual rule in Algorithm 1, which is the deterministic ERF update, not a refresh §3.1, eq. 9.
  • Masked positions do not drift. For masked diffusion the exit rate of the mask token is zero, so the passive residual at a masked position stays fixed app. A. For masked diffusion each position jumps at most once, so the ERF path has the same law as Gillespie's and bridge sampling is exact app. D.
  • Theorem assumptions. The marginal-preservation result assumes strictly positive marginals at every time, continuous rates and no explosion app. H. The main text does not discuss zero-probability states further.
  • No discretisation error bound in the main text. Exactness of the frozen sampler is shown only for factorised distributions with an exact denoiser §3.2. Compare against ancestral sampling at matched NFE before relying on it.
  • Canonical uniform rates are slow. With canonical rates, uniform sampling makes about 7 jumps per position at 8 NFEs and needs 40 bisection steps per solve. U-NetFlux makes about 1 jump and has a closed form §6.1 tab. 2. The speedup falls to 1.10 to 1.15 at 512 NFEs tab. 6. The two uniform variants also use different terminal times app. F.
  • Parallel updates need a locality property. Processing positions in parallel is valid only with the masked, uniform and U-NetFlux rates under leave-one-out freezing. Other frozen-rate choices need sequential updates §3.2 app. A.
  • Bridge sampling is not exact for uniform diffusion. Bridge sampling changes the coupling of X_t and X_0 for uniform diffusion. Refresh sampling is valid in principle, and the paper uses bridge sampling empirically app. D.
  • Boundary condition dropped. The theory asks for a boundary condition at s = 0 to remove trivial minimisers. The authors do not impose it, because it did not help and the teacher initialisation seems enough §4. For the DCD baseline, the exact boundary target gives infinite KL unless it is smoothed app. D.
  • Gumbel inputs are part of ERC. ERC conditions the student on −log E_t §6.2. Leaving that input out gives a different model, which the paper ablates §6.2.
  • Sudoku selection and noise. Each table entry is the maximum over samplers and temperatures on the evaluation puzzles, averaged over two seeds app. F. Gaps under about one point are within noise; for example MDM Hard at 64 NFEs is 66.43 for ERC against 66.35 for the teacher tab. 7. The tables have no confidence intervals.
  • DiffusionGemma comparison is not compute-matched. The native procedure averages 11.1 forward evaluations against 48 for ERF, and the 0.7-point gap lies inside the intervals tab. 1 app. G.
  • Baselines are re-implementations. All baseline numbers come from the authors' own runs from the same teacher §6.2. They are not the published numbers of those methods.
  • Missing training details. Learning rate, optimiser, EMA decay and gradient clipping for ERC on TinyGSM and OpenWebText are not stated, and neither is the noise schedule of the trained models. The number of substeps in the joint refresh is not stated either. Only the Sudoku teacher recipe is given tab. 5.
  • Timing hardware. Speed numbers are for one AMD MI210 with batches of four and do not transfer to other hardware app. F.

Lineage

  • Builds on: Gillespie's exact simulation and its first- and next-reaction variants §3 §5; continuous-time discrete diffusion, which casts sampling as exact CTMC simulation §5; the probability-flow ODE for continuous diffusion §1; and consistency distillation §4. The card gives author-year names only, because the paper's text does not supply arXiv ids.
  • Compared against: ancestral sampling, Euler and categorical τ-leaping app. C app. F; net-flux rates of Zhang et al. (2023) §3.2 §5; SDTT (Deschenaux et al., 2024), DCD (Sahoo et al., 2025), D-MMD (Hoogeboom et al., 2026) and iDLM (Li et al., 2026) §6.2; and Gumbel-based deterministic training (Zhang et al., 2026) and DDNO (Eyring et al., 2026) §1 §5.
  • Superseded by: not stated.

Source and license

Adapted from “An ODE-based Sampler for Discrete Diffusion Models” by Samson Gourevitch, Yazid Janati, Eric Moulines, Eric P. Xing, Alain Durmus, Giacomo Zanella (arXiv:2610.40618), 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.