AB-Sparse : Sparse Attention with Adaptive Block Size for Accurate and Efficient Long-Context Inference
Di Liu, Ruitian Wang, Chen Chen, Mingliang Gong, Yongjie Yuan, Han Zhao, Yu Feng, Quan Chen, Minyi Guo · 2026
Read AB-Sparse : Sparse Attention with Adaptive Block Size for Accurate and Efficient Long-Context Inference by Di Liu, Ruitian Wang, Chen Chen, Mingliang Gong, Yongjie Yuan, Han Zhao, Yu Feng, Quan Chen, Minyi Guo (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-2605-12110.txt.
Introduction
Di Liu and eight colleagues present AB-Sparse, a training-free system for fast long-context inference. As context grows, KV cache loading drags speed down, and fixed block sizes assume all heads behave alike. Heads differ widely in how block size affects them, so AB-Sparse gives each head its own block size. It offsets the extra memory with lossless centroid coding of blocks, plus custom GPU code for mixed block sizes. Tests show accuracy gains up to 5.43 percent over block sparse baselines, with no speed loss.
Catalog record
| CREATOR | Di Liu, Ruitian Wang, Chen Chen, Mingliang Gong, Yongjie Yuan, Han Zhao, Yu Feng, Quan Chen, Minyi Guo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32654 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.12110
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
AB-Sparse : Sparse Attention with Adaptive Block Size for Accurate and Efficient Long-Context Inference Di Liu, Ruitian Wang, Chen Chen, Mingliang Gong, Yongjie Yuan, Han Zhao, Yu Feng, Quan Chen, Minyi Guo Abstract As large language models scale to longer contexts, loading the growing KV cache during attention computation becomes a critical bottleneck. Previous work has shown that attention computation is dominated by a small subset of tokens. This motivates block sparse attention methods that partition the KV cache into fixed-size blocks and selectively compute attention over those blocks exhibiting high importance. However, these methods assign a uniform block size across all attention heads, implicitly assuming homogeneous behavior throughout the model. Our analysis reveals that this assumption is flawed: attention heads exhibit widely varying sensitivity to block granularity, and uniformity leads to suboptimal accuracy. We present AB-Sparse , a training-free algorithm-system co-designed framework that improves accuracy while preserving throughput. AB-Sparse introduces lightweight adaptive block size allocation across attention heads to improve accuracy. To compensate for the additional memory overhead, it further employs lossless block centroid quantization. In addition, custom GPU kernels are developed to support efficient execution with variable block sizes. Evaluation results demonstrate that AB-Sparse achieves an accuracy improvement of up to 5.43 % over existing block sparse attention baselines without throughput overhead. 1 Introduction Large language models (LLMs) 3 ; 14 ; 33 are increasingly deployed in applications that demand long-context understanding, ranging from multi-document summarization 34 to repository-level code analysis 19 and long-form reasoning 27 . While larger context windows enable these capabilities, they introduce significant challenges for efficient model serving. At every decoding step, loading the entire KV cache from memory becomes a bottleneck that scales linearly with context length. For instance, the KV cache for a single request of 128K context length on Llama-3.1-8B 20 reaches 16GB, comparable to the model weights in size. The key to addressing this bottleneck lies in the inherent sparsity of attention: only a small subset of tokens dominates the attention output 32 . This property has inspired a growing body of sparse attention methods that can be categorized into three paradigms, as illustrated in Figure 2 . While all three paradigms reduce KV cache loading to lower inference latency, they each face different trade-offs among efficiency, practicality, and accuracy. Token-based methods such as H 2 O 36 and InfiniGen 12 estimate per-token importance at every decoding step and select the most relevant tokens, but incur high per-step selection overhead, compromising efficiency. Semantic-based methods such as Clusterkv 17 and RetroInfer 5 cluster tokens by key similarity and retrieve only the relevant clusters, but restructure the KV cache layout, compromising practicality with standard paged KV cache management 11 ; 37 ; 35 . Block-based methods such as Quest 25 and ArkVale 4 partition the KV cache into fixed-size blocks and load only the Top- K for attention computation, preserving both efficiency and practicality. This makes block-based methods a promising foundation, and the key to fully unlocking their potential lies in improving accuracy without sacrificing throughput. Figure 1 : Qualitative comparison of various sparse attention paradigms. Figure 2 : Illustration of block sparse attention workflow. Our analysis reveals that the accuracy limitation of block-based methods stems from a fundamental yet overlooked assumption: a uniform block size is applied across all attention heads 25 ; 4 . However, attention heads are known to exhibit highly heterogeneous behaviors 31 ; 30 . As shown in Figure 4 , our measurement study further reveals that this heterogeneity extends to their sensitivity to block granularity, with heads varying significantly in their block size preference. Forcing a uniform block size across all heads thus creates an inherent tension: for heads that require fine-grained resolution, an overly large block size coarsens selection granularity, causing critical tokens to be missed; for heads that are insensitive to granularity, an overly small block size unnecessarily increases the number of blocks, amplifying computation and memory cost. The attention head heterogeneity necessitates adaptive block size allocation: assigning finer granularity to sensitive heads to preserve accuracy, while allowing coarser blocks for insensitive heads to reduce overhead. However, realizing this in practical inference systems is non-trivial, with challenges arising from three aspects. First, adjusting block sizes at runtime requires recomputing centroids for all blocks, which is prohibitively expensive; a lightweight mechanism is needed to determine per-head block size assignments prior to deployment. Second, assigning smaller blocks to sensitive heads multiplies their centroid count, introducing significant memory overhead that calls for a lossless compression scheme to reduce centroid footprint. Third, heterogeneous block sizes lead to non-uniform centroid counts across heads and conflict with the uniform page size assumption in existing paged KV cache systems, necessitating custom GPU kernels for efficient execution. We present AB-Sparse , a training-free algorithm-system co-designed framework that addresses these challenges through three tightly integrated components. First, AB-Sparse introduces a lightweight calibration-driven profiling strategy; it exploits the stability of per-head block size sensitivity across diverse inputs to derive reliable assignments prior to deployment. Second, observing that block centroids are precision-insensitive as they are used only for ranking rather than for attention computation, AB-Sparse proposes lossless centroid quantization to reduce memory footprint. Third, AB-Sparse implements custom GPU kernels to support efficient execution with adaptive block sizes. An indexing mechanism enables variable-length batched execution across heads, while a page mapping mechanism maintains compatibility with standard paged KV cache management. We evaluate AB-Sparse on three widely used open source models across two long-context benchmarks. AB-Sparse consistently outperforms existing block sparse attention baselines, achieving up to 5.43% accuracy improvement without sacrificing throughput. Our contributions are summarized as follows: • We conduct a systematic measurement study on block size sensitivity, revealing that attention heads exhibit substantial heterogeneity in block granularity preference (§ 2.3 ). • We propose an adaptive block size allocation strategy based on lightweight calibration-driven profiling. We introduce lossless centroid quantization to reduce memory footprint. We design custom GPU kernels with two key mechanisms: indexing for variable-length batched execution, and page mapping for compatibility with standard paged KV cache management (§ 3 ). • We evaluate AB-Sparse on three LLMs across two long-context benchmarks, demonstrating consistent accuracy improvements of up to 5.43% over uniform-block-size baselines without throughput overhead (§ 4 ). 2 Background and Motivation 2.1 LLMs and Attention Operation The core component of LLMs is the attention operation 26 . At each decoding step t , the attention operation computes the dot product between the query vector \mathbf{q}_{t}\in\mathbb{R}^{1\times d} (where d is the hidden dimension) and the key vectors of all preceding tokens \mathbf{k}_{i}\in\mathbb{R}^{1\times d} (for i\leq t ). This product is scaled by d^{-\frac{1}{2}} and normalized through Softmax function to yield the attention score a_{t,i} . These scores then weight the value vectors \mathbf{v}_{i} , resulting in the final attention output \mathbf{o}_{t} . z_{t,i}=\frac{\mathbf{q}_{t}\cdot\mathbf{k}^{T}_{i}}{\sqrt{d}},\quad a_{t,i}=\dfrac{e^{z_{t,i}}}{\sum_{j=1..t}{e^{z_{t,j}}}},\quad\mathbf{o}_{t}=\sum_{i=1..t}a_{t,i}\cdot\mathbf{v}_{i} (1) The attention module is typically composed of multiple components, each referred to as an attention head 26 ; 1 . Each head independently performs computation as in Equation 1 and captures diverse features from different subspaces. The results from all heads are then aggregated to yield the output. LLM inference consists of two stages: the prefill phase and the decoding phase. The prefill phase processes all prompt tokens