EvolKV: Evolutionary KV Cache Compression for LLM Inference

Bin Yu, Yekun Chai2025 · DOI

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.

The EvolKV framework utilizes a bottom-up, group-wise evolutionary optimization process to determine layer-specific KV cache budgets.

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.

Comparison of EvolKV's discovered layer-wise budgets against standard heuristics like uniform (StreamingLLM/SnapKV) and pyramidal (PyramidKV) strategies.

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

BibTeX
@misc{yu2025evolkv,
  author = {Bin Yu and Yekun Chai},
  title = {{EvolKV: Evolutionary KV Cache Compression for LLM Inference}},
  year = {2025},
  doi = {10.18653/v1/2025.findings-emnlp.88},
}

Loading related content...

Figure