Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective
This work addresses the challenge of optimizing KV cache efficiency and query load balancing in multi-LLM serving systems, offering a novel solution with significant performance gains.
The paper tackles the problem of KV caching in LLM inference under limited memory, where existing eviction policies like LRU struggle with dynamic query arrivals and conflicting objectives in multi-LLM serving. It introduces a unified model and algorithms combining randomized eviction with learning-based query routing, achieving improvements such as up to 6.92x in cache hit rate and 77.4% increase in throughput over state-of-the-art methods.
KV caching is a fundamental technique for accelerating Large Language Model (LLM) inference by reusing key-value (KV) pairs from previous queries, but its effectiveness under limited memory is highly sensitive to the eviction policy. The default Least Recently Used (LRU) eviction algorithm struggles with dynamic online query arrivals, especially in multi-LLM serving scenarios, where balancing query load across workers and maximizing cache hit rate of each worker are inherently conflicting objectives. We give the first unified mathematical model that captures the core trade-offs between KV cache eviction and query routing. Our analysis reveals the theoretical limitations of existing methods and leads to principled algorithms that integrate provably competitive randomized KV cache eviction with learning-based methods to adaptively route queries with evolving patterns, thus balancing query load and cache hit rate. Our theoretical results are validated by extensive experiments across 4 benchmarks and 3 prefix-sharing settings, demonstrating improvements of up to 6.92$\times$ in cache hit rate, 11.96$\times$ reduction in latency, 14.06$\times$ reduction in time-to-first-token (TTFT), and 77.4% increase in throughput over the state-of-the-art methods. Our code is available at https://github.com/fzwark/KVRouting.