2.2 Continuous Batching

If PagedAttention answers “how many requests fit in GPU memory,” Continuous Batching answers “can the requests that fit actually keep the GPU fed.” That is the other half of the modern inference engine’s throughput jump. This section starts from traditional batching’s fatal weakness, shows where idle slots in a batch come from and how they get erased. The core idea is one sentence: schedule by iteration step instead of by batch.

⏰ Currency note: iteration-level scheduling follows the Orca paper; the Scheduler’s queues, preemption, and source walk-through are based on vLLM v0.32.0 (released 2026-10-18).

📑 Contents

• 1. Why batch at all
• 2. Static Batching’s fatal weakness
• 3. Continuous Batching: iteration-level scheduling
• 4. What happens in one scheduling loop
• 5. Working with PagedAttention
• 6. Source walk-through: the vLLM V1 Scheduler
• 7. Key tradeoffs in scheduling
• Summary
• Self-check list
• References

---

1. Why batch at all

Back to the first principle from the last chapter: Decode is memory bound. The bottleneck is moving the whole model’s weights from GPU memory into the compute units. There is a huge opportunity here—one weight move that only serves 1 token of 1 request is a waste; if that same move can serve tokens from many requests at once, arithmetic intensity jumps and idle compute gets used.

That is the value of batching: merge many requests’ compute into one large matrix op and amortize the weight-move cost.

Analogy: a commute shuttle. Sending a bus for one person (one weight move for one token) burns fuel badly; filling the bus first (one batch serving many requests) drops the per-person cost. Larger batches mean lower cost per token and higher system throughput.

📌 Key point: batching raises throughput and barely hurts per-request latency—because the bottleneck is moving weights, a bit more token compute is nearly “free” for memory-bound Decode. The only question is: how do you organize the batch?

---

2. Static Batching’s fatal weakness

The naive approach is Static Batching: gather a full batch of requests, send them through the model together, and only start the next batch when every request in this one has finished generating.

Sounds reasonable, but it has a fatal flaw—generation lengths differ wildly. In the same batch, request A may finish after 20 tokens while request B needs 500. Under Static Batching:

• Request A is done at step 20, but it must sit in the batch waiting until the slowest request B finishes all 500 steps before the whole batch releases.
• For those 480 steps after A finished, the “slot” it occupies in the batch is pure idle work—the GPU keeps computing for a position that no longer matters.

Analogy: a carpool that will not let anyone off until every passenger reaches their destination. Early arrivals should get out, but they stay locked in while the car detours; seats stay taken and people waiting outside cannot board.

The figure below plots three requests in one batch on a 500-step timeline: blue is actively generating; blue hatched cells are slots forced idle after a request finished.

⚠️ Note: under Static Batching, a lot of compute is wasted on empty slots for finished requests, and new requests must wait for the whole batch to end before they can enter. The waste ratio depends on length spread in the batch: with 8 requests, the longest runs 500 steps and the other 7 average only 50, then of $8 \times 500 = 4000$ slot-steps only $500 + 7 \times 50 = 850$ do real work—about 79% idle. Larger length gaps mean worse waste.

---

3. Continuous Batching: iteration-level scheduling

Continuous Batching (also called in-flight batching) breaks the problem by refining the scheduling granularity from “a whole batch” down to “one iteration step.”

🔑 Core idea: Iteration-level Scheduling—stop treating “the full lifetime of a batch of requests” as the scheduling unit; instead reschedule after every generation step (one token). After each step the engine immediately checks:

• Which requests emitted EOS or hit a length limit? → remove them from the batch at once and free their memory; no waiting on others.
• Did memory and batch capacity free up space? → pull new requests from the waiting queue immediately into the next step’s compute.

So the batch composition is fluid: requests join as they arrive and leave as they finish; almost every step the GPU works at full load for requests that are still generating—no idle slots spinning.

The figure below draws both schedulers on the same 4 slots. Blue is A–D that arrived together; yellow is E, F, G that arrive later; blue hatched cells are idle slots left by finished requests; white cells are free. Top: Static Batching waits until B finishes at step 10 before admitting E, F, G. Bottom: Continuous Batching fills new requests in the same step that A, C, D exit.

Back to the carpool analogy: it is now a flag-and-board, get-off-at-your-stop bus—passengers leave when they arrive, empty seats fill from the curb immediately, and the bus stays full as it rolls.

📌 Key point: Continuous Batching gains come from two places: finished requests leave immediately (no idle spin), and new requests fill immediately (no waiting for the whole batch), so queueing latency drops a lot too. The Orca paper that first systematized iteration-level scheduling reported 36.9× higher throughput than then-current FasterTransformer on GPT-3 175B at the same latency (that multiplier also folds in Orca’s other optimizations and depends on the workload).

---

4. What happens in one scheduling loop

Zoom in on what vLLM does each step. Think of a loop that never stops:

📥 Admit new requests → 🗂️ Schedule → ⚙️ One forward step → 📤 Handle outputs → 🔁 Back to the start

1. Admit new requests: put newly arrived requests into the Waiting queue.
2. Scheduling decision: the scheduler decides who rides this step. It balances two groups—Running requests still generating (Decode), and new requests from Waiting that can fit (Prefill). Whether there is room depends on how many free KV Blocks remain in GPU memory (exactly the information PagedAttention provides).
3. One forward step: run one model forward on the chosen batch; each Decode request produces 1 new token, Prefill produces the first token.
4. Handle outputs: append new tokens to each request’s KV Cache; check which hit EOS or a length limit, mark them done, and return their KV Blocks to the free pool.
5. Loop: go back to step 1.

💡 Tip: when memory is tight and Running is too full, the scheduler can also preempt: pause some requests, free their KV Blocks, and keep others moving. In vLLM V1, preempted requests always drop KV and recompute on resume; §6.3 shows the matching code.

---

5. Working with PagedAttention

Continuous Batching and PagedAttention are a pair that only work at full strength together. That pairing matters:

• Continuous Batching’s “leave and refill on the fly” needs fine-grained, anytime allocate and free of memory. With traditional large contiguous allocations, the hole a finished request leaves may not fit a new one, so dynamic refill never gets off the ground.
• PagedAttention’s fixed-size blocks + allocate on demand + free immediately is exactly that fine-grained memory elasticity: a request finishes and its blocks return to the free pool; a new request takes blocks on demand from the pool.

🔑 Core idea: PagedAttention owns “how memory is laid out”; Continuous Batching owns “how requests are scheduled”; the product is vLLM’s high throughput. Either alone is not enough—like a bus system that needs both flexible seat management and a flag-and-board schedule.

---

6. Source walk-through: the vLLM V1 Scheduler

Map the scheduling loop onto code. The vLLM V1 engine concentrates iteration-level scheduling in the Scheduler class in vllm/v1/core/sched/scheduler.py. Below follows the design skeleton on main (code keeps moving; method signatures follow your installed version).

⚠️ Note: the biggest design change from V0 to V1 is that the scheduler no longer sees a “Prefill phase” and a “Decode phase.” Source comments say explicitly “no ‘decoding phase’ nor ‘prefill phase’”: each request just keeps pushing num_computed_tokens toward num_tokens_with_spec (total target including speculative tokens). That unified view is exactly what lets Chunked Prefill in §2.4 mix Prefill and Decode in one step.

6.1 Two queues and one loop

The scheduler keeps two core pieces of state:

In the figure below, white cells are requests queued in waiting; blue cells are requests computing in running; orange arrows are transfers between the two.

• self.running: a list of requests currently computing.
• self.waiting: a priority queue of requests waiting to run. Two policies—FCFS (first come first served) and PRIORITY. v0.32.0 also has helper queues such as kv_holding_waiting, deferred_waiting, and the per-step temporary step_skipped_waiting, used to park requests that cannot be scheduled this step because a dependency is not ready (e.g. async KV transfer unfinished). You can ignore them when reading the main line.

The two most important methods map to the “schedule → forward → handle outputs” loop from §4:

• schedule(): the core of one scheduling step. It holds a token budget (token_budget), walks running first to allocate tokens and KV blocks for requests already generating, and only if budget remains and no preemption happened does it pull new requests from waiting. Finally it packs a SchedulerOutput for the model to execute.
• update_from_output(): after the model returns this step’s output, append sampled tokens to each request, check stop conditions (EOS / length limit), free finished requests’ resources, and assemble results for the client.

6.2 Decision order inside one schedule step

The order inside schedule() shows clearly why in-flight requests outrank new ones:

# Pseudocode: main line of V1 Scheduler.schedule() (not literal source)
def schedule(self):
    token_budget = self.max_num_batched_tokens
    scheduled = []
    preempted = []

    # First priority: feed requests already running (mostly Decode)
    req_index = 0
    while req_index < len(self.running) and token_budget > 0:
        req = self.running[req_index]
        num_new = compute_new_tokens(req, token_budget)   # limited by budget / max_model_len
        while True:                                       # if allocate fails, preempt and retry
            blocks = self.kv_cache_manager.allocate_slots(req, num_new)
            if blocks is not None:
                break
            victim = self.running.pop()                   # FCFS kicks the last (latest joined)
            self._preempt_request(victim)                 # free blocks, push back to waiting head
            preempted.append(victim)
            if victim is req:                             # kicked ourselves; this request skips the step
                break
        if blocks is None:
            break
        scheduled.append(req)
        token_budget -= num_new
        req_index += 1

    # Second priority: only if budget remains and this step had no preemption, admit new Prefill
    if not preempted and token_budget > 0:
        while self.waiting and token_budget > 0:
            req = self.waiting.pop_front()
            if not self._can_admit(req):                  # running cap / LoRA checks, etc.
                break
            self.running.append(req)
            scheduled.append(req)

    return SchedulerOutput(scheduled)

Two design points hide in this logic:

1. In-flight requests beat new ones: keep already-running requests moving first; leftover budget admits new work. That avoids “new requests keep cutting in, old ones never finish” starvation.
2. Preemption fires when memory is exhausted: when allocate_slots returns None (no KV blocks), the scheduler picks a “victim,” frees its blocks, and retries the allocation until it succeeds or the current request itself is kicked. Under FCFS it kicks the last entry in running (latest joined); under PRIORITY it kicks the one with the largest (priority, arrival_time)—lowest priority, and among equals the latest arrival.

6.3 What preemption does in code

A preempted request goes through cleanup in _preempt_request(): free its KV blocks and encoder cache → set state to PREEMPTED → reset num_computed_tokens to zero → push back to the head of waiting so it resumes first when resources free up.

📌 Key point: that zeroing of num_computed_tokens means V1’s resume strategy is recompute: next time the preempted request is scheduled, it Prefills the prompt and already-generated tokens from scratch instead of swapping KV back from CPU (this pairs with the two resume modes in §2.1). Official tuning docs say V1 defaults to recompute rather than swap because recompute is cheaper under the V1 architecture; with Prefix Cache on, released full blocks that have not been evicted yet can hit on resume.

💡 Tip: when reading the scheduler, hold this main line—waiting/running + token_budget + allocate_slots return value driving preemption. The abstract “scheduling loop” in §4 is just those three interacting. Deeper scheduling (how Chunked Prefill splits) is in §2.4; Chapter 3 walks the same flow again with nano-vllm’s slim Scheduler.

---

7. Key tradeoffs in scheduling

Continuous Batching is powerful, but the scheduler faces conflicting goals; engineering needs to see the tradeoffs clearly:

• Throughput vs latency: more requests in one step raise system throughput, but each forward step also takes longer, so per-request TPOT gets a bit worse. Batch size has to balance the two.
• Prefill vs Decode contention: Prefill for a new request is heavy compute-bound work. Stuffing a very long prompt Prefill into a step can clearly slow Decode TPOT for the same batch (TPOT jitter). That is exactly what the next section’s Chunked Prefill fixes—split long Prefill into chunks so it does not monopolize a whole step at once.
• Fairness vs efficiency: do early arrivals go first? Can long requests starve under short ones cutting in? Scheduling policy has to trade overall efficiency against fairness across requests.

⚠️ Note: Continuous Batching makes latency metrics load-sensitive. At low load batches are small and latency is low; at high load batches grow, queues lengthen, and P95/P99 tail latency rises clearly. For capacity planning, always load-test latency at target concurrency, not on idle numbers.

---

📝 Summary

• Batching’s essence is amortizing weight-move cost, putting memory-bound Decode’s compute to work, raising throughput with almost no latency cost.
• Static Batching’s fatal flaw is “mutual drag inside the batch”: short requests wait out the longest one; larger length gaps mean more idle slot-steps.
• Continuous Batching refines scheduling to the iteration step (Iteration-level Scheduling): leave on finish, fill on arrival; idle slots mostly disappear.
• It works deeply with PagedAttention: the latter gives fine-grained reclaimable memory so the former can keep a dynamic batch.
• In source, V1’s Scheduler drives scheduling with waiting/running + token_budget, preferring in-flight requests and preempting when memory runs out, and no longer splits Prefill/Decode phases.
• Scheduling trades off throughput/latency, Prefill/Decode contention, fairness/efficiency; Prefill interfering with Decode is further eased by Chunked Prefill.

🎯 Self-check list

• Explain from a memory-bound view why batching raises throughput
• State the concrete mechanism by which short requests get dragged by long ones under Static Batching
• Explain the essential difference between Iteration-level Scheduling and batch-level scheduling
• Describe the “exit finished requests, admit new ones” flow in one vLLM scheduling step
• Explain why Continuous Batching depends on PagedAttention’s fine-grained memory management
• State the waiting/running queues in the V1 Scheduler and the decision order in schedule()
• Explain why the V1 scheduler “does not distinguish Prefill/Decode phases,” and why default preemption uses recompute
• Analyze how batch size pushes throughput and TPOT in opposite directions
• Explain why a long-prompt Prefill interferes with Decode in the same batch, and which technique eases it

📚 References

• vLLM official blog: Easy, Fast, and Cheap LLM Serving with PagedAttention
• Orca: A Distributed Serving System for Transformer-Based Generative Models (iteration-level scheduling)
• vLLM V1 Alpha Release (unified scheduler design)
• vLLM V1 source — vllm/v1/core/sched/scheduler.py (Scheduler implementation)
• vLLM — Optimization and Tuning (preemption and recompute)