Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Serving

1. Problem Statement

The paper addresses the critical bottleneck in serving Large Language Models (LLMs) with long contexts (hundreds of thousands to millions of tokens).

• Memory Capacity & Bandwidth: The Key-Value (KV) cache grows linearly with sequence length, quickly exhausting GPU High Bandwidth Memory (HBM). While offloading to CPU memory helps capacity, it introduces PCIe latency.
• Inefficiency of Sparse Attention: Dynamic sparse attention algorithms promise to reduce computation and memory access by selecting only a subset of critical tokens. However, existing implementations fail to translate these algorithmic savings into system-level gains due to two main issues:
  1. Lack of Unified Abstractions: Sparse algorithms operate at different granularities (e.g., blocks vs. clusters) and require ad-hoc, algorithm-specific implementations. This prevents sharing optimized kernels, memory management, and scheduling logic.
  2. Irregular Data Movement: Sparse access patterns are scattered and non-contiguous. Retrieving fine-grained KV subsets across the GPU-CPU boundary underutilizes PCIe bandwidth and adds significant latency, often erasing the benefits of sparsity.
• The Gap: There is a large discrepancy between the theoretical potential of sparse attention (an "ideal" system) and current real-world performance, primarily due to poor data management and metadata overhead.

2. Methodology: The Spin Framework

The authors propose Spin, a sparse-attention-aware inference framework that co-designs the execution pipeline with hierarchical KV storage. Spin is built on top of vLLM and integrates three core techniques:

A. Unified Partition Abstraction

Spin introduces a common logical unit called a Partition to unify diverse sparse algorithms.

• Pipeline Decoupling: The inference pipeline is abstracted into five operations:
  • Algorithm-specific: Index (organize tokens), Select (identify critical partitions), and Attention (compute output).
  • System-managed: Offload (place data in memory) and Retrieve (fetch data from CPU).
• Mapping: Different granularities (blocks, clusters, tokens) are mapped to a shared page-based KV substrate. This allows the system to optimize the common data movement layer (Offload/Retrieve) while allowing algorithm developers to customize only the selection logic.

B. Dynamic, Locality-Aware KV Management

To maximize GPU residency and minimize PCIe transfers, Spin implements a sophisticated memory manager:

• Buffer Elasticity: The system dynamically sizes the GPU buffer per request, splitting it into Mandatory Pages (critical for the current step) and Buffering Pages (retained for temporal locality). The scheduler balances per-request throughput against system-wide concurrency.
• Bucketed LRU Policy: Instead of a global LRU (which is expensive), Spin uses a GPU-friendly Bucketed LRU. It groups pages into buckets based on recency timestamps (e.g., 64 buckets). This avoids global sorting, allowing parallel eviction decisions on the GPU that align with the bulk-access patterns of sparse attention.
• Head-wise Physical Pages: To avoid fetching unused data, KV pages are organized per attention head, ensuring only relevant data is transferred over PCIe.

C. Hierarchical Metadata Management

Metadata overhead (page tables) can consume massive GPU memory in long-context scenarios.

• Two-Level Indexing: Inspired by OS paging, Spin uses a two-level index structure. A small top-level directory resides on the GPU, pointing to second-level segments allocated on-demand in CPU memory.
• Scalability: This ensures metadata scales with the active physical working set rather than the worst-case logical address space, reducing metadata HBM consumption by orders of magnitude.
• Tier-Split: Latency-critical metadata stays on the GPU, while capacity-heavy metadata is offloaded to CPU memory.

3. Key Contributions

1. Unified Abstraction: A common five-operation pipeline that decouples algorithmic logic from system-level data management, enabling diverse sparse algorithms to share optimized runtime support.
2. Locality-Aware Memory Manager: A novel buffer management system featuring dynamic per-request sizing and a GPU-optimized Bucketed LRU policy that exploits temporal locality in sparse access patterns.
3. Scalable Metadata: A hierarchical, two-level metadata layout that drastically reduces GPU memory overhead, enabling larger batch sizes and longer contexts.
4. System Integration: A full implementation integrated into vLLM, supporting multiple sparse algorithms (ShadowKV, RetroInfer, SeerAttention-R) and hardware platforms (A100, B200).

4. Experimental Results

The authors evaluated Spin against vLLM (dense), vLLM-Offload, and original sparse implementations across various models (Qwen3-14B/32B, Llama-3.1-70B) and benchmarks (LongBench-v2, LongGenBench).

• Throughput: Spin achieves 1.66× to 5.66× higher end-to-end throughput compared to vLLM. The gains are most significant at high request rates where vLLM suffers from memory thrashing.
• Latency (TTFT): Spin reduces Time-To-First-Token (TTFT) by 7–9× compared to vLLM, primarily by sustaining larger batch sizes and reducing queueing delays.
• Decode Latency (TPOT): Compared to original sparse implementations, Spin reduces per-token decode latency by 8.4% to 58%, translating to up to 2.39× throughput improvement.
• Efficiency Drivers:
  • The locality-aware buffer management improves decode throughput by 2.18×.
  • Hierarchical metadata reduces metadata HBM consumption by 49–78×, freeing up space for KV caches.
• Scalability: Spin supports 2.5–3.3× larger average batch sizes than baselines during online serving.

5. Significance

• Bridging the Gap: Spin successfully bridges the gap between the theoretical promise of sparse attention and practical system efficiency, demonstrating that algorithmic sparsity can be effectively leveraged in production systems.
• Generalizability: By abstracting the common execution pattern, Spin provides a reusable framework for future sparse attention algorithms, eliminating the need for ad-hoc system re-implementations.
• System-Level Optimization: The paper highlights that for long-context LLMs, the primary bottleneck is shifting from pure computation to data movement and memory management. Optimizing the GPU-CPU hierarchy and metadata structures is as critical as the attention algorithm itself.
• Production Readiness: Built on vLLM and tested on state-of-the-art hardware (A100, B200), Spin offers a practical path for deploying long-context LLMs with high concurrency and low latency.