What scheduling algorithms teach us about serving LLMs

Serving an LLM looks simple from the outside: accept a prompt, run a model, stream an answer. Inside the system, many requests compete for the same limited accelerator memory and compute. Some prompts are tiny. Others carry an entire document. Some answers finish after one sentence; others keep generating for minutes. A few callers pay for tighter latency, while background jobs mainly care that the work eventually completes.

The scheduler decides who moves next. That decision affects cost, responsiveness, fairness, and even which product features remain usable during a traffic spike. The algorithms are familiar from operating systems and networks, but LLM inference adds an important twist: the amount of work is uncertain, and each request changes shape while it runs.

What is LLM inference scheduling?

Direct answer: An LLM scheduler decides which requests enter memory, which tokens run next, and how scarce capacity is shared. A good policy treats prefill and decode separately, accounts for KV-cache pressure, protects interactive work without starving batch jobs, and stops admitting requests before queues become unbounded. Its job is predictable service under contention, not maximum utilization.

Four takeaways:

• Track first-token and inter-token latency separately.
• Budget resident tokens, not request count alone.
• Give lanes explicit shares and age waiting work.
• Reject before queue age breaks the promise.

A queue is compressed product strategy. It reveals whose wait matters, which work may be delayed, and what the system protects when capacity runs out.

There is no neutral queue

First-in, first-out feels impartial because arrival order is easy to explain. But imagine that a long document-analysis request arrives one millisecond before twenty chat messages. Strict FIFO can make every short interaction wait behind one expensive job. The queue preserved arrival order while producing an experience few users would call fair.

Moving short work ahead improves the average wait. It also creates a new risk: a steady supply of small requests can postpone a large one indefinitely. Giving every tenant an equal slice prevents one customer from taking the whole machine, but equal slices may be wasteful when their requests cannot be batched together. Adding priorities protects interactive traffic, yet an unchecked high-priority lane can quietly become the only lane that matters.

These are the choices behind how I design systems, not implementation details. Before selecting an algorithm, name the promise: fast first tokens for chat, predictable completion for batch work, isolation between tenants, a maximum queue wait, or the lowest cost per generated token. One policy rarely maximizes all of them.

LLM work changes shape while it runs

Prefill is a large, visible meal

During prefill, the model processes the input tokens and builds the state needed for generation. The scheduler knows the prompt length, so this phase is comparatively measurable. Long prompts demand substantial compute in a burst and occupy more cache memory. Starting several of them together can delay first-token latency across the entire batch. This phase split is measured in Sarathi-Serve.

Decode is a series of small, uncertain bites

During decode, each active request produces tokens incrementally. The output length is not known in advance. A request may stop naturally, hit a limit, call a tool, or be cancelled by a user who closed the page. Decode rewards continuous batching: finished requests leave and new ones join without waiting for a fixed batch to complete. That keeps the accelerator busy, but it turns scheduling into a decision repeated at nearly every step. This is the iteration-level scheduling introduced by Orca.

Memory becomes part of the queue

The key-value cache retains attention state for active sequences. As prompts and outputs grow, that cache can become the binding constraint even when raw compute remains. The PagedAttention paper shows how dynamic growth and fragmentation reduce batch capacity. A scheduler therefore chooses not just who runs, but whose state stays resident, who pauses, and whether pausing costs more than waiting to admit new work.

01 / ADMITAccept work the system can honor

02 / GROUPBatch compatible requests

03 / RUNShare decode progress

04 / RECLAIMRelease memory quickly

Old policies still help, if we read their fine print

The useful question is not “Which algorithm is fastest?” It is “Which workload and failure cost does this policy represent?”

A small scenario makes the tradeoff concrete

Suppose one model endpoint receives three kinds of work. Chat requests have short prompts and usually produce a few paragraphs. Document requests arrive less often, carry long context, and generate structured reports. An offline pipeline sends hundreds of summaries and has no human waiting on the stream.

Strict FIFO lets the offline pipeline build a wall in front of chat. Strict priority fixes chat but may leave the pipeline unfinished every afternoon. A single global shortest-job queue improves the dashboard average while allowing one noisy customer to dominate it with tiny calls.

A practical policy can combine ideas. Reserve most immediately available capacity for interactive work, but guarantee the batch lane a minimum share. Limit each tenant’s active tokens so one account cannot occupy every decode slot. Let unused reserved capacity be borrowed instead of sitting idle. Age waiting requests upward so a document job eventually crosses the line. Finally, stop admitting work once the promised queue-time bound cannot be met.

This hybrid is less elegant than naming one textbook algorithm. It is also easier to connect to product behavior: chat stays responsive, background work makes measurable progress, tenants remain isolated, and overload produces a clear refusal instead of an unbounded wait.

Continuous batching changes what “efficient” means

Traditional static batching waits for a group, pads inputs to compatible shapes, runs them together, and returns the result. That works well when jobs are similar. Generation is uneven: one sequence stops while its neighbor continues for another thousand tokens. Waiting for the longest member wastes capacity.

Continuous batching fills those gaps as requests finish. The GPU sees a moving group rather than a fixed cohort. This usually improves utilization, but a full batch is not automatically a good batch. Mixing a massive prefill with latency-sensitive decode can interrupt the smooth cadence users experience as streaming. Packing too many long sequences can exhaust cache and force expensive state movement. Chasing tokens per second alone can make time to first token worse.

The scheduler needs a budget for each kind of work: how much prefill can enter during a decode cycle, how many total tokens may be resident, and when a waiting request should take precedence over adding one more active sequence. Chunking a long prefill can reduce the time it monopolizes compute, though smaller chunks add coordination overhead. Sarathi-Serve calls this chunked prefill. Preemption can rescue urgent work, though it is only useful if saving, moving, or recomputing state costs less than the delay it avoids.

Utilization is a constraint, not the whole objective. An accelerator can be 100% busy doing work that violates the latency promise customers actually notice.

Fairness needs a unit

“Treat every request equally” is ambiguous. One request may contain fifty tokens and another fifty thousand. Request fairness gives both one place in line. Token fairness accounts for their different cost. Tenant fairness prevents a caller with many small requests from multiplying its share. Service-tier fairness deliberately gives different promises to different groups. A token-based model is evaluated in Fairness in Serving Large Language Models.

Choose the unit that matches billing and user expectations, then make it observable. A useful starting point is weighted token service per tenant, combined with a maximum waiting age. The weight expresses an intended share under contention. The age bound prevents a large or low-weight request from being postponed forever.

Fairness also applies over time. If a tenant is quiet, its share can be borrowed. When it returns, the system should restore its entitlement without instantly evicting every active request. That calls for a bounded burst allowance rather than rigid partitions. The goal is predictable access, not unused capacity.

Admission control comes before clever scheduling

No scheduler can create capacity. Once arrivals exceed sustainable service, the queue grows until latency, memory, or user patience fails. Hiding that condition behind retries makes it worse: timed-out clients submit again, duplicate work enters the queue, and useful throughput falls further.

Admission control makes overload explicit. It can reject immediately, ask the caller to retry after a real delay, route eligible work to another pool, degrade to a smaller model, or convert an interactive request into an asynchronous job. The right response depends on the product, but it should be selected before the incident.

Use bounds the system can enforce: maximum input length, maximum output reservation, active-token limits per tenant, queue capacity by lane, and a queue-age deadline. Cancel work as soon as the client disconnects when semantics allow it. Idempotency keys help prevent a retry from becoming a second expensive generation.

Common failure modes are surprisingly ordinary

• Optimizing the average. A better median can hide a much worse experience for the slowest five percent of requests.
• Trusting output estimates too much. A size prediction is useful for ordering, but it needs caps and correction when reality diverges.
• Letting priority become identity. Permanent high-priority callers can starve the shared system. Reserve capacity and age lower lanes.
• Ignoring cancellations. Generating tokens for a closed connection burns capacity and distorts throughput metrics.
• Confusing queue time with model time. Faster kernels do not repair an admission policy that permits an hour of waiting work.
• Testing with one prompt shape. Uniform synthetic traffic hides interference between long prefill, short chat, and sustained decode.

Measure the promise, not just the machine

Slice these signals by workload instead of collapsing them into one fleet-wide number. A healthy aggregate can combine excellent batch throughput with unusable chat latency. Also record scheduler decisions: why a request waited, which limit blocked admission, and when a priority or aging rule changed its position. Without that context, graphs show the symptom but not the policy that produced it.

A practical way to design the first policy

1. Classify the work. Separate interactive, long-context, and offline traffic only when their promises differ. Too many lanes create a policy nobody can reason about.
2. Write one service objective per lane. Define first-token, streaming, completion, and maximum queue-age expectations. State what happens when each cannot be met.
3. Set hard safety limits. Bound context, generation, resident tokens, per-tenant concurrency, and queued work before tuning an ordering rule.
4. Start with a legible hybrid. Weighted fair sharing between lanes, FIFO within a lane, and aging for old requests is often easier to operate than a highly predictive scheduler.
5. Replay a hostile workload. Mix prompt sizes, output lengths, cancellations, bursts, and one noisy tenant. Increase arrival rate past saturation and confirm that failure is controlled.
6. Tune from user-visible distributions. Change one control at a time, then compare latency percentiles, useful throughput, queue age, and fairness together.

A sophisticated scheduler is not automatically a mature one. The mature version has explicit promises, bounded starvation, boring overload behavior, and enough decision data to explain a bad request after the fact. Prediction can be added later when real traces show where a simpler policy leaves meaningful performance on the table.

The best scheduling policy is not the one that wins a clean benchmark. It is the one that keeps the product’s promises when the workload stops being clean.

Sources and further reading

• Orca (OSDI 2022): iteration-level scheduling and selective batching.
• PagedAttention (SOSP 2023): KV-cache fragmentation and paging.
• Sarathi-Serve (OSDI 2024): chunked prefills and stall-free batching.
• DistServe (OSDI 2024): prefill-decode interference and latency objectives.
• Fairness in Serving Large Language Models (OSDI 2024): token-based fair sharing.