acceptodds
Under review as a conference paper at ICLR 2027

Approximation Algorithms for Dual-Memory Request Scheduling in Disaggregated LLM Inference

Abstract

Disaggregated LLM inference executes the prefill and decode phases on separate resource pools, reducing interference between the two phases. However, this architecture introduces a coupled scheduling problem because a request that completes prefill retains its prompt KV cache in prefill memory until it is admitted to the decode pool. Prefill and decode admission decisions therefore jointly determine memory occupancy and request completion times. To the best of our knowledge, this problem lacks a formal formulation, and no approximation guarantees are known for request scheduling in disaggregated LLM inference. We formalize this setting as the dual-memory request scheduling (DMRS) problem, whose objective is to minimize the sum of request completion times, and prove that it is strongly NP-hard. We develop two deterministic polynomial-time approximation algorithms. The first applies to instances satisfying and and achieves an approximation ratio of , where and are the maximum normalized prefill and peak decode memory demands among all requests, respectively. In particular, it yields a -approximation when . The second algorithm applies to all feasible instances and achieves a uniform -approximation. Finally, evaluations on two H100 GPUs using trace-derived offline workloads show that the proposed algorithms reduce the sum of request completion times relative to multiple vLLM deployment baselines.

Primary area:
optimization
Keywords:
large language models, disaggregated inference, KV cache management, approximation algorithms, request scheduling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_EVJxOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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?

  2. 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?

  3. 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
AuthorsOpenReview ↗

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=0t=0 (Section 2.1, p. 3). Individual requests may be submitted at different times; the common release time t=0t=0 simply marks when the full batch becomes available to the scheduler.

  1. Practical examples.

    • CI unit test generation (Single-job burst): A code change can trigger a continuous integration (CI) job that identifies target test classes and submits one generation request per class in a single batch at t=0t=0 (directly matching our Azure Code workload). Meta’s TestGen-LLM illustrates code changes triggering batch unit-test generation in practice [1].
    • Periodic batch inference (Windowed backlog release): In asynchronous or high-load inference services, requests arrive over time, accumulate in a queue, and are released together to the scheduler at scheduled windows (t=0t=0).
  2. 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.

  3. 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

  1. 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.

  2. Tail latency. At κ=2\kappa=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\kappa=2 (revised manuscript, Appendix H.1, Figures 5(b) and 6(b)).

RequestsConversation Alg. 1 (s)Conversation Alg. 2 (s)Code Alg. 1 (s)Code Alg. 2 (s)
500.0340.0370.0140.015
1000.2120.2180.1060.110
1500.9120.9290.6520.659
2003.2663.2942.6492.661
25011.28711.3168.9408.958

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.

WorkloadModelMean output tokensColocatedAlgorithm 1Algorithm 2
ConversationQwen2.5 7B244.524.49 / 4.9325.10 / 6.1328.18 / 6.10
ConversationLlama 3.1 8B244.526.65 / 5.3527.07 / 6.6830.12 / 6.60
CodeQwen2.5 7B22.88.79 / 10.605.47 / 6.246.08 / 6.25
CodeLlama 3.1 8B22.89.81 / 12.145.96 / 7.016.64 / 6.86

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.

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.

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

The paper studies request scheduling in prefill--decode (P/D) disaggregated LLM inference. Prefill and decode run on separate pools with KV-cache capacities MPM_P and MDM_D. A request that has finished prefill keeps its prompt KV cache in prefill memory until it is admitted to decode. The authors formalize this as the Dual-Memory Request Scheduling (DMRS) problem. In this offline, clairvoyant setting, all requests arrive at t=0t=0 and (mi,pi,di)(m_i, p_i, d_i) are known in advance. The objective is to minimize the sum of completion times. The authors prove strong NP-hardness via a reduction from 3-PARTITION and derive an LP relaxation with Queyranne-type memory-time load inequalities. They then give two LP-guided group-scheduling algorithms: an (8+41−α+81−β)\bigl(8+\frac{4}{1-\alpha}+\frac{8}{1-\beta}\bigr)-approximation for α,β<1\alpha,\beta<1, which is 3232 for α,β≤1/2\alpha,\beta\le 1/2, and a uniform 3636-approximation. Experiments include CPU comparisons against the ILP optimum and the LP bound, and a 2×2\timesH100 vLLM deployment where the algorithms reduce total completion time (TCT) relative to a vLLM P/D baseline.

Critical strengths
  • Rigorous and correct theory within the model. The DMRS formulation is clean and precise, and the analysis is elegant. I checked the main proofs (the NP-hardness reduction from 3-PARTITION, Lemmas 1-2 on the LP and its separation oracle, and the charging arguments in Lemmas 5 and 7) and found them correct, including the ratio optimization at ρ=3/2\rho = 3/2. This matters because it establishes the first approximation guarantees for a formally defined two-pool P/D scheduling problem.
  • Complete treatment of the stated problem. The results cover both restricted instances (α,β<1\alpha, \beta < 1) and all feasible instances, handling the boundary cases α=1\alpha = 1 or β=1\beta = 1 via the large/small classification. The paper is well written and the appendix is thorough.
Critical weaknesses

1. The objective does not match the setting. The model is offline (all requests released at t=0t = 0, output lengths known), which is essentially batch inference. For batch workloads the natural objective is makespan or throughput, not the sum of completion times. The paper gives no makespan guarantee, and the empirical evidence suggests the proposed algorithms may hurt makespan:

  • Fig. 10 shows higher P99 completion times than P/D for all four model/workload combinations.
  • Fig. 14 shows lower throughput than Colocated.

Both are consistent with the SPT-like behavior induced by minimizing ∑iCi\sum_i C_i and with the idle tails created by the strict group barriers. Makespan also appears to be the easier objective here: a simple greedy admission policy without LP-based grouping seems to already achieve a constant-factor makespan approximation via the paper's own charging argument, using the standard lower bounds

OPTmax⁡≥max⁡{∑iℓiPMP,∑iℓiDMD,max⁡i(mi+di)}\mathrm{OPT}_{\max} \ge \max \lbrace \frac{\sum_i \ell^P_i}{M_P}, \quad \frac{\sum_i \ell^D_i}{M_D}, \quad \max_i (m_i + d_i) \rbrace with only a single prefill tail and a single decode tail to charge. If this is right, the LP and grouping machinery is only justified for ∑iCi\sum_i C_i, which is not the metric that matters for batch inference.

2. The central coupling has limited relevance to practical P/D systems. The key modeling feature, requests retaining prompt KV in prefill memory while waiting for decode admission, is largely an artifact of a specific P/D design. Many online disaggregated serving systems reserve or pre-allocate decode-side KV memory before admitting a request to prefill (e.g., SGLang's PD disaggregation and NVIDIA Dynamo), which essentially eliminates the waiting set W(t)\mathcal{W}(t) and avoids the problem by construction. In addition, prefill-pool KV memory is rarely the binding resource in practice, because KV is freed right after transfer. The experiments create this bottleneck artificially by setting MP≈1.5max⁡ipiM_P \approx 1.5 \max_i p_i (roughly 11K tokens on an H100). In the online setting, where a latency-oriented objective like ∑iCi\sum_i C_i would make sense, the offline clairvoyant model does not apply. The paper therefore lacks a convincing deployment scenario: in batch mode the objective is mismatched, and in online mode the modeled design is not what practical systems use.

3. The resource model omits compute and bandwidth. The only constraints in the model are KV-cache capacities.

  • Prefill is compute-bound. Concurrent prefills share GPU FLOPs, so a request's actual prefill time depends on what else is co-scheduled. The model instead assigns a fixed mim_i regardless of concurrency, which amounts to free parallelism up to MPM_P.
  • Decode is memory-bandwidth-bound. Step time grows with batch size and total context length, yet each step is modeled as a constant slot.

With realistic KV capacities, prefill-pool memory would rarely bind and compute would become the real constraint, which the model does not capture. The small MPM_P used in the experiments effectively serializes prefill, which may make the model look more accurate than it is. Relatedly, mim_i in the GPU experiments is derived from isolated prefill latency; when the proxy admits several prefills concurrently, vLLM batches them, so realized times likely deviate from the plan. This deviation is not reported.

Questions for authors
  1. Can you provide makespan guarantees for Algorithms 1 and 2? How do they compare, theoretically and empirically, to a simple greedy admission policy without LP grouping or group barriers? Please report makespan/throughput against P/D directly.
  2. Why is the "prefill-retention" P/D design the relevant one, given that decode-side pre-reservation removes the coupling? Please add a baseline that combines decode-side reservation with simple greedy ordering.
  3. How do the results change under realistic KV capacities, where MPM_P is not artificially small?
  4. How would the model and guarantees change if prefill were compute-constrained (prefill time depending on the concurrent prefill workload) and decode step time depended on batch size and context length?
  5. In the GPU experiments, how large is the deviation between planned and realized admission and completion times?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 62et

We thank Reviewer 62et for recognizing our contributions.


Weakness 1: Objective and LP grouping

Why minimize TCT (∑iCi\sum_i C_i): In continuous integration (CI) test generation each generated test enters compilation and validation as soon as it is returned. Minimizing TCT reduces the average wait before validation begins, whereas makespan (max⁡iCi\max_i C_i) only cares about the last request:

Example. Suppose 99 requests take 1 s each and one takes 100 s. All are released at t=0t=0 and run serially on one processor. Both orders have the same makespan (199 s) and batch throughput. The mean completion time is 149.50 s with the long request first and 51.49 s with the short requests first. The short requests first order returns 99 results within 99 s.

Greedy makespan. Without group barriers, scan waiting decodes first, then unstarted prefills at time zero and each completion. Admit every request that fits and reserve peak decode KV. For α,β≤1/2\alpha,\beta\le1/2, after both scans, a decode wait implies over half the decode pool is reserved. Otherwise, an unstarted prefill implies over half the prefill pool is occupied.

Let A=∑iℓiP/MPA=\sum_i\ell_i^P/M_P, B=∑iℓiD/MDB=\sum_i\ell_i^D/M_D, and H=max⁡i(mi+di)H=\max_i(m_i+d_i). Peak reservations use at most twice the mandatory decode memory-time load. Charging these slots and adding tails of length at most 2H2H gives Cmax⁡G≤2A+4B+2H≤8,OPTmax⁡.C_{\max}^G\le 2A+4B+2H\le 8\\,\mathrm{OPT}_{\max}. The last inequality follows from OPTmax⁡≥max⁡A,B,H\mathrm{OPT}_{\max}\ge\max\\{A,B,H\\}. LP grouping bounds completion times for successive prefixes to establish the TCT guarantee.

Tradeoffs. Figure 10 shows higher P99 than P/D, and Figure 14 shows lower throughput than Colocated.


Weakness 2: Retained caches and practical capacities

Admission. Upfront decode reservation can delay prefill. With deferred reservation, requests can start prefill earlier. Those waiting for decode retain their KV in the prefill pool. See Question 2 for the comparison.

Capacity. Figure 9 shows lower Code TCT than P/D at all tested budgets (κ=1.5\kappa=1.5 to 44). Conversation gains diminish as capacity increases.


Weakness 3: Computation and bandwidth

We fix prefill durations and decode step times to isolate KV-capacity constraints. In practice, concurrent prefills share compute, and decode step times can vary with batch size and context length. Extending the guarantees requires accounting for how these changes affect KV occupancy.

See Question 5 for the differences between the schedule and the recorded event times.


Question 1: Makespan and greedy comparison

Let L=max⁡A,B,HL=\max\\{A,B,H\\}. In either pool, adding ii to S∖iS\setminus\\{i\\} increases the LP inequality's right side by ℓi∑j∈Sℓj/M≤ℓiL\ell_i\sum_{j\in S}\ell_j/M\le\ell_i L. Capping any Cˉi>L\bar C_i>L at LL preserves feasibility and improves the objective. Thus max⁡iCˉi≤L≤OPTmax⁡\max_i\bar C_i\le L\le\mathrm{OPT}_{\max} at an optimum. The pointwise bounds Ci≤rCˉiC_i\le r\bar C_i yield makespan factors of 8+4/(1−α)+8/(1−β)8+4/(1-\alpha)+8/(1-\beta) for Algorithm 1 when α,β<1\alpha,\beta < 1, and 36 for Algorithm 2 on all feasible instances. For α,β≤1/2\alpha,\beta\le1/2, these give 32 and 36, compared with 8 for greedy (Weakness 1).

CPU simulation. TCT / makespan relative to deferred greedy on the 14B batches.

PolicyConversationCode
Greedy, deferred admission1.000/1.0001.000/1.000
Greedy, upfront reservation1.014/1.0301.586/1.316
Algorithm 11.021/1.0981.436/1.159
Algorithm 21.164/1.2161.821/1.307

GPU measurements. Makespan (s) / throughput (requests/s) for Qwen2.5-14B-Instruct, with 250 requests, one H100 per phase, and κ=2\kappa=2. One run per configuration.

WorkloadvLLM P/DAlgorithm 1Algorithm 2
Conversation109.83/2.276132.25/1.890148.99/1.678
Code38.29/6.52951.82/4.82552.47/4.764

See the revised manuscript (Appendix H.4, Table 7 and Appendix H.3, Table 5).


Question 2: Upfront reservation

See Weakness 2. The CPU table includes greedy reservation of peak decode KV from prefill admission through decode completion. Both use the same budgets and increasing mi+dim_i+d_i order.


Question 3: KV capacities

See Weakness 2 and Figure 9 (κ=4\kappa=4).


Question 4: Variable execution times

See Weakness 3.


Question 5: Timing deviations

Median / P95 absolute deviation (s) between schedule times (10.91 ms/slot) and proxy timestamps from batch release

WorkloadMethodPrefill admissionPrefill completionDecode admissionDecode completion
ConversationAlgorithm 12.82/9.343.21/9.353.14/9.973.43/10.27
ConversationAlgorithm 24.82/12.015.05/12.054.69/12.674.81/12.97
CodeAlgorithm 14.79/24.725.74/25.335.73/25.335.77/25.35
CodeAlgorithm 25.59/22.825.81/23.365.81/23.305.84/23.39

See Table 6 in Appendix H.3 of the revised manuscript.

Dear Reviewer 62et,

We wanted to follow up and see whether our response and revised manuscript address the concerns raised in your review. If any questions remain, we would be happy to clarify them.

If the revisions address your concerns, we would appreciate it if you could update your review and rating as you see fit.

Thank you again for your time and constructive feedback.

I thank the authors for the detailed response and the substantial additional experiments. The new CPU comparison between deferred and upfront reservation (e.g., 1.000 vs. 1.586 TCT on Code) partially supports the relevance of modeling retained prefill caches, and I appreciate this. However, my main concerns remain, and several of the new results reinforce them.

1. Motivation for TCT in an offline setting. I remain unconvinced by the motivation. If users care about average waiting time, the workload is latency-sensitive, and the relevant setting is online: requests arrive over time, and the waiting time from a request's arrival until its batch is formed and dispatched is part of the latency the user experiences. The offline model assumes that all requests are available at t = 0, which excludes exactly this waiting time. Conversely, in genuine offline batch processing (e.g., batch inference APIs with long completion windows), the per-request average waiting time is generally not the objective; makespan and throughput are. Both online serving and offline batching exist in production, but the paper's combination, an offline batch model with an average-latency objective, does not correspond to either.

The CI test-generation example illustrates this: generation requests are produced over time and results are consumed as they return, which is a streaming/online workload. For such a workload, the proposed approach would first need to accumulate a batch, incurring a waiting time that the model ignores, and the appropriate comparison would be against online policies that schedule requests on arrival (e.g., continuous batching in vLLM), not against offline schedules. The single-processor example in the response only shows that shortest-job-first reduces mean completion time, which is a classical result and does not justify the offline modeling choice.

2. The simple greedy outperforms the proposed algorithms, even on TCT. In the new CPU table, the deferred-admission greedy without LP grouping is better than both Algorithm 1 and Algorithm 2 on both TCT and makespan, by up to 44% (Algorithm 1) and 82% (Algorithm 2) in TCT on Code. Combined with the authors' confirmation that the greedy has a better makespan bound (8 vs. 32/36), this suggests the benefit comes from deferred admission itself, while the LP-guided grouping, which is the paper's main technical contribution, does not help and in fact hurts in practice. Its value appears to be mainly in enabling the TCT proof.

Overall, the theory is correct and well presented, and I appreciate the authors' effort. However, the offline setting does not match the latency objective it optimizes, the response confirms that the proposed algorithms are dominated in practice by a simpler policy. I therefore maintain my original score.

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

The paper studies offline scheduling of LLM requests across separate prefill and decode memory pools, minimizing the sum of completion times. Its distinctive coupling is that a completed prefill retains its prompt KV cache until decode admission, while decode memory demand grows with generated tokens. The authors prove strong NP-hardness, construct a memory-time-load LP lower bound with polynomial-time separation, and give two deterministic approximation algorithms based on LP-guided grouping and peak decode-memory reservation. Algorithm 1 achieves 8 + 4/(1-alpha) + 8/(1-beta) for alpha,beta < 1; Algorithm 2 uses large/small demand classes to obtain a uniform 36-approximation for every feasible instance. Validation includes small-instance ILP comparisons, larger comparisons with the LP lower bound, and two-H100 experiments with Qwen2.5-7B and Llama-3.1-8B on trace-derived offline batches.

Critical strengths
  1. The formulation captures a meaningful coupling that a single memory-budget model misses: waiting for decode admission prolongs occupancy of prefill memory (Sections 2.1-2.2). Accounting explicitly for both this retained cache and growing decode demand makes the optimization problem useful as a theoretical foundation for disaggregated serving. The strong NP-hardness result also holds in the simple one-slot-per-phase setting.

  2. The paper provides an end-to-end approximation framework, including an efficiently separable LP relaxation and a uniform guarantee that covers requests approaching or reaching an entire pool's capacity. In particular, the accounting of waiting slots through decode congestion, the less-than-two-factor peak-reservation load bound, and the class-based charging argument address the two-pool coupling. The proofs in Appendices B-F appear internally consistent on inspection. Table 1 further shows substantially better observed ratios than the worst-case constants, although the larger-instance numbers are ALG/LP rather than exact optimality gaps.

Critical weaknesses
  1. The practical motivation for the offline objective is insufficiently established. The Introduction (p. 2) explicitly states that the paper studies offline scheduling, and Section 2.1 (p. 3) assumes that all requests arrive at time zero with prefill durations and output lengths known in advance. These assumptions are disclosed, but the paper does not identify a concrete workload that jointly motivates this information model, P/D disaggregation, and minimizing the sum of request completion times.

  2. The choice of P/D disaggregation is not sufficiently justified for the evaluated hardware and model scale. The experiments dedicate one H100 to prefill and another to decode for Qwen2.5-7B and Llama-3.1-8B, but do not establish which bottleneck makes this split preferable to an appropriately configured colocated deployment for these offline workloads.

  3. The experiment is too narrow to establish robustness across hardware and model scales. All GPU experiments use two H100 GPUs and only Qwen2.5-7B and Llama-3.1-8B, which are similar in parameter count. Varying the software KV-cache capacity on this setup does not substitute for evaluating GPUs with different compute-to-memory-bandwidth ratios, memory capacities, or interconnect characteristics.

Questions for authors
  1. Please clarify the practical motivation for the offline setting and objective. What concrete application has all requests available at time zero, with prefill durations and exact output lengths known in advance, and benefits primarily from minimizing the sum of completion times rather than makespan, throughput, or GPU cost? Please explain how the required information would be obtained in that application and why this objective captures its actual needs.

  2. Please justify the deployment choice of dedicating one H100 to prefill and another to decode for the evaluated 7B/8B models. Which measured bottleneck makes P/D disaggregation preferable to colocated serving in these workloads? Please support the explanation with interference, GPU-utilization, and KV-transfer measurements under comparable resource budgets, and discuss the results against both the existing tensor-parallel colocated baseline and two independent single-GPU colocated replicas.

  3. Can you provide additional experiments on GPU types such as RTX 4090, RTX 5090, and A100, and on models spanning meaningfully different parameter scales and architectures, including MoE models and additional dense models? Please report the feasible deployment and parallelism configurations for each setting, and compare completion time and throughput against appropriate colocated and P/D baselines. These tests would help establish whether the observed benefits persist beyond the current two-H100, 7B/8B setup and how they depend on hardware and model characteristics.

3 comments
AuthorsOpenReview ↗

Response to Reviewer mm4h

We thank Reviewer mm4h for the detailed assessment.

Weakness 1: Practical motivation and the offline objective

A motivating scenario is a backlog of independent code generation requests in an existing P/D service. For example, after a code change, a continuous integration (CI) job can identify the target test classes and release one generation request per class as a single batch at t=0t=0. The prompts can include source code and existing tests. With one GPU per phase, prefill for a long prompt can proceed while another request generates a test. See Weakness 2 for the deployment comparison.

  • Why minimize TCT? Suppose 99 requests take 1 second each and one request takes 100 seconds. All are available at t=0t=0 and run serially on one processor. Both orders have the same makespan (199 seconds) and batch throughput. The mean completion time is 149.50 seconds with the long request first and 51.49 seconds with the short requests first. The latter order lets users start reviewing or testing 99 results within the first 99 seconds.

  • How are the parameters obtained? The model's tokenizer gives the input token count pip_i. We interpolate prefill measurements at different prompt lengths on the target GPU and convert the estimate to mim_i time slots. In our controlled experiments, we fix the output length at did_i tokens by ignoring the EOS token. In ordinary serving, output lengths would generally need to be predicted.


Weakness 2: Justification of the P/D deployment

We assign one H100 to prefill and one to decode so the two phases can run concurrently on separate GPUs.

  1. Why separate the phases for a batch released at t=0t=0? KV-cache capacity limits how many requests can run at once. Later requests can start prefill while earlier requests are still decoding. On a shared GPU, prefill for long prompts can delay ongoing decode steps. On the Code workload, Table 4 reports mean TPOT of 10.60–12.14 ms for Colocated and 6.24–7.01 ms for our algorithms. With separate GPUs, the system transfers the KV cache between phases and coordinates admission under the two memory limits.

  2. What do the results show? With two H100s in each setup, both algorithms reduced TCT on the Code workload by 41.8–49.0% relative to vLLM P/D and 30.7–38.9% relative to the best tested colocated baseline across the two models (Table 2). The vLLM P/D comparison uses the same one-GPU-per-phase deployment and shows the benefit of our admission policies within that setup.


Weakness 3: Evaluation scope

We extended the evaluation to Qwen2.5-14B-Instruct (Appendix H.3) using the same two H100 GPUs, with one GPU per phase, 250 requests per workload, and κ=2\kappa=2. All methods use the same workloads and KV cache budgets.

Table R1. TCT normalized by the vLLM P/D baseline (lower is better).

WorkloadvLLM P/DAlgorithm 1Algorithm 2
Conversation1.0000.8130.940
Code1.0000.5780.596

On the same 14B setup, both algorithms reduced TCT relative to vLLM P/D.


Question 1: Why minimize TCT in the offline setting, and how are request parameters obtained?

See Weakness 1 for the motivating workload, the TCT example, and how we obtain the request parameters.


Question 2: Why dedicate one H100 to each phase, and how does P/D compare with colocated serving?

See Weakness 2 for the deployment rationale and Code results. DistServe [1] documents interference between prefill and decode on shared GPUs. In Table 2, colocation without chunked prefill achieved lower TCT than vLLM P/D in all four cases and gave the lowest TCT on the Conversation workload.


Question 3: What are the completion time and throughput results on a larger 14B model?

Please see Table R1 in Weakness 3 for normalized TCT on Qwen2.5-14B-Instruct. Table R2 reports request throughput for the same runs.

Table R2. Request throughput on Qwen2.5-14B-Instruct (requests/s)

WorkloadvLLM P/DAlgorithm 1Algorithm 2
Conversation2.2761.8901.678
Code6.5294.8254.764

Relative to vLLM P/D, both algorithms reduced mean request completion time on both workloads. They took longer to finish each 250-request batch, yielding lower request throughput.

See Appendix H.3 of the revised manuscript for details and Table 5 for the full serving results.


References

[1] Zhong et al. DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving. OSDI 2024.

In what real world scenario, all the requests arrive at the same time? And why in this scenario, we need to disaggragete prefill and decode?

Thank you for the follow-up. We address both questions below:

Question 1: In what real-world scenario do all the requests arrive at the same time?

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=0t=0 (Section 2.1, p. 3). Individual requests may be submitted at different times; the common release time t=0t=0 simply marks when the full batch becomes available to the scheduler. We have revised Section 2.1 to remove this ambiguity. This batch release at t=0t=0 commonly occurs in two settings:

  1. CI unit test generation (Single-job burst): A code change can trigger a continuous integration (CI) job that identifies target test classes and submits one generation request per class in a single batch at t=0t=0 (directly matching our Azure Code workload). Meta’s TestGen-LLM illustrates code changes triggering batch unit-test generation in practice [1].
  2. Periodic batch inference (Windowed backlog release): In asynchronous or high-load inference services, requests arrive over time, accumulate in a queue, and are released together to the scheduler at scheduled windows (t=0t=0).

Why minimizing Total Completion Time (TCT, ∑iCi\sum_i C_i) matters here: To further clarify the metric rationale from your earlier question, in CI test generation each generated test enters compilation and validation as soon as it is returned. Minimizing TCT reduces the average wait before validation begins, whereas makespan (max⁡iCi\max_i C_i) only cares about the last request:

Example (TCT vs. Makespan): Suppose 99 short requests (1 s1\text{ s}) and 1 long request (100 s100\text{ s}) are released at t=0t=0. Running the long request first (Schedule A) vs. running the 99 short requests first (Schedule B) gives the same makespan (199 s199\text{ s}). However, Schedule A forces all 99 short requests to wait 100 s100\text{ s} (average wait 149.5 s149.5\text{ s}), whereas Schedule B returns 99% of the tests within 99 s99\text{ s} (average wait 51.5 s51.5\text{ s}, nearly a 3×3\times reduction).


Question 2: Why disaggregate prefill and decode in this scenario?

In short: GPU memory is too small to process the whole batch at once, so some requests must prefill while others decode—and P/D disaggregation prevents the two phases from slowing each other down.

  1. Memory limits force overlapping waves of prefill and decode: For a realistic batch (n=250n=250), total KV-cache demand far exceeds GPU memory (∑ipi≫MP,∑ihi≫MD\sum_i p_i \gg M_P, \sum_i h_i \gg M_D). Thus, even when all requests are released at t=0t=0, a system cannot prefill all requests at once; requests must execute in waves, where the next wave prefills while the current wave decodes.
  2. Colocated serving suffers cross-wave interference: Test generation prompts include both source code and existing test classes. On a shared GPU, prefilling long prompts for the next wave delays ongoing decode steps for requests already generating tests [2] (mean TPOT on Code rises to 10.6–12.1 ms10.6\text{--}12.1\text{ ms} for Colocated vs. 6.2–7.0 ms6.2\text{--}7.0\text{ ms} for our P/D policies; Table 4).
  3. P/D disaggregation removes this interference—when paired with joint admission scheduling: With one GPU per phase, prefill for the next wave proceeds in parallel while the current wave decodes uninterrupted. However, at t=0t=0, naive P/D fails without coordinated admission:

    Example (Why Naive P/D Fails vs. Our Policies): Let MP=MD=10M_P = M_D = 10 with 4 requests at t=0t=0: two decode-heavy requests L1,L2L_1, L_2 (1 s1\text{ s} prefill, pi=5p_i=5; 10 s10\text{ s} decode, peak memory hi=6h_i=6) and two short requests S1,S2S_1, S_2 (1 s1\text{ s} prefill, pi=5p_i=5; 1 s1\text{ s} decode, hi=2h_i=2).

    • Naive P/D (vLLM P/D): Greedily admits L1,L2L_1, L_2 to prefill at t=0t=0 (5+5≤105+5 \le 10). At t=1t=1, L1L_1 enters decode (hL1=6≤10h_{L_1}=6 \le 10), but L2L_2 is blocked (6+6>106+6 > 10). L2L_2 waits in W(t)\mathcal{W}(t) for 10 s10\text{ s}, retaining 55 units of prefill memory and blocking S1,S2S_1, S_2 even though Decode has 10−6=410-6=4 free units (enough for both S1,S2S_1, S_2).
    • Algorithms 1 & 2: Coordinate both pools so S1,S2S_1, S_2 are not blocked behind retained prefill caches. Under the same two-H100 budget (Table 2), P/D with our admission policies reduces TCT on Code workloads by 40–49% over vLLM P/D and by 31–39% over the best tested colocated baseline.

We hope the above replies address your remaining concerns.

References

[1] Alshahwan et al. Automated Unit Test Improvement using Large Language Models at Meta. FSE 2024.

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

This paper studies request scheduling in prefill-decode disaggregated LLM inference, where the prefill and decode phases operate under separate GPU resources. The authors formulate the Dual-Memory Request Scheduling (DMRS) problem, aiming to minimize the sum of request completion times while accounting for the memory occupied by KV caches during prefill, waiting, and decoding. They show that DMRS is NP-hard and develop two LP-guided polynomial-time approximation algorithms. Experiments on synthetic and trace-derived workloads demonstrate improvements in total completion time compared with the vLLM disaggregated serving baseline.

Critical strengths

S1: The paper formalizes the coupling between prefill and decode admission decisions caused by KV cache memory occupancy, providing a mathematical framework for studying scheduling in disaggregated LLM inference.

S2: The paper establishes strong NP-hardness and develops two polynomial-time approximation algorithms with explicit worst-case guarantees.

Critical weaknesses

The formulation assumes that all requests arrive simultaneously and that their prefill processing times and output lengths are known in advance. In practical LLM serving systems, requests arrive dynamically, and output lengths are generally unknown until generation completes. These assumptions substantially simplify the scheduling problem and limit the applicability of the proposed algorithms to realistic online serving workloads.

Questions for authors
  1. How could the proposed algorithms be adapted to real-world settings where requests arrival and output lengths are unknown? Would these theoretical properties remain meaningful?

  2. How would the KV cache transfer latency and bandwidth constraints affect the formulation?

  3. Could the authors compare against scheduling mechanisms from recent disaggregated serving systems and evaluate larger models or multi-GPU prefill/decode pools?

3 comments
AuthorsOpenReview ↗

Response to Reviewer uuMA

We thank Reviewer uuMA for recognizing the formulation and theoretical contributions. We respond to the main concern and questions below.


Weakness: 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=0t=0 (Section 2.1, p. 3). Individual requests may be submitted at different times; the common release time t=0t=0 simply marks when the full batch becomes available to the scheduler. We have revised Section 2.1 to remove this ambiguity.

  1. Practical examples.

    • CI unit test generation (Single-job burst): A code change can trigger a continuous integration (CI) job that identifies target test classes and submits one generation request per class in a single batch at t=0t=0 (directly matching our Azure Code workload). Meta’s TestGen-LLM illustrates code changes triggering batch unit-test generation in practice [1].
    • Periodic batch inference (Windowed backlog release): In asynchronous or high-load inference services, requests arrive over time, accumulate in a queue, and are released together to the scheduler at scheduled windows (t=0t=0).
  2. 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.

  3. 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.


Question 1: How can the algorithms handle unknown arrivals and output lengths?

  1. An extension combines batch scheduling with output length prediction.

    • Arrivals: Requests arriving at different times can be collected into batches and scheduled when the previous batch finishes. More frequent rescheduling must account for requests still running and the memory they occupy.
    • Output lengths: Predictions can guide request ordering and decode memory reservations. Runtime memory checks and an explicit policy for requests exceeding their predicted lengths are needed.
  2. Under the same P/D design, online policies that use predicted output lengths face the same admission dependencies captured by our offline model. Our offline lower bounds provide a starting point for deriving competitive ratios in this non-clairvoyant setting. Hence, these theoretical properties remain meaningful.


Question 2: How would KV transfer latency and bandwidth affect the formulation?

Transfer adds communication constraints and changes memory occupancy.

  • Transfer latency: Decode must wait for KV transfer to finish. The model must specify when prefill memory is released and decode memory is allocated. Retaining caches during transfer can delay subsequent prefills.
  • Bandwidth constraints: Concurrent transfers share link bandwidth. Transfer completion times and the resulting memory occupancy depend on bandwidth allocation, requiring additional scheduling analysis.

Question 3: Can we evaluate a larger model?

We additionally evaluated Qwen2.5-14B-Instruct (Appendix H.3) on two H100 GPUs, with one GPU per phase, 250 requests per workload, and κ=2\kappa=2. All methods use identical workloads and KV capacity budgets.

Table R1. TCT normalized by the vLLM P/D baseline; lower is better.

WorkloadvLLM P/DAlgorithm 1Algorithm 2
Conversation1.0000.8130.940
Code1.0000.5780.596

Both algorithms achieve lower TCT on this larger model:

  • Conversation: Algorithms 1 and 2 reduce TCT by 18.7% and 6.0%, respectively.
  • Code: Algorithms 1 and 2 reduce TCT by 42.2% and 40.4%, respectively.

See Appendix H.3 of the revised manuscript for details and Table 5 for the full serving results.


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.

Dear Reviewer uuMA,

We would like to follow up on our response and the revised manuscript to ask whether they have addressed the concerns you raised in your comments. Should any issues remain, we would be happy to provide further clarification.

If your concerns have been resolved, we would greatly appreciate it if you could update your comments and rating accordingly.

Thank you once again for your valuable time and constructive feedback.

Thank you for the detailed response and the additional experiments. The clarification regarding batch release times helps explain the intended scheduling setting, and the new results on Qwen2.5-14B provide additional evidence of the effectiveness of the proposed algorithms. I appreciate the theoretical contributions of this work, but I remain concerned about the gap between the scheduling assumptions and practical disaggregated LLM serving systems. Therefore, I will maintain my original rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.