Prefix caching enables Large Language Model (LLM) servers to reuse the Key-Value (KV) states and accelerate prefill computation for requests that share a prefix with earlier prompts, thus reducing latency and serving cost. With limited memory, the KV cache eviction policy becomes a decisive factor in determining the overall benefits of prefix caching. Production traffic may have single-turn, multi-turn, agentic, or any mixture of these request types. Our findings indicate that agentic steps return within seconds and favor recency, while popular prompts and long conversations return after many other requests and favor frequency. Across 20 mixes, no single policy is always best: vLLM's default LRU provides 12% higher cache hits than the frequency-oriented S3FIFO on agentic-heavy mixes but trails it by up to 22% elsewhere, and even a single workload parameter can flip the winner for a fixed mix. We present WAKMan, a workload-aware KV cache manager that picks its eviction policy from live traffic without knowing request types or reading prompts. It improves hit rate over LRU by 5 percentage points on average, with the lowest mean and worst-case optimality gap of all policies.
📄 Arxiv Preprint: WAKMan: Workload Aware KVCache Manager
Every T = 15 min, the estimator replays the last window of block hashes (already computed by vLLM) through shadow LRU and S3FIFO policies, and the server switches to whichever had the higher hit rate. No request types, prompt content, or offline training are needed.
Prefix-cache hit rate (%) on the 20 workload mixes (S/M/A = % single-turn / multi-turn / agentic). Bold = best policy per row; Ideal = infinite cache.
- No static policy wins everywhere: LRU is best on 8 agentic-heavy mixes; S3FIFO on 12 single-/multi-turn-heavy mixes.
- Each static policy has a large worst case: LRU loses up to 22.4 points, S3FIFO up to 11.7.
- WAKMan is the most robust: lowest mean and max regret, recovering a median 84% of the LRU–S3FIFO gap. Its worst case (0/100/0) comes from starting on LRU for the first 15 min of a 1-hour trace.
Even with the request mix fixed, a single workload parameter (turns per conversation, input length) flips the better static policy by up to ~15 points. WAKMan uses neither the mix nor these parameters, yet tracks LRU where LRU wins and moves toward S3FIFO where S3FIFO wins.
analysis/—paper_figures.ipynbregenerates the paper's result plots fromexperiments/; figures are saved inanalysis/figures/.configs/— the golden workload configs.data/— generated workload traces + the generation how-to.experiments/— bare-minimum run artifacts, organized by algorithm (LRU/,S3FIFO/, …).runner/— the launch folder: run perf tests viarun_experiments.sh(with JSON batch specs inexperiment_groups/andbase_perf_test_configs/).vllm/- custom vLLM eviction policies implementation.
- Suhas Kumar Morisetty - Columbia University
- Vaibhavi Lokegaonkar - University of Maryland, College Park
- Sachin Mathew Varghese - Capital One
- Wesley Harris - Capital One


