SparseD: Sparse Attention for Diffusion Language Models
Authors: name: Zeqing Wang, name: Gongfan Fang, name: Xinyin Ma, name: Xingyi Yang, name: Xinchao Wang

While diffusion language models (DLMs) offer a promising alternative to
autoregressive models (ARs), existing open-source DLMs suffer from high
inference latency. This bottleneck is mainly due to the attention's quadratic
complexity with respect to context length in computing all query-key pairs.
Intuitively, to reduce this complexity, a natural strategy is to restrict
attention to sparse patterns that retain only the most relevant connections.
Such approaches are well-established in ARs, where attention follows fixed and
clearly defined sparse patterns. However, in DLMs, we observe distinct sparsity
behaviors: (1) attention patterns vary across heads, (2) attention patterns in
each head remain highly similar across denoising steps, and (3) early denoising
steps are critical for generation. These findings render sparse attention
methods designed for ARs largely incompatible with DLMs, as they fail to
capture head-specific structures and risk degrading generation when applied in
early denoising steps. To address these challenges, we propose SparseD, a novel
sparse attention method for DLMs. Leveraging the observations, SparseD only
requires pre-computing head-specific sparse patterns one time, and reuses them
across all steps. This prevents recomputing sparse patterns at each denoising
step. Meanwhile, SparseD uses full attention in the early steps, then switches
to sparse attention later to maintain generation quality. Together, these
establish SparseD as a practical and efficient solution for deploying DLMs in
long-context applications. Experimental results demonstrate that SparseD
achieves lossless acceleration, delivering up to 1.50times speedup over
FlashAttention at a 64k context length with 1,024 denoising steps.