# SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 59 of its 80 references that are in the map.
- First posted on arXiv 17 Jun 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [GLM: General Language Model Pretraining with Autoregressive Blank Infilling](https://mlsanity.com/paper/2103.10360/) (2021)
- [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)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)

## Built on by (most cited first, 30 of 39)

- [SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs](https://mlsanity.com/paper/2410.13276/) (2024)
- [SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference](https://mlsanity.com/paper/2502.18137/) (2025)
- [ReDeEP: Detecting Hallucination in Retrieval-Augmented Generation via Mechanistic Interpretability](https://mlsanity.com/paper/2410.11414/) (2024)
- [Why Does the Effective Context Length of LLMs Fall Short?](https://mlsanity.com/paper/2410.18745/) (2024)
- [KeyDiff: Key Similarity-Based KV Cache Eviction for Long-Context LLM Inference in Resource-Constrained Environments](https://mlsanity.com/paper/2504.15364/) (2025)
- [Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning](https://mlsanity.com/paper/2502.02770/) (2025)
- [ZipVL: Efficient Large Vision-Language Models with Dynamic Token Sparsification](https://mlsanity.com/paper/2410.08584/) (2024)
- [SepLLM: Accelerate Large Language Models by Compressing One Segment into One Separator](https://mlsanity.com/paper/2412.12094/) (2024)
- [IndexCache: Accelerating Sparse Attention via Cross-Layer Index Reuse](https://mlsanity.com/paper/2603.12201/) (2026)
- [The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs](https://mlsanity.com/paper/2504.17768/) (2025)
- [Lynx: Enabling Efficient MoE Inference through Dynamic Batch-Aware Expert Selection](https://mlsanity.com/paper/2411.08982/) (2024)
- [Speculative Prefill: Turbocharging TTFT with Lightweight and Training-Free Token Importance Estimation](https://mlsanity.com/paper/2502.02789/) (2025)
- [Geometry-Aware Rotary Position Embedding for Consistent Video World Model](https://mlsanity.com/paper/2602.07854/) (2026)
- [DAPE V2: Process Attention Score as Feature Map for Length Extrapolation](https://mlsanity.com/paper/2410.04798/) (2024)
- [Rethinking Key-Value Cache Compression Techniques for Large Language Model Serving](https://mlsanity.com/paper/2503.24000/) (2025)
- [FSA: An Alternative Efficient Implementation of Native Sparse Attention Kernel](https://mlsanity.com/paper/2508.18224/) (2025)
- [Vegas: Self-Speculative Decoding with Verification-Guided Sparse Attention](https://mlsanity.com/paper/2602.07223/) (2026)
- [SparK: Query-Aware Unstructured Sparsity with Recoverable KV Cache Channel Pruning](https://mlsanity.com/paper/2508.15212/) (2025)
- [vAttention: Verified Sparse Attention](https://mlsanity.com/paper/2510.05688/) (2025)
- [Compact Attention: Exploiting Structured Spatio-Temporal Sparsity for Fast Video Generation](https://mlsanity.com/paper/2508.12969/) (2025)
- [PSA: Pyramid Sparse Attention for Efficient Video Understanding and Generation](https://mlsanity.com/paper/2512.04025/) (2025)
- [SALE : Low-bit Estimation for Efficient Sparse Attention in Long-context LLM Prefilling](https://mlsanity.com/paper/2505.24179/) (2025)
- [AnTKV: Anchor Token-Aware Sub-Bit Vector Quantization for KV Cache in Large Language Models](https://mlsanity.com/paper/2506.19505/) (2025)
- [SPLA: Block Sparse Plus Linear Attention for Long Context Modeling](https://mlsanity.com/paper/2601.22379/) (2026)
- [QUOKA: Query-Oriented KV Selection For Efficient LLM Prefill](https://mlsanity.com/paper/2602.08722/) (2026)
- [From Static Inference to Dynamic Interaction: A Survey of Streaming Large Language Models](https://mlsanity.com/paper/2603.04592/) (2026)
- [GhostServe: A Lightweight Checkpointing System in the Shadow for Fault-Tolerant LLM Serving](https://mlsanity.com/paper/2605.00831/) (2026)
- [An Efficient Hybrid Sparse Attention with CPU-GPU Parallelism for Long-Context Inference](https://mlsanity.com/paper/2605.07719/) (2026)
- [Unveiling Effective In-Context Configurations for Image Captioning: An External & Internal Analysis](https://mlsanity.com/paper/2507.08021/) (2025)
- [CSAttention: Centroid-Scoring Attention for Accelerating LLM Inference](https://mlsanity.com/paper/2604.08584/) (2026)

## Abstract (arXiv)

Large language models (LLMs) now support extremely long context windows, but the quadratic complexity of vanilla attention results in significantly long Time-to-First-Token (TTFT) latency. Existing approaches to address this complexity require additional pretraining or finetuning, and often sacrifice model accuracy. In this paper, we first provide both theoretical and empirical foundations for near-lossless sparse attention. We find dynamically capturing head-specific sparse patterns at runtime with low overhead is crucial. To address this, we propose SampleAttention, an adaptive structured and near-lossless sparse attention. Leveraging observed significant sparse patterns, SampleAttention attends to a fixed percentage of adjacent tokens to capture local window patterns, and employs a two-stage query-guided key-value filtering approach, which adaptively select a minimum set of key-values with low overhead, to capture column stripe patterns. Comprehensive evaluations show that SampleAttention can seamlessly replace vanilla attention in off-the-shelf LLMs with nearly no accuracy loss, and reduces TTFT by up to 2.42× compared with FlashAttention.