WAKMan: Workload Aware KVCache Manager

On the same vLLM server, which eviction policy the prefix cache should use depends on what traffic is arriving right now. Agent requests come back within seconds carrying the same history, so the most recently used blocks are the ones to keep, and the default LRU fits. The popular system prompts of single-turn requests and the histories of multi-turn chats come back much later, after a flood of one-off content, and only S3FIFO (an eviction policy that protects blocks used repeatedly) keeps them. Across 20 request mixes, LRU wins 8 and S3FIFO wins 12, and changing a single parameter within one mix can flip the winner. The authors' fix is simple: every 15 minutes, replay the traffic just seen on two simulated caches and use whichever had the higher hit rate for the next window. On average it gains 5 points of hit rate over LRU alone, and its worst-case gap to the best policy is the smallest of the three.

Teams running LLM serving or inference platforms should spend ten minutes on it, because the conclusion is directly usable: there is no universally best eviction policy, and the cheapest robust option is to let live traffic choose. It uses only the block hashes vLLM already computes, needs no request types and reads no prompts, which suits deployments where many products share one service and request metadata is unavailable. The evidence is thin, though: all traffic is synthetic, each trace lasts one hour, and compared with simply switching to S3FIFO the average gain is about half a point. The core idea in one sentence: simulate both policies on recent traffic offline and let the simulation decide the live policy for the next window.

What problem is it solving?

Prefix caching lets requests that share an opening skip repeated prefill. GPU memory is limited, so when blocks fill up some must be evicted, and a wrong eviction means recomputation, raising latency and cost. vLLM evicts with LRU by default.

Take a cache that holds only 3 blocks and two kinds of traffic (illustrative):

S3FIFO is an eviction policy built to resist "scan pollution": new blocks first enter a small probation queue and are promoted to the main queue only if they are used again there; blocks not reused during probation are evicted, leaving only a "ghost" record, and if one comes back soon it goes straight into the main queue. It protects blocks that are reused repeatedly, at the cost of evicting blocks that have just arrived and are about to be used a second time.

So each policy has its losing cases. In the paper, the median gap between two steps of an agent session is 6 seconds, between two chat turns 60 seconds, and a single-turn system prompt waits for the next call to the same service. The first favours recency, the other two frequency. Production traffic usually mixes all three, and the mix shifts over time.

Why not manage request types separately?

Existing systems do exactly that: separate queues for agent, chat and single-turn requests, or fitting from past traces how soon each type returns. The authors point out two assumptions: the server knows each request's type and turn number, and the timing patterns are stable. In shared multi-product deployments neither holds. Conversation history is assembled on the client and arrives as one long token sequence, and privacy restrictions stop the server from reading prompts to infer the type. The traffic mix keeps drifting, so a distribution fitted last year may not hold today.

That leaves one option: decide using only what the cache itself can see.

How WAKMan works: two shadow caches, compared every 15 minutes

WAKMan (Workload Aware KVCache Manager, the authors' name for the system) sits beside vLLM:

Why size the simulators by the average free queue length? In vLLM, blocks in use by running requests cannot be evicted; the policy only manages blocks in the free queue, so the simulators should have that capacity, not the whole GPU memory.

How does it avoid reading prompts? For prefix caching vLLM already hashes every 16-token block, and identical prefixes give identical hashes. The simulators replay requests in arrival order. For LRU, a block hash already in the queue counts as a hit; otherwise it is inserted, evicting the least recently used block if the cache is full. Both simulated hit rates divide the number of block-hash hits by the total number of block hashes seen, rather than measuring each request's continuously reusable prefix. No GPU or model is needed.

A worked example (illustrative): in the last 15 minutes 10,000 block hashes appeared; the LRU simulator hit 5,200 and the S3FIFO simulator 5,600, hit rates of 52% and 56%, so the next 15 minutes use S3FIFO.

Compared with classic adaptive caches such as ARC, the difference is granularity. ARC tunes the split between recency and frequency inside one cache on every access; WAKMan swaps the whole policy once per window. That keeps the eviction path simple, and any policy that can be written as a simulator can join the candidate pool.

Experiments: no single policy always wins

The experiments serve a 26B-parameter Gemma 4 MoE model on 4 RTX PRO 6000 GPUs, with GPU memory utilisation deliberately set to 0.5, one-hour traces and an average of 1.5 requests per second. The rate was tuned: lower and the cache rarely evicts, higher and blocks are evicted before any reuse, and in both cases the policy does not matter. The 20 workloads vary only the shares of the three request types, written as single-turn/multi-turn/agentic percentages. The metric is the prefix-cache hit rate counted over prompt tokens.

Representative rows (Ideal is the hit rate with an infinite cache, an upper bound for any policy):

The gap is, on the same mix, the best hit rate of the three minus the policy's own. On pure agent traffic LRU beats S3FIFO by about 12 points, because the agent's next step returns within seconds and S3FIFO's probation queue cannot hold it; on traffic heavy in chat and single-turn requests S3FIFO leads by a wide margin, because it keeps popular prompts and long histories. This shows that picking the wrong policy costs double-digit hit rate.

WAKMan has the lowest mean and maximum gap. Look at the mixes where the two static policies differ by more than 1 point: dividing what WAKMan gains over the worse one by the gap between better and worse gives a median of 84%. That is, when the two differ by 10 points, it typically recovers about 8.

It loses most on pure multi-turn traffic: 15.0 against 26.0 for S3FIFO. The reason is that it starts with LRU and makes its first switch only after 15 minutes, and each trace is one hour, so a quarter of the time is spent on the wrong policy. The authors expect this startup cost to shrink on longer traffic.

Changing one parameter can flip the winner

The ablation asks whether the best policy still changes when the mix is fixed. On traffic split evenly among the three types, LRU wins with 2 turns per chat session, while S3FIFO wins by 15.4 points with 8 turns. The reason is that more turns mean early history is reread more often, so the frequency signal is stronger. Single-turn input length has the same effect: LRU is better at 128 tokens and S3FIFO at 8K tokens, because long one-off payloads flush the cache harder.

The figure also shows WAKMan's ceiling: at 8 turns its hit rate is about 41%, well below S3FIFO's roughly 49% and only better than LRU. The authors describe it as moving toward S3FIFO rather than matching it, again because the first 15 minutes are fixed to LRU.

Limitations as I see them

First, the evidence is synthetic. The 20 mixes and the ablations all come from the authors' own generator, one hour each. In real traffic the speed at which request types shift and the distribution of popular prompts may differ, and these are exactly what decide whether switching pays off.

Second, the gain over simply using S3FIFO is small. Mean gap is 2.04 against 2.53, about half a point; on single-turn-heavy traffic WAKMan is about 3 points below S3FIFO (46.5 against 49.5). If your traffic has little agent share, static S3FIFO may be enough.

Third, switching has a cost that the paper does not quantify. The authors admit in the appendix that when the two policies have similar hit rates, or when traffic alternates quickly between modes, replay and switching overhead may exceed the benefit, and how to set the window T is not yet studied.

How a serving team could try it

Step one: replay offline first. Log a day of production block hashes, run them through LRU and S3FIFO simulators, and compare hit rates in 15-minute slices to see whether the two often trade places. If one wins all day, just switch to it.

Step two: if they often trade places, deploy WAKMan and shorten the window, for example starting at 5 minutes, to check whether startup and switching losses can be reduced.

Step three: judge success by time to first token and prefill compute; hit rate is only an intermediate metric.

Recommendation and search teams running agent-style retrieval and single-turn generation on the same LLM service are where the method's premise is most likely to hold.

Verdict

In one sentence: the prefix cache's eviction policy should follow the traffic, and replaying recent traffic helps the server choose a policy for the next window. If traffic then changes abruptly, that policy may no longer fit, and the server waits until the next decision to choose again.