Why LLMs Run Out of VRAM: KV Cache Fragmentation and How PagedAttention Fixes It

You deploy a 13-billion parameter model quantized to 4-bit weights. The static model weights consume roughly 7.5 GB of VRAM. You put it on an NVIDIA RTX 4090 with 24 GB of memory, confident you have more than 16 GB of headroom for traffic.

Then you run a batch of 8 concurrent requests with 4,000-token context windows.

Within seconds, your server throws torch.cuda.OutOfMemoryError: CUDA out of memory or your throughput collapses from 80 tokens per second to single digits.

Where did those 16 gigabytes go?

Most developers assume GPU memory during inference is dominated by model weights. In reality, once an LLM starts serving concurrent users, the Key-Value (KV) Cache quickly swallows more memory than the model itself.

Even worse: in naive serving setups, up to 60% to 80% of that VRAM is pure waste, locked away by memory fragmentation.

Here is what is actually happening inside GPU memory during inference, why naive allocators fail, and how an idea borrowed from 1960s operating systems (PagedAttention) fixed it.

1. Why Transformers Need a KV Cache

To understand why memory explodes, look at how autoregressive token generation works.

Generating text is an iterative loop. When generating token $t$:

1. The token is embedded and passed through $N$ transformer layers.
2. In each self-attention layer, the model computes Query ($Q$), Key ($K$), and Value ($V$) projections.
3. Attention is calculated: $$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$
4. To compute the attention of the new token $t$ against all previous tokens $(1 \dots t-1)$, the model needs the $K$ and $V$ vectors of every previous token.

Step 1:  [Prompt: "The", "quick", "brown"]  -> Generates "fox"
Step 2:  ["The", "quick", "brown", "fox"]   -> Generates "jumps"
Step 3:  ["The", "quick", "brown", "fox", "jumps"] -> Generates "over"

Without caching, generating token 1,000 would require recomputing the Key and Value matrices for all 999 previous tokens across every single transformer layer. That would turn inference complexity into $O(n^2)$ compute.

To avoid this quadratic recalculation, inference engines store the $K$ and $V$ tensors of all previous tokens in GPU High-Bandwidth Memory (HBM). On every step, we only compute $Q$, $K$, and $V$ for the single new token, append its $K$ and $V$ to the cache, and calculate attention against the stored history.

Compute drops to $O(1)$ per step. But your memory requirement becomes dynamic and strictly increasing.

2. The Concrete Math of KV Cache Growth

How big is a KV cache in physical memory?

For every generated token, at every transformer layer, we must store two vectors ($K$ and $V$).

The exact formula for KV cache memory per token is:

$$\text{Bytes per Token} = 2 \times n_{\text{layers}} \times n_{\text{kv_heads}} \times d_{\text{head}} \times b$$

Where:

• $2$ accounts for both the Key and Value tensors
• $n_{\text{layers}}$ is the number of transformer layers
• $n_{\text{kv_heads}}$ is the number of Key-Value attention heads
• $d_{\text{head}}$ is the hidden dimension per head
• $b$ is the precision in bytes (2 bytes for FP16/BF16, 1 byte for FP8)

Example 1: Multi-Head Attention (Llama-2-13B)

• Layers ($n_{\text{layers}}$): 40
• KV Heads ($n_{\text{kv_heads}}$): 40 (standard Multi-Head Attention)
• Head Dimension ($d_{\text{head}}$): 128
• Precision: 16-bit float (2 bytes)

$$\text{Bytes per Token} = 2 \times 40 \times 40 \times 128 \times 2 = 819,200 \text{ bytes} \approx 800\text{ KB per token}$$

For a single request processing a 4,096-token context:
$$4,096 \times 800\text{ KB} \approx 3.2\text{ GB per sequence}$$

If you serve 8 concurrent users at 4k context:
$$8 \times 3.2\text{ GB} = \mathbf{25.6\text{ GB of VRAM}}$$

The KV cache alone exceeds the total VRAM of an RTX 4090 before you even account for model weights or CUDA overhead.

Example 2: Grouped-Query Attention (Llama-3-8B)

Modern architectures use Grouped-Query Attention (GQA) where multiple query heads share a single KV head.

• Layers: 32
• KV Heads: 8 (sharing across 32 query heads)
• Head Dimension: 128
• Precision: 16-bit float (2 bytes)

$$\text{Bytes per Token} = 2 \times 32 \times 8 \times 128 \times 2 = 131,072 \text{ bytes} = 128\text{ KB per token}$$

At 4,096 tokens, one request takes 512 MB. A batch of 32 requests takes 16 GB.

3. The Real Culprit: Memory Fragmentation

If a request only needs 512 MB at 4k tokens, why did naive serving engines run out of memory with only a handful of short requests?

The problem lies in how standard PyTorch memory allocators manage dynamic tensors.

Standard attention kernels (like basic PyTorch MultiheadAttention or cuDNN) expect the Key and Value tensors of a sequence to be stored in contiguous virtual and physical memory.

Naive Allocator (Contiguous Slot per Sequence):
Request A: [Token 1][Token 2][Token 3] ... [Reserved Empty Space up to 4096]
Request B: [Token 1][Token 2] ............ [Reserved Empty Space up to 4096]

Because the inference engine cannot predict when a model will emit the <|endoftext|> token, it faces three severe structural inefficiencies:

1. Internal Fragmentation (Static Max-Length Reservation)

To prevent constant memory reallocation and costly CUDA memory copies as sequences grow, naive engines pre-allocate a contiguous memory buffer sized for max_model_len (e.g., 4,096 tokens).

If a user prompt only generates 350 tokens and terminates, the remaining 3,746 token slots (over 90% of the allocated buffer) sit completely unused, yet locked.

2. Reservation Waste (Future Slots)

Even if an engine attempts dynamic chunking, it must reserve memory for future tokens that have not arrived yet. That reserved memory cannot be assigned to other concurrent requests.

3. External Fragmentation

Requests finish at different times. As short requests finish and free their memory chunks, the GPU memory pool becomes a checkerboard of small, non-contiguous free memory holes.

Even if you have 8 GB of total free VRAM, if the largest contiguous block is only 200 MB, a new incoming request requiring a 500 MB contiguous buffer will immediately crash with an Out of Memory error.

In research published by UC Berkeley (Kwon et al., SOSP 2023), measurements showed that in traditional serving systems like FasterTransformer and Orca, only 20% to 40% of the allocated KV cache memory actually held useful token states. The remaining 60% to 80% was lost to fragmentation.

4. How PagedAttention Solves Fragmentation

Operating systems solved the exact same problem for system RAM in the 1960s with Virtual Memory Paging.

A process sees a continuous virtual address space ($0 \dots N$), but the OS kernel splits physical RAM into fixed-size 4 KB pages. A CPU Page Table maps each virtual page to any available non-contiguous physical memory frame.

PagedAttention (the core engine powering vLLM, SGLang, and modern inference backends) applies this exact concept to GPU VRAM.

Logical KV Cache (Sequence 0):
[Block 0: Tokens 0-15] -> [Block 1: Tokens 16-31] -> [Block 2: Tokens 32-47]
           │                         │                         │
           ▼                         ▼                         ▼
Physical GPU Memory (Non-contiguous):
[Physical Block 84]       [Physical Block 12]       [Physical Block 903]

How the Architecture Works:

1. Fixed-Size KV Blocks: The KV cache of a sequence is partitioned into fixed blocks of tokens (typically 16 or 32 tokens per block).
2. Centralized Physical Block Pool: At startup, vLLM pre-allocates all available GPU memory into a pool of physical blocks.
3. Block Tables: For each active sequence, the engine maintains a Block Table (analogous to an OS page table). The block table records the physical block ID where each logical block resides, along with how many slots in the latest block are filled.
4. On-Demand Allocation: When a request starts, the engine allocates only one physical block (16 tokens). As the model generates tokens 1 through 15, it writes into the existing block. When it hits token 16, the engine grabs another physical block from the pool and records its address in the Block Table.

The PagedAttention CUDA Kernel

Standard cuBLAS and FlashAttention kernels require contiguous memory pointers.

PagedAttention replaces the attention operation with a custom GPU kernel. During the decoding step, the kernel reads the query token $Q_i$, looks up the sequence's Block Table, and dynamically fetches $K$ and $V$ vectors directly from scattered physical memory addresses across GPU HBM during the matrix multiplication loop.

The Result:

• Internal Fragmentation: Limited strictly to the last uncompleted block of a sequence (less than 4% memory waste with block size 16).
• External Fragmentation: 0%. Any free block anywhere in memory can be assigned to any sequence immediately.
• Effective Batch Size: Increases by 2x to 4x on the exact same hardware.

5. Superpowers of Paged Memory: Zero-Copy Forking

Because memory is managed through indirection (block tables pointing to physical blocks), PagedAttention unlocks memory optimizations that are impossible with contiguous arrays.

1. Parallel Sampling & Tree Search

Suppose you want the model to generate 4 candidate completions for the same prompt (e.g., beam search, voting, or speculative draft trees).

In naive systems, you must duplicate the prompt's KV cache 4 times in memory.

With PagedAttention, all 4 sequences point their block tables to the same physical prompt blocks. The physical blocks are marked with a reference count of 4.

Request Prompt (Tokens 0-31): Physical Block #7, Physical Block #14 (Ref Count = 2)

Branch A (Tokens 32-47) -> Writes to new Physical Block #89 (Private)
Branch B (Tokens 32-47) -> Writes to new Physical Block #102 (Private)

Only when a branch generates its first new token does the engine allocate a new private block for that specific branch (Copy-on-Write). Memory consumption for the prompt is reduced by 75%.

2. Automatic Prefix Caching

In agentic workflows, system prompts, tool schemas, and multi-turn conversation history are reused constantly across requests.

With prefix caching enabled, when a new request arrives containing a system prompt that matches a previously computed sequence, vLLM checks its hash table of physical blocks. If the tokens match, it skips the prefill compute phase entirely and simply maps the existing physical blocks into the new request's block table.

First-token latency (Time-to-First-Token) drops from hundreds of milliseconds to near zero, and VRAM usage for the shared prefix drops to 0 additional bytes.

6. Practical Tuning Guide for Production Inference

If you are running self-hosted LLMs using vLLM, SGLang, or Ollama, here is how to tune these memory parameters for maximum throughput:

1. Tune GPU Memory Utilization

By default, vLLM sets gpu_memory_utilization=0.90. This reserves 90% of total VRAM for model weights and the KV block pool, leaving 10% for PyTorch activation buffers and CUDA contexts.

# For dedicated serving nodes with fixed models, raise utilization to 0.95
vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --gpu-memory-utilization 0.95 \
  --max-model-len 8192

If you experience random CUDA initialization crashes, lower it to 0.85.

2. Select the Right Block Size

The default block size in vLLM is 16.

• Block size 16: Lowest internal fragmentation. Best for workloads with short, unpredictable outputs.
• Block size 32: Better GPU memory coalescing and slightly higher arithmetic throughput on high-end GPUs (A100/H100), with slightly higher tail waste.

vllm serve meta-llama/Llama-3.1-8B-Instruct --block-size 32

3. Enable Prefix Caching for Multi-Turn Agents

If you run coding assistants, customer support bots, or agent loops that share large system prompts:

vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --enable-prefix-caching

4. Enable FP8 KV Cache

If you are memory-bound rather than compute-bound, you can quantize the KV cache from FP16 (2 bytes) to FP8 (1 byte). This cuts your KV memory usage in half with negligible perplexity degradation.

vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --kv-cache-dtype fp8

Summary: Contiguous vs Paged Attention

The next time your local or production LLM runs out of VRAM, remember: the bottleneck is rarely just the model parameters. Understanding how the KV cache grows and how paging eliminates memory waste is the single most important lever for scaling LLM inference throughput.