mlsanityData to 7 Oct 2026

Inference-time sparse attention with asymmetric indexing

arXiv 2502.08246 ↗First posted 12 Feb 2025cs.CLcited by 11

Not on the map. Why?

Abstract (arXiv)

Self-attention in transformer models is an incremental associative memory that maps key vectors to value vectors. One way to speed up self-attention is to employ GPU-compatible vector search algorithms based on standard partitioning methods such as k-means. However, such partitioning methods yield poor results in this context because (1) the keys and queries follow different distributions, and (2) the RoPE positional encoding hinders the bucket assignment. This paper introduces Saap (Self-Attention with Asymmetric Partitions), which overcomes these problems. It is an asymmetrical indexing technique that employs distinct partitions for keys and queries, thereby approximating self-attention with a data-adaptive sparsity pattern. It works on pretrained language models and only requires to train (offline) a small query classifier. On a long context Llama 3.1-8b model, with sequences ranging from 100k to 500k tokens, Saap typically reduces by a factor of 20 the fraction of memory that needs to be looked-up, which translates to a time saving of 60% when compared to FlashAttention-v2.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 38 of its 57 references that are in the map. First posted on arXiv 12 Feb 2025.

Builds on

38 of 57 references.

References · 38

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  5. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  6. 2017Billion-scale similarity search with GPUscited by 2,477
  7. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,291
  8. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  9. 2020Reformer: The Efficient Transformercited by 1,658
  10. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,311
  11. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,270
  12. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
26 more
  1. 2024SnapKV: LLM Knows What You are Looking for Before Generationcited by 848
  2. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  3. 2019Compressive Transformers for Long-Range Sequence Modellingcited by 699
  4. 2023YaRN: Efficient Context Window Extension of Large Language Modelscited by 584
  5. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 507
  6. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 487
  7. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMscited by 466
  8. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Timecited by 428
  9. 2016Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activationscited by 413
  10. 2024∞Bench: Extending Long Context Evaluation Beyond 100K Tokenscited by 360
  11. 2024InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memorycited by 192
  12. 2024GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLMcited by 155
  13. 2023Unlimiformer: Long-Range Transformers with Unlimited Length Inputcited by 127
  14. 2024RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrievalcited by 114
  15. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 112
  16. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 103
  17. 2024Keep the Cost Down: A Review on Methods to Optimize LLM' s KV-Cache Consumptioncited by 96
  18. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  19. 2024Evaluating Quantized Large Language Modelscited by 75
  20. 2023CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUscited by 22
  21. 2024Results of the Big ANN: NeurIPS'23 competitioncited by 21
  22. 2024FrameQuant: Flexible Low-Bit Quantization for Transformerscited by 17
  23. 2024Memory Mosaicscited by 16
  24. 2022OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queriescited by 14
  25. 2024RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Searchcited by 12
  26. 2023DeDrift: Robust Similarity Search under Content Driftcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 7.

11 papers.

  1. 2025SeerAttention-R: Sparse Attention Adaptation for Long Reasoningcited by 28
  2. 2025Kinetics: Rethinking Test-Time Scaling Lawscited by 11
  3. 2025VIBE: Vector Index Benchmark for Embeddingscited by 6
  4. 2026Self-Indexing KVCache: Predicting Sparse Attention from Compressed Keyscited by 5
  5. 2026Thin Keys, Full Values: Reducing KV Cache via Low-Dimensional Attention Selectioncited by 2
  6. 2025Machine learning and high dimensional vector searchcited by 1
  7. 2026ScenarioControl: Vision-Language Controllable Vectorized Latent Scenario Generationcited by 0
  8. 2026Cluster with Auctions for Vector Searchcited by 0
  9. 2026SAS: Simple Attention Sparsification via End-to-End Optimization of Context Rankingcited by 0
  10. 2026Self-Indexing Attention for Compression-Compatible Sparse Long-Context LLM Inferencecited by 0
  11. 2026Attention via Black-Box Vector Searchcited by 0