PaperlayerView exact revision on arXiv

Source-linked AI summary

When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse

Yiyu Liu, Minlan Yu, Juncheng Yang

arXiv:2609.28870v1cs.DCcs.LG

TL;DR

Prefix-cache behavior under agentic workloads is poorly understood, even as growing contexts make avoiding repeated prefill increasingly important. Across production traces and memory settings, the paper finds little benefit over LRU from sophisticated policies and recommends adding other signals selectively.

  • Problem

    Prefix-cache eviction patterns, particularly under agentic workloads, remain largely unexplored despite the cost of recomputing growing contexts.

    Source: §1 · p. 1

  • Method

    The paper studies production traces, evaluates eviction policies across memory regimes, and introduces a compute-savings ratio and offline bounds for miss costs.

    Source: §1 · p. 2, §5.2 · p. 10

  • Results

    Most advanced eviction algorithms offer little improvement over LRU, while Belady’s optimum shows substantial remaining headroom.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Retain recency as the foundation, adding quick demotion, compute-aware eviction, and capacity-dependent granularity selectively.

    Source: §1 · p. 2

    The effects of compute-aware eviction vary with attention designs, which place deployments at different points between constant and depth-dependent recomputation cost.

    Source: §6.1 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

Prefix caching avoids redundant prefill for growing LLM contexts, but production prefix-cache behavior—especially for agentic workloads—has been poorly understood. The paper finds that session-driven reuse makes recency robust, while non-uniform miss costs and skewed session footprints call for selective additions to LRU.

1 Introduction

  • Production prefix-cache behavior, particularly for agentic workloads, has been largely unexplored despite the importance of reducing recomputation as contexts grow.Long-running sessions reuse prefixes, while Transformer prefill cost grows rapidly with sequence length.Source: §1 · p. 1
  • Most advanced eviction algorithms offer little improvement over LRU, frequency-based policies often perform worse, and Belady’s optimum leaves substantial headroom.The paper asks what makes a good eviction policy for LLM prefix caches and finds traditional cache signals do not close the gap to the offline optimum.Source: §1 · p. 1
  • Successive turns within a session concentrate reuse into short, session-bounded lifetimes, making recency predictive while frequency largely reflects session age.This workload structure explains LRU’s robustness and the poor performance of frequency-based policies.Source: §1 · p. 1
  • Miss costs vary with prompt depth, and a small number of large sessions consume disproportionate cache capacity while contributing many hits.As a result, equal hit ratios can still imply different prefill costs and time-to-first-token.Source: §1 · pp. 1–2
  • The paper recommends retaining recency and adding quick demotion, compute-aware eviction, or capacity-dependent granularity only where workload conditions warrant them.It also introduces a compute-savings ratio and offline bounds, and plans to release production traces and a simulator.Source: §1 · p. 2

2 Background

LLM inference uses a KV cache to avoid recomputation, while prefix caching reuses exact shared histories across requests. The background distinguishes session-driven prefix reuse from traditional web and storage cache workloads.

2.1 LLM Inference

  • Each Transformer layer applies projections, attention, and an MLP to process token representations.Attention computes query-key dot products to aggregate values; the MLP then applies nonlinear transformations.Source: §2.1 · p. 2

2.2 LLM KV Cache

  • The KV cache stores key and value vectors during prefill for use during sequential decoding, reducing repeated attention computation.Initial prompt processing latency, including queueing delay, is measured as TTFT; generation speed is measured as TPOT.Source: §2.2 · pp. 2–3

2.3 LLM Serving Prefix Cache

  • Prefix caching reuses cached KV states only when the entire preceding sequence matches, organizing reusable states in a prefix tree while decoupling physical eviction from that tree.Requests commonly share system prompts, examples, or conversation histories; the cache uses fixed-length blocks across HBM and larger global memory pools.Source: §2.3 · p. 3

2.4 Sessions

  • A session is a continuous conversation or agent task whose sequential requests append user inputs and tool outputs to shared context.This append-only structure preserves history and supports prefix reuse.Source: §2.4 · p. 3

2.5 Traditional Web and Storage Cache

  • Traditional web and block-storage workloads exhibit patterns such as Zipfian popularity, one-hit wonders, and sequential scans that have shaped eviction algorithms.These workload patterns differ from the session-driven prefix-cache setting.Source: §2.5 · p. 3

3 Fancy Algorithms Do Not Work Well

The evaluation compares fourteen online eviction policies with Belady’s offline optimum on production prefix-cache traces across constrained and large memory settings. Advanced policies generally fail to improve on LRU, while the offline result leaves substantial headroom.

3.1 Traces and Simulator

  • The evaluation uses FreeInference and Chutes production traces, which provide fine-grained cross-session block identity and multi-turn agentic traffic.A custom C++ simulator models the requirement that all blocks for an incoming request’s prefix be resident together during prefill.Source: §3.1 · p. 4, Table 3 · p. 4

3.2 Evaluation of Eviction algorithms

  • The study evaluates fourteen online algorithms against Belady across per-replica HBM capacities of 24–120 GiB and global pools of 0.25–12 TiB.It reports hit and compute-savings ratios under a uniform cost model.Source: §3.2 · p. 4, §3.1 · p. 4
  • Across production traces and memory capacities, none of the state-of-the-art algorithms improves block hit ratio over LRU, while Belady remains a higher offline ceiling.Most advanced policies match or slightly trail LRU; quick-demotion results vary by trace, and frequency-based policies perform far worse.Source: §3.2 · pp. 4–5, Figure 2 · p. 5

4 What Makes Prefix-Cache Different

Across production workloads, recency remains a strong eviction signal, but its advantage depends on workload and cache capacity. Prefix-cache behavior is shaped by session-bounded reuse, while depth-dependent miss costs and skewed session footprints create additional design tradeoffs.

4 What Makes Prefix-Cache Different

  • The study compares FreeInference Trace with Wikipedia web-CDN and CloudPhysics block-I/O workloads, treating each KV block as a distinct cache object.It uses these workload contrasts to examine characteristics that distinguish prefix caching from traditional cache workloads.Source: §4 · p. 5

4.1 Session-Bounded Lifetimes

  • Most reused prefix blocks live under 30 minutes, and working-set overlap falls near zero beyond two hours, so retaining old blocks offers little benefit.Multi-turn session blocks are confined to their originating conversations, while system prompts can persist across sessions.Source: §4.1 · pp. 5–6

4.2 Recency Provides a Key Signal

  • Reuse is concentrated in short intervals: the median intra-session gap is 8.2 s, and 99.7% of gaps fall under 22 minutes.Long-idle blocks should be reclaimed aggressively because they are unlikely to be reused and cost capacity to retain.Source: §4.2 · pp. 6–7

4.3 Frequency Tracks Session Progress

  • Frequency tracks session progress rather than reuse timing, but a second hit raises reuse probability from 69.4% to 88.7%, helping filter one-hit prompts.Frequency is therefore a poor eviction ranking signal but can help as an admission filter in workloads with many one-hit blocks.Source: §4.3 · pp. 7–8

4.4 Position-Dependent Miss Costs

  • Equal-sized misses on deeper prompt blocks cost more attention computation, so hit ratio alone does not determine TTFT.Long requests reach 111K tokens at the 90th percentile, and retaining deeper blocks can reduce recomputation cost for comparable expected reuse.Source: §4.4 · p. 8

4.5 Heavy-Tailed Session Footprints

  • Session footprints are highly skewed: the 99th-percentile session reaches 12.2 GiB, and the top 10% of sessions hold 76.2% of KV bytes.Constrained caches benefit from partial-session eviction; expansive pools can use session-level management to reduce metadata overhead.Source: §4.5 · pp. 8–9, Figure 10 · p. 9

4.6 Findings Generalize Across Workloads

  • At 1 TiB, LRU is within 0.4 points of the best online algorithm on every trace, but at 24 GiB it leads on none.LRU catches up at 60–462 GiB on the Qwen traces, versus 37 GiB on FreeInference Trace.Source: §4.6 · p. 9

5 What Designs Can Be Helpful?

LRU remains the foundation because recency fits session-bounded reuse, but prefix-cache design must account for one-hit traffic, depth-varying recomputation costs, and cache capacity. The section recommends targeted additions rather than a single policy for every setting.

5.1 Quick Demotion

  • At 24 GiB on Qwen To-B, S3-FIFO reaches a 0.491 hit ratio versus LRU’s 0.403 when one-hit prompts threaten the active working set.Quick demotion is useful chiefly when one-hit prompts account for an extremely high volume of traffic.Source: §5.1 · pp. 9–10, Figure 11 · p. 10

5.2 Compute-awareness

  • BeladyCompute stays within 1.03 points of the ILP optimum at 24 GiB, 0.41 points at 48 GiB, and 0.08 points at 96 GiB.The gap between hit-optimal Belady and BeladyCompute is +12.6 points at 24 GiB on FreeInference Trace, but ≤1.1 points on the other five traces, offering a diagnostic for whether compute-awareness is worthwhile.Source: §5.2 · pp. 10–11, Figure 12 · p. 10
  • With high variance in block costs, RandomCompute reaches a 0.638 compute-savings ratio at 24 GiB, 10.4 points above LRU and above standard hit-optimal Belady.Partial-node eviction cuts average hole count by 8.7× while sacrificing negligible compute savings at 24 GiB; practical chunk size should align with the contiguous batching token budget when applicable.Source: §5.2 · p. 11
  • At 48 GiB, partial-node compute-aware eviction cuts average TTFT by 19.9% (1.04 s vs. 1.29 s) and raises prefill throughput by 18.8% (65.6K vs. 55.2K tokens/s) over LRU.The H200 evaluation also finds block-based RandomCompute incurs 4.0× higher TTFT and 3.9× lower throughput than LRU because of fragmentation.Source: Figure 13 · p. 10, §5.2 · p. 11

5.3 Block-Level vs. Session-Level Eviction

  • At 24 GiB, session-level eviction loses 10.5 hit-ratio points for LRU and 18.7 compute-savings points for RandomCompute; at 48 GiB, losses remain 3.3 and 5.5 points.The gap becomes virtually unmeasurable in large pools, where session-level eviction can reduce metadata overhead; evicting whole sessions can also purge shared system prompts.Source: §5.3 · pp. 11–12, Figure 14 · p. 11

5.4 Summary

  • Use quick demotion only when one-hit prompts threaten capacity, compute-aware partial-node eviction for long sequences with variable recomputation costs, and block-level eviction in constrained HBM.Large secondary pools can use either block- or session-level eviction, while compute-awareness should be confined to the main cache when combined with quick demotion.Source: §5.1 · p. 10, §5.2 · p. 11, §5.4 · p. 12

6 Discussion

The discussion identifies deployment conditions that alter how the designs apply: attention mechanisms change the cost model, routing can affect replica pressure, and SSD offloading is usually unnecessary.

6.1 Other Attention Designs

  • Alternative attention designs change recomputation costs, so the cost model needs recalibration, while the reuse patterns still apply.Sliding-window attention moves costs toward constant with prefix depth; hybrid attention makes the benefit depend on the share of full-attention layers.Source: §6.1 · p. 12

6.2 Interaction with Load Balancing

  • Cache-affinity routing can create uneven replica pressure from heavy-tailed session footprints, but the eviction findings remain applicable after a request reaches a replica or shared pool.The underlying dynamics remain session-bounded lifetimes, concentrated recency, and varying compute costs.Source: §6.2 · p. 12

6.3 SSD Offloading

  • SSD offloading is generally unnecessary for most workloads because session-bounded working sets churn before SSD capacity helps; long-tail reuse or extreme capacity demands are exceptions.In those cases, selective admission is needed to preserve flash endurance while capturing the limited reuse window.Source: §6.3 · p. 12

7 Related Work

The related-work section positions this study as a comparison of replacement policies within existing prefix-cache mechanisms, using production traces with properties needed for policy simulation. It distinguishes cross-request eviction from adjacent routing, context-management, and within-context KV techniques.

7 Related Work

  • Prior prefix-cache work spans KV storage tiers and retention policies, while this study compares classical, learned, and prefix-specific replacement across production traces and capacity ranges.Its analysis connects policy behavior to session-bounded reuse, frequency, non-uniform miss costs, and session footprint.Source: §7 · p. 12
  • Existing public traces lack the combination of agentic traffic, accurate multi-day timestamps, and fine-grained block hashes needed for robust policy simulation.The introduced traces enable controlled comparison of eviction policies and their offline optimum on the same request stream.Source: §7 · p. 13
  • Within-context KV methods may trade output quality for per-request memory, whereas this study’s cross-request blocks are exactly reconstructible and misses cost prefill compute.Cache-aware routers decide where requests run; eviction decides what remains available at each replica.Source: §7 · p. 13

8 Conclusion

The conclusion argues that advanced traditional-cache eviction policies offer little improvement over LRU because session-paced prefix reuse makes recency predictive. It recommends retaining recency and adding targeted techniques for specific workload and capacity conditions.

8 Conclusion

  • Advanced eviction algorithms designed for traditional storage yield surprisingly little improvement over LRU, while some can degrade performance.The reported comparison includes a large gap to the optimal Belady oracle.Source: §8 · p. 13
  • Prefix reuse follows active-session pacing, making recency useful while frequency signals are ineffective; miss costs also vary with depth and session footprints are heavy-tailed.Source: §8 · p. 13
  • The conclusion recommends conditionally adding quick demotion, compute-aware eviction, and capacity-tier-dependent granularity to a recency foundation.These targeted optimizations are presented as a foundation for scalable prefix caching.Source: §8 · p. 13

A Capacity Sweeps

Capacity sweeps reveal policy behavior that comparisons at only a few cache sizes can miss: policies may cross over or vary nonmonotonically as capacity grows.

A Capacity Sweeps

  • The sweeps extend comparisons to 65 capacities across both cache-size regimes, while Table 6 lists trace sizes.LRB is omitted because its sweep is prohibitively slow and it never outperforms LeCaR at the four sampled capacities on either production trace.Source: A Capacity Sweeps · p. 17, Table 6 · p. 17
  • On Qwen To-C, LIRS shifts from 4.2 points above LRU to 10.1 points below it at 724 GB.On FreeInference Trace, W-TinyLFU’s hit ratio rises to 0.866 at 97 GB, falls to 0.759 at 906 GB, and recovers to 0.933 at 12 TB.Source: A Capacity Sweeps · p. 17
  • W-TinyLFU’s hit ratio on FreeInference Trace is nonmonotonic across the sweep: 0.866 at 97 GB, 0.759 at 906 GB, and 0.933 at 12 TB.Source: A Capacity Sweeps · p. 17

B Sensitivity Analysis of Concurrency

As concurrency rises, hit ratios decline and policy differences widen; the experiment varies concurrency while replaying the same requests.

B Sensitivity Analysis of Concurrency

  • The experiment replays the same 73,637 requests at each target concurrency, so the concurrency trend is relevant, but absolute hit ratios should not be compared with §3.1.Sessions are truncated and arrival times rescaled to vary concurrency.Source: B Sensitivity Analysis of Concurrency · p. 17
  • At 48 GiB, Belady’s hit ratio falls from 0.926 at concurrency 8 to 0.713 at concurrency 32, while LRU’s falls from 0.898 to 0.517.Hit ratio declines for every policy, including the offline optimum.Source: B Sensitivity Analysis of Concurrency · p. 17
  • At concurrency 32, S3-FIFO reaches 0.573 versus LRU’s 0.517; at concurrency 1024 in the pool, S3-FIFO, ARC, and LIRS overtake other online policies.As concurrency rises, fewer reuses remain reachable within cache capacity: in HBM, the share falls from 92.5% at concurrency 8 to 50.1% at 32; in the pool it is 54.1% at concurrency 1024.Source: B Sensitivity Analysis of Concurrency · p. 17

C Compute Savings under the Linear Cost Model

Under the linear cost model, compute-aware policies gain more than under the measured model, while partial-node eviction remains close to free and the offline approximation stays close to optimal.

C Compute Savings under the Linear Cost Model

  • At 24 GiB, RandomCompute saves 0.646 against LRU’s 0.524, while BeladyCompute reaches 0.745 against Belady’s 0.599.The margins are 12.2 and 14.6 points, respectively; BeladyCompute clears the hit-optimal Belady oracle by 4.7 points.Source: C Compute Savings under the Linear… · p. 18
  • BeladyCompute is 0.95 points below the ILP solution at 24 GiB, 0.40 at 48 GiB, and 0.08 at 96 GiB.Partial-node eviction gives up 0.03 points of compute savings at 24 GiB under the linear model.Source: C Compute Savings under the Linear… · p. 18
  • At 1 TiB, every policy and both oracles lie within 0.2 points of one another; the two cost models rank policies identically, with wider margins under linear cost.Source: C Compute Savings under the Linear… · p. 18

D Recompute Fragmentation

Partial-node eviction reduces recompute fragmentation by producing fewer, longer holes while leaving total recompute volume nearly unchanged.

D Recompute Fragmentation

  • RandomCompute’s hole count reaches 143 at the 99th percentile and 281 at maximum, compared with 2 and 16 under partial-node eviction.Both policies have a median of one hole per request.Source: D Recompute Fragmentation · p. 18
  • Partial-node eviction raises mean hole length from 85.5 to 742.6 blocks and reduces holes no longer than two blocks from 56.6% to 0.8%.Source: D Recompute Fragmentation · p. 18
  • Total recompute volume is nearly unchanged: 258.0 M blocks for RandomCompute and 257.9 M for partial-node eviction.Source: D Recompute Fragmentation · p. 18
  • At 24 GiB over 327,548 requests, partial-node eviction leaves fewer holes per request, and those holes are longer.Source: Figure 20 · p. 19
Loading 2609.28870v1…