LoSA: Locality Aware Sparse Attention for Block-Wise Diffusion Language Models

Haocheng Xi, Harman Singh, Yuezhou Hu, Coleman Hooper, Rishabh Tiwari, Aditya Tomar, Minjae Lee, Wonjun Kang, Michael Mahoney, Chenfeng Xu, Kurt Keutzer, Amir Gholami · 2026

Read LoSA: Locality Aware Sparse Attention for Block-Wise Diffusion Language Models by Haocheng Xi, Harman Singh, Yuezhou Hu, Coleman Hooper, Rishabh Tiwari, Aditya Tomar, Minjae Lee, Wonjun Kang, Michael Mahoney, Chenfeng Xu, Kurt Keutzer, Amir Gholami (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12056.txt.

Introduction

Xi and eleven colleagues propose LoSA, sparse attention for diffusion language models generating tokens freely. Naive sparse attention fails through KV inflation, as different queries pick different prefix positions, ballooning accessed pages. Between denoising steps, few active tokens change much, while stable tokens stay nearly constant. LoSA reuses prefix-attention for stable tokens and sparse attention only for active tokens, shrinking KV indices. Across models and benchmarks it preserves dense accuracy, gaining up to 9 points at aggressive sparsity, 1.54 lower density, and up to 4.14 speedup on RTX A6000 cards.

Catalog record

CREATORHaocheng Xi, Harman Singh, Yuezhou Hu, Coleman Hooper, Rishabh Tiwari, Aditya Tomar, Minjae Lee, Wonjun Kang, Michael Mahoney, Chenfeng Xu, Kurt Keutzer, Amir Gholami
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41428
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.12056

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

LoSA: Locality Aware Sparse Attention for Block-Wise Diffusion Language Models Haocheng Xi, Harman Singh, Yuezhou Hu, Coleman Hooper, Rishabh Tiwari, Aditya Tomar, Minjae Lee, Wonjun Kang, Michael Mahoney, Chenfeng Xu, Kurt Keutzer, Amir Gholami Abstract Block-wise diffusion language models (DLMs) generate multiple tokens in any order, offering a promising alternative to the autoregressive decoding pipeline. However, they still remain bottlenecked by memory-bound attention in long-context scenarios. Naïve sparse attention fails on DLMs due to a KV Inflation problem, where different queries select different prefix positions, making the union of accessed KV pages large. To address this, we observe that between consecutive denoising steps, only a small fraction of active tokens exhibit significant hidden-state changes, while the majority of stable tokens remain nearly constant. Based on this insight, we propose LoSA ( Lo cality-aware S parse A ttention), which reuses cached prefix-attention results for stable tokens and applies sparse attention only to active tokens. This substantially shrinks the number of KV indices that must be loaded, yielding both higher speedup and higher accuracy. Across multiple block-wise DLMs and benchmarks, LoSA preserves near-dense accuracy while significantly improving efficiency, achieving up to + 9 +9 points in average accuracy at aggressive sparsity levels while maintaining 1.54 × 1.54\times lower attention density. It also achieves up to 4.14 × 4.14\times attention speedup on RTX A6000 GPUs, demonstrating the effectiveness of the proposed method. Figure 1 : Illustration of the KV-union effect: in block diffusion, each query selects a small set of prefix KV positions, but the effective cost is determined by the union across the block, inflating KV access. Our method computes sparse attention only for selected (active) tokens during denoising and reuses cached results for the others (static tokens), substantially reducing the size of the KV union and the latency. 1 Introduction Timestep t-1 : \|q_{t-1}\|_{2} Timestep t : \|q_{t}\|_{2} Timestep t : MSE( q_{t-1},q_{t} ) Figure 2 : Visualizing representation change locality across denoising steps. Left and middle plots show the L2 norm of query vectors at timesteps t-1 and t respectively. The right plot shows the per-token MSE between query vectors across the two timesteps. Only a small fraction of tokens exhibit large changes, motivating the reuse of cached-prefix attention for stable tokens. Diffusion language models (DLMs) have emerged as a compelling alternative to autoregressive transformers for text generation ( 2 ; 26 ; 24 ; 25 ) . Unlike autoregressive models that generate tokens sequentially, DLMs generate tokens via iterative denoising and can update a block of tokens in any order, offering potential benefits for complex reasoning tasks. Recent block-wise DLMs ( 1 ; 6 ; 37 ) produce tokens in diffusion-based blocks, enabling any-order, non-autoregressive generation within a block while preserving autoregressive dependencies across blocks. These models rely on a KV cache to reuse prefix representations. Despite this flexibility, 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, the cost of repeatedly loading the KV cache dominates inference latency ( 10 ) . A natural approach to accelerate block-wise DLMs is to apply sparse attention methods developed for autoregressive LLMs ( 29 ; 45 ; 23 ; 35 ) . These methods select a subset of KV positions per query, reducing memory traffic. However, when naively adapting such methods to diffusion language models (DLMs), we encounter a KV Inflation problem (Figure 1 ), as different queries within the same block tend to select different KV positions. Since attention remains memory-bound, the overhead is determined by the size of the union of KV positions of all queries in the block. Let B be the block size, the size of this union can increase by at most B times compared with per-query budget, effectively negating the intended speedup from sparsity. To mitigate this problem, we observe that block-wise diffusion provides a unique structure absent in autoregressive decoding: Locality of Representation Changes across denoising steps. As shown in Figure 2 , between consecutive denoising iterations, only a small fraction of tokens undergo substantial updates to their hidden representations; we refer to these as Active tokens . The remaining Stable tokens have queries that change minimally, meaning their attention patterns, and therefore their attention outputs, remain approximately constant. Building on this observation, we introduce LoSA ( Lo cality-aware S parse A ttention), a method that exploits locality of representation changes to reduce KV cache memory operations. The key idea is to compute sparse prefix attention only for active tokens at each denoising step, since they are the only queries whose attention patterns change substantially. For the remaining stable tokens (i.e. tokens whose hidden representation has negligible change across denoising steps), we reuse cached prefix-attention outputs from the previous step. By reducing the number of queries that participate in sparse attention from the block size B to |\mathcal{A}| (where \mathcal{A} is the set of active tokens), we shrink the union of selected KV positions and directly lower memory traffic, leading to higher speedup. Beyond efficiency gains, LoSA also improves accuracy compared to naive sparse attention. The key advantage is that for stable tokens, our method preserves the full attention information from the cached prefix, whereas sparse attention can only access a subset of KV Cache. Therefore, for the majority of the tokens, LoSA attention computation is more accurate, making the performance degradation less severe. We summarize our contributions as follows: • We observe Locality of Representation Changes in block-wise diffusion: across denoising steps, only a small fraction of tokens ( Active tokens ) undergo substantial representation changes, while the majority ( Stable tokens ) maintain approximately constant. Details in § 3.2 . • We identify the KV Inflation problem in block-wise DLM inference: when applying sparse attention to a block of B queries, the attention kernel must load the union of selected prefix KV positions across the block, making the speedup less than expected. Details in § 3.1 . • We propose LoSA , a sparse attention method that reuses cached prefix attention outputs for stable tokens and computes sparse attention only for active tokens, reducing the union of selected KV indices by \sim 1.5\times in practice. Details in § 4 . • We evaluate LoSA on SDAR-8B ( 6 ) , Trado-8B, and Trado-4B ( 31 ) across LongBench and reasoning benchmarks. Compared to SparseD ( 32 ) , Sparse-dLLM ( 28 ) , and QUEST ( 29 ) , LoSA achieves up to +9 points accuracy improvement on LongBench at aggressive sparsity while maintaining 1.5\times lower attention density. On NVIDIA RTX A6000 GPUs, LoSA delivers up to 4.14\times attention speedup, with the trend transferring to newer hardware ( 3.67\times on RTX 5090). 2 Preliminaries 2.1 Block-Wise Diffusion Language Models Block-wise diffusion language models (DLMs) generate text in blocks of B tokens, where each block is treated as a single generation unit. Blocks are generated autoregressively, while attention within each block is bidirectional. At a denoising step, the queries, keys and values corresponding to the current block are denoted as {\bm{Q}}_{b},{\bm{K}}_{b},{\bm{V}}_{b}\in\mathbb{R}^{B\times d} , where d is the head dimension and the subscript b stands for block . Since the denoising process follows an autoregressive manner, we maintain

Read the complete text