In production LLM serving frameworks (such as vLLM, TGI, and TensorRT-LLM), memory is the single most critical constraint limiting concurrent throughput. While model parameters consume static VRAM, the dynamic Key-Value (KV) Cache generated during attention decoding grows rapidly with request batch sizes and context lengths.

Legacy serving runtimes allocated pre-allocated contiguous memory blocks based on maximum potential sequence length (e.g. 4,096 tokens). This resulted in severe Internal and External Memory Fragmentation, wasting up to 60%–80% of GPU memory. PagedAttention (Kwon et al.) introduced virtual memory paging concepts to GPU KV caching, transforming LLM serving density.

1. The KV Cache Memory Sizing Equation

For a model with $L$ layers, $H_{\text{kv}}$ key-value heads, head dimension $d_{\text{head}}$, precision bytes $P$ (e.g., 2 bytes for FP16), and sequence length $S$, the memory required to store the KV cache for a single request is calculated as:

$$\text{Memory}_{\text{KVCache}} = 2 \times L \times H_{\text{kv}} \times d_{\text{head}} \times S \times P \text{ bytes}$$

For Llama-3-70B ($L=80, H_{\text{kv}}=8, d_{\text{head}}=128$) with sequence length $S=8,192$ in FP16 ($P=2$):

$$\text{Memory} = 2 \times 80 \times 8 \times 128 \times 8192 \times 2 = 2,684,354,560 \text{ bytes} \approx 2.68 \text{ GB per request}$$

If a GPU server attempts to host a batch of 32 concurrent streams, over 85 GB of VRAM is consumed strictly by the KV cache.

2. Virtual Memory Paging: PagedAttention Block Tables

PagedAttention mimics operating system virtual memory management. Instead of requiring contiguous memory allocations, PagedAttention partitions the KV cache into fixed-size physical blocks (e.g., 16 tokens per block).

The serving engine maintains a dynamic Block Table per request, mapping logical sequence tokens to non-contiguous physical GPU memory pages:

Logical Token Index: [0..15] -> Physical GPU Memory Block 4 Logical Token Index: [16..31] -> Physical GPU Memory Block 19 Logical Token Index: [32..47] -> Physical GPU Memory Block 2

This design eliminates external fragmentation completely and reduces internal fragmentation to less than 4% (only within the final active block of a sequence).

3. Chunked Prefill & FlashDecoding Integration

LLM inference consists of two distinct operational phases:

  • Prefill Phase (Compute-Bound): Processes initial prompt tokens in parallel, generating KV caches for all prompt tokens.
  • Decode Phase (Memory-Bound): Generates 1 token at a time, reading prior KV caches sequentially.

Chunked Prefill co-locates prefill and decode requests within the same iteration batch. Long prompt prefills are split into fixed chunk sizes (e.g., 512 tokens), preventing prompt processing from starving active decode streams.

4. Python Block Table Memory Allocation Engine

from typing import List, Dict class PhysicalBlock: def __init__(self, block_id: int, block_size: int = 16): self.block_id = block_id self.block_size = block_size self.ref_count = 0 class BlockManager: def __init__(self, total_blocks: int, block_size: int = 16): self.block_size = block_size self.free_blocks: List[PhysicalBlock] = [PhysicalBlock(i, block_size) for i in range(total_blocks)] self.block_tables: Dict[int, List[PhysicalBlock]] = {} def allocate(self, request_id: int, num_tokens: int): num_blocks_needed = (num_tokens + self.block_size - 1) // self.block_size if len(self.free_blocks) < num_blocks_needed: raise MemoryError("Out of GPU KV Cache Memory Blocks!") allocated = [] for _ in range(num_blocks_needed): block = self.free_blocks.pop(0) block.ref_count += 1 allocated.append(block) self.block_tables[request_id] = allocated return [b.block_id for b in allocated] def append_token(self, request_id: int, current_seq_len: int): # Check if new block required if current_seq_len % self.block_size == 0: if not self.free_blocks: raise MemoryError("KV Cache full during decode step!") new_block = self.free_blocks.pop(0) new_block.ref_count += 1 self.block_tables[request_id].append(new_block) def free(self, request_id: int): if request_id in self.block_tables: for block in self.block_tables[request_id]: block.ref_count -= 1 if block.ref_count == 0: self.free_blocks.append(block) del self.block_tables[request_id] # Test Allocation Engine if __name__ == "__main__": mgr = BlockManager(total_blocks=100, block_size=16) p_ids = mgr.allocate(request_id=101, num_tokens=45) print(f"Allocated {len(p_ids)} physical blocks for Request 101: {p_ids}") mgr.free(request_id=101) print(f"Available free blocks after release: {len(mgr.free_blocks)}")