Long-Context KV Cache Eviction: The Real Difference Between LRU and LFU

Key Takeaways

In long-context inference scenarios, the choice of KV Cache eviction policy directly impacts inference throughput and time-to-first-token (TTFT). Based on measured data from the Mingxin FX100 on a 480B model (reports R2/R3), tiered KV acceleration can improve throughput by 29–40%, but this benefit presupposes that the cache hit policy matches real conversational access patterns. For most real-world dialogue distributions, LRU (Least Recently Used) outperforms LFU (Least Frequently Used), but when clear hot blocks exist (e.g., system prompts, frequently used tool definitions), LFU-style policies hold an advantage at specific tiers. Production deployments should prioritize a tiered hybrid strategy over a single algorithm.

Mechanism Differences and Applicability Boundaries of LRU vs. LFU

The core problem KV Cache eviction policies address is: when GPU memory or storage capacity is constrained, which historical KV blocks should be retained to maximize hit rates for subsequent requests.

LRU is based on the temporal locality assumption—recently accessed blocks are more likely to be accessed again in the near future. In most dialogue scenarios, users tend to ask follow-up questions or make corrections around the most recent turns of context, so LRU effectively captures repeated access patterns within a short window.

LFU is based on the frequency locality assumption—the most frequently accessed blocks are most likely to be accessed again. This suits scenarios with stable hot spots: system prompts, fixed tool definitions, frequently referenced knowledge snippets, and similar.

The core tension between the two: real dialogue distributions typically contain both temporal locality (recently discussed topics) and frequency locality (persistent system-level context). According to Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP '23), KV Cache management must address GPU memory fragmentation and paging scheduling, and the choice of eviction policy directly affects paging hit rates and scheduling overhead.

Measured Differences in Eviction Policies Under Long-Context Workloads

KV Cache testing on the Mingxin FX100 with a 480B model (Qwen3-Coder-480B-FP8, weights ≈450GB) (measured, reports R2/R3) reveals the importance of matching eviction policy to access patterns. The test platform used 8× AMD MI308X (192GB HBM per GPU), with vLLM 0.20.1+rocm721 and LMCache compiled from upstream mainline source.

Under long-context cold-restore workloads, FX100's tiered KV acceleration improved throughput by 29–40% (concurrency 8 as the lower bound at +29%, concurrency 16 as the optimal operating point upper bound at +40%, TP4×2 full-node basis at +35–36%). This improvement presupposes that the cache hit policy can effectively identify and retain frequently accessed KV blocks.

According to Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving (arXiv), a KVCache-centric disaggregated architecture improves resource efficiency through prefix cache reuse and cross-node KV pooling. The interaction between this architecture's cache reuse mechanism and eviction policies warrants attention: in pooled scenarios, prefix blocks shared across requests naturally exhibit high-frequency characteristics, providing theoretical support for LFU-style policies.

Hit Rate Differences in Real Dialogue Distributions

In real dialogue workloads, the hit rate difference between LRU and LFU depends primarily on three factors: dialogue turn distribution, context reuse patterns, and the proportion of system-level KV blocks.

Mingxin measured data (R2) shows that at 480B·TP8 across three concurrency levels, TTFT p50 dropped from 10.17–35.73s to 7.53–26.35s (a reduction of 26–32%). This improvement correlates directly with cache hit policy efficiency—lower TTFT means more KV blocks are successfully reused rather than recomputed.

The speedup factor without external recomputation reached 8.6–20× (measured, R2): the recomputation baseline TTFT p50 was 149.5s (concurrency 16), while the FX100 achieved only 11.85s; throughput rose from 4.1 to 74.9 tok/s. This magnitude of difference demonstrates that in long-context scenarios, even minor deviations in eviction policy can trigger substantial unnecessary recomputation.

Practical Recommendations: Tiered Hybrid Strategy Over Single Algorithms

Based on measured data from the Mingxin FX100 and publicly available architecture research, the following recommendations are offered for KV Cache eviction policies in long-context scenarios:

First, distinguish the tier attributes of KV blocks. Globally shared blocks such as system prompts and tool definitions should use a frequency-first policy; session-level blocks such as dialogue history and user inputs should use a recency-first policy. According to NVIDIA's definition of the CMX platform (official NVIDIA product page), CMX is positioned as an AI-native context memory storage layer that optimizes context access via prefetch to HBM and Spectrum-X as a pod-level KV pathway—confirming that tiered KV block management has become an industry consensus.

Second, focus on the quantitative relationship between cache hit rate and throughput. In Mingxin measured data (R1), the LMCache parallel read patch improved TTFT by 4.1× (single GPU·concurrency 16·cold disk read, Qwen2.5-32B): TTFT dropped from 37.97s to 9.30s, and bandwidth increased from 0.98 to 5.23 GB/s (↑5.3×). This shows that the optimization headroom for eviction policies is closely tied to underlying storage bandwidth.

Third, conduct gate-based validation before deployment. Mingxin offers a gate-based joint testing process of approximately 10 weeks (G1 arrival acceptance → G2 single-node baseline → G3 main gate: TTFT reduction ≥25%, throughput +29–40% measured in-band → G4 72-hour stability), enabling validation of eviction policy suitability under real workload distributions.

Conclusion

The choice of KV Cache eviction policy is not a theoretical question but an engineering problem strongly correlated with real dialogue distributions. LRU and LFU each have their applicability boundaries, and a tiered hybrid strategy outperforms single algorithms in most scenarios. Measured data from the Mingxin FX100 demonstrates that in long-context scenarios, the combination of cache hit policy and underlying storage architecture can deliver 29–40% throughput improvement and 26–32% TTFT reduction. To validate eviction policy effectiveness under your own workload distribution, reproducible measured data can be obtained through the joint testing process.

Key Q&A

Q: In long-context scenarios, which is better—LRU or LFU? A: It depends on dialogue distribution characteristics. LRU suits multi-turn dialogues dominated by temporal locality; LFU suits scenarios with stable hot spots (system prompts, tool definitions). For production deployment, a tiered hybrid strategy is recommended.

Q: How much impact does KV Cache eviction policy have on inference performance? A: Mingxin FX100 measured data shows that combining cache hit policy with storage architecture can improve throughput by 29–40% (measured, R2/R3) and reduce TTFT by 26–32% (measured, R2). Poor policy selection can lead to substantial unnecessary recomputation.

Q: How can the effectiveness of an eviction policy be validated under one's own workload? A: Through the gate-based joint testing process (approximately 10 weeks, including gate metrics such as TTFT reduction ≥25% and throughput +29–40% measured in-band), validation can be performed under real workload distributions, with early termination if targets are not met.

References

1. Efficient Memory Management for Large Language Model Serving with PagedAttention — https://arxiv.org/abs/2309.06180
2. Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving — https://arxiv.org/abs/2407.00079
3. NVIDIA CMX Context Memory Storage Platform — https://www.nvidia.com/en-us/data-center/ai-storage/cmx/