- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper addresses runtime KV-cache imbalance in multi-GPU LLM serving. Although PagedAttention and continuous batching improve within-instance memory management, request growth and completion can create cross-instance imbalance, causing queueing, preemption, and tail-latency spikes. The authors observe that existing systems (Llumnix, MELL, L4) lack a load-driven, request-level migration decision that models the conditional value of a KV cache, and that fixed Top-1/Top-3 migration-set sizes either under- or over-migrate. The paper proposes ARI, a decision layer built on top of MELL's initial allocator and request-level execution paths (Direct-KV transfer or Token-RePrefill). Its three main components are:
- Rule-interpolated migration priority: Five normalized features (source pressure, request KV size, estimated migration cost, global imbalance, remaining execution time) are matched against a sparse rule base via Gaussian kernels; normalized consequent interpolation yields a continuous migration priority, capturing conditional feature interactions that a fixed additive linear score cannot express (formally shown in Proposition 7).
- Online rule growth and confidence update: Post-migration utility (balance improvement, memory released, migration time, extra latency) feeds back to update rule confidence (Eq. 4), and recurrent, poorly covered states in a dense region of the feature buffer trigger the creation of new rules (Eq. 5), with density/coverage tests restricting growth.
- Destination-aware minimum Top-k planning: A fixed destination score selects feasible targets on a virtual cluster state; the planner greedily applies CV-reducing moves and stops at the first balanced prefix (Eq. 6), avoiding over-migration without searching for a globally minimal migration subset.
Experiments on 4-GPU and 8-GPU A100 testbeds with Qwen2.5-1.5B, Llama-2-7B, and Llama-2-13B, against MELL, Llumnix, FastServe, L4, and a Linear Score ablation, show throughput gains over MELL in all six settings (6.7%–151.5%), e.g., 436.82→675.31 tokens/s (+54.6%) with 30.9% lower P95 on 4-GPU/7B, and first place in four of six settings. Ablations attribute most benefit to remaining-duration and adaptive components.
Critical strengths
- Conditional, non-additive candidate valuation. Unlike the fixed linear scoring of prior systems, ARI's Gaussian rule interpolation explicitly models conditional interactions — a large KV cache is valuable only when source pressure is high, transfer is cheap, and substantial decoding remains — and this advantage is backed by a formal separation result (Proposition 7) showing orderings no affine score can realize.
- Online rule-base evolution with controlled growth. The combination of coverage/density gating (Eq. 5) and observed-utility confidence updates (Eq. 4) allows the priority mechanism to adapt at runtime while provably bounding the feedback state (Proposition 4), addressing the previously unverified "how should the rule base evolve" question in this scheduling framework.
- Destination-aware minimum Top-k planning. Coupling request ranking, destination selection, and migration-set size in one planner — stopping at the first balanced greedy prefix (Eq. 6) — directly answers the unanswered "how many to move" question, and the ablation shows it trades modest throughput for 33.3% fewer migrations versus fixed Top-k.
- Clean separation of concerns with honest scoping. Planning, reservation, execution, and adaptation are clearly delimited; ARI reuses MELL's initial allocation and Direct-KV/Token-RePrefill execution paths rather than redesigning them, and the appendix carefully distinguishes decision-time vs. feedback-time predictions, NE vs. N/A vs. zero, and planned vs. committed migrations.
- Demonstrated gains where conditions are favorable. On 4-GPU/7B, ARI achieves +54.6% throughput and −30.9% P95 over MELL, a 33.7% throughput advantage over the Linear Score ablation with 19.1% fewer migrations at nearly unchanged P95, and a clear joint benefit over Llumnix on 8-GPU/13B (+25.3% throughput, −3.7% P95, −31.2% migration execution time).
Critical weaknesses
- The 4-GPU/13B failure case is unexplained and undermines the contribution claim. ARI's throughput (268.77) is not only below Llumnix (320.36) and FastServe (310.02) but below its own ablation baseline Linear Score (308.11), and P95 is uniformly worse; the paper only states that "the observed advantage concentrates on the tested 7B configurations" (lines 408–409) without analyzing the root cause — a clear tension between the contribution statement and the experimental evidence.
- The benefit–cost account of "smarter scheduling" is not settled. Table 8 shows ARI's planning time (6.56 ms) is 22× that of Llumnix (0.30 ms), and on 4-GPU/7B ARI performs fewer migrations than MELL (10.03 vs. 11.00) yet takes longer migration execution time (2,875.02 vs. 1,940.73 ms, lines 427–429). Whether the added planning/execution cost is justified across settings is left as aggregate, setting-dependent observations.
- Statistical reporting contradicts the stated protocol. The paper claims "rigorous run-level statistical analysis" (line 719), yet sample standard deviations exist for only one of 18 configurations (Table 7, 4-GPU/13B), with no confidence intervals or significance tests anywhere, and run-level raw records, failed trials, and exclusion counts are absent from the aggregate files (lines 415–418).
- Adaptation does not demonstrably improve prediction. Prediction error remains 0.30828 with or without confidence updates (Table 4 discussion, line 452), the confidence update is explicitly "not guaranteed to move toward the target," and the repeated-identical-feedback example in Appendix B shows the default update can leave predictions stuck — so the online-learning component's causal benefit is established only through P95 ablation numbers in one setting.
- Key execution-path claims lack commit-level evidence. Backend selection (Direct-KV vs. Token-RePrefill) is "separate from scoring" with an auto setting that "does not establish which backend executed" (lines 284–285); without per-run commit records, the migration-efficiency comparisons (transfer bytes, re-prefill tokens, execution time) cannot be attributed to a specific execution path.
Questions for authors
- 4-GPU/13B regression: What is the root cause of ARI underperforming its own Linear Score ablation on 4-GPU/13B (268.77 vs. 308.11 tokens/s, higher P95, higher KV imbalance 0.4402 vs. 0.3197)? Can you decompose the failure into feature-scale, rule-matching, or destination-selection effects, and does the trained rule base differ qualitatively from the 7B case?
- Overhead accounting: Given planning time of 6.56 ms (22× Llumnix) and longer migration execution time than MELL on 4-GPU/7B despite fewer migrations, under what workload/cluster conditions does the benefit–cost balance of ARI turn negative? Please provide a per-setting break-even analysis and clarify which backend (Direct-KV vs. Token-RePrefill) actually executed each migration via commit records.
- Statistical rigor: The paper claims "rigorous run-level statistical analysis," but standard deviations exist only for 4-GPU/13B. Will you release run-level raw records and report confidence intervals or paired significance tests for all 18 configurations, particularly for the 7B settings where the headline claims rest on single-point aggregate numbers?
2 comments
Response to Question 3 and Weakness 3: Statistical Reporting and Supporting Records
The aggregate tables are not the full extent of the retained evidence. Complete archived comparison groups include per-run records that support paired reanalysis.
For example, in the historical four-GPU 7B confidence-on/off comparison, the mean paired change in per-run end-to-end P95 latency is −625.80 ms, with a paired 95% confidence interval of [−3314.20, 2062.60] ms. This distinguishes a favorable point estimate from a statistically established improvement.
We are prepared to provide the corresponding per-seed results and available request/event records, together with experiment versions, workload identifiers, seeds, and archive hashes. The evidence index will also identify completion, failure, rerun, and exclusion records. Complete paired experiments and aggregate-only summaries will be explicitly distinguished, so that uncertainty and significance claims are tied to the records supporting each comparison.
The submitted manuscript and appendix provide the primary results and analyses; these additional records provide the finer-grained evidence needed to audit the comparisons.
Response to Weakness 4: Prediction Quality and Adaptation Benefits
Confidence adaptation affects relative rule influence and candidate ordering. Aggregate utility-prediction MAE therefore does not fully characterize its scheduling value. Our historical confidence-on/off ablations show favorable point estimates for P95 TPOT and end-to-end P95 latency in both model settings: the respective reductions are 3.74% and 8.91% for 1.5B, and 7.21% and 7.27% for 7B. The paired interval reported above illustrates the uncertainty accompanying these observations.
The repeated-feedback example identifies a specific limitation of the original heuristic update. We reproduced this behavior on CPU: with two equal-match rules having consequents 0.2 and 0.8, the original update keeps the prediction at 0.5 under repeated toy feedback of 0.8. A separately implemented normalized-gradient variant with projection and backtracking reduces absolute error from 0.3000 to approximately 0.2379 after 100 updates, using a learning rate of 0.05 in the same construction.
This is a mechanism-level result for the separate variant, not a GPU performance result or a retrospective claim about the original experiments. It provides a concrete direction for improving credit assignment. Targeted matched-trace comparisons of original, frozen, and normalized-gradient confidence updates will assess ranking quality, pre-update error, and serving outcomes across additional model sizes and GPU configurations.
We thank the reviewer for the detailed assessment. Our responses below draw on the submitted manuscript and appendix, together with quantitative reanalysis of retained experimental records. We have retained run-level results and migration-event logs for the archived experiments discussed here. We are prepared to provide the relevant supporting records through an anonymized supplementary artifact, with explicit links to the corresponding tables, configurations, and runs, to facilitate verification.
Response to Question 1 and Weakness 1: Understanding the 4-GPU/13B Regression
ARI’s contribution is a request-level KV-cache migration policy for multi-GPU LLM serving, combining context-dependent priority interpolation, destination-aware virtual planning, and state-dependent stopping. The four-GPU/13B comparison is particularly informative because it tests ARI against its own Linear Score baseline on both serving performance and KV balance.
Our analysis separates three stages:
Feature-scale alignment. Model geometry and decoding speed affect KV-byte and remaining-duration inputs relative to the configured normalization scales.
Rule activation. In a separate 13B diagnostic trace, 11 of 12 candidates at the first recorded decision have a zero remaining-duration feature. Their priority scores cluster around 0.5, with a total span of approximately 5.95×10−6. This provides a concrete example of weak feature and priority separation at a decision point.
Destination selection and execution. Candidate priority is followed by capacity checks, destination scoring, and virtual imbalance evaluation. The accepted migration therefore depends on the interaction between ranking and target selection. The snapshot-level imbalance condition also differs from the time-averaged imbalance measured during continuing arrivals and KV growth.
The implementation initializes rule prototypes from configuration and adapts the priority library online. Model-specific behavior is therefore reflected in feature distributions, rule activation, and subsequent growth. We will present the frozen initial configurations alongside these activation profiles and use controlled replays with initial placement and destination selection held fixed to isolate the ranking contribution.
Response to Question 2 and Weaknesses 2 and 5: Overhead Accounting and Executed Backends
The benefit–cost account requires accumulated scheduling cost and actual migration cost, rather than migration count alone. Fewer migrations can take longer when the selected requests carry larger contexts or incur longer execution pauses.
Our retained records already provide a stage-level breakdown. Across 134 recorded ARI migration-decision events in the historical eight-GPU 7B track, average priority computation takes 0.454 ms, virtual planning takes 32.923 ms, and total scheduler time is 33.903 ms. Priority computation accounts for approximately 1.34% of the recorded scheduler time. Virtual planning is the dominant measured scheduler component in these events.
For a migrated request with n remaining tokens, a simple amortization condition is
nΔTPOT>Textra,
where ΔTPOT is the expected per-token improvement and Textra is the incremental pause and queueing cost on the request’s critical path. Using the quoted 2.875 seconds as an illustrative pause budget, amortization requires more than 11.23 ms/token improvement over 256 remaining tokens, or 5.62 ms/token over 512 tokens, before additional queueing costs. This identifies the unfavorable regime: expensive migrations of short-lived requests, or destinations offering insufficient decoding improvement.
Executed-backend identities are also recorded. In the archived eight-GPU 7B auto matrix, all 481 committed migrations executed Token-RePrefill, including 134 ARI commits. Separately, the fixed Direct-KV 1.5B archive contains 495 verified Direct-KV commits. These records distinguish backend availability, selector configuration, and the path actually executed.
The supporting evidence can provide selected and executed modes, transferred bytes, re-prefill tokens, execution times, and commit/rollback outcomes. Scheduling costs will be associated with their actual invocation counts, including recorded empty-plan invocations, rather than inferred from migration counts.