Paper notes · arXiv 2025
Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding
Two tricks that make LLaDA and Dream an order of magnitude faster without touching the weights. Diffusion LLMs cannot use a standard KV cache because attention is bidirectional, so the paper decodes block by block and reuses keys and values that barely change between steps. And instead of unmasking a fixed number of tokens per step, it unmasks every token whose confidence clears a threshold.
Algorithm 1 puts both together. Step through it line by line:
- 1x ← [p0; [MASK], …, [MASK]]
- 2Initialize KV cache (single or dual) for x// KV cache init
- 3for k = 1 to K do
- 4s ← |p0| + (k−1)B, e ← |p0| + kB
- 5for t = 1 to T do
- 6Use cache, run pθ on x[s,e) if DualCache else x[s,:)// Cache reuse
- 7For masked xi, ci = max pθ(xi | ·)// Confidence
- 8if strategy == threshold then
- 9Unmask all i in [s,e) with ci ≥ τ, always the max ci
- 10else if strategy == factor then
- 11Sort ci descending as (c(1), …, c(m))
- 12Find largest n with (n+1)(1 − c(n)) < f
- 13Unmask top-n tokens, always the max ci
- 14end if
- 15if all x[s,e) unmasked then
- 16break
- 17end if
- 18end for
- 19Update KV cache: DualCache ? prefix & suffix : prefix// Cache update
- 20end for
- 21return x
promptblock 1block 2block 3
Loading PDF… open it directly
PDF reproduced unmodified under CC BY-NC-ND 4.0. Highlights and notes are mine.