PagedAttention and vLLM Architecture: Virtual Memory for LLM Serving

In 2023, researchers at UC Berkeley introduced vLLM and the PagedAttention algorithm (Kwon et al.), revolutionizing Large Language Model infrastructure. By adopting the time-tested principles of Virtual Memory and Paging from Operating Systems, PagedAttention eliminates memory fragmentation, slashing KV cache memory waste from over 60% down to less than 4% and boosting system throughput by $2\times -4\times$.

In this lesson, you will dissect the internal architecture of PagedAttention, study its block table translation mechanisms, examine Copy-on-Write for branching generation, and prepare for Landmark Global Arena Capstone #2: PagedAttention Block Table Allocator.

1. The Core Innovation: Logical vs Physical Blocks

In an Operating System:

• A user application sees a contiguous virtual address space ($0\text{x}0000\dots 0\text{xFFFF}$).
• The OS Memory Management Unit (MMU) maps each virtual page to arbitrary, non-contiguous physical RAM frames using a Page Table.

PagedAttention applies this exact paradigm to the Transformer KV Cache:

1. Logical KV Blocks: A request's context sequence is divided into fixed-size logical chunks of $B_{\text{size}}$ tokens (typically $B_{\text{size}}=16$ or $32$ tokens).
2. Physical KV Blocks: Physical GPU VRAM is pre-allocated at startup into a fixed pool of memory pages. Each physical page holds the Key and Value tensors for exactly $B_{\text{size}}$ tokens.
3. Block Table: A dynamic lookup table maintained by the serving engine that maps each request's Logical Block index to its assigned Physical Block index in VRAM.

Why Internal Fragmentation is Bounded to $<4\%$

In PagedAttention, memory is allocated incrementally one block at a time only when a request generates tokens that overflow its current block.

• Internal fragmentation occurs only in the very last active block of a sequence.
• If block size is $16$ tokens, the maximum wasted space for a sequence is at most $15$ tokens.
• For an average context of 500 tokens: $\text{Waste}\le \frac{15}{500}=3.0\%\text{ waste}$

2. PagedAttention Attention CUDA Kernel Mechanics

During the autoregressive decoding step for token $t$:

1. The model computes the query vector ${\mathbf{q}}_t$ for the new token.
2. The custom PagedAttention CUDA kernel takes the Query vector and the request's Block Table.
3. Instead of fetching contiguous tensors from memory, the CUDA kernel iterates through the physical block pointers listed in the Block Table:
   • Fetches physical block #7 from VRAM $\to$ computes dot product with ${\mathbf{q}}_t$ for tokens $0-15$.
   • Fetches physical block #1 from VRAM $\to$ computes dot product with ${\mathbf{q}}_t$ for tokens $16-31$.
   • Fetches physical block #12 from VRAM $\to$ computes dot product with ${\mathbf{q}}_t$ for tokens $32-47$.
4. The kernel performs online Softmax reduction across all blocks and multiplies by the physical Value blocks in a single, fused operation.

3. Copy-on-Write (CoW) for Parallel Sampling & Beam Search

When generating multiple completions for the same prompt (e.g., $N=4$ responses for RLHF sampling or majority-vote reasoning), naive systems replicate the entire prompt KV cache 4 times.

PagedAttention achieves zero-copy branching using Copy-on-Write (CoW):

1. When a prompt is processed, its logical blocks are assigned physical blocks with a reference count of $4$ (ref_count = 4).
2. All 4 output streams share the exact same physical blocks in VRAM for the prompt.
3. When Stream 1 generates a new token and needs to write to its own block:
   • If the block's ref_count > 1, the engine allocates a new physical block from the free pool, copies the 16 tokens over, decrements the old block's reference count to 3, and updates Stream 1's Block Table.
   • Subsequent token writes happen privately in Stream 1's allocated block.

4. Minimal Python Implementation: PagedAttention Block Allocator

The following Python class implements a functional block-table memory allocator with physical block pool management, dynamic token appending, and Copy-on-Write branching.

5. 🏆 Landmark Global Arena Capstone #2 Preview

In Arena Capstone #2 (global-llm-paged-attention-allocator), you will build a production-grade virtual memory PagedAttention allocator supporting:

• Physical Block Table allocation and release.
• Dynamic token allocation with automatic block boundary crossing.
• Copy-on-Write reference counting and page duplication on mutation.
• Deterministic simulation of multi-tenant KV cache paging.

6. Summary & Key Takeaways

1. Virtual Memory Solves the KV Cache Wall: PagedAttention splits logical sequences into small fixed-size blocks (16 or 32 tokens) mapped to non-contiguous physical GPU pages.
2. Near-Zero Memory Waste: Internal fragmentation is strictly limited to the trailing block ($<4\%$), eliminating over 60% of legacy serving waste.
3. Copy-on-Write Enables Free Branching: Parallel sampling and beam search share physical prompt memory pages until a worker modifies its sequence.
4. The Standard for Modern AI: PagedAttention powers vLLM, TensorRT-LLM, SGLang, and Hugging Face TGI, serving as the foundational memory manager of production AI infrastructure.