Lab 03 — Continuous Batching & PagedAttention

Phase: 08 — Inference Optimization at Depth | Difficulty: ⭐⭐⭐⭐⭐ | Time: 4–5 hours

vLLM's PagedAttention + continuous batching achieves 23× higher throughput than naive batching.

What you build

  • KVBlock — fixed-size memory block for KV cache storage
  • PagedKVCache — block table mapping sequences to KV blocks, LRU eviction when OOM
  • ContinuousBatcher — admit new requests mid-batch, evict finished ones each step
  • simulate_serving — end-to-end serving simulation with arrival/completion tracking

Key concepts

ConceptWhat to understand
KV cache fragmentationStatic allocation wastes memory — paged allocation wastes ~0%
Block tableSequence → list of physical block IDs (like virtual memory paging)
Continuous batchingAdd/remove sequences each step — no waiting for full batch
LRU evictionEvict least-recently-used blocks when new sequence can't fit
PreemptionSuspend running sequence, swap to CPU, resume when memory frees

Files

FilePurpose
lab.pyStubs with TODO markers
solution.pyComplete working implementation
test_lab.pypytest suite
requirements.txtDependencies

Run

pip install -r requirements.txt
python lab.py
pytest test_lab.py -v