- 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:
- 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.
- 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).
- Lightweight block-level attention extension — records compact prefix ratios
W_i = P_i/l_iinside 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
- 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.
- 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.
- 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.
- 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).
- 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
- 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).
- "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.
- 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.
- 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.
- 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
- 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?
- 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?
- 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?
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.
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:
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.