mlsanityData to 7 Oct 2026

Compression Barriers for Autoregressive Transformers

arXiv 2502.15955 ↗First posted 21 Feb 2025cs.DS cs.AI cs.CCcited by 5

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

A key limitation of autoregressive Transformers is the large memory needed at inference-time to cache all previous key-value (KV) embeddings. Prior works address this by compressing the KV cache, but often assume specific structural properties of the embeddings. This raises the following natural question: Can truly sublinear space utilization be achieved without such assumptions? In this work, we answer this question in the negative. Any algorithm for attention-based token generation must use Theta(nd) space, where n is the number of tokens generated so far and d = Omega(log n) is the dimension of the KV embeddings. Our proof involves a reduction from a classic communication complexity problem and uses a randomized construction that leverages properties of projections in the spirit of the Johnson-Linderstrauss lemma. For the low-dimensional regime d = o(log n), we show that any algorithm requires Omega(d· ed) space and prove, using tight bounds on covering numbers, that SubGen, proposed by Zandieh, Han, Mirrokni and Karbasi, matches this bound. Further, we investigate how sparsity assumptions enable token generation in truly sublinear space, presenting impossibility results and proposing a new KV cache compression algorithm for sliding window attention when the value cache outside the window is unmasked. Finally, we analyze token generation's time complexity, using an indistinguishability argument to prove that no non-adaptive algorithm can compute attention online in sublinear time for all tokens.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 41 of its 48 references that are in the map. First posted on arXiv 21 Feb 2025.

Builds on

41 of 48 references.

Closest ancestors · 11

Same direction, newest first

  1. 2024A Survey on Large Language Model Acceleration based on KV Cache Management27 Dec
  2. 2024DiffKV: Differentiated Memory Management for Large Language Models with Parallel KV Compaction4 Dec
  3. 2024Compute Or Load KV Cache? Why Not Both?4 Oct
  4. 2024Keep the Cost Down: A Review on Methods to Optimize LLM' s KV-Cache Consumption25 Jul
  5. 2024RazorAttention: Efficient KV Cache Compression Through Retrieval Heads22 Jul
  6. 2024PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling4 Jun
  7. 2024MiniCache: KV Cache Compression in Depth Dimension for Large Language Models23 May
  8. 2024SubGen: Token Generation in Sublinear Time and Memory8 Feb
  9. 2023CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Serving11 Oct
  10. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs3 Oct
  11. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time26 May

Other references · 30

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  5. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  6. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  7. 2020Rethinking Attention with Performerscited by 1,584
  8. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  9. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  10. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 507
  11. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  12. 2019Adaptively Sparse Transformerscited by 154
18 more
  1. 2022On The Computational Complexity of Self-Attentioncited by 137
  2. 2023Representational Strengths and Limitations of Transformerscited by 132
  3. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  4. 2023Fast Attention Requires Bounded Entriescited by 102
  5. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  6. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 82
  7. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  8. 2021A Practical Survey on Faster and Lighter Transformerscited by 73
  9. 2024QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overheadcited by 47
  10. 2024SKVQ: Sliding-window Key and Value Cache Quantization for Large Language Modelscited by 41
  11. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  12. 2023Faster Causal Attention Over Large Sequences Through Sparse Flash Attentioncited by 24
  13. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  14. 2017Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Searchcited by 8
  15. 2024Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysiscited by 8
  16. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  17. 2021Greenformers: Improving Computation and Memory Efficiency in Transformer Models via Low-Rank Approximationcited by 5
  18. 2023Attention: Marginal Probability is All You Need?cited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

5 papers.

  1. 2026The risk of KV cache compressioncited by 4
  2. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  3. 2026Thin Keys, Full Values: Reducing KV Cache via Low-Dimensional Attention Selectioncited by 2
  4. 2026Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructionscited by 0
  5. 2026Divergence Timing and Cumulative Disagreement under KV-Cache Evictioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Visual Autoregressive Transformers Must Use Omega(n2 d) Memory
  2. 2026Tensor Cache: Eviction-conditioned Associative Memory for Transformers
  3. 2023Context Compression for Auto-regressive Transformers with Sentinel Tokens
  4. 2026MomentKV: Closing the Directional Gap in KV Cache Eviction for Long-Context Inference
  5. 2026AttSVD:Prompt-Adaptive Low-Rank KV Cache Compression via Attention-Guided SVD
  6. 2026Tensor Decomposition of Transformer Key-Value Caches: Spectral Structure and Format Comparison
  7. 2026Beyond Token Eviction: Mixed-Dimension Budget Allocation for Efficient KV Cache Compression
  8. 2026KV Cache Compression Through the Lens of Transform Coding