TL;DR
This paper introduces FAEDKV, a novel, training-free method for compressing the Key-Value (KV) cache in Large Language Models (LLMs). By transforming the KV cache into the frequency domain, FAEDKV ensures that all tokens contribute equally to the compressed representation, mitigating biases found in existing methods and significantly improving performance on long-context tasks.
What Problem Does This Paper Address?
Large Language Models (LLMs) are increasingly used for tasks requiring long contexts, such as complex reasoning and question answering. A major bottleneck for these models is the Key-Value (KV) cache, which stores intermediate computations to speed up generation. The KV cache's memory footprint grows linearly with context length, quickly consuming resources and limiting the practical context window. Existing compression methods, like token eviction or learned projections, often introduce biases by favoring recent or high-attention tokens, leading to a "lost in the middle" problem where crucial early information is forgotten. This necessitates either costly model retraining or results in degraded performance.
Methods
FAEDKV tackles this problem by leveraging the frequency domain. The core idea is to transform the KV cache into its frequency components using a novel Infinite-Window Fourier Transform (IWDFT). This allows for a more balanced representation of all tokens, regardless of their position or attention score.
Here's a breakdown of their approach:
- Frequency Domain Transformation: The KV cache is converted from the time domain to the frequency domain using the Discrete Fourier Transform (DFT).
- Infinite-Window DFT (IWDFT): To handle the growing KV cache during autoregressive decoding without excessive memory or computational overhead, they propose IWDFT. This method recursively updates frequency bins with a normalization factor based on the current sequence length, preventing overflow and avoiding the need to store past time-domain samples.
- Frequency Ablation Study: To identify which frequency components are most important for preserving information, they conduct a layer-wise ablation study. By temporarily removing different frequency "chunks" and measuring the resulting perplexity increase, they pinpoint critical spectral bands for each layer.
- Greedy Compression: Based on the ablation study, they employ a greedy strategy to select the most important frequency components for compression, discarding the rest. This ensures that essential information is retained while significantly reducing the cache size.
- Workflow:
- Pre-filling: During the initial context processing, a segment of the KV cache is transformed into the frequency domain, pruned based on importance, and stored.
- Decoding: As new tokens are generated, the compressed frequency-domain cache is updated using IWDFT. For attention calculations, the relevant parts of the compressed cache are reconstructed back to the time domain using a sparse Inverse DFT (IDFT).
Crucially, FAEDKV is training-free and requires only a one-time ablation study and minor modifications to the attention module, making it easily integrable into existing LLM architectures.
Datasets
- WikiText-103-v1: Used for the frequency ablation study to identify important spectral components.
- LongBench: A benchmark for long-context question answering, used to evaluate FAEDKV's performance against baselines.
- Needle-In-A-Haystack: A benchmark designed to test retrieval accuracy in long documents, used to assess FAEDKV's ability to preserve information integrity across varying context lengths and token positions.
- PG19: Used for evaluating pre-filling and decoding latency.
Key Insights and Ideas
- Frequency Domain as a Bias Mitigator: The most significant insight is that transforming the KV cache into the frequency domain inherently treats all tokens more equally. This bypasses the "attention score bias" that plagues eviction-based methods, leading to more robust long-context understanding.
- IWDFT for Efficient, Unbiased Updates: The proposed IWDFT is a clever solution to recursively update the compressed KV cache without needing to store full time-domain windows or losing information from older tokens.
- Frequency Components Hold Diverse Information: The ablation study revealed that while low-frequency components are generally important, many high-frequency components also play a critical, non-negligible role. This suggests that simple low-pass filtering is suboptimal and a more nuanced, chunk-based approach is necessary.
- Position-Agnostic Retrieval: FAEDKV's frequency-domain approach leads to remarkably consistent retrieval accuracy, irrespective of where the target information is located within the document.
Key Results
- LongBench Performance: FAEDKV achieved significant accuracy improvements, outperforming existing methods like H2O by up to 22% and SnapKV by 2.12 points on average, especially under tight cache budget constraints.
- Needle-In-A-Haystack: FAEDKV demonstrated superior and more consistent retrieval accuracy compared to LoCoCo, especially across different context lengths and compression ratios. It showed remarkable position-agnostic retrieval.
- Latency: FAEDKV maintained efficient generation for sequences up to 24k tokens, whereas a full KV cache baseline ran into VRAM limits beyond 12k tokens. FAEDKV showed consistent improvements in pre-fill and decoding latency.
- Compression Ratio: FAEDKV achieved competitive compression ratios (e.g., 0.094, 0.125, 0.25) while maintaining high performance.
Limitations and Future Work
- Experimental Scale: Experiments were conducted on models deployable on a single A6000 GPU, simulating resource-constrained environments. The behavior of significantly larger models and the scalability of FAEDKV warrant further investigation.
- Further Optimization: Opportunities exist for even more performant frequency-based inference by exploring signal locality or semantic clustering within the frequency domain.
- Architectural Extension: FAEDKV focuses on efficient KV cache management within the existing maximum context length and does not inherently extend the model's architectural limit. Future work could explore how to combine FAEDKV with methods that extend the context window itself.
Summary updated