𝚫 \mathbf{\Delta} Attention: Fast and Accurate Sparse Attention Inference by Delta Correction
Jeffrey Willette, Heejun Lee, Sung Ju Hwang, KAIST, DeepAuto.ai · 2025
Read 𝚫 \mathbf{\Delta} Attention: Fast and Accurate Sparse Attention Inference by Delta Correction by Jeffrey Willette, Heejun Lee, Sung Ju Hwang, KAIST, DeepAuto.ai (2025) 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-2505-11254.txt.
Introduction
Jeffrey Willette, Heejun Lee, and Sung Ju Hwang fix the accuracy collapse of sparse attention by correcting the statistical drift the shortcuts introduce. Their paper appeared in two thousand twenty-five. Attention lets transformers weigh context, but its cost grows quadratically with length. Sparse methods skip most of that cost and quietly lose accuracy.
The team traced the loss to a shift in output distributions. Decoding queries then misalign with keys cached from the prompt stage. Their delta correction nudges sparse outputs back toward the full-attention distribution. It layers on top of any sparse method without retraining. On a long-context benchmark it recovered most of the lost accuracy. Sparsity stayed extremely high while speed multiplied many times over. Million-token prompts became practical in their tests. The fix is small, general, and cheap, a rare combination.
Catalog record
| CREATOR | Jeffrey Willette, Heejun Lee, Sung Ju Hwang, KAIST, DeepAuto.ai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11254
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
𝚫 \mathbf{\Delta} Attention: Fast and Accurate Sparse Attention Inference by Delta Correction Jeffrey Willette, Heejun Lee, Sung Ju Hwang, KAIST, DeepAuto.ai Abstract The attention mechanism of a transformer has a quadratic complexity, leading to high inference costs and latency for long sequences. However, attention matrices are mostly sparse, which implies that many entries may be omitted from computation for efficient inference. Sparse attention inference methods aim to reduce this computational burden; however, they also come with a troublesome performance degradation. We discover that one reason for this degradation is that the sparse calculation induces a distributional shift in the attention outputs. The distributional shift causes decoding-time queries to fail to align well with the appropriate keys from the prefill stage, leading to a drop in performance. We propose a simple, novel, and effective procedure for correcting this distributional shift, bringing the distribution of sparse attention outputs closer to that of quadratic attention. Our method can be applied on top of any sparse attention method, and results in an average 36%pt performance increase, recovering 88% of quadratic attention accuracy on the 131K RULER benchmark when applied on top of sliding window attention with sink tokens while only adding a small overhead. Our method can maintain approximately 98.5% sparsity over full quadratic attention, making our model 32 times faster than Flash Attention 2 when processing 1M token prefills. 1 Introduction The main operation that powers modern transformers, self-attention ( Vaswani et al., 2017 ) , creates causal pairwise comparisons for every item in a sequence. While powerful and expressive, this operation comes with a quadratic complexity, leading to the need for large amounts of computation during inference on long sequences. This increases direct costs for hardware and electricity as well as negative externalities such as CO 2 emissions. Training-free sparse attention modifications aim to lower the quadratic complexity at inference time, but come with unwanted side effects such as accuracy degradation due to the sparsification of the attention matrix. Figure 1 : RULER 131K Subsets. At long context lengths, sparse attention can degrade performance by a large margin. Our simple \mathbf{\Delta} correction improves performance and only requires an additional 1.5% of the full quadratic attention computation. Recent works on sparse attention have found that a sparse sliding window can be added at inference time without a total loss of model stability. This is accomplished by saving a small number of initial tokens, and applying a sliding window on all subsequent tokens (Streaming LLM ( Xiao et al., 2023 ) ). Subsequent works such as Star Attention ( Acharya et al., 2024 ) have proposed a similar sparse prefill strategy with a fully dense decoding procedure to generate new tokens. This strategy has the positive attribute of a sparse prefill while still performing attention with all tokens during generation. This should allow the model to accurately recall context buried deep within the prompt. However, we find that this is not the case in practice. For example, there is a challenging subset of the RULER ( Hsieh et al., 2024 ) benchmark titled MultiKey-3, which consists entirely of unique UUID keys and values, and the large language model (LLM) must be able to recall the proper value for a particular key in order to get a correct answer. In this setting, a sliding window of 2048 tokens provides more than adequate room for encoding individual key and value pairs together within the window. One would then expect that a dense decode procedure would be able to retrieve the proper UUID given a user query. However, we find that this is not the case and the dense decode achieves a surprisingly low accuracy of 0% as opposed to 62% when using quadratic attention. Figure 2 : Comparing RULER 131K prefill attention latency and accuracy for sparse attention methods. We find this drop in accuracy arises from a distributional shift in the output tokens of each layer due to the sparse prefill. This distributional shift causes problems with the query-key dot products in long contexts and therefore results in an extreme drop in performance as the queries no longer align with the expected keys. We study this problem and found a surprisingly simple fix which we dub \mathbf{\Delta} Attention that improves the accuracy of sliding window attention from 0% to 44% ( Figure 1 , NIAH MK3) on this challenging subset while maintaining more than 11-fold speedup over plain Flash Attention 2 ( Dao, 2023 ) for processing 131K context lengths ( Figure 2 ). Through evaluations on perplexity, natural language understanding, and synthetic tasks, we demonstrate that our method consistently results in better performance while maintaining the low latency of the sparse prefill. Our contributions are as follows: • We identify a distributional shift in tokens when applying an inference-time sparse attention method to pretrained transformers, which interferes with query-key alignment on long contexts and leads to a drop in performance. • We introduce Delta ( \mathbf{\Delta} ) Attention, a sparse post-processing correction that realigns sparse outputs with full quadratic attention. • Our method adds negligible latency overhead compared to plain sparse attention, while drastically increasing performance over purely sparse methods. • Our method is designed to work in the attention output space, so it can be seamlessly integrated with existing sparse attention kernels and inference pipelines without major modification. 2 Background & Related Work The self attention mechanism of a transformer takes an input sequence \mathbf{X}\in\mathbb{R}^{N\times d} of individual tokens \mathbf{x}_{i}\in\mathbb{R}^{d} for i\in\{1..N\} . After applying linear projections \mathbf{W_{Q}},\mathbf{W_{K}},\mathbf{W_{V}}\in\mathbb{R}^{d\times d} to the input \mathbf{X} to achieve the respective \mathbf{Q},\mathbf{K},\mathbf{V} matrices, positional encodings such as ( Su et al., 2024 ) are applied to \mathbf{Q} and \mathbf{K} . With \sigma representing the softmax operation over the last dimension, the self-attention operation for an arbitrary layer in a transformer is the following, \mathbf{AV}=\sigma\left(\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d}}\right)\mathbf{V}=\sigma\left(\frac{\mathbf{XW_{Q}}(\mathbf{XW_{K}})^{\top}}{\sqrt{d}}\right)\mathbf{XW_{V}} (1) We omit the output projections, attention heads, and post-attention multilayer perceptrons (MLPs). For a deeper discussion of these topics in transformers, please see ( Vaswani et al., 2017 ) . The most expensive operation in Equation 1 that arises from the multiplication inside \sigma() which results in the implicit construction of an attention matrix \mathbf{A}\in\mathbb{R}^{N\times N} which is computationally expensive for large N . Due to the causality condition of language, a token \mathbf{x}_{i} may only influence another token \mathbf{x}_{j} where the index i\leq j . In practice, this means that only the lower triangle of \mathbf{A} is computed. After traversing through the layers of the network, the next token in the sequence \mathbf{x}_{N+1} is generated (predicted) and added to the input sequence to generate the next token and so on until the sequence terminates. In this generation phase, each iteration may use the previously computed tokens, which are stored within a cache at each layer, so that we may avoid re-calculating the entire attention matrix in Equation 1 . With a union operator \cup which concatenates matrices by adding new rows, and considering that \mathbf{K,V} contain tokens with indices \{1..N\} , and the newly generated token has index i=N+1 , the generative process for the next token proceeds through the attention layers as, (\mathbf{a}^{\top}\mathbf{v})_{i}=\sigma\left(\frac{\mathbf{q}_{i}^{\top}\left[\mathbf{K}\cup\mathbf{k}_{i}^{\top}\right]^{\top}}{\sqrt{d}}\right)\left(\mathbf{V}\cup\mathbf{v}_{i}^{\top}\right) (2) Sparse attention prefill methods aim to reduce the quadratic computation in Equation 1 by computing a