Request Scheduling & Queueing

Continuous batching told you the engine makes a scheduling decision every token step. This page is about the decision itself. Requests do not arrive in neat batches — they arrive at random, in bursts, with wildly different prompt and output lengths. Between the open socket and the GPU sits a scheduler whose choices determine, on the same hardware, whether a user waits 200 ms or 8 seconds, and whether the GPU bills you for useful tokens or idle silicon.

The loop

Every iteration the scheduler runs the same loop: look at the queue, pick a batch under the memory budget, run one GPU step, then repeat.

                 admission control
   arrivals ──►  ┌──────────────┐      ┌──────────────────────┐
   (random)      │  wait queue  │ ───► │   running batch       │
                 │  R5 R6 R7 …  │      │  R1 R2 R3 R4 (in HBM) │
                 └──────────────┘      └──────────┬───────────┘
                       ▲                          │  1 forward step
                       │  preempt: evict KV       ▼
                       └───────────────  GPU  ──► emit 1 token each
                                                  finished? free KV, admit from queue

Two budgets bound every choice: compute (how much math one step can do) and KV memory (how many requests’ caches fit in HBM at once, from the KV math). The scheduler is forever spending those two budgets against a queue of strangers.

Admission control

A new request can only join the running batch if there is free KV space for its cache. If HBM is full, it waits in the queue. Admission policy decides which waiter goes next: first-come-first-served is simplest and fairest; but you might prioritize short prompts (cheap, fast wins), or requests from a paying tier, or those closest to breaching their SLO. Admitting too aggressively risks running out of KV mid-flight; too conservatively leaves the GPU under-full and wastes the throughput you are paying for.

Preemption: the eviction trick

What happens when the running requests’ KV caches grow (every decode step adds a token) until HBM is about to overflow? The scheduler preempts a victim request: it evicts that request’s KV blocks to free memory, lets the survivors continue, and later recomputes or swaps back the victim’s KV to resume it.

HBM full, R4 must yield:
  evict R4's KV ─► free blocks ─► R1..R3 keep running
  later: re-admit R4, recompute its prefill (or swap KV from CPU), resume decode

Two recovery options: recompute (re-run the victim’s prefill from its tokens — cheap in memory, costs FLOPs and latency) or swap (copy its KV out to CPU RAM and back — costs PCIe bandwidth, saves the recompute). Either way preemption is the safety valve that lets the scheduler admit optimistically without crashing when memory tightens. It is also a latency cost: a preempted user’s tokens stall until they are scheduled back in.

Prefill and decode compete for the GPU

A subtle conflict: a freshly admitted request must prefill its whole prompt (a big, compute-heavy, parallel pass) before it can decode (one memory-bound token at a time). These two phases want the GPU at the same time. Run a large prefill and the decoding users’ tokens hitch (their TPOT spikes); starve prefill and new users wait forever for their first token (high TTFT). Schedulers mix them deliberately — chunked prefill breaks a long prompt into pieces interleaved with decode steps so neither phase monopolizes the GPU.

Knob	Helps	Hurts
Favor decode	low TPOT for active users	high TTFT for new arrivals
Favor prefill	low TTFT, fast first token	hitches existing users’ decode
Chunked prefill	balances both	bookkeeping overhead

Fairness vs throughput, and the SLO

The deepest tension: the highest-throughput policy is often unfair. Always batching the longest-prefix or short-output requests maximizes tokens/sec — and starves the unlucky long request indefinitely. SLO-aware scheduling flips the objective from “max tokens/sec” to “max requests that meet their deadline,” deliberately leaving some throughput on the table to bound tail latency. Queue depth is the load signal that ties it together: a growing queue means arrivals outpace service, so you raise admission pressure, shed load, or (next chapters) add replicas.

Throughput and latency are the same knob pulled opposite ways

Bigger batches and aggressive admission maximize tokens/sec and minimize dollar-per-token — but lengthen every individual user’s wait. A latency SLO is a cap on batch size in disguise. You cannot have maximum throughput and minimum latency at once; the scheduler is where you choose the point on that curve.

Worked example: queue depth as a cost-vs-latency dial

A GPU serves 50 requests/sec at steady state. Arrivals jump to 65/sec for a burst.

arrival 65/s, service 50/s → backlog grows 15 requests every second
after 4 s burst: queue depth ≈ 60 requests
TTFT for the last arrival ≈ 60 / 50 ≈ 1.2 s of pure queue wait

That 1.2 s is latency you are not billed extra for — but if the SLO is 500 ms TTFT, you have breached it. Your options are exactly the levers above: admit more aggressively (risking preemption), shed the overflow (drop requests), or scale out. Queue depth turned an invisible memory contention into a number you can alarm on.

It actually happened — Orca makes the schedule per-token (2022)

Before 2022, serving systems batched at the request level: pick a batch, run all of it to completion, then start the next — so one slow 2,000-token generation held a fast 10-token reply hostage for its entire run. Orca (Yu et al., OSDI 2022) introduced iteration-level scheduling — re-decide the batch every single token step, letting finished requests leave and new ones join mid-flight — paired with selective batching to handle the now-uneven shapes. That is the continuous-batching loop this page is built on, and the reason the scheduler has a decision to make every iteration at all. vLLM and the rest of the serving stack productionized the idea; Orca is where the request stopped being the unit of scheduling.

The architect’s lens

The scheduler sits between the socket and the GPU and spends two budgets against a queue of strangers. The five questions:

• Why does it exist? Because requests arrive at random, in bursts, with wildly different prompt and output lengths — something must decide who runs each GPU iteration under the two hard budgets: compute per step and KV memory in HBM.
• What problem does it solve? Allocating that scarce compute and KV across the queue — admission control (who joins when KV frees up), preemption (evict a victim’s KV when HBM fills, recovered by recompute or CPU swap), and refereeing prefill vs decode for the same silicon.
• What are the trade-offs? Fairness vs throughput vs SLO: aggressive admission maximizes tokens/sec but risks mid-flight preemption; favoring decode protects TPOT but spikes new arrivals’ TTFT (chunked prefill balances them) — and a latency SLO is really a cap on batch size in disguise.
• When should I avoid it? You never avoid scheduling — only choose the policy: FCFS for simplicity, SLO-aware to bound tail latency, priority for paid tiers — trading raw throughput for predictable deadlines as the workload demands.
• What breaks if I remove it? The GPU can’t coherently share among requests — either it serves one at a time (and falls over on concurrency) or admits blindly until KV overflows and crashes; queue depth, the load signal that drives autoscaling, has nothing watching it.

Check your understanding

1. What two budgets bound every scheduling decision, and where does each come from?
2. What is admission control deciding, and what goes wrong if it is too aggressive or too conservative?
3. Describe preemption and the two ways a preempted request’s KV can be recovered.
4. Why do prefill and decode conflict, and what does chunked prefill do about it?
5. In the worked example, why did TTFT for the last arrival reach 1.2 s, and what does queue depth let you do about it?

Show answers

1. Compute (how much math one GPU step can do) and KV-cache memory (how many requests’ caches fit in HBM at once, from the KV-cache math).
2. It decides which waiting request joins the running batch and when; too aggressive risks running out of KV mid-generation and forcing preemption, too conservative leaves the GPU under-full and wastes throughput.
3. Under memory pressure the scheduler evicts a victim request’s KV to free HBM; it recovers by either recomputing the victim’s prefill from its tokens (cheap memory, costs FLOPs/latency) or swapping the KV out to CPU RAM and back (costs PCIe bandwidth, saves recompute).
4. Prefill is a big compute-heavy parallel pass and decode is memory-bound one-token steps; running them together makes them fight for the GPU, so chunked prefill splits a long prompt into pieces interleaved with decode to keep TTFT and TPOT both bounded.
5. Arrivals (65/s) outpaced service (50/s), building a ~60-request backlog over the 4 s burst; at 50/s service the last arrival waits ~60/50 ≈ 1.2 s. Queue depth makes that contention an observable number you can alarm on and respond to by admitting harder, shedding load, or adding replicas.