Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Serving
Zihan Zhao, Baotong Lu, Shengjie Lin, Yizou Chen, Jing Liu, Yanqi Zhang, Ziming Miao, Ming-Chang Yang, Haiying Shen, Qi Chen, Fan Yang · 2026
Read Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Serving by Zihan Zhao, Baotong Lu, Shengjie Lin, Yizou Chen, Jing Liu, Yanqi Zhang, Ziming Miao, Ming-Chang Yang, Haiying Shen, Qi Chen, Fan Yang (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-26837.txt.
Introduction
Zhao and ten colleagues present SPIN, a framework unifying sparse attention for long-context language-model serving. Sparse attention reads only a small query-dependent slice of stored key-value state, but varied granularities and GPU-CPU transfers usually erase the gains. SPIN maps varied patterns onto one page store, manages cache budgets by locality, and sizes metadata to the active set. Built on vLLM, it beats plain vLLM on throughput and first token time, cutting token time by up to 58 percent.
Catalog record
| CREATOR | Zihan Zhao, Baotong Lu, Shengjie Lin, Yizou Chen, Jing Liu, Yanqi Zhang, Ziming Miao, Ming-Chang Yang, Haiying Shen, Qi Chen, Fan Yang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58116 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26837
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Serving Zihan Zhao, Baotong Lu, Shengjie Lin, Yizou Chen, Jing Liu, Yanqi Zhang, Ziming Miao, Ming-Chang Yang, Haiying Shen, Qi Chen, Fan Yang Abstract . Long-context LLM serving is bottlenecked by the cost of attending over ever-growing KV caches. Dynamic sparse attention promises relief by accessing only a small, query-dependent subset of the KV state per decoding step and extending the KV storage to CPU memory. In practice, however, these algorithmic savings rarely translate into end-to-end system-level gains because sparse methods typically operate at different granularities and thus rely on ad hoc, per-algorithm implementations. At the same time, hierarchical KV storage introduces a new systems bottleneck: retrieving fine-grained, irregular KV subsets across the GPU–CPU boundary can easily erase the benefits of sparsity. We present Spin , a sparse-attention-aware inference framework that co-designs the execution pipeline with hierarchical KV storage through three techniques: (1) a unified partition abstraction that maps different sparsity granularities onto a shared page-based KV substrate; (2) a locality-aware KV cache manager that dynamically sizes per-request HBM budgets and uses a GPU-friendly bucketed LRU policy to cut PCIe round-trips; and (3) a two-level hierarchical metadata layout sized to the active working set rather than the worst-case address space. Built on vLLM with three representative sparse attention algorithms, Spin delivers 1.66 1.66 – 5.66 × 5.66\times higher end-to-end throughput and 7 7 – 9 × 9\times lower TTFT than vLLM, and reduces TPOT by up to 58 % 58\% over the original sparse-attention implementations. 1. Introduction To support increasingly sophisticated workloads such as long-context reasoning ( 61 ; 6 ; 57 ) , document understanding ( 24 ; 60 ; 39 ) , and code generation ( 8 ; 51 ; 73 ) , modern LLMs have expanded their context windows to hundreds of thousands or even millions of tokens ( 43 ; 5 ; 20 ; 42 ) . This trend makes long-context serving fundamentally costly because the key-value (KV) cache ( 45 ) , intermediate states in attention , grows linearly with the sequence length, and decoding repeatedly reads all historical KV states for every generated token. Consequently, serving is jointly constrained by the memory bandwidth to sustain linear KV accesses and GPU memory capacity to hold expanding KV caches. Dynamic sparse attention offers a promising algorithmic response. Prior work shows that, for a given query, only a small subset of historical tokens typically dominates the next-token prediction ( 15 ; 16 ; 18 ) . Recent sparse methods therefore preserve the full KV cache but select only the critical subset at each decoding step ( 56 ; 34 ; 14 ; 71 ) , reducing the amount of KV data that attention must process per step. The selective access pattern of sparse attention breaks the full-KV dependency assumed by prior dense-serving systems ( 26 ; 77 ) and makes hierarchical KV storage attractive. The system can keep the full KV cache in high-capacity CPU memory and fetch only critical KV states to the GPU on demand at fine granularity ( 13 ; 55 ) , thereby alleviating GPU memory pressure. For example, a single 128K-token request for Qwen3-8B requires roughly 19GB of KV cache, whereas a sparse method with 95% sparsity needs to process less than 1GB of KV data per decoding step, enabling higher concurrency and better hardware utilization. Yet, these algorithmic gains do not automatically translate into system-level efficiency, for two major challenges. Figure 1 . Gap Between Theoretical and Realized Performance. The ideal envelope represents an oracle system with optimal GPU–CPU KV caching and retrieval. On 32K-context workloads on an A100 GPU (80GB), existing sparse attention implementations ( 55 ) remain far below this bound and also fail to scale to large batch sizes due to inefficient memory management, whereas the Spin -powered system approaches the envelope. Lack of Unified Abstractions for Sparsity. Sparse algorithms are diverse, rapidly evolving, and operate at different granularities (e.g., blocks ( 55 ) and clusters ( 13 ) ). Existing inference frameworks ( 25 ; 77 ) do not provide a common interface that accommodates these variants, so existing sparse-attention support has evolved into algorithm-specific prototypes that cannot readily share optimized kernels, memory management, or online scheduling support. Realizing the system-level benefits of sparsity therefore requires a unified abstraction that preserves algorithm-specific flexibility while enabling the system to optimize the common substrate. Irregular KV Retrieval Erodes Sparsity Benefits. Once the full KV cache is placed in CPU memory, sparse serving becomes constrained by GPU–CPU data movement. Unlike dense attention, whose KV accesses are largely contiguous and predictable ( 47 ) , sparse attention retrieves small, scattered KV subsets that vary across decoding steps, layers, and heads. These irregular transfers underutilize PCIe bandwidth and add latency to the critical path. Prior work ( 63 ; 66 ) shows that autoregressive decoding also exhibits temporal locality: critical tokens often overlap across consecutive steps. Realizing the benefits of sparsity therefore fundamentally requires a locality-aware memory manager that both caches useful KV states and retrieves misses efficiently. To better quantify the gap between the theoretical and realized performance of sparse attention algorithms, we define an ideal sparse-serving envelope : an oracle system that serves most selected KV tokens from GPU memory while incurring the theoretically minimum retrieval overhead under an optimal caching policy ( 9 ) . As shown in Figure 1 , existing sparse attention implementations remain far below this bound due to the aforementioned reasons. To narrow the gap between sparse attention’s theoretical promise and practical system efficiency, we present Spin , a sp arse-attention-aware in ference framework. Spin abstracts diverse sparse attention algorithms into a common five-operation pipeline with three algorithm-specific compute operations ( Index , Select , and Attention ) and two shared data-management operations ( Offload and Retrieve ). The key observation is that these algorithms share a common execution pattern and differ mainly in sparsity granularity. Spin therefore introduces partition as a common logical unit that maps different granularities onto the same pipeline. This design exposes clean interfaces for algorithm-specific customization while reusing optimized implementations of Offload and Retrieve , allowing diverse sparse methods to share efficient KV management. Based on this pipeline, Spin builds a KV-cache management system for sparse serving across the GPU–CPU hierarchy with three design decisions: 1. Partition Abstraction. Spin treats partition as the key abstraction connecting sparse algorithms with page-based KV cache management. This separates algorithm-defined sparsity units from hardware-efficient units, allowing the runtime to preserve algorithmic flexibility while allocating and transferring KV data at page granularity. 2. Dynamic, Locality-aware KV Management. To maximize GPU residency under dynamic serving workloads, Spin extends beyond conventional append-only paged KV caches with a lightweight, locality-aware KV manager. Its dynamic KV buffer supports per-request resizing and in-place updates as requests arrive, advance, and complete, while maintaining GPU-friendly metadata that enables efficient locality-aware replacement policies. 3. Hierarchical Metadata. Metadata overhead such as page tables increases with context length: even dense attention incurs nontrivial bookkeeping, and attention head-wise sparsity pattern introduces additional indexing metadata. Spin therefore adopts OS-style multi-level indexing so that metadata scales with the physical working set rather than the worst-case logical space, while