- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper studies request scheduling in disaggregated LLM inference, where prefill and decode are executed on separate resource pools. An important challenge is that requests waiting for decode admission may still occupy prefill KV memory, so the two scheduling decisions are coupled.
The authors formulate this problem as Dual-Memory Request Scheduling (DMRS), with the objective of minimizing total completion time. They prove the problem is strongly NP-hard and propose two polynomial-time approximation algorithms, including one with a uniform 36-approximation guarantee.
The paper also evaluates the algorithms on synthetic workloads, Azure trace-derived workloads, and two H100 GPUs. The proposed methods improve total completion time over the disaggregated P/D baseline in the main GPU experiments.
Critical strengths
-
The problem formulation is clear and useful. The dependency between prefill and decode memory is an important issue in disaggregated inference systems. It is good to have a formal scheduling problem that captures this interaction, instead of only studying the problem through system heuristics.
-
The theoretical contribution looks interesting. The authors provide an NP-hardness result and two approximation algorithms with explicit guarantees. I also appreciate that they include both optimization experiments against ILP/LP references and actual GPU serving experiments, which helps connect the theory to practical inference workloads.
Critical weaknesses
-
My main concern is the assumptions used by the scheduling model. The algorithm assumes all requests arrive at the same time and their output lengths and processing demands are known in advance. In real LLM serving, requests arrive dynamically and output lengths are normally unknown. Also, decode computation can depend on the active batch size, which is not explicitly modeled here. These assumptions are reasonable for a theoretical starting point, but they limit how directly the approximation guarantees can be used for real serving systems.
-
The practical benefits seem to depend on the workload and serving configuration. In Table 2, the colocated baseline performs better than Algorithm 1 for conversation workloads. The appendix also reports higher P99 completion times in some settings. I think the paper could better explain when the proposed algorithms should be preferred over existing scheduling approaches, especially if tail latency is important.
Questions for authors
-
How sensitive are the algorithms to incorrect estimates of output length? Would it be possible to use predicted output lengths instead of knowing the exact values in advance?
-
Are LP solving time and offline batch preparation overhead included in the end-to-end serving comparison? How large are these costs for practical batch sizes?
-
Can the authors explain why colocated serving performs better for conversation workloads in Table 2? What workload properties determine whether disaggregated scheduling is beneficial?
2 comments
Dear Reviewer EVJx,
Thank you for your feedback. We would welcome your thoughts on whether our response and revised manuscript address the concerns you raised. If any questions remain, we would be happy to clarify them.
If your concerns have been addressed, we would appreciate your considering an update to your review and rating.
Thank you for taking the time to consider our revisions.
Response to Reviewer EVJx
We thank Reviewer EVJx for recognizing the formulation and theoretical contributions.
Weakness 1: Batch release and known request parameters
We first apologize for the confusion: our original manuscript did not clearly distinguish between when individual requests arrive (are submitted) and when a batch is released to the scheduler at t=0 (Section 2.1, p. 3). Individual requests may be submitted at different times; the common release time t=0 simply marks when the full batch becomes available to the scheduler.
Practical examples.
Scheduling difficulty. The Dual-Memory Request Scheduling (DMRS) problem remains strongly NP-hard even with complete information. To the best of our knowledge, ours is the first framework providing approximation guarantees for minimizing total completion time under separate prefill and decode capacities.
Prior theory: Related theoretical studies consider offline scheduling and predicted output lengths. Wang et al. [2] study offline scheduling with known lengths; Jaillet et al. [3] study online scheduling with exact lengths or predictions with bounded overestimation.
Weakness 2: Workload dependence and tail latency
Mean completion time. Table 2 favors our algorithms on Code and colocation without chunked prefill on Conversation. Both algorithms reduce TCT relative to vLLM P/D in all four cases.
Tail latency. At κ=2, vLLM P/D has the lowest P99 among the tested P/D policies in all four cases (Figure 10).
Question 1: Can the algorithms use predicted output lengths?
Yes. Predicted lengths can guide scheduling and decode reservations. Overestimates can waste KV capacity. Underestimates can exhaust reservations, requiring runtime checks and a policy for overruns. Sensitivity depends on error size and available KV capacity. Our guarantees assume known prefill durations and output lengths, with fixed decode step times. Extending them to online serving requires accounting for dynamic arrivals, prediction errors, and how batch-dependent decode times affect KV occupancy.
Question 2: How much time does offline planning take?
GPU timing starts at batch release, after LP solving and schedule construction. The table gives mean runtime on the CPU at κ=2 (revised manuscript, Appendix H.1, Figures 5(b) and 6(b)).
Question 3: Why does colocation perform better on conversation workloads?
For the Table 2 runs, each pair gives mean TTFT (s) / mean TPOT (ms). Colocated uses tensor parallelism without chunked prefill.
Colocated achieved lower TTFT and TPOT on Conversation (Table 4). Its TPOT advantage accumulated over the longer outputs. The benefit of P/D depends on prompt length, output length, and how often long prefills overlap with and delay ongoing decode steps on shared GPUs.
See Table 4 in Appendix H.2 of the revised manuscript for the latency breakdown.
References
[1] Alshahwan et al. Automated Unit Test Improvement using Large Language Models at Meta. FSE 2024.
[2] Wang, Ye, and Zhou. LLM Serving Optimization with Variable Prefill and Decode Lengths.
[3] Jaillet et al. Online Scheduling for LLM Inference with KV Cache Constraints.