acceptodds
Under review as a conference paper at ICLR 2027

Scheduling Backwards for LLM Batching under Progress Constraints

Abstract

Requests in an LLM decode batch generate their next tokens together, even though their attention workloads differ with context length. This motivates controlling resource disparity within a batch. We study an offline, nonpreemptive scheduling model with slots and a budget on generated-token progress differences; for equal prompt lengths, this also bounds context-length disparity. The constraint creates admission blackouts: a slot can be free even though no new request can join the running batch. We introduce Right-Aligned scheduling (RA), which constructs schedules backwards to coordinate request starts. A window invariant proves that RA never has a larger makespan than sorted static batching on any instance. Refined idle-time accounting yields a -approximation, with a tight factor on instances of at most requests for . An observation-based retiming rule preserves feasibility under valid duration upper bounds. On held-out conversational snapshots at a prespecified operating point, the retimed implementation improves logical throughput by over the strongest tested same-budget forward baseline, and by under bounded forecast perturbations.

Primary area:
learning theory
Keywords:
LLM serving, batching algorithm

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 3 reviews, above 27% of the others.
Reviewer_p8zJOpenReview ↗
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.

1 comment

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 δ\delta tokens, a progress budget α\alpha bounds the context-length difference between concurrent requests by α+δ\alpha+\delta. 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.

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

This paper studies scheduling for progress-homogeneous LLM inference, where active requests in a batch must have served-token counts within a budget α. The authors formalize the problem as a slot scheduling problem with capacity B and a progress-disparity constraint, propose Right-Aligned (RA) scheduling that constructs schedules backwards in decreasing length order, and prove a window invariant yielding instance-wise domination of sorted static batching plus an unconditional approximation factor below two, with a tighter constant on structured instances. Experiments are conducted in a logical event-driven simulator on Vidur trace prefixes and synthetic workloads.

Critical strengths
  1. The problem is real and well motivated. Progress homogeneity captures a genuine tension in continuous batching: newly admitted requests start at progress zero while running requests may have advanced hundreds of tokens, causing context-length skew, unfair slowdown, and KV-cache pressure. The mapping from progress disparity to current-context disparity is clean and non-trivial.

  2. The formulation is clean. The model with non-preemptive contiguous service and the α-fair active-batch constraint is a valid abstraction. The objective isolates the core trade-off between fairness and batch utilization, and the backward construction with its two-sided admissibility condition is a genuine algorithmic idea rather than heuristic glue.

Critical weaknesses

The evaluation is based on simulation. All main results come from a logical simulator reporting tokens per logical iteration rather than milliseconds; the decode-time surrogate uses an attention coefficient the authors describe as "assumed, not measured," and the native Vidur adapter was not run end-to-end. The abstraction differs from real serving in precisely the dimensions that drive latency: the clock assumes uniform per-iteration cost, prompt length enters only through the disparity bound, and interleaved prefill/decode (including chunked prefill) and paged KV-cache pressure are absent. Dynamic arrivals are also outside the guarantees. RA is an offline schedule assuming all requests are available at time zero, and the paper explicitly does not assert an online competitive ratio. Consequently, the logical-iteration gains cannot be translated into online QPS or tail latency, and the paper's own surrogate analysis suggests the benefit may be diluted once real hardware effects are included.

Questions for authors

Can the authors provide end-to-end measurements (e.g., TTFT, TPOT, P99 latency, tokens/s, GPU utilization) on at least one open-source serving framework and model, and, if full integration is infeasible, a decode-only microbenchmark using measured kernel latency rather than the assumed coefficient?

1 comment

We thank the reviewer for recognizing the scheduling formulation and the backward construction of RA. We have substantially strengthened the empirical evaluation to address the concern that improvements in theory may not translate into GPU execution time.

Our main result with vLLM shows that RA achieves 22.26% higher throughput than LPT-G. Even without imposing the budget constraint to the native vLLM, RA (with constraint) still gains 3.50% throughput over it. We also used direct measurements of vLLM's paged FlashAttention-2 kernel to show that heterogeneous context lengths can increase attention latency.

Our new results also include actual prefill, decode, and paged KV allocation in vLLM, and we report the number of decode iterations. RA uses 22.00% fewer decode iterations than LPT-G, and attains the basic makespan lower bound on seven of eight backlogs. This is the two-layer regime, which is covered by Theorem 5.

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

This paper studies the scheduling of large language model (LLM) inference requests under a progress-homogeneity constraint. Unlike conventional continuous batching, which primarily aims to maximize throughput, the proposed formulation limits the maximum progress difference among concurrently executing requests.

Critical strengths
  1. It is an interesting observation that the timing of request admissions, rather than merely their ordering, is essential when progress-homogeneity constraints are imposed.

  2. The backward scheduling strategy is conceptually simple but nontrivial. It directly addresses admission blackouts, a structural phenomenon that conventional forward greedy scheduling may fail to handle efficiently.

  3. There is theoretical analysis in addition to heuristic algorithms.

Critical weaknesses
  1. The problem formulation in Sec. 2 is very difficult to follow. The paper does not clearly distinguish the practical LLM batching problem from the abstract mathematical scheduling problem it actually solves. Although the mathematical problem is well-defined (despite some typos and a problematic presentation), the constraints seem quite hypothetical to me, and I don't see how they adequately connect to the actual computational behavior of LLM inference.

  2. The paper introduces quite some nonstandard terms, such as "capacity-respecting," "α-fair," etc., without sufficiently connecting them to established scheduling terminology. For example, "capacity-respecting" simply means satisfying the machine-capacity constraint, for which "capacity-feasible" would be more conventional. Similarly, the term "α-fair" may be misleading, as the proposed constraint concerns differences in request progress rather than fairness in the usual sense of resource allocation or service quality. The current terminology creates an unnecessary barrier to understanding the problem and obscures the relationship between the proposed formulation and classical parallel-machine scheduling.

  3. The theoretical analyses are based on strict assumptions (e.g., all requests available at time zero, having known processing lengths, advancing at a uniform rate, etc.) These assumptions simplify the problem but deviate from practical LLM serving systems. This creates a gap between the theoretical results and their applicability to real-world continuous batching.

Questions for authors
  1. What is the intended deployment scenario? For example, how would requests arriving during an existing schedule's execution be handled, and how often would the backward schedule need to be recomputed?

  2. To what extent can the theoretical results be applied to practical scenarios?

1 comment

We thank the reviewer for recognizing the importance of this observation. We have drastically revised the presentation for clarity.

Answer to W1: Math formulation and the connection to LLM inference.

The motivation for the progress budget is to control context-length heterogeneity within a decode batch. If prompt lengths span δ\delta tokens, bounding the difference in generated-token progress by α\alpha also bounds the active context-length spread by α+δ\alpha+\delta. This gives a direct connection between the progress constraint and LLM inference, independent of the attention implementation.

Naturally, the constraint introduces a scheduling problem: when a running request has progressed more than α\alpha tokens, a new request cannot join the batch even if a slot is freed. These admission blackouts create idle iterations that RA seeks to eliminate through backward scheduling.

We rewrote Sections 1–2 to explain this connection before developing the theory. Section 2 now formally defines slots, iterations, progress, and the admission condition. Section 4.2 further evaluates RA in vLLM with native attention kernels and paged KV allocation, demonstrating that the scheduling improvements translate into higher GPU throughput.

Answer to W2: Terminology.

We adopted capacity-feasible and α\alpha-feasible, and removed the former use of “fair” for the progress constraint. We define the terms in Section 2, and we also identify the unconstrained special case as classical P∥Cmax⁡P\|C_{\max} scheduling.

Answer to W3: Applicability of Assumptions.

The approximation guarantees apply to an offline backlog with known lengths. This setting is practically relevant because inference requests often arrive in bursts, creating backlogs that can be scheduled together. It also serves as a building block for multi-GPU serving, where requests assigned to each GPU form a local scheduling problem. We therefore view offline scheduling as an important problem in its own right.

We also evaluate RA directly in the practical setting of vLLM, with actual prefill, decode, and paged KV allocation. For uncertain lengths, Proposition 7 establishes that observation-based retiming preserves feasibility when the supplied lengths upper-bound actual lengths.

Answer to Q1–Q2: We now give both theoretical and empirical results for offline scheduling. In the exact-length offline setting, all requests are available before execution, so RA computes the schedule only once before processing begins. Our analysis focuses only on this offline problem, and handling new requests arriving during execution is currently outside the scope of our work.

Comments on the paper

1 comment

We thank the reviewers for their thoughtful comments. We have clarified the scheduling problem and reorganized the paper around our main theoretical contribution, and connected it to the practical application.

In this revised version,

  • Section 2 introduces the model, the connection between progress and context-length spread, and admission blackouts.
  • Section 3 presents the backward construction, the window invariant, instancewise domination of static batching, and the sharper approximation guarantees in one sequence.
  • Section 4 presents observation-based retiming alongside practical GPU evaluation.

The main new experimental evidence is an evaluation in vLLM with Qwen2.5 (Section 4.2). Across eight held-out backlogs of 128 requests, RA achieves 22.26% higher throughput than longest-first admission under the same progress gate and engine configuration. RA uses 22.00% fewer decode iterations and attains the basic makespan lower bound on seven of eight backlogs. The timed runs include prefill, decode, paged KV allocation, and output collection. Even without imposing the budget constraint on the native vLLM, RA (with constraint) still gains 3.50% throughput over it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.