Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Yang Shen; Meghana Madhyastha; Robert Underwood; Bogdan Nicolae; Randal Burns

cs.DCJun 19, 2026

Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Authors: Yang Shen, Meghana Madhyastha, Robert Underwood, Bogdan Nicolae, Randal Burns

Organizations: Department of Computer Science, Johns Hopkins University, Baltimore, USA

Abstract

Key-value (KV) caching is a powerful technique for accelerating large language model inference and generation. Inference workloads are large and diverse, which makes them difficult to cache effectively. Existing cache management strategies adopt the least-recently-used policy for evicting cache blocks. However, LRU leads to multiple unrelated workloads flushing each other's caches. To address this, we integrate adaptive caching that dynamically allocates cache space between recently and frequently occurring KV blocks. Evaluations show that it improves the KV cache hit rate by up to 10.8% and reduces time to first token by up to 12.6% over naive vLLM on synthetic document question answering workloads, and 2.1% and 2.0% respectively on real-world conversation workloads. The method generalizes well to batch inference and demonstrates clear interpretability while effectively accommodating diverse workloads.

Explore similar work

Learning to Evict from Key-Value Cache
Feb 10, 2026Luca Moschella, Laura Manduchi, Ozan SenerKey-Value Cache Eviction Key-Value Cache
Multi-Segment Attention: Enabling Efficient KV-Cache Management for Faster Large Language Model Serving
Jun 1, 2026Chunan Shi, Yilei Chen, Yilin Chen +2Cache LLM Inference Efficiency
MetaKV: Adaptive KV Cache Compression for Constrained LLM Inference
Sep 7, 2026Michael Wang, Keith Li, Roozbeh BostandoostKey-Value Cache Compression LLM Inference Efficiency

Feb 10, 2026 · cs.CLJ/K move · Enter open · S save

Learning to Evict from Key-Value Cache

Luca Moschella, Laura Manduchi, Ozan Sener

Apple

The growing size of Large Language Models (LLMs) makes efficient inference challenging, primarily due to the memory demands of the autoregressive Key-Value (KV) cache. Existing eviction or compression methods reduce cost but rely on heuristics, such as recency or past attention scores, which serve only as indirect proxies for a token's future utility and introduce computational overhead. We reframe KV cache eviction as a reinforcement learning (RL) problem: learning to rank tokens by their predicted usefulness for future decoding. To this end, we introduce KV Policy (KVP), a framework of lightweight per-head RL agents trained on pre-computed generation traces using only key and value vectors. Each agent learns a specialized eviction policy guided by a holistic reward, derived from future utility, that evaluates the quality of the ranking across all cache budgets, requiring no modifications to the underlying LLM or additional inference. Evaluated across two model families on the long-context benchmark RULER (up to 128K tokens) and the multi-turn dialogue benchmark OASST2-4k, KVP significantly outperforms strong baselines. Zero-shot tests on standard downstream tasks (BoolQ, LongBench passage retrieval, GovReport) further show that KVP generalizes beyond its training distribution and to considerably longer sequence lengths. These results demonstrate that learning to predict future token utility is a powerful and scalable paradigm for adaptive KV cache management.

Key-Value Cache Eviction Key-Value Cache Key-Value Cache LLM Inference Efficiency

Open paper Ask about it PDF

Abstract

Explore similar work

Learning to Evict from Key-Value Cache

Multi-Segment Attention: Enabling Efficient KV-Cache Management for Faster Large Language Model Serving

MetaKV: Adaptive KV Cache Compression for Constrained LLM Inference