Nearly Optimal Attention Coresets
Not on the map. Why?
Abstract (arXiv)
We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values (K,V) in ℝd, there exists a subset (K',V') of size at most O(√d eρ+o(ρ)/varepsilon) such that [ left| operatornameAttn(q,K,V)- operatornameAttn(q,K',V') right| ≤ varepsilon ] simultaneously for all queries whose norm is bounded by ρ. This outperforms the best known results for this problem. We also offer an improved lower bound showing that varepsilon-coresets must have size Omega(√d eρ/ε).
Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 45 of its 54 references that are in the map. First posted on arXiv 7 May 2026.
Builds on
45 of 54 references.
References · 45
- 2017Attention Is All You Needcited by 60,361
- 2023GPT-4 Technical Reportcited by 18,396
- 2020Scaling Laws for Neural Language Modelscited by 6,586
- 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
- 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,718
- 2021Prefix-Tuning: Optimizing Continuous Prompts for Generationcited by 3,915
- 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
- 2020Longformer: The Long-Document Transformercited by 3,413
- 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
- 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
- 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
- 2020Rethinking Attention with Performerscited by 1,601
33 more
- 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
- 2024SnapKV: LLM Knows What You are Looking for Before Generationcited by 880
- 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 832
- 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
- 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 575
- 2022Efficiently Scaling Transformer Inferencecited by 539
- 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 501
- 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMscited by 474
- 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Timecited by 439
- 2024PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funnelingcited by 432
- 2024xLSTM: Extended Long Short-Term Memorycited by 327
- 2024DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Headscited by 288
- 2024Data Engineering for Scaling Language Models to 128K Contextcited by 186
- 2025TurboQuant: Online Vector Quantization with Near-optimal Distortion Ratecited by 125
- 2023Fast Attention Requires Bounded Entriescited by 102
- 2024Not All Heads Matter: A Head-Level KV Cache Compression Method with Integrated Retrieval and Reasoningcited by 97
- 2025Cartridges: Lightweight and general-purpose long context representations via self-studycited by 86
- 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
- 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
- 2024RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Searchcited by 48
- 2015Frequent Directions : Simple and Deterministic Matrix Sketchingcited by 39
- 2026Fast KV Compaction via Attention Matchingcited by 31
- 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
- 2019Discrepancy, Coresets, and Sketches in Machine Learningcited by 30
- 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
- 2024SubGen: Token Generation in Sublinear Time and Memorycited by 21
- 2025Streaming Attention Approximation via Discrepancy Theorycited by 11
- 2025Short window attention enables long-term memorizationcited by 11
- 2014Spectral norm of random tensorscited by 9
- 2019Online Vector Balancing and Geometric Discrepancycited by 9
- 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
- 2024A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluationscited by 5
- 2023Optimal Online Discrepancy Minimizationcited by 2
Built on by
Citing papers per year: 2026: 4.
4 papers.