The KV Cache OOM
CUDA_OOM_KILLED — 13.25 GiB free, request rejected
ML Platform: An A100 inference server has 51 active chats and more than 13 GiB free in its KV-cache arena. A new 4096-token request still cannot reserve a 2 GiB contiguous region.
The trap: Per-request contiguous KV regions turn churn from mixed-length sequences into scattered holes. Total free memory is large, but the biggest span is only 0.75 GiB.
Your task
Implement three methods on `PagedAllocator` in `paged_attention.py`: allocate one block on demand, reclaim a completed request, and map logical token positions through its block table.
Book: One sequence, one contiguous tensor. Prod: Fixed-size physical blocks plus logical-to-physical mapping.
Skills you'll prove
Interview Tip
When discussing LLM serving, explain that KV-cache demand grows with sequence length and concurrency. Contiguous reservation wastes capacity and can fail when churn leaves only small free spans. Paged KV caches allocate fixed-size blocks on demand, map logical positions through a block table, and reclaim blocks as requests finish. This improves admission and batching without requiring each request's KV memory to be physically contiguous.