Request Scheduling and Preemption

Two requests arrive together. One will generate 40 tokens, the other 4,000. Serve them first-come-first-served with the long one first and the short request waits for the entire long generation, a delay 100 times its own service time. Serve the short one first and total waiting time collapses. Shortest-job-first is optimal for average waiting time and has been since the 1950s.

The obstacle is specific to autoregressive generation: nobody knows which request is which. Output length is revealed only by generating it.

Head-of-line blocking, and two ways out

Run-to-completion scheduling gives head-of-line blocking its classic form. Continuous batching softens it, since a finished sequence leaves its slot immediately, but does not remove it: a slot occupied by a 4,000-token generation is unavailable for the whole time, and when the batch is full new arrivals queue behind it.

Preempt. FastServe exploits the fact that generation is incremental to preempt at the granularity of a single output token, running a multi-level feedback queue that demotes long-running requests so short ones are not starved. It reports throughput improvements of up to 31.4x and 17.9x over vLLM at the same average and tail latency requirements respectively (Wu et al., 2023, arXiv:2305.05920).

Predict. Exact output length is not predictable, but relative order often is. Framing scheduling as learning to rank, and using the predicted ranks to approximate shortest-job-first, gave 2.8x lower latency in chatbot serving and 6.5x higher throughput in synthetic data generation (Fu et al., 2024, arXiv:2408.15792). The insight is that ranking is a far easier learning problem than regression, and ranking is all the scheduler needs.

What preemption actually costs

Preempting a sequence means deciding what happens to its KV cache. vLLM, which introduced paged KV cache management, offers the two options (Kwon et al., SOSP 2023, arXiv:2309.06180):

Recompute. Drop the blocks, and when the request resumes, re-run prefill over its prompt plus the tokens generated so far. Memory is freed instantly. The cost is compute, and it grows as the sequence lengthens, so preempting a request that is 3,000 tokens into generation is far more expensive than preempting one at 100.

Swap. Copy the blocks to host memory and back. The cost is PCIe bandwidth in both directions and the latency of the transfer, which competes with the transfers the running batch needs.

Neither is free, and both have a thrash regime. When memory pressure is sustained, the server can spend more time evicting and restoring than generating, and effective capacity falls below what a static memory calculation predicts. Admission control exists to prevent entry into that regime rather than to manage it.

Scheduling is a policy question, not only a mechanism

The choice among FCFS, SJF-by-prediction, and priority classes is a decision about which requests are allowed to be slow. Approximating SJF minimises mean waiting time and systematically penalises long generations, which is correct for a chat product and wrong for a batch summarisation job whose requests are all long. A serving tier handling both needs separate queues with separate SLOs, not one clever policy.

Fairness is the other axis. Pure SJF starves long requests indefinitely under sustained load, which is why practical schedulers use aging, multi-level feedback, or a per-tenant token budget rather than raw SJF.

When it breaks

Length predictors degrade silently under distribution shift. A ranker trained on last quarter's traffic mis-orders a new workload, and the failure mode is not an error but a gradual return to FCFS-like tail latency. The predictor needs the same monitoring as any other production model.

Preemption interacts badly with prefix caching. Evicting a sequence may free blocks that a shared prefix depends on, so an eviction taken to relieve pressure destroys cache that other requests were about to reuse, and the recomputation shows up on a different request. Eviction policy and prefix-sharing policy have to be designed together.

Streaming clients notice preemption. A recompute-preempted request pauses mid-stream and resumes, so the user sees a stall in the middle of an answer. Inter-token latency variance, not just its mean, is part of the user-visible SLO.

Speculative decoding changes the accounting. Draft tokens consume batch slots and are discarded on rejection, so under saturation a technique that lowers latency at low load can lower goodput at high load. Scheduling policy and speculation policy must be tuned against the same load profile.