Eigen Attention: Attention in Low-Rank Space for KV Cache Compression

Utkarsh Saxena, Gobinda Saha, Sakshi Choudhary, Kaushik Roy

TL;DR

Eigen Attention is a novel post-training technique that compresses the Key-Value (KV) cache of Large Language Models (LLMs) by performing attention in a low-rank space. By projecting keys and values into a lower-dimensional subspace determined by their principal components, the authors achieve up to a 40% reduction in memory overhead and a 60% boost in inference speed with minimal impact on model accuracy.

What Problem Does This Paper Address?

As we push LLMs toward longer context windows (e.g., 32k tokens and beyond), we hit a "memory wall." During inference, LLMs use a KV cache to store previously computed keys and values, avoiding redundant calculations. However, the size of this cache grows linearly with sequence length and batch size.

For a model like Llama-2 7B with a batch size of 16 and a 32k context, the model weights take up about 14 GB, but the KV cache balloons to a staggering 256 GB. This makes inference heavily memory-bound: the GPU's computation cores sit idle while waiting for massive amounts of KV cache data to be fetched from off-chip memory. Eigen Attention aims to shrink this footprint by reducing the embedding dimension of the cached vectors themselves.

Methods

The core idea behind Eigen Attention is that while LLM weights might be high-rank, the actual activations (the keys, queries, and values) often reside in a much lower-dimensional subspace.

  1. Basis Vector Generation: The authors run a small "calibration" set of text through the model to collect representative Query ($Q$), Key ($K$), and Value ($V$) matrices.
  2. Singular Value Decomposition (SVD): They perform SVD on these matrices to find the principal basis vectors (eigenvectors) that capture the most information.
  3. Low-Rank Projection: They project the high-dimensional $Q, K,$ and $V$ into a lower-dimensional space of rank $r$ (where $r < d$, the original dimension).
  4. Weight Merging: Crucially, these projection matrices are merged into the existing model weights ($W^Q, W^K, W^V, W^O$) offline. This means that during inference, the model naturally produces lower-dimensional keys and values, directly reducing the KV cache size without requiring extra projection steps.
Figure 1: Comparison between (a) Standard Attention and (b) Eigen Attention. Eigen Attention utilizes lower dimensional (r ≪d) query, key, and value projection matrices than the standard attention operation, leading to KV cache compression and compute FLOPs benefits.

The authors also introduce a Layer-wise Rank Allotment strategy. Instead of using the same compression ratio for every layer, they use an error-budget approach to assign more bits to sensitive layers and compress "easier" layers more aggressively.

Datasets

  • Calibration: A small subset of WikiText-2 was used to generate the basis vectors.
  • Language Generation Evaluation: Wikitext-2 and C4 were used to measure perplexity (PPL).
  • Zero-Shot Benchmarks: The models were tested on PiQA, WinoGrande, Arc-easy/challenge, and HellaSwag using the lm-eval-harness framework.
  • Fine-tuning: The Alpaca dataset was used for optional low-rank adaptation (LoRA) to recover performance lost during compression.

Key Insights and Ideas

  • Keys are more compressible than Values: The eigenvalue analysis (Figure 2) reveals that keys typically have a lower intrinsic rank than values. In practice, for a 40% total compression, keys might be compressed by 54% while values are only compressed by 26%.
  • Initial layers are "fluffier": With the exception of the very first layer, the early layers of LLMs tend to be more compressible than the later layers.
  • Orthogonality is Key: Eigen Attention doesn't replace existing methods like quantization (reducing bit-precision) or token pruning (evicting unimportant tokens). Instead, it works synergistically with them. You can compress the dimension with Eigen Attention, prune tokens with $H_2O$, and then quantize the remaining data to 4-bits.
  • The RoPE Hurdle: Models using Rotary Positional Embeddings (RoPE), like Llama, require a specific mathematical workaround because RoPE expects a fixed dimension. The authors handle this by storing low-rank keys but transforming them back to high-rank just before the attention dot-product.
Figure 2: Eigenvalue spectrum analysis for OPT-30b model. (a), (b) The Y-axis is the normalized cumulative eigenvalue value after performing SVD on the key value representation matrix, and the X-axis is an index of the largest eigenvalue. (c), (d) Dimensions of the low-rank matrices with normalized cumulative eigenvalue of 0.9.

Key Results

  • Memory Savings: Achieved up to 40% reduction in KV cache size across OPT, MPT, and Llama families.
  • Latency Gains: For the OPT-66b model, Eigen Attention provided a 60% reduction in attention operation latency.
  • Performance Recovery: While raw compression causes a slight drop in accuracy, a short fine-tuning step (2000 steps of LoRA) brought zero-shot accuracy to within 2% of the baseline.
  • OOM Prevention: In high-batch, long-context scenarios where standard attention triggered "Out of Memory" (OOM) errors, Eigen Attention allowed the model to continue functioning smoothly.

Limitations and Future Work

  • RoPE Overhead: For models like Llama-3, the extra transformation needed to support RoPE actually introduced a slight latency penalty (up to 8% in some cases), even though memory was saved. Optimizing this kernel is a clear next step.
  • Calibration Sensitivity: The authors noted that while WikiText works well, they haven't extensively studied which datasets provide the "best" basis vectors for general-purpose use.
  • Integration: Future work involves integrating Eigen Attention into high-throughput serving frameworks like vLLM to see how it performs alongside advanced memory management techniques like PagedAttention.

Summary updated

Abstract

Large language models (LLMs) represent a groundbreaking advancement in the domain of natural language processing due to their impressive reasoning abilities. Recently, there has been considerable interest in increasing the context lengths for these models to enhance their applicability to complex tasks. However, at long context lengths and large batch sizes, the key-value (KV) cache, which stores the attention keys and values, emerges as the new bottleneck in memory usage during inference. To address this, we propose Eigen Attention, which performs the attention operation in a low-rank space, thereby reducing the KV cache memory overhead. Our proposed approach is orthogonal to existing KV cache compression techniques and can be used synergistically with them. Through extensive experiments over OPT, MPT, and Llama model families, we demonstrate 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. Code is available at https://github.com/UtkarshSaxena1/EigenAttn.
BibTeX
@inproceedings{saxena2024eigen,
  author = {Utkarsh Saxena and Gobinda Saha and Sakshi Choudhary and Kaushik Roy},
  title = {{Eigen Attention: Attention in Low-Rank Space for KV Cache Compression}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=BuAQnkzoA5},
}
Figure