WAKMan Picks a KV-Cache Eviction Policy and Beats LRU by 5 Percentage Points

Prefix caching in LLM servers saves money and time, but only as long as the needed prefix stays in memory. Memory is limited, so the outcome depends on the KV-cache eviction policy. Researchers Suhas Kumar Morisetty and three co-authors, who worked on this during an internship at Capital One, tested popular strategies on 20 workload mixes. The conclusion is simple: there is no single best policy. They propose WAKMan, a manager that picks an eviction policy based on live traffic. On average, it improves hit rate by 5 percentage points over LRU.

Why agents and chatbots want different things from the cache

Prefix caching lets a server reuse Key-Value states for requests that share a prefix with earlier prompts. This speeds up the prefill stage and lowers latency and serving cost. But real production traffic is mixed: single requests, multi-turn conversations, agent chains, or any blend of them.

These request types have different "return times" to a prefix. Agent steps come back within a few seconds, so they need a cache that remembers the recent past. Popular prompts and long conversations come back after many other requests, so access frequency matters more for them. The first pattern suits LRU well; the second suits frequency-based policies.

Where LRU wins and where it loses

vLLM uses LRU by default. The authors compared it with the frequency-oriented S3FIFO and found a pattern that breaks the habit of picking one policy for good:

• on mixes dominated by agentic requests, LRU gets 12% more cache hits than S3FIFO;
• on the other mixes, LRU trails S3FIFO by up to 22%;
• even a single workload parameter can change the winner within the same mix.

The last point is the most unpleasant for engineers. You cannot measure traffic once, pick a policy, and forget about it. It takes only one parameter shifting for yesterday's leader to end up at the back of the pack.

What WAKMan does

WAKMan chooses an eviction policy based on live traffic. It does not need to know which requests are arriving, and it does not need to read the prompts themselves. For production, this is an important condition: request content is often sensitive, especially in an organization like a financial company, where the internship took place. The manager only needs to observe how traffic behaves.

WAKMan's results:

• an average hit rate gain of 5 percentage points over LRU;
• the lowest average gap to the optimal policy among all compared approaches;
• the lowest worst-case gap to the optimum among all compared approaches;
• tested on 20 mixes of single-turn, multi-turn, and agentic workloads.

The second and third points matter more than the average gain. They speak to predictability: WAKMan does not necessarily win on every individual mix, but it misses the best option less often and by a smaller margin. For an inference operator, that is worth more than one impressive win on a specific benchmark.

What teams with a growing share of agents should do

Agentic scenarios are quickly taking up a larger part of traffic. The cache profile changes with them: short "hot" returns become more frequent, while popular prompts and long conversations remain in the background. If the eviction policy is hard-coded into the server and never revisited, part of the benefit of prefix caching is lost. It is lost in the form of repeated prefill, that is, wasted GPU-seconds and added latency.

Practical takeaways for those running their own inference on vLLM:

• measure hit rate separately by workload type, not just as a server-wide average;
• do not treat LRU as an unconditionally safe choice: on some mixes it loses to S3FIFO by up to 22%;
• re-check the policy whenever the share of agentic traffic changes;
• judge solutions by the worst case, not just by the average gain.

WAKMan shows that policy selection can be automated without access to request content. For large deployments, a 5-percentage-point hit rate gain means less recomputation on every prefix and steadier latency under mixed traffic.