WAKMan：工作负载感知的 KV 缓存管理器

# WAKMan: Workload Aware KVCache Manager
Source: [https://arxiv.org/html/2610.36355](https://arxiv.org/html/2610.36355)
###### Abstract

Prefix caching enables a Large Language Model \(LLM\) servers to reuse the Key\-Value \(KV\) states and accelerate prefill computation stage for requests that share a prefix with earlier prompts, thus reducing latency and serving cost\. With limited memory resource, 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 a mixture of any combination 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 strategy LRU provides 12% higher cache hits as compared to 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 even for any particular 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\.

††footnotetext:\*Equal contribution\. Author order was determined by a coin toss\. Work done during internship at Capital One\.
1Columbia University,vm2825@columbia\.edu
2University of Maryland, College Park,vlokegao@umd\.edu
3Capital One,\{sachinmathew\.varghese, wesley\.harris\}@capitalone\.com## 1Introduction

![Refer to caption](https://arxiv.org/html/2610.36355v1/marquee.png)Figure 1:Hit\-rate difference \(S3FIFO−\-LRU\) across 21 request mixes\. Purple: S3FIFO better\. Yellow: LRU better\. No single policy wins everywhere\.Serving Large Language Models \(LLMs\) efficiently at scale has become a prominent challenge in system design\. LLM inference process involves generating the key and value vectors of each prompt token based on its preceding context\. Requests that share a prompt prefix therefore produce identical KV states, and storing these can avoid unwanted recomputation\. Most LLM servers store this KV cache in the GPU memory so that future requests with a common prefix can reuse these KV blocks\. Since GPU memory is limited, cached blocks require eviction in order to store newer KV blocks\. KV blocks will have to be recomputed if a particular block is required immediately after it gets evicted thus increasing the latency and computation cost for that request\. Hence, selecting which KV blocks to evict is critical for extracting maximum performance from an LLM system, and the right strategy depends on how blocks are reused across requests\.

LLM serving traffic can be a mix of three types of requests: single\-turn, multi\-turn, and agentic \(Appendix[E](https://arxiv.org/html/2610.36355#A5)\)\. These differ in length of prefix they share and how quickly a shared prefix is requested again\. vLLM[Kwon et al\. \(2023\)](https://arxiv.org/html/2610.36355#bib.bib28)evicts blocks in Least Recently Used \(LRU\) order by default\. LRU strategy works well when shared prefixes return quickly, as in agentic sessions\. It fares sub\-optimally when many one\-time blocks, such as single\-turn payloads, push out blocks that will be reused later, such as fixed prompts and long conversation histories\. Scan\-resistant policies such as S3FIFO protect these blocks, but they can evict fast\-returning agentic blocks before their next use\. Figure[1](https://arxiv.org/html/2610.36355#S1.F1)shows the this effect across mixes of the three request types\. S3FIFO is better when single\-turn or multi\-turn requests dominate, while LRU is better when agentic requests dominate\. The better policy also changes when the mix is fixed and a workload parameter, such as the number of turns per conversation, changes \(Figure[3](https://arxiv.org/html/2610.36355#S3.F3)\)\. Since traffic also shifts over time, this makes selecting a policy upfront suboptimal\.

Recent systems improve on LRU strategy by making KV cache eviction aware of the request type\. UniCache\([Yang et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib15)\)and SAECache\([Fang et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib18)\)keep separate queues for agentic, chat, and single\-turn requests, and a study of Alibaba’s production traces models KV cache reuse by request type and turn number\([Wang et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib16)\)\. Other systems predict when a prefix will be reused, either with a trained model\([Fang et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib18)\)or with inter\-access time distributions fit on past traces\([Yang et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib15);[Wang et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib16);[Li et al\., 2026](https://arxiv.org/html/2610.36355#bib.bib22)\)\. These methods make two assumptions: the server knows each request’s type and turn, and reuse timing stays stable over time\. Neither holds in any large\-scale shared deployment serving multiple use cases\. As requests arrive, conversation or agent history is concatenated on the client side\. The server cannot recover a request’s type or turn due to data\-sharing and data\-privacy restrictions in most shared deployments\. The traffic mix also keeps shifting, so a distribution fit on past traces may no longer hold\. A policy for serving must therefore rely only on what the cache itself observes\.

We propose WAKMan, a workload\-aware KV cache manager that selects its eviction policy from live traffic \(Figure 1\)\. WAKMan runs shadow copies of LRU and S3FIFO alongside the server\. At fixed intervals, it replays the most recent trace on both and switches the server to the policy with the higher simulated hit rate\. WAKMan uses only the block hashes that vLLM already computes\. It needs no request types, no prompt content, and no offline training, and it does not change model outputs\. Unlike adaptive policies such as ARC[Megiddo and Modha \(2003\)](https://arxiv.org/html/2610.36355#bib.bib26)and LeCaR[Vietri et al\. \(2018\)](https://arxiv.org/html/2610.36355#bib.bib27), which adjust within a single cache on every request, WAKMan selects one complete policy per interval \(Section[2](https://arxiv.org/html/2610.36355#S2)\)\. This keeps the eviction path simple, and any policy that can be simulated can join the candidate pool\.

We evaluate WAKMan on 19 synthetic workloads with different mixes of single\-turn, multi\-turn, and agentic requests, served with Gemma on vLLM\. WAKMan improves the hit rate over LRU, the vLLM default, by 5 points on average\. To test whether a single candidate policy would suffice, we also run S3FIFO n\. S3FIFO is better than LRU on most workload mixes, but it falls well behind on agentic\-heavy mixes, where LRU is better\. WAKMan follows the policy that fits the current traffic, and it has the lowest gap between its cache hit rate and that of the ideal cache policy of the three policies\.

## 2Methodology

![Refer to caption](https://arxiv.org/html/2610.36355v1/method.png)Figure 2:Overview of WAKMan\.EveryTTminutes, the estimator replays recent block hashes through shadow LRU and S3FIFO policies, and the server switches to the policy with the higher hit rate\.Our method switches the eviction policy of vLLM[Kwon et al\. \(2023\)](https://arxiv.org/html/2610.36355#bib.bib28)between LRU and S3FIFO[Yang et al\. \(2023\)](https://arxiv.org/html/2610.36355#bib.bib25)at run time\. EveryTTminutes, it asks which of the two policies would have served the lastTTminutes of traffic better, and uses that policy for the nextTTminutes \(Figure[2](https://arxiv.org/html/2610.36355#S2.F2)\)\. We initially seed vLLM with LRU\. During each window ofTTminutes, we log the arrival time and the block hashes of every request\. We also track the average size of the free block queue over the window\.

Estimator\.At the end of each window, the estimator replays the logged requests in arrival order through two shadow policies, one for LRU and one for S3FIFO\. The estimator mimics the eviction of vLLM as closely as possible without a GPU or a model runner, using only the block hashes from vLLM\. Both shadow policies get a cache capacity equal to the average size of the free block queue, since this is roughly the space that the eviction policy manages\. Below, we describe the logic of LRU & S3FIFO used in both the vLLM implementation and the estimator\.

Shadow LRU policy\.The shadow LRU policy maintains a single queue of block hashes ordered by recency\. A hit is counted when an incoming block hash is already present in the queue\. On a miss, the block is inserted and the least recently used block is evicted if the cache is full\. The hit rateh​i​tL​R​Uhit\_\{LRU\}is the number of hits divided by the total number of block hashes seen in the lastTTminutes\.

Shadow S3FIFO policy\.The shadow S3FIFO policy keeps small, main, and ghost queues\. Unlike the original, the small and main queues resize freely, with their total equal to the available GPU blocks\. New blocks enter the small queue and move to the main queue if hit\. Otherwise, they go to the ghost queue, and returning ghost blocks enter the main queue directly\. The FIFO main queue reinserts blocks with a nonzero 2\-bit hit counter rather than evicting them\.h​i​tS​3​F​I​F​Ohit\_\{S3FIFO\}is computed as for LRU\.

Switching criteria\.EveryTTminutes, both shadow policies are replayed on the trace from the lastTTminutes\. Ifh​i​tS​3​F​I​F​O\>h​i​tL​R​Uhit\_\{S3FIFO\}\>hit\_\{LRU\}111h​i​tL​R​Uhit\_\{LRU\}is hit rate from running shadow LRU policy, the server uses S3FIFO for the nextTTminutes\. Otherwise, it uses LRU\. When the server switches from S3FIFO to LRU, the ghost queue entries are discarded\.

## 3Experiments

### 3\.1Workload Data

We use only synthetic workloads\. Synthetic traces let us set the properties of each request type and change one property at a time\. Each trace is one hour long, with an average arrival rate of 1\.5 requests per second\.222We tuned this rate to put the cache under pressure\. At lower rates, the cache rarely evicts\. At higher rates, blocks are evicted before any reuse, so the eviction policy does not matter\.We sample each prompt, input, and output length from a normal or log\-normal distribution with a set mean or median\. Appendix[F](https://arxiv.org/html/2610.36355#A6)gives the full configuration\.

Single\-turn requests\.Single\-turn requests draw their fixed prompts from a catalog of 100 services, with prompt lengths from roughly 300 to 8K tokens\. We model the skewed popularity from Section[E](https://arxiv.org/html/2610.36355#A5)with a Zipf–Mandelbrot law, so the request rate of a service decreases with its popularity rank\. We set roughly 15% of requests have no fixed prompt\.

Multi\-turn requests\.We model both the number of turns per session and the inter\-turn time with log\-normal distributions, with medians of three turns and 60 seconds\.

Agentic requests\.We model the number of turns per session and the inter\-turn time with log\-normal distributions\. A session has 5 to 15 turns, with a median of 7\. The inter\-turn time has a median of 6 seconds and a cap of 300 seconds\. Most turns add a short tool result, but 15% add a long context read of about 3K tokens\.

Heterogeneous sweep\.We generate 20 workloads that vary only the mix of single\-turn, multi\-turn, and agentic sessions, from pure types to equal thirds, with all other parameters fixed\. We write a mix as S/M/A, the percentage of each type\.

### 3\.2Setup

We servegoogle/gemma\-4\-26B\-A4Bin bf16 on vLLM with tensor parallelism across four NVIDIA RTX PRO 6000 Blackwell GPUs \(96 GB each\), with GPU memory utilization 0\.5 and a block size of 16 tokens\. LRU, S3FIFO, and WAKMan run inside vLLM as Python implementations\. WAKMan starts with LRU and decides everyT=15T=15minutes\. AIPerf replays each trace at its exact timestamps\. We report the prefix\-cache hit rate, the fraction of prompt tokens read from the KV cache\. The ideal hit rate uses an infinite cache and bounds any policy\. A policy’s regret on a workload is the best hit rate among all policies minus its own\.

### 3\.3Results

Figure 3:The best static policy changes within a fixed request mix\. \(a, b\) The 33/33/33 mix as one parameter grows\. \(c\) Variants of the 0/50/50 mix, each with one parameter changed\. The gray bar spans LRU and S3FIFO, and the label gives the better static policy and its margin in points\.Table 1:Prefix\-cache hit rate \(%\) on the 20 workload mixes\. Bold shows the best policy in each row\. Ideal is the hit rate with an infinite cache\.Table[1](https://arxiv.org/html/2610.36355#S3.T1)gives the hit rates on the 20 mixes\. No static policy is the best on all mixes\. Between the two static policies, LRU wins on 8 mixes and S3FIFO wins on 12\. Each static policy also has a large loss on some mixes\. LRU loses up to 22\.4% of cache hits, and S3FIFO loses up to 11\.7% of the same\.

Agentic workloads favor LRU\.Agentic turns arrive quickly, so the next turn of a session usually finds its history at the recent end of the cache\. Thus, recency is a good signal for reuse, making LRU the better policy\. S3FIFO puts each new block in its small queue first and evicts agentic blocks from it before the next turn arrives\.

Single\-turn workloads favor S3FIFO\.Single\-turn reuse depends on frequency\. The fixed prompts of popular services get many hits, but the payloads get no hits\. S3FIFO keeps the hot fixed prompts in its main queue and removes each payload quickly from the small queue\. Thus, S3FIFO protects the fixed prompts from scan pollution by the payloads, making its hit rate close to ideal\.

Multi\-turn workloads favor S3FIFO\.In a multi\-turn workload, many other requests arrive during the long gap between two turns\. These requests push the conversation history to the old end of the LRU queue, and LRU evicts it\. But each turn reads the full history again, so the blocks of earlier turns get more hits as the conversation continues\. S3FIFO moves these blocks to its main queue and keeps them across the gap\.

The dynamic policy is the most robust\.The dynamic policy has the lowest mean and maximum regret of the three policies\. When LRU and S3FIFO differ by more than one point, the dynamic policy recovers a median of 84% of the difference\.The largest regret is on the pure multi\-turn mix \(0/100/0\) where the dynamic policy suffers due to its initialization with LRU\. The dynamic policy starts with LRU and makes its first switch only after 15 minutes, a quarter of each one\-hour trace\. On longer traces, this startup cost shrinks\.

### 3\.4Ablations

The main sweep shows that the best policy depends on the request mix\. The ablations aim to seek answers to two questions\. First, does the best policy also change when the mix stays fixed and one workload parameter changes? Second, if it changes, does the dynamic policy adapt?

We use the balanced 33/33/33 mix and change either the turns per multi\-turn session or the single\-turn input length\. We also change single parameters of the 0/50/50 mix\.

The mix alone does not determine the best policy\.Figure[3](https://arxiv.org/html/2610.36355#S3.F3)shows that a single parameter, such as number of turns in multi\-turn requests, can flip the better static policy\. On 33/33/33, LRU wins with 2 turns per session, but S3FIFO wins by 15\.4 points with 8 turns\. Single\-turn input length has the same effect, favoring LRU at 128 tokens and S3FIFO at 8K tokens\. On 0/50/50, either policy can win by up to 10 points depending on the parameter\. Since these parameters vary with users and applications, an operator cannot fix one policy in advance\.

The dynamic policy adapts\.The dynamic policy uses neither the mix nor the workload parameters\. On every point in Figure[3](https://arxiv.org/html/2610.36355#S3.F3), it never falls more than 0\.5 points below the worse static policy\. Where LRU is better, the dynamic policy matches LRU\. Where S3FIFO is better, it moves toward S3FIFO\.

## 4Conclusion

We studied KV cache eviction in LLM serving under heterogeneous workloads\. vLLM’s default LRU policy is not the best for all workloads, since the better policy changes with the request mix and with single workload parameters\. WAKMan selects the better policy at run time by replaying recent traffic, and it has the lowest mean regret of the three policies\.

## Limitations

We use only LRU and S3FIFO\([Yang et al\., 2023](https://arxiv.org/html/2610.36355#bib.bib25)\)as candidate policies\. Any policy that a simulator can replay, such as ARC\([Megiddo and Modha, 2003](https://arxiv.org/html/2610.36355#bib.bib26)\), can join the pool and add headroom where both candidates are far from the ideal hit rate\. Our goal was not to find the best eviction policy, but to show that trace replay can help in selecting a better policy at run time\.

Determining the exact or exploring the need for a dynamically changing time interval T to provide the maximum possible cache hit rates needs further analysis\.

## References

- Changet al\.\(2024\)C\. Chang, W\. Lin, C\. Lin, C\. Chen, Y\. Hu, P\. Wang, N\. Huang, L\. Ceze, M\. S\. Abdelfattah, and K\. WuPalu: compressing kv\-cache with low\-rank projection\.External Links:2407\.21118,[Link](https://arxiv.org/abs/2407.21118)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Changet al\.\(2026\)C\. Chang, W\. Lin, C\. Lin, H\. Chiang, Y\. Akhauri, X\. Dai, H\. Jiang, Y\. Li, L\. Ceze, K\. Wu, and M\. S\. AbdelfattahXKV: cross\-layer kv\-cache compression via aligned singular vector extraction\.External Links:2503\.18893,[Link](https://arxiv.org/abs/2503.18893)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Fanget al\.\(2026\)S\. Fang, Z\. Li, W\. Wu, J\. Ji, Q\. Liu, and R\. PuNot all tokens are worth caching: learning semantic\-aware eviction for llm prefix caches\.External Links:2605\.18825,[Link](https://arxiv.org/abs/2605.18825)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1),[§1](https://arxiv.org/html/2610.36355#S1.p3.1)\.
- Fenget al\.\(2025\)S\. Feng, Y\. Liu, H\. Li, X\. Chen, S\. Shen, K\. Du, Z\. Gu, R\. Zhang, Y\. Huang, Y\. Cheng, J\. Yao, Q\. Zhang, G\. Ananthanarayanan, and J\. JiangEVICPRESS: joint kv\-cache compression and eviction for efficient llm serving\.External Links:2512\.14946,[Link](https://arxiv.org/abs/2512.14946)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Kimet al\.\(2025a\)J\. Kim, J\. Kim, S\. Kwon, J\. W\. Lee, S\. Yun, and H\. O\. SongKVzip: query\-agnostic kv cache compression with context reconstruction\.External Links:2505\.23416,[Link](https://arxiv.org/abs/2505.23416)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Kimet al\.\(2025b\)M\. Kim, S\. Hong, R\. Ko, S\. Choi, H\. Lee, J\. Kim, J\. Kim, and J\. ParkOaken: fast and efficient llm serving with online\-offline hybrid kv cache quantization\.InProceedings of the 52nd Annual International Symposium on Computer Architecture,SIGARCH ’25,pp\. 482–497\.External Links:[Link](http://dx.doi.org/10.1145/3695053.3731019),[Document](https://dx.doi.org/10.1145/3695053.3731019)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Kwonet al\.\(2023\)W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. Gonzalez, H\. Zhang, and I\. StoicaEfficient memory management for large language model serving with pagedattention\.InProceedings of the 29th symposium on operating systems principles,pp\. 611–626\.Cited by:[Appendix B](https://arxiv.org/html/2610.36355#A2.p1.1),[§1](https://arxiv.org/html/2610.36355#S1.p2.1),[§2](https://arxiv.org/html/2610.36355#S2.p1.1)\.
- Liet al\.\(2026\)H\. Li, R\. He, Q\. Mang, Q\. Zhang, H\. Mao, X\. Chen, H\. Zhou, H\. Zhang, A\. Cheung, J\. Gonzalez, and I\. StoicaContinuum: efficient and robust multi\-turn llm agent scheduling with kv cache time\-to\-live\.External Links:2511\.02230,[Link](https://arxiv.org/abs/2511.02230)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1),[§1](https://arxiv.org/html/2610.36355#S1.p3.1)\.
- Liet al\.\(2025\)X\. Li, Z\. Xing, Y\. Li, L\. Qu, H\. Zhen, W\. Liu, Y\. Yao, S\. J\. Pan, and M\. YuanKVTuner: sensitivity\-aware layer\-wise mixed\-precision kv cache quantization for efficient and nearly lossless llm inference\.External Links:2502\.04420,[Link](https://arxiv.org/abs/2502.04420)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Linet al\.\(2026\)X\. Lin, J\. Wang, O\. Kondrateva, Y\. Shi, B\. Li, and G\. L\. ZhangCompressKV: semantic\-retrieval\-guided kv\-cache compression for resource\-efficient long\-context llm inference\.External Links:2606\.24467,[Link](https://arxiv.org/abs/2606.24467)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Liuet al\.\(2026a\)Y\. Liu, M\. Yu, and J\. YangWhen fancy eviction fails: rethinking cache replacement for llm prefix reuse\.External Links:2609\.28870,[Link](https://arxiv.org/abs/2609.28870)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Liuet al\.\(2026b\)Y\. Liu, J\. Ji, L\. An, R\. Jain, G\. Polatkan, S\. Zhu, and S\. ChangPractical online kv cache compaction for llm agents: an empirical study\.External Links:2608\.00902,[Link](https://arxiv.org/abs/2608.00902)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Megiddo and Modha \(2003\)N\. Megiddo and D\. S\. ModhaARC: a Self\-Tuning, low overhead replacement cache\.In2nd USENIX Conference on File and Storage Technologies \(FAST 03\),San Francisco, CA\.External Links:[Link](https://www.usenix.org/conference/fast-03/arc-self-tuning-low-overhead-replacement-cache)Cited by:[§1](https://arxiv.org/html/2610.36355#S1.p4.1),[Limitations](https://arxiv.org/html/2610.36355#Sx1.p1.1)\.
- Panet al\.\(2024\)R\. Pan, Z\. Wang, Z\. Jia, C\. Karakus, L\. Zancato, T\. Dao, R\. Netravali, and Y\. WangMarconi: prefix caching for the era of hybrid llms\.arXiv preprint arXiv:2411\.19379\.Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Panet al\.\(2025\)Z\. Pan, A\. Patel, Z\. Hu, Y\. Shen, Y\. Guan, W\. Li, L\. Qin, Y\. Wang, and Y\. DingKVFlow: efficient prefix caching for accelerating llm\-based multi\-agent workflows\.External Links:2507\.07400,[Link](https://arxiv.org/abs/2507.07400)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Panet al\.\(2026\)Z\. Pan, C\. Wu, Z\. Hu, X\. Qiang, Z\. Yu, and Y\. DingRR\-evict: fine\-grained prefix cache eviction beyond lru for agentic llm serving\.External Links:2609\.32278,[Link](https://arxiv.org/abs/2609.32278)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Shenet al\.\(2026\)Y\. Shen, M\. Madhyastha, R\. Underwood, B\. Nicolae, and R\. BurnsRecency/frequency adaptive kv caching for large language model serving\.External Links:2606\.21238,[Link](https://arxiv.org/abs/2606.21238)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Staniszewski and Łańcucki \(2026\)K\. Staniszewski and A\. ŁańcuckiKV cache transform coding for compact storage in llm inference\.External Links:2511\.01815,[Link](https://arxiv.org/abs/2511.01815)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Vietriet al\.\(2018\)G\. Vietri, L\. V\. Rodriguez, W\. A\. Martinez, S\. Lyons, J\. Liu, R\. Rangaswami, M\. Zhao, and G\. NarasimhanDriving cache replacement with ML\-based LeCaR\.In10th USENIX Workshop on Hot Topics in Storage and File Systems \(HotStorage 18\),Cited by:[§1](https://arxiv.org/html/2610.36355#S1.p4.1)\.
- Wanget al\.\(2026\)J\. Wang, J\. Han, X\. Wei, S\. Shen, D\. Zhang, C\. Fang, R\. Chen, W\. Yu, and H\. ChenKVCache cache in the wild: characterizing and optimizing kvcache cache at a large cloud provider\.External Links:2506\.02634,[Link](https://arxiv.org/abs/2506.02634)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1),[§1](https://arxiv.org/html/2610.36355#S1.p3.1)\.
- Xianget al\.\(2025\)X\. Xiang, R\. Joshi, Y\. Liu, J\. Yao, C\. Zhao, J\. Jiang, Y\. Zhou, E\. Kohler, and M\. YuShadowServe: interference\-free kv cache fetching for distributed prefix caching\.External Links:2509\.16857,[Link](https://arxiv.org/abs/2509.16857)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Xieet al\.\(2026\)B\. Xie, Z\. Wang, M\. Tanaka, and Z\. ZhengPEEK: predictive queue\-informed kv cache management for llm serving\.External Links:2607\.02525,[Link](https://arxiv.org/abs/2607.02525)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Yanget al\.\(2025\)D\. Yang, A\. Li, K\. Li, and W\. LloydLearned prefix caching for efficient llm inference\.InAdvances in Neural Information Processing Systems,D\. Belgrave, C\. Zhang, H\. Lin, R\. Pascanu, P\. Koniusz, M\. Ghassemi, and N\. Chen \(Eds\.\),Vol\.38, Main Conference,pp\. 45770–45792\.External Links:[Document](https://dx.doi.org/10.52202/085713-1526),[Link](https://proceedings.neurips.cc/paper_files/paper/2025/file/414f642a1ea9350006669774cba9bcd4-Paper-Conference.pdf)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Yanget al\.\(2023\)J\. Yang, Y\. Zhang, Z\. Qiu, Y\. Yue, and R\. VinayakFIFO queues are all you need for cache eviction\.InProceedings of the 29th Symposium on Operating Systems Principles,SOSP ’23,New York, NY, USA,pp\. 130–149\.External Links:ISBN 9798400702297,[Link](https://doi.org/10.1145/3600006.3613147),[Document](https://dx.doi.org/10.1145/3600006.3613147)Cited by:[§2](https://arxiv.org/html/2610.36355#S2.p1.1),[Limitations](https://arxiv.org/html/2610.36355#Sx1.p1.1)\.
- Yanget al\.\(2026\)W\. Yang, Y\. Ma, M\. Xie, X\. Zheng, and S\. LiuUniCache: task\- and type\-aware kv cache compression for unified multimodal models\.External Links:2609\.32831,[Link](https://arxiv.org/abs/2609.32831)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1),[§1](https://arxiv.org/html/2610.36355#S1.p3.1)\.
- Zhenget al\.\(2026\)H\. Zheng, F\. Fu, J\. Wu, B\. Yuan, Y\. Zhang, H\. Wang, Y\. Zhu, X\. Yan, and J\. JiangEfficient serving for dynamic agent workflows with prediction\-based kv\-cache management\.External Links:2605\.06472,[Link](https://arxiv.org/abs/2605.06472)Cited by:[§D\.2](https://arxiv.org/html/2610.36355#A4.SS2.p1.1)\.
- Zuoet al\.\(2026\)F\. Zuo, Z\. Zhou, H\. Cong, X\. Xi, and H\. F\. LeungRateQuant: optimal mixed\-precision kv cache quantization via rate\-distortion theory\.External Links:2605\.06675,[Link](https://arxiv.org/abs/2605.06675)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.
- Zweigeret al\.\(2026\)A\. Zweiger, X\. Fu, H\. Guo, and Y\. KimFast kv compaction via attention matching\.External Links:2602\.16284,[Link](https://arxiv.org/abs/2602.16284)Cited by:[§D\.1](https://arxiv.org/html/2610.36355#A4.SS1.p1.1)\.

## Appendix APotential risks

WAKMan changes only which KV blocks stay in GPU memory\. It does not change model outputs, so it adds no risk to the content, safety, or fairness of generated text\. We see three operational risks\. First, a switch can be wrong for an entire interval\. WAKMan chooses the policy for the nextTTminutes based on the traffic of the previousTTminutes\. If the traffic changes sharply right after a decision, the server keeps a mismatched policy until the next decision, and requests in that interval see a lower hit rate, higher latency, and higher cost\. Second, prefix caching can leak information through timing\. A request whose prefix is already cached skips prefill and receives its first token sooner\. A user who shares the server can send a guessed prefix and measure this delay to learn whether another user recently sent the same prefix, such as a particular system prompt or document\. WAKMan does not create this channel, which exists for any prefix cache\. However, it changes which prefixes stay cached and for how long\. For example, S3FIFO keeps popular prefixes longer than LRU, which can keep the signal observable for longer\. WAKMan should therefore be deployed with the isolation that operators already use for prefix caching, such as separate caches for each user or tenant\. Third, switching has its own cost\. The estimator replays the traffic of every interval, and each switch changes how the cached blocks are ordered for eviction\. For some traffic patterns, this overhead can exceed the benefit of the extra cache hits\. This can happen when the two policies have similar hit rates, so a switch gains little, or when traffic alternates quickly between recency\-heavy and scan\-heavy phases, so one switch is soon followed by another\. In such cases, a static policy may be cheaper overall\.

## Appendix BLicense of artifacts

We use vLLM[Kwon et al\. \(2023\)](https://arxiv.org/html/2610.36355#bib.bib28), the Gemma 4 model \(google/gemma\-4\-26B\-A4B\), and AIPerf\. All three are released under the Apache License 2\.0, which permits research and commercial use, modification, and redistribution\. Our use of each artifact is consistent with its license and intended use\. All workloads in this paper are synthetic and generated by our own trace generator, so they contain no personal or user data\.

## Appendix CUse of AI Assistants

We used Claude, an AI assistant, to help with writing\. It helped restructure and shorten drafts of the introduction and methodology, suggest phrasing for figure captions, and draft parts of the Limitations section\. All research ideas, system design, implementation, experiments, and results are our own\. The authors reviewed and edited all AI\-assisted text and take full responsibility for the content of the paper\.

## Appendix DBackground

KV cache optimizations fall into three families\. Offloading moves key\-value state across the GPU, CPU, and disk hierarchy\. Compression shrinks the cache through quantization, low\-rank approximation, or token pruning \. Exact eviction keeps full\-precision blocks on the GPU and only chooses which to drop under memory pressure\. Our work is an exact\-eviction method\.

### D\.1KV Cache Compression Strategies

Quantization stores keys and values with fewer bits per entry, through rotation\-based vector quantization[Zuo et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib2), layer\-wise and head\-wise mixed precision[Li et al\. \(2025\)](https://arxiv.org/html/2610.36355#bib.bib1);[Zuo et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib2), or hardware co\-design with offline\-profiled outlier thresholds[Kim et al\. \(2025b\)](https://arxiv.org/html/2610.36355#bib.bib3)\. Transform coding and low\-rank methods remove redundancy in the feature dimension\. Palu[Chang et al\. \(2024\)](https://arxiv.org/html/2610.36355#bib.bib4)and xKV[Chang et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib5)use within\-layer and cross\-layer low\-rank factorization, KVTC[Staniszewski and Łańcucki \(2026\)](https://arxiv.org/html/2610.36355#bib.bib6)adds PCA, adaptive quantization, and entropy coding for stored caches, and ShadowServe[Xiang et al\. \(2025\)](https://arxiv.org/html/2610.36355#bib.bib7)offloads decompression to a SmartNIC\. Latent compaction shortens the sequence by fitting a smaller cache instead of keeping a subset of the original\. Attention Matching[Zweiger et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib8)fits compact keys and values to match full\-cache attention, and Liu et al\.[Liu et al\. \(2026b\)](https://arxiv.org/html/2610.36355#bib.bib9)adapt it to online agents\. Token selection keeps the KV entries of important tokens and evicts the rest\. CompressKV[Lin et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib10)scores tokens with semantic retrieval heads, and KVzip[Kim et al\. \(2025a\)](https://arxiv.org/html/2610.36355#bib.bib11)scores tokens by how well they reconstruct the context\. These methods compress the KV state of a single request and mostly fix their choices offline\. Our work is complementary: it decides which cached blocks to keep across requests and adapts the policy online\. Unlike the compression methods above, our method does not alter the cached KV blocks\. It keeps each block at full precision and instead decides which blocks to retain and which to evict\. Our method therefore belongs to the family of eviction\-based techniques, and it can be combined with compression for added benefits to cache hit rates\.

### D\.2KV Cache Eviction Strategies

Eviction\-based methods keep cached KV blocks intact and decide which blocks to retain when GPU memory runs out\. Production engines such as vLLM and SGLang default to LRU[Xie et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib12)\. Recency and frequency policies refine this default\. Liu et al\.[Liu et al\. \(2026a\)](https://arxiv.org/html/2610.36355#bib.bib13)evaluate 14 policies on production traces and find that recency is unusually predictive, so sophisticated policies gain little over LRU\. ARC\-based caching[Shen et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib14)adapts the split between recency and frequency queues using ghost caches, and UniCache[Yang et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib15)captures multiple reuse patterns and balances cache allocation across tasks in heterogeneous workloads\. Workload\-aware and learned policies predict reuse directly\. Wang et al\.[Wang et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib16)use per\-workload reuse probability distributions, LPC[Yang et al\. \(2025\)](https://arxiv.org/html/2610.36355#bib.bib17)predicts which conversations will continue, and SAECache[Fang et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib18)learns the reuse value of each token type online\. Cost\-aware policies weigh the price of a miss\. Marconi[Pan et al\. \(2024\)](https://arxiv.org/html/2610.36355#bib.bib19)uses FLOP efficiency for hybrid models, and EvicPress[Feng et al\. \(2025\)](https://arxiv.org/html/2610.36355#bib.bib20)jointly decides compression and eviction across storage tiers\. Agent\-aware policies exploit program structure\. KVFlow[Pan et al\. \(2025\)](https://arxiv.org/html/2610.36355#bib.bib21)ranks agents by steps to execution, Continuum[Li et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib22)pins KV blocks during tool calls with a time\-to\-live, PBKV[Zheng et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib23)predicts agent invocations in dynamic workflows, and RR\-Evict[Pan et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib24)spreads reclamation across idle agents\. PEEK[Xie et al\. \(2026\)](https://arxiv.org/html/2610.36355#bib.bib12)uses the waiting queue to protect prefixes that pending requests will need\. Most of these methods commit to a single policy or tune one policy online\. In contrast, our method selects between whole policies at run time based on their simulated hit rate on recent traces\.

## Appendix ETypes of Workloads

A production LLM service receives requests from many applications through one endpoint\. We group these requests into three types: single\-turn, multi\-turn, and agentic\. The three types differ in two properties that control the reuse of KV cache blocks, namely the shared prefix and the inter\-turn time\.

Single\-turn workloads\.A single\-turn workload consists of independent requests, such as API calls from services or sandboxes, each answered in one turn\. Each request combines a fixed prompt, a template reused across many requests, with a unique payload\. Popularity is skewed: a few fixed prompts receive most requests\. Requests with the same fixed prompt therefore share it as a prefix, but no payload is ever reused\.

Multi\-turn workloads\.A multi\-turn workload consists of conversations between users and the LLM, as in a chatbot\. Each conversation starts with a context specific to its user, such as a system prompt combined with user memory or reference documents\. Each turn appends the previous response and a new message to the history, so the prefix grows and the KV cache can supply most of the inpu\. But the inter\-turn time is long: the user reads, thinks, and types, which takes seconds to minutes\.

Agentic workloads\.An agentic workload consists of automated workflows in which the LLM takes a sequence of steps\. Each step appends the result of the previous step, such as a tool output, to the workflow history, so the prefix grows as in a conversation\. Agentic sessions run more turns than conversations, and with no human in the loop, the inter\-turn time is short\.333Long tool calls or code execution can lengthen the gap between agent steps\. Our heterogeneous workloads cover long gaps through their multi\-turn fraction\.

Heterogeneous workloads\.A shared deployment may receive all three types at once, with their requests interleaved\. The proportions also change over time, for example when chat traffic peaks during work hours and batch jobs run overnight\. The mix determines which KV cache eviction policy performs best, and in this paper we analyze how this choice changes across proportions\.

## Appendix FWorkload Configuration

This configuration generates the main workloads in Section[3\.1](https://arxiv.org/html/2610.36355#S3.SS1)\. For each of the 20 mixes, we change only thefracvalue of each profile\. Thefracvalues give the fraction of new sessions of each type\. In eachsystem\_promptsandmixturelist, the generator draws a length from a log\-normal distribution with the given median and log\-space spread \(sigma\)\. Thecataloggives the number of single\-turn services and the parameters of their Zipf–Mandelbrot popularity,p⁡\(r\)∝\(r\+q\)−αp\(r\)\\propto\(r\+q\)^\{\-\\alpha\}\.

```
seed: 0
duration_s: 3600
arrival_rate: 1.5
profiles:
  single:
    frac: 1.0
    share_head: true
    no_system_prompt_frac: 0.15
    catalog: {n_services: 100, alpha: 1.3, q: 5}
    system_prompts:
    - {weight: 0.1, median: 8000, sigma: 0.05}
    - {weight: 0.6, median: 2500, sigma: 0.2}
    - {weight: 0.2, median: 1000, sigma: 0.2}
    - {weight: 0.1, median: 300,  sigma: 0.25}
    input:  {mean: 2048, std: 128, skew: right}
    output: {mean: 512,  std: 256, skew: left}
  multi_turn:
    frac: 0.0
    share_head: false
    min_turns: 2
    turns: {median: 3, sigma: 0.6}
    inter_turn_time: {median: 60.0, sigma: 0.5}
    system_prompts:
    - {weight: 0.2, median: 1250, sigma: 0.2}
    - {weight: 0.5, median: 500,  sigma: 0.2}
    - {weight: 0.3, median: 150,  sigma: 0.25}
    input:  {mean: 1024, std: 128}
    output: {mean: 768,  std: 64}
  agentic:
    frac: 0.0
    share_head: false
    min_turns: 5
    max_turns: 15
    turns: {median: 7, sigma: 1.7}
    inter_turn_time: {median: 6, sigma: 2.5}
    max_delay_s: 300
    system_prompts:
    - {weight: 0.4, median: 1024, sigma: 0.2}
    - {weight: 0.4, median: 2048, sigma: 0.2}
    input:
      mixture:
      - {weight: 0.85, median: 600,  sigma: 0.5}
      - {weight: 0.15, median: 3000, sigma: 0.2}
    output: {median: 126, sigma: 1.4}
```