cs.DCSep 24, 2026
SaveWhen Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
Organizations: Harvard University
Abstract
Long-running LLM applications repeatedly send growing context, making prefix caching critical for reducing prefill cost. Yet prefix-cache behavior under agentic workloads remains poorly understood. We study production traces from two companies and evaluate 14 eviction algorithms across HBM-constrained and large memory-pool settings. Despite a large gap to Belady, sophisticated policies designed for traditional caches provide little benefit over LRU. The reason is structural: prefix reuse is dominated by the regular pacing of active sessions, making recency unusually predictive. Prefix caching nevertheless introduces new challenges, including heavy-tailed session footprints and highly variable miss costs as attention computation grows with sequence length. We introduce the compute-savings ratio and two offline oracles to quantify these effects. Our results show that effective prefix-cache management should retain recency as its foundation while selectively adding quick demotion for one-hit prefixes, compute-aware partial eviction for expensive misses, and capacity-dependent eviction granularity. We will release the traces and simulator to support future research.
Figures & tables
Figure 1 : Paper overview: We characterize five fundamental properties of production prefix-cache workloads (§ 4 ), derive their implications for cache management, and map them to our targeted design techniques (§ 5 ).
| FreeInference Trace | Chutes Trace | |
|---|---|---|
| Requests | 327.5 K | 515.8 K |
| in multi-turn sessions | 34.3% | 26.1% |
| Span | 7.0 d | 130.9 d |
| Tokens processed | 10.5 B | 9.7 B |
| Unique tokens | 0.63 B | 2.23 B |
| Request tokens, average | 32.0 K | 18.7 K |
Table 1 : LLM inference request traces from two organizations. Requests are capped at 256K tokens.
| Size | Blocks | Example setting |
| HBM, per replica: 24–120 GiB | ||
| 24 GiB | 16,384 | native-context floor |
| 48 GiB | 32,768 | 1 H200 at 0.8 memory fraction |
| 96 GiB | 65,536 | 1 B200, bf16 weights |
| DRAM/SSD pool, global: 0.25–12 TiB | ||
| 1 TiB | 699,051 | full node in Mooncake [ 51 ] |
Table 2 : Cache sizes we evaluate.
| Trace | Requests | Tokens | Span | Block size | Scope | Agentic |
| TraceLab [ 80 ] † | 357 K | 54.9 B | 253 d, scattered | none | — | ✓ |
| Mooncake, tool & agent [ 51 ] | 23.6 K | 0.20 B | 1 h | coarse (512 tokens) | global | ✓ |
| AgentX [ 53 ] | 98.8 K | 21.6 B | per session | intermediate (64 tokens) | per session | ✓ |
| Qwen Bailian [ 64 ] ∗ | 10.8–172.8 K | 0.05–0.25 B | 2 h | fine (16 tokens) | global | very little |
| FreeInference Trace (this work) | 327.5 K | 10.5 B | 7.0 d | fine (16 tokens) | global | ✓ |
| Chutes Trace (this work) | 515.8 K | 9.7 B | 130.9 d | fine (16 tokens) | global | ✓ |
Table 3 : Comparison of public LLM-serving traces with the two traces introduced in this work. Only FreeInference Trace and Chutes Trace combine fine-grained block identity scoped across sessions, agentic traffic, and a multi-day span.
Figure 2 : Block hit ratio on the two production traces for fourteen eviction algorithms and offline optimum (Belady). Across different memory capacities, none of the state-of-the-art algorithms improve over LRU.
| Class | Trace | Requests | Distinct items | Span | Description |
|---|---|---|---|---|---|
| Prefix cache | FreeInference Trace | 327.5 K | 39.6 M blocks | 7.0 d | One week of a public LLM inference service. |
| Web | Wikipedia 2019 text [ 12 ] | 207.6 M | 18.4 M objects | 21.0 d | Wikipedia’s CDN request log for article text. |
| Block | CloudPhysics w01 [ 63 , 12 ] | 215.8 M | 122.8 M objects | 6.3 d | Disk I/O of one VM volume from a production fleet. |
Table 4 : We compare three different caching workloads in this paper: LLM serving prefix cache, web cache (CDN), and block cache.
| Characteristic | Prefix cache | Web | Block |
|---|---|---|---|
| Lifetime (§ 4.1 ) | Minutes, bounded by the session | Days with a persistent hot core | Days without hot core |
| Reuse interval (§ 4.2 ) | Short, low variance | Long, high variance | Long, paced by periodic jobs |
| Frequency (§ 4.3 ) | Wide spread; tracks session progress | Zipfian; a few get most accesses | Few accesses; scans dominate |
| Miss penalty (§ 4.4 ) | Grows with block depth | One uniform fetch | One uniform fetch |
| Session footprint (§ 4.5 ) | Heavy-tailed per session | No session structure | No session structure |
Table 5 : Summary of the characteristics that separate the prefix-cache workload from the web and block workloads. Each characteristic carries the subsection that measures it.
Figure 3 : (a) Prefix-cache blocks are short-lived, with lifetimes up to 100 shorter than in traditional caches. (b) Sessions are short: P90 is 14 minutes, while the median is under 1 minute. (c) Working set similarity is high at very short intervals due to short reuse but rapidly falls to zero due to short lifetime .
Figure 4 : (a) Prefix-cache reuse intervals are short with low variance. (b) Request inter-interval time within a session is short.
Figure 5 : Frequency is not a good indicator for LLM prefix cache. (a) Reuse intervals are largely independent of block popularity in the LLM prefix cache. (b) Block lifetime increases with access frequency and shows a wide spectrum. (c) Frequency is a poor predictor of future reuse.
Figure 6 : (a) Prefix-cache blocks are reused more frequently than in web and storage block caches. (b) Requests per session show a wide spectrum.
Figure 7 : Measured TTFT against the number of tokens computed per request, over 10,000 FreeInference Trace requests replayed on vLLM [ 29 ] with Qwen3-Coder-30B [ 59 ] under LRU at a 48 GiB cache on a single NVIDIA H200. Color indicates the mean depth (position in the prompt) of the computed tokens. Similar token counts can incur substantially different TTFT.
Figure 8 : Depth-dependent recomputation cost on Qwen3-Coder-30B [ 59 ] , measured on NVIDIA H200. Both requests compute 8K tokens, but the second must attend to an additional 64K cached tokens, increasing computation and TTFT.
Figure 9 : Distribution of request sequence lengths in tokens, over all requests and over the requests that belong to multi-turn sessions. Long requests both occupy substantial HBM and create deep blocks with high recomputation costs. Dotted lines mark the two medians, 3,386 and 66,605 tokens.
Figure 10 : Per-session KV footprint of the prefix-cache trace.
Figure 11 : Block hit ratio of six eviction algorithms at the four capacities of Table 2 , on two of the four Qwen Bailian traces [ 64 ] and on AgentX, a replay of 393 Claude Code sessions [ 53 ] .
Figure 12 : Compute-savings ratio on FreeInference Trace under the Qwen3-Coder-30B [ 59 ] cost model. BeladyCompute tightly approximates the ILP optimum, whereas standard Belady falls short. Compute-aware eviction substantially improves compute savings, and partial-node eviction preserves these gains without degradation.
Figure 13 : End-to-end performance on H200 with 48 GiB cache replaying 10,000 requests from FreeInference Trace. TTFT (a) and throughput (b) were measured in separate runs. Partial-node compute-aware eviction yields substantial TTFT and throughput gains over LRU, whereas block-based eviction incurs severe degradation due to fragmentation.
Figure 14 : Block-level (solid) vs. session-level (hatched) eviction on the prefix-cache trace. While session-level eviction matches block-level performance at large capacities, it degrades under tight constraints.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 15 : Block hit ratio against cache size on the four Qwen Bailian traces, over the two cache-size regimes of § 3.1 . Figure 11 reports the corresponding comparison at four capacities.
Figure 16 : Block hit ratio against cache size on the two production traces of § 3.2 . Figure 2 reports the corresponding comparison at four capacities.
Figure 17 : Block hit ratio against cache size on AgentX. Sampled at 26 capacities over the same range as Figures 15 and 16 ; Figure 11 reports the corresponding comparison at four capacities.
| Trace | Requests | Block accesses |
|---|---|---|
| Qwen To-C | 43.1 K | 6.3 M |
| Qwen To-B | 172.8 K | 10.0 M |
| Qwen Coder | 43.0 K | 15.5 M |
| Qwen Thinking | 10.8 K | 3.2 M |
| FreeInference Trace | 327.5 K | 656.2 M |
| Chutes Trace | 515.8 K | 603.6 M |
Table 6 : Sizes of the four Qwen Bailian traces and the two production traces.
Figure 18 : Hit ratio against session concurrency at a fixed cache size, on the synthetic multi-turn trace, in the per-replica HBM regime (a) and the DRAM/SSD pool regime (b); the two panels share a axis. Every point replays the same set of requests.
Figure 19 : Compute-savings ratio on the prefix-cache trace under an idealized linear cost, where a block’s recompute cost is proportional to its position in the prompt. Same policies, colors and capacities as Figure 12 , which uses the measured cost model.
Figure 20 : Effect of partial-node eviction on recompute fragmentation at 24 GiB over the 327,548 requests of FreeInference Trace. Partial-node eviction leaves fewer holes per request (a), and those holes are longer (b).