Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective

AI summary

Overview

Research area: machine learning systems and LLM inference optimization, specifically KV cache eviction and KV cache-aware load balancing. Technical level: Advanced. Scope: the paper develops a unified mathematical model and two algorithms, RLT and LBGR, that jointly improve KV cache hit rates and query routing across multiple LLM workers.

What This Paper Is About

KV caching speeds up LLM inference by reusing key-value pairs from previous queries, but its effectiveness under limited memory depends heavily on the eviction policy. The default LRU eviction struggles with dynamic online query arrivals, especially in multi-LLM serving, where balancing query load across workers and maximizing each worker’s cache hit rate are conflicting goals. This paper builds a formal model for this trade-off and proposes principled algorithms to improve both objectives.

Key Contributions

1. The first unified formal model for KV cache-aware load balancing, capturing the coupling between local cache eviction and global query routing by decomposing query latency into service time and queueing delay and minimizing makespan across LLMs.
2. A formal analysis showing that LRU-based eviction, specifically Leaf-LRU in SGLang’s RadixAttention, has a worst-case competitive ratio that degrades to O(n), and proposing Randomized Leaf Token eviction (RLT) with an O(log n) worst-case competitive ratio.
3. A learning-based greedy routing algorithm, LBGR, that estimates end-to-end latency using service time, queue load with exponential decay, and an online residual regression model, then routes each query to the LLM with the lowest predicted latency.
4. Extensive evaluations across 4 benchmarks and 3 prefix-sharing settings, reporting up to 6.92× higher cache hit rate, 11.96× latency reduction, 14.06× TTFT reduction, and 77.4% throughput increase over state-of-the-art methods, with code available at https://github.com/fzwark/KVRouting.

Main Findings

• Theoretical limitation of LRU. For Leaf-LRU in RadixAttention under single-query processing, the competitive ratio is upper bounded by (B_i - L + 2) and lower bounded by (B_i - L + 1). Under continuous batching with batch size β, it is upper bounded by (B_i - L - β + 3) and lower bounded by (B_i - L - β + 2). In the worst case, this becomes O(n).

• RLT improves the competitive ratio. RLT is Θ(log(B_i - L))-competitive under single-query processing and Θ(log(B_i - L - β))-competitive under continuous

Authors’ abstract

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.