mlsanityData to 14 Oct 2026

Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding

arXiv 2503.11108 ↗First posted 14 Mar 2025cs.LG cs.AI cs.CCcited by 2

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

Abstract (arXiv)

The key-value (KV) cache in the tensor version of transformers presents a significant bottleneck during inference. While previous work analyzes the fundamental space complexity barriers in standard attention mechanisms [Haris and Onak, 2025], our work generalizes the space complexity barriers result to tensor attention version. Our theoretical contributions rely on a reduction from communication complexity and deduce the memory lower bound for tensor-structured attention mechanisms when d = Omega(log n). Furthermore, we introduce two types of tensor attention cache and present a trade-off between time and memory for two scenarios. Overall, our work provides a theoretical foundation for us to understand the time-memory tradeoff of KV-Cache compression in tensor attention decoding and offers more perspectives in developing more memory-efficient tensor attention Transformer architectures.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 121 of its 159 references that are in the map. First posted on arXiv 14 Mar 2025.

Builds on

121 of 159 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025Compression Barriers for Autoregressive Transformers21 Feb
  2. 2024Compute Or Load KV Cache? Why Not Both?4 Oct
  3. 2024MiniCache: KV Cache Compression in Depth Dimension for Large Language Models23 May
  4. 2024SubGen: Token Generation in Sublinear Time and Memory8 Feb
  5. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models24 Jun
  6. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time26 May

Other references · 115

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  6. 2023GPT-4 Technical Reportcited by 18,396
  7. 2024The Llama 3 Herd of Modelscited by 14,715
  8. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  9. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  10. 2021Swin Transformer: Hierarchical Vision Transformer using Shifted Windowscited by 12,139
  11. 2020End-to-End Object Detection with Transformerscited by 7,414
  12. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
38 more
  1. 2020Training data-efficient image transformers & distillation through attentioncited by 4,586
  2. 2021The Power of Scale for Parameter-Efficient Prompt Tuningcited by 3,795
  3. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  4. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  5. 2021BEiT: BERT Pre-Training of Image Transformerscited by 2,375
  6. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  7. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  8. 2021Calibrate Before Use: Improving Few-Shot Performance of Language Modelscited by 1,392
  9. 2020Making Pre-trained Language Models Better Few-shot Learnerscited by 1,256
  10. 2024Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Predictioncited by 1,023
  11. 2023LLaMA-Adapter: Efficient Fine-tuning of Language Models with Zero-init Attentioncited by 781
  12. 2018Image Transformercited by 772
  13. 2022Transformers learn in-context by gradient descentcited by 732
  14. 2023LLaMA-Adapter V2: Parameter-Efficient Visual Instruction Modelcited by 602
  15. 2022Efficiently Scaling Transformer Inferencecited by 539
  16. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  17. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 252
  18. 2023Representational Strengths and Limitations of Transformerscited by 133
  19. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 130
  20. 2023Fast Attention Requires Bounded Entriescited by 102
  21. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  22. 2024FlowAR: Scale-wise Autoregressive Image Generation Meets Flow Matchingcited by 80
  23. 2014Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcingcited by 63
  24. 2024QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overheadcited by 52
  25. 2023An Over-parameterized Exponential Regressioncited by 45
  26. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  27. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  28. 2024SKVQ: Sliding-window Key and Value Cache Quantization for Large Language Modelscited by 44
  29. 2023On Sparse Modern Hopfield Modelcited by 42
  30. 2024On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscited by 41
  31. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 40
  32. 2013Sequential Transfer in Multi-armed Bandit with Finite Set of Modelscited by 38
  33. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  34. 2017Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimizationcited by 35
  35. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  36. 2023STanHop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Predictioncited by 35
  37. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  38. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32

50 most cited of 115 All 115 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

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

2 papers.

  1. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  2. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026Tensor Cache: Eviction-conditioned Associative Memory for Transformers
  2. 2026KV Cache Compression Through the Lens of Transform Coding
  3. 2026Towards Tight Bounds for Streaming Attention
  4. 2024A Simple and Effective L2 Norm-Based Strategy for KV Cache Compression
  5. 2026Multi-Head Low-Rank Attention
  6. 2026The risk of KV cache compression
  7. 2025TPLA: Tensor Parallel Latent Attention for Efficient Disaggregated Prefill and Decode Inference
  8. 2023Deep Tensor Network