acceptodds
Under review as a conference paper at ICLR 2027

CARRIER to CARRY: Modeling KV Cache Dynamics for Provably Stable Routing in Distributed LLM Inference

Abstract

In distributed large language model (LLM) serving, key-value (KV) cache reuse reduces time-to-first-token (TTFT) by avoiding redundant prefill computation, yet exploiting shared prefixes remains challenging because caching affinity tends to concentrate requests on a few instances while pending requests alter the cached context available for subsequent reuse. To formalize this challenge, we introduce CARRIER, a mathematical model to represent request arrivals by affinity group and distributed LLM serving system with cache reuse, retention, and eviction across instances. Building on CARRIER, we develop CARRY, a routing algorithm that learns serving potential, a state function that balances immediate prefix reuse against instance load while accounting for future cache usefulness, thereby enabling a unified theoretical analysis that establishes exponential system stability, proves robustness to bounded perturbations, and quantifies CARRY's capacity advantage over baselines. Experiments across three benchmarks show that CARRY achieves improvements of up to 75.2% cache hit rate, 82.1% and 68.6% of TTFT reductions at P50 and P90, 77.8% and 68.6% of latency reductions at P50 and P90 over the state-of-the-art methods.

Primary area:
reinforcement learning
Keywords:
Large Language Models, LLM Serving, KV Cache reuse, Reinforcement Learning, Request Routing

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DcJ3OpenReview ↗
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
AuthorsOpenReview ↗

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.

Do you think the theory can be rigorously generalized to batch size>1? I believe theoretical guarantee should be used to show insights but not just display beautiful mathematics.

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 BnB_n, Appendix A.4.4 defines RnG=∑J∈Bn(p~J+d~J),RnL=∑J∈Bn(d~J+p~J/υ)R_n^G=\sum_{J\in B_n}(\widetilde p_J+\widetilde d_J), R_n^L=\sum_{J\in B_n}(\widetilde d_J+\widetilde p_J/\upsilon). The analysis uses bounded positive aggregate service rates, 0<μb−≤rnL≤μb+,rnL≤rnG≤υrnL0<\mu_b^-\le r_n^L\le\mu_b^+, r_n^L\le r_n^G\le\upsilon r_n^L, rather than treating a batch of size KbK_b as KbK_b independent GPUs or assuming linear throughput scaling.

Static batching. Each batch contains at most the oldest KbK_b 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)}\lambda\Gamma_{\pi,b}(w)<1, \Gamma_{C,b}(w)\le\min\{\Gamma_{CG,b}(w),\Gamma_{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: span⁡a(ecb)≤Ecb+κcbDw,b(W)\operatorname{span}_{a}(e^{cb}) \le E_{cb} + \kappa_{cb}D_{w,b}(W). Combining the batching drift argument with the action-error comparison used in Theorem 3 gives the sufficient condition λ[ΓC,b(w)+κcb2]<1\lambda\left[\Gamma_{C,b}(w)+\frac{\kappa_{cb}}2\right]<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βaWaGa2\beta_aW_aG_a, 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.

AuthorsOpenReview ↗

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 KK 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 nn, $ 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 K=0K=0, the cache feature uses the current cache; for larger KK, it uses the cache propagated through the corresponding queue prefix. When KK covers the full queue, the original queue-prediction representation is recovered. Here, KK 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 K∈{0,2,8,32}K\in\{0,2,8,32\} 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 KK generally recovers more of CARRY’s performance. The reported imbalance advantage for K≥2K\ge2, 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.

Reviewer_a52kOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents CARRIER, a model for distributed LLM serving that captures queue-dependent KV-cache reuse, retention, and eviction. Building on this model, CARRY routes requests using a learned serving potential that combines effective workload with the expected usefulness of retained cache. The paper derives stability and robustness guarantees under its modeling assumptions and analyzes the stabilization of weight updates. Evaluations in nominal and vidur-based simulators report latency and throughput improvements across conversational, agent, and long-context workloads.

Critical strengths
  1. Meaningful problem formulation. The paper recognizes that cache availability can change while requests wait, motivating routing decisions that account for queue-dependent cache evolution.
  2. Coherent analytical framework. The formulation connects cache reuse, effective workload, and load balancing, enabling a unified analysis of serving stability and robustness to estimation errors.
  3. Lightweight design and broad evaluation. The routing policy uses a compact feature representation, and experiments across multiple workloads, arrival rates, model sizes, and cluster scales provide evidence of improved tail-latency control.
Critical weaknesses
  1. Insufficient isolation of individual contributions. The ablations mainly establish the importance of workload features and congestion penalties, without clearly isolating the benefits of TD learning against equally informed fixed math policies.
  2. Lack of production baselines. Although Min-TTFT and DualMap are included, the evaluation omits other relevant industrial approaches such as Dynamo and LLM-d's mechanisms.
  3. No reported real-system validation. All reported end-to-end performance results rely on profile+simulation, with no small-scale real GPU serving deployment to validate the gains. While I understand a hundred-GPU scale experiment is impractical, even a modest experiment would substantially strengthen confidence that the improvements persist under actual scheduling, cache dynamics, and routing overhead.
Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer a52k

We appreciate your careful feedback, which helped us better isolate our learning component and extend our empirical benchmark suite.

W1. Insufficient isolation of individual contributions.

The ablations haven’t clearly isolated the benefits of TD learning against equally informed fixed math policies.

Thank you for pointing out that removing workload features does not, by itself, isolate the contribution of TD learning.

We added a complementary ablation that retains CARRY’s feature representation but removes TD-based weight learning. Specifically, Figure 11 evaluates eight randomly sampled fixed-weight configurations on ShareGPT over four seeds and reports the average performance of these equally informed fixed math policies.

As shown in Figure 11, CARRY achieves better P99 TTFT, P99 latency, cache hit rate, and load imbalance compared with the averaged fixed-weight baseline.

We take this result as empirical evidence for the incremental benefit of TD-driven weight learning. We have revised our manuscript wording in Appendix A.5.

W2. Lack of production baselines.

The evaluation omits other relevant industrial approaches such as Dynamo and LLM-d's mechanisms.

Thank you for suggesting these important industrial baselines.

We have incorporated Dynamo-KV and llm-d into both the modeling-consistency experiment and the main evaluation in Section 5.

Across the three scenarios, CARRY reduces P95 TTFT in Table 1 by 5.4%–37.7% relative to Dynamo-KV and 6.3%–47.4% relative to llm-d. All policies run under identical workloads, cache capacities, arrival rates, and random seeds, and CARRY maintains a higher average cache hit rate on all three datasets.

These results extend our comparison to the routing mechanisms you pointed out. Table 1 and Figure 3 present the complete comparison.

W3. Lack of real-system validation.

All reported end-to-end performance results rely on profile+simulation, with no small-scale real GPU serving deployment to validate the gains.

We appreciate this important distinction. We agree that even a modest live GPU deployment would offer complementary evidence that profiling and simulation cannot provide.

Our practical simulator is built upon Vidur, whose execution model integrates hardware profiling, runtime prediction, and event-driven scheduling. Our extension adds affinity-group-aware cache, retention, reuse, and eviction dynamics, and the nominal simulator is calibrated separately using traces collected from the practical simulator. We have also added static- and continuous-batching simulation experiments to evaluate our routing policy.

We therefore explicitly treat live-system deployment as a valuable orthogonal validation left for future work, rather than framing our extended simulation results as its replacement. The revision reinforces empirical evidence within our controlled simulation setting and makes these scope boundaries explicit in Appendix A.5.

Thanks for the response and the added experiments.

W3 remains unresolved, since there is still no end-to-end evaluation on a real serving system. After reading reviewer DcJ3’s comments, I’m also more concerned about whether the assumptions that over-simplified batching and cache preservation fit in reality. Those are easy to satisfy in simulation, but I don't believe it will carry to real-deployment.

Based on above, I also don’t think W2 is fully resolved yet. The batching settings used for Dynamo and llm-d are still unclear. If it is still batch size 1 or 4 with static batching, the results are not convincing to me.

For these reasons, I’ll keep my scoring.

AuthorsOpenReview ↗

Clarification

Thank you for your thoughtful follow-up and continued consideration. We appreciate your emphasis on practical applicability and would like to offer a few clarifications regarding our additional evaluations.

Regarding W2, we agree that comparisons with industrial serving approaches are important. Dynamo and llm-d are comprehensive distributed serving frameworks, while our work primarily focuses on cache-aware modeling and routing policy design. To ensure a meaningful and controlled comparison, we have incorporated their corresponding routing mechanisms into both the modeling consistency evaluation (Figure 2) and the routing performance evaluation (Table 1 and Figure 3), under identical serving conditions. These additions directly address the modeling and routing aspects relevant to our contribution, and the results consistently demonstrate CARRY's advantages.

We also recognize the importance of batching in practical serving. Our main experiments isolate routing-policy differences under a common serving configuration, while Figure 6 additionally evaluates CARRY under both static and continuous batching, providing complementary evidence of its effectiveness under more complex serving dynamics.

Regarding W3, our evaluation uses application-derived workloads and a practical simulator built upon Vidur's hardware-profiled execution framework. This design aims to connect our analytical model with more realistic serving behavior while maintaining controlled and reproducible comparisons.

We sincerely appreciate your constructive feedback, which has helped us strengthen the evaluation. We hope these clarifications and additional results provide a clearer picture of the scope and contributions of our work.

Reviewer_xTdmOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies a really important problem in a distributed setup where there are replicas of an LLM, and LLM serving is required. How does one enable the best KV cache reuse? The authors introduce two things: carrier and carry. Carrier is a mathematical model, and carry is an algorithm that helps different objectives compete with each other.

The authors conduct several experiments across a simulator for various kinds of setups and present substantially improved results.

Critical strengths
  • The paper tackles a really important and relevant problem: how does one do distributed serving of large language models for KV cache reuse, especially for time to first token for prefill?
  • The abstract is very well written, and the keys of the method are very clear.
  • The framing of the problem is quite good, and the theoretical analysis is pretty solid. I enjoy reading the theorems.
  • The experimental simulation results show meaningful P95 prefill improvements across various datasets.
Critical weaknesses
  • I felt that the details in the related work section are a bit limited. There are other works on LLM profile optimization, and also SGlang has work on sticky routing.
  • Other prior works seem a bit limited and are not compared in the experiment section.
  • It would have been nice to present real-world data experiments to further bolster the paper. This, to me, is the most critical issue with the paper.
Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer xTdm

We appreciate your careful reading and constructive feedback, which helped us strengthen both our discussion of related work and empirical evaluation.

W1. Limited details of related work.

The details in the related work section are a bit limited.

We appreciate this suggestion to enrich our contextual discussion.

We have expanded Section 1.2 to draw clearer distinctions among several complementary lines of prior work: profile-driven serving configuration optimization (AIConfigurator), hardware-software serving simulation (LLMServingSim), sticky and session-affinity routing (SGLang), prediction-free and short-horizon routing (BalanceRoute), plus the industrial routing designs adopted in Dynamo and llm-d.

Beyond adding these citations and discussions, we have also extended our empirical comparisons: Dynamo-KV and llm-d are now integrated into our main evaluation, as elaborated in W2.

W2. Limited prior work.

Other prior works seem a bit limited and are not compared in the experiment section.

Thank you for encouraging a broader empirical comparison.

We have incorporated Dynamo’s KV-aware routing policy (Dynamo-KV) and the routing configuration from llm-d into Figure 2(a), Table 1, and Figure 3.

All baselines run on identical request streams, with matched cache capacities, arrival rates and random seeds. In Table 1, CARRY cuts P95 TTFT against Dynamo-KV by 5.4%, 20.9%, and 37.7% on ShareGPT, LooGLE, and OpenHands respectively; the corresponding improvements over llm-d are 6.3%, 32.5%, and 47.4%. CARRY also attains higher average cache hit rates across all three benchmarks. Figure 2(a) further validates that our affinity-group abstraction aligns closely with the cache representations used for these baselines: the resulting P50/P90 TTFT gap stays within 1% across tested setups.

These new results demonstrate that CARRY’s gains are not restricted to the original academic baselines.

W3. Real-world data experiments.

It would have been nice to present real-world data experiments to further bolster the paper.

We appreciate this point on experimental realism, we agree that the provenance of both the dataset and the execution model should be explicit.

Our three datasets are not simple synthetic draws over request sizes. ShareGPT consists of publicly shared multi-turn user conversations. The OpenHands workload captures agent–tool interaction traces; we now specify the exact trajectory release and task subset in Appendix A.5. LooGLE supplies long-context tasks built upon authentic source material including research papers, Wikipedia entries and transcripts.

We keep the native ordering of requests inside each affinity group, while independently configuring arrival timings to sweep over different offered loads. In this setup, request content and application-level patterns are data-derived, while arrival processes and serving execution remain controlled experimental components, to conduct experiments across a wide range of system load regimes.

Our practical simulator extends Vidur with explicit modeling of cache retention, reuse and eviction, while retaining its event-driven, hardware-profiled execution backbone. The nominal simulator is calibrated using traces collected from this practical simulator.

We have spelled out these boundaries in the “Application Scenarios” and “Simulation Infrastructure” paragraphs of Appendix A.5. These refinements better ground our evaluation.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General Response

We thank the reviewers for their thoughtful feedback, which has helped us substantially improve the paper. Our revision focuses on isolating the contributions of the routing design, broadening the empirical evaluation, and clarifying the scope of the theoretical and practical claims.

G1. Broader baselines and related work. We incorporate the routing configurations of Dynamo and llm-d into our modeling-consistency study and main evaluation (Figure 2(a), Table 1, Figure 3). Within our unified setup, CARRY reduces the P95 TTFT in Table 1 by 5.4%–37.7% compared with Dynamo-KV and by 6.3%–47.4% compared with llm-d across the three benchmarks. Moreover, related work in Section 1.2 is extended to discuss profile-based configuration optimization, serving simulation, sticky routing, and short-horizon routing.

G2. Ablations of TD learning. Figure 11 introduces a no-TD policy that shares the same feature representation. On ShareGPT, we evaluate eight randomly sampled fixed-weight configurations across four random seeds and report their averaged performance. CARRY improves tail latency, cache hit rate, and load imbalance over this baseline. This result isolates the benefit of TD learning beyond equally informed fixed math policies.

G3. Batching and partial prediction. Proposition 1 and Appendix A.4.4 extend our analysis to static batching and continuous batching under explicitly stated service, cache-preservation, and approximation-error assumptions. Figure 6 evaluates a policy trained under static batching on both static- and continuous-batching practical simulators, with batch size 4 and results averaged over four seeds. Appendix A.3 and Figure 7 further investigate CARRY-P for queue-prediction depths K∈{0,2,8,32}K \in \{0, 2, 8, 32\}, revealing a load-dependent trade-off between limited horizon and the quality of cache-aware routing.

G4. Evaluation clarification and scope. Our workloads of benchmarks are derived from ShareGPT, OpenHands, and LooGLE, and our practical simulator builds upon Vidur’s hardware-profiled execution framework. We clearly separate request content from the originating applications, configured arrival processes, and simulated execution.

Area_Chair_2R5XOpenReview ↗

Reviewers: please respond to the author rebuttal

Dear reviewers,

The authors have posted responses to your reviews. The author-reviewer discussion closes on November 18 (AoE).

Please read the responses and reply here before then: let the authors know whether your concerns have been addressed, what remains open, and whether you are updating your score. If your assessment is unchanged, please say so explicitly. Engaging with the other reviews is also welcome.

Thank you, Area Chair

Area_Chair_2R5XOpenReview ↗

Final reminder: discussion closes today (Nov 18 AoE)

The author-reviewer discussion closes today, November 18 (AoE).

Dear reviewers,

None of the reviewers has yet responded to the authors' rebuttal on this paper. Please read the authors' response and post a brief reply here before the deadline: whether your concerns have been addressed, what remains open, and whether you are updating your score. If your assessment is unchanged, please say so explicitly. Your response is important for the final recommendation.

Thank you, Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.