# Inference-time sparse attention with asymmetric indexing

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [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)
- [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)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [YaRN: Efficient Context Window Extension of Large Language Models](https://mlsanity.com/paper/2309.00071/) (2023)
- [FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision](https://mlsanity.com/paper/2407.08608/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [∞Bench: Extending Long Context Evaluation Beyond 100K Tokens](https://mlsanity.com/paper/2402.13718/) (2024)
- [InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory](https://mlsanity.com/paper/2402.04617/) (2024)
- [GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM](https://mlsanity.com/paper/2403.05527/) (2024)
- [Unlimiformer: Long-Range Transformers with Unlimited Length Input](https://mlsanity.com/paper/2305.01625/) (2023)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Keep the Cost Down: A Review on Methods to Optimize LLM' s KV-Cache Consumption](https://mlsanity.com/paper/2407.18003/) (2024)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)

## Built on by (most cited first, 11 of 11)

- [SeerAttention-R: Sparse Attention Adaptation for Long Reasoning](https://mlsanity.com/paper/2506.08889/) (2025)
- [Kinetics: Rethinking Test-Time Scaling Laws](https://mlsanity.com/paper/2506.05333/) (2025)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Self-Indexing KVCache: Predicting Sparse Attention from Compressed Keys](https://mlsanity.com/paper/2603.14224/) (2026)
- [Thin Keys, Full Values: Reducing KV Cache via Low-Dimensional Attention Selection](https://mlsanity.com/paper/2603.04427/) (2026)
- [SAS: Simple Attention Sparsification via End-to-End Optimization of Context Ranking](https://mlsanity.com/paper/2609.13141/) (2026)
- [Machine learning and high dimensional vector search](https://mlsanity.com/paper/2502.16931/) (2025)
- [ScenarioControl: Vision-Language Controllable Vectorized Latent Scenario Generation](https://mlsanity.com/paper/2604.17147/) (2026)
- [Cluster with Auctions for Vector Search](https://mlsanity.com/paper/2607.13728/) (2026)
- [Self-Indexing Attention for Compression-Compatible Sparse Long-Context LLM Inference](https://mlsanity.com/paper/2609.13205/) (2026)
- [Attention via Black-Box Vector Search](https://mlsanity.com/paper/2610.10135/) (2026)

## 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.