Kv Cache Pagedattention

PART 10 — KV Cache & PagedAttention

In the decode while loop, recalculating the Attention scores for tokens 1-100 just to generate token 101 is wasteful.

• KV Cache: We cache the computed Key and Value tensors for every token. This is pure Dynamic Programming (Memoization).

The Problem: Pre-allocating contiguous GPU memory for the max context window (e.g., 32k tokens) for every user results in massive memory fragmentation (just like old OS memory management).

The Solution: PagedAttention (vLLM) * SDE Analogy: OS Virtual Memory Paging. * Instead of allocating contiguous memory, we allocate small "pages" (e.g., blocks of 16 tokens). A block table maps logical token positions to physical memory blocks. This eliminates fragmentation and allows memory sharing (e.g., if 100 users share the same system prompt, they share the same physical KV cache blocks).

---