Diffusion LLM Part 2: Discrete Diffusion -- How to Add Noise to Text
D3PM, Transition Matrices, Absorbing States, MDLM -- how to bring diffusion from continuous space to discrete tokens.
Diffusion LLM Part 2: Discrete Diffusion -- How Do You Add Noise to Text?
In Part 1, we explored the principles of Diffusion operating in continuous space. Adding Gaussian noise to image pixels is natural, but text tokens are discrete data. What happens if you add noise of 0.3 to "hello"?
In this post, we cover how to bring Diffusion into discrete space. Starting from D3PM's Transition Matrix and arriving at MDLM's Masked Diffusion -- the direct ancestors of LLaDA.
D3PM: Diffusion in Discrete Space
Austin et al. (2021) raise a fundamental question in D3PM (Discrete Denoising Diffusion Probabilistic Models): how do you define a forward process for discrete data where you can't add Gaussian noise?
The answer: use a Transition Matrix.
In continuous Diffusion, Gaussian noise plays a central role. In discrete Diffusion, a transition matrix Q_t takes its place. At each step t, the probability of token x_{t-1} changing to x_t is defined by a matrix:
q(x_t | x_{t-1}) = Cat(x_t; p = x_{t-1} * Q_t)
Here, Cat is the Categorical distribution, and Q_t is a K x K matrix (where K is the vocabulary size). Q_t[i][j] represents the probability of token i changing to token j.
Correspondence with continuous Diffusion:
Related Posts
Paper of the Week #3 — Half the FLOPs Is Not Half the Time
One integer halves a fine-grained MoE's expert compute (arXiv 2609.04575) and its Table 5 replicates on one A100 to within a point. The paper never reports time, so I measured it: nothing in HF transformers, nothing at batch 1 in the vLLM you run today, 1.35x at batch 8. Plus the OLMoE control and the iso-cost harness control promised in issue #2.
The paper stopped at half the experts. A quarter loses four points instead of thirty, and a model trained without renormalization tells you why.
Two cells arXiv:2609.04575 never ran: k₁=2 and k₁=3 on Qwen3.6-35B-A3B, and the whole k₂ trick on OLMoE, which was trained without renormalization. The second one is a clean test of the paper's mechanism.
One integer halves MoE expert compute. We measured the speed the paper didn't: free at batch 8, not at batch 1.
We reproduced Table 5 of arXiv:2609.04575 on one A100 and measured the throughput the paper leaves out: nothing in HF transformers, nothing at batch 1 in stock vLLM, 1.35× at batch 8.