DL S070 · Continuous Batching — The Idea That Made LLM Serving Cheap

Series: Deep Learning & LLMs From Scratch — 80 sessions · Session 70 / 80 · Module M11 · ~2 hours

The story

Serving LLMs used to be embarrassing. In 2022, a well-tuned Triton server running GPT-J-6B on an A100 got maybe 100 tokens/sec of aggregate throughput. The GPU was 5% utilized. Everyone knew batching helped, but batching in the old (BERT-era) sense — pad all requests to the longest length, run them together — was a disaster for generative models because different requests generate different numbers of tokens.

Then Orca (OSDI 2022) shipped iteration-level scheduling, later called continuous batching. vLLM took it mainstream in 2023. Suddenly the same A100 was doing 3000+ tokens/sec aggregate. 30× throughput improvement, same hardware. No fancy quantization, no distillation, just a better scheduling algorithm.

Today: what static/dynamic batching are and why they suck for LLMs, how continuous batching solves it, the interaction with the KV cache (S066), and Little's Law — the single most useful equation for capacity planning that no one teaches you.

An analogy: the airport security line

Static batching is a TSA agent who insists on processing exactly 8 passengers at a time. If passenger 3 needs an extra bag search (500-token completion), everyone else stands there watching, even though 7 of them are ready to move on. When they finally all clear, the agent takes the next 8. In between batches, the metal detector sits idle.

Continuous batching is the airport you actually want. As soon as any passenger clears the checkpoint, the next one in the queue steps in. The agent is always processing exactly 8 people; the specific 8 change every second. Nobody waits for anyone else's baggage search. Throughput is bounded by the checkpoint's actual capacity, not by the slowest passenger.

On a GPU, the "checkpoint" is a single forward pass. Each pass produces one new token for every request currently in the batch. Between passes, the scheduler swaps requests in and out. It's boring, mechanical, and it was the single biggest inference speedup of 2023.

Prerequisites

• Session 066 — batch size is limited by KV cache; this session builds on that.
• Session 069 — its interaction with batching is subtle.

1 · Why static batching fails

Old-school (BERT-era) batching: collect $B$ requests, pad them to the max length, run one forward pass, return results. Works great when all requests have similar lengths and produce fixed outputs (e.g., classification).

LLM generation breaks the assumptions. Requests arrive at different times, prompts have wildly different lengths, and — critically — completion lengths are unknown up front and can differ by 100×. If request A completes in 20 tokens and request B needs 500, static batching pins B behind an idle slot for A once A finishes but the batch pass hasn't. The GPU is busy but 15 of 16 slots are computing padding.

Timeline sketch:

Dynamic batching (Triton-era): admit requests up to a batch-window deadline, then run. Same problem once started.

2 · Continuous batching (iteration-level scheduling)

Orca's insight: decouple the batch from the request. Every decode iteration, the scheduler decides which requests to include. When a request finishes, it drops out and a new request slots in — mid-batch, no waiting for the whole batch to finish.

The GPU is always running a full-width forward pass, mixing decode steps for old requests with prefill for new ones. Utilization approaches 100%.

The magic ingredient: the forward pass doesn't care whether tokens are "old decode" or "new prefill" or which request they belong to. It just processes a big batched tensor. As long as attention masks correctly isolate each request's context, you can mix any set of live requests every iteration.

Selective batching

Two operations behave differently across positions in the batch:

• Attention — request-local; the queries in request A shouldn't see request B's keys. Handled with a block-diagonal mask, or with FlashAttention's varlen (variable-length) support, which packs sequences end-to-end and marks boundaries via cu_seqlens arrays.
• Everything else (LayerNorm, feed-forward, LM head, embeddings) — position-independent. Just concat all tokens and run once.

Orca calls this selective batching: batch what you can, isolate what you must.

3 · Interaction with the KV cache

Each active request holds a KV cache proportional to its context length (S066). Continuous batching lets you juggle 100+ concurrent requests — but each new one costs KV memory. The scheduler must know:

• Current KV memory budget.
• Per-request KV footprint (grows as they decode).
• Whether admitting request $E$ will OOM.

Without smart memory management, you're stuck preallocating max_seq per slot (huge waste). PagedAttention (S071) solves this by chunking KV into fixed-size pages that can be freed and reallocated as requests come and go. Continuous batching and PagedAttention are two halves of the same design.

4 · Little's Law — the capacity-planning equation

Every queueing-theory course teaches this and every ML engineer eventually rediscovers it:

$L = \lambda \cdot W$

• $L$ = average number of requests in the system (concurrency).
• $\lambda$ = arrival rate (requests/sec).
• $W$ = average time each request spends in the system (latency, sec).

For LLM decode specifically, phrased in tokens: $\text{throughput (tok/s)} = \text{concurrency} \times \text{per-request tokens/sec}$

Example. You want 500 requests/min = 8.3 req/s. Each request generates on average 300 tokens at 40 tok/s per stream → $W = 7.5$ s. Concurrency needed: $L = 8.3 \times 7.5 \approx 63$. You need a serving stack that comfortably runs batch-size 63 for your model on your GPU. From S066 you already know how much KV memory that is; from that you know how many GPUs you need.

5 · Prefill vs decode scheduling

The scheduler faces an ongoing tension. Prefill (a new request's prompt) is compute-bound and dominates the pass duration; decode (existing requests) is memory-bound and cheap per step. Mix badly and you get:

• Prefill starvation: new requests wait forever behind long decodes. Terrible p99 latency.
• Decode starvation: existing streams stutter every time a big prompt arrives. Terrible TPS variance.

Strategies:

• First-come, first-served (FCFS) prefill-priority. Simple, hurts existing streams when a big prompt hits.
• Decode-priority. Existing streams smooth; time-to-first-token (TTFT) is unbounded.
• Chunked prefill (Sarathi, DistServe). Split a big prompt into ~2k-token chunks and interleave prefill chunks with decode steps in the same iteration. Bounds both TTFT and inter-token latency (ITL). Now the default in vLLM and TensorRT-LLM.

Chunked prefill in one iteration:

iteration i: [ req A decode 1 tok | req B decode 1 tok | req C prefill chunk 1 (2048 tok) ]
iteration i+1: [ A dec | B dec | C prefill chunk 2 ]
...

The forward is one big variable-length pass over ~2050 tokens. Attention masks (varlen) keep each request's context isolated.

6 · Prefix caching — the batching-adjacent freebie

Two users hit your system with the same system prompt (typical for a product). Without help, you re-prefill those tokens for every user. With prefix caching (vLLM --enable-prefix-caching), the KV cache for shared prefixes is retained and reused across requests. TTFT drops to near-zero for shared prefixes.

It's not batching per se, but every serious continuous-batching system ships it because the memory manager already tracks KV pages.

7 · A minimal continuous-batching loop (educational)

Real vLLM/TGI code is thousands of lines. The core idea in pseudocode:

import heapq
 
class Scheduler:
    def __init__(self, kv_budget_tokens, max_batch):
        self.running = []          # list of Request currently decoding
        self.waiting = []          # priority queue of Request awaiting admission
        self.kv_used = 0
        self.kv_budget = kv_budget_tokens
        self.max_batch = max_batch
 
    def admit(self):
        while self.waiting and len(self.running) < self.max_batch:
            req = self.waiting[0]
            if self.kv_used + req.prompt_len > self.kv_budget:
                break                       # not enough KV memory
            heapq.heappop(self.waiting)
            self.running.append(req)
            self.kv_used += req.prompt_len
 
    def step(self, model):
        # 1) admit new requests if room
        self.admit()
        # 2) build batched input: last token of each running request + any prefill chunks
        tokens, cu_seqlens, kv_ptrs = self._pack_batch()
        # 3) one forward pass
        logits = model.forward_varlen(tokens, cu_seqlens, kv_ptrs)
        # 4) sample next token per request, append to KV cache
        new_toks = sample(logits)
        for req, tok in zip(self.running, new_toks):
            req.tokens.append(tok)
            self.kv_used += 1
        # 5) evict finished requests
        for req in list(self.running):
            if req.done():
                self.running.remove(req)
                self.kv_used -= len(req.tokens)  # free KV pages
                req.callback(req.tokens)

Missing (deliberately) for clarity: preemption, paged KV, chunked prefill, speculative integration, priority. All of these live in Scheduler.step in real systems.

8 · Pitfalls

10 · The 2024–2025 batching landscape

Continuous batching in 2022 was one idea. In 2025 it's a stack of interlocking optimizations. Here's what's new since Orca.

10.1 Disaggregated prefill (Splitwise / DistServe)

Patel et al., Splitwise (ISCA 2024) and Zhong et al., DistServe (OSDI 2024) noticed: prefill and decode have opposite hardware preferences. Prefill wants raw FLOPs (H100); decode wants HBM bandwidth (A100 is nearly as good, cheaper). Running both on the same GPU means one is always the wrong hardware for the current work.

Disaggregated serving: dedicate some GPUs to prefill, others to decode. Ship the KV cache between them over NVLink/RDMA when prefill finishes. Result: 2–4× tokens/dollar improvement at high traffic. Meta, Microsoft, and Anthropic all reportedly run some variant of this in production in 2025.

10.2 vLLM V1's unified scheduler

The January 2025 vLLM v1 release merged prefill and decode paths. Every request has a single "tokens I need to process this step" number, and the scheduler picks a batch that fits the token budget. Prefills, decodes, chunked prefills, and speculative-verifications are all the same abstraction. Cleaner code, ~1.5× throughput on mixed workloads.

10.3 SGLang's RadixAttention

Zheng et al., SGLang (2024) store KV caches in a radix tree keyed by token-prefix. Two requests sharing a system prompt physically share KV pages via copy-on-write. On agent workloads (few-shot prompts, react/CoT scaffolds), 5× throughput uplift vs vLLM without prefix caching, and 30% vs vLLM with prefix caching (SGLang's tree structure catches partial-prefix matches vLLM misses).

10.4 The current default recipe (mid-2025)

For an English-code chat workload on 8×H100:

1. vLLM v1 (or SGLang if you're heavy on shared prefixes).
2. fp8 weights + fp8 KV cache.
3. --enable-chunked-prefill on (V1 default).
4. --enable-prefix-caching on (V1 default).
5. EAGLE-3 speculator if latency-critical, off if throughput-critical.
6. Tensor parallel = 2 for 70B, 4 for 405B fp8, 8 for larger.

That stack routinely hits 8000–12000 tok/s aggregate on one 8×H100 node with Llama-3-70B at reasonable p99.

Further reading — the modern serving stack:

• Yu et al., Orca (OSDI 2022) — the founding paper.
• Kwon et al., PagedAttention (SOSP 2023) — the memory manager that makes it practical.
• Patel et al., Splitwise (ISCA 2024).
• Zhong et al., DistServe (OSDI 2024).
• vLLM team, V1 alpha blog (Jan 2025).
• Zheng et al., SGLang / RadixAttention (2024).

9 · Mermaid: the scheduler loop

Recall

Stretch: you have SLA: p99 TTFT ≤ 300 ms, per-stream ≥ 30 tok/s. Your prompts average 1500 tokens, completions 400. Model runs prefill at 5000 tok/s and decode at 40 tok/s per stream on a single A100 at concurrency 32. Can one A100 hit the SLA at 10 QPS? Show the arithmetic.

In your own words: continuous batching wins because __________________________.

Spaced review: S066 KV cache (the memory constraint), S069 speculative decoding (interacts).

Next session (S071): we open the hood on vLLM and TGI. PagedAttention (the missing piece), block manager, scheduler internals.

Bring back tomorrow:

• Iteration-level vs request-level scheduling.
• Little's Law: $L = \lambda W$.
• Chunked prefill as the default answer to TTFT-vs-TPS.

import random
# replace with real output lengths from your logs
lens = [random.choice([20, 40, 60, 900]) for _ in range(512)]
B = 32
useful = sum(lens)
static = 0
for i in range(0, len(lens), B):
    chunk = lens[i:i+B]
    static += max(chunk) * len(chunk)   # every slot runs to the longest
print('useful token-steps :', useful)
print('static-batch steps :', static)
print('wasted fraction    :', round(1 - useful/static, 3))

Previous: ← DL S069 · Next: DL S071 →