Continuous Batching & Scheduling

FlashAttention reduces memory traffic inside one attention kernel. The next serving question sits one layer higher: how does an inference server decide which requests share each forward pass?

Continuous batching is an inference scheduler problem: keep the GPU busy while requests arrive with different prompt lengths, output lengths, and deadlines. Production LLM servers batch work without waiting for every request to finish at the same time.

A shared code-assistant endpoint during a release freeze receives mixed work. Some developers ask for a one-line completion. Others paste a failing test log and ask for a migration plan. Hundreds of mixed-length requests hit the same serving pool 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 developer asks for a ten-paragraph migration plan, completed short answers leave idle batch slots until the long generation ends.

Continuous batching^{[1]Reference 1Orca: A Distributed Serving System for Transformer-Based Generative Models.https://www.usenix.org/conference/osdi22/presentation/yu[2]Reference 2Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} 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 one-line completion might need only ten decode steps. A long migration explanation 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 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

Static batching treats the batch as one unit of work. Once those two LLM facts are in play, varying prompt and output lengths make that design expensive.

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. That leaves 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 freezes the active request set until the longest response finishes. Even if two short completions finished hundreds of decode steps ago, their slots stay blocked until the slowest request ends. Continuous batching rebuilds the active set at decode boundaries: as soon as one sequence stops, the next queued sequence can take that slot. The GPU keeps more useful token work in flight.

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 code-assistant requests

Make the waste concrete with numbers. Suppose the GPU can run three requests at once, and three code-assistant requests arrive:

Static batching runs all three together. Request A finishes after 10 iterations, Request B after 50, and Request 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, Request A finishes and a new request (Request D) joins immediately. At iteration 50, Request B finishes and Request 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 trace, continuous batching fills slots that static batching would leave idle, so the server can finish substantially more useful completions 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:

Slot utilization isn't GPU utilization. The 43.3% figure is batch-slot occupancy: how often a request-shaped seat is busy under static batching. Filling every slot still leaves tensor cores idle on memory-bandwidth-bound decode, and HBM can be nearly full while model FLOPs utilization (MFU) stays low. Rough ladder:

Continuous batching is a GPU capacity win because it keeps more useful work in flight. It doesn't promise that SM occupancy or MFU jump to 100%.

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 are harder to store efficiently in contiguous tensors. PagedAttention (block-based memory management) is 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 are harder to store 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 Qwen3.6-27B's published Gated Attention geometry (16 full-attention layers, 4 KV heads, head dimension 256, FP16 cache), each new token adds about 64 KiB of KV state.^{[3]Reference 3Qwen3.6-27Bhttps://huggingface.co/Qwen/Qwen3.6-27B} A 4,096-token sequence therefore needs roughly 0.25 GiB of cache. If those same 16 layers stored separate K/V tensors for all 24 query heads instead of GQA, the cache would grow to roughly 1.5 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:

Which term makes KV-cache memory grow during decoding?

Answer

$s$, the sequence length. Every new generated token extends the stored key and value tensors, so cache memory grows linearly with active sequence length.

PagedAttention Solution

PagedAttention^{[2]Reference 2Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} 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 near-zero KV-cache waste in its evaluated allocation design, in contrast with substantially higher reservation waste in its baseline systems.^{[2]Reference 2Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} 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 (ITL), also called time between tokens (TBT). TPOT is closely related but isn't identical: papers such as DistServe define Time Per Output Token (TPOT) as the average time per output token after the first.^{[4]Reference 4DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

This 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. Chunked prefill 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, then co-schedule bounded chunks with decode work.
2. Disaggregated prefill: Separate prefill and decode onto different GPU pools.^{[4]Reference 4DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}
3. Priority scheduling: Prioritize decode steps to minimize latency.

---

Scheduling policies

The scheduler rebuilds the active set every iteration. Policy decides which waiting work gets scarce decode slots next.

First-Come-First-Served (FCFS)

FCFS admits requests in arrival order. That is easy to reason about and usually fair, but a long migration plan at the front can block many shorter completions behind it.

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 single-line completion) don't get stuck behind a long design 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 ITL 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.^{[4]Reference 4DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

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 recovery designs are:

1. Recomputation: Drop the victim request's KV cache and re-run its prompt tokens 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).
2. Swap Out (CPU Offload): Move the victim request's KV cache from GPU VRAM to CPU RAM.
   • Pros: Saves progress; can be cheaper than recomputation when discarded state would be expensive to rebuild.
   • Cons: Consumes host-device bandwidth and adds resume latency.

These are design options, not universal defaults. Current vLLM V1 uses RECOMPUTE as its default preemption mode because recomputation has lower overhead in that architecture.^{[5]Reference 5Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html} The cheaper choice in another runtime still depends on prompt length, host-device bandwidth, and how expensive replaying prefill would be. If you tune a particular engine, check its current scheduler documentation and trace preemption events rather than assuming one policy is active.

This simplified Python simulation of a continuous batch scheduler demonstrates the core iteration loop, including consistent KV-block accounting as requests grow token by token and one swap-out preemption path when the next step can't fit. This swap-out-only teaching model differs from current vLLM V1 preemption, which defaults to recompute. 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.

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. The tight-budget assertion proves that this example's swap-out preemption branch runs rather than merely existing in the code.

A recompute path is the dual policy (and the one many engines default to). Pseudocode for the victim branch:

Swap-out pays host-device bandwidth to keep KV. Recompute pays prefill FLOPs to rebuild it. Choose from measured prompt length, PCIe bandwidth, and preemption frequency.

Continuous batching × speculative decoding

Speculative decoding is more than a per-request speedup; it changes the token-budget math for the whole continuous batch:

1. Budget inflation. After verify, each active request may emit up to k + 1 tokens (draft span plus possible bonus). The scheduler must reserve max_num_batched_tokens as if those multi-token steps can land together, not as one token per request.
2. ITL jitter from acceptance variance. High acceptance packs more useful tokens per step; rejects free partial work unevenly and can stall one stream while neighbors stream smoothly, even when mean TPOT looks fine.
3. Mixed streams. Speculative and non-speculative requests share one token budget. A burst of long draft verifies can starve plain decode seats the same way a fat prefill can.

The accept/reject rule lives in speculative decoding. Keep the continuous-batch loop and token budget from this lesson when you read it.

Why does continuous batching usually schedule by token or KV-cache budget instead of only request count?

Answer

Requests have different prompt lengths and generated lengths. One long prompt can consume far more prefill work and KV-cache memory than many short chats, so request count alone misstates GPU capacity.

---

Serving Engines and System Designs

These ideas 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 offered request rate, $\lambda$, that keeps the required fraction, $\alpha$, of requests within both TTFT and TPOT objectives.^{[4]Reference 4DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670} A compact definition is:

$$\text{Goodput} = \max\left\{\lambda : P(\text{TTFT} \le T_{\text{TTFT}} \text{ and } \text{TPOT} \le T_{\text{TPOT}}) \ge \alpha\right\}$$

Here, $T_{\text{TTFT}}$ and $T_{\text{TPOT}}$ are the latency limits, while $\alpha$ is the required attainment fraction, such as 90%. To measure goodput, increase offered load and select the highest request rate whose attainment remains at or above $\alpha$. In interview settings, this is the right framing: optimize tokens/sec only after you define the TTFT, TPOT, and attainment targets that matter for users.

A single observation window doesn't establish that maximum. It can still report observed SLO-compliant throughput, which is useful when diagnosing why raw throughput alone hides latency failures:

Why doesn't this 10-second window establish goodput?

Answer

It measures compliant completions at one offered load. Establishing goodput requires sweeping offered request rates and finding the maximum rate that still meets the chosen SLO-attainment target.

---

Advanced scheduling: chunked prefill

One remaining bottleneck in naive continuous batching is prefill/decode interference. Sarathi-Serve^{[8]Reference 8Sarathi-Serve: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills.https://arxiv.org/abs/2308.16369} addresses this with chunked-prefills plus decode-maximal batching. 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-Serve 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:

Chunking protects decode cadence

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. It can pair an admitted chunk with decode work that fits the same token budget, then reconsider the active mix before the next chunk. 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.^{[5]Reference 5Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html}

The same budget tradeoff becomes easier to inspect as a small schedule:

---

Disaggregated serving

A more advanced approach, disaggregated serving, splits prefill and decode across separate worker pools. Splitwise^{[9]Reference 9Splitwise: Efficient Generative LLM Inference Using Phase Splitting.https://arxiv.org/abs/2311.18677} and DistServe^{[4]Reference 4DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670} 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

Splitting these two phases creates a specialized pipeline where requests move to the hardware pool that fits their current state. The diagram traces that 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.^{[4]Reference 4DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

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.

---

Scheduling rules to keep

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. Don't optimize only for tokens/sec. Optimize for goodput, TTFT, TPOT, and ITL 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.

---

Run a scheduling stress trace

Run one mixed workload with short and long prompts, record queue wait, TTFT, ITL, token-budget use, KV-block pressure, and preemptions, then compare the trace with your declared scheduler policy. Keep the table as the acceptance artifact for the next policy change.