acceptodds
Under review as a conference paper at ICLR 2027

Efficient LLM Inference Rescheduling via Progressive KV Cache Migration

Abstract

In multi-instance large language model (LLM) serving, dynamic request arrivals and unpredictable autoregressive decoding can create runtime resource inefficiencies such as GPU external memory fragmentation and load imbalance, complicating low-latency serving under high load. Runtime rescheduling can mitigate such inefficiencies by moving active requests across GPUs, but existing live-migration mechanisms require the full KV cache to be transferred before the source-side memory can be released. As a result, rescheduling decisions may take long to become effective, limiting their ability to promptly adjust resource allocation under evolving resource pressure. This paper revisits whether destination-side decoding must wait for full KV cache transfer. We observe temporal sparsity stability, where partial KV cache remains important over a short decoding window. With this property, the destination can resume decoding after receiving the temporally stable critical KV cache, while the remaining KV cache is refilled in the background. This enables earlier request handoff and source-side memory reclamation. So we design KVFlow, a rescheduling system for progressive KV cache migration. KVFlow exposes lightweight block-level attention statistics, selects migration-friendly requests with stable critical KV cache, and progressively refills the remaining KV cache after handoff. Our evaluation shows that, compared to a state-of-the-art rescheduling system, KVFlow reduces migration handoff latency by up to 6.89 and lowers migration-time KV cache footprint by about 30%, while preserving generation quality. In the main mixed-workload evaluation, compared with Llumnix, KVFlow reduces mean time-to-first-token (TTFT) by up to 24.0% and reduces P99 request latency and P99 TTFT by 27.1% and 47.3% on average, respectively.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Rescheduling, LLM Serving, MLSys

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_pJZNOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the problem that runtime request rescheduling in multi-instance LLM serving is slow to take effect: existing live-migration systems (e.g., Llumnix) can only hand off a request and release source-side memory after the entire KV cache has been transferred, which can take over 16 seconds for a 32K-context request on Llama-3.3-70B.

The authors make a key observation — temporal sparsity stability: a small, attention-weight-selected "critical" subset of KV pages remains useful over a short decoding window (mean cosine similarity > 85% for ~20 decoding steps), and delaying refill degrades generation quality while early refill preserves it. Building on this, they design KVFlow, a rescheduling system with three components:

  1. Progressive KV cache migration protocol — a three-stage process: (i) transfer the critical KV subset while decoding continues on the source; (ii) brief pause-and-handoff with incremental KV and metadata, after which the destination resumes decoding and the source releases incorporated blocks; (iii) background refill of the remaining KV blocks, with out-of-order arrival handled via PagedAttention block-table remapping.
  2. TiDEX scheduling — selects migration candidates by a benefit score (useful memory relief capped by the release target, divided by critical-subset size) plus a temporal-stability check (top-K hit rate ≥ 0.60 and JS-shift ≤ 3% over snapshots 16 steps apart).
  3. Lightweight block-level attention extension — records compact prefix ratios W_i = P_i/l_i inside FlashAttention's online softmax and reconstructs globally normalized block weights in O(T_c) via a reverse suffix-product scan (with a split-KV extension using per-split LSE values).

On a 24-GPU RTX 3090 cluster and an 8-GPU A800 server, KVFlow reduces handoff latency by up to 6.89×, lowers migration-time KV footprint by ~30%, and releases source-side cache 1.96–4.49× faster than Llumnix; in end-to-end mixed workloads it cuts mean TTFT by up to 24.0% and P99 TTFT by 47.3% on average versus Llumnix, at near-lossless generation quality and ~0.014 ms/attention-computation overhead.

Critical strengths
  1. A well-motivated and quantified problem: The paper empirically demonstrates that live-migration completion time (6.2–16.7 s at 32K context) renders runtime rescheduling ineffective precisely when it is most needed — queueing latency and TTFT barely improve during the high-load interval, and each migration incurs ~166 MB of extra duplicated memory.
  2. A novel and practically valuable observation — temporal sparsity stability: The key insight that critical KV pages remain useful for tens of decoding steps (unlike one-step spatial sparsity in prior work such as InfiniGen/QUEST) cleanly decouples request handoff from full cache transfer, and is validated with attention-similarity, generation-quality, and per-request heterogeneity experiments.
  3. A complete, well-engineered system: KVFlow is implemented on top of Llumnix/vLLM and covers the full stack — a three-stage migration protocol with out-of-order block-table re-mapping and partial source-side release, a two-level scheduler (global pair selection + TiDEX request/subset selection), and a zero-overhead-attention attention-statistics extension compatible with FlashAttention's online softmax, including Split-KV execution.
  4. Safety-aware request selection rather than indiscriminate early handoff: The paper honestly shows that unconditional progressive migration degrades quality (score drop 0.279→0.272 / 0.357→0.299), and TiDEX's hit-rate + JS-shift filtering demonstrably selects requests with much smaller score drops (0.011 vs. 0.047 on M7B/Gov).
  5. Comprehensive evaluation with actionable benefits: Results span handoff latency, memory footprint, defragmentation, load balancing, and end-to-end serving across two hardware platforms, two migration backends (Gloo/NCCL), and multiple models — with the preemption-reduction results (1 vs. 94 preemptions at 6 QPS on MATH-500) particularly compelling.
Critical weaknesses
  1. No analysis of "refill time vs. stability window" mismatch: The critical KV subset is only stable for roughly ~20 decoding steps (Figure 4a), but background refill of a 32K-context cache may take far longer than 20 steps — the subset may "expire" before refill completes. The paper shows that late refill degrades quality (up to 9.43%), but provides no mechanism or analysis for what happens when refill speed cannot keep up with the stability window (e.g., re-selection, throttling handoff, or partial attention correction).
  2. "Non-faithful output" during refill is acknowledged but not analyzed: Appendix A.2 (Lines 795–798) explicitly states that decoding during refill "is not guaranteed to reproduce full-KV outputs." For reasoning workloads with long chains of thought (e.g., MATH-500), small deviations in early tokens can cascade. The paper offers no output-consistency analysis, rollback mechanism, or characterization of when deviations propagate.
  3. The cost of TiDEX filtering is understated: Figure 5(d) shows only 26%–80% of requests pass the stability check, and Figure 5(b) shows that without filtering, up to 62% of requests (Q32B/Gov) drop more than 0.02 in score. In other words, the system is "afraid to migrate" a substantial fraction of requests, which shrinks the method's applicability — this limitation should be quantified in the abstract/conclusion and its effect on rescheduling coverage under pressure analyzed.
  4. Partial-cache decoding quality is only evaluated on a limited set of workloads: The motivation experiments use Mistral-7B (ROUGE-L) and Qwen3-4B-Thinking (MATH-500) at a fixed top-25% retention; sensitivity to model family (e.g., models with strong positional/attention drift), attention patterns (e.g., retrieval-heavy or multi-needle tasks), and longer generation horizons remains unexplored.
  5. End-to-end benefit derives from a small migrated fraction (~1%): The headline serving gains come from migrating only ~1% of requests; the paper does not report the behavior when migration demand is high (e.g., many simultaneous OOM-threatening requests), where TiDEX filtering plus refill bandwidth contention could dilute the benefits.
Questions for authors
  1. Refill speed vs. stability window: How long does background refill actually take for a 32K-context request relative to the ~20-step stability window, and what is the fallback policy when the critical subset "expires" before refill completes? Is re-selection of a new critical subset from remaining blocks supported, and what is its cost?
  2. Output consistency during refill: Can you characterize (even empirically) how often and how severely outputs during the partial-cache window diverge from full-KV decoding, particularly for long chain-of-thought reasoning? Would a lightweight rollback/re-verification mechanism be feasible if divergence is detected?
  3. Applicability under heavy migration demand: When many requests simultaneously need migration (e.g., cluster-wide memory pressure), how does the 26%–80% TiDEX pass rate interact with the rescheduling targets? Do unselected requests end up being preempted, and does the benefit shrink toward Llumnix's behavior in that regime?
1 comment
AuthorsOpenReview ↗

Response to reviewer pJZN

We appreciate your thoughtful review and constructive comments. We address your concerns below. Please let me know if you have any further questions; We will respond promptly.

1. Refill duration, stability, and fallback

We conducted a 32K-context case study using Mistral-7B, TP=2, and NCCL. Time and decoding steps start at destination-side handoff completion. KV fractions are normalized by historical tokens present at handoff, excluding newly generated tokens.

StageTime after handoff (s)Decoding stepsHistorical KV available
Handoff complete0020.46%
First refill applied0.6672140.54%
Second refill applied1.1674360.63%
Third refill applied1.5526580.72%
Full refill applied1.97088100%

Full refill takes 1.970 s (88 steps), but the first refill arrives after 21 steps, increasing historical KV availability from 20.46% to 40.54%. Subsequent events progressively restore the remaining KV. Thus, although full refill exceeds the approximately 20-step stability range, decoding does not rely solely on the initial critical subset throughout. Progressive refill expands historical context and helps accommodate attention changes. The observed stability range is empirical, not a fixed expiration time for the subset.

The implementation follows the established refill order without an attention-change triggered fallback or online critical-subset re-selection. Such recovery could add coordination overhead during decoding. KVFlow instead combines stability-based selection with progressive restoration. Online re-selection is not implemented, so its cost has not been evaluated. We will clarify these choices and distinguish observed stability from actual refill duration.

2. Output consistency and reasoning quality

Different reasoning paths can yield the same correct answer, and sampling can introduce variation even with full-KV decoding. Token-level divergence therefore does not directly indicate quality degradation. We assess final-answer accuracy as a measure of task-level correctness.

Temporal attention stability offers an opportunity for short-term partial-cache decoding, not a guarantee of identical outputs. Progressive refill limits partial-cache execution but does not undo previously generated tokens. We report MATH-500 accuracy under the A800 configuration described in the appendix:

QPSOverall vLLMOverall KVFlowMigrated requestsSubset vLLMSubset KVFlow
494.27%95.07%7192.96%94.37%
595.20%94.67%6888.24%88.24%
695.00%94.07%7884.62%85.90%
794.73%94.73%10297.06%96.08%

Each setting includes three 500-request runs per method. Overall accuracy covers 1,500 request instances. “Subset” denotes successfully migrated requests, paired with vLLM on the same questions and runs; counts pool all three runs.

These results show similar observed final-answer accuracy, including on migrated requests. They assess task-level correctness, not the frequency or severity of intermediate trajectory divergence.

Implementing lightweight rollback or re-verification is challenging: detecting divergence requires a reliable verification signal, and recovery must account for tokens already generated or streamed to the user. Our current implementation therefore relies on stability-based selection and progressive refill; recovery remains a direction for future work.

3. Heavy migration demand and TiDEX eligibility

Migration redistributes existing resources rather than increasing cluster capacity. It can alleviate imbalance and local memory pressure when destination capacity is available, but preemption may still occur near overall capacity, as observed in our high-load experiments (Figure 7c).

In our 24×3090 experiments, approximately 1% of requests migrated. TiDEX selects eligible requests to meet the memory-relief target; not every request must pass. If one migration provides insufficient relief, the scheduler reassesses pressure and triggers further migrations as needed. Excluded requests are not automatically preempted: migrating eligible requests can release memory so unselected requests continue locally. When eligible requests cannot provide sufficient relief and others must be relocated, KVFlow uses conventional full-KV migration for requests unsuitable for progressive migration.

Under heavy demand, insufficient eligible requests would increase reliance on full-KV migration, reducing progressive migration opportunities and bringing KVFlow's behavior closer to Llumnix's. If destination capacity is exhausted, redistribution is limited and preemption may still be necessary. KVFlow's advantage is expected to diminish in this workload.

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

This paper proposes KVFlow, a system that improves the responsiveness of runtime rescheduling in multi-instance LLM serving by decoupling request handoff from full KV cache transfer. Using block-level attention statistics and temporal stability filtering, KVFlow transfers the critical KV cache first, allows the destination to resume decoding early, and refills the remaining KV cache in the background while progressively reclaiming source-side memory. The authors evaluate migration efficiency, memory footprint, and end-to-end serving performance on an RTX 3090 cluster and an A800 platform. They report up to a 6.89× reduction in handoff latency, approximately 29% lower mean KV cache occupancy within a fixed 10-second observation window, and a 47.3% average reduction in P99 time-to-first-token (TTFT) relative to Llumnix. The evidence supports the system-level performance benefits, although generation quality preservation remains dependent on empirical filtering and the workload.

Critical strengths
  1. The paper addresses a consequential systems bottleneck that downtime alone can obscure. Uninterrupted decoding does not imply timely source-side resource reclamation. KVFlow jointly designs early handoff and progressive memory reclamation, and connects these mechanisms to improvements in source release time, queueing, and TTFT. This coherent connection between the mechanism and the measured benefits is a central reason to support acceptance.

  2. The implementation covers the critical execution mechanisms and is evaluated on real clusters. The contribution extends beyond sparse attention-based selection to block-table mappings, asynchronous refill, execution ownership transfer, and low-overhead statistics collection. Table 1, Figures 6–7, and Appendix D collectively support the feasibility of the approach.

Critical weaknesses
  1. The evidence for near-lossless generation quality does not yet adequately characterize the risks of actual migration. Figure 5 shows nonzero mean ROUGE-L drops even among TiDEX-selected requests, approximately 0.011 for Mistral on GovReport and 0.012 for Qwen on GovReport. Averages cannot rule out substantial degradation on a small subset of requests, and stability over the preceding 16 decoding steps does not guarantee stability throughout the subsequent refill window. Appendix D.6 provides system performance on a long-output reasoning workload but does not report accuracy under the same end-to-end configuration. The current results therefore do not sufficiently rule out performance gains coming at the expense of semantic correctness for some requests.

  2. The statistical reliability of the tail-latency gains and the attribution of migration costs remain insufficiently established. Each main end-to-end run contains only 500 requests, so P99 depends on roughly five observations in the tail. The supplementary A800 experiments also state that the number of runs varies across settings, without fully reporting the run counts or confidence intervals. For the reported migrations that take seconds, the paper additionally lacks a breakdown of effective transfer bandwidth and transfer, synchronization, and queueing costs. These omissions limit confidence in the magnitude and generalizability of the benefits.

Questions for authors
  1. Quality verification: Under actual end-to-end migration, what are the distribution of quality drops, the fraction of requests with substantial degradation, and MATH-500 accuracy? Please report results for migrated requests separately from results over the entire workload.

  2. Mechanism clarification: How does KVFlow respond when attention changes abruptly during refill despite a stable preceding window? Is there a fallback mechanism? Is there an empirically validated relationship among the critical-subset ratio, the estimated refill duration, and the number of decoding steps for which partial-cache execution remains safe?

  3. Statistical and baseline verification: Could you provide the number of independent runs and P99 confidence intervals for each setting, together with Llumnix's effective KV transfer bandwidth and migration latency breakdown? These details would materially affect my confidence in the robustness of the tail-latency gains.

3 comments
AuthorsOpenReview ↗

Response to reviewer Sba2

Thank you for your thoughtful feedback, which will help us strengthen the paper. We address your concerns below. Please let us know if you have any further questions; we will respond promptly.

1. End-to-end quality

We report overall and migrated-subset quality, pairing migrated requests with vLLM on the same questions.

Qwen2.5-32B/GovReport. Three serving runs of 500 requests each yielded:

RunMigratedOverall KVFlowChange vs. vLLMSubset vLLMSubset KVFlow
160.357580+0.0366%0.3400200.350967
250.357325−0.0347%0.3951440.382780
350.357366−0.0232%0.3830150.374698

The overall vLLM score was 0.357449, versus 0.357424 averaged across KVFlow runs. With TiDEX, each run's relative overall change was below 0.04% in magnitude, indicating negligible aggregate change here.

MATH-500. We evaluated three 500-request runs per method and QPS. Answers are scored correct if mathematically equivalent to the reference.

QPSOverall vLLMOverall KVFlowMigratedSubset vLLMSubset KVFlow
494.27%95.07%7192.96%94.37%
595.20%94.67%6888.24%88.24%
695.00%94.07%7884.62%85.90%
794.73%94.73%10297.06%96.08%

Results pool 1,500 request instances per method and QPS. Overall differences range from −0.93 to +0.80 percentage points. On migrated instances, KVFlow answers 292/319 correctly versus vLLM's 291/319, showing similar observed accuracy under the evaluated settings.

2. Attention changes, fallback, and refill progress

The 16-step window screens recent attention stability; it is not intended to cover the full refill duration. After handoff, KVFlow progressively incorporates received KV blocks into decoding, reducing reliance on the initial critical subset and potentially mitigating attention changes.

KVFlow currently has no explicit change-triggered fallback. Recovery during decoding could add coordination overhead and interrupt generation; our design combines stability-based selection with progressive refill. The results above support this choice under the evaluated configuration.

In the 8×A800 experiments:

QPSFirst refillSecond refillThird refillSteps to full refill
413.5 / 25.2%27.0 / 16.4%45.7 / 19.3%27.9
514.8 / 23.0%31.2 / 17.8%50.0 / 17.5%44.0
612.8 / 19.5%31.5 / 18.6%50.8 / 16.3%31.3
713.3 / 24.8%29.7 / 17.4%48.6 / 19.1%24.4

Refill cells give mean cumulative decoding steps since handoff / mean fraction of handoff-time historical KV newly added. Event columns include only requests requiring that event; full-refill means include all requests completing refill. The first refill adds 19.5%–25.2% of historical KV after 12.8–14.8 steps on average, consistent with our motivation experiments showing better quality with earlier refill.

3. P99 variability and baseline verification

We report three runs of 500 requests per setting and system. Entries are mean ± sample standard deviation of per-run P99 TTFT (seconds).

PlatformQPSvLLMLlumnixKVFlow
24×3090526.263 ± 15.72518.567 ± 6.0728.211 ± 1.484
24×30905.533.599 ± 2.12427.576 ± 24.34913.060 ± 4.963
24×3090631.092 ± 5.03533.048 ± 18.91921.613 ± 7.044
24×30906.530.025 ± 12.08936.773 ± 26.00719.787 ± 9.287
8×A80043.994 ± 1.3919.380 ± 1.6241.275 ± 0.311
8×A80055.133 ± 0.4975.180 ± 0.8592.276 ± 0.438
8×A80067.118 ± 1.7145.928 ± 0.8500.902 ± 0.144
8×A80074.874 ± 1.0482.105 ± 0.1861.055 ± 0.285

We repeated the Qwen2.5-32B/GovReport single-request experiment for both systems with matching migration configurations and the same backend. Event times are measured from migration initiation.

MetricLlumnixKVFlow
Application-level effective bandwidth (GB/s)0.2310.235
Total migration latency (ms)10,051.59,882.8
First destination-side token (s)10.1012.502
First source-KV release (s)10.0522.461

Effective bandwidth is transferred KV bytes divided by transfer-call duration, including waiting. Llumnix's mean migration latency comprises 30.3 ms pre-allocation, 9,950.2 ms transfer calls, and 71.0 ms other operations. Similar bandwidth and total migration latency indicate that KVFlow's benefit comes from earlier decoding and source-memory release through progressive migration, while total migration duration remains approximately unchanged.

Thanks for your rebuttal. I would keep my ratings.

Thank you for considering our rebuttal. Please let us know if you have any further questions or would like additional clarification. We would be happy to provide more details.

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

This paper presents KVFlow, a system for runtime request rescheduling in multi-instance LLM serving. KVFlow transfers a critical subset of the KV cache to enable early destination-side decoding, then progressively refills the remaining cache while releasing source-side memory. Its TiDEX policy selects migration candidates using estimated memory-relief benefits and temporal attention stability, supported by a lightweight attention-statistics extension. Experiments report faster migration handoff, lower migration-time memory occupancy, and improved serving latency compared with Llumnix and vLLM.

Critical strengths
  • The paper addresses a concrete bottleneck: live migration delays source-side memory release. KVFlow releases target amounts of memory 1.96–4.49× faster than Llumnix.
  • The implementation delivers measurable serving gains beyond faster handoff, including up to 24.0% lower mean TTFT than Llumnix in the main experiment.
Critical weaknesses
  • The “near-lossless” claim is too strong. On Qwen2.5-32B/GovReport, even TiDEX-selected requests lose 0.030 in mean score, while only 26% of requests qualify for migration (Figure 5).
  • TiDEX checks stability over the previous 16 decoding steps, but does not relate this window to the actual refill duration. Its fixed thresholds therefore lack validation when transfers are slow (§4.2).
  • Each main serving experiment contains only 500 requests, leaving roughly five observations in the P99 tail. Without repeated-run variability, the reported P99 improvements are difficult to assess (§5.3).
  • The A800 MATH-500 experiment reports latency and preemptions but omits answer accuracy. It therefore does not establish whether the serving gains preserve reasoning quality (Table 3).
Questions for authors

Please see the weaknesses.

3 comments
AuthorsOpenReview ↗

Response to reviewer FuE2

Thank you for your thoughtful and constructive feedback. We sincerely appreciate your careful review and address your four concerns below. If you have any further questions, please let us know, and we will respond as promptly as possible.

  1. The “near-lossless” claim

We agree that “near-lossless” needs qualification: the 0.030 mean-score decrease on TiDEX-selected Qwen2.5-32B/GovReport requests demonstrates a quality cost. We will distinguish this from aggregate quality changes in end-to-end serving. In three serving runs of 500 requests each:

RunMigratedOverall KVFlow scoreChange vs. vLLMSubset vLLMSubset KVFlow
160.357580+0.0366%0.3400200.350967
250.357325−0.0347%0.3951440.382780
350.357366−0.0232%0.3830150.374698

“Subset” denotes migrated requests. The overall vLLM score was 0.357449, versus 0.357424 averaged across KVFlow runs. Each run's relative overall change was below 0.04% in magnitude. We will qualify our claim as negligible aggregate quality change under the evaluated serving configuration, rather than per-request losslessness.

The 26% eligibility rate determines which requests may migrate; actual migration depends on serving and rescheduling conditions. Only 1.0%–1.2% migrated in these runs. This does not establish that 26% eligibility suffices under all rescheduling conditions.

  1. Stability window and refill duration

The 16-step window screens recent attention stability; it is not intended to cover the full refill duration. As described in “Stage 3: Remaining KV Cache Refill,” KVFlow progressively adds historical KV during decoding, reducing reliance on the initial critical subset. We measured:

QPSFirst refillSecond refillThird refillSteps to full refill
413.5 / 25.2%27.0 / 16.4%45.7 / 19.3%27.9
514.8 / 23.0%31.2 / 17.8%50.0 / 17.5%44.0
612.8 / 19.5%31.5 / 18.6%50.8 / 16.3%31.3
713.3 / 24.8%29.7 / 17.4%48.6 / 19.1%24.4

Refill cells give mean cumulative decoding steps since handoff / mean fraction of handoff-time historical KV newly added. Each event column includes only requests requiring that event; full-refill means include all requests completing refill. The first refill adds 19.5%–25.2% of historical KV after 12.8–14.8 steps on average. Progressive refill can help accommodate subsequent attention changes, consistent with our motivation experiments showing better quality with earlier refill.

Our main evaluation uses a 100 Gbps interconnect, reflecting the high-bandwidth production deployments targeted by KVFlow. Under these conditions, progressive refill balances quality and migration efficiency. Substantially slower transfers delay memory relief and reduce the benefit of migration-based rescheduling, making such configurations unsuitable for KVFlow’s intended production deployment.

  1. Run-to-run variability of P99 TTFT

We now report three runs of 500 requests per platform, QPS, and system. Entries are mean ± sample standard deviation of per-run P99 TTFT (seconds).

PlatformQPSvLLMLlumnixKVFlow
24×3090526.263 ± 15.72518.567 ± 6.0728.211 ± 1.484
24×30905.533.599 ± 2.12427.576 ± 24.34913.060 ± 4.963
24×3090631.092 ± 5.03533.048 ± 18.91921.613 ± 7.044
24×30906.530.025 ± 12.08936.773 ± 26.00719.787 ± 9.287
8×A80043.994 ± 1.3919.380 ± 1.6241.275 ± 0.311
8×A80055.133 ± 0.4975.180 ± 0.8592.276 ± 0.438
8×A80067.118 ± 1.7145.928 ± 0.8500.902 ± 0.144
8×A80074.874 ± 1.0482.105 ± 0.1861.055 ± 0.285

KVFlow has lower mean P99 TTFT than both baselines at every evaluated setting. These repeats support the observed trend. We will add run counts and variability to the appendix.

  1. Answer accuracy on MATH-500

We evaluated three 500-request runs per method at each QPS. A response is correct if its final answer is mathematically equivalent to the reference. Migrated-subset comparisons use the same questions in corresponding vLLM runs.

QPSOverall vLLMOverall KVFlowMigrated countSubset vLLMSubset KVFlow
494.27%95.07%7192.96%94.37%
595.20%94.67%6888.24%88.24%
695.00%94.07%7884.62%85.90%
794.73%94.73%10297.06%96.08%

Overall accuracy pools 1,500 request instances per method and QPS; migrated counts also pool three runs, counting repeated questions separately. Overall differences range from −0.93 to +0.80 percentage points. Across 319 migrated instances, KVFlow answers 292 correctly (91.54%) versus vLLM's 291 (91.22%). These show similar observed accuracy under the evaluated settings. We will add the results to the appendix.

AuthorsOpenReview ↗

Response to reviewer FuE2 (Additional P99 Results)

Thank you again for highlighting variability in P99 across repeated runs. Following our earlier response, we conducted 10 additional runs (5000 requests at all) for each system at each QPS on 8×A800. The table below summarizes all 10 new runs and reports the mean P99 TTFT, the sample standard deviation, and a nominal 95% confidence interval for the mean. The estimated gains changed at some QPS settings. Although P99 TTFT varied across runs, KVFlow consistently achieved the lowest mean P99 TTFT across all four QPS settings, with reductions of 59.1% to 76.2% relative to the faster baseline at each setting.

QPSSystemMean P99 TTFT (s)Sample SD (s)Nominal 95% CI for the mean (s)
4vLLM5.3883.273[3.047, 7.729]
4Llumnix6.2304.071[3.318, 9.142]
4KVFlow1.7140.742[1.143, 2.284]
5vLLM4.7871.569[3.580, 5.993]
5Llumnix4.7991.697[3.380, 6.217]
5KVFlow1.9590.835[1.317, 2.601]
6vLLM5.7762.090[4.281, 7.271]
6Llumnix5.2091.301[4.279, 6.140]
6KVFlow1.8450.893[1.206, 2.484]
7vLLM5.7071.556[4.593, 6.820]
7Llumnix4.7502.234[3.152, 6.348]
7KVFlow1.1300.336[0.889, 1.371]

Dear Reviewer, Thank you again for your time and thoughtful review. As the discussion period is nearing its end, we would appreciate any feedback on our responses. Please let us know if you have any further questions or would like additional clarification.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response: End-to-End Quality, Progressive Refill, and Tail Latency

Dear Area Chair and Reviewers,

We appreciate your careful reviews and constructive comments, which will help us strengthen the paper. We summarize our responses to three recurring concerns below; detailed results are provided in our individual responses.

1. End-to-end quality

We would first like to clarify a potential misunderstanding: migration-based rescheduling does not require moving a large fraction of requests. In our end-to-end serving experiments, only 1.0%–2.0% of requests were migrated to relieve memory pressure. KVFlow may affect the accuracy of only these migrated requests, while freeing memory and improving serving performance for the system as a whole.

In our Qwen2.5-32B/GovReport serving experiments, only 5–6 out of 500 requests (1.0%–1.2%) were migrated per run. KVFlow exposes only this small migrated subset to partial-cache decoding, while the resulting memory relief benefits other requests on the source instance and improves overall serving performance. The intended trade-off is therefore a potential quality cost on a small subset of requests in exchange for broader latency and memory-management benefits. Across three runs, the relative overall score change versus vLLM was below 0.04% in magnitude in each run. This measures the aggregate quality impact under the evaluated serving conditions; it does not imply that individual migrated requests are lossless. We report migrated-subset scores separately and will qualify the “near-lossless” claim accordingly.

For MATH-500, we evaluated three 500-request runs per method at each of four QPS settings. Overall accuracy differences between KVFlow and vLLM ranged from −0.93 to +0.80 percentage points. Across 319 migrated request instances, KVFlow answered 292 correctly (91.54%), compared with 291 (91.22%) for vLLM on the same instances. These results show similar observed final-answer accuracy under the evaluated settings, including on the requests directly affected by migration.

2. Attention stability and progressive refill

The 16-step selection window measures recent attention stability; it is not intended to cover full refill. KVFlow progressively incorporates arriving KV blocks, reducing reliance on the initial critical subset during decoding.

In a 32K-context Mistral-7B case study (TP=2, NCCL), full refill took 1.970 s, or 88 decoding steps after handoff. The first refill was applied after 21 steps, increasing historical KV availability from 20.46% to 40.54%, followed by progressive restoration to 100%. In the 8×A800 end-to-end experiments, the first refill occurred after 12.8–14.8 steps on average and added 19.5%–25.2% of historical KV. These measurements characterize progressive refill under the evaluated settings, rather than establishing a general safe partial-cache decoding horizon. The current implementation relies on stability-based selection and progressive refill.

3. Tail-latency variability

We now report three 500-request runs per system and QPS on both 24×3090 and 8×A800, including the mean and sample standard deviation of per-run P99 TTFT. KVFlow achieves lower mean P99 TTFT than both vLLM and Llumnix at every evaluated setting on both platforms. These repeated measurements support the observed trend toward lower tail latency.

We will incorporate these results, and clarifications into the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.