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

• URL: http://arxiv.org/abs/2503.11108v2
• Date: Thu, 27 Mar 2025 07:02:19 GMT
• Title: Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
• Authors: Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Yu Tian,
• Abstract summary: The key-value cache in the tensor version of transformers presents a significant bottleneck during inference.<n>Our work generalizes the space complexity barriers result to tensor attention version.<n>Overall, our work provides a theoretical foundation for us to understand the time-memory tradeoff of KV-Cache compression in tensor attention decoding.
• Score: 30.769940410718558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Warp-Cortex: An Asynchronous, Memory-Efficient Architecture for Million-Agent Cognitive Scaling on Consumer Hardware [0.0]
  We present Warp Cortex, an asynchronous architecture that theoretically enables million-agent cognitive scaling.<n>We empirically demonstrate 100 concurrent agents at 2.2 GB total VRAM, with theoretical capacity exceeding 1,000 agents before compute latency becomes the bottleneck.<n>We further introduce Referential Injection, a non-intrusive KV-cache update mechanism that allows asynchronous sub-agents to influence primary generation without stream disruption.
  arXiv  Detail & Related papers  (2026-01-03T23:11:21Z)
• Trellis: Learning to Compress Key-Value Memory in Attention Models [48.12167339402521]
  This paper introduces Trellis, a novel Transformer architecture with bounded memory.<n> Trellis replaces the standard KV cache with a fixed-size memory and train a two-pass recurrent compression mechanism to store new keys and values into memory.<n>Experiments on language modeling, common-sense reasoning, recall-intensive tasks, and time series show that the proposed architecture outperforms strong baselines.
  arXiv  Detail & Related papers  (2025-12-29T20:32:10Z)
• QuantSparse: Comprehensively Compressing Video Diffusion Transformer with Model Quantization and Attention Sparsification [67.15451442018258]
  Diffusion transformers exhibit remarkable video generation capability, yet their prohibitive computational and memory costs hinder practical deployment.<n>Model quantization and attention sparsification are two promising directions for compression, but each alone suffers severe performance degradation under aggressive compression.<n>We propose textbfQuantSparse, a unified framework that integrates model quantization with attention sparsification.
  arXiv  Detail & Related papers  (2025-09-28T06:49:44Z)
• KV-Latent: Dimensional-level KV Cache Reduction with Frequency-aware Rotary Positional Embedding [72.12756830560217]
  Large language models (LLMs) based on Transformer Decoders have become the preferred choice for conversational generative AI.<n>Despite the overall superiority of the Decoder architecture, the gradually increasing Key-Value cache during inference has emerged as a primary efficiency bottleneck.<n>By down-sampling the Key-Value vector dimensions into a latent space, we can significantly reduce the KV Cache footprint and improve inference speed.
  arXiv  Detail & Related papers  (2025-07-15T12:52:12Z)
• ReCalKV: Low-Rank KV Cache Compression via Head Reordering and Offline Calibration [81.81027217759433]
  Large language models (LLMs) are often constrained by the excessive memory required to store the Key-Value ( KV) cache.<n>Recent methods have explored reducing the hidden dimensions of the KV cache, but many introduce additional computation through projection layers.<n>We propose ReCalKV, a post-training KV cache compression method that reduces the hidden dimensions of the KV cache.
  arXiv  Detail & Related papers  (2025-05-30T08:49:27Z)
• Memory-Efficient Visual Autoregressive Modeling with Scale-Aware KV Cache Compression [21.840636839249026]
  We introduce ScaleKV, a novel KV cache compression framework tailored for Visual Autoregressive ( VAR) architectures.<n>Based on two critical observations, ScaleKV categorizes transformer layers into two functional groups: drafters and refiners.<n>Our approach effectively reduces the required KV cache memory to 10% while preserving pixel-level fidelity.
  arXiv  Detail & Related papers  (2025-05-26T07:11:42Z)
• Bottlenecked Transformers: Periodic KV Cache Abstraction for Generalised Reasoning [9.730604030100318]
  Large Language Models struggle with generalisation beyond their training distribution.<n>IB theory posits that model generalisation emerges from an optimal balance between input compression and retention of predictive information in latent representations.<n>We show that decoder-only Transformers are inherently constrained in their ability to form task-optimal sequence representations.<n>We propose a modification to the Transformer architecture, in the form of an additional module that globally rewrites the KV cache.
  arXiv  Detail & Related papers  (2025-05-22T17:33:49Z)
• SQuat: Subspace-orthogonal KV Cache Quantization [19.131705063324883]
  We introduce SQuat (Subspace-orthogonal KV cache quantization), which reduces peak memory by 2.17 to 2.82, improves throughput by 2.45 to 3.60, and achieves more favorable benchmark scores than existing KV cache quantization algorithms. We show that our method reduces peak memory by 2.17 to 2.82, improves throughput by 2.45 to 3.60, and achieves more favorable benchmark scores than existing KV cache quantization algorithms.
  arXiv  Detail & Related papers  (2025-03-31T17:37:32Z)
• Tensor Product Attention Is All You Need [54.40495407154611]
  Product Attention (TPA) is a novel attention mechanism that uses tensor decompositions to represent queries, keys, and values compactly.<n>TPA achieves improved model quality alongside memory efficiency.<n>We introduce the ProducT ATTion Transformer (T6), a new model architecture for sequence modeling.
  arXiv  Detail & Related papers  (2025-01-11T03:37:10Z)
• Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers [23.991344681741058]
  We analyze the circuit complexity of Attention and $mathsfRoPE$-based Attention, showing that they cannot solve fixed membership problems or $(A_F,r)*$ closure problems.<n>These findings highlight a gap between the empirical performance and theoretical constraints of Attention and $mathsfRoPE$-based Attention Transformers.
  arXiv  Detail & Related papers  (2024-12-23T23:26:07Z)
• More Tokens, Lower Precision: Towards the Optimal Token-Precision Trade-off in KV Cache Compression [71.42818367729573]
  In large language models (LLMs), the memory usage of KV cache has become a critical bottleneck during inference. The mainstream KV compression methods, including KV pruning and KV quantization, primarily focus on either token or precision dimension separately. In this paper, we comprehensively investigate the token-precision trade-off in KV cache compression.
  arXiv  Detail & Related papers  (2024-12-17T09:20:31Z)
• CSR:Achieving 1 Bit Key-Value Cache via Sparse Representation [63.65323577445951]
  We propose a novel approach called Cache Sparse Representation (CSR) CSR transforms the dense Key-Value cache tensor into sparse indexes and weights, offering a more memory-efficient representation during LLM inference. Our experiments demonstrate CSR achieves performance comparable to state-of-the-art KV cache quantization algorithms.
  arXiv  Detail & Related papers  (2024-12-16T13:01:53Z)
• LoRC: Low-Rank Compression for LLMs KV Cache with a Progressive Compression Strategy [59.1298692559785]
  Key-Value ( KV) cache is crucial component in serving transformer-based autoregressive large language models (LLMs) Existing approaches to mitigate this issue include: (1) efficient attention variants integrated in upcycling stages; (2) KV cache compression at test time; and (3) KV cache compression at test time. We propose a low-rank approximation of KV weight matrices, allowing plug-in integration with existing transformer-based LLMs without model retraining. Our method is designed to function without model tuning in upcycling stages or task-specific profiling in test stages.
  arXiv  Detail & Related papers  (2024-10-04T03:10:53Z)
• Eigen Attention: Attention in Low-Rank Space for KV Cache Compression [9.080678336379528]
  We propose Eigen Attention, which performs the attention operation in a low-rank space, thereby reducing the KV cache memory overhead. We show that Eigen Attention results in up to 40% reduction in KV cache sizes and up to 60% reduction in attention operation latency with minimal drop in performance.
  arXiv  Detail & Related papers  (2024-08-10T22:47:12Z)
• A Simple and Effective $L_2$ Norm-Based Strategy for KV Cache Compression [13.981807478365452]
  Existing approaches to reduce the Key-Value cache size involve either fine-tuning the model to learn a compression strategy or leveraging attention scores to reduce the sequence length. We find a clear correlation between the $L$ and the attention scores over cached KV pairs, where a low $L$ of a key embedding leads to a high attention score during decoding. Our experimental results show that this simple strategy can reduce the KV cache size by 50% on language modelling and needle-in-a-haystack tasks and 90% on passkey retrieval tasks without losing accuracy.
  arXiv  Detail & Related papers  (2024-06-17T11:35:16Z)
• Tensor Attention Training: Provably Efficient Learning of Higher-order Transformers [18.331374727331077]
  Time complexity of tensor attention is a significant obstacle to its utilization in transformers. We prove that the backward gradient of attention training can be computed in almost linear time.
  arXiv  Detail & Related papers  (2024-05-26T02:59:13Z)
• Unlocking Data-free Low-bit Quantization with Matrix Decomposition for KV Cache Compression [87.5604418100301]
  Key-value( KV) caching is an important technique to accelerate the inference of large language models. Existing methods often compromise precision or require extra data for calibration. We introduce textbfDecoQuant, a novel data-free low-bit quantization technique based on tensor decomposition methods.
  arXiv  Detail & Related papers  (2024-05-21T08:35:10Z)
• CORM: Cache Optimization with Recent Message for Large Language Model Inference [57.109354287786154]
  We introduce an innovative method for optimizing the KV cache, which considerably minimizes its memory footprint. CORM, a KV cache eviction policy, dynamically retains essential key-value pairs for inference without the need for model fine-tuning. Our validation shows that CORM reduces the inference memory usage of KV cache by up to 70% with negligible performance degradation across six tasks in LongBench.
  arXiv  Detail & Related papers  (2024-04-24T16:11:54Z)
• FAST: Factorizable Attention for Speeding up Transformers [1.3637227185793512]
  We present a linearly scaled attention mechanism that maintains the full representation of the attention matrix without compromising on sparsification. Results indicate that our attention mechanism has a robust performance and holds significant promise for diverse applications where self-attention is used.
  arXiv  Detail & Related papers  (2024-02-12T18:59:39Z)
• On the Convergence of Encoder-only Shallow Transformers [62.639819460956176]
  We build the global convergence theory of encoder-only shallow Transformers under a realistic setting. Our results can pave the way for a better understanding of modern Transformers, particularly on training dynamics.
  arXiv  Detail & Related papers  (2023-11-02T20:03:05Z)
• Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs [82.08922896531618]
  We introduce adaptive KV cache compression, a plug-and-play method that reduces the memory footprint of generative inference for Large Language Models (LLMs) We conduct targeted profiling to discern the intrinsic structure of attention modules. Based on the recognized structure, we then construct the KV cache in an adaptive manner: evicting long-range contexts on attention heads emphasizing local contexts, discarding non-special tokens on attention heads centered on special tokens, and only employing the standard KV cache for attention heads that broadly attend to all tokens.
  arXiv  Detail & Related papers  (2023-10-03T05:17:08Z)
• Multi-Grid Tensorized Fourier Neural Operator for High-Resolution PDEs [93.82811501035569]
  We introduce a new data efficient and highly parallelizable operator learning approach with reduced memory requirement and better generalization. MG-TFNO scales to large resolutions by leveraging local and global structures of full-scale, real-world phenomena. We demonstrate superior performance on the turbulent Navier-Stokes equations where we achieve less than half the error with over 150x compression.
  arXiv  Detail & Related papers  (2023-09-29T20:18:52Z)
• Mega: Moving Average Equipped Gated Attention [150.3124713793503]
  Mega is a simple, theoretically grounded, single-head gated attention mechanism equipped with (exponential) moving average. We show that Mega achieves significant improvements over other sequence models, including variants of Transformers and recent state space models.
  arXiv  Detail & Related papers  (2022-09-21T20:52:17Z)
• Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers [42.93754828584075]
  We present a new Transformer architecture, Performer, based on Fast Attention Via Orthogonal Random features (FAVOR) Our mechanism scales linearly rather than quadratically in the number of tokens in the sequence, is characterized by sub-quadratic space complexity and does not incorporate any sparsity pattern priors. It provides strong theoretical guarantees: unbiased estimation of the attention matrix and uniform convergence.
  arXiv  Detail & Related papers  (2020-06-05T17:09:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.