# Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving

arXiv: https://arxiv.org/abs/2503.00392 · HTML: https://mlsanity.com/paper/2503.00392/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 40 of its 45 references that are in the map.
- First posted on arXiv 1 Mar 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 30 of 40)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [SAMSum Corpus: A Human-annotated Dialogue Dataset for Abstractive Summarization](https://mlsanity.com/paper/1911.12237/) (2019)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers](https://mlsanity.com/paper/2105.03011/) (2021)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [Multi-News: a Large-Scale Multi-Document Summarization Dataset and Abstractive Hierarchical Model](https://mlsanity.com/paper/1906.01749/) (2019)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [QMSum: A New Benchmark for Query-based Multi-domain Meeting Summarization](https://mlsanity.com/paper/2104.05938/) (2021)
- [Efficient Attentions for Long Document Summarization](https://mlsanity.com/paper/2104.02112/) (2021)
- [ZeRO-Infinity: Breaking the GPU Memory Wall for Extreme Scale Deep Learning](https://mlsanity.com/paper/2104.07857/) (2021)
- [InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Management](https://mlsanity.com/paper/2406.19707/) (2024)
- [PowerInfer: Fast Large Language Model Serving with a Consumer-grade GPU](https://mlsanity.com/paper/2312.12456/) (2023)

## Built on by (most cited first, 7 of 7)

- [FreeKV: Boosting KV Cache Retrieval for Efficient LLM Inference](https://mlsanity.com/paper/2505.13109/) (2025)
- [Long Context Scaling: Divide and Conquer via Multi-Agent Question-driven Collaboration](https://mlsanity.com/paper/2505.20625/) (2025)
- [PLM: Efficient Peripheral Language Models Hardware-Co-Designed for Ubiquitous Computing](https://mlsanity.com/paper/2503.12167/) (2025)
- [An Efficient Hybrid Sparse Attention with CPU-GPU Parallelism for Long-Context Inference](https://mlsanity.com/paper/2605.07719/) (2026)
- [KV Cache Offloading for Context-Intensive Tasks](https://mlsanity.com/paper/2604.08426/) (2026)
- [TempoNet: Slack-Quantized Transformer-Guided Reinforcement Scheduler for Adaptive Deadline-Centric Real-Time Dispatchs](https://mlsanity.com/paper/2602.18109/) (2026)
- [MOIRA: Mass-Oriented Indexing with Ragged Attention for Long-Context Decoding](https://mlsanity.com/paper/2610.04313/) (2026)

## Abstract (arXiv)

Processing long contexts has become a critical capability for modern large language models (LLMs). However, serving long-context LLMs comes with significant inference costs due to the high memory overhead of the key-value (KV) cache. Existing work leverages dynamic sparse attention algorithms (DSAes) to mitigate the KV cache overhead, but these algorithms rely on top-k KV cache selection, which results in a trade-off between accuracy and efficiency. A larger k improves accuracy but decreases efficiency, while a smaller k boosts efficiency but compromises accuracy. To overcome this trade-off, this paper presents PSA, a underlineProgressive underlineSparse underlineAttention mechanism that integrates algorithmic innovations with system co-design to achieve both high inference accuracy and improved efficiency in LLM serving. The PSA algorithm adaptively adjusts the KV cache budget of different tokens and layers according to their real attention weight distributions, rather than relying on a fixed budget k. This enables high accuracy while minimizing KV cache usage. To further enhance execution efficiency, we introduce a pipelined iteration scheme that reduces CPU-GPU interleaving and synchronization overhead during PSA computation. Additionally, we implement unified GPU memory management that optimizes PSA's memory utilization by accounting for uneven memory requirements across different model layers. Extensive experimental results demonstrate that PSA reduces KV cache usage for attention computation by up to 2.4× and 8.8×, and increases end-to-end serving throughput by up to 1.4× and 2.0×, compared to state-of-the-art DSAes and systems without sparse attention, respectively.