Exploring the Limits of KV Cache Compression in Visual Autoregressive Transformers

• URL: http://arxiv.org/abs/2503.14881v1
• Date: Wed, 19 Mar 2025 04:18:57 GMT
• Title: Exploring the Limits of KV Cache Compression in Visual Autoregressive Transformers
• Authors: Bo Chen, Xiaoyu Li, Yekun Ke, Yingyu Liang, Zhenmei Shi, Zhao Song,
• Abstract summary: We take the first step in formally defining the KV-cache compression problem for Visual Autoregressive transformers.<n>We then establish a fundamental negative result, proving that any mechanism for sequential visual token generation must use at least $Omega(n2 d)$ memory.
• Score: 25.2590541420499
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental challenge in Visual Autoregressive models is the substantial memory overhead required during inference to store previously generated representations. Despite various attempts to mitigate this issue through compression techniques, prior works have not explicitly formalized the problem of KV-cache compression in this context. In this work, we take the first step in formally defining the KV-cache compression problem for Visual Autoregressive transformers. We then establish a fundamental negative result, proving that any mechanism for sequential visual token generation under attention-based architectures must use at least $\Omega(n^2 d)$ memory, when $d = \Omega(\log n)$, where $n$ is the number of tokens generated and $d$ is the embedding dimensionality. This result demonstrates that achieving truly sub-quadratic memory usage is impossible without additional structural constraints. Our proof is constructed via a reduction from a computational lower bound problem, leveraging randomized embedding techniques inspired by dimensionality reduction principles. Finally, we discuss how sparsity priors on visual representations can influence memory efficiency, presenting both impossibility results and potential directions for mitigating memory overhead.

Related papers

• Compression Barriers for Autoregressive Transformers [0.8331054243801623]
  Key limitation of autoregressive Transformers is the large memory needed to cache all previous key-value embeddings.<n>We show that any algorithm requires $Omega(dcdot ed)$ space and prove, using tight bounds on covering numbers, that SubGen, proposed by Zandieh, Han, Mirrokni and Karbasi, matches this bound.
  arXiv  Detail & Related papers  (2025-02-21T21:37:52Z)
• PrefixKV: Adaptive Prefix KV Cache is What Vision Instruction-Following Models Need for Efficient Generation [65.36715026409873]
  Key-value (KV) cache, necessitated by the lengthy input and output sequences, notably contributes to the high inference cost. We present PrefixKV, which reframes the challenge of determining KV cache sizes for all layers into the task of searching for the optimal global prefix configuration. Our method achieves the state-of-the-art performance compared with others.
  arXiv  Detail & Related papers  (2024-12-04T15:48:59Z)
• 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)
• Reducing Fine-Tuning Memory Overhead by Approximate and Memory-Sharing Backpropagation [29.139579820699495]
  This work strives to reduce memory overhead in fine-tuning from perspectives of activation function and layer normalization. We apply our Approx-BP theory to backpropagation training and derive memory-efficient alternatives of GELU and SiLU activation functions. In addition, we introduce a Memory-Sharing Backpropagation strategy, which enables the activation memory to be shared by two adjacent layers.
  arXiv  Detail & Related papers  (2024-06-24T03:09:15Z)
• GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM [37.87634266742105]
  Key-value (KV) caching has become the de-facto to accelerate generation speed for large language models (LLMs) inference. Existing methods rely on dropping unimportant tokens or quantizing all entries uniformly. We propose GEAR, an efficient KV cache compression framework that achieves near-lossless high-ratio compression.
  arXiv  Detail & Related papers  (2024-03-08T18:48:30Z)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference [78.65321721142624]
  We focus on a memory bottleneck imposed by the key-value ( KV) cache. Existing KV cache methods approach this problem by pruning or evicting large swaths of relatively less important KV pairs. We propose LESS, a simple integration of a constant sized cache with eviction-based cache methods.
  arXiv  Detail & Related papers  (2024-02-14T18:54:56Z)
• Topology-aware Embedding Memory for Continual Learning on Expanding Networks [63.35819388164267]
  We present a framework to tackle the memory explosion problem using memory replay techniques. PDGNNs with Topology-aware Embedding Memory (TEM) significantly outperform state-of-the-art techniques.
  arXiv  Detail & Related papers  (2024-01-24T03:03:17Z)
• LoMA: Lossless Compressed Memory Attention [0.0]
  Lossless Compressed Memory Attention (LoMA) is a novel approach to reduce memory and computational demands during autoregressive generation. LoMA incorporates a specialized training or fine-tuning precedure alongside an autoregressive generation algorithm optimized for the compressed context. Experimental validation has demonstrated that LoMA significantly reducing computational consumption and memory usage.
  arXiv  Detail & Related papers  (2024-01-16T09:18:46Z)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  We introduce a novel approach for implementing the KV cache which significantly reduces its memory footprint. Our approach is based on the observation that a small portion of tokens contributes most of the value when computing attention scores. We propose Heavy Hitter (H$$O), a KV cache eviction policy that dynamically retains a balance of recent and H$$ tokens.
  arXiv  Detail & Related papers  (2023-06-24T20:11:14Z)
• DiffRate : Differentiable Compression Rate for Efficient Vision Transformers [98.33906104846386]
  Token compression aims to speed up large-scale vision transformers (e.g. ViTs) by pruning (dropping) or merging tokens. DiffRate is a novel token compression method that has several appealing properties prior arts do not have.
  arXiv  Detail & Related papers  (2023-05-29T10:15:19Z)
• Learning sparse auto-encoders for green AI image coding [5.967279020820772]
  In this paper, we address the problem of lossy image compression using a CAE with a small memory footprint and low computational power usage. We propose a constrained approach and a new structured sparse learning method. Experimental results show that the $ell_1,1$ constraint provides the best structured proximal sparsity, resulting in a high reduction of memory and computational cost.
  arXiv  Detail & Related papers  (2022-09-09T06:31:46Z)
• ABC: Attention with Bounded-memory Control [67.40631793251997]
  We show that bounded-memory control (ABC) can be subsumed into one abstraction, attention with bounded-memory control (ABC) ABC reveals new, unexplored possibilities. First, it connects several efficient attention variants that would otherwise seem apart. Last, we present a new instance of ABC, which draws inspiration from existing ABC approaches, but replaces their memory-organizing functions with a learned, contextualized one.
  arXiv  Detail & Related papers  (2021-10-06T03:53:25Z)

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.