dLLM Notes

Paper notes · arXiv 2025

Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding

Chengyue Wu, Hao Zhang, Shuchen Xue, Zhijian Liu, Shizhe Diao, Ligeng Zhu, Ping Luo, Song Han, Enze Xie

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:

  1. 1x ← [p0; [MASK], …, [MASK]]
  2. 2Initialize KV cache (single or dual) for x// KV cache init
  3. 3for k = 1 to K do
  4. 4s ← |p0| + (k−1)B, e ← |p0| + kB
  5. 5for t = 1 to T do
  6. 6Use cache, run pθ on x[s,e) if DualCache else x[s,:)// Cache reuse
  7. 7For masked xi, ci = max pθ(xi | ·)// Confidence
  8. 8if strategy == threshold then
  9. 9Unmask all i in [s,e) with ci ≥ τ, always the max ci
  10. 10else if strategy == factor then
  11. 11Sort ci descending as (c(1), …, c(m))
  12. 12Find largest n with (n+1)(1 − c(n)) < f
  13. 13Unmask top-n tokens, always the max ci
  14. 14end if
  15. 15if all x[s,e) unmasked then
  16. 16break
  17. 17end if
  18. 18end for
  19. 19Update KV cache: DualCache ? prefix & suffix : prefix// Cache update
  20. 20end for
  21. 21return x

promptblock 1block 2block 3

Toy model, illustrative numbers: 4 prompt tokens, then 3 blocks of 4. Line 6 runs only the current block (DualCache) or the block plus every mask after it (prefix cache); everything else is read from the cache, marked by the blue strip. Lines 2 and 19 are the only full passes. Switch to the factor rule to commit more tokens per step.

Loading PDF… open it directly

PDF reproduced unmodified under CC BY-NC-ND 4.0. Highlights and notes are mine.