mlsanityData to 14 Oct 2026

MagicPIG: LSH Sampling for Efficient LLM Generation

arXiv 2410.16179 ↗First posted 21 Oct 2024cs.CL cs.LGcited by 111

Not on the map. Why?

Cited by 64 in Efficient LLM inference and serving, but placed by its own abstract, which didn’t fit.

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.

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

50 of 73 references.

References · 50

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2024The Llama 3 Herd of Modelscited by 14,715
  4. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  5. 2020Measuring Massive Multitask Language Understandingcited by 7,963
  6. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  7. 2017TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehensioncited by 2,955
  8. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,626
  9. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,598
  10. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  11. 2020Reformer: The Efficient Transformercited by 1,668
  12. 2023LongBench: A Bilingual, Multitask Benchmark for Long Context Understandingcited by 1,417
38 more
  1. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,346
  2. 2024Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preferencecited by 1,184
  3. 2024SnapKV: LLM Knows What You are Looking for Before Generationcited by 880
  4. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 832
  5. 2024VideoLLaMA 2: Advancing Spatial-Temporal Modeling and Audio Understanding in Video-LLMscited by 771
  6. 2018CoQA: A Conversational Question Answering Challengecited by 683
  7. 2024KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachecited by 637
  8. 2022Efficiently Scaling Transformer Inferencecited by 539
  9. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 501
  10. 2021A Dataset of Information-Seeking Questions and Answers Anchored in Research Paperscited by 486
  11. 2022DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scalecited by 407
  12. 2023RepoBench: Benchmarking Repository-Level Code Auto-Completion Systemscited by 353
  13. 2024Retrieval Head Mechanistically Explains Long-Context Factualitycited by 232
  14. 2024QServe: W4A8KV4 Quantization and System Co-design for Efficient LLM Servingcited by 208
  15. 2024How to Train Long-Context Language Models (Effectively)cited by 146
  16. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 130
  17. 2024Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inferencecited by 126
  18. 2024Leave No Document Behind: Benchmarking Long-Context LLMs with Extended Multi-Doc QAcited by 122
  19. 2024RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrievalcited by 116
  20. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  21. 2015Practical and Optimal LSH for Angular Distancecited by 106
  22. 2024Sequoia: Scalable, Robust, and Hardware-aware Speculative Decodingcited by 103
  23. 2023Fast Attention Requires Bounded Entriescited by 102
  24. 2024TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decodingcited by 102
  25. 2024PQCache: Product Quantization-based KVCache for Long Context LLM Inferencecited by 95
  26. 2024Loki: Low-rank Keys for Efficient Sparse Attentioncited by 89
  27. 2023FlashDecoding++: Faster Large Language Model Inference on GPUscited by 71
  28. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  29. 2024FastDecode: High-Throughput GPU-Efficient LLM Serving using Heterogeneous Pipelinescited by 49
  30. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  31. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 44
  32. 2021FBGEMM: Enabling High-Performance Low-Precision Deep Learning Inferencecited by 41
  33. 2021A Survey on Locality Sensitive Hashing Algorithms and their Applicationscited by 40
  34. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  35. 2017A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Modelscited by 16
  36. 2024IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUscited by 8
  37. 2024Inference Performance Optimization for Large Language Models on CPUscited by 6
  38. 2017Unique Entity Estimation with Application to the Syrian Conflictcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 48; 2026: 58.

111 papers.

Sort:

By area:

  1. 2025Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attentioncited by 407
  2. 2024A Survey on Large Language Model Acceleration based on KV Cache Managementcited by 131
  3. 2025KVzip: Query-Agnostic KV Cache Compression with Context Reconstructioncited by 95
  4. 2024SCBench: A KV Cache-Centric Analysis of Long-Context Methodscited by 60
  5. 2025Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruningcited by 49
  6. 2025RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compressioncited by 41
  7. 2025SeerAttention-R: Sparse Attention Adaptation for Long Reasoningcited by 30
  8. 2025The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMscited by 29
  9. 2024HashAttention: Semantic Sparsity for Faster Inferencecited by 24
  10. 2025Efficient Attention Mechanisms for Large Language Models: A Surveycited by 22
  11. 2024SCOPE: Optimizing Key-Value Cache Compression in Long-context Generationcited by 20
  12. 2025FreeKV: Boosting KV Cache Retrieval for Efficient LLM Inferencecited by 14
38 more
  1. 2026Learning to Evict from Key-Value Cachecited by 14
  2. 2025RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inferencecited by 13
  3. 2025Kinetics: Rethinking Test-Time Scaling Lawscited by 12
  4. 2025Inference-time sparse attention with asymmetric indexingcited by 11
  5. 2025TailorKV: A Hybrid Framework for Long-Context Inference via Tailored KV Cache Optimizationcited by 10
  6. 2025Rectified Sparse Attentioncited by 10
  7. 2025KeepKV: Achieving Periodic Lossless KV Cache Compression for Efficient LLM Inferencecited by 9
  8. 2025AttentionPredictor: Temporal Patterns Matter for KV Cache Compressioncited by 7
  9. 2025A2ATS: Retrieval-Based KV Cache Reduction via Windowed Rotary Position Embedding and Query-Aware Vector Quantizationcited by 7
  10. 2025Progressive Sparse Attention: Algorithm and System Co-design for Efficient Attention in LLM Servingcited by 7
  11. 2025Mustafar: Promoting Unstructured Sparsity for KV Cache Pruning in LLM Inferencecited by 7
  12. 2025HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inferencecited by 7
  13. 2025LeanK: Learnable K Cache Channel Pruning for Efficient Decodingcited by 7
  14. 2026Vegas: Self-Speculative Decoding with Verification-Guided Sparse Attentioncited by 7
  15. 2026MISA: Mixture of Indexer Sparse Attention for Long-Context LLM Inferencecited by 7
  16. 2025VIBE: Vector Index Benchmark for Embeddingscited by 6
  17. 2025Trainable Dynamic Mask Sparse Attentioncited by 6
  18. 2025GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Evictioncited by 6
  19. 2025SparseServe: Unlocking Parallelism for Dynamic Sparse Attention in Long-Context LLM Servingcited by 6
  20. 2025vAttention: Verified Sparse Attentioncited by 6
  21. 2025Hold Onto That Thought: Assessing KV Cache Compression On Reasoningcited by 6
  22. 2025Exploiting Sparsity for Long Context Inference: Million Token Contexts on Commodity GPUscited by 5
  23. 2025Unveiling Simplicities of Attention: Adaptive Long-Context Head Identificationcited by 5
  24. 2025Memory Mosaics at scalecited by 5
  25. 2026Double-P: Hierarchical Top-P Sparse Attention for Long-Context LLMscited by 5
  26. 2026IceCache: Memory-efficient KV-cache Management for Long-Sequence LLMscited by 5
  27. 2026KVDrive: A Holistic Multi-Tier KV Cache Management System for Long-Context LLM Inferencecited by 5
  28. 2026SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inferencecited by 5
  29. 2026Sparrow: Sparse Rollout for Stable and Efficient Long-context RL of Large Language Modelscited by 5
  30. 2026SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformerscited by 5
  31. 2024Deploying Foundation Model Powered Agent Services: A Surveycited by 4
  32. 2025Retrospective Sparse Attention for Efficient Long-Context Generationcited by 4
  33. 2025LouisKV: Efficient KV Cache Retrieval for Long Input-Output Sequencescited by 4
  34. 2025NOSA: Native and Offloadable Sparse Attentioncited by 4
  35. 2025KV Admission: Learning What to Write for Efficient Long-Context LLM Inferencecited by 4
  36. 2026Unifying Sparse Attention with Hierarchical Memory for Scalable Long-Context LLM Servingcited by 4
  37. 2026Towards Efficient Large Language Model Serving: A Survey on System-Aware KV Cache Optimizationcited by 4
  38. 2025APB: Accelerating Distributed Long-Context Inference by Passing Compressed Context Blocks across GPUscited by 3

50 most cited of 111 All 111 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025HCAttention: Extreme KV Cache Compression via Heterogeneous Attention Computing for LLMs
  2. 2026PackInfer: Compute- and I/O-Efficient Attention for Batched LLM Inference
  3. 2025MoSKA: Mixture of Shared KV Attention for Efficient Long-Sequence LLM Inference
  4. 2025HGCA: Hybrid GPU-CPU Attention for Long Context LLM Inference
  5. 2026LycheeDecode: Accelerating Long-Context LLM Inference via Hybrid-Head Sparse Decoding
  6. 2026Multi-Segment Attention: Enabling Efficient KV-Cache Management for Faster Large Language Model Serving
  7. 2026Ragged Paged Attention: A High-Performance and Flexible LLM Inference Kernel for TPU
  8. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs