Prefix caching is a key performance optimization in Large Language Model (LLM) serving systems, enabling reuse of attention Key-Value (KV) states across requests with shared prompt prefixes. However, the size of GPU memory limits cache capacity, making the eviction policy a critical factor in overall system performance. Existing systems primarily rely on simple heuristics, such as LRU, and apply the same policy across task categories, implicitly assuming homogeneous workloads. In practice, however, modern LLMs serve heterogeneous workloads that mix multi-turn conversational traffic with diverse single-turn API requests, leading to fundamentally different prefix reuse patterns. In this work, we first design a trace-driven prefix cache simulator built on vLLM to systematically characterize prefix reuse across representative workloads. Our analysis reveals two dominant reuse patterns---session reuse and structural reuse---that vary significantly across task types. Motivated by these observations, we propose UniCache, a unified eviction policy that jointly captures both reuse patterns and dynamically balances cache allocation across tasks. When implemented in vLLM, UniCache achieves substantial improvements under heterogeneous workloads, improving prefix cache hit rates by up to 17.32% and reducing inference latency by up to 3.63× compared to existing policies.
Ouyang et al. (2026) studied this question.