UC Berkeley's LoSA Makes Diffusion LLMs 4.14x Faster on Long Contexts
A new sparse attention method solves the KV Inflation problem in block-wise diffusion language models, cutting attention latency up to 4.14x while lifting accuracy.
ProTakeaways
- LoSA introduces locality-aware sparse attention for block-wise diffusion language models, tackling the KV Inflation problem.
- Naive sparse attention fails on DLMs because different queries in a block select different KV pages, inflating the union up to 2x.
- Only a small fraction of tokens change hidden state between denoising steps; LoSA reuses cached attention for stable tokens.
- Sparse attention runs only for active tokens, shrinking KV cache density by 1.54x on average across LongBench.
- Delivers up to +9 to +10 accuracy points over QUEST at budget 128 on Trado-8B and SDAR-8B.
- Achieves 4.14x attention speedup on RTX A6000 and 3.67x on RTX 5090 at 64K context length.
Block-wise diffusion language models have been pitched as the escape hatch from strictly left-to-right autoregressive decoding. They fill in a whole block of tokens at once through iterative denoising, which sounds fast until you run one on a long context and watch the attention layer devour your GPU's memory bandwidth. A team from UC Berkeley, FuriosaAI, UT Austin, ICSI and LBNL has now published LoSA, a sparse attention method built for this setting, showing up to 4.14x speedups on RTX A6000 while improving accuracy over prior sparse baselines.
Why sparse attention breaks on diffusion LLMs
A block-wise diffusion language model (DLM) generates B tokens at a time in any order, with attention that is bidirectional inside the block and autoregressive across blocks. These models rely on a KV cache to reuse prefix representations, but they remain bottlenecked by prefix attention: at each denoising step, all tokens in the block must attend to the entire cached prefix. For long contexts, loading the KV cache dominates latency.
The obvious fix is to borrow sparse attention tricks from autoregressive LLMs, like QUEST, which pick a small subset of KV positions per query. That approach falls apart on DLMs because of what the authors call the KV Inflation problem. Even though each query selects only k KV positions, different queries may select different positions, so the effective number of KV positions loaded can become much larger than k, negating the intended speedup from sparsity. In the worst case the union grows to min(L, Bk), and empirically it can inflate attention density by roughly 2x.