Allocate the Cache: Blocks, Waste, and PagedAttention

In the previous lesson, you derived the complete KV cache memory formula and calculated exact byte counts for Llama 3 8B, Llama 2 7B, and other models. You saw that a single request at 4K context with BF16 precision needs 0.5 GiB, and that batch size and context length multiply each other — a batch of 64 at 128K context needs 1.0 TiB of cache memory alone.

Now we face the allocation problem: How do you actually reserve those bytes on the GPU?

---

The Problem with Contiguous Pre-Allocation

In early inference engines, memory for a request’s KV cache had to be allocated as a single, contiguous block of VRAM.

The fundamental dilemma: You do not know in advance how many tokens the model will generate. Generation stops when the model emits an end-of-sequence token (for example, <|endoftext|>), which is non-deterministic. The prompt might be 50 tokens and the completion 5, or the prompt might be 50 tokens and the completion 2,000.

Therefore, engines had to pre-allocate memory for the worst-case sequence length — the configured maximum context window (max_seq_len), typically 2,048 or 4,096 tokens (and up to 128K or 1M on modern models).

---

Internal vs External Memory Fragmentation

This pre-allocation strategy creates two distinct types of memory waste.

Internal Fragmentation

Internal fragmentation is memory reserved inside a request’s contiguous buffer that is never actually written to.

Example: You reserve 4,096 token slots for a request. The model generates 200 tokens and stops. The remaining 3,896 slots (95%) sit empty, but no other request can use them because the buffer is one contiguous reservation.

External Fragmentation

External fragmentation is memory holes between allocated request buffers.

Even if total free memory across the GPU is 10 GiB, if it is chopped into small 500 MiB gaps, a new request needing a contiguous 2 GiB block will crash with an Out-Of-Memory (OOM) error — despite 10 GiB being free!

Real production impact: Contiguous allocation resulted in 60% to 80% memory waste in early serving systems. A GPU with 80 GiB VRAM could effectively serve only 16–32 GiB worth of actual cache data.

---

PagedAttention: Operating System Virtual Memory for GPUs

The key insight from operating systems: virtual memory solved this decades ago using paging.

Instead of one contiguous block, divide GPU physical VRAM into fixed-size physical blocks (for example, 16 tokens per block). A request’s cache is then a chain of these blocks, scattered anywhere in physical memory.

Core Concepts (Explained Before Use)

Term	Meaning
Physical Block	A fixed-size chunk of GPU VRAM that holds B_size token slots (e.g., 16 tokens × 128 KiB = 2 MiB). Blocks are allocated from a global free list.
Logical Block	The sequence’s view: Block 0 = tokens 0–15, Block 1 = tokens 16–31, Block 2 = tokens 32–47, etc. Always contiguous in logical space.
Block Table	A per-request lookup array: block_table[logical_block_id] = physical_block_id. Maps logical positions to physical memory.
Free List	Global pool of unallocated physical blocks. When a request needs a new logical block, the engine pops one from this list.

Dynamic On-Demand Allocation

• A request starts with zero physical blocks allocated.
• When the first token arrives (prefill), the engine allocates one physical block (Logical Block 0).
• When the request fills that block (token 16 arrives), the engine allocates another physical block (Logical Block 1).
• No pre-allocation. No guessing. The request consumes exactly the memory it needs, plus at most B_size - 1 slots in the final block.

Waste Reduction

Fragmentation Type	Contiguous Pre-Allocation	PagedAttention
External	Severe (60–80% waste)	0% — any free block fits any request
Internal	Up to (max_seq_len - actual_len) tokens	Bounded to ≤ B_size - 1 tokens per request

With B_size = 16 and a 4K sequence: maximum internal waste = 15 tokens = 0.37%. With B_size = 16 and an 8K sequence: < 0.2% waste.

---

How the Block Table Works

The block table is a simple array. For a request with logical blocks 0, 1, 2:

block_table = [ 7, 2, 14 ]

This means:

• Logical Block 0 (tokens 0–15) → Physical Block #7
• Logical Block 1 (tokens 16–31) → Physical Block #2
• Logical Block 2 (tokens 32–47) → Physical Block #14

Token lookup at decode time:

To read the Key/Value for token position t:

logical_block_id = t // B_size
slot_in_block    = t % B_size
physical_block   = block_table[logical_block_id]
physical_address = physical_block.base_address + slot_in_block * bytes_per_token

The attention kernel reads from this physical address. No contiguous buffer required.

---

Exercise 1: Naive Static Pre-Allocation Waste Calculation

Scenario: 4 concurrent requests on Llama 3 8B (128 KiB per token). Static pre-allocation: 2,048 tokens per request. Actual sequence lengths:

• Request 1: 200 tokens
• Request 2: 600 tokens
• Request 3: 150 tokens
• Request 4: 1,050 tokens

Step 1: Total allocated memory

4 requests × 2,048 tokens/request × 128 KiB/token
= 8,192 × 128 KiB
= 1,048,576 KiB
= 1.0 GiB

Step 2: Total actually used memory

(200 + 600 + 150 + 1,050) tokens × 128 KiB/token
= 2,000 × 128 KiB
= 256,000 KiB
= 250.0 MiB
≈ 0.244 GiB

Step 3: Wasted memory

1.0 GiB - 0.244 GiB = 0.756 GiB
Percentage wasted = 0.756 / 1.0 = 75.6%

Result: 75.6% of allocated memory is wasted — almost entirely internal fragmentation. This is the baseline we must improve.

---

Exercise 2: Tracing PagedAttention Block Mapping Step-by-Step

Parameters: Block size B_size = 4 tokens. Request has 9 tokens (tokens 0 to 8).

Initial Allocation

Logical Block	Token Range	Physical Block
0	0, 1, 2, 3	#7
1	4, 5, 6, 7	#2
2	8	#14

Block table: [7, 2, 14]

Physical Block #14 has 1 slot used (token 8), 3 slots free.

Trace New Token Arrivals

Token 9 arrives:

• logical_block_id = 9 // 4 = 2
• slot_in_block = 9 % 4 = 1
• Physical Block #14 already allocated → write to slot 1
• No new allocation needed.

Tokens 10 and 11 arrive:

• Token 10 → Logical Block 2, slot 2
• Token 11 → Logical Block 2, slot 3
• Physical Block #14 now full (4/4 slots used).

Token 12 arrives:

• logical_block_id = 12 // 4 = 3 (new logical block!)
• slot_in_block = 12 % 4 = 0
• Engine allocates Physical Block #9 from free list
• Appends to block table: block_table = [7, 2, 14, 9]
• Writes token 12 to Physical Block #9, slot 0

Result: The request grew from 3 to 4 physical blocks, each allocated exactly when needed. Zero external fragmentation. Internal waste at most 3 tokens (the unused slots in the last block).

---

Exercise 3: Concurrency and Throughput Gain from PagedAttention

System: GPU server with 32 GiB KV cache pool. Workload: Average sequence length 500 tokens; max context limit 4,096 tokens. Model: Llama 3 8B (128 KiB per token).

Case A: Naive Static Pre-allocation

Memory per request = 4,096 tokens × 128 KiB = 512 MiB = 0.5 GiB
Max concurrency    = 32 GiB / 0.5 GiB = 64 requests

Case B: PagedAttention (16-token blocks)

Tokens per request = ceil(500 / 16) × 16 = 32 × 16 = 512 tokens
Memory per request = 512 × 128 KiB = 64 MiB = 0.0625 GiB
Max concurrency    = 32 GiB / 0.0625 GiB = 512 requests

Concurrency Multiplier

512 / 64 = 8× higher throughput!

Why 8×? The average sequence (500 tokens) needs only 512 token slots with paging, but 4,096 slots with static pre-allocation. The ratio is 4,096 / 512 = 8. This matches the up to 8× concurrency increase reported in the vLLM paper.

---

Summary Reference Table

Dimension	Contiguous Pre-Allocation	PagedAttention
External fragmentation	Severe (60–80% waste)	0%
Internal fragmentation	Up to max_seq_len - actual_len	≤ B_size - 1 tokens
Memory efficiency at 500 avg / 4K max	~12% utilized	~99.8% utilized
Allocation timing	All at request start	On-demand, per block
OOM risk from holes	High	None
Block table overhead	None	Small array per request (~1 KiB)
Kernel complexity	Simple contiguous reads	Indirect lookup via block table
Concurrency multiplier (typical)	1× (baseline)	4×–8×

---

Primary Source Citations

• Kwon et al. (2023), Efficient Memory Management for Large Language Model Serving with PagedAttention — arXiv:2309.06180 (Original PagedAttention paper, vLLM system)
• Denning (1970), Virtual Memory — ACM Computing Surveys (Operating system paging foundations)
• Yu et al. (2022), Orca: A Distributed Serving System for Transformer-Based Generative Models — arXiv:2211.05102 (Iteration-level scheduling, pre-dates PagedAttention but motivates the problem)

---

What Comes Next

• Next lesson: Reuse, Evict, or Limit Earlier Context — Now that cache memory is allocated efficiently, learn how multiple requests can share prefix blocks (prefix caching), how to evict blocks when memory fills up, and how sliding-window attention bounds cache growth.
• Previous lesson: Calculate KV Cache Memory by Hand
• Track overview: Start Here: LLM Foundations