FAEDKV : Infinite-Window F ourier Transform for Unbiased KV Cache Compression (2025)

Abstract: The efficacy of Large Language Models (LLMs) in long-context tasks is often hampered by the substantial memory footprint and computational demands of the Key-Value (KV) cache. Current compression strategies, including token eviction and learned projections, frequently lead to biased representations—either by overemphasizing recent/high-attention tokens or by repeatedly degrading information from earlier context—and may require costly model retraining. We present FAEDKV (Frequency-Adaptive Infinite-Window for KV cache), a novel, training-free KV cache compression framework that ensures unbiased information retention. FAEDKV operates by transforming the KV cache into the frequency domain using a proposed Infinite-Window Fourier Transform (IWDFT). This approach allows for the equalized contribution of all tokens to the compressed representation, effectively preserving both early and recent contextual information. A preliminary frequency ablation study identifies critical spectral components for layer-wise, targeted compression. Experiments on LongBench benchmark demonstrate FAEDKV’s superiority over existing methods by up to 22%. In addition, our method shows superior, position-agnostic retrieval accuracy on the Needle-In-A-Haystack task compared to compression based approaches.

## introduction llm has become the paradigm in languagegenerating tasks. it can perform variety of important tasks such as text generation, question answering, mathmatical problem-solving. for this types of problems, a long context is often required to provide enough background information, thus they demand the model have long context capability. ## preliminaries existing kv cache compression largely relies on eviction or learning-based techniques, which can introduce recency bias. our approach differs by applying a novel frequency-domain transformation to the kv cache, aiming for equalize token contribution to the compressed state. this requires empirically analyzing frequency component importance via ablation experiments that measure perplexity changes upon pruning. this section outlines preliminaries and the frequency ablation study. ## faedkv 4.1 infinite window dft the standard discrete fourier transform (dft), as defined in equation ( 4 ), provides a static analysis of an entire input sequence. however, in autoregressive transformer models, new tokens are generated sequentially. if we were to recompute the dft over the entire growing kv cache (of current length n ) at each decoding step, this would incur a computational cost of o(n log n ) using fft (or o(n 2 ) naively) for that single step. this is problematic when compared to the typical complexities of decoder-only transformers. we notice that sliding-window dft is better being recursively updated. with window size m , it updates each frequency bin as: m , for @xmath0, 1, . . . , m -1. (8) here, x[t + 1] is the new input sample entering the window, and x[t -m + 1] is the oldest sample leaving the window.the sliding-window dft efficiently updates the windowed frequency representation at o(m ) per time step to update all m frequency bins. despite this, it presents two major drawbacks for our goal of kv cache compression. firstly, it necessitates storing all m time-domain samples of the current window. secondly, this subtraction of x[t -m + 1] completely removes information about tokens older than the m -sample window. to address the fixed memory window and associated storage overhead of the standard slidingwindow dft, an intuitive first step is to remove the subtraction of the oldest sample (x[t-m +1]). this creates a conceptually infinite, recursive window. however, this simpler recursion would lead to unbounded accumulation of values in the frequencydomain state s t [k], risking floating-point overflow for very long sequences common in llms @xcite . our infinite window dft (iwdft), defined in equation 9, prevents such overflow by incorporating a normalization factor based on the current sequence length, n , into each recursive update: here, s t [k] is the previous state for the k-th frequency bin. we approximate term n -1 n to 1 since most context is larger than 1000. this iwdft approach is applied during decoding to update the k and v caches. it resolves the primary issues of the standard sliding window by avoiding extra time-domain storage and the hard cut-off of past information. unlike methods that can introduce bias @xcite , iwdft processes each token's contribution consistently. the update is efficient (o(n df t ) per step), training-free, and compatible with autoregressive llms. ## conclusion in this paper, we introduced faedkv, a novel training-free kv cache compression algorithm designed to mitigate memory overhead in llms while promoting unbiased information retention. our approach uniquely leverages frequencydomain transformations, guided by an empirical frequency ablation study to identify critical spectral components for preservation. the core of our method, the iwdft, enables efficient and normalized updates to the compressed cache during autoregressive decoding, ensuring a more consistent treatment of token contributions over time. experimental results on multiple benchmarks demonstrate faedkv's ability to achieve significant cache compression with competitive, and often superior, performance compared to existing methods, particularly in preserving information uniformly across long contexts.