WAKMan: Workload Aware KVCache Manager

1 Introduction

• Across request mixes, S3FIFO is better when single-turn or multi-turn requests dominate, while LRU is better when agentic requests dominate.A workload parameter can also flip the better static policy even when the mix is fixed.Source: Figure 1 · p. 1, §1 · p. 1
• Evicted KV blocks may need recomputation when requested again, increasing latency and computation cost.Selecting which blocks to evict is therefore critical to LLM system performance.Source: §1 · p. 1
• Request-type-aware and reuse-prediction methods assume the server knows request type and turn, or that reuse timing remains stable over time.Shared deployments may hide request types, while traffic mixes shift; WAKMan instead uses cache-observed traffic.Source: §1 · p. 2
• WAKMan improves hit rate over LRU by 5 points on average and has the lowest gap to the ideal cache policy among the three policies.It selects the policy that fits current traffic without needing request types or prompt content.Source: §1 · p. 2

2 Methodology

• Every T minutes, WAKMan replays the previous interval’s requests through shadow LRU and S3FIFO policies and selects the higher-hit-rate policy for the next interval.It starts with LRU; if switching from S3FIFO to LRU, it discards ghost-queue entries.Source: §2 · pp. 2–3, Figure 2 · p. 3
• The estimator logs request arrival times and block hashes, and sets shadow-cache capacity to the average free-block queue size over the interval.It mimics eviction without a GPU or model runner, using block hashes computed by vLLM.Source: §2 · p. 2
• Shadow LRU tracks block hashes by recency, while shadow S3FIFO uses small, main, and ghost queues and reinserts main-queue blocks with nonzero hit counters.Each policy’s hit rate is hits divided by the block hashes seen during the interval.Source: §2 · p. 2

3.1 Workload Data

• Synthetic traces comprise 20 workloads spanning single-turn, multi-turn, and agentic sessions, from pure types to equal thirds; the heterogeneous sweep varies only their mix, holding all other parameters fixed.Each trace lasts one hour, averaging 1.5 requests per second.Source: §3.1 · p. 3

3.3 Results

• LRU wins 8 mixes and S3FIFO 12; their losses reach 22.4% and 11.7%, respectively, while the dynamic policy has the lowest mean and maximum regret.Table 1 reports hit rates for the 20 mixes; the dynamic policy also recovers a median 84% of the difference when the static policies differ by more than one point.Source: Table 1 · p. 3, §3.3 · pp. 3–4

3.2 Setup

• The experiment measures prefix-cache hit rate—the fraction of prompt tokens read from KV cache—on vLLM serving Gemma-4-26B-A4B in bf16.The setup uses four RTX PRO 6000 Blackwell GPUs and a 15-minute WAKMan decision interval.Source: §3.2 · p. 3

3.4 Ablations

• At 33/33/33, eight turns give S3FIFO a 15.4-point lead; 128-token inputs favor LRU, 8K favor S3FIFO, and dynamic stays within 0.5 points of the worse static policy.The 0/50/50 variants also show either static policy winning by up to 10 points, depending on the parameter.Source: Figure 3 · p. 4, §3.4 · p. 4

3.3 Results

• Agentic reuse favors recency, whereas single-turn prompt popularity and multi-turn history reuse favor S3FIFO’s frequency-oriented retention.Agentic turns return quickly; single-turn payloads are removed while popular fixed prompts are kept, and S3FIFO preserves multi-turn history across long gaps.Source: §3.3 · p. 4
• When LRU and S3FIFO differ by more than one point, the dynamic policy recovers a median 84% of their difference, but its largest regret occurs on pure multi-turn traces.It starts with LRU and makes its first switch after 15 minutes, a quarter of each one-hour trace; the startup cost shrinks on longer traces.Source: §3.3 · p. 4

• The study examines KV-cache eviction in LLM serving under heterogeneous workloads.Source: §4 · p. 4
• WAKMan selects an eviction policy at runtime by replaying recent traffic, and has the lowest mean regret among the three policies.Source: §4 · p. 4
• The better eviction policy changes with the request mix and even with individual workload parameters.Source: §4 · p. 4

• WAKMan uses only LRU and S3FIFO as candidate policies.Source: Limitations · p. 5
• Replayable policies such as ARC could join the pool where both current candidates are far from ideal hit rate.Source: Limitations · p. 5
• Further analysis is needed to determine whether dynamically changing interval T can maximize cache hit rates.Source: Limitations · p. 5

• WAKMan changes which KV blocks stay in GPU memory and does not change model outputs, avoiding added content, safety, or fairness risk to generated text.Source: A Potential risks · p. 6
• A sharp traffic shift after a decision can leave WAKMan using a mismatched policy until the next decision, lowering hit rate and raising latency and cost.Source: A Potential risks · p. 6
• Replay and cache reordering overhead can exceed extra-hit benefits when policies have similar hit rates or traffic alternates quickly between phases.Source: A Potential risks · p. 6

• The work uses vLLM, the Gemma 4 model, and AIPerf.Source: B License of artifacts · p. 6
• All three artifacts are released under Apache License 2.0, permitting research and commercial use, modification, and redistribution.Source: B License of artifacts · p. 6
• All workloads are synthetic and generated by the authors, so they contain no personal or user data.Source: B License of artifacts · p. 6

C Use of AI Assistants

• Claude helped restructure and shorten introduction and methodology drafts, suggest figure-caption phrasing, and draft parts of the Limitations section.Source: C Use of AI Assistants · p. 6
• The authors state that all research ideas, system design, implementation, experiments, and results are their own.Source: C Use of AI Assistants · p. 6
• The authors reviewed and edited AI-assisted text and take full responsibility for the paper's content.Source: C Use of AI Assistants · p. 6

D Background

• Exact eviction keeps full-precision KV blocks on the GPU and chooses which blocks to drop when memory is constrained.Source: D Background · p. 7

D.1 KV Cache Compression Strategies

• Compression methods alter a request's KV state, whereas this work retains full-precision blocks and decides online which cached blocks to keep across requests.The paper describes its eviction approach as complementary to compression and potentially combinable with it.Source: §D.1 · p. 7

D.2 KV Cache Eviction Strategies

• Existing eviction strategies include recency-, frequency-, workload-, cost-, and agent-aware approaches, while this method selects between whole policies using recent simulated hit rates.Source: §D.2 · p. 7

E Types of Workloads

• Single-turn requests combine a fixed, frequently reused prompt with a unique payload that is not reused.Source: E Types of Workloads · pp. 7–8
• Multi-turn conversations extend a user-specific prefix each turn, but users may take seconds to minutes before requesting the next turn.Source: E Types of Workloads · p. 8
• Agentic workflows also extend their prefixes across steps, typically with more turns and shorter inter-turn times because no human is in the loop.Source: E Types of Workloads · p. 8
• A shared deployment can interleave all three request types, and changing proportions can alter which eviction policy performs best.Source: E Types of Workloads · p. 8

F Workload Configuration

• Each of the 20 mixes changes only the fraction of new sessions assigned to each workload profile.Source: F Workload Configuration · p. 8
• The generator samples lengths from log-normal distributions using profile-specific medians and log-space spreads, with single-turn popularity parameterized by a Zipf–Mandelbrot catalog.Source: F Workload Configuration · p. 8
• Long tool calls or code execution can lengthen agent-step gaps, and the heterogeneous workloads represent long gaps through their multi-turn fraction.Source: F Workload Configuration · p. 8