Text is discrete — you cannot add Gaussian noise to a token. This lecture carries flow and diffusion to discrete data using continuous-time Markov chains, and builds a diffusion language model that fills in masked words in parallel.
For four lectures we built one machine. Start from an easy distribution (a Gaussian blob). Transport it continuously toward the data distribution by following a differential equation — an ODE for a flow model, an SDE for a diffusion model. We learned to simulate that with tiny Euler steps, and (in Lectures 2–3) to train the velocity arrows by flow matching and score matching.
Now point that machine at language. Immediately it breaks. The velocity arrow in an ODE answers "which way, how fast?" — a direction in real space. There are no directions between symbols. The Gaussian kick in an SDE adds a small real number to each coordinate. There is no "small real number" you can add to the token "the." The continuous-state assumption is baked into every formula we wrote.
Here is the analogy that will carry you through the lecture. A continuous diffusion model is like a balloon drifting on the wind — smooth, continuous motion. A discrete model is like a frog on a grid of lily-pads. The frog cannot drift halfway between pads; it sits on one pad, and at random instants it jumps to a neighbor. We get to set the rate at which it tends to jump in each direction. Generation becomes: design the jump-rates so that a frog starting on a "noise" pad hops, over time, onto a "real sentence" pad.
We will keep the running example tiny and concrete: a four-token "sentence" over a small alphabet, corrupted into [MASK] symbols and then reconstructed. Tiny enough to compute every probability by hand; structurally identical to a billion-parameter diffusion LLM.
In the continuous world a sample was a point in Rd — d real numbers. We need the discrete replacement for that, and it has exactly two ingredients.
Read the two numbers carefully — they will haunt us:
Just as before, generation is sampling. The data distribution pdata is now a probability mass function over S: it assigns to each possible sequence z a non-negative weight pdata(z), and these sum to 1 over all sequences. "All texts on the internet" is such a distribution — grammatical, sensible sentences carry high mass; keyboard mash carries near-zero mass. As always, we never see pdata; we only get a dataset of samples z ∼ pdata (a corpus).
A, B, C} (so V = 3), sequence length d = 4. A data point is a length-4 string like ABCA or CCAB. The state space has |S| = 34 = 81 possible sequences. Small enough that, in Chapter 4's code lab, we list and reason about them directly — impossible for real text, perfect for learning.
[MASK]One small but pivotal move. For the kind of model we build, we extend the vocabulary with a special extra symbol, [MASK], that means "this position has been erased — its real symbol is hidden." So the working alphabet becomes V ∪ {[MASK]}. A partially-corrupted sentence is then a mix of real symbols and [MASK] holes, e.g. A·[MASK]·C·[MASK]. This single addition is what makes the whole machine concrete and is the heart of masked diffusion language models (Chapter 7).
We have a discrete state space S. We need the discrete replacement for "transport a point continuously through time." In the continuous world that job belonged to the ODE/SDE. Here it belongs to the continuous-time Markov chain (CTMC).
"Continuous-time" refers to when the jumps can happen — at any real-valued instant, not on a fixed clock tick. "Markov chain" means the process has no memory: where it jumps next depends only on where it is now, not on the whole history of how it got there.
How do we describe a CTMC quantitatively? By its transition probabilities: for a small elapsed time h, the probability of being in state y at time t+h given you are in state x at time t. Together with the initial distribution (where you start), these probabilities fully determine the process. They are the discrete analogue of "the flow tells you where you end up."
But here is the catch we already met in the continuous world: for any interesting process we do not have a closed-form formula for those transition probabilities. In Lecture 1 we did not have the flow map either — we had the vector field and we simulated. We need the discrete analogue of a vector field: a local rule that says, instant by instant, how fast the process tends to jump where. That object is the rate matrix, and it is the entire subject of Chapter 3.
Three states (A, B, C). The colored staircase is one CTMC trajectory: flat stretches (sitting on a pad) punctuated by sudden jumps to a neighbor. Press New trajectory for fresh randomness — same rules, different path, because the dynamics roll dice. Raise the jump rate and the staircase gets busier (more, sooner jumps). Notice: between jumps nothing moves — there is no drift, only sudden teleports.
The vector field ut(x) was the soul of the continuous model: at every location and time it gave a velocity. Its discrete replacement is the rate matrix (also called the generator), written Qt. It answers the discrete version of "which way, how fast" — namely "from state x, how fast do I tend to jump to each other state y?"
The diagonal looks strange — a negative "rate of staying." Read it as bookkeeping, not a real jump. Rule (2) says: the total rate of all outgoing jumps from x, plus the diagonal, equals zero. Equivalently, the diagonal is minus the total outflow. This is exactly the constraint that keeps probability conserved — nothing is created or destroyed, mass only moves between states.
The vector field defined an ODE we Euler-stepped: Xt+h = Xt + h·ut(Xt). The rate matrix defines a CTMC, and the discrete Euler step is just as simple. Over a tiny time h, the probability of having jumped from x to a different state y is approximately rate×time:
Here δy=x (the Kronecker delta) is 1 when y equals x and 0 otherwise — it says "with no jump you stay put." The term h·Qt(y | x) is the small probability of jumping to y. Read it as: "each tiny instant, the chance of a particular jump is its rate times the elapsed time." For small h this is a valid probability distribution over the next state, and we sample from it. That single line is the discrete Euler step — the engine of every CTMC sampler.
Now the Vd problem from Chapter 1 strikes. A full rate matrix has one entry per ordered pair of states — that is |S|2 = V2d numbers. Utterly impossible to store. So real CTMC models impose a sparsity constraint: they are factorized.
x and y are neighbors (differ in the one position). For length-2 sequences, AB and AC are neighbors (only position 2 changed); AB and CC are not (two positions changed) — a factorized model forbids that double jump in a single instant. Multi-position changes still happen over the full trajectory, just never in one infinitesimal step (their probability is order h², negligible).
The continuous diffusion model needed a forward / noising process: run it forward and any data point decays into a simple Gaussian. We need the discrete analogue — a process that fades a clean sentence into pure "noise" over time t from 0 to 1. The cleanest version is masking, also called the absorbing-state process.
[MASK]. Once a token is masked it stays masked — [MASK] is an absorbing state, a lily-pad with no way out. So as corruption grows, more and more positions turn into [MASK] holes, until the whole sentence is [MASK][MASK]…[MASK]: the noise distribution.
Let a scheduler κt control how much information survives at time t. By convention κ runs from κ = 0 (everything destroyed, all [MASK]) at t = 0 up to κ = 1 (everything intact) at t = 1, increasing monotonically. The probability that a given clean token zj has survived (still shows its true value) at time t is κt; the probability it has been masked is 1 − κt.
[MASK]. Each token is a mixture — with weight κt it shows the data symbol, with weight 1 − κt it shows noise. This is the factorized mixture path: a per-token mixture that "fades in one distribution and fades out another." Same role as Gaussian noising, completely different mechanism.
Recall the two endpoints a forward process must hit. At t = 1, κ = 1, so every token survives with probability 1 — the distribution is the clean data point z (all mass on z). At t = 0, κ = 0, so every token is masked — the distribution is the fixed noise point (all [MASK]). In between it interpolates: a sentence partly real, partly holes. That is exactly the discrete analogue of "pinit at one end, pdata at the other," which is all a probability path needs to be.
ABCA (d = 4). Take the simplest linear scheduler κt = t, and evaluate at t = 0.25. Then survival probability is 0.25 and mask probability is 0.75 per token. Expected number of masked tokens = d×(1 − κt) = 4×0.75 = 3 — on average 3 of the 4 positions are holes at t = 0.25. At t = 0.75: 4×0.25 = 1 masked. At t = 1: 4×0 = 0 (clean). At t = 0: 4×1 = 4 (fully masked). The expected count of [MASK]s falls smoothly from 4 down to 0 as t grows — that monotone fade is the signature of the process.
The clean sentence sits at the top. Drag the slider to set the survival level κ (right = clean, left = fully masked). Each token independently shows its true symbol with probability κ (teal) or a █ mask hole otherwise (dim). Press Re-corrupt to roll the dice again at the same level — the pattern of holes is random, but the expected count follows d×(1−κ). The bar reports masked count vs. the theoretical expectation.
Now build the forward process yourself and confirm the expected mask-count law.
We can corrupt data into masks. To generate, we must run the process backward — turn masks into real tokens. As in the continuous case, we don't learn the reverse process directly; we learn a local object (there it was the marginal vector field / score) and the reverse follows. Here that object is the marginal rate matrix, and discrete flow matching delivers a stunning simplification of what we actually have to learn.
Fix a known clean target z. What rate matrix Qz drives the masking path for that z? Astonishingly simple: a masked token should jump only to its true symbol zj, and an already-correct token should not move. In words: "if a position is wrong (masked), un-mask it to the correct token; if it's already right, leave it." The rate of that correcting jump rises as t → 1 (set by the schedule), reflecting the urgency to finish.
Unpack it. κ̇t (read "kappa-dot") is the time-derivative of the scheduler — how fast information is being added; the prefactor κ̇t⁄(1−κt) is just a time-dependent speed. The meat is the bracket: it pushes mass toward the model's predicted clean symbol p1|t(· | x) and away from the current token (the δ term). Everything in the rate matrix is known except that one probability — the network's guess of the clean token.
Training is now ordinary supervised learning. Take a clean sentence z, pick a random time t, corrupt it to a noisy x by the masking process, and ask the network to recover each original token. Score it with the standard cross-entropy (negative log-likelihood) per position, summed over the sequence:
Read it: average over data sentences z, random times t, and noisy versions x, of the summed per-token negative-log-probability the network assigns to the true tokens. No simulation during training — just "corrupt, predict the clean tokens, penalize wrong guesses." This is the discrete analogue of the flow-matching regression loss, and it is what billion-token diffusion LLMs minimize.
[MASK]) plus the scalar time t. The network (a transformer over length d) outputs logits of shape d × V — for each position, a score per vocabulary symbol. A softmax per row turns that into pθ1|t(· | x)j, the posterior over the clean token at position j. The loss only ever asks: did you assign high probability to the real token zj? That d × V output is linear in length — the factorization (Chapter 3) is what makes this fit in memory instead of Vd.
# Discrete Flow Matching training step (one iteration) z = sample_data() # a clean sequence (z_1,...,z_d) t = uniform(0, 1) # random time kappa = schedule(t) # survival prob in [0,1] x = z.copy() for j in range(d): # forward corruption (parallel over j) if random() < (1 - kappa): x[j] = MASK # mask this token logits = net(x, t) # shape d x V (the denoiser) loss = cross_entropy(logits, z) # predict the CLEAN tokens z loss.backward(); opt.step()
We have a trained denoiser pθ1|t(· | x). Now run the CTMC forward in generation time (from the all-mask noise toward data) using the marginal rate matrix. Concretely this means: repeatedly take a noisy sequence, ask the denoiser to guess the clean tokens, and use those guesses to turn some masks into real tokens. That is the discrete Euler step (Chapter 3) wired to a learned rate.
[MASK][MASK]…[MASK]. Loop over n small steps in time:
The word parallel is the whole point. Every position is updated independently and simultaneously in each step (the factorized rate matrix allows this). One forward pass of the network produces all d posteriors at once; we then un-mask many positions in the same step. Contrast with an autoregressive LLM, which must produce token 1, then condition on it to produce token 2, and so on — strictly one at a time, left to right.
Start fully masked. Press Un-mask step to run one reverse step: a few of the most-confident positions reveal their token (teal), chosen by a toy denoiser that scores the true token highest. Watch the holes fill in out of order — high-confidence words first — not left-to-right. Reset to re-mask. The bar tracks how many positions are revealed vs. how many steps you've taken; fewer steps reveal more per step (coarser, riskier), more steps reveal more gradually.
Now implement the reverse sampler yourself: iteratively un-mask the lowest-confidence-first... no — the highest-confidence positions, committing each prediction, until the exact target is reconstructed.
Let's assemble the full pipeline and lay it next to the autoregressive (GPT-style) approach it competes with. A masked diffusion language model (MDLM) is the special, dominant case where the noise distribution is "all [MASK]" — the initial point is the fully-masked sequence.
# Sample from a masked diffusion language model # Input: trained denoiser net(x, t) -> per-position posterior; steps n t = 0.0 h = 1.0 / n x = [MASK] * d # X_0: fully masked (the noise dist.) for i in range(n): post = net(x, t) # shape d x V: clean-token posteriors for j in range(d): # PARALLEL across positions if x[j] == MASK: # discrete Euler step: small prob to un-mask this step if should_unmask(post[j], h, t): x[j] = sample(post[j]) # reveal a real token, commit it t = t + h return x # X_1, a generated sentence ~ p_data
The shape is identical to Lecture 1's flow-model sampler: draw the easy noise, loop n steps, return the endpoint. The differences are all "discrete": the noise is the all-mask sequence (not a Gaussian); each step un-masks (jumps) instead of drifting; and the network outputs posteriors over the vocabulary instead of a velocity vector.
| Autoregressive (GPT) | Diffusion LM (MDLM) | |
|---|---|---|
| Order | Strict left-to-right | Any order; often confidence-first |
| Per step | One token | Many tokens in parallel |
| Editing / in-fill | Hard (no native in-fill) | Native — just mask & re-fill holes |
| KV caching | Yes — reuse past keys/values | No — full sequence re-encoded each step |
| Inductive bias | Left-to-right matches causal text | Must learn any-order generation (harder) |
Now build the full reverse sampler: iteratively un-mask, most-confident-first, committing each prediction until the exact target is reconstructed.
Time for the payoff. Below is a complete masked-diffusion sampler running on a short target "sentence." It starts fully masked and, step by step, un-masks the most-confident positions until the whole sequence is reconstructed — exactly the loop of Chapter 7, animated. Play with the controls and watch how the number of steps and the per-step reveal budget trade off, and how the order is emergent (not left-to-right).
The target is a short word sequence. Press Generate to run the reverse process: every step, the toy denoiser scores each masked slot's true word, and the most-confident slots reveal (teal) and stay committed. Bars under each token show the denoiser's confidence. Drag steps (more steps = more gradual, smoother refinement) and reveal budget (how many positions can un-mask per step). Notice the holes fill out of order, high-confidence words first — the hallmark of parallel, any-order diffusion decoding.
(No quiz here — the simulation is the test. Make it converge in 2 steps, then in 9, and predict what changes before you drag.)
You rebuilt the entire flow-and-diffusion machine on discrete data — and discovered the recipe barely changed. Here is the whole lecture on one page, and where it sits in the series and the field.
[MASK] noise. The marginalization trick shows the marginal rate matrix is a reparameterization of a per-position denoiser p1|t(zj | x) — so training is just classification (cross-entropy), and sampling un-masks tokens in parallel, any-order.
[MASK] marks erased positions.[MASK]. Expected masked count = d·(1−κt). Teleports mass (fade out true, fade in mask) — doesn't move it through space.[MASK]; loop n steps: denoise → un-mask most-confident positions in parallel → commit → advance time. Returns X1 ∼ pdata.
[MASK] noise.