# MagicPIG: LSH Sampling for Efficient LLM Generation

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

## Key facts

- Cited by 111 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 73 references that are in the map.
- First posted on arXiv 21 Oct 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [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)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [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)
- [VideoLLaMA 2: Advancing Spatial-Temporal Modeling and Audio Understanding in Video-LLMs](https://mlsanity.com/paper/2406.07476/) (2024)
- [CoQA: A Conversational Question Answering Challenge](https://mlsanity.com/paper/1808.07042/) (2018)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [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)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [RepoBench: Benchmarking Repository-Level Code Auto-Completion Systems](https://mlsanity.com/paper/2306.03091/) (2023)
- [Retrieval Head Mechanistically Explains Long-Context Factuality](https://mlsanity.com/paper/2404.15574/) (2024)
- [QServe: W4A8KV4 Quantization and System Co-design for Efficient LLM Serving](https://mlsanity.com/paper/2405.04532/) (2024)
- [How to Train Long-Context Language Models (Effectively)](https://mlsanity.com/paper/2410.02660/) (2024)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference](https://mlsanity.com/paper/2403.09054/) (2024)
- [Leave No Document Behind: Benchmarking Long-Context LLMs with Extended Multi-Doc QA](https://mlsanity.com/paper/2406.17419/) (2024)

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

- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [A Survey on Large Language Model Acceleration based on KV Cache Management](https://mlsanity.com/paper/2412.19442/) (2024)
- [KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction](https://mlsanity.com/paper/2505.23416/) (2025)
- [SCBench: A KV Cache-Centric Analysis of Long-Context Methods](https://mlsanity.com/paper/2412.10319/) (2024)
- [Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning](https://mlsanity.com/paper/2502.02770/) (2025)
- [RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression](https://mlsanity.com/paper/2502.14051/) (2025)
- [SeerAttention-R: Sparse Attention Adaptation for Long Reasoning](https://mlsanity.com/paper/2506.08889/) (2025)
- [The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs](https://mlsanity.com/paper/2504.17768/) (2025)
- [HashAttention: Semantic Sparsity for Faster Inference](https://mlsanity.com/paper/2412.14468/) (2024)
- [Efficient Attention Mechanisms for Large Language Models: A Survey](https://mlsanity.com/paper/2507.19595/) (2025)
- [SCOPE: Optimizing Key-Value Cache Compression in Long-context Generation](https://mlsanity.com/paper/2412.13649/) (2024)
- [FreeKV: Boosting KV Cache Retrieval for Efficient LLM Inference](https://mlsanity.com/paper/2505.13109/) (2025)
- [Learning to Evict from Key-Value Cache](https://mlsanity.com/paper/2602.10238/) (2026)
- [RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference](https://mlsanity.com/paper/2505.02922/) (2025)
- [Kinetics: Rethinking Test-Time Scaling Laws](https://mlsanity.com/paper/2506.05333/) (2025)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [TailorKV: A Hybrid Framework for Long-Context Inference via Tailored KV Cache Optimization](https://mlsanity.com/paper/2505.19586/) (2025)
- [Rectified Sparse Attention](https://mlsanity.com/paper/2506.04108/) (2025)
- [KeepKV: Achieving Periodic Lossless KV Cache Compression for Efficient LLM Inference](https://mlsanity.com/paper/2504.09936/) (2025)
- [AttentionPredictor: Temporal Patterns Matter for KV Cache Compression](https://mlsanity.com/paper/2502.04077/) (2025)
- [A2ATS: Retrieval-Based KV Cache Reduction via Windowed Rotary Position Embedding and Query-Aware Vector Quantization](https://mlsanity.com/paper/2502.12665/) (2025)
- [Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Serving](https://mlsanity.com/paper/2503.00392/) (2025)
- [Mustafar: Promoting Unstructured Sparsity for KV Cache Pruning in LLM Inference](https://mlsanity.com/paper/2505.22913/) (2025)
- [HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inference](https://mlsanity.com/paper/2506.02572/) (2025)
- [LeanK: Learnable K Cache Channel Pruning for Efficient Decoding](https://mlsanity.com/paper/2508.02215/) (2025)
- [Vegas: Self-Speculative Decoding with Verification-Guided Sparse Attention](https://mlsanity.com/paper/2602.07223/) (2026)
- [MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inference](https://mlsanity.com/paper/2605.07363/) (2026)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Trainable Dynamic Mask Sparse Attention](https://mlsanity.com/paper/2508.02124/) (2025)
- [GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction](https://mlsanity.com/paper/2509.00388/) (2025)

## Abstract (arXiv)

Large language models (LLMs) with long context windows have gained significant attention. However, the KV cache, stored to avoid re-computation, becomes a bottleneck. Various dynamic sparse or TopK-based attention approximation methods have been proposed to leverage the common insight that attention is sparse. In this paper, we first show that TopK attention itself suffers from quality degradation in certain downstream tasks because attention is not always as sparse as expected. Rather than selecting the keys and values with the highest attention scores, sampling with theoretical guarantees can provide a better estimation for attention output. To make the sampling-based approximation practical in LLM generation, we propose MagicPIG, a heterogeneous system based on Locality Sensitive Hashing (LSH). MagicPIG significantly reduces the workload of attention computation while preserving high accuracy for diverse tasks. MagicPIG stores the LSH hash tables and runs the attention computation on the CPU, which allows it to serve longer contexts and larger batch sizes with high approximation accuracy. MagicPIG can improve decoding throughput by up to 5× across various GPU hardware and achieve 54ms decoding latency on a single RTX 4090 for Llama-3.1-8B-Instruct model with a context of 96k tokens. The code is available at https://github.com/Infini-AI-Lab/MagicPIG.