Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective
Authors: Fangzhou Wu
Sandeep Silwal
Qiuyi Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: KV Cache
Prefix Sharing
LRU
Large Language Models
LLM Routing
KV Cache Eviction
Multi-LLM Serving
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We present the first unified model of KV cache eviction and query routing, and propose algorithms that combine provably competitive randomized eviction with learning-based routing to significantly boost inference efficiency and reduce latency.

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.

Published as a conference paper at ICLR 2026
RANDOMIZATION BOOSTS KV CACHING, LEARNING BALANCES QUERY LOAD: A JOINT PERSPECTIVE
Fangzhou Wu', Sandeep Silwal', Qiuyi (Richard) Zhang 'University of Wisconsin- -adiisn, GGoogee DeepMind
cous9@wisc.eet silwal saralcca @cs wisc. edu, giuyiz@google.com com
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.92x x in cache hit rate, 11.96x reduction in latency, 14.06x reduction in increase in throughput over the state-of-the-aat methods. Our code is available at attps://githus com http://wwww..ceeetteeee/////eeee
(TTFT), and 77.4%
INTRODUCTION
The increasing demands of Large Language Model (LLM) services impose substantial inference overhead on the L.M serving system (Jaillet et al. 2026). KV caching has emerged as a core technique to alleviate such costs by storing and reusing the key- value pairs of previously processed tokens as reusable prefixes for future generation (Vaswani et al. 2017). While practical, its effectiveness under limited memory is highly sensitive to the eviction policy, particularly in online processing, since the cache hit rate of a future query depends directly on which tokens have been evicted beforehand (Dan & Towsley] 1990). Although the traditional Least Recently Used (LRU) eviction policy Neil et al. 1993 Fiat et al.] 199I) remains the dominant choice in current LLM LLM--erving system designs (Zheng al. 2024 Kwon al. 2023 NVIDIA 2025), its strategy of evicting the oldest tokens within specific prefix-sharing cache structures is fragile and can be readily compromised under dynamic query arrivals (Fiat et al. 1991). In worst-case scenarios (Figure |
left). LRU may evict exactly the tokens needed by the next query, leading to cache misses and ultimately increasing inference latency.
This instability of eviction becomes more pronounced in a scaled multi-LLM setting, where the objective of balancing query loads across LLMs inherently conflicts with the goal of maximizing the cache hit rate for the single model. Such conflicts naturally extend to a general KV cache-aware load balancing problem. Figure (right) outlines its key trade-offs between caching affinity and global load balancing: (i) While maximizing eaching affinity by routing similar queries to the same LLM may appear ideal, it inevitably leads to severe global load imbalance. This becomes particularly problematic when large batches of similar queries are routed to a single LLM, resulting in queueing delay dominating over actual service time and nullifying the benefits from the high cache hit rate. (ii) Conversely, distributing queries to balance query load without considering the cache situation leads to poor cache hit rate and, ultimately, suboptimal end-to-end inference latency. Furthermore, routing queries across LLMs introduces dependencies within the online sequence of queries, as actions taken in earlier steps have sizeable impact on those taken later, creating additional variability, and further

---

Published as a conference paper at ICLR 2026
KV Cache Eviction on Single LLM
KV Cache-Aware Load Balancing in Multi-LLM Scenarios
LRU-based Eviction Policy
Cache Affinity First
Global Load-Balancing First
When
Aneff
Prott
Maten
Router
Router
(Query
Queries
Oispatching
Queries
Dispatching
Evrict the Oldest Takensi
Lead to Cache Misses!
Query
Lood
Low Cache
Optimal Eviction Policy
Queue
Imbalance!
Hit Rote!
WWhen
Profis Sharing
Profi
Profe
Matten
Match
Optimal Eviction!
Coche Hitl
Cache
cache
cache
cache j
Figure I: Key trade-off's between single LLM cache affinity and global load balancing in the KV cache-aware load balancing problem.
destabilizing existing LRU eviction policies. These complex tensions underscore the need for formal mathematical model capturing the underlying dynamics.
Existing work, however, primarily relies on heuristics to address this problem, where they either adopt a static linear score that ranks each LLM based on cache hit rate and queue length, or employ a rule-based strategy that switches between highest-hit hit-rate and least-loaded routing using predefined load-balance threshold (NVIDIA) 2025 Ilm d) 2025 Zheng et al.. 2024). While easy to implement, these methods suffer from key limitations and struggle to optimize both objectives. They are inherently static and unable to adapt to dynamic query arrival patterns. Their modeling of queue workload limited to the raw counts of pending queries, which overly simplistic and fails to capture the true dynamics of system congestion. They are also fundamentally limited in achieving optimal performance, as they are rooted in heuristics, lack formal modeling, and therefore fail to capture the intricate coupling between cache eviction and load balancing.
This work establishes the first unified model of KV cache-aware load balancing to fill the gap between practical designs and theoretical understanding. The model formalizes the end-to-end latency of query on each I.I.M by decomposing it into service time and queuing delay, explicitly modeling service time as a function of cache state and defining the queue load of each LLM the cumulative service time of its assigned queries, with the objective of minimizing the makespan across LLMs. Within this formulation, our formal analysis reveals the inherent limitations of the LRU-based eviction policies, whose competitive ratio degrades to O(n) in the worst case.
These insights further motivate the proposition of principled algorithms, RLT and LBGR. For each LLM, RLT introduces Randomized Leaf Token eviction to replace traditional LRU, improving robustness dynamic query arrival patterns and achieving worst-case competitive ratio of Oloog n). LBGR then routes queries greedily by estimating the end-to-end latency for each LLM using dynamic, online learning-bard based strategy. particular, estimates the service time and queue load using a global cache tracker and applies exponential decay the queue load estimate to account for its natural reduction over time. To capture residual latency beyond service and queueing delays, an online residual regression model is deployed and continuously updated during runtime.
We validate the effectiveness of our algorithms through extensive experiments across 4 benchmarks and distinct prefix-sharing settings, demonstrating up to 11.96x and 5.46 x reductions in end-to-enu latency, and up to 14.06 and 7.19x reductions in time-to- to-iisttttooenn (TTFT) compared to state-of- the-art methods
1lama-3.1-8B- Insstrutttt (NVIDIA L40) and Llama-3.1 1-170---Instrun H200), respectively, with context lengths up to 8k tokens. Furthermore, on Llama-3.1 1-88-Innttrct, RLT achieves up to 6.92x higher cache hit rate and 77.4% higher throughput than the LRU-based eviction policy under worst-case query arrivals. To summarize, our main contributions are:
(NVIDIA
1.
We present the first unified formal model for the KV cache-aware load balancing problem, which captures the intricate coupling between local cache eviction and global load balancing.
2

---

Published as a conference paper at ICLR 2026
2. Within this model, we provide formal analysis that reveals the theoretical limitations of existing system designs and motivates two simple yet effective algorithms, RLT and LBGR.
3. RLT introduces Randomized Leaf Token eviction in prefix-sharing KV cache structure, improving robustness to dynamic query arrivals and achieving a worst-case competitive ratio of (log n), which is exponentially better than the (n) achieved by the existing LRU-based eviction policy.
4. LBGR employs an online regression model that incorporates cache state to dynamically estimate end-to-end latency and greedily route queries to the LLM with the lowest predicted latency, providing greater adaptability to dynamic query patterns than prior static beuristic-based methods. We conduct extensive evaluations on 4 benchmarks across 3 prefix-sharing settings, which validate the effectiveness of the proposed algorithms, showing notable reductions in end-to-end latency.
2 BACKGROUND
KV Cache Management. Recent work on KV cache management falls into two strands. Context- aware methods leverage model-driven signals to compress the KV cache, retaining only a fixed-budget
subset (Zhang et al. 2023 Xiao et al. 2024 Liu at (023). Examples include H2O, which preserves
high-attention tokens, and StreamingLLM which retains initial attention sinks (Zhang al. 2023
Xiao et al. 2024 Liu al. 2023). Another strand aims to improve KV cache efficiency via memory layout and interface design (Kwon et al. 2023 Zheng al.
2024). vLLM reduces fragmentation
with fixed-size virtualized memory pages [K won et al. 2023). while RadixAttention enables prefix
sharing and reuse via radix tree (Zheng al. 2024). However, those systems rely on LRU-based
KV cache eviction, which is fragile under dynamic or adversarial query arrivals. The lack of formal analysis further reveals gap between practical designs and thcoretical understanding.
KV Cache-Aware Load Balancing, In multi-LLM serving, KV cache-aware load balancing arises from the need to balance queue load while preserving KV reuse (Sun et al.. 2024 Zheng et al. 2024
Lee el al., 2024). Most systems use heuristics that trade off cache affinity and queue load (NVIDIA
Zheng et al. 2024 [l d 2025). For instance, SGLang switches between hit-rate and based routing using a tixed threshold (Zheng et al., 2024), while others use static linear scores (NVIDIA 2025| [l d, 2025). While practical, these methods are largely heuristic, lack formal modeling, and may underpertorm under dynamic query arrivals. See extended related work in Appendix D
FORMAL PROBLEM FORMULATION AND THEORETICAL ANALYSIS
While modeling all aspects of the KV cache- aware load balaneing is intractable, its essential properties can be effectively captured through a simplified formulation that minimizes the makespan across all LLMs during serving.
3.1 UNIFIED ONLINE FORMULATION FOR KV CACHE- LOAD BALANCING
Let M denote the number of workers (LLMs) I indexed by i E [M]] each denoted by m, and equipped with KV cache of size B, tokens. We given a sequence of N queries, Q {1) N which are processed in fixed order (online arrival). Each query Oj has input length of [yyl tokens, and its response aj consists of layl tokens. We use two variables to track the state of each worker m. after processing j queries: (1) p("), which denotes the total accumulated load on worker m,, and (2) s("), which represents the cache state of worker m,, The system is initialized at j = 0 with p. = 0 and 5:0) = for all E [M.. For any query dj we define húj ((5(5-11) .4j) as the number of cache-hit tokens on m,, Let oCAChED and orMIss denote the time costs of processing cached and uncached tokens, respectively. Then, the service time cost for 9j on m, can be defined as
)=1+
Costij = aCACHED hag + amiss (la5) - h.g) + Oij
(1)
where O,ÿ is the time cost of generating the output aj. Let mij E {0, 1} be the binary decision variable indicating whether query 9, is routed to worker m,, subject to ΣM Zij 1, e [N].
Throughout, we use "L.M"" and "worker" interchangeably and assume all deployed L.Mss are of the same
type.
3

---

Published as a conference paper at ICLR 2026
Table I: Notation and definitions.
Notation
Description
M
Number of workers (LLMs)
mH
The i-th worker (LLM)
B;
KV cache size (in tokens) worker me;
Q
Queries processed in a fixed order (online arrival) Input token sequence of j-th query Output token sequence of j-th query
4
a
p())
Query load of worker m: after processing queries
s(u)
Cache state of worker after processing j queries
biy
Number of cache-hit tokens of d3 worker
OCACHED
Per-token time cost cached tokens
OAIIS
Per-token time cost for uncached tokens
Costa
Service time cost of processing I on worker m,
Tij
Binary routing variable, equal to if Øj is assigned to worker mi
Once the assignment Zij is made for 4j. the system state is updated for all workers accordingly. The queue load of each worker is incremented by the service time cost only if it was assigned the query:
p()) = = + zιj Costij-
(2)
The cache state is updated only for the worker that processes the query:
UPDATECACHE(S B.) s(i-1)
s =
(3)
if Tij
where UPDATECACHE() is function (e.g., an LRU policy) that returns the new cache state of m4. The objective is to find the assignment x { that minimizes the following makespan: ming (P!
3.2 THEORETICAL LIMITATIONS OF LRU-BASED EVICTION
Leaf-LRU. Building on unified model above, formally analyze the performance of LRU-based eviction policies, focusing on Lea (L-LRU), the eviction algorithm used in SGLang, one the state-of-the-art L.LM serving systems. In SGLang, the Attention mechanism stores KV values in radix tree structure organized at token granularity, and evicts the least recently used leaf tokens using L-LRU when memory is saturated. Since the process time of token hits negligible compared to that of misses, we ignore the hit cost and focus on the total number of token misses.
Cache Matching and Arrival Model. As the response aj of each query qj is also cached in the radix tree, we define the complete token path 1 := d3 llla, as the concatenation of the prompt and its generated tokens. Accordingly, we extend the query set Q the set of complete token paths Q = (Tr Cache matching then reduces to longest- preefix path matching in the radix tree. In the following analysis, assume an arbitrary (potentially adversarial) arrival order over Q
Competitive Ratio of Leaf-LRU in RadixAttention. We compare L-LRU against the optimal eviction strategy (OPT), which evicts the leaf token whose next appear lies furthest the future. Our analysis covers both single-query and batch processing settings. Following (Fiat et al. 199T), we partition Q into disjoint phases (To). where each phase 4, (except possibly the last) contains exactly B, distinct tokens. In any phase 9oo (o 2 2), a token is defined as clean for L-LRU it was cache the end of l--1 and has not appeared in 9o; new if it appears for the first time in vo and old it has already been seen earlier in Te. Inspired by (Fiat et al. 1991), we begin by establishing lower bound on the number of misses incurred by OPT during phase in the following Lemma I
the
Lemma 1. In RadixAntention, the amortized number of misses incurred by OPT in a phase T. with c clean tokens is lower bounded by max(c/2,1]
All proofs are provided in Appendix
4

---

Published as a conference paper at ICLR 2026
We then analyze the maximum number of misses that L-LRU can incur in phase % with clean tokens. Misses can occur in only two cases: (1) when a new token appears, or (2) when previously evicted old token reappears. We first derive upper bound on the number of misses assuming that case (2) does not occur (Lemma 2) and then show that case (2) indeed never arises (Lemma
Lemma 2. For any phase To with e clean tokens, the number of misses incurred by L-LRU under single-query processing is at most B, C c, assuming no old token reappears after eviction.
Lemma 3. Under single-query processing L-LRU, no old token reappears in any 4o after eviction.
Using Lemmas to 3 we establish the competitive ratio of L-LRU under single-query processing.
Theorem 4 (Singlc-Query). Under single-query processing setting, the competitive ratio of L-LRU
RadixAttention on worker my with cache capacity B, is upper bounded by (B; L L++2 2) and lower bounded by (B, - C+1] 1), where L denotes the minimum length over all F E Q.
We next consider a continuous batching setting, where the system handles B distinct queries concur- rently during processing. We assume 3.mar I B, ensure that the cache can store the KV entries of all / in-progress queries, each with length up Lmaaz without evicting any entries belonging to those queries. This capacity condition aligns with typical real-world configurations and is precisely the regime where the choice of eviction policy has significant impact. Furthermore, we assume the queries within each batch are distinct, which is essential for obtaining a meaningful worst-case analysis in the batched setting (see Appendix C for detailed discussion). Building the previous analysis, we present the competitive ratio of L-LRU under this setting in the following Theorem 5
Theorem 5 (Batch). Consider the continuous batch setting with batch size B. Let Lmaz and L denote the maximum and mininum lengths over all 1 Q. If 3Lmaz S Bi, where B; is the cache capacity of worker mi and all queries in a batch are distinct, then, the competitive ratio of L-LRU in RadixAttention upper bounded by (B, L 3 3++3) 3) and lower bounded by - B 22.
Our analysis (Theorems 4 and shows that L-LRU achieves an (n)) competitive ratio in the worst case. When fixing the KV cache size B; and the maximum length Lmaxs decreasing the minimum length C drives the competitive ratio toward B,. This indicates that when lengths of queries are highly imbalanced, the competitive ratio increases and the performance of L-LRU may degrade.
4 METHODOLOGY
Motivated by the formal model and analysis above, we integrate randomized eviction algorithm (Sec- tion 4.1) with learning-bane based greedy routing algorithm that routes queries based on estimated end-to-end latency (Section 4.2) to balance query load while maintaining a high cache hit rate.
Algorithm 1 RLT
Algorithm LBGR
1: Marking token set initialization: T <- Ø
1: /* Online Routing Thread +/
2: KV cache size: B:
2: for qj do
3: Complete token paths: Q <- Q
3: for E [M] do
4: for I Q do
4: Estimate the h. via global radix tree
5: 5(5) + 5(1-1)
5: Costij +- -CCACHEDLLy axnss (14,1 Tens)
6: for E I, do
6:
bis + -ooun , l9il hug, 1505111
7:
T (t)
8:
if IT = B; + then
7:
Fas Costij + p(5-1) + +0; dij
9:
T (t)
8:
1" arg miggin Eej. 2ij = 1 17]
10:
if E 5 then
9: Vi [M], p()) 5(-11) + JJy Costej
11:
continue else
10: Route 4j to m.-
12:
11: > /* Online Updating Taread */
13:
if 5 is full then
12: if observe actual latency Ey then
14:
U (leaf tokens in s 5(') A
13: 0. +- ONLINEUPDATE (0:, dig, Fij Fes))
15:
Choose E uniformly at random
14: P. +- RELEASELOAD P.,, Costos P, At)
16:
5(1) + EvICT(S!)) .u)
15: /* Background Decay Thread //
17:
50) < (
16: Every Al time units: Vi, P. + pl:
5

---

Published as a conference paper at ICLR 2026
4.1 RANDOMIZED LEAF TOKEN EVICTION
Inspired by the classical marking algorithm FFitt et al. 1991 we introduce the Randomized Leaf Token eviction algorithm, RLT. As detailed in Algorithm | RLT iterates over each token in every path
T E Q and marks accessed tokens by adding them to marking set (lines 4-7 in Algorithm Once B; + unique tokens have been marked, all marks are cleared except for the most recently accessed token (lines 8-9 in Algorithm [ When a requested token is not in the cache and the cache is full, RLT evicts an unmarked leaf token uniformly at random from the current cache before loading the new token (lines 13-17 in Algorithm!!] D.
Competitive Ratio of RLT. The effectiveness of RLT stems from its use of randomness, which breaks the dependence on query arrival order and enhances robustness against dynamic or adversarial query arrivals, yielding more stable performance. We formally establish its competitive ratio in both single-query and batch processing settings in the following Theorem and corollary| 7
Theorem 6
RLT is (log( B; - comppttitve on worker my with cache capacity B, under single-query processing setting, where is the minimal length over all r E Q.
Corollary 7 (Batch). RLT is O[log( - -ommpeepte on worker my with capacity B₃ under continuous batching setting, where C is the minimal length over all ; E Q. and B is the batchsize.
Our analysis shows that RLT achieves a competitive ratio of (log n). which a logarithmic improve- ment over L-LRU. We further prove that no dependent algorithm can achieve a better competitive ratio than RLT in either single-query or continuous batching settings (Theorem and corollary 9 Theorem 8 (Single-Quesl
No randomized eviction algorithm can achieve competitive ratio better than (log - L)) on worker m, with cache capability of B, in the single-query processing setting, where L denotes the minimal length over all 1 E Q.
Corollary 9 (Batch). No randomized eviction algorithm can achieve a competitive ratio better than (log( B. - -) on worker m, with cache capability of B, in the continuous batching setting, where L denotes the minimal length over all 1 E Q and B the batch size.
4.2 LEARNING-BASED GREEDY ROUTING
To handle dynamically evolving arrivals, we introduce the Learning-Bass Based Greedy Routing (LBGR) algorithm (Algorithm 2 which estimates per-LLM end-to-end latency via an online regression and greedily routes each query the LLM with the lowest estimate.
Overall Cost Formulation. The end-to-end latency Eij of routing query qj to worker m, can be
modeled in the decomposition of Ei Costij + -((--)) Building on this, LBGR estimates this latency via the following predictive model:
Egg
Costaj
PD-1)
estimation
queue loud estimation
residual correction
where Costiy is the estimated service time, p0-1) is the current estimated queue load of m, (sce below), and 0.5 Øsy is a learned regression term (see below) that captures residual latency bias.
Service Time Estimation. Building on the global radix tree in SGLang (which records the cache state of each worker and enables efficient estimation cache hit rates; see Appendix B for futher discussion), we estimate the number of cache-hit tokens for query gj on worker m, as hij. serving as
a proxy for the true hit count h (5 (اا 93) under cache state s(;-1) The estimated service time then:
Costa aCcChed Tui + aMIss (lg) heg))
where we omit the time cost of output token generation and absorb it into the learned residual term.
Queue Load Estimation. To approximate queue load, each m; maintains queue load P. that is updated with each incoming query. When qj is routed to m. (xij = 1), the load incremented as:
pb) p(0-1) + Trjj
Costig-

---

Published as a conference paper at ICLR 2026
Dathe-Jwate-
1.0
1.0
Overrll Lie Rate
10
Normalocs
Normatoo
0.5H
11.8x
0.51
Kod
0.5
Overs life Pare
Nomsliznd
Nomnuiied
Nomalizet Thoight
Nomolasd
Nomalzed
Nomalked
Overa lie Race
Momokzed
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.0
Overa Ht Bake
Noma Rend
Norma Poutin 11F7
Numakkal
2.50
Noma
Thrught
0.5
0.5
2.5
32.00
12.9x
0.0
0.0
0.00
9.0
Figure 2: Results on Llama-3. 1i-ma--.--8BIInstteee (Latency, TTFT, and Throughput normalized for compar- ison). Rows correspond to: GSP (top), ShareGPT (second), UltraChat (third), and Loogle (bottom). For the first four metrics, lower is better; for the last two, higher is better. Our algorithms consistently outperform all baselines across all benchmarks and metries.
To further simulate the natural reduction in queue load over time, we apply exponential decay independently every At O time units: P, < pP,, where p 1) is the decay factor. Upon completion of 4j. LBGR releases any remaining load associated with 9j (line 13 in Algorithm 2b.
Greedy Routing with Online Residual Correction. Latency bias naturally arises from complex environmental factors that are not captured by service time or queue load. To account for these fluctu- ations, learn lightweight residual model for each m, using online linear regression parameterized by 0. For each query Іj. we extract the feature vector di == @hhy. 19 1 hig. p()-1)), and predict
end-to-end latency Eij for all workers [M] using Equation (4. The query gj is then dispatched to the worker with the lowest estimated latency, = arg minke[M] Eig. Upon observing the realized latency Fij. the model is updated online by minimizing the squared loss (Fis F.iy)
5 EVALUATION
Models. Following (Zheng et al. 2024), we evaluate two types LLMs: dense Llama-3. mod- els (Grattafiori et al. 2024) and the sparse (MoE) Mixtral model (Jiang et al. 2024), with model sizes ranging from 8B to 70B. We vary the number of deployed workers from to 10, with 4 workers used the default setting. All experiments for Llama-3.1 --8t--rrrtrtt
10 NVIDIA L40 GPUs, while experiments with Ilama-3. 1aama-3.1-70B---. 1--11-00--nnrreee and Mixtral 8x use NVIDIA H200 GPUs.
Baselines. For the eviction policy, compare RLT with the default L-LRU used in SGLang (state-of- the-art LLM serving system). For load balancing, we evaluate LBGR against three routing algorithms: (i) random routing, (ii) round-robin routing (SGLang 2025c), and (iii) cache-aware routing (SGLang
2025a These combinations yield three baselines: (1) R (2) Round- Lou and (3) LFU where Cache ABaree- the current state-of-the-ars
Workloads. Following (Zheng et al. 2024), we evaluate over 3 distinct prefix-sharing workloads under limited cache memory, spanning both syntheric and real-world scenarios: (1) Synthetic prefix- caching test using the Generated Shared Prefix (GSP) benchmark (SGLang) 2025b); (2) Multi-turn conversations using real-world logs from ShareGPT (shal (023) and UltraChat (Ding et al. (023):
(3) Long-document QA using Loogle (Li al. 2024). We extend these benchmarks by introducing variability in prompt lengths to simulate realistic and challenging serving conditions. The number of output tokens varied from 4 to 128, with 4 used as the default. Furthermore, consider two distinct query ariiall orders: (i) random query order, and (ii) a worst-case round-robin order, with
'e use LRU denote L-LRU baseline for simplicity.

---

Published as a conference paper at ICLR 2026
Not nolleed
Litatio
1.0
Not mollaed
mallaed
Mn TIPE
Now mamallan
Oversil Las Falts
0.0
0.0
0.0
0.0
0.0
3.0
1.0
1.0
1.0
1.0
Ovetrs 1ige Rete
1.0
Noraatzed
Nemaated
Norma mommaazd Pactia Tir
Naroeteed
Barmal Rod Throught
0.5
0.5
0.5
Figure 3: Results on 1amm--.1-70B-Instruue (top) and Mixtral-8 7B-Instruct--vO. (bottom) under
the ShareGPT benchmark. Our algorithms consistently outperform all baselines across metrics.
Rancom-LRU
Round Robin+LRU
Cache Cache_fngrr+4 LRU
Cache RLTrec
LBGR-LRUICUrii
LUGR+RUToOuri
Bemobbed
Modeo lawee
0.50
Rar Parmalio Trea
22.8%
0.0
0.0
0.0
0.00
0.0
Figure 4: Results on Llama- 1.mma-3.11-8 -.-.-3..--I--tttii under the Loogle benchmark with the worst-case round- robin arrival order. Round-robin alternates queries to disrupt KV locality. LBGR+RLT counters this, outperforming all baselines across all metrics.
Random-I
Round-Rohhin-iii
Cache-Awaaee
Nor melieeeee Modton LoMe
Noe malioaa
Vorma OOmmarNN
Not SENNNIE
malioed voorrr
130
STS 8 10111-311102
Figure 5: Results 1--ma--.--BB-I--se- under GSP benchmark with varying request rates.
the random order used by default. All workloads follow Poisson arrival process, and we vary the request rate from 4 to 20 requests/s, with 12 requests/s used as the default.
Metrics. We report four main performance metrics: cache hit rate, throughput, latency, and time to first token (TTFT). For latency and TTFT, we report the median (P50) to reflect the typical user experience and the 95th percentile (P95) capture tail latency. Furthermore, we provide fine- grained breakdown of runtime overhead, reporting time cost for eviction and routing operations, For additional experimental setup details, see Appendix(A)
End-to-End Performance. We present the main results on Llama-3.1 3.10aa33.1--00 1-8B--Intruue across 4 bench- marks in Figure 2 Our methods, Cache-Aware+ LBG and LBGR+RLT, consistently outperform all baselines, achieving the lowest latency and TTFT on every benchmark. On average, LBGR+RLT achieves 30.9 and 44.49 improvements median latency and TTFT compared to Random+LRU, and improves over the state-of- the-ar art latency and 14.06x in median TTFT. For tail performance, it still achieves an average 2.03 improve- ment in P95 latency and 2.62x speedup in P95 TTFT over Rache-Aware+LLU. When applying RLT, Ticche-wwrr+RRL achieves 6.98 x and 6.40x faster than Cache-Aware++LRR latency and TTFT on average. With the learning-basee strategy, LBGR+LRU also outperforms Cache-Aware+LRU, achieving 9.98x lower median latency and 9.58x lower median TTFT on average. Furthermore, LBG achieves the highest cache hit and throughput across all benchmarks, averaging 36.45% % higher hit rate. 36.51 % higher throughput than Cache-Aware++Pee LRU. These results demonstrate the strong and comprehensive efficiency gains of our algorithms under dynamic query arrivals with varying lengths.
Awarr+LLaU by 11.96x in median
median
Model Size & Architecture.
We evaluate the generalizability of our algorithms across model as a representative large dense model and
scales and architectures, using 1imma-3.--70--Inseii Mixtral-8x 7B-Instruct-vO. as a sparse MoE model. As shown Figure 3 our methods consistently outperform all baselines on the ShareGPT benchmark across all metrics. LBGR+RLT achieves the lowest latency and TTFT, reducing median latency by 38% and TTFT by 44.87 compared with the best baseline, and also achieves the highest hit rate and throughput both models. These results demonstrate the generalizability and adaptability our algorithms serving both large dense and sparse MoE models. Additional results on other benchmarks provided in Appendix
8

---

Published as a conference paper at ICLR 2026
Round--RbiinsRR
Cache-Aurare-1Bu
Normstod Modian Wodtor Lanancy
No Rond
HE
5
10
0.0
10
10
Figure 6: Results on Llama-3. 3.1-8B-1--BB. 1--8--Insstrcc under GSP benchmark with varying number of workers
(LLMs), where the r-axis denotes the number of workers.
Random-18u
Bobinn
AuarreiRU
LRGR.BLI
Noltin Lttelyy
Vormtood
Normltod Lewerr
Homerre
Normalood P95
Overal T 2 C
Noemal
85
0.6
0.5 03
0.6
0.5
0.5
03 DJ7 0. 03
0.5 0.5 0.8
Figure 7: Results on Llama-3. -nsttrrrtttttt under GSP benchmark with varying size of KV cache, where the r-axis denotes the percentage of GPU memory used by the KV cache.
Table 2:
Ablation comparison of performance and runtime overhead between Aaahe-Aware+LLUU and our methods on the GSP benchmark. Time-based metries (4) are reported in milliseconds (ms), while hit rate (f) and throughput (1) are measured in percentage and requests per second, respectively.
Method
P50 Latency
P95 Latency P50 ITFT P95 TTFT
Hit Rate Throughput
Average Eviction Time Routing Time
Average
Cache Awaro+LRU
26680.55
46766.77
25022.76
46139.36 36
23.89%
10.73
0.13
0.47
Cache-Aware-RLT (Ours)
19191.25
38917.27
14332.81
37504.69
26.36%
11.05
0.71
0.51
LBGR+LRU (Ours)
6025.11
24561.47
2958.01
21073.78
33.33%
11.80
0.09
1.03
LBGR+RLT (Ours)
2263.61
15334.89
1088.57
11495.05
37.31% %
11.92
1.05
1.45
Query Order. We evaluate the robustness of our algorithms on Loogle under worst-case query arrivals, where queries from each document arrive in round-robin manner. As shown in Figure LBGR+RLT maintains the strongest performance in the worst-case setting, achieving the lowest median and P95 latency and TTFT, and the highest hit rate and throughput compared with all baselines. Notably, it reduces median latency and TTFT by 22.8x and 15.5x compared to Bache-Awaree+uee These results highlight the robustness of our algorithms under adversarial query arrivals.
Request Rate. We vary the request rate from 4 to 20 to evaluate the robustness of our method under different query arrival intensities. As shown in Figure 5 LBGR+RLT consistently achieves lowest latency and TTFT at both median and P95 across all request rates. It also consistently delivers the highest cache rate and throughput across all settings. These results underscore the strong performance and robustness of our method under varying query loads.
Number of Workers. We assess the performance of our algorithms under different numbers of deployed workers (LLMs), varying the number of workers from 2 to 10. As shown in Figure LBG consistently outperforms all baselines across all metrics and settings. Even with as few 2 workers, it maintains leading performance. For throughput, our method is higher when the number of workers is relatively small (e.g., 2 or 4). As the number of workers increases (2 6), the throughput of all methods converges the same value. This is expected: with the request rate fixed at 12 requests/s, once the system has sufficient capacity, all methods can saturate this limit. These results underscore the scalability of our algorithms across varying numbers of deployed workers.
KV Cache Size. We evaluate the impact of the KV cache size by varying the allocated GPU memory percentage from 50% to 90% on L40. As shown in Figure 7 our algorithms consistently outperform all baselines across all metrics and cache size settings. As the cache size increases, the performance gap between our method and the baselines widens significantly. Even under constrained settings (e.g.. using only 50% of GPU memory), method maintains clear Iead. These results demonstrate the robustness and strong performance our algorithms under varying KV cache availability.
Ablation Study on the Effectiveness and Overhead of RLT and LBGR. Table 2 presents detailed analysis of the effectiveness and runtime overhead of our algorithms. Using RLT, Cache-Aware RLT consistently outperforms Tache-Aware+LLe across all metrics, reducing median latency and TTFT by 28.1% and 42.7% %. respectively. This confirms the effectiveness of RLT under dynamic and length- imbalanced query arrivals. Furthermore, adopting the learning- based routing strategy, LBGR+LRU

---

Published as a conference paper at ICLR 2026
achieves even greater gains Cache-Aware+LFUU reducing median latency and TTFT by 77.4% and 88.2%. respectively. This highlights the adaptiveness and effectiveness of LBGR compared to static routing strategies used in SGLang, Combining both algorithms, LBGR+RLT achieves the best performance, reducing median latency and TTFT by 11.8x and 23x, respectively. This shows that integrating learning-based routing with randomized eviction provides strong robustness and performance. In terms of runtime overhead, the total added runtime overhead of RLT and LBGR is only about 2ms per query, which negligible compared overall end-to-en latency. Specifically, for eviction, RLT adds only 0.58ms over LRU with Cache-Aware and 0.96ms when paired with LBGR. For routing, LBGR adds only 0.56ms over Cache-Aware when used with LRU, and 0.94ms when used with RLT. This demonstrates the practicality of our algorithms for real-world deployment.
More Experiments. We present additional results by varying the shared-prefix ratio, number of serving queries, output token length, and maximum batch size, where our methods achieve the best performance across all settings (Appendix Figures T0 to 13). We also conduct two ablations: (i) comparing RLT and L-LRU on a single worker, where RLT shows clear improvements (Appendix Ta- ble and (ii) evaluating the impact of decay interval At, which highlights the importance of timely queue load decay for effective query routing (Appendix Figure 14 See Appendix B for details.
LIMITATIONS AND CONCLUSION
This work presents the first unified mathematical model that captures the core tensions between KV cache eviction and query routing in the KV cache-aware load balancing problem. Our analysis identifies the theoretical limitations of existing approaches and leads principled algorithms that combine provably competitive randomized eviction with learning-basee methods for adaptive query routing under dynamic workloads. We validate proposed algorithms through extensive experiments across 4 benchmarks and 3 different prefix-sharing settings, demonstrating substantial improvements in inference efficiency and notable reductions in end-to-end latency.
One limitation of our current implementation is the lack of evaluation for multi-modal inference. We focus on text-only KV cache and implement our algorithms based on the SGLang codebase, leaving support for multi-modalin for future work. Furthermore, our available computation resources limit the experiments at most 10 workers in a single-domain setup, which may not fully capture the behavior in larger or geo-distributed deployments. Exploring broader scales and additional domains left for future investigation.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
We have taken concrete steps to ensure reproducibility of our results. An anonymized repository is included in the supplemental materials, containing the complete source code, configuration files, and scripts necessary to reproduce the experiments. All implementation details, such as model versions, hardware specifications, and evaluation procedures, are described in Section [5] aadd Appendix The design and implementation of our proposed algorithms are presented in Section 4 and Appendix For theoretical results, complete and detailed proofs are provided Appendix
REFERENCES
Sharegpt dataset., 2023. URL
ShareGPT Vicuna unfiltered
Joshua Ainslic, James Lee- Thorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi-head checkpoints. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, pp. -901,, Singapore, December 2023, Association for Computational Linguistics. doi: 10. 10.18653/v1/200 htt/222222222p... maannlp-minn299.. URL https://aclanthonn
wwtpo//g//2... emnlp ma
2987
Asit Dan and Don Towsley. An approximate analysis of the Iru and fifo buffer replacement schemes.
In Proceedings of the 1990 ACM SIGMETRICS Conference Measurement and Modeling of Computer Systems, SIGMETRICS '90, pp. 143-152, New York, NY, USA, 1990. Association for Computing Machinery. ISBN 0897913590. doi: 00.1144/98457.98522
URL https
adoii.og//00. wtt.oo////............... 11e.1114457777. 98525
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Gpt3.int80: 8- bit matrix multiplication for transformers at scale. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 30318-30332. Curran Associates, Inc., neurips www.ips..c/pappeeeeee cc/paper files//pape/2022 Pappeeeaaaeeeceaaaaaaeeeeeeee Conference pdf
2022. URL https:: File/ cile/c3ba40
Ning Ding, Yulin Chen, Bokai Xu, Yujia Qin, Shengding Hu, Zhiyuan Liu, Maosong Sun, and Bowen Zhou. Enhancing chat language models by scaling high-quality instructional conversations. In Houda Bouamor, Juan Pino. and Kalika Bali (eds.). Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 3029-300200 1051, Singapore, December 2023. Association for Computational Linguisties. doi: 10. 18.1/ 1/t.3/////222..o// wee2222..mmlpmmmm. maannp-main.18... URL Btttp:://aclantholoog org/ 2023. emnlp-ma in. 183/
Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young. Competitive paging algorithms. Journal of Algorithms, 12(4))685-699, 1991.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshom, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong. Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius. Daniel Song. Danielle Pintz, Danny Livshits. Danny Wyatt, David Esiobu, Dhruv Choudbary, Dhruv Mabajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Francisco Guzmán, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Govind Thattai, Graeme Nail, Gregoire Mialon, Guan Pang. Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, lliyan Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jack Zhang, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee. Jeremy Fu. Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua
11

---

Published as a conference paper at ICLR 2026
Saxe, Junteng Jia, Kalyan Vasuden Alwala, Karthik Prasad, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid El-Arini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu, Kunal Bhalla, Kushal Lakhotia, Lauren Rantala- Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz. Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Mahesh Pasupuleti, Mannat Singh, Manohar Paluri, Marcin Kardas, Maria Tsimpoukelli, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoychev, Niladri Chatterji, Ning Zhang, Olivier Duchenne, Onur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng. Prajjwal Bhargava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohan Maheswari, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang, Saghar Hosseini, Sahana Chennabasappa, Sanjay Singh, Sean Bell, Seohyun Sonia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang, Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mihaylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do, Vish Vogeti, Vitor Albiero, Vladan Petrovic, Weiwei Chu. Wenhan Xiong, Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaofang Wang, Xiaoqing Ellen Tan, Xide Xia, Xinfeng Xie, Xuchao Jia, Xuewei Wang. Yaelle Goldschlag, Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song, Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aayushi Srivastava, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Amos Teo, Anam Yunus, Andrei Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchandani, Annie Dong. Annie Franco, Anuj Goyal, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin I Leonhardi, Bernie Huang, Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing I Liu, Bo Wu, Boyu Ni. Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Ce Liu, Changhan Wang. Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Cynthia Gao, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, David Adkins. David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang. Duc Le. Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Tric-Tuan Le, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smothers, Fei Sun, Felix Kreuk, Feng Tian, Filippos Kokkinos, Firat Ozgenel, Francesco Caggioni. Frank Kanayet, Frank Seide, Gabricla Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpem, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hakan Inan, Hamid Shojanazeri, Han Zou, Hannah Wang. Hanwen Zha, Haroun Habeeb, Harrison Rudolph, Helen Suk, Henry Aspegren, Hunter Goldman, Hongyuan Zhan, Ibrahim Damlaj. Igor Molybog, Igor Tufanov, Ilias Leontiadis, Irina-Elena Veliche Itai Gat, Jake Weissman, James Geboski, James Kohli, Janice Lam, Japhet Asher, Jean-Baptiste Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein. Jeremy Teboul, Jessica Zhong, Jian Jin, Jingyi Yang, Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Junjie Wang, Kai Wu, Kam Hou U, Karan Saxena, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kiran Jagadeesh, Kun Huang, Kunal Chawla, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A. Leandro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Miao Liu, Michael L. Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha White, Navyata Bawa, Nayan Singhal, Nick Egebo, Nicolas Usunier, Nikhil Mchta, Nikolay Pavlovich Laptev. Ning Dong, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub, Raghotham Murthy,
12

---

Published as a conference paper at ICLR 2026
Raghu Nayani, Rahul Mitra, Rangaprabhu Parthasarathy, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang, Russ Howes, Ruty Rinott, Sachin Mehta, Sachin Siby, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Mahajan, Saurahh Verma, Seiji Yamamoto, Sharadh Ramaswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng, Shenghao Lin, Shengxin Cindy Zha, Shishir Paril, Shiva Shankar, Shuqiang Zhang, Shuqiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyigbe, Soumith Chintala, Stephanic Max, Stephen Chen, Steve Kehoe, Steve Satterfield, Sudarshan Govindaprasad, Sumit Gupta, Summer Deng, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Koehler, Thomas Robinson, Tianhe Li, Tianjun Zhang. Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vlad lonescu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenchen Wang. Wenwen Jiang, Wes Bouaziz, Will Constable, Xiaocheng Tang. Xiaojian Wu, Xiaolan Wang, Xilun Wu, Xinbo Gao, Yaniv Kleinman, Yanjun Chen. Ye Hu, Ye Jia, Ye Qi, Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang. Yu Zhao, Yuchen Hao, Yundi Qian, Yunlu Li, Yuzi He, Zach Rait, Zachary De Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, Zhiwei Zhao, and Zhiyu Ma. The Ilama 3 herd of models, 2024. URL httthtts: /ata::///axvv... wwwpiii.vrg//bba org/abs 2207 21783
Coleman Hooper, Sehoon Kim, Hiva Mohammadzadeh, Michael W. Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length Ilm inference with kv cache quantization. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural Information Process- ing Systems, volume 37, pp. 1270-1303. Curran Associates, Inc., 2024. doi: 10.52202/ files/paper pdf
079017-0040. URL http:::/prroeedinssseeeeooooo
Patrick Jaillet, Jiashuo Jiang, Konstantina Mellou, Marco Molinaro, Chara Podimata, and Zijie Zhou. Online scheduling for Ilm inference with kv cache constraints, 2026. URL https:
//arxiv. www.:rrgggaaa... /trgg/bb//// 250220002211
Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel. Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie- Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang. Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mixtral of experts, 2024. URL https: http///aavvvvv.e///e//eee/eaaava http//aaiivv...raaeaaaaaeeeeaeee 2401. 04088
Peng Jiang and Gagan Agrawal. linear speedup analysis of distributed deep learning with sparse and quantized communication. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-
and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL ht http:://e//ppccppppceeeeam wtleasnneeeraa nwwrips cc/paper files/ /
Woosuk Kwon, Zhuoban Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP '23, pp. 611 611-626, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400702297. doi: 10.11457360000633613366 I.0.11553360006...
Utt.ttts:://doo org/
Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. Infinigen: efficient generative inference of large language models with dynamic kv cache management. In Proceedings of the 18th USENIX Conference on Operating Systems Design and Implementation, OSDI'24, USA, 2024. USENIX Association. ISBN 978- 1-939133-40-33
Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. LooGLE: Can long-context language models understand long contexts? In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pp. 16304-16333, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.18653/v 1/2024, acl-.og.899. URL https: / antho ogg.oy............ acl long. 85971
13

---

Published as a conference paper at ICLR 2026
Darryl Lin, Sachin Talathi, and Sreekanth Annapureddy. Fixed point quantization of deep con- volutional networks. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), ) Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2858,, New York, New York, USA, 20-22 Jun 2016. PMLR. URL m prwss/ w48/////////////// wtt.......s/////Tmmeaaaa h.tml
https://proceedii htt.://nnnnn....ee///eot.....e
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anas- tasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for Ilm kv cache compression
test time. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 52342-52364, Curran Associates, Inc., 2023. URL htttps://procceednngs..ee neu.edddiinnnunuuriree wwt.eeepppppppppeereeiiiiieeeee.
File aale/a452a/2 FLL.A4422226664eeeeha11111166333 Cowfrreooeeeeeeeeeeeeeeeeee pdf
Ilm d. 11m-d, 2025. URL WtR.:ttpsss//itthb.omm///mmm
NVIDIA. Dynamo, 2025. URL
Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum. The Iru-k page replacement algorithm for database disk buffering. In Proceedings of the 1993 ACM SIGMOD International Conference
on Management of Data, SIGMOD '93, pp. 297-306, New York, NY, USA, 1993. Association for Computing Machinery. ISBN 0897915925.
doi: (0.1145/170035.1000
URL https
7/doi 021/10.1145/1700333 17000
SGLang.
Cache-aware routing, 2025a.
URL https::/github.cco projecct
sqlang
SGLang. Generated-shared-prede -peefxx 2025b. URL https://gituuub.cc///ggggg/
sglang
SGLang. Round-robin routing, 2025c.
Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Re, Ion Stoica, and Ce Zhang. FlexGen: High-throughput generative inference of large language models with single GPU. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning mlr
Research, pp. 3109331003333 31116. PMLR, 23-29 Jul 2023. URL h htttt:::/prccceediiiit press/ vooss/v202/se 2hen22//sheg23a html
Ying Sheng, Shiyi Cao, Dacheng Li, Coleman Hooper, Nicholas Lee, Shuo Yang, Christopher Chou, Banghua Zhu, Lianmin Zheng, Kurt Keutzer, Joseph E. Gonzalez, and lon Stoica. S-lora: Serving thousands of concurrent lora adapters, 2024. URL httphttt:://// //ttxpp.//axxi..../ wwwpexivvv.orgaeae www./ba//aa.a 03285
Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, and Wei Lin. Llumnix: dynamic scheduling for large language model serving. In Proceedings of the 18th USENIX Conference on Operating Systems Design and Implementation, OSDI'24, USA, 2024. USENIX Association. ISBN 978- 188-1-939133 11-939933--0-3.
Ashish Vaswani, Noam Shazeer. Niki Parmar. Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL file
Hao Wu, Patrick Judd, Xiaojie Zhang, Mikhail Isaev, and Paulius Micikevicius. Integer quantization for deep learning inference: Principles and empirical evaluation, 2020. URL httpss///axiv
org/ org/abs/ 2004. 09602
Tian Xia, Ziming Mao, Jamison Kerney, Ethan J. Jackson, Zhifei Li, Jiarong Xing, Scott Shenker, and lon Stoica. Skywalker: A locality- cross-rees region load balancer for Ilm inference, 2025.
URL.tttss: htt.:/ttts///aiiiiei wwtprxivvvoorr/ooo 2505
14

---

Published as a conference paper at ICLR 2026
Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. SmoothQuant: Accurate and efficient post- traiiinnn quantization for large language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato. and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 38087-38099, PMLR, 23-29 Jul 2023. URL
https::/pproceednggs..t mlr ottp:://feceeeclsssss..spssssssp www.///cxxi22...... html
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, 2024. URLhttps: httpppss////ppeeveieeee net/ forum? ftrrummid=NGG55.5 2VF
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In Proceedings of the 18th Anmual Symposium on Foundations of Computer Science, SFCS '77. pp. 222 227, USA, 1977. IEEE Computer Society. doi: 10.1 109/SFCS. URL https //doi.org/ 10. 110./1FCS...SC.. 1977.22
Zhewei Yao, Reza Yazdani Aminabadi, Minjia Zhang, Xiaoxia Wu, Conglong Li, and Yuxiong He. Zeroquant: Efficient and affordable post-training quantization for large-scale transform- ers. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.). Ad- vances Neural Information Processing Systems, volume 35, pp. reur cc cc/paper files/paper Coateerrooefeeecce.po
Curran Asso-
ciates, Inc., 2022.
Zhenyu Zhang, Ying Sheng. Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang "Atlas" Wang, and Beidi Chen. H2o: Heavy-hitter oracle for efficient generative inference of large language mod- els. In A. Oh, T. Naumann, A. Globerson, Saenko, M. Hardt, and S. Levine (eds.), Ad- vances in Neural Information Processing Systems, volume 36, pp. 34661-34710. Curran Asso- ciates, Inc., 2023. UtL/tttss//prrreeennn...ouuuuupp ccppaper ott.a//rcpppppc///pppe.eeeeaaaaa files/paper) 2023/ fi 22207114440001111122222220002232
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. Sglang: Efficient execution of structured language model programs. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet. J. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 62557-62583. Curran Associates, Inc., 2024. doi: 10.52202/ sesppp/eeeppeeeeespppppperrrrr 00024406777887777111100000000060
079017-2000. URL htg. http::////ppoeeeennnnrrrrrrrrrpp
Yiren Zhou, Seyed- MeyseeMohsen Moosavi-Dezfooli, Ngai-Man Cheung, and Pascal Frossard. Adaptive quantization for deep neural network. Proceedings of the AAAI Conference on Artificial Intelligence. 32(1), Apr. 2018 doi: 10. w1t0///aa........11111... URL htt.httss://ooo aaai www..agg/n..e.........ee .org/index
php Php/AAATI arrt www../eweeeeeeee..............oe 11633
15

---

Published as a conference paper at ICLR 2026
A EXPERIMENTAL DETAILS
Models. Following Zhengg et al. 2024), we evaluate two types of LLMs: dense Llama-3.1 mod- els (Grattafiori et al. 2024) and the sparse (MoE) Mixtral model (Jiang et al. 2024), with model sizes ranging from 8B to 70B. The number of deployed workers varies between and TO during evaluation, and is set to by default unless otherwise specified. All experiments for 1rmna-3--8B-Inssiie run on 10 NVIDIA L40 GPUs, while experiments with 1aemma...-7OB-Iniiiiii use 4 NVIDIA H200 GPUs. Unless otherwise specified, we fix the KV cache size to approximately 200k tokens for each model to ensure a fair comparison. We use BF16 precision for all models, and apply quantization to FP8 for Llama-3.1-700 200k-token KV cache. With these settings, the 200k-token KV cache fits naturally within the maximum available GPU memory for --nntrucc- on L40 and Llama-3. 1 1-Instruct--008 on H200 without requiring manual adjustment. For Mixtral, we manually configure the KV memory budget to use 80% of the GPU memory to support a comparable cache size. Unless otherwise specified, we allow each worker to automatically maximize the running batch size (maximum running queries) subject to the available GPU memory.
are and Mixtral 8x
to accommodate memory limitations and maintain
Baselines. For the eviction policy, we compare our randomized eviction algorithm, RLT, against the default adopted L-LRU eviction strategy in SGLang. This choice is motivated by two main reasons: (i) LRU-based eviction is the dominant approach in existing systems (Zheng et al.. 2024 Kwon et al. 2023 [lm d, [025 NVIDIA 2025) and thus represents the mainstream design choice, and (ii) Our implementation builds on the SGLang codebase, which is the state-of-the-arr open-source LLM serving system, and uses L-LRU as its built-in eviction policy. Therefore, comparing against L-LRU is both reasonable and representative, and also demonstrates the effectiveness of our proposed method. For load balancing, we evaluate LBGR against three routing algorithms: (i) random routing, (ii) round-robin routing (SGLang 2025c), and (iv) cache-award aware routing (SGLang. 2025a). Round- robin routing cycles through workers in order, whereas cache-aware routing switches between the highest-hit-rail and the least-loaded routing based on a predefined heuristic -alance threshold. These combinations yield three basclines: (I) Random+LRU, (2) Round-Robin+LAL and (3)
Bache-Aware+LLLU where Becche-Awar+LLFU is the current state-of-the-an
Workloads. Following prior work (Zheng et al.) 2024), we evaluate over 3 distinet prefix-sharing workloads under limited cache memory. spanning both synthetic and real-world scenarios: (1) Synthetic
test using the Generated Shared Prefix (GSP) benchmark (SGLang) 20256);
(2) Multi-turn conversations using real- wollw logs from ShareGPT (sha 2023) and UltraChat (Ding et al. 2023); (3) Long-document QA using Loogle (Li et al. 2024). We extend these benchmarks by introducing variability and imbalance in prompt lengths to simulate realistic and challenging serving conditions. The number of output tokens is varied from 4 to 128 with 4 used as the default.
For the GSP benchmark, we consider 128 groups, each containing 32 queries (a total of 4096 queries) that share the same prefix and prompt length, differing only in their suffixes. To introduce prompt- length imbalance,
assign lengths cyclically across groups using 5 values spanning 3 representative scales: small (512 tokens), medium (1024 and 2048 tokens), and large (4096 and 8192 tokens). All groups share the same prefix ratio, with 4 settings evaluated (0.3, 0.5, 0.7, 0.9) and 0.5 used as the default. For the multi-turn conversation setting, we evaluate two benchmarks, ShareGPT and UltraChat, using 128 clients, each maintaining an independent multi-turn conversation. To capture the imbalance and dynamic nature of real-world conversations, we vary the number of conversation rounds per client across (2, 4, 6, 8), with each round introducing a 1024-token user input (padded as needed to reach the target length). In the long-documd -ongddocmment QA task on the Loogle benchmark, we randomly select 5 512 documents, each paired with the full set of questions. To reflect lnput-length imbalance, we vary the document length by truncating each one to one of four target lengths: (1024, 2048, 4096, 8192) tokens.
Furthermore, we consider two distinct query arrival orders: (i) a random query order, and (ii) worst-case round-robin order. Unless otherwise specified, we use the random order as the default setting, For the GSP and Loogle benchmarks, we additionally evaluate under round-robin order, where we iterate over groups (or documents) in a fixed cycle and issue one query per group/document each turn, repeating this cycle until all queries have been dispatched. All workloads follow a Poisson arrival process, and we vary the request rate from 4 to 20 requests/s, with 12 requests/s used as the default.
16

---

Published as a conference paper at ICLR 2026
Cathe-dwate
Normalocs
1.0
Wemalbee
1.0
1.0
Overall Usee Rete
10
Normaloo
0.5
0.51
Kodd
1.0
Overs life Park
Wommliioe
Nommulied
Nomalizet Thought
Nomolggd
Lakoto
Nomalzed
Nomalaed
Overa lie Race
Momotzed
0.5
0.0
0.0
0.0
0.0
0.0
0.0
Overa He Rate
Noma Rend
Moutin 11F7
Numakked
Noma
02.
0.5
8.5
0.5
22 0.00
0.0
0.0
Figure 8: Results on Llama-3, 1--0B-Instruue (Latency, TTFT, and Throughput normalized for comparison). Rows correspond to: GSP (top), ShareGPT (second). UltraChat (third), and Loogle (bottom). For the first four metrics, lower is better; for the last two, higher is better. Our algorithms consistently outperform baselines across all benchmarks and metrics.
Metrics. We report four main performance metrics: cache hit rate, throughput, latency, and time to first token (TTFT). For latency and TTFT, we report median (P50) and P95. Furthermore, we provide a fine-grained breakdown runtime overhead, including the time cost for eviction operations in L-LRU and RLT, and the routing operations of LBGR.
Implementation. Our implementation based on the SGL.ng--044. codebase, a state-of-the open-source LLM serving system. We implement RLT in Cython to minimize eviction overhead, and integrate LBGR into SGLang's 's cxisting Rust-based cache-aware routing framework as drop-in replacement policy. In the implementation of LBGR, scale the overall time cost estimation per- tktkkn unit to improve regression stability and reduce sensitivity to noise. For service time
estimation (Costi)). ), fix the cached token coefficient aCCACHED 0 per Ik tokens and the uncached token coefficient to aMiss = 1000 ms per 1 tokens. For the background decay thread, smooth the worker queue load using exponential decay with factor p 31 /1/32, updated every 20ms. For the online residual model, we use a 4-dimensional linear regression model with three input features and one bias term, updated online with learning rate of 0.992.
B ADDITIONAL EXPERIMENTAL RESULTS
Model Size & Architecture. We evaluate the generalizability our algorithms across model scales and architectures, using Llama-3.1-700-Instii Mixtral-8x I--nnstruc---OO as sparse MoE model. As shown in Figure X and Figure 9 our methods consistently outperform all baselines across all benchmarks and evaluation metrics. LBGR+RLT achieves the lowest average latency and TTFT, reducing median latency by 5.46 and TTFT by 7.19x compared to the best baseline on 1.ama--.1-70B-Insttruu and reducing both median latency and TTFT by 24.2% % on Mixtral. It also achieves the highest average cache hit rate and throughput on both models. These results demonstrate the robustness and adaptability of our algorithms in serving both large dense and sparse MoE models.
as representative large dense model and
Shared-Prefix Ratio & Number of Shared-Prefix Queries. We evaluate the impact of two key factors related to prefix sharing on algorithm performance: the shared prefix ratio (i.e., the fraction of tokens shared across queries in a group, see Appendix for details), and the number of shared-prefix queries per group. As shown in Figure I0 when varying the shared prefix ratio from 0.3 to 0.9 on the GSP benchmark, our method consistently achieves strong performance across all settings. Even at low sharing (ratio 0.3), method outperforms all baselines by clear margin, and high sharing (ratio 0.9), it continues to maintain the advantage. We further vary the number of queries per shared-preft group from 4 to 128. Figure 11 shows that LBG consistently outperforms all
17

---

Published as a conference paper at ICLR 2026
Normaloss
Molton Lite
1,0
Wemaleed
Meda TTTr
Namelied
1.0
Overall Upe Rete
10
Normatoo
0.5
Overs lift Park 0
Nommuiiad
Nomalbzet
Lakato
Overr li Race
Nomolggd
Nomalked
Momalaze
Nomalaed
Momoazed
0.0
0.0
0.0
0.0
0.
0.0
Overs Ht EaMe
Nomn Rend
homnakad
Moutin 1177
Numekked
0.5
0.5
0.5
0,5
Noma
0.0
Figure 9: Results on Mixtral-8 x In-tnstruct--OO (Latency, TTFT, and Throughput normalized for comparison). Rows correspond to: GSP (top), ShareGPT (second), UltraChat (third), and Loogle (bottom). For the first four metrics, lower is better; for the last two, higher is better. Our algorithms consistently outperform baselines across all benchmarks and metrics.
Bandam-L
Round-Robins1.u
Cache-Auare-
LBC
Normoteed
Normatzed 235 Leenay
Normolens MoROA TIP
Normaloed
Rormalaed
0.50
03
035
0.7
0.9
0.5
0.7
0.
05
0.7
0.9
03
0.5
07
03
0.5
03
0.7
0.
055
07
Figure 10: Results on Llama-3 3.1-8B--.. 1-8B-Inntruct under GSP benchmark with varying shared prefix ratio.
Random LAU
Robin-RabineLe
Cache Aware-- LRU
LBGR ALT
Overgl Hes tade
spomatted
Pl Nommloowe
Moraatedd Masian
Nomaaooo
0.5
0.50
54125
16
54125
54125
16
$4125
10 32
64126
10 B4120
Figure 11: Results on Llama-33 1-1-8B-Instruue under GSP benchmark with varying number of queries, where the z-axis denotes the number of queries per -arrfd-prefix group.
baselines almost all group sizes. As the number of queries per group increases, the performance gap between LBGR+RLT and the baselines continues to widen. These results demonstrate the strong robustness and adaptability of our algorithms under diverse prefix-sharing conditions.
Number of Output Tokens. Figure 12 presents the performance of our method, LBGR+RLT, under varying maximum generated output lengths, ranging from 4 to 128 tokens. The results clearly show that LBGR+RLT outperforms all baselines across all metrics and output lengths, further demonstrating its strong performance under diverse output generation lengths.
We vary the limit on the maximum number of concurrent queries per worker from 64. shown in Figure 13 LBGR+RLT significantly outperforms all baselines across all settings, demonstrating its strong performance under varying batch sizes. Notably, Cache- Awa consistently outperforms Cache-Aware+LRRy across metrics and settings, which validates theoretical analysis transferring in practice: Our eviction algorithm, RLT, achieves a significantly better competitive ratio compared to L-LRU in both the single-query and batch processing settings.
Maximum Concurrent Queries.
Performance of RLT on Single Worker. We evaluate the performance of RLT on a single worker under the worst-case query anrival order in the GSP benchmark, using 64 shared-prefin groups with 32 queries each. B the normalized comparison between L-LRU and RLT, showing that RLT reduces median latency and median TTFT by 45 % and 47 respectively. It also improves tail
18

---

Published as a conference paper at ICLR 2026
Round--obiin-180 Lo
Madian Labancy
tE Rast
Narmalawd po0
Normaloe
0.5
Figure 12: Results Llama-3. -.1---3-.------nntttt under GSP benchmark with varying maximum output token lengths.
Modian Lokand
103
1.0
Nomaated
horma Reod Mosian TIM
Narmatted
Figure 13: Results -amma--.--B-Inntrueee under GSP benchmark with varying limits the
maximum number of concurrent queries processed by each worker.
3000
Ovenll Rake
0.20
8.56
0.44
2000 6.00
60
80
15200
00200
66
80
2020
16.00
10
16
16
18:75
Figure 14: Ablation results on 1aama-3.1-8B-Instruue under GSP benchmark with varying decay
interval At from 10ms 80ms.
Table 3: Comparison of RLT and L-LRU on the single worker under round-robin query arrivals on
GSP benchmark.
Normalized Normalized
Normalized
Normalized
Normalized Throughput
Algorithm
Hit Rate
P50 Latency
P95 Latency
P50 TTFT
P95 TTFT
L-LRU
1.0
1.0
1.0
1.0
6.06 %
0.62
RLT
0.55
0.53
0.55
0.54
41.93%
1.0
performance, reducing P95 latency and P95 TTFT by 45% and 46%. Notably, RLT significantly boosts cache hit rate, achieving 6.92x higher hit rate and 77.4% increase in throughput over L-LRU.
Decay Interval At. To investigate the impact of the decay factor used in LBGR, we vary the decay interval At from 10ms to 80ms. As shown in Figure [4] increasing At leads to a drop in performance. This result highlights the importance of the background decay thread: applying timely qucue load decay enables a more accurate reflection of the current query load state for each worker. Without decay, under weak decay setting (i.e., large At), the estimated queue load becomes stale and less responsive to recent traffic, which degrades routing decisions and overall performance.
C THEORETICAL PROOFS
C.1 COMPETITIVE RATIO OF L-LRU
Lemma 1. In RadixAttention, the amortized number of misses incurred by OPT in a phase To with clean tokens lower bounded by max max(c/2,1],
Proof. We denote by d the number of tokens in the cache of OPT that do appear in the cache of L-LRU at the beginning of phase Tu. Similarly, let e denote the number of tokens in the cache of OPT that do not appear in the cache of L-LRU at the end of phase T..
By definition, there are e clean tokens in T. each of which is not present in the cache of L-LRU at the start of the phase. Thus, each clean token must cause cache miss for L-LRU.
19

---

Published as a conference paper at ICLR 2026
Now, consider the overlap between the caches of OPT and L-LRU at the start and end of T.- At the start of v.- There are d tokens in OPT's cache that are not in L-LRU's cache. Therefore, at least d of the clean tokens are also not present in OPT's cache, which means OPT incurs at least c misses during this phase.
At the end of T.- There are tokens in OPT's cache that not in L-LRU's cache. Two possible types of tokens may remain in L-LRU's cache: (i) ghost tokens that in the first path F processed in 4. that were not accessed at all during % but remained in the cache, and (ii) new tokens accessed during 1. The occurrence of the first type is because the phase boundary may split the first path F between 1--1 and To. Due to the leaf-based eviction behavior of L-LRU, the prefix of T (in phase 1--1) may still exist in the cache even if not accessed in 1v. while its suffix (in 1v) will be evicted first, as evictions target leaf tokens first. Since the entire path I'J must exist in the cache for both OPT and L-LRU after being processed, we denote a as the number of the prefix tokens of J. j. and b as the number of its suffix tokens (new tokens).
Note that the ghost tokens can only exist in the first path I at the end of fe. Suppose that ghost tokens from paths other than r exist the cache. Then L-LRU will only be able to hold B; - a new tokens, requiring space for + more tokens. Since ghost tokens are least recently used, they will be evicted first to make room for the new tokens. As result, L-LRU will evict u such tokens from other paths and from r leaving only b of H (either ghost new tokens) in the cache.
We then analyze the cache state of OPT. The e different tokens in OPT's cache but not in L-LRU's fall into three types: (i) tokens that never exist in the cache of L-LRU from the start to the end of To: (2) y new tokens from T that were evicted by L-LRU; and (3) & ghost tokens from y that were evicted by L-LRU. Thus, we have
+ y Consider the following three cases:
. Casel: When y > O. This indicates that OPT contains the full a ghost tokens. Hence, OPT holds w + a tokens that never appear during Iu. leaving only B; - (w + a) slots to process B; new tokens. Therefore, it must occur at least w + a misses. Since at most tokens from r are evicted by L-LRU, we have + = I a. Thus, OPT must occur at least w + a 2
+ 2 misses.
Case 2: When y 0 and O. Since = >> O, it indicates that and there are only b ghost tokens left in the cache of L-LRU (i.e., 5 = a b----op a)a, and therefore, OPT holds total b+ z ghost tokens in the cache. Therefore, it ocurrs at least + 2 w y+ + w+ misses.
. Case 3: When y = 0 and 0. Then, we have c, and OPT occurs at least misses
Combining the above, the number of misses incurred by OPT in phase To is at least max d, c} > (c d c). Summing over all phases, the amortized number of misses incurred by OPT in a phase
f. is at least c/2. Finally, since OPT must incur at least one miss per phase (because cache of size
B, cannot hold all B, + I different tokens), the amortized number of misses per phase is at least max(c/2, 1).
O
Lemma 2. For any phase 4o with e clean tokens, the number of misses incurred by L-LRU under single-query processing is at most B; - C C assuming no old token reappears after eviction.
Proof. If e 2 L, then B: - L L+c 2 B: Since misses only occur for new tokens and there are at
most B, new tokens in a phase, the maximum number of misses for L-LRU in this case B,, which is bounded by B: f + c.
If e < L, we analyze the maximum number of new tokens that can incur misses. Consider the first path 1,, after processing the initial clean tokens C1.
(a), if I, is completed during the phase, there are at least c new tokens that must be processed that do not incur any misses. This is because I' consists of three components: (i) tokens already stored in the cache, (ii) tokens that might be evicted while loading the initial clean tokens (at most c1), and (iii) its own clean tokens (c2). The second and third parts (which will incur misses) together account for at most tokens, and the first part, at least c tokens, will not result in additional misses. Then, the total number of misses of L-LRU is bounded by B L + c.
As shown in Figure 15
20

---

Published as a conference paper at ICLR 2026
Root
Root
tokens do
ci
at most
fill]
Old taken
Iy least
(not completed)
Tj
(a)
(b)
(c)
Figure 15: Visualizing key ideas in theoretical proofs
I is not completed during the phase, as shown in Figure 15 (b): the maximal number misses for L-LRU is y c1 C2 y/ + c, where y is the number of prefix tokens of J that initially exist in the cache but are evicted when loading the initial clean tokens. Assume there are w prefix tokens from the initial clean tokens, and other distinct tokens remaining the cache that are on the same paths as the initial clean tokens and J- Then, we have
y B, (w + c1)
where 0j is the initial clean tokens. Therefore, the total number of misses can be bounded as
+ c - B; (w +a) + B, = + L c-
(8)
where it follows from = 2 0 and w w C.
Therefore, the maximal total number of misses of L-LRU is bounded by B, L + assuming that no old token reappears after being evicted.
Lemma 3. Under single-query processing in L-LRU, old token reappears in any To after eviction.
Proof. Let us analyze the first occurrence of such case for an old token. This token can be either a leaf or an internal token in path r, As shown Figure 15 (c), assume this old token has prefix tokens, and tokens have been accessed among these prefix tokens during this phase. This indicates that at least B, y + new tokens must have been accessed by the time the old token evicted. To see this, note that if this token is being evicted, all other leaf tokens currently in the cache must have been accessed more recently. Furthermore, because tokens within the same path are processed consecutively, the prefix tokens of these other leaf tokens also more recently accessed.
Since 2 of the old token's 's prefix tokens have already been visited, at least B; - y + 2 new tokens have been accessed the time the old token is evicted. When revisiting this old token, its y prefix tokens must be accessed again, of which z have already been processed. Thus, there are to be assessed before the revisit. In total, this means B, y + + y before the old token is revisited. Therefore, the phase 9. ends here, and case (2) cannot occur.
z new tokens B, tokens accessed
Theorem (Single-Query). Under single-query processing setting, the competitive ratio of L-LRU in RadixAttention worker my with cache capacity B, is upper bounded by (B; - -L + 2) and lower bounded by (B, L+ 1), where C denotes the minimum length over all I3 E Q.
Proof. For the first phase 1, since the cache is initially empty, OPT behaves the same L-LRU. For any subsequent phase %o (v >> 1), we analyze the following two bounds:
Upper Bound. First, note that OPT incurs least max(c/2, misses in any phase % if there clean tokens that phase, according to Lemma] [ Furthermore, by the definition of a phase, where each phase consists of B, distinct tokens, the start of each phase is always associated with path that ends with the clean tokens.
Next, let analyze the maximum number of misses that L-LRU incur for given phase 4. with a clean tokens. A miss can occur in one two cases: (1) a new token appears, or (2) an old token appears after being evicted.
21

---

Published as a conference paper at ICLR 2026
According to Lemma 3
case (2) cannot occur during phase, so according to Lemma 2 the total
number misses of L-LRU is bounded by B, - C +
Therefore, the upper bound of the competitive ratio of L-LRU is bounded by
B: -
max
B; - +
max
Lower Bound. We construct a set of paths that share the same L - prefix but with only one leaf token different. We then repeatedly query 11 2,,,,,,... [B, B,-C+2 in loop. In this scenario, OPT can only incur I miss, while L-LRU incurs B; C + misses in each phase. Therefore, the lower bound for the competitive ratio of L-LRU is B; 1.1.
Based on the proof of single-query processing, we introduce the proof of batch processing.
Theorem 5 (Batch). Consider the continuous batch setting with batch size B. Let Lmaz and denote the maximum and minimum lengths over all , E Q. If 3L S Bi where B; is the cache capacity of worker ms. and all queries in a batch are distinct, then, the competitive ratio of L-LRU in RadixAttention is upper bounded by (B, - C - 3 3) and lower bounded by (B; - C 3 +)..
Proof. We assume that mLmaz < B, which ensures that the cache can always hold ,3 queries simultancously at any point during generation. Based on this, there will be no abnormal evictions, such as evicting the KV values of tokens that belong to queries currently being generated. We now consider the following two bounds.
Upper Bound. According to Theorem consider the scenario where case (2) does not occur. Let us examine the first complete batch S, that follows the initial clean tokens within any phase "- Following the same analysis, if 2 L + 3 - 1, we have B L 3 + 1 2 B, so the total number misses is bounded by B; number of new tokens that can incur misses. If S, completed during the phase, there
B+c+1. I < C 1, we analyze the maximum
at least C+ 3 11 c new tokens that must be processed but do not incur any misses. This is because the tokens in S, can be categorized into three components: (i) tokens already present in the cache, (ii) tokens that may be evicted when loading the initial clean tokens and will incur misses when revisited, and (iii) its own clean tokens that incur misses. The first part, which does not contribute to additional misses, contains at least L + 3 - e tokens. This follows from the fact that the minimal number of distinct tokens in a batch is
Therefore, the total number of misses of L-LRU is bounded
by B, - L 3 c
If Sj not completed during the phase, that is, if any queries in Sj are not finished, then the batch is considered unfinished. In this case, the maximal number of misses can be represented as + where y is the number of prefix tokens of Sy that initially reside in the cache but are evicted when loading the initial clean tokens. This is because, in the continuous batch setting, new queries can be regarded as incurring misses and continuation of those that have already been completed. Let w. be the number of prefix tokens of the initial clean tokens, and let z denote the number of other distinct tokens remaining the cache that are on the same paths as the initial clean tokens and Sj. Thus, the total number of misses is bounded follows:
+ c & B (w + e1) + B, z = L+ 8 -
(10)
where the inequalities follow from 2 and w + 2 L 1-1+B.
Therefore, when case (2) does not occur, the total number of misses of L-LRU is bounded by
B, L 3
Now, consider the first time situation (2) occurs, where a miss is caused by revisiting an old token that has been evicted. It possible that there are multiple old tokens involved, with at most different old tokens evicted and revisited simultaneously. Let us focus on the oldest among them, i.e., the old token that was visited earliest during the phase. Applying the same analysis as Theorem 4 to this oldest token, conclude that, upon revisiting, at least B, new tokens must have been accessed since was evicted. Therefore, the phase % ends here, and case (2) cannot occur again within the same phase.
22

---

Published as a conference paper at ICLR 2026
For OPT, it incurs least max misses, according to Lemma of L-LRU is upper-bounded by
Thus, the competitive ratio
B, - - B, - ++3 max max22/2211
max
(11)
Lower Bound. We construct B, L + 2 paths that share the same L - 1 tokens prefix but with only one leaf token different, [2,,....... :....... -,,.,,BBBCCC [3,-c+2]. Furthermore, we construct B, C +-3 batches, where u-th batch contains paths {I' 12,
We can do the following querying: 1, 1, B; - C - B + 3 batch in a loop. Therefore, for each phase, OPT can only incur miss, whereas the L-LRU incurs B, C - 3 + 2 misses per phase. Therefore, the lower bound for the
competitive ratio of L-LRU is B, - C - +
Discussion of the assumption 3Lmaz I B₁. We assume that 3 I B,, which ensures that the cache can always hold 3 queries simultaneously at any point during running and thus prevents abnormal evictions (e.g.. evicting KV entries for queries that are still being generated). This condition models the capacity constraint in practical LLM systems: GPU memory is limited, so system operators typically choose maximum batch size 33 and context length Lmaz such that their product does not exceed the available KV cache capacity B₁ If instead fLmaz > B, holds persistently, any policy that forms such batches would eventually be forced to evict KV entries belonging to failures. Therefore, our analysis focuses on the well- eel-iprovieooed regime where merr I B,, which accurately reflects real-world configurations and is precisely the setting where the choice of eviction policy has a meaningful impact.
in-progress queries, leading to degenerate cache behavior and a high risk of out-of-
We assume that queries in batch distinct obtain meaningful worst-case analysis for the batched setting. Without any diversity constraint, one can always construct worst-case batches by repeating single query path / times In this case, the behavior reduces the single-query setting and the upper bound of competitive ratio becomes B, - C - 2. In Theorem S it considers all queries in the batch are different, which ensures the batch must contain least L + +
distinct tokens. This exactly leads to the - term in the final upper bound B; L 3 + 3. More generally, one can consider that each batch contains at least d distinct queries, then the same analysis gives an upper bound of B; C - d + 3 with d < 3, which is weaker than the bound in Theorem [ In deployed LLM services, batches are formed from requests arriving within short time window, typically from different users, so batch contents are often diverse and can be reasonably approximated as distinct. Furthermore, due to the stochastic nature of LLM generation, even identical inputs may lead to different output paths, further increasing diversity within batch. Thus, we focus the representative high-diversity case d = 33 where all queries in a batch are distinct.
C.2 COMPETITIVE RATIO OF RLT
Theorem 6 Sangle--uery), RLT is (log( - comppetitieee on worker my with cache capacity B, under single-query processing setting, where is the minimal length over all I E Q.
Proof. First, by Lemma D any algorithm, including OPT, incurs an amortized number of misses of at least max(c/2, 1} per phase. We now bound the expected number of misses incurred by RLT in a given phase. Following the analysis in (Fiat et al. 1991). we partition the B, new tokens into two groups: (1) clean tokens, which are not present in RLT's 's cache at the start of phase 4.. and (2) stale tokens, which are present in the cache at the beginning of % but may be evicted during the phase.
In this setting, miss can occur either when accessing a clean token or when accessing stale token that has been evicted earlier in the phase. To maximize the number of misses, an adversarial request sequence first accesses all clean tokens, causing the eviction of some stale tokens. Subsequent requests to these evicted stale tokens could then incur the maximal number of additional misses. This is because accessing all clean tokens first increases the chance that the stale tokens will be evicted, therefore increasing the number of misses
The number of misses incurred by clean tokens is clearly c. For each stale token, the expected cost of a miss equals the probability that it has been evicted by the time it is accessed. This probability is maximized at c/s, s, where e is the number of clean tokens (i.e., the maximum number of evicted stale
23

---

Published as a conference paper at ICLR 2026
tokens at any moment during the phase), and is the number of stale tokens that have not yet been accessed at that point.
According to Theorem the total number of misses in a phase is upper bounded by min B, C C+ C, Bi). Therefore, the number stale tokens that may incur a miss RLT is at most n = min B, L + c, B.}. Hence, the total expected number of misses caused by stale tokens is upper bounded by:
R Rm
c(Hn - Ho)
(12)
7- w
where H represents the Harmonic number.
Then, the expected number misses incurred by RLT in a phase is upper bounded by c+ cHH Hc). Accordingly, the competitive ratio of RLT is bounded by:
c H Ho)
max
(13)
max/
Assuming which holds in most practical LLM-serving scenarios, the above expression yields a competitive ratio of:
+ (log(B; - C 2)) (Bog(B,- -
(14)
Therefore, RLT is O(log(B: (ofRk-))))coom -comootetiiiee on worker i with cache capacity B, under single-query processing.
Corollary 7 (Batch). ALT is B -oompettieee on worker my with capacity By under 3)-
continuous batching setting, where is the minimal length over all T2 E Q, and B is the batchsize.
Proof. Following the same analysis in Theorem 6 we have that the total number of misses in phase is upper bounded by min B; gives the maximum number of stale tokens that may result in misses in RLT. Accordingly, the total expected number of misses caused by stale tokens is also upper- bounded by:
3 + c c 1, B. Therefore, n min B; L - 3 + c + 1, Be}
R-c-1
c(Hn Ho)
(15)
n-
Then, the competitive ratio of RLT is similarly bounded by:
c cHH, H.)
max
(16)
fc/2,
With L 2 2, we have the following competitive ratio:
θ (log( B; - L 3 + 3)) = θ (log( (B: - - - L)))
(17)
Therefore, RLT is (logg( B; L -3))-competitivv worker i with cache capacity B, under
continuous batching generation.
Next, we show that dependent algorithm can achieve competitive ratio better than (Bo C)) in the single-query processing setting, and (log B, L. ())) in the continuous batching setting. Theorem 8 (Single-Query,, No randomized eviction algorithm can achieve a competitive ratio better than Ologg B, L)) worker m, with cache capability of B; in the single-query processing setting. where C denotes the minimal length over all I E Q
Proof. To establish the lower bound, we apply Yao's principle Yao 1977). Specifically, first show that there exists a distribution of input query paths {x1, T2..... T.. such that any deterministic eviction algorithm D incurs competitive ratio of at least H HB. C+2-
The construction is as follows: each path shares a common prefix of length L but differs the last tail token. We sample each query path r uniformly at random from the index set j E [B; 2).
24

---

Published as a conference paper at ICLR 2026
where [B, - fl....,B, B, - C 2}. Under this distribution, the expected number of cache misses incurred by any D is:
Misssl = B; + n- -B (B,-++1)
12
- C 2 -
(18)
where the first B, terms account for the initial misses for B, tokens, incurred by the (B, - C 1) distinct query paths, the second term corresponds to subsequent misses, where each of the remaining n (B; L + 1) query paths has a probability B,-C+2 of incurring a miss.
Next, by Lemma 1 we have a lower bound on the number of misses incurred by OPT:
MissoPT 2 (max(c/2,1)) 2 V
(19)
where V is the number of phases in the query sequence. When V is a random variable, it follows that [[MissoPT] [E[]]
Since OPT always evicts the token whose next use is furthest in the future, will evict the tail token furthest in the future. Suppose such token is evicted time and reappears at time y. Then, there will be no cache misses between and This is because there are only B; - L + 2 distinct query paths, and the eache can hold most B, - + of them, which means only the evicted path is temporarily excluded. Furthermore, any other tail token must appear at least once between and y: otherwise, it would have been a better candidate for eviction due to its more distant reuse, which contradicts the eviction rule of OPT. Thus, the expected number of queries between two consecutive misses (i.e., between w and yy follows the structure of the classical coupon collector's problem:
B. B.-C+2
Bly w] = -B; - L
Σ
= =(: - L 2) C+2
(20)
which leads to
B[MissoPT] (B; L 2B BB-222
(21)
Therefore, the competitive ratio of any deterministic algorithm D is lower bounded by:
B[MissD] HB,-c+2
(22)
E Missor!
Finally, leverage Yao's principle to establish lower bound for the competitive ratio of any randomized algorithm. Let X denote the random variable representing the input query paths {2,] Then, we have
Ex- (Miss HB,-c+2Bx- (M
(23)
We assume D is the distribution over the deterministic algorithms. Taking the expectation over D D, we have
Ex Ex-sssMissppX")) 2 HB.-c+2Ex (0a-crrExx-MMisoo(((T")
(24)
By the definition of expectation, it indicates that there exists a specific sequence of input paths {x in such that
Ep[Missp((z}])) He.-craMissoor((11)
(25)
Therefore, for any randomized eviction algorithm, its competitive ratio under the single-query processing setting is lower bounded by:
Hn.-c+2= θ (log(B; L))
(26)
Corollary (Batch). No randomized eviction algorithm can achieve a competitive ratio better than O(log(B, (B, - -L- B)) on worker with cache capability of B, in the continuous batching setting, where L denotes the minimal length over all D Q and (3 is the batch size.
25

---

Published as a conference paper at ICLR 2026
first construct B; - C + 2 distinct paths each sharing the same L tokens prefix but differing in their final (tail) token. Based on these paths, define B, C 3 distinct batches, where the u-th batch consists of the paths [2,, 1- I a+ }. J. Now consider the given query batch sequence, (21.:22.....5 ,n where each æ; batch picked uniformly random from the total B; L B batches. Then, the expected number of misses incurred by any deterministic algorithm D is then lower bounded by:
Proof. Following the analysis in Theorem [Tı,Ty,
Missp] B,
(27)
B --
- 3
3 + where this follows from the fact that least B; - 3 initially empty cache.
distinct batches are required to fill an
According to Lemma and Theorem 8 the expected number of misses incurred by OPT satisfies
E [MisSOPT]] (ma 1))] E[]
(28)
where V is the number of phases for the given queries.
Next, note that under the given query batches, OPT only evicts one token at time. This is because each batch contains exactly one unique tail token from the last path I -- and this setup mirrors the single-query setting analyzed in Theorem Therefore, by applying the same analysis, the expected number of tokens between any two misses (say, between w and y) follows:
B, A+3
Ely w|
(B: L C-
Σ
=B. L 8+ B
(29)
which leads to
[|MosTOT
11
(30)
(B, - L B 3) C-C-8+3
Therefore, the competitive ratio of any deterministic eviction algorithm D in the continuous batching setting is lower bounded by:
E M[Miss HR,-C-81
(31)
E Missoot
Finally, by Yao's principle, we conclude that for any randomized eviction algorithm under the continuous batching setting, its competitive ratio is at least
HB. = θ (log(B) B, - C C-))
(32)
D EXTENDED RELATED WORK
KV Cache Optimization. The computational complexity of Large Language Models (LLMM)) in
token generation scales quadratically with sequence length (Jaillet et al., 2026 Ainslie et al. 2023 Vaswani al. (017). KV caching is fundamental optimization that mitigates this complexity by
storing the computed KV pairs for past tokens and reusing them for future queries (Kwon et al. Lee et al. 2024 Sheng al. 2024). However, the limited memory capacity of KV caches remais a bottleneck for long-cone contect generation, where storing the entire historical token context is impractical (Zhang al. [0023] Xiao et al. 2024). Researchers, therefore, have explored memory reduction through quantization techniques that compress cached KV values (Lin et al. 2016 Wu al. 2020 Zhou al.) 2018 Jiang & Agrawal 2018). This involves converting the full full-precision values (c.g.. FP16) stored in the cache to precispeniiioon integer formats (c.g.. INT8) (Yao et al.) 2022 Sheng et al. 2023 Hooper et al. 2024). However, outlier KV values often lead to significant performance degradation during quantization (Dettmers al.) 2022 Xiao al., 2023). This has motivated specialized techniques such as SmoothQuant (Xiao et al. 2023) and KVQuant (Hooper
2023
et al. 2024). which smooth isolate outliers to improve quantization robustness.
KV Cache Management. Recent work on KV cache management falls into two complementary strands. Context-aware methods leverage model-driven signals (e.g., attention weights token
26

---

Published as a conference paper at ICLR 2026
importance) to score tokens, retaining only fixed-budget subset and evicting the rest (Zhang et al. 8023)XXiao et al. 2024: Liu et al., 2023). Representative examples include H2O, which preserves HitterHitters with high attention scores (Zhagg al. (023), and StreamingLLMM which retains initial attention sink tokens that anchor model stability (Zhang et al. 2023 Xíao et al. 2024). While effective at reducing memory, these strategies risk performance degradation
tasks requiring high-fidelity recall, since pruning may inadvertently discard critical long-range context. Another strand is system-oriented and context-agnostic, focusing on improving KV-cache utilization through redesigned memory layouts and management interfaces (Kwon et al. 2023 Zheng et al., (024). vLLM's PagedAttention
virtualizes the cache into fixed-size pages to reduce fragmentation and support efficient sharing under tight GPU memory (Kwon et al. 2023), while Radix Attention uses a radix tree over token prefixes to enable prefix reuse and fine- inneggained allocation/eviccion for high- throughput serving (Zheng et al.) 2024). However, those systems rely primarily on LRU-based policy for KV cache eviction, which is fragile under adversarial or bursty query patterns and can yield negligible hit-rate improvements in the worst case. This reliance, coupled with the lack of formal analysis for ordered, prefix-sharing KV cache structures, reveals gap between practical designs and theoretical understanding in KV cache eviction.
KV Cache-Aware Load Balancing. In multi-LLM serving, balancing queue load while preserving KV reuse gives rise to the problem of KV cache-aware load balancing {Sun al., 2024 Zheng et al., 2024,] Lee et al. (2024). Most systems tackle this with heuristics that trade off cache affinity
against query load (NVIDIA, 2025 Zheng al. 2024] Ilm d 2025). SGLang, for example, employs a rule-based strategy that switches between highest-hil -eahest-hiilrate routing and least-loaded routing based on
predefined load-balance threshold (Zheng et al. 2024). Other systems instead adopt a static linear scoring function that combines prahh-mmach match benefits with current load to guide routing (NVIDIA 2025] [lm d (005)). SkyLB focuses on decentralized deployments, employing per-region coordinators and multi-region prefix trie preserve KV locality across regions (Xia et al. (025). While practical, these methods remain largely heuristic and lack formal modeling for the underlying KV cache-aware load balancing problem, leaving them vulnerable to suboptimal performance under dynamic query patterns.
E DISCUSSION ON GLOBAL RADIX TREE
In our implementation of LBGR, we directly use the cxisting global radix tree in SGLang to estimate the cache hit rate for each worker for incoming query. This global radix tree caches queries at the character level, avoiding tokenization and significantly reducing runtime overhead. It maintains per-worker cache state, where each worker corresponds to subtree consisting of multiple root-to-leaf character paths, and each path may be associated with multiple workers simultaneously. For a new query, performs longest-prefix match against the subtree of each worker and estimates the hit rate based on the character-level match. This estimate may deviate from the true cache hit rate based on the worker's 's token-level cache due two factors: (i) mismatch between character-level and token-level granularity, and (ii) staleness or inconsistency in the shared tree caused by concurrent updates. The same global radix tree also used across all baselines in our experiments, including the state-of-thee -ortte--rtt method. A detailed investigation of this structure and its associated biases is beyond the scope of this work and is left for future research.
F LLM USAGE
We used LLMs only for language polishing and grammar correction. All technical content, theoretical analysis, algorithm design, and experimental results were developed independently by the authors.
27


Reviews:
[{"review_id": "eleW8DyZWB", "reviewer": "Reviewer_HKW6", "summary": "The paper studies the concept of KV caching, which is fundamentally important for serving LLMs. The authors focus on providing a mathematical model to understand the interplay between KV cache hits and query load balancing. They provide theoretical results on the poor worst-case performance of algorithms like Leaf-LRU. They then provide two new algorithms: randomized leaf token (RLT) and learning-based greedy routing (LBGR). This new approach outperforms state", "questions": "See weaknesses", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. LLM KV cache managements and query routing is a very critical problem, and the paper does a good job of choosing an important problem to solve\n2. The paper does quite a good job at piecing together the theoretical underpinnings of KV cache management, which makes the motivation of RLT and LBGR easy.\n3. Section 3.1 does a great job at formalizing the notation and laying the groundwork for further sections. The lemmas are intuitive to understand\n4. The experiments are quite extensive, covering large and small, dense and MoE models. The improvements across the board are strong", "weaknesses": "1. The improvements claims made in the intro should be qualified by model type and size, context length, HBM available etc. Otherwise it is hard to trust these numbers. Please take the time to segment the results into small vs large, dense vs MoE, relationship with context length etc.\n2. Some recent literature reviews are missing. For example, [1]\n3. The figures could be a bit better. For instance, Figure 5 is violating the margin.\n4. The idea of the MIP is not used much throughout the paper, so casting the problem as a MIP seems a bit incomplete", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pw8jZbMtR8", "reviewer": "Reviewer_NRb7", "summary": "The paper proposes a unified model of KV cache–aware load balancing and introduces two algorithms that jointly improve cache hit rate and end-to-end latency. The authors show L-LRU has worst-case O(n) competitiveness while RLT achieves O(logn), and they report large empirical gains across four benchmarks and multiple model sizes.  ￼  ￼  ￼", "questions": "Thank you for the submission. I like the paper overall, the KVCache scheduling topic for load balancing is timely, the theoretical results are crisp, and the experiments are compelling. I especially appreciated the side-by-side algorithms and the clear latency decomposition in LBGR, which make the motivation and mechanics transparent. That said, a few descriptions felt a bit under-explained to me. I’d appreciate clarifications on the following:\n- Theorem 5 assumes βL_{\\max}\\le B_i and that queries in a batch are distinct. How representative is this in deployed systems? What happens to the bounds or behavior when those assumptions are violated?\n- How sensitive are results to the hyper-parameter settings choices across hardware/model sizes? Any guidance for setting them without tuning? \n- Since you normalize many plots, it would help to include at least one table with absolute value so readers can reason about real-world SLOs.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- Clear problem framing that couples cache eviction with routing\n- Strong empirical results across four benchmarks with higher hit rate and throughput￼", "weaknesses": "- Some assumptions are under-discussed (see questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NTisxrgTvQ", "reviewer": "Reviewer_hRYq", "summary": "This paper presents the first unified theoretical model that couples KV cache eviction and query load balancing for multi-LLM serving. It identifies the fragility of LRU-based eviction under dynamic query arrivals and proposes two principled algorithms: RLT, a randomized eviction achieving logarithmic competitive ratio, and LBGR, a learning-based greedy routing method predicting end-to-end latency online.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper is clearly written, and the main problem is well-motivated from a practical LLM-serving perspective.  \n2. This paper provides a combination of a theoretical foundation and practical implementation.\n3. I appreciate that the authors go beyond heuristic system designs and provide a theoretically grounded formulation together with competitive analysis for the cache eviction process.", "weaknesses": "1. As I understand, RLT may be affected by the random seed. It would be better to include an ablation study evaluating the stability of RLT under different random seed settings.\n2. From Figure 6, it appears that the advantage of your method diminishes as the number of workers increases. Could you explain why the proposed approach cannot (or does not need to) scale to a larger number of workers?\n3. Writing: It would be better to include a notation table in Section 3 to improve readability and help readers follow the theoretical formulation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sm81V6LsNf", "reviewer": "Reviewer_yivC", "summary": "This paper addresses the critical trade-off between KV cache eviction and query routing in multi-LLM serving systems. It introduces the first unified mathematical model to formalize this trade-off, identifies theoretical limitations of existing LRU-based eviction policies, and proposes two novel algorithms: RLT eviction and LBGR.", "questions": "1. I am wondering how to run the code? seems the authors do not contain a readme.\n2. The state-of-the-art baseline is \"Cache-Aware+LRU\" from SGLang, which switches between hit-rate and load-based routing using a fixed threshold. Have you compared LBGR to dynamic threshold-based routing (where the threshold adapts to query arrival patterns)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The unified mathematical model fills a critical gap by explicitly coupling local cache eviction dynamics with global load balancing, a connection that prior heuristic-based methods failed to formalize.\n2. RLT’s randomized eviction mechanism is simple to implement, seems simple but works. \n3. The evaluation covers a broad range of scenarios: 4 benchmarks (synthetic and real-world), 3 prefix-sharing settings, model sizes from 8B to 70B (dense and MoE architectures).", "weaknesses": "1. The theoretical analysis notes that L-LRU’s performance degrades with imbalanced query lengths, but the paper does not explicitly evaluate how RLT/LBGR perform across different query length distributions (e.g., heavy-tailed vs. uniform).\n2. The ablation table (Table 1) reports \"Average Eviction Time\" and \"Average Routing Time\" but does not compare these to baselines (e.g., L-LRU’s eviction time vs. RLT’s).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)