What does the vLLM style continuous batching scheduler 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 core scheduling method of serving engines like vLLM. On every decode step it decides which requests run together as one batch, to keep the GPU busy. Static batching groups a fixed set of requests, pads them to the longest one, and runs the group until every request finishes. A request that finishes in 20 tokens then waits for a 2000-token neighbor, and the GPU runs the long one nearly alone. This waste 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 and frees its KV cache memory. It then admits new waiting requests into the freed space. The binding constraint is KV memory, not compute. It counts free KV blocks 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 one batched decode step over every active request and repeats. This per-step rebuilding 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, give running requests the blocks for their next tokens. If memory is over-committed, preempt lower-priority running requests. Fourth, if nothing was preempted, admit waiting requests up to the remaining budget, running prefill (or chunked prefill for long prompts) for each new admission. Fifth, assemble the batch tensor and run one batched decode step. Preemption has two types. 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. vLLM's V1 engine uses recompute only. Throughout, the scheduler tracks block reference counts so shared prefixes use copy on write, plus per-request priority, usually FIFO with starvation guards. The scheduler, not paged attention alone, is the throughput lever. A weak admission policy leaves KV memory unused and loses most of the gain.

TL;DR

Each iteration the scheduler reaps finished requests, recomputes the KV-block budget, preempts via swap or recompute if running work cannot grow, admits waiting work into what is left, then runs one 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. Dishes already cooking get the room they need first. If the kitchen is jammed, the chef sets a dish aside. Either the half-cooked food goes in the fridge to resume later, or the chef scrapes it and re-preps from scratch when room opens up. Only when nothing had to be set aside do new orders waiting at the pass get started, as many as the free burners can hold. 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 an LLM serving engine. It is the single component that converts paged attention's memory savings into actual throughput.

The setting is one GPU and a fixed pool of KV-cache blocks. A stream of requests arrives and finishes at unpredictable times, with very different prompt and output lengths. The scheduler runs a small, strict loop once per decode step. It reconciles finished work, waiting work, and memory over-commit, then runs exactly one batched forward pass. If the loop is right, the GPU stays fully used. If it is wrong, KV blocks sit unused, the GPU waits for work, and most of the gain is lost.

Iteration-level scheduling removes head-of-line blocking, and the admission budget is measured in KV blocks rather than compute. Preemption, chunked prefill and prefix-sharing reference counts are what separate 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 and pads them to the longest sequence. It runs the entire group forward until every member emits its stop token. It is simple, and it is also where most of the throughput is lost.

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. Membership is frozen for the lifetime of the batch.

Continuous batching was introduced by the Orca serving system and popularized by vLLM. It solves 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. 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.
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 main idea 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 removes head-of-line blocking

Primary sources. Browse if you want the original framing.