Introduction
As Large Language Models (LLMs) are increasingly deployed for long-context tasks, the memory requirements of the Key-Value (KV) cache have become a critical bottleneck. The KV cache stores previous token states to accelerate generation, but its size grows linearly with sequence length. Combined with the quadratic complexity of self-attention, this makes processing long contexts prohibitively slow and memory-intensive.
Existing solutions typically rely on static heuristics, such as uniform allocation or pyramidal strategies, which assume a fixed importance for each layer. However, these "one-size-fits-all" approaches ignore the specialized functional roles of different transformer layers. We introduce EvolKV, an adaptive framework that uses evolutionary search to discover optimal, model-specific KV cache distributions, achieving superior performance while using as little as 1.5% of the original memory budget.
Methodology: Evolutionary Optimization
EvolKV treats KV cache allocation as a black-box optimization problem. Rather than manually designing heuristics, the framework employs an evolutionary algorithm to search for the most effective cache budget for each layer.
Key Components
- Evolutionary Search (CMA-ES): The framework uses the Covariance Matrix Adaptation Evolution Strategy to iteratively refine cache budgets based on performance feedback from downstream tasks.
- Layer Grouping: To manage the high-dimensional search space of modern LLMs (e.g., 32 layers in Mistral-7B), contiguous layers are grouped into optimization units.
- Multi-objective Fitness Function: Candidate compression schemes are evaluated by a fitness score that balances task performance (e.g., F1 score or accuracy) against cache efficiency, favoring configurations that maximize performance within a target budget.
- Plug-and-Play Compatibility: EvolKV is designed for frozen, off-the-shelf LLMs and requires no fine-tuning or architectural modifications.
Experimental Setup
The framework was evaluated across 11 diverse tasks using major benchmarks including LongBench (long-context understanding), GSM8K (mathematical reasoning), Needle-in-a-Haystack (fact retrieval), and RULER. Experiments were primarily conducted on Mistral-7B-Instruct and Llama-3-8B-Instruct.
Insights: The Non-Uniform Importance of Layers
The most significant finding from our evolutionary search is that optimal cache distributions are neither uniform nor pyramidal. EvolKV consistently discovered that certain layers—particularly those in the middle of the model—act as computational bottlenecks and require significantly larger budgets than others to maintain performance.
Furthermore, distributions optimized for tight constraints (e.g., a budget of 128 tokens) generalize well when scaled to larger budgets. This suggests that EvolKV captures stable, task-aligned importance patterns inherent to the model's architecture. In some instances, such as code completion, EvolKV actually outperformed the full, uncompressed KV cache, suggesting that strategic pruning can act as a form of noise reduction.
Key Results
- State-of-the-Art Performance: EvolKV consistently outperformed strong baselines like SnapKV, StreamingLLM, and PyramidKV across nearly all tasks and budget settings.
- Retrieval and Reasoning: On the Needle-in-a-Haystack test, EvolKV showed a 13% improvement over the best baseline. On the GSM8K benchmark, it surpassed heuristic baselines by up to 7 percentage points in low-budget scenarios.
- Extreme Efficiency: The framework preserves approximately 95.7% of full-model performance on reasoning tasks while using only a tiny fraction of the original cache memory.
Limitations and Future Work
While EvolKV is highly effective at the layer level, future research could explore even finer granularity by allocating budgets at the individual attention-head level. Additionally, while the initial evolutionary search requires several evaluation rounds, the resulting budgets are highly reusable. Future work will also investigate the impact of different tokenization schemes on cache compression efficiency.
Summary updated