Continuous Batching Explained: Orca, vLLM & Iteration-Level Scheduling
Static batching makes the whole GPU wait on the slowest request. Continuous batching retires finished requests and admits new ones at every decode step — the scheduling trick, plus the memory fix that makes it possible.
Explain it like I’m five
Imagine a teacher reading aloud from every kid’s storybook, one word per book, going around the circle. When one kid’s story ends, she doesn’t wait for the others to finish their books — she hands the next kid their book and keeps reading. The circle is always full.
A GPU serving chat works the same way: every step, it writes one new word — one token — for every request in its batch. The old way filled a batch and waited until the longest request finished before letting anyone new in, so a haiku sat waiting on an essay. Continuous batching rebuilds the batch at every single step: a finished request leaves, a waiting prompt takes its seat, and the GPU never babysits an empty chair.
Intuition: serving is about utilization, not the batch
Thousands of people chat with the same model at once — one GPU serving them all. How does it not melt? The answer is not a faster model; it is a scheduler that refuses to let the GPU idle. Static batching synchronizes on the slowest request. Continuous batching re-schedules every token, keeping the GPU fed.
Start with the physics of generation. A language model produces text autoregressively: each forward pass emits exactly one new token per request. To serve many users, you batch requests together and run one forward pass over the whole batch per step. The naive way to do this — static batching — collects a batch of requests, pads them, runs them together, and waits until every request in the batch finishes before starting the next one.
The problem is that requests finish at wildly different times. One user asks for a haiku — twenty tokens. Another asks for an essay — two thousand. Nobody knows the output length in advance, so the batch cannot move on until the longest request completes. This is head-of-line blocking: the whole GPU waits on one slow request while the slots of finished requests sit idle, burning full forward passes on empty chairs. To make it worse, static batching typically pads every sequence to the longest one, so the GPU also burns compute on padding tokens that mean nothing.
Notice what kind of waste this is. It is not a compute problem — the GPU is doing the same number of FLOPs per step either way. It is a utilization problem: expensive GPU slots are occupied by requests that have nothing left to say. The fix therefore lives in the scheduler, not the kernel. At every decode step, retire finished requests and slide new ones into their slots. The batch is rebuilt every iteration — and that is continuous batching, also called iteration-level scheduling or in-flight batching.
Static batching synchronizes on the slowest request; continuous batching re-schedules at every decode step, so the GPU’s forward passes are always spent on requests that still have tokens left to generate.
How the scheduler works, step by step
Iteration-level scheduling
Mechanically, continuous batching is simple — deliberately so. Each iteration of the scheduler does three things. First, it retires: any request that emitted its end-of-sequence token (or hit its length limit) leaves the running batch immediately, and its GPU state is freed. Second, it admits: waiting prompts are prefilled — one compute-heavy forward pass over the whole prompt — and slide into the freed slots. Third, it runs: a single forward pass over whatever is in the batch, generating one new token for every running request. Then the loop repeats. The composition of the batch changes at every single token, which is why Orca’s authors named the idea iteration-level scheduling.
The crucial detail is that “one forward pass” still means one kernel launch over the whole batch per step — the GPU is not doing extra launches. What changes is only membership: which requests are inside the batch when the launch happens. A request that finishes at step 20 does not hold its slot hostage for another 1,980 steps while an essay finishes; the very next step, a new prompt is being prefilled into that slot.
Selective batching: batching operations, not just requests
Orca’s second idea, selective batching, answers a subtle question: how do you run one forward pass over requests with different sequence lengths at all? The insight is that not every operation in a transformer needs the sequences to line up. The linear layers — the big matrix multiplications in the MLPs and projections — operate token by token, so tokens from different requests can be concatenated and pushed through one batched GEMM regardless of which sequence they came from. Only attention is genuinely per-request, because each request attends to its own keys and values. So the engine batches selectively: non-attention operations across requests of different lengths, attention computed per request. The per-request attention is exactly where the KV cache lives — each request’s growing key/value history — which is why the memory story below matters so much.
Where the prefill goes
New prompts cannot just join a decode step; their prompt tokens must first be processed in a prefill pass, which is compute-bound and much heavier than a single decode step. Admitting a long prompt therefore briefly stalls the decode requests sharing that step — their time-per-token spikes while the prefill hogs the batch. Production schedulers handle this with chunked prefill (splitting a long prompt across several steps so each step stays balanced) or by disaggregating prefill and decode onto separate GPUs entirely, shipping the KV cache between them. The interview section below digs into that tradeoff.
Toy example: 4 slots, 6 decode steps. Darker cells are requests admitted mid-batch — no waiting for D to finish.
Retiring and refilling slots every step is easy to say and hard to do, because every request carries its own growing KV cache. Jam requests together naively and their caches fragment the GPU memory into unusable shards. The vLLM paper solved exactly this with PagedAttention — the next section’s second use case.
Real-world use: from the Orca paper to every serving stack
Continuous batching went from a 2022 research idea to the default scheduler in production LLM serving in about a year — because it fixed the utilization problem every serving team was staring at, and vLLM fixed the memory problem underneath it.
The paper that named the idea. “Orca: A Distributed Serving System for Transformer-Based Generative Models” (Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, Byung-Gon Chun — Seoul National University and FriendliAI, OSDI 2022) introduced iteration-level scheduling: the scheduler makes a new batching decision at every iteration instead of every request, so finished sequences return immediately and new ones enter without waiting. It also introduced selective batching, batching non-attention operations across requests of different lengths while computing attention per request.
The paper that made it practical. “Efficient Memory Management for Large Language Model Serving with PagedAttention” (Woosuk Kwon, Zhuohan Li, Sicheng Zhuang, Ying Sheng, Lianmin Zheng, Cody Yu, Joey Gonzalez, Hao Zhang, Ion Stoica — UC Berkeley, SOSP 2023, arXiv 2309.06180) attacked the memory wall underneath continuous batching: naive engines reserve a contiguous KV buffer per request sized for the worst case, wasting 60–80% of KV memory to fragmentation. PagedAttention stores the cache in fixed-size non-contiguous blocks addressed through a per-request block table — the operating system’s virtual-memory trick applied to attention — allocating pages on demand and sharing them copy-on-write for parallel sampling and beam search. vLLM pairs it with fine-grained iteration-level batching and preemptive scheduling.
Today iteration-level scheduling is the industry default. Open serving engines schedule at iteration level out of the box — NVIDIA’s TensorRT-LLM calls the same idea in-flight batching — and the principle has become the water every serving system swims in: never let a finished request hold a GPU slot. The research frontier moved on to what happens inside the step — chunked prefills, prefill/decode disaggregation — but every one of those systems still re-schedules every iteration.
Source: “Efficient Memory Management for Large Language Model Serving with PagedAttention,” Kwon et al., SOSP ’23 ↗
Source: Anyscale explainer on continuous batching in production serving ↗
The Orca paper reports a 36.9× throughput improvement over FasterTransformer; the vLLM paper reports 2–4× higher throughput than FasterTransformer and Orca at equal normalized latency — and the vLLM launch announcement claims up to 24× higher throughput than HuggingFace Transformers. These are the papers’ and authors’ own reported figures, not independent benchmarks.
The pattern is always the same: find the idle resource, then re-schedule around it. Static batching left GPU slots idle; PagedAttention reclaimed the idle KV memory those slots needed. When your interviewer asks “how would you serve this model,” they are listening for that reflex — name the bottleneck, then name the scheduler that removes it.
Work the head-of-line blocking by hand
A static batch of 4 requests with output lengths of 20, 50, 200, and 2,000 tokens, at roughly 50 ms per decode step. The batch cannot advance until the longest request finishes.
Same GPU, same model, same requests — the only change is when the scheduler is allowed to make decisions.
The scheduler in thirty lines
class Scheduler:
def __init__(self, max_tokens, block_size=16):
self.waiting = [] # prompts not yet scheduled
self.running = [] # requests with KV pages on GPU
self.max_tokens = max_tokens
self.pages = PagePool(block_size)
def step(self, new_requests):
# 1. retire finished requests — their slots free immediately
for req in list(self.running):
if req.finished:
self.pages.free(req.blocks) # return KV pages to the pool
self.running.remove(req)
deliver(req.output)
# 2. admit waiting prompts into the freed slots
self.waiting.extend(new_requests)
budget = self.max_tokens - sum(r.tokens for r in self.running)
while self.waiting and budget > 0:
req = self.waiting.pop(0)
req.blocks = self.pages.alloc(req.prompt_len) # prefill KV, one block at a time
self.running.append(req) # joins the next forward pass
budget -= req.prompt_len
# 3. one forward pass over the whole batch: the decode step
logits = model.forward(self.running) # attention gathers KV via block tables
for req in self.running:
token = sample(logits[req])
req.append(token) # cache may grow by one more page
if token == EOS:
req.finished = True # retired at the top of the next step
# 4. preemption (production detail): if pages run out,
# evict a running request — swap its blocks to CPU or
# free them and recompute later. Never crash on OOM.The real vLLM scheduler adds a token budget per step, chunked prefill, and block-level preemption — but the loop above is the whole idea: retire, admit, one forward pass. Notice the PagedAttention sketch hiding in steps 1 and 2: KV memory is allocated and freed as fixed-size blocks per request, never as one contiguous slab, so retiring a request returns its pages to the pool instantly instead of leaving a hole.
Six questions that test the real understanding
What to say (≈90 sec): “Static batching collects a batch of requests, runs them together, and waits until every request finishes before starting the next. But generation is autoregressive — one token per request per step — and output lengths vary wildly: a haiku is twenty tokens, an essay is two thousand, and you never know the length in advance. So the batch can’t advance until the longest request completes. That’s head-of-line blocking: the slots of finished requests sit idle while the GPU keeps burning full forward passes over the whole batch. On top of that, static batching usually pads every sequence to the longest one, so you also burn compute on padding tokens. The waste isn’t compute — it’s utilization: expensive GPU slots occupied by requests with nothing left to say.”
Likely follow-up: “Couldn’t you just sort requests by length?” → Lengths aren’t known until generation finishes, arrivals are unpredictable, and sorting doesn’t fix variable finish times — it just reshuffles the same synchronization problem.
The answer that sinks you: “Because batching adds overhead.” Why it fails: vague and wrong-axis — the issue is idle slots synchronized on the slowest request, not launch overhead.
What to say (≈90 sec): “The scheduler runs a three-part loop every single iteration. First, retire: any request that emitted its end-of-sequence token leaves the running batch immediately and its KV pages are freed. Second, admit: waiting prompts get prefilled — one compute-heavy pass over the whole prompt — and slide into the freed slots. Third, run: one forward pass over the whole batch generates exactly one new token per running request. The batch composition therefore changes every token — that’s why Orca called it iteration-level scheduling. The GPU still does one kernel launch per step; the only thing that changes is which requests are inside the batch when the launch happens.”
Likely follow-up: “How can prefill and decode share one forward pass when the shapes differ?” → Selective batching: the linear layers operate token-by-token, so tokens from different requests concatenate into one batched GEMM; only attention stays per-request. That’s Orca’s second idea.
The answer that sinks you: “The batch refills when it’s empty.” Why it fails: that’s just static batching with extra steps — the whole point is re-scheduling at every iteration, not at batch boundaries.
What to say (≈90 sec): “Every request carries its own KV cache, which grows token by token as it generates — and for the full picture on why the cache exists, see the KV cache guide. Naive engines give each request one contiguous GPU buffer sized for the worst-case length it might reach. Two pathologies follow: internal fragmentation, where a request that stops at 50 tokens still holds its 2,048-token reservation, and external fragmentation, where freed gaps are too small for a new request. Systems waste 60–80% of KV memory this way, which directly caps how many requests fit in a batch — so the scheduler can’t refill slots it can’t afford. PagedAttention borrows the OS virtual-memory trick: store each sequence’s cache in fixed-size non-contiguous blocks, addressed through a per-request block table, allocated on demand one block at a time. The attention kernel just gathers the scattered blocks via the table. Blocks are reference-counted, so a shared prompt is stored once and copied only on divergence — copy-on-write, which saves up to 55% of memory on beam search in the paper’s evaluation.”
Likely follow-up: “What happens when memory still runs out?” → Preempt, don’t crash: swap a request’s blocks to CPU RAM or free them and recompute later when space frees up.
The answer that sinks you: “PagedAttention makes attention itself faster.” Why it fails: it’s an exact algorithm — the win is memory utilization letting you batch more requests, not a change to the attention math.
What to say (≈90 sec): “Prefill processes the entire prompt at once — it’s compute-bound, high-utilization, one big matmul. Decode generates one token per request — it’s memory-bandwidth-bound, streaming weights and the KV cache for very little compute. When you admit a long prompt into a decode batch, that step’s latency is set by the heaviest member: every decode request’s time-per-token spikes while the prefill hogs the batch. So you have an interference problem. The in-batch fix is chunked prefill: split a long prompt across several steps so each step stays balanced. The architectural fix is disaggregation — Splitwise and DistServe showed you can put prefill and decode on separate GPUs and ship the KV cache between them, eliminating the interference entirely. The tradeoff is interconnect bandwidth for the KV transfer plus the cost of the extra hardware, and it pays off when the workload has clearly separated prefill-heavy and decode-heavy phases.”
Likely follow-up: “When is disaggregation not worth it?” → When the interconnect can’t move the KV cache fast enough relative to the compute saved, or when request phases are mixed so neither pool stays utilized — then you’ve just added hardware and latency for nothing.
The answer that sinks you: “Prefill and decode should always share one batch — simpler is better.” Why it fails: ignores the interference entirely — the mixed step’s latency is set by the prefill, and your decode SLOs die.
What to say (≈90 sec): “It fixes idle slots, so ask when slots aren’t idle. First, no queue depth: if the arrival rate is low, there’s nobody waiting to refill freed slots — the scheduler has nothing to schedule. Second, uniform request lengths: if every request is roughly the same length, static batching barely wastes anything and the extra scheduling buys nothing. Third, prefill-bound workloads: if the bottleneck is the big prompt pass rather than decode idling, re-scheduling decode steps doesn’t touch it. Fourth, strict per-request latency SLOs: packing the batch raises every member’s time-per-token, so a latency-sensitive request can do worse in a full batch than alone. The diagnostic is always the same — measure GPU utilization and the fraction of steps doing useful work; continuous batching pays off exactly where slots sit idle.”
Likely follow-up: “How would you detect that in production?” → Track GPU utilization alongside per-step useful-token fraction and queue depth — idle slots with an empty waiting queue means the scheduler isn’t your problem.
The answer that sinks you: “Continuous batching always increases throughput.” Why it fails: no free lunch — with no queue it’s inert, and under tight latency SLOs the fuller batch can hurt the metric you actually care about.
What to say (≈90 sec): “They’re orthogonal layers that stack. Continuous batching is a scheduling policy — it decides which requests run each step. The KV cache is a reuse optimization — it avoids recomputing keys and values across steps, and PagedAttention is how the cache is managed so the batch actually fits in memory. FlashAttention is an IO optimization for the attention computation itself — tiling Q, K, V through SRAM so the N×N matrix never hits slow memory. In practice they divide the work by phase: prefill is compute-bound, so it uses tiled FlashAttention-style kernels; decode is memory-bound on KV reads, so PagedAttention’s block management is what lets you raise the batch size — and a bigger batch means each weight read serves more tokens, raising arithmetic intensity. The composed picture is tiled attention over paged KV blocks, re-scheduled every iteration.”
Likely follow-up: “So why doesn’t FlashAttention fix decode?” → Because decode’s bottleneck is streaming weights and KV cache from HBM — there’s no large N×N intermediate to tile away, so it’s a different bottleneck with a different fix.
The answer that sinks you: “They’re competing optimizations — you’d pick one.” Why it fails: they attack three different bottlenecks — scheduling, cache reuse, attention IO — and production systems run all three at once.
Key takeaways
- Serving is about utilization, not the batch — the GPU’s job is never to idle on a finished request.
- Static batching synchronizes on the slowest request: head-of-line blocking plus padding waste.
- Continuous batching re-schedules every decode step — retire finished requests, admit waiting ones, one forward pass.
- The hard part is KV memory: contiguous reservation fragments it; PagedAttention’s block tables fix it.
- Prefill and decode want different schedules — chunk long prefills, or disaggregate the phases entirely.
- Your interview one-liner: iteration-level scheduling — retire and admit every decode step, with paged KV memory keeping the GPU fed.