What does the vLLM style continuous batching scheduler actually do at each step?

Short answer·Hard·4.0 · 0·~3 min·Asked atFireworks Ai Hugging Face NVIDIA·Relevant atCloudflare Groq Vllm

Attempt it

Describe the responsibilities of a vLLM style continuous batching scheduler at each decode iteration. Be specific about admission, eviction, preemption, and what happens when KV memory is over committed.

Free · 2 AI evals / day

**Continuous batching** is the scheduler at the heart of a modern serving engine like vLLM. Its job is to keep the GPU busy by deciding, on every decode step, which requests run together as one batch. Static batching, the old approach, groups a fixed set of requests, pads them to the longest one, and runs the whole group until every request finishes. The problem: a short request that finishes in 20 tokens is stuck waiting for a 2000-token neighbor. The GPU runs the long one nearly alone. That wasted capacity is head of line blocking. Continuous batching fixes this by scheduling at the iteration level. At the start of each step the scheduler reaps any request that just finished, frees its KV cache memory, and admits new waiting requests into the freed space. The binding constraint is KV memory, not compute. The scheduler counts how many free KV blocks exist and admits only as many requests as fit. If memory runs out mid-flight, it preempts a running request, either spilling its cache to CPU or dropping it to rebuild later. Then it runs exactly one batched decode step across every active request and loops. This per-step churn is why vLLM gets several times the throughput of naive serving.

**The continuous-batching scheduler** runs a tight loop once per decode iteration, mixing requests at the token level rather than the request level. It has five responsibilities per step. First, reap finished requests on EOS, a stop sequence, or hitting max tokens, and free their KV blocks. Second, recompute the KV-block budget, namely physical free blocks minus reservations. Third, admit waiting requests up to that budget, running prefill (or chunked prefill for long prompts) for each new admission. Fourth, if memory is over-committed, preempt lower-priority running requests. Fifth, assemble the batch tensor and run one batched decode step. Preemption has two flavors. Swap moves a victim's KV blocks to CPU memory and pages them back over PCIe on resume. Recompute drops the KV and rebuilds it via prefill when the request is readmitted. Recompute wins for short prompts where rebuild is cheap. Swap wins when the prompt is long and CPU bandwidth is available. Throughout, the scheduler tracks block reference counts so shared prefixes use copy on write, plus per-request priority, usually FIFO with starvation guards. The headline is that the scheduler, not paged attention alone, is the throughput lever. A weak admission policy strands KV memory and throws away most of the win.

TL;DR

Each iteration the scheduler reaps finished requests, recomputes the KV-block budget, admits waiting work up to it, preempts under pressure via swap or recompute, then runs one batched decode step.

Memory aid

Easy to grasp

Picture a busy restaurant kitchen with one shared stove. Every few seconds the head chef checks it. Finished dishes come off and free up burners. New orders waiting at the pass get started, but only as many as the freed burners can hold. If the kitchen is jammed and one long order is hogging space, the chef sets a dish aside, either keeping its half-cooked food warm in the fridge to resume later, or scraping it and re-prepping from scratch when room opens up. Then the chef pushes every active dish one step forward together, in a single sweep, before checking again. The stove is the GPU, the burners are KV memory, and that constant per-step reshuffle is continuous batching.

Key concepts

Continuous batching Paged attention KV cache Preemption

Concept explanation~2 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

The continuous-batching scheduler is the control plane of a modern LLM serving engine, and it is the single component that converts paged attention's memory savings into actual throughput. Candidates often stop at the phrase "vLLM uses paged attention and continuous batching" without being able to say what the scheduler does on each iteration. That gap is exactly what a hard systems interview probes.

The mental model: there is one GPU, a fixed pool of KV-cache blocks, and a stream of requests arriving and finishing at unpredictable times with wildly different prompt and output lengths. The scheduler runs a small, strict loop once per decode step, reconciling finished work, waiting work, and memory over-commit, then firing exactly one batched forward pass. Get the loop right and the GPU stays saturated. Get it wrong and you strand KV blocks, starve the device, and throw away most of the win.

This deep dive walks the per-iteration loop in order, explains why iteration-level scheduling eliminates head of line blocking, derives why the admission budget is measured in KV blocks rather than compute, contrasts the two preemption strategies, and covers the second-order machinery, chunked prefill and prefix-sharing reference counts, that separates a toy scheduler from a production one.

Static batching and the head-of-line problem

Static batching, sometimes called request-level batching, gathers a fixed group of requests, pads them to the longest sequence, and runs the entire group forward until every member emits its stop token. It is simple, and it is also where most of the throughput leaks away.

The failure is head of line blocking. Output lengths in real traffic vary by one to two orders of magnitude. A request that finishes in 20 tokens sits in the batch occupying a slot and KV memory until a 2000-token neighbor completes. For the long tail of that batch the GPU is effectively running a single sequence, far below its compute and bandwidth ceiling.

The other cost is admission latency. A new request that arrives one step after a static batch starts cannot join; it waits for the entire batch to drain. Under bursty load this inflates time to first token badly, even when the device has spare capacity, because membership is frozen for the lifetime of the batch.

Continuous batching, introduced by the Orca serving system and popularized by vLLM, attacks both problems by making batch membership dynamic at the granularity of a single decode step. The unit of scheduling is the iteration, not the request. Each step the running set can shrink as requests finish and grow as new ones are admitted, so the GPU is continuously refilled to near its memory ceiling. A finished short request frees its slot the instant it completes, and a waiting request can occupy that slot on the very next step rather than waiting for an unrelated 2000-token sequence to drain.

The five per-iteration responsibilities, in order

Why the admission gate is KV blocks, not compute

Preemption: swap versus recompute

Second-order machinery: chunked prefill and prefix sharing

Situations where this technique stops working.

2–4 min · Everything important, quickly.

Real products, models, and research that use this idea.

vLLM (UC Berkeley) pairs continuous batching with paged attention and is the reference scheduler most open-source serving builds on in 2026.
SGLang adds prefix-aware scheduling so requests sharing a long system prompt are admitted together and reuse cached blocks.

What an interviewer would ask next. Try answering before peeking at the approach.

QWhy does decode push a batch into over-commit even when admission was within budget?

Each running request grows its KV cache by roughly one block as its sequence lengthens. Admission only checks the budget at entry. After several steps the aggregate footprint of the running set climbs past free blocks, forcing preemption mid-flight.

3 more follow-ups an interviewer would ask next. Sign in to reveal them.

Red flags & common mistakes

The phrases that signal junior thinking. Click to expand.

Most common mistake

Describing it as static batching that pads to the longest sequence. The whole point is iteration-level scheduling, where finished requests leave and new ones join every step, with no head of line blocking.

60 second bullets to scan on the way to the call.

The five per-step responsibilities and why reap comes before admit
How iteration-level scheduling kills head of line blocking

Primary sources. Browse if you want the original framing.