SPLA : Block Sparse Plus Linear Attention for Long Context Modeling

Bailin Wang, Dan Friedman, Tao Lei, Chong Wang · 2026

Read SPLA : Block Sparse Plus Linear Attention for Long Context Modeling by Bailin Wang, Dan Friedman, Tao Lei, Chong Wang (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-2601-22379.txt.

Introduction

Bailin Wang, Dan Friedman, Tao Lei, and Chong Wang fix a flaw in fast attention for long texts. Block-sparse attention reads only picked chunks, which saves huge cost. Their 2026 preprint notes that dropped chunks take their context with them, and picks can miss the mark.

Their method, SPLA, picks chunks with a sharper score, drawn from second-order cues. It then keeps a light linear path so dropped chunks still leave a trace. The goal is long memory at low cost. That goal matters for book-length and code-length tasks. The work refines a key speed trick.

Catalog record

CREATORBailin Wang, Dan Friedman, Tao Lei, Chong Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22379

Browse the full library · About the Tower of Babel

Full text

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

SPLA : Block Sparse Plus Linear Attention for Long Context Modeling Bailin Wang, Dan Friedman, Tao Lei, Chong Wang Abstract Block-wise sparse attention offers significant efficiency gains for long-context modeling, yet existing methods often suffer from low selection fidelity and cumulative contextual loss by completely discarding unselected blocks. To address these limitations, we introduce Sparse Plus Linear Attention (SPLA), a framework that utilizes a selection metric derived from second-order Taylor expansions to accurately identify relevant blocks for exact attention. Instead of discarding the remaining “long tail,” SPLA compresses unselected blocks into a compact recurrent state via a residual linear attention (RLA) module. Crucially, to avoid IO overhead, we derive an optimized subtraction-based formulation for RLA—calculating the residual as the difference between global and selected linear attention—ensuring that unselected blocks are never explicitly accessed during inference. Our experiments demonstrate that SPLA closes the performance gap in continual pretraining, surpassing dense attention models on long-context benchmarks like RULER while maintaining competitive general knowledge and reasoning capabilities. † † affiliationnotice: Work done while the first and last authors were at Apple. 1 Introduction The capabilities of Large Language Models (LLMs) have scaled rapidly, with a particular emphasis on extending context windows to millions of tokens. As sequence lengths increase, however, the decoding phase becomes a critical bottleneck. Because decoding is memory-bound, serving long-context models with full attention requires loading increasingly large Key-Value (KV) caches, often necessitating the usage of more GPUs/TPUs to accommodate the memory footprint. To alleviate this, blockwise sparse attention mechanisms (e.g., NSA ( Yuan et al. 2025 ) , InfLLM ( Zhao et al. 2025 ) ) have emerged as a promising optimization. By selectively loading only the most relevant blocks of the cache, these methods significantly increase inference throughput and reduce latency. However, current sparse approaches face two fundamental limitations. First, their block selection methods—which are based on highly compressed block representations—suffer from low selection fidelity , often failing to accurately identify the most relevant blocks. Second, by strictly truncating unselected blocks, existing methods suffer from cumulative contextual loss . As context grows, the probability mass in the “long tail” becomes non-negligible, introducing a divergence between sparse and dense attention that severely degrades generation quality. In this paper, we introduce SPLA , a principled framework designed to close the performance gap between sparse and dense attention. First, SPLA leverages second-order Taylor expansions to derive a selection metric directly from a principled approximation of the original attention objective. Furthermore, instead of simply truncating the context, we introduce a Sparse Plus Linear Attention paradigm. We partition the context into "exact" and "approximate" sets: relevant blocks are retrieved for exact attention, while the “long tail" is compressed into a recurrent state via residual linear attention (RLA). Crucially, we implement RLA via a subtraction-based formulation that requires no explicit memory access for unselected blocks, maintaining the IO profile of sparse decoding. In summary, the contributions of this work are as follows: 1. We derive a principled block selection strategy based on second-order Taylor expansions. By utilizing block-level mean and covariance statistics, we bridge the mathematical gap between token-level attention and block-level retrieval, enabling more accurate selection. 2. We propose SPLA , a novel framework that strictly partitions the context into exact and approximate components. By processing unselected blocks via residual linear attention, SPLA preserves the full global context—closing the performance gap with dense attention on sequence lengths up to 256k while retaining the efficiency of sparse decoding. SPLA is particularly well-suited for adapting pretrained dense attention models. Empirically, we demonstrate that dense models can be converted to SPLA architectures with a negligible number of additional parameters. We believe this represents a promising direction for efficient long-context modeling: standard attention architectures can be maintained during the expensive pretraining phase, and then seamlessly adapted into efficient sparse variants during the continual pretraining stage. 2 Background and Motivation We use the decoding workload to describe the framework and motivation of the sparse attention mechanism, though these concepts generalize to other primary workloads such as training and prefilling. In the decoding phase, the attention mechanism computes the output {\bm{o}} as: {\bm{o}}=\sum_{i=1}^{N}\frac{\exp{({\bm{q}}{\bm{k}}_{i}^{\intercal})}}{{\mathcal{Z}}({\bm{q}},{\bm{k}}_{1:N})}{\bm{v}}_{i} (1) where {\bm{q}},{\bm{k}}_{i},{\bm{v}}_{i}\in\mathbb{R}^{d} denote the query, key, and value vectors, respectively, and {\mathcal{Z}} denotes the normalization term. Conventionally, {\bm{k}}_{1:N} and {\bm{v}}_{1:N} are referred to as the KV cache, which must be retained in memory to be attended to by all future query vectors. For simplicity, we assume the current query token is at position N , requiring consideration of all preceding tokens in the cache. The decoding workload is intrinsically memory-bound. The majority of runtime is dominated by loading the KV cache from memory, while the actual computation (vector dot-products) is relatively cheap, resulting in low arithmetic intensity. Consequently, when the sequence length N becomes large (e.g., 1 million tokens), decoding efficiency degrades significantly, particularly in terms of latency. The central idea of sparse attention is to alleviate this memory bottleneck by selectively loading only a subset of the KV cache for computation. In this section, we describe the selection mechanism and the subsequent sparse attention procedure. Notation. We denote the page (or block) size as B , the group size for Grouped Query Attention (GQA) as G , the number of selected pages as k , the head dimension as d , and the sequence length as N . {\mathcal{Z}} denotes the normalization function. 2.1 Page Attention and Selection In practice, attention modules are typically served using logical pages (i.e., PagedAttention ( Kwon et al. 2023 ) ) to maximize memory utilization and continuity. Given this memory layout, it is natural to select KV caches at the granularity of the page size B . Specifically, the most relevant pages are identified to perform attention: {\bm{o}}=\sum_{i\in{\mathcal{I}}}\frac{\exp{({\bm{q}}{\bm{k}}_{[i]}^{\intercal})}}{{\mathcal{Z}}({\bm{q}},{\bm{k}}_{{\mathcal{I}}})}{\bm{v}}_{[i]}\in\mathbb{R}^{d}, (2) where {\bm{k}}_{[i]}:={\bm{k}}_{(i-1)B+1:iB} and {\bm{v}}_{[i]}:={\bm{v}}_{(i-1)B+1:iB}\in\mathbb{R}^{B\times d} represent the key and value blocks, and {\mathcal{I}}\subset[N/B] denotes the set of indices of the relevant blocks. The index set {\mathcal{I}} is computed via a selection operator applied to block summaries: {\mathcal{I}}=\text{Select}\big(\{\text{BlockScore}({\bm{q}},{\bm{k}}_{[i]})\}_{i=1}^{N/B}\big) (3) where \text{BlockScore}({\bm{q}},{\bm{k}}_{[i]}):=\frac{\exp{({\bm{q}}\tilde{\bm{k}}_{[i]}^{\intercal})}}{{\mathcal{Z}}({\bm{q}},\tilde{\bm{k}})}\quad\in\mathbb{R}\quad. Here, \tilde{\bm{k}}_{[i]} is a mapping that obtains a compact, block-level representation from the full block {\bm{k}}_{[i]} . The selector is designed to be input-dependent, meaning {\mathcal{I}} is a function of {\bm{q}} , unlike input-agnostic patterns such as sliding windows ( Xiao et al. 2024b ) . Existing works explore various designs for these mappings and selection functions. Regarding the mapping, Quest ( Tang et al. 2024 ) utilizes non-parametric pooling operations (specifically min and max values), while Inf-LLM v2 ( Zhao et al. 2025 ) employs mean pooling. In contrast, NSA ( Yuan et al. 2025 ) utilizes a parametric MLP layer to learn block representations. Regarding the selection function, TopK ( Yuan et al. 2025 ; Zhao et al. 2025 ) is the most common choice due to its hardware efficiency. Alternatively, TopP ( Lin et al. 2025 ) employs nucleus sampling to offer flexibility when the attention distribution is long-tailed, while other approaches ( Desai et al. 2025 ) propose hybrids of top- k and random sampling. Some methods, such as ( Chen et al. 2024 ) , utilize Locality Sensitive Hashing (LSH), though this is often suboptimal as it is data-agnostic. 2.2 Grouped Sparsity To generalize from single-head to multi-head settings, it is efficient to enforce

Read the complete text