- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper introduces Right-Aligned Scheduling (RA), a scheduling algorithm for continuous LLM batching with approximation guarantees. RA constructs the schedule backward, prioritizing longer requests to reduce idle execution capacity and thereby improve overall request completion time. The paper also provides approximation guarantees and evaluates RA using Vidur.
Critical strengths
- The paper tackles an interesting scheduling problem and provides theoretical approximation guarantees.
- The proposed algorithm introduces little scheduling overhead.
- The evaluation shows promising performance improvements.
Critical weaknesses
- The evaluation is overly simplified and relies primarily on simulation, while omitting important factors such as prefill and KV-cache management.
- The problem formulation appears somewhat disconnected from practical serving deployments, where fully offline scheduling without preemption is uncommon.
Questions for authors
Thanks for submitting your work. I enjoyed reading the paper and found the scheduling idea interesting. However, I found parts of the presentation difficult to follow, and I am not yet convinced that the targeted setting is sufficiently representative of practical LLM serving. The evaluation also abstracts away several important system effects. Below are some comments:
-
How practical is the assumed offline, non-preemptive scheduling setting? Production workloads typically involve online arrivals, and output lengths are generally unknown in advance.
-
Does the modeling account for heterogeneous attention costs across requests? Modern techniques such as FlashDecoding can substantially mitigate inefficiencies caused by heterogeneous sequence lengths. How does RA interact with or improve upon such mechanisms?
-
The evaluation is relatively small-scale, involving only a few hundred requests, and appears to rely entirely on simulation. A real-GPU evaluation would strengthen the paper substantially. The current setup also excludes prefill, KV-cache allocation, online arrivals, and hardware-level timing effects.
-
Some text in the evaluation is unusual. For example, “The native Vidur package was not available in this environment, and attempts to retrieve it and its dependencies failed at network resolution.” This reads more like an artifact of the paper's experimental environment than material appropriate for the paper and should be clarified or removed.
We thank the reviewer for recognizing the theoretical contribution and the scheduling efficiency of RA. We have carefully revised the presentation and added real-GPU experiments to strengthen the connection between the theoretical results and practical LLM inference.
Answer to: Why we make the offline assumption
The offline assumption is practically relevant because inference requests often arrive in bursts, creating backlogs that can be scheduled together. We therefore study how to minimize the makespan of such backlogs. Offline single-GPU scheduling also serves as a building block for multi-GPU serving. By assuming offline, we can isolate admission timing and establish theoretical guarantees. And our empirical results show that the theoretical results translate into practical improvements in throughput and efficiency.
Answer to: Heterogeneous attention costs and real GPU experiments
We clarified the connection between progress disparity and context-length spread in Section 2. When prompt lengths span δ tokens, a progress budget α bounds the context-length difference between concurrent requests by α+δ. Modern attention kernels can improve the efficiency of each decode iteration, while RA reduces the idle iterations caused by admission blackouts.
To examine the combined effect, we run RA directly in vLLM with its native attention kernels and paged KV allocation. RA achieves 22.26% higher throughput than LPT-G under the same progress budget, with 22.00% fewer decode iterations. Even without imposing the budget constraint to the native vLLM, RA (with constraint) still gains 3.50% throughput over it.