Continuous Batching & Serving

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Static Batching: The Waste Problem
5. Continuous Batching
6. Iteration-Level Scheduling
7. PagedAttention Memory Management
8. Prefill-Decode Disaggregation
9. Scheduling Policies
10. Throughput vs Latency Optimization
11. Common Pitfalls
12. Summary
13. Exercises

Learning Objectives

1. Quantify the GPU utilization waste in static batching.
2. Derive the throughput improvement from continuous batching.
3. Explain PagedAttention's virtual memory analogy for KV-cache.
4. Analyze the prefill-decode scheduling conflict.
5. Choose scheduling policies for different latency/throughput requirements.

Notation

• $B$ — batch size
• $T_i$ — generation length of request $i$
• $\text{TTFT}$ — time to first token
• $\text{ITL}$ — inter-token latency
• $\text{TPS}$ — tokens per second (throughput)

Core Intuition

LLM serving is fundamentally different from traditional ML inference: requests arrive dynamically, have variable output lengths (unknown until generation completes), and share GPU resources. Naive batching wastes enormous compute — continuous batching treats the GPU as a pipeline, inserting and removing requests at every iteration to maximize utilization.

Static Batching: The Waste Problem

Static batching: Group $B$ requests, generate until the longest finishes, then start next batch.

Problem: If request lengths are $T_1 = 10, T_2 = 100, T_3 = 500$:

• Request 1 finishes at step 10 but the GPU slot stays occupied (padded) until step 500.
• GPU utilization: $\frac{10 + 100 + 500}{3 \times 500} = 40.7\%$.

Waste formula: For requests with lengths $T_1, \ldots, T_B$:

In practice, output lengths follow a heavy-tailed distribution → utilization often 20–40%.

Continuous Batching

Key idea: At each generation step, independently decide for each slot:

• Continue generating if request is active.
• Insert new request if a slot becomes free.

No waiting for the slowest request. As soon as request $i$ completes (generates EOS), its GPU slot is freed and a new request from the queue takes its place.

Utilization: Approaches 100% if there are always requests in the queue:

Throughput improvement: 2–3x over static batching in production workloads.

Iteration-Level Scheduling

At each decoding iteration, the scheduler:

1. Checks which requests have completed (generated EOS or hit max length).
2. Evicts completed requests, frees their KV-cache.
3. Admits new requests from the waiting queue (if memory available).
4. Preempts low-priority requests if a high-priority request needs resources.

Admission control: The key constraint is KV-cache memory. Each active request consumes memory proportional to its current context length. The scheduler must ensure:

PagedAttention Memory Management

Analogy: KV-cache management mirrors OS virtual memory:

• Physical pages: Fixed-size blocks of GPU memory.
• Page table: Maps each request's logical KV positions to physical pages.
• Demand paging: Allocate pages only when tokens are generated.
• Copy-on-write: Share pages for common prefixes (system prompts).

Benefits:

• Eliminates internal fragmentation (no pre-allocation to max length).
• Enables memory sharing across requests.
• Supports preemption (swap pages to CPU memory).

Implementation (vLLM):

• Page size: typically 16 tokens.
• Each page: $2 \times L \times H \times d_k \times P \times 2$ bytes (FP16).
• Allocation: O(1) per page from free list.

Prefill-Decode Disaggregation

The conflict: Prefill (processing the prompt) and decode (generating tokens) have fundamentally different computational profiles:

• Prefill: Compute-bound, processes many tokens in parallel, high arithmetic intensity.
• Decode: Memory-bound, processes one token per request, low arithmetic intensity.

Problem: Running both on the same GPU creates interference:

• A long prefill blocks decode for all other requests (increases ITL).
• Decode's small batches waste compute capacity that prefill could use.

Solution: Disaggregation (Splitwise, DistServe):

• Separate GPU pools for prefill and decode.
• Prefill GPUs: optimized for throughput (large batches, high compute).
• Decode GPUs: optimized for latency (small batches, high bandwidth).
• KV-cache transferred from prefill GPU to decode GPU after prompt processing.

Scheduling Policies

First-Come-First-Served (FCFS): Process requests in arrival order. Simple, fair, but not optimal for any metric.

Shortest-Job-First (SJF): Prioritize requests with shorter expected output length. Minimizes average latency but requires length prediction.

Preemptive scheduling: Pause a long-running request to serve a short one. KV-cache swapped to CPU memory; resumed later.

Priority queues: Different SLA tiers get different priorities. Premium requests preempt standard ones.

Prefix-aware scheduling: Group requests with shared prefixes together to maximize KV-cache reuse.

Throughput vs Latency Optimization

Throughput maximization (batch processing):

• Maximize batch size: fill GPU memory with as many concurrent requests as possible.
• Allow higher ITL in exchange for more total tokens/second.
• Best for: offline processing, batch jobs.

Latency minimization (interactive):

• Keep batch size small: ensure each decode step is fast.
• TTFT constraint: prefill must complete within SLA (e.g., 200ms).
• ITL constraint: each token generated within budget (e.g., 50ms).
• Best for: chatbots, real-time applications.

Pareto frontier: There's an inherent tradeoff:

Increasing batch size improves throughput but increases per-token latency.

Common Pitfalls

Pitfall 1. Not accounting for KV-cache growth in batch size planning. Admitting too many requests leads to OOM when they all generate long outputs.

Pitfall 2. Mixing long prefills with latency-sensitive decode. A single 10K-token prefill can block all decoding for 500ms, violating ITL SLAs for other requests.

Pitfall 3. Ignoring the cold-start problem. First token latency (TTFT) is dominated by prefill time. For long prompts (>10K tokens), TTFT can be several seconds even with continuous batching.

Summary

• Static batching wastes 40–80% of GPU compute due to variable output lengths.
• Continuous batching achieves ~100% utilization by inserting/removing requests every step.
• PagedAttention manages KV-cache like virtual memory — no fragmentation, enables sharing.
• Prefill-decode disaggregation resolves the fundamental compute-profile mismatch.
• Scheduling policy choice depends on SLA: throughput (max batch) vs latency (min batch).

Exercises

Exercise 1. For requests with lengths $T = [50, 150, 400, 80, 200]$: compute static batching utilization vs continuous batching utilization (assuming infinite queue).

Exercise 2. Compute the maximum concurrent requests for an 80GB GPU serving a 7B model (14GB weights) with per-token KV-cache of 160KB and average context 2048 tokens.

Exercise 3. Design a scheduling policy that maintains TTFT < 500ms and ITL < 100ms for a model with prefill speed 10K tokens/s and decode speed 50 tokens/s.

Exercise 4. Derive the memory transfer cost of preempting a request with 4096 cached tokens to CPU (PCIe Gen4, 32 GB/s).

Exercise 5. Explain why prefix caching combined with continuous batching can achieve super-linear throughput scaling when many requests share a system prompt.