Authors: Kazi Hasan Ibn Arif, JinYi Yoon, Dimitrios S. Nikolopoulos, Hans Vandierendonck, Deepu John, Bo Ji
Organizations: Virginia Tech Blacksburg, VA, USA · Inha University Incheon, South Korea · Queen’s University Belfast Belfast, UK · University College Dublin Dublin, Ireland
Modern LLM serving systems use prefix caching to accelerate multi-turn conversational workloads. They cache the key-value states of previous conversation prefixes and reuse them when subsequent requests share the same prefix, to avoid redundant prefill computation and reduce serving latency. However, achieving a high cache hit rate remains challenging because cache reuse depends on whether a conversation continues and how soon the next turn arrives. Our analysis of real workloads shows that user intent is a useful signal for this behavior, as different intents exhibit different continuation probabilities and inter-turn delays. Based on this key insight, we propose Intent-Aware Caching (IAC), an online eviction policy that classifies requests by intent, learns lightweight reuse statistics from recent serving logs and leverages these statistics to guide an oracle-inspired eviction strategy. Extensive evaluation on real workloads (WildChat and ShareChat) shows that IAC reaches a 34.6% cache hit rate. This substantially outperforms both the previous learning-based approach (18.8%) and traditional methods such as least recently used (LRU, 12.2%), while reducing average serving latency by up to 46.1%.
Figures & tables
Figure 1: (a) In a typical multi-turn conversation, each new request includes previous user queries and model responses as a prefix; caching this prefix reduces redundant prefill computation and lowers TTFT. (b) The input context grows with the number of turns, increasing serving cost. (c) Both conventional and ML-based policies achieve much lower cache hit rates than oracle policies.
Figure 2: (a) Insight 1 : Mean number of turns varies across intent categories. (b) Insight 2 : Reuse delays vary across intent categories and turns. The delay CDF, clipped at 600 s, motivates using (intent,turn) as the workload category.
Figure 3: Insight 3 : Cache reuse patterns (i.e., #turns and delay) vary over the course of a representative day.
Figure 4: Overview of IAC. The Intent Classifier assigns an intent category to each newly arrived request. The Statistics Estimation module tracks the batch of recent logs and periodically updates cache reuse statistics. During serving, the Cache Eviction Policy (see Eq. ( 1 )) computes a priority score for the leaf nodes (e.g., C and D in the figure) and evicts the node with the lowest score.
Figure 5: Offline training pipeline of the intent classifier. Step 1 : intent discovery with TnT-LLM [ 41 ] and few-shot LLM labeling. Step 2 : training an MLP head on a frozen text embedder.
Figure 6: Cache hit rate of IAC vs. the baselines. ( a ) On WildChat and ShareChat, two real workloads with original timestamps, IAC achieves the highest cache hit rate among online policies at every cache capacity. ( b ) On ShareGPT with synthetic Poisson arrival rates λ (new conversations per sec.), IAC consistently outperforms the online baselines even as higher λ increases cache contention.
Figure 7: ( a ) IAC reduces TTFT across various models by improving cache hit rate. ( b ) IAC maintains lower average latency as request rate increases, showing higher throughput under load.
Figure 8: Ablation and sensitivity of IAC. ( a ) Intent-turn grouping with the recency, reuse, and size signals performs best. ( b ) Finer intent categories lower classifier accuracy but raise cache hit rate by preserving reuse differences that coarser groups merge. ( c ) Cache hit rate degrades gracefully as intent labels are replaced with random ones, since the turn, recency, and size signals remain intact.
Figure 9: Reuse-window estimators.
Model (size)
Acc.
Lat.
ModernBERT (0.2B+3.7M)
62%
33 ms
E5-Small (0.1B+2.9M)
70%
13 ms
E5-Base (0.2B+3.7M)
71%
16 ms
E5-Large (0.5B+4.2M)
72%
20 ms
E5-Large-Inst (0.5B+4.2M)
75%
20 ms
Table 1: Embedding backbone models.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Timestamp
#Samples
Avg. length
Avg. turns
#Languages
ShareChat [ 20 ]
✓
142,808
1250
4.62
101
WildChat [ 19 ]
✓
1,039,785
736
2.54
68
LMSys-Chat [ 43 ]
✗
1,000,000
284
2.02
65
ShareGPT [ 42 ]
✗
94,145
442
3.51
41
Appendix
Table 2: Summary of the datasets used in this study. We use ShareChat and WildChat as the main workloads because they provide original user timestamps. LMSys-Chat and ShareGPT are used to evaluate different request arrival patterns, while all four datasets are used to train the intent classifier.
Figure 10: Inter-turn delay distributions on WildChat-1M [ 19 ] . Progressively finer grouping by workload signals exposes cache-reuse structure that is hidden by a single global distribution, motivating our design. Although turn index alone provides limited separation for delay modeling, it remains useful for estimating reuse probability.
Batch size
p50 (ms)
p95 (ms)
Per-request (ms)
Throughput (req/s)
Peak GPU mem. (GB)
1
19.4
20.6
19.4
52
2.29
10
19.4
19.8
1.94
515
2.29
100
19.6
19.9
0.20
5,112
2.29
Appendix
Table 3: Latency, throughput, and memory of the E5-Large-Inst intent classifier with batching.
Replay window
LRU
IAC (ours)
Gain
Update time (CPU)
10K–20K
13.7
20.4
+49%
1.32 s
20K–30K
9.8
17.9
+83%
1.41 s
30K–40K
14.2
23.5
+66%
1.37 s
40K–50K
11.6
19.7
+70%
1.53 s
Appendix
Table 4: Causal rolling-window evaluation on WildChat (140K token capacity, N=10 K). The statistics are re-estimated from past folds only. Cache hit rate in %.
Capacity ( ×103 tokens)
Full-Horizon
IAC (ours)
80
21.5
23.7
110
27.4
29.8
140
31.0
34.6
170
35.3
38.5
Appendix
Table 5: Cache hit rate (%) on ShareChat with the binary median-based recency test (IAC) and with the full delay distribution (Full-Horizon).
Figure 11: WA [ 15 ] trace.
Figure 12: Extended evaluation including WA on ShareChat. ( a ) Cache hit rate across cache capacities. ( b ) TTFT latency across serving settings.
Figure 13: Cache hit rate on LMSys-Chat under different arrival rates λ (150K tokens).
Table 19
Policy
Mean
p50
p90
LRU
6.51
4.29
17.80
LPC
4.91
3.67
11.84
IAC (ours)
3.43
3.03
6.77
Oracle
3.21
2.07
5.06
Appendix
Table 8: Mean and tail TTFT (s) on Llama-3-70B (4 × A100) at 10 requests/s.
Policy
p10
p25
p50
p75
p90
Overall
LRU
0.0
0.0
0.6
13.3
75.4
17.1
LPC
0.0
0.0
0.7
12.8
74.2
22.4
IAC (ours)
0.0
0.0
0.3
14.3
86.8
38.5
Oracle
0.0
0.0
0.1
7.7
69.9
46.2
Appendix
Table 9: Percentiles of the per-request cache hit ratio (%) at 16 requests/s and 170K token capacity. Overall is the token-weighted cache hit rate used in the rest of the paper.
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.
Semantic caching lowers the cost of serving large language models (LLMs) by reusing stored responses for similar requests. In multi-turn conversations, whether a cached response is acceptable depends on both conversations' histories, which embedding similarity of requests and histories predicts poorly (AUC 0.62--0.74 on five workloads). We therefore learn the reuse risk, the probability that a cached response is unacceptable, from judge feedback, and choose a budgeted set of conversation states to cache by weighing the generation cost a reuse avoids against a price for unacceptable reuse. We propose CUCB-SC-MT, which learns a cache from logged conversations with a suboptimality guarantee, and CLCB-LS-MT, which learns online and has O~(N) regret over N requests when conversation states recur. On math-tutoring (SocraTeach) and movie-ticketing (Taskmaster-3) conversations, both achieve lower loss than prior semantic caching approaches: ContextCache, multi-turn variants of ElastiCache and vCache, and single-turn semantic caching at every cache budget. With 1,000 cache entries, CLCB-LS-MT avoids 35--41% of the generation cost through acceptable reuses, against at most 22--25% for the baselines, and lowers estimated serving latency by 19--35%.
Baran Atalar, Selly Beyene, Xutong Liu +1
Carnegie Mellon University, Pittsburgh, PA, USA · University of Washington Tacoma, Tacoma, WA, USA
Prefix caching is a key optimization in Large Language Model (LLM) serving, reusing attention Key-Value (KV) states across requests with shared prompt prefixes to reduce expensive prefill computation. However, its benefit depends critically on the eviction policy as GPU memory is scarce, and existing policies such as LRU largely treat cached blocks uniformly. This view ignores a fundamental property of LLM prompts: not all tokens are equally worth caching. We show that different token types within a prompt, including system prompts, user queries, tool outputs, model responses, and chain-of-thought reasoning, exhibit up to 756x variation in reuse rates, yet no existing eviction policy exploits this signal. In this paper, we present SAECache (Semantic-Adaptive Eviction for prefix caches), a semantic-adaptive prefix cache eviction policy that addresses this gap through three innovations: (1) a multi-queue architecture that routes KV blocks to task-specific queues with tailored priority metrics, capturing both session reuse in multi-turn requests and structural reuse in templated single-turn requests; (2) a semantic-aware token weighting mechanism that learns the reuse value of different token types online through eviction feedback; and (3) a fully adaptive online learning schema for all parameter updates, including log-normal timing parameters, position decay power, queue weights, and meta-parameters, which eliminates manual tuning and enables automatic adaptation to deployment-specific workload characteristics. Through extensive evaluation across heterogeneous workloads, we demonstrate that SAECache achieves 1.4x-2.7x TTFT improvement over production-style baselines, while fixed-parameter alternatives can degrade by up to 2.7x under workload mismatch -- a failure mode our adaptive approach avoids entirely.
Shaoke Fang, Ziang Li, Wenfei Wu +3
Peking University · FirestAI · Tsinghua University +2