Home / Fundamentals / Inference & Serving

Inference & ServingSeniorQuestion 4 of 7

How do continuous batching and paged attention improve LLM serving throughput?

30-second answer

Static batching holds a batch until its longest request finishes, wasting slots and delaying new requests. Continuous batching schedules every decode iteration: finished sequences leave and waiting ones join, keeping the batch full. Paged attention stores the KV cache in fixed-size blocks with per-sequence block tables, so memory isn't reserved for maximum length, waste is under one block per sequence, and blocks can be shared for common prefixes or parallel samples. Together they raise the effective batch size several-fold. Chunked prefill bounds latency spikes from long prompts; disaggregation separates prefill and decode pools.

Try answering out loud before reading on. The walkthrough below is paced for a 40-minute interview round.

0–5 min Clarify and frame

Framing: "I'll explain why naive batching wastes GPU time and memory, then iteration-level scheduling, then paged KV memory, then prefix sharing and prefill scheduling, with what each buys."

5–15 min Core explanation

Static batching problem. Batch 16 requests; outputs range from 20 to 1,000 tokens. The batch runs until the longest finishes: most slots sit idle for most steps, and new requests wait for the whole batch.

Continuous (iteration-level) batching. The scheduler decides the batch at every decode step:

  • Finished sequences (EOS or max tokens) leave immediately, freeing slots and KV memory.
  • Waiting requests are admitted (prefilled) as soon as memory allows.
  • The batch stays near capacity; throughput gains of several times over static batching are typical under varied output lengths.

Scroll sideways to see the whole diagram.

Inside an LLM serving engineComponents: Clients (stream over SSE); Request queue (admit when KV fits); Iteration scheduler (continuous batching); Model step (decodes + prefill chunk); Sampler (logits → tokens); KV block manager (block tables); Prefix cache (reused prefix blocks); Paged KV memory (16-token blocks in HBM); CPU swap (preempted sequences). Flow: Clients to Request queue; Request queue to Iteration scheduler; Iteration scheduler to Model step; Model step to Sampler; Sampler to Clients (tokens); Iteration scheduler to KV block manager (allocate / free); Prefix cache to KV block manager; KV block manager to Paged KV memory; Model step to Paged KV memory (read / append K,V); Paged KV memory to CPU swap.Clientsstream over SSERequest queueadmit when KV fitsIteration schedulercontinuous batchingModel stepdecodes + prefill chunkSamplerlogits → tokensKV block managerblock tablesPrefix cachereused prefix blocksPaged KV memory16-token blocks in HBMCPU swappreempted sequencestokensallocate / freeread / append K,V
Inside an LLM serving engine. Requests are queued by priority and admitted only when their KV blocks fit. Every iteration, the scheduler builds a batch from running decodes plus chunks of new prompts. The block manager maps each sequence to paged KV blocks and reuses cached prefix blocks. Finished sequences free their blocks immediately and stream out.

15–25 min Deep dive: paged attention

Memory problem. Contiguous per-sequence KV buffers must be reserved for the maximum possible length, because you don't know the output length in advance. Most of the reservation is wasted, and freed buffers fragment memory. Early systems wasted the majority of KV memory this way.

Paging. Split the KV cache into fixed blocks (e.g. 16 tokens × layers × KV heads). Each sequence has a block table mapping logical blocks to physical ones, allocated on demand.

  • Waste ≤ one partial block per sequence.
  • Sharing with copy-on-write: parallel samples (n > 1) or beam candidates share prompt blocks; a block is copied only when modified.
  • Prefix caching: blocks keyed by a hash of their token content (and all previous tokens); a new request with the same prefix reuses them and skips that part of prefill.
  • Preemption: when memory runs out, a sequence can be swapped to CPU or dropped and recomputed later.

The attention kernel reads K/V through the block table (gathering non-contiguous blocks), at a small overhead.

Scheduling details:

  • Admission control: admit a new request only if its prompt plus some expected output fits; otherwise queue.
  • Chunked prefill: a 30k-token prompt is prefilled in chunks interleaved with decode steps, so ongoing streams don't stall.
  • Priorities and fairness: interactive vs batch traffic, per-tenant limits.

25–32 min Trade-offs

Technique Gain Cost
Continuous batching High utilization Variable step composition; scheduler complexity
Paged KV Near-zero fragmentation, sharing Indirection in kernels; block-size tuning
Prefix caching Lower TTFT and compute Memory for cached blocks; cache-aware routing
Chunked prefill Bounded inter-token latency Slightly lower prefill efficiency
Disaggregated prefill/decode Independent tuning and scaling KV transfer bandwidth; more moving parts

Larger batches still increase each step's duration (more KV reads), so a latency SLO caps the batch.

32–37 min Production example

A team moved from a static-batching server to a paged, continuously batched engine. At equal p95 latency, throughput rose ~3×; enabling prefix caching for a 2k-token shared system prompt cut mean TTFT from ~400 ms to ~120 ms. Long-document requests caused inter-token latency spikes for chat users until chunked prefill (2k-token chunks) was enabled.

37–40 min Likely follow-ups

  • How do you pick the block size? Small blocks reduce waste but increase table size and kernel overhead; 16–32 tokens is common.
  • How does prefix caching interact with load balancing? Route by prefix hash (consistent hashing) to maximize hits, with spillover under load.
  • What happens on preemption? Swap blocks to CPU or recompute the prefix later; recomputation is often cheaper than it sounds because prefill is fast.

What interviewers listen for

  • Clear statement of both problems: idle slots and wasted memory.
  • Paging mechanics, including sharing and prefix caching.
  • Awareness of prefill/decode interference.

Red flags

  • Confusing continuous batching with dynamic batching of whole requests.
  • Not knowing why contiguous KV allocation wastes memory.