FairCache: Demystifying Cache-Induced Unfairness in Multi-Tenant Large Language Model Serving

Abstract

Large language models (LLMs) increasingly rely on context caching to enhance serving efficiency. However, this optimization inadvertently compromises fairness in multi-tenant LLM serving systems. Existing fair schedulers, which account only for compute resources, are unable to handle the multi-dimensional resource demands introduced by context caching. We identify that tenants with high cache hit rates are perceived as having lower compute costs, leading schedulers to unfairly prioritize them over others. Furthermore, the first tenant to compute a shared prefix fully bears the prefill cost for shared prefixes, while subsequent consumers free-ride on the cached data without contributing to such prefill cost. Addressing such unfairness via rigid allocation strategies (e.g., static partitioning) overlooks workload heterogeneity, inevitably wasting host memory on low-reuse workloads. To address the challenges above, we introduce FairCache, the first system that achieves comprehensive resource fairness in multi-tenant LLM serving with context caching. FairCache unifies compute, memory, and I/O costs into a single scheduling metric, and redistributes the prefill cost of shared prefixes across all benefiting tenants to mitigate free-riding. For cache management, FairCache combines the max-min fair allocation with a lightweight reuse-value model that reclaims cold data without harming fairness. Extensive evaluations using a prototype implementation with diverse workloads demonstrate that FairCache effectively eliminates cache-induced unfairness while maintaining high serving efficiency. Theoretical analysis further establishes FairCache's fairness properties and Pareto-efficient cache utilization under bounded request costs, work-conserving operation, and deterministic tie-breaking.