How much accuracy can you keep while speeding up prefill?
The headline numbers are dramatic: Block-attention reports a 98.7% reduction in time-to-first-token and 99.8% fewer FLOPs on a 32K-token input, while keeping performance comparable to full attention after fine-tuning [1]. But that's a best-case scenario—the method requires fine-tuning the model to adapt to block-wise attention, and it works best when the context is naturally segmented into blocks (like retrieved documents).
Other methods aim for training-free or lightweight-training sparsity. VSPrefill, which uses a lightweight indexer to predict important columns and diagonals, preserves 98.35% of full-attention accuracy on LongBench and RULER while achieving a 4.95x average speedup at 128K context [2]. TokenSelect, a training-free method, reports up to 23.84x speedup in attention computation and 2.28x end-to-end latency reduction, but its accuracy is not directly compared to full attention in the abstract [5].
The key tension: the more aggressive the sparsity, the more accuracy you risk. SparseServe, which offloads unselected KV caches to DRAM, shows that even with dynamic sparse attention, you can get up to 9.26x lower TTFT and 3.14x higher throughput, but it doesn't report accuracy numbers—implying that the accuracy-efficiency frontier is still being mapped [8].
What happens to the context you don't attend to?
A natural follow-up is whether discarding unselected blocks loses important information. SPLA directly addresses this by compressing unselected blocks into a compact recurrent state via a residual linear attention module, rather than throwing them away [3]. This approach not only closes the performance gap with dense attention but actually surpasses it on RULER, suggesting that the 'long tail' of context matters more than previously thought.
This contrasts with methods like TokenSelect that rely on top-k selection and discard the rest [5]. The question becomes: when is it safe to discard, and when do you need a fallback? SPLA's success hints that a hybrid—sparse for the most relevant blocks, linear for the rest—might be the most robust path forward.
Another angle is pattern sharing. Sparse Pattern Sharing [6] exploits the observation that attention patterns are similar across heads and inputs, so you only compute full attention for a small subset of heads and share those patterns. This reduces the cost of accurate selection, but it raises the question: how stable are these patterns across different tasks and domains? The paper shows consistency across diverse inputs, but that's on benchmarks—real-world deployment might be more varied.
How do these methods behave under real serving loads?
Most sparse attention papers focus on a single inference call, but serving systems handle many concurrent requests with varying prefill and decode phases. P-PAS shows that the optimal token scheduling budget changes with load: larger budgets help under low pressure, but smaller budgets reduce interference with decoding under high pressure [7]. This means a sparse prefill method that works well in isolation might not translate to a serving system without adaptive scheduling.
Memory is another bottleneck. SparseServe and LongSight both tackle the problem of KV cache size: SparseServe offloads unselected KV caches to DRAM to free HBM for larger batch sizes [8], while LongSight uses compute-enabled CXL memory to store KV caches, supporting up to 1M tokens on a single GPU [9]. These are system-level solutions that complement the algorithmic sparsity, but they introduce new questions about cache management, data transfer overhead, and hardware requirements.
The research question here is: how do you co-design the sparse attention algorithm with the serving system to maximize throughput and minimize latency under realistic workloads? The papers suggest that the answer is not just algorithmic—it's about scheduling, memory hierarchy, and hardware acceleration.
About These Sources
This answer is built on 9 studies (4 peer-reviewed, 5 preprints) — published from 2024 to 2026, 9 from 2024 or later — selected as the most relevant from 9 studies that passed quality screening, drawn from 24 papers retrieved from a database of over 500 million.
Sources used in this answer
Block-Attention for Efficient Prefilling
Block-attention, which divides context into blocks and reuses KV states, reduces TTFT by 98.7% and FLOPs by 99.8% on 32K-token inputs while maintaining comparable performance to full attention after fine-tuning, across 11 benchmarks.
VSPrefill: Vertical-Slash Sparse Attention with Lightweight Indexing for Long-Context Prefilling
VSPrefill, using a lightweight indexer to predict important vertical columns and slash diagonals, preserves 98.35% of full-attention accuracy on LongBench and RULER while achieving a 4.95x average speedup at 128K context, without modifying backbone parameters.
SPLA: Block Sparse Plus Linear Attention for Long Context Modeling
SPLA combines block-sparse attention with a residual linear attention module to compress unselected blocks, surpassing dense attention on RULER in continual pretraining while maintaining competitive general knowledge.
Exploiting Sparsity for Long Context Inference: Million Token Contexts on Commodity GPUs
A top-k selection mechanism that attends to less than 2% of input tokens achieves over 95% of model performance on RULER, AlpacaEval, and Open LLM Leaderboard, enabling 1M-token inference on commodity GPUs with ~16GB RAM.
TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection
TokenSelect, a training-free method using per-head soft voting to select critical KV cache tokens, achieves up to 23.84x speedup in attention computation and 2.28x end-to-end latency reduction, with superior performance compared to state-of-the-art long-context inference methods.
Accelerating Prefilling for Long-Context LLMs via Sparse Pattern Sharing
Sparse Pattern Sharing exploits inter-head similarity in attention patterns to compute full attention for only a small subset of heads, achieving superior or comparable speedup to state-of-the-art methods while delivering the best overall accuracy.
P-PAS: Prefill-Pressure Adaptive Scheduling for Long-Context LLM Serving
P-PAS shows that the optimal token scheduling budget in vLLM depends on load pressure; dynamic adaptation maintains low end-to-end latency across changing loads, while large prefill chunks improve efficiency only under low scheduling pressure.
SparseServe: Unlocking Parallelism for Dynamic Sparse Attention in Long-Context LLM Serving
SparseServe, a serving system for dynamic sparse attention, uses hierarchical HBM-DRAM management to achieve up to 9.26x lower mean TTFT and 3.14x higher token generation throughput compared to state-of-the-art systems.
LongSight: Compute-Enabled Memory to Accelerate Large-Context LLMs via Sparse Attention
LongSight, an algorithm-hardware co-design using compute-enabled CXL memory, supports up to 1M-token contexts for Llama models on a single GPU, effectively elevating LPDDR DRAM to HBM-like performance.