- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The paper studies the cache-aware routing in LLM serving. The setting is: there are several replicas with PD mixing, when a request arrives at the global router, it optimizes this routing decision. For this routing, there are many baseline policies, such as join shortest queue, round robin, cache aware, power of-2, and recent load balancing algorithms. The paper contains a credible operational idea: a router should evaluate the cache that a request will encounter when it is served, rather than only the cache visible when it arrives. Then, it follows with some theoretical results and numerical experiments.
Critical strengths
The paper studies the cache-aware routing with an analytical perspective.
The theoretical results are rigorous.
The numerical experiments are run from real hardware.
Critical weaknesses
I think the authors should spend more efforts explain the routing policies' intuition rather than providing rigorous theoretical guarantees. The reason is that, for the current theoretical guarantee, it assumes that the batch size is 1 in each GPU replica. This never happens in real, even if in huge KV peak workloads such as multi-round LLM serving/agent serving, I never see any experiment taking batch size=1. This obviously makes theoretical contribution plausible. However, what is the purpose for theoretical guarantee? I believe theoretical guarantee should be used to show insights but not just display beautiful mathematics.
Moreover, the routing policy mentioned by this paper requires a lot of information, e.g. the whole decode length which is hard to predict accurately in real (since a same prefill can lead to different decode length). I found a recent LLM routing paper accepted by Neurips 2026 (Bu et al. 2026, https://arxiv.org/abs/2605.06113), asking one crucial question: How much lookahead is actually necessary for cache-aware LLM routing? That paper suggests routing does not require knowing the entire future. A sufficiently accurate short-horizon prediction can already be enough to make a much better current assignment. From my real engineering experience, predicting the whole decode length is usually inaccurate, and the policies based on full decode length information can be extremely not robust.
Questions for authors
Do you think the theory can be rigorously generalized to batch size>1? I guess this can be quite hard.
Is it possible to incorporate the partial prediction idea to your routing policy? I think that paper cares about load balancing, which does not care about much on cache-aware cases. I believe if these ideas can combine, it can improve the LLM routing significantly.
If these questions can be discussed deeply, I will increase my score.
2 comments
Response to Reviewer DcJ3 (2/2)
W2&Q2. Partial prediction and algorithm practicability.
Is it possible to incorporate the partial prediction idea to your routing policy? The routing policy mentioned by this paper requires a lot of information.
Thank you for suggesting the connection to short-horizon routing. We agree that practical routing should not rely on an accurately known complete future output.
We added Appendix A.3 to separate observable inputs from estimated quantities and introduced the partial-prediction variant CARRY-P.
Algorithm practicability. Among the information that our routing policy relies on, prompt length and prefix metadata, queue order, generated-token progress, and current cache telemetry are observable at routing time. Future decode length—including the unfinished decode portion of an active request—is not directly observable and must be estimated. Future retained cache and serving-time cache hits also depend on uncertain completion, retention, and eviction dynamics.
Partial prediction. BalanceRoute motivates limiting future information for load-aware assignment. Our adaptation limits queue-dependent cache/workload propagation: only the first waiting requests contribute predicted effective workload and propagated cache transitions; later requests contribute their known prefill sizes. Specifically, for the post-decision waiting queue of instance , $ W_n^{P,K} = R_n^G + \sum_{i=1}^{\min(K,r_n)}G_{n,J_{n,i}} + \sum_{i=\min(K,r_n)+1}^{r_n}p(J_{n,i}). $ For , the cache feature uses the current cache; for larger , it uses the cache propagated through the corresponding queue prefix. When covers the full queue, the original queue-prediction representation is recovered. Here, counts waiting requests, rather than decode steps. The adaptation therefore limits queue lookahead. Its cache-aware component is the retained-context and cache-hit evolution within the predicted queue prefix.
What the experiment shows. Figure 7 evaluates on OpenHands across four seeds. Selected finite-horizon variants approach CARRY more closely at the lowest tested load, while the latency and cache-hit gap widens as arrival rates increase. Larger generally recovers more of CARRY’s performance. The reported imbalance advantage for , together with lower cache reuse, reveals a stronger load-balancing tendency. Thus, limited prediction is not uniformly sufficient: the useful horizon depends on queue pressure and the importance of delayed cache reuse.
Connection to robustness. Theorem 3 gives error-adjusted stability conditions for the specified decode-size and cache-action errors. This motivates analyzing imperfect predictions, but does not automatically certify every horizon-truncated policy: omitted queue work can accumulate, and its induced action error must satisfy the theorem’s bound. We therefore use Figure 7 as an empirical horizon-sensitivity study, rather than claiming an unconditional stability guarantee for all CARRY-P variants.
This addition turns the suggested connection into a concrete design trade-off: shallow lookahead reduces future-information requirements, whereas deeper cache-aware propagation becomes more important under contention. It also identifies where a practical short-horizon predictor would be most useful.
Response to Reviewer DcJ3 (1/2)
We appreciate your thoughtful questions on the scope of our theoretical guarantees and the practical information requirements of the routing policy.
W1&Q1. Batching extension and theoretical insights.
We appreciate this important distinction between formal guarantees and actionable routing insights. We agree that our original single-request abstraction limited the scope of the analysis.
We have added a batching extension together with supporting experiments.
Model extension for batching. Section 2.2 now extends the representation through aggregated active-batch residual work and ordered cache transitions. For a batch Bn, Appendix A.4.4 defines RnG=∑J∈Bn(pJ+dJ),RnL=∑J∈Bn(dJ+pJ/υ). The analysis uses bounded positive aggregate service rates, 0<μb−≤rnL≤μb+,rnL≤rnG≤υrnL, rather than treating a batch of size Kb as Kb independent GPUs or assuming linear throughput scaling.
Static batching. Each batch contains at most the oldest Kb waiting requests, remains fixed until completion, and starts immediately when an idle instance has waiting work. Under the coupled cache/service and boundary-update conditions stated in Appendix A.4.4, the action-increment decomposition is preserved. Theorem 2’s drift argument then yields λΓπ,b(w)<1,ΓC,b(w)≤min{ΓCG,b(w),ΓLB,b(w)}. This is the static-batching statement in Proposition 1.
Continuous batching. We additionally require FIFO refill at completion boundaries, preservation of earlier cache outcomes and completed service, a positive per-request completion-rate bound, and a controlled discrepancy between the continuous-batch action increment and its static-batch approximation: spana(ecb)≤Ecb+κcbDw,b(W). Combining the batching drift argument with the action-error comparison used in Theorem 3 gives the sufficient condition λ[ΓC,b(w)+2κcb]<1. Thus, the continuous result uses the static-batch representation as a controlled approximation. The proof and the additional notation are in Appendices A.4.4 and A.1.
Theoretical insights. Theorem 1 quantifies the trade-off: cache reuse reduces required service work, whereas instance-level imbalance reduces the stability margin. Consequently, maximizing cache hits alone need not improve sustainable serving load. The action increment underlying Theorem 2 contains 2βaWaGa, showing why the same incoming effective work is more costly on an already congested instance. The cache-usefulness terms account for how an assignment changes retained context. Theorem 3 then explains the cost of imperfect information through a contraction of the certified capacity region. Theorem 1 supplies a necessary outer condition; Theorem 2 and Proposition 1 supply sufficient inner conditions. An actual separation from a baseline follows only when CARRY’s sufficient condition holds and that baseline has a negative stability margin.
Empirical evaluation under batching. In Figure 6, we train CARRY in the static-batching nominal simulator and evaluate the resulting policy in practical simulators with static and continuous batching, using batch size four and four random seeds. CARRY obtains lower reported TTFT quantiles, higher cache hit rate, and lower imbalance than Cache Greedy and Load Balance in both tested modes. These experiments support the transfer of the routing benefit to the evaluated batching settings.
Together, these additions broaden the modeling and theoretical scope of our work beyond single-request serving under explicit assumptions, clarify how the analysis guides cache-aware routing, and strengthen the empirical evidence for CARRY in both static- and continuous-batching settings.