Pith. sign in

REVIEW 14 cited by

MagicPIG: LSH Sampling for Efficient LLM Generation

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.16179 v4 pith:5TSRCTMN submitted 2024-10-21 cs.CL cs.LG

Zhuoming Chen , Ranajoy Sadhukhan , Zihao Ye , Yang Zhou , Jianyu Zhang , Niklas Nolte , Yuandong Tian , Matthijs Douze
show 3 more authors
Leon Bottou Zhihao Jia Beidi Chen
This is my paper · ORCID
classification cs.CLcs.LG
keywords attentionmagicpigapproximationsparseaccuracycomputationcontextdecoding
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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\times$ 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 14 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Unveiling Simplicities of Attention: Adaptive Long-Context Head Identification

    cs.CL 2025-02 conditional novelty 7.0 of 10

    A second-moment Gaussian approximation of bulk key distributions lets a cheap query-adaptive test label attention heads as local or long-context, matching a full-attention oracle and outperforming static head pruning.

  2. ParisKV: Fast and Drift-Robust KV-Cache Retrieval for Long-Context LLMs

    cs.LG 2026-02 conditional novelty 6.0 of 10

    ParisKV retrieves top-K KV pairs on GPU using analytic sign-pattern centroids and calibrated 4-bit reranking, matching full attention accuracy in most settings while cutting million-token decode latency up to 44x.

  3. What Makes Position Zero Special? A Mechanistic Study of Position Zero Attention Sinks in LLMs

    cs.LG 2026-02 conditional novelty 6.0 of 10

    Position-zero attention sinks in transformers emerge from causal-masking asymmetry: position zero attends only to itself, and an MLP then amplifies its representation into a stable, high-norm 'sink'.

  4. vAttention: Verified Sparse Attention

    cs.LG 2025-10 conditional novelty 6.0 of 10

    vAttention is a sparse attention method that mixes heavy-hitter tokens with a statistically sized random sample to provide (ε, δ)-guaranteed approximation of full attention.

  5. Rectified Sparse Attention

    cs.CL 2025-06 conditional novelty 6.0 of 10

    ReSA keeps sparse decoding accurate by refreshing the KV cache with dense attention every f tokens, achieving near-lossless quality with a large speedup.

  6. HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inference

    cs.LG 2025-06 conditional novelty 6.0 of 10

    HATA learns per-head binary hash codes for queries and keys and selects top-k tokens by Hamming distance, achieving up to 7.2x decoding speedup over full attention with near-baseline accuracy on tested benchmarks.

  7. Hardware-Efficient Attention for Fast Decoding

    cs.LG 2025-05 conditional novelty 6.0 of 10

    Grouped-Tied Attention and Grouped Latent Attention reduce KV-cache memory and speed up LLM decoding by up to 2x while matching the quality of GQA and MLA at up to 1.47B parameters.

  8. GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity?

    cs.CL 2025-02 conditional novelty 6.0 of 10

    A new synthetic benchmark reveals that LLM reasoning accuracy decays sigmoidally with problem complexity and that repeated sampling has poor scaling efficiency.

  9. OrchANN: Hierarchical Orchestration for Skewed Out-of-Core Vector Search

    cs.DB 2025-12 conditional novelty 5.5 of 10

    OrchANN's unified I/O orchestration—hybrid per-cluster indexes, query-driven routing graphs, and triangle-inequality pruning—cuts SSD reads and outperforms DiskANN, Starling, SPANN, and PipeANN in out-of-core vector search.

  10. GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction

    cs.CL 2025-08 conditional novelty 5.0 of 10

    GraphKV adds a similarity-based decay penalty to existing top-k KV cache eviction scores, improving retention diversity and accuracy on LongBench and needle-in-a-haystack tasks.

  11. Learn from the Past: Fast Sparse Indexing for Large Language Model Decoding

    cs.LG 2025-05 reject novelty 5.0 of 10

    LFPS predicts which KV cache positions a decoder will attend to by reusing historical vertical and slash patterns plus local expansion, then runs exact Top-k only on the predicted candidate set.

  12. Exploiting Sparsity for Long Context Inference: Million Token Contexts on Commodity GPUs

    cs.CL 2025-02 conditional novelty 5.0 of 10

    A top-k attention mechanism backed by CPU vector search allows million-token LLM contexts to run on a 16GB GPU while keeping over 95% of dense-attention performance, though the 2% sparsity claim does not hold at the l...

  13. An Overview of Algorithms for Contactless Cardiac Feature Extraction from Radar Signals: Advances and Challenges

    eess.SP 2025-08 unverdicted novelty 4.0 of 10

    The paper claims to be the first review of signal-processing algorithms for radar-based cardiac monitoring, with a new taxonomy and public dataset listings.

  14. SeerAttention-R: Sparse Attention Adaptation for Long Reasoning

    cs.LG 2025-06 conditional novelty 4.0 of 10

    A learned gate selects the important KV blocks during long decoding, preserving math reasoning accuracy while skipping up to 90% of attention work.

Pith tools