Continuous Batching & Scheduling

The previous chapter showed how FlashAttention reduces memory traffic inside one attention kernel. This chapter moves up one layer: how does an inference server decide which requests share each forward pass?

Continuous batching is a serving scheduler problem: keep the GPU busy while requests arrive with different prompt lengths, output lengths, and deadlines. This chapter shows how production LLM servers batch work without waiting for every request to finish at the same time.

Imagine an order-support chatbot on a busy shopping holiday. Some customers ask for a quick refund status (two sentences). Others paste their entire order history and ask for a detailed analysis (ten paragraphs). Hundreds of these requests hit the server at once.

A simple request-level baseline handles this with static batching. It fills a batch of requests, runs them together, and waits for the longest one to finish before starting the next batch. If one customer asks for a ten-paragraph analysis, completed short answers leave idle batch slots until the long generation ends.

Continuous batching^[1][2] fixes this waste by letting the server reuse a slot at the next token-generation step (the next iteration) after a request finishes. Under sustained mixed-length workloads, that can increase useful GPU work per step without changing the model itself. It pairs naturally with flexible Key-Value (KV) cache management, because admission still depends on available cache memory.

---

Why Batching Is Tricky for LLMs

To understand why static batching is so wasteful, recall two facts about how LLMs generate text.

First, LLMs are autoregressive: they produce text one token at a time. Processing the input prompt (the prefill phase) can be done in parallel, but generating each new token (the decode phase) happens sequentially. A short refund question might need only ten decode steps. A long order analysis might need two hundred.

Second, the output token count usually isn't known ahead of time. The engine stops when it hits a stop token or a length limit. That means the scheduler can't know in advance when a request will finish.

These two facts make LLM serving fundamentally different from image-classification serving, where every request has the same fixed shape and finishes in a single forward pass.

The Problem with Static Batching

In fixed-shape model serving, batching is simpler because requests may complete in one forward pass. In LLM serving, requests have varying prompt and output lengths. Because output token count usually isn't known until generation stops (either at a stop token or a length limit), the engine can't know in advance when a request will finish.

With static batching, all requests in a batch must wait for the longest request to complete before the next batch can start. This synchronous execution model forces the engine to maintain the batch shape until each sequence is fully generated. The result is large idle capacity and, in pipelined deployments, pipeline bubbles:

Most slots become idle as soon as their request finishes, so utilization can collapse in heterogeneous workloads. Requests 1 and 3 are done early, but their GPU memory stays reserved until Request 2 completes. No new requests can join because the batch shape is fixed. Throughput falls even though the hardware still has work it could be doing.

---

Continuous Batching (Iteration-Level Scheduling)

Continuous batching (also known as iteration-level scheduling) moves scheduling to the decode-step boundary. After each generation step (or after each prefill chunk in engines that chunk prefills), the server checks which requests finished, frees their slots, and admits new work if memory and token-budget constraints allow.

Static batching is like a delivery truck that waits until every warehouse order is packed before leaving the dock. Even if the first parcel was ready ten minutes ago, that slot stays blocked until the slowest parcel is ready. Continuous batching is like a cross-dock lane with fixed loading slots: as soon as one parcel leaves the belt, the next queued parcel takes its place. The lane stays full, maximizing useful work per step.

Completed requests leave immediately, and queued requests can join on the next iteration. The scheduler effectively rebuilds the active running set for the next forward pass.

A Worked Example: Three Support Tickets

Make the waste concrete with numbers. Suppose the GPU can run three requests at once, and three support tickets arrive:

Static batching runs all three together. Ticket A finishes after 10 iterations, Ticket B after 50, and Ticket C after 200. For iterations 11 through 200, the slots for A and B sit idle. Total GPU iterations for this batch: 200. Wasted slot-iterations: 190 for A's slot plus 150 for B's slot = 340 idle slots.

Continuous batching starts with [A, B, C]. At iteration 10, Ticket A finishes and a new ticket (Ticket D) joins immediately. At iteration 50, Ticket B finishes and Ticket E joins. The GPU keeps all three slots busy until the queue empties. The only idle iterations happen when the waiting queue is empty.

In this tiny example, continuous batching fills slots that static batching would leave idle, so the server can answer substantially more customer questions per GPU hour without a hardware upgrade.

Under sustained load, slot reuse avoids idle work from completed short requests. Actual utilization still depends on token budgets, memory pressure, phase mix, and kernel efficiency.

This first calculation isolates slot reuse from GPU details. It treats each active output token as one useful slot-iteration:

One subtle but important detail: modern schedulers are usually limited by a token budget or KV-cache budget, rather than a raw "number of requests" cap. One long prefill can consume more scheduler budget than many short decode-only requests.

Continuous batching pairs naturally with a flexible memory manager. Because requests come and go, their Key-Value (KV) caches cannot be stored efficiently in contiguous tensors. This is why PagedAttention (block-based memory management) is such a practical companion to continuous batching.

---

Memory Management: The Hidden Enabler

To understand why continuous batching was difficult to implement initially, we need to look at memory management. Recall that during the decode phase, the model stores a Key-Value (KV) cache: a running record of attention states for every token generated so far. Because requests leave and join the batch at unpredictable times, their KV caches can't be stored efficiently in contiguous tensors.

The Fragmentation Problem

In standard Transformer implementations, the KV cache for a request is often treated like a growing contiguous buffer sized for a maximum sequence length.

When requests have different lengths and arrive at different times:

1. Internal Fragmentation: You have to pre-allocate memory for max_seq_len (e.g., 4096 tokens) even if the request generates 50 tokens.
2. External Fragmentation: As requests finish and leave, they create variable-sized "holes" in GPU memory that new requests might not fit into cleanly.

The KV cache for a single sequence grows with every decode step. For a 70B-class model with GQA (80 layers, 8 KV heads, head dimension 128, FP16), each new token adds about 320 KiB of KV state. A 4,096-token sequence therefore needs roughly 1.25 GiB of cache. If the same model stored a full KV head set instead of GQA, the cache would balloon to roughly 10 GiB at 4K tokens. That's why fragmentation hurts so much: even modest over-allocation can strand gigabytes of VRAM that could have admitted other requests.

A useful size estimate follows this formula:

$$M_{KV} = 2 \times L \times s \times H_{kv} \times d \times b$$

Where $L$ is the number of layers, $s$ is the sequence length, $H_{kv}$ is the number of KV heads, $d$ is the head dimension, and $b$ is bytes per element (2 for FP16). The leading 2 accounts for both key and value tensors.

Use the formula directly before choosing a concurrency target:

PagedAttention Solution

PagedAttention^[2] solves this by borrowing the concept of virtual memory from operating systems, as illustrated below.

1. KV Blocks: The KV cache is divided into fixed-size blocks (e.g., 16 or 32 tokens).
2. Non-Contiguous Allocation: Blocks can be stored anywhere in GPU memory (VRAM). They don't need to be contiguous.
3. Block Table: Each request keeps a mapping table from logical page to physical block that tells the runtime where its KV blocks live.

This allows the scheduler to allocate memory dynamically as tokens are generated. The vLLM paper reports less than 4% waste in its evaluated allocation design, in contrast with substantially higher reservation waste in its baseline systems.^[2] Fixed blocks make dynamic admission practical without requiring large contiguous allocations.

This toy allocation computes the last-block slack for a few active sequences:

PagedAttention is a memory management technique for non-contiguous KV blocks. FlashAttention is a compute optimization that tiles attention to reduce High Bandwidth Memory (HBM) I/O. They are orthogonal techniques, but systems such as vLLM often combine them to improve both memory capacity and compute speed.

---

Prefill vs. Decode Phases

LLM serving has two distinct computational phases with opposing characteristics:

Prefill (Prompt Processing)

• Processes all input tokens in parallel (like training).
• Often compute-heavy because it processes many prompt tokens in matrix multiplications.
• Runs once per request at the start.
• Latency goal: Minimize Time To First Token (TTFT).

Decode (Token Generation)

• Generates tokens one at a time (autoregressive).
• Often memory-bandwidth limited at practical batch sizes because each step processes few new tokens while reading model and KV state.
• Runs many times per request (once per output token).
• Latency goal: Minimize inter-token latency. Many dashboards report this as TBT or TPOT, while papers such as DistServe define TPOT as the average time per output token after the first.^[3]

The following table summarizes the key differences between the prefill and decode phases:

The Interference Problem

Blindly mixing a full long prefill with decode work can harm inter-token latency. A large prefill request (for example, processing a 4K-token document) can delay decode steps for concurrent streams. Later in the article we'll look at chunked prefill, which bounds how much prefill work competes in one scheduling step.

Token-budget scheduling makes that bound visible:

Solutions include:

1. Chunked prefill: Break long prefills into chunks, interleave with decode steps.
2. Disaggregated prefill: Separate prefill and decode onto different GPU pools.^[3]
3. Priority scheduling: Prioritize decode steps to minimize latency.

---

Scheduling Policies

The scheduler's job is to decide which requests to run in the next iteration.

The scheduler is like a warehouse dispatch desk. First-Come-First-Served (FCFS) loads orders in arrival order, which is fair, but a one-item replacement waits behind a huge wholesale pallet. Shortest-Job-First (SJF) prioritizes quick orders first, which improves average wait time. Preemption is like pausing a low-priority batch to ship an urgent replacement, then resuming later. Each scheduling policy is a tradeoff between fairness, throughput, and latency.

First-Come-First-Served (FCFS)

It's the most straightforward approach and simple to reason about. Requests are admitted in arrival order, which is usually fair, but it isn't optimal for overall system throughput. A long-running request at the front of the queue can block many shorter requests behind it, increasing the average latency across the system.

Shortest-Job-First (SJF)

The scheduler prioritizes requests that are expected to require fewer output tokens. In theory, this can improve average latency because short responses (like a simple "Yes" or "No") don't get stuck behind a long refund-policy explanation. In practice, output length is unknown ahead of time, so pure SJF is rare in LLM serving. Real systems approximate it with heuristics such as prompt-length bucketing, tenant priorities, or token-budget limits.

This queue calculation shows the benefit SJF would have if output lengths were known. Production engines need estimates, priorities, or fairness controls because they don't know these lengths in advance:

Priority and Decode-First Scheduling

Many production schedulers care more about keeping existing streams smooth than about starting every new request immediately. A user notices TPOT jitter right away, while a modest TTFT increase on a newly arrived long prompt is often less damaging. That leads to policies such as decode-first scheduling, per-tenant priorities, and SLO-aware admission control.^[3]

Preemption Strategies

When GPU memory is full (KV cache blocks are exhausted), the scheduler must either pause work, evict state, or stop admitting new requests. Two common recovery strategies are:

1. Swap Out (CPU Offload): Move the victim request's KV cache from GPU VRAM to CPU RAM.
   • Pros: Saves progress; cheap to resume if PCIe bandwidth is available.
   • Cons: High latency penalty for the swapped-out request.
2. Recomputation: Drop the KV cache entirely and re-run the prefill phase when the request is rescheduled.
   • Pros: Zero memory overhead on CPU; simple to implement.
   • Cons: Wastes GPU compute; works best when the prompt is short (low prefill cost).

These are design options, not universal defaults. The cheaper choice depends on prompt length, host-device bandwidth, and how expensive replaying prefill would be. Recomputation can be better when prompts are short enough that rebuilding state costs less than moving KV blocks off the GPU. Swapping matters when discarded state would be expensive to rebuild. If you tune a particular engine, check its current scheduler documentation and trace preemption events rather than assuming one policy is active.

Here is a simplified Python simulation of a continuous batch scheduler. It demonstrates the core iteration loop, including consistent KV-block accounting as requests grow token by token and a swap-out decision when the next step can't fit. The schedule_step method is called before every forward pass, and finish_decode_step is called after that pass emits one token for each active request.

The key observation is that schedule_step() rebuilds the active set at every iteration, scanning the running requests and admitting queued work under the batch and KV-cache budgets.

In a real server, the control loop alternates between schedule_step() and finish_decode_step(): schedule the next forward pass, run it once, record the extra token and any newly needed KV block, then repeat. Real schedulers add more machinery on top of this loop, such as prefix-cache reuse, cancellation handling, speculative decoding, and token-budget accounting. A recomputation-based preemption path would drop the victim's KV cache and put it back into waiting instead of parking it in swapped. The tight-budget assertion proves that this example's preemption branch runs rather than merely existing in the code.

---

Serving Engines and System Designs

The ideas in this article show up across most modern inference stacks, but some entries below are production engines while others are research systems that shaped later engine design:

Other servers implement many of the same ideas too. Feature matrices change quickly, so treat engine comparisons as moving targets and verify the current docs before making a production choice.

---

Throughput vs. Goodput

Benchmark numbers in this space are highly workload-dependent. The meaningful comparison isn't "Which server is fastest?" but "Which system stays within TTFT and TPOT targets for my traffic mix?"

The literature still gives useful anchor points:

Goodput: The Production Metric

Raw throughput can be misleading if a large fraction of requests miss their latency target. DistServe frames goodput as the maximum request rate that can be served while still meeting TTFT and TPOT objectives at a chosen SLO-attainment target.^[3] A simple mental model is:

$$\text{Goodput} = \frac{\text{requests processed within SLA}}{\text{total time}}$$

Unlike raw throughput (which counts all completed requests), goodput only counts requests that satisfy the latency target. In interview settings, this is the right framing: optimize tokens/sec only after you define the TTFT, TPOT, and end-to-end latency targets that matter for users.

Calculate goodput from an explicit latency objective rather than reporting only completions:

---

Advanced Scheduling: Chunked Prefill

One remaining bottleneck in naive continuous batching is prefill/decode interference. Sarathi-Serve addresses this with chunked-prefills plus decode-maximal batching.^[6] A single long prefill can delay other requests waiting for a decode step, producing visible gaps in token output when the phase mix is poorly scheduled.

Mechanism

Chunked prefill splits a long prefill phase into smaller blocks (for example, 512-token or 1,024-token chunks). Sarathi then uses decode-maximal batching to pair one prefill chunk with as many decode requests as possible, so the chunk keeps the GPU compute units busy while the decodes "piggyback" on the same batch. This flow shows how chunking prevents latency spikes:

Why This Matters

Without chunked prefill, a long prefill can occupy a long scheduling interval. During this window, concurrent decode requests wait for their next token. Users can see irregular token output even if average TBT looks acceptable.

With chunked prefill, the same 4,000-token document can be split into smaller pieces. With a 512-token chunk size, for example, the scheduler processes about 8 chunks and gains scheduling boundaries at which decode work can run. The long prompt may pay overhead from additional scheduling and kernel boundaries, but one admitted prefill chunk no longer consumes the entire prompt in one step.

Current vLLM V1 documentation describes chunked prefill as enabled by default: the scheduler prioritizes decode requests and uses the remaining max_num_batched_tokens budget for prefills, chunking a prefill that doesn't fit. Its tuning guidance notes the tradeoff: larger token budgets tend to improve TTFT and throughput, while smaller budgets can improve inter-token latency.^[7]

Here is the same budget tradeoff as a small schedule:

---

Disaggregated Serving

A more advanced approach, disaggregated serving, splits prefill and decode across separate worker pools. Splitwise^[8] and DistServe^[3] study this design explicitly. The motivation is simple: prefill often wants dense matrix-math throughput, while decode often wants KV-cache capacity and memory bandwidth.

Disaggregation isn't the right default for every deployment. For short prompts, small clusters, or workloads with high prefix-cache hit rates, running prefill on the decode worker can be simpler than paying a KV-transfer hop. The right comparison is goodput under a defined TTFT and TPOT objective, including transfer overhead.

Architecture

By decoupling these two phases, we can construct a specialized pipeline where requests are routed to the most appropriate hardware pool for their current state. The following diagram illustrates this disaggregated architecture:

Benefits

• Prefill workers: Can be sized and tuned for high matrix-math throughput.

• Decode workers: Can be sized for KV-cache capacity and memory bandwidth without worrying about prefill interference.

• Scaling: You can scale prefill and decode pools independently based on whether your traffic skews toward long prompts or long generations.

Cost

The KV cache (or equivalent prefill state) must be transferred between pools. Whether that transfer is worth it depends on prompt length, interconnect speed, and your TTFT/TPOT SLOs. DistServe is a good reminder that once you optimize for goodput instead of raw TPS, paying that transfer cost can still be the right tradeoff.^[3]

Estimate the handoff bytes before assuming split pools improve latency:

---

Common Mistakes in Production

Even experienced engineers trip over a few predictable traps when tuning a continuous batching setup.

Static Batching Mindset

Symptom: You design the scheduler as if all requests in a batch must start and finish together.

Cause: Traditional model-serving systems often batch fixed-shape requests, so the batch is treated as one request-level unit of work.

Fix: Treat decoding as an iteration-level loop. Finished requests leave at the next boundary, cancellations free their KV blocks, and waiting requests enter when batch and token budgets allow.

The OOM Oversimplification

Symptom: You increase max_batch_size and the server crashes with an out-of-memory error mid-generation.

Cause: You treated memory as a fixed cost per request, ignoring that the KV cache grows with every output token. A batch of ten short prompts fits easily, but if those prompts turn into long generations, the cache doubles or triples in size.

Fix: Tune by KV cache blocks or token budget, not by raw request count. Monitor peak memory during the longest generations in your workload, and leave headroom for bursts.

Ignoring Time to First Token (TTFT)

Symptom: Throughput benchmarks look great, but users complain that new requests take forever to start responding.

Cause: The scheduler is so focused on keeping the decode batch full that it delays admitting new prefills. A long queue of decode work starves the waiting queue.

Fix: Set a maximum decode-only iteration budget or a waiting-timeout. If a request sits in the queue longer than your TTFT target, preempt a low-priority decode stream and admit the new prefill. The right balance depends on your product: a chat app needs low TTFT, while a background summarization pipeline can tolerate a longer wait.

---

Try It Yourself: The Manual Scheduler

Here's a concrete exercise to test whether the concept has stuck.

Scenario: You have a GPU batch size of 3. Five support tickets arrive:

Task: Walk through the first 50 iterations by hand.

1. Which three tickets start in the initial batch?
2. At which iteration does the first ticket finish?
3. Which ticket replaces it?
4. How many total decode iterations would static batching require if the initial batch were [T1, T2, T3]?
5. How many iterations does continuous batching save?

Answer sketch: T3 finishes first, at iteration 15, making room for T4. T1 finishes at iteration 20, making room for T5. T2 finishes at iteration 40. T5, which started at iteration 20, finishes at iteration 30. T4, which started at iteration 15, finishes at iteration 45. Static batching needs 40 iterations for the first batch and 30 for the second, totaling 70. Continuous batching finishes all five tickets in 45 iterations, saving 25 iterations (roughly 35% faster).

Check the hand calculation with a three-slot event simulation:

---

Key takeaways

1. Static batching wastes capacity when request lengths differ. Finished requests leave idle holes until the slowest request completes.

2. Continuous batching is common in high-throughput LLM serving. It schedules at the iteration level, adding and removing requests dynamically.

3. Memory management and scheduling are inseparable. Dynamic admission only works well if KV-cache allocation is flexible.

4. Prefill/decode interference is often the next bottleneck. Chunked prefill and disaggregation both exist to keep decode latency smooth.

5. Metrics matter. Don't optimize only for tokens/sec. Optimize for Goodput, TTFT, and TPOT under your actual workload.

The evolution of LLM serving is a move toward finer-grained control: batch-level static scheduling, then iteration-level continuous scheduling, then chunked prefill to reduce interference, then phase-level disaggregation when prefill and decode need different hardware pools.

---

What you should be able to defend

After working through this chapter, you should be able to:

1. Explain static-batch waste. Show why heterogeneous output lengths create idle slots and, in pipelined deployments, pipeline bubbles.
2. Describe iteration-level scheduling. Walk through finished-request removal, queued-request admission, and active-set rebuilding at decode boundaries.
3. Analyze prefill/decode interference. Explain why compute-heavy prefills can stall memory-bound decode streams.
4. Connect scheduling to memory. Explain why PagedAttention and fixed-size KV blocks make continuous admission practical.
5. Compare policies. Discuss FCFS, priority scheduling, decode-first scheduling, swapping, and recomputation.
6. Use goodput correctly. Define goodput as request throughput under TTFT and TPOT/SLA targets, not raw tokens per second.

Production questions

How does Sarathi-Serve reduce prefill-decode interference?

Sarathi-Serve splits long prefills into smaller chunks, then builds decode-maximal batches around those chunks. One prefill chunk can run with as many decode requests as possible, so a single long prompt does not block every active stream for a large uninterrupted prefill window. The result is smoother TBT/TPOT and lower tail latency for concurrent users.^[6]

What is the optimal batch size for a given GPU?

There is no universal batch size. The practical limit depends on weight memory, KV-cache growth, prompt length distribution, output length distribution, and scheduler token budget. Profile on target hardware and choose the largest request or token budget that improves throughput without missing TTFT, TPOT, or end-to-end latency SLOs.

How should cancellations work mid-generation?

A canceled request should leave the running set at the next scheduler boundary. Its KV-cache pages should be returned to the memory pool immediately, so the scheduler can admit other work instead of carrying a dead sequence until the original batch would have finished.

How does disaggregated inference separate prefill and decode?

Disaggregated inference routes prompt processing to a prefill pool and token generation to a decode pool. After prefill finishes, the KV state moves to a decode worker. That lets prefill workers optimize for dense matrix math and decode workers optimize for KV-cache capacity and memory bandwidth, at the cost of an extra state-transfer hop.^[3]

Why is PagedAttention closely tied to continuous batching?

Continuous batching works much better when KV caches are allocated in fixed-size blocks instead of large contiguous tensors. Requests start, grow, finish, and cancel at unpredictable times. PagedAttention maps logical token blocks to non-contiguous physical blocks, so the scheduler can admit new work without needing large contiguous VRAM regions.^[2]

Course handoff

You now understand why LLM serving is fundamentally an iteration-level scheduling problem, not a request-level one. You can explain the difference between static and continuous batching, calculate the throughput gain from slot reuse, and identify why flexible memory management and careful prefill/decode scheduling are needed to keep latency smooth.

The next article, Scaling LLM Inference, builds directly on this foundation. It explains why decode is memory-bandwidth bound, how KV cache design and PagedAttention shape the batch size limit, and how speculative decoding adds another layer of throughput optimization. You'll need the mental model of the iteration loop and the token budget you built here to understand why speculative decoding does more than speed up individual requests; it changes the math for the whole batch.