PagedAttention: How vLLM Serves AI Like an Operating System

You're running a model server. 50 users are chatting simultaneously. Each conversation has a different length — some are 200 tokens in, some are 10,000. You've pre-allocated GPU memory for each user assuming maximum context length.

Result? 60-80% of your GPU memory is wasted. Reserved but empty. Sitting there doing nothing while new users queue up.

This is the exact problem that operating systems solved in the 1960s with virtual memory. And in 2023, the vLLM team at UC Berkeley brought that same idea to LLM serving.

PagedAttention treats KV cache like virtual memory — with pages, page tables, and even copy-on-write. It increased serving throughput by 2-4x without changing a single model weight.

The KV Cache Waste Problem

Let's look at how traditional LLM servers allocate memory for KV cache:

Contiguous Allocation (The Old Way)

Each request gets a contiguous block of GPU memory pre-allocated for its maximum possible sequence length:

GPU Memory Layout (Traditional):

←— Request A: allocated 8K tokens —→←— Request B: allocated 8K tokens —→ [used: 1200 tokens][wasted: 6800][used: 3500 tokens][wasted: 4500]

Request A: 1200/8000 used = 85% wasted

Request B: 3500/8000 used = 44% wasted

Average: ~65% memory wasted

Why allocate the maximum? Because you don't know how long the conversation will be. And KV cache must be contiguous in traditional implementations — you can't just extend it when you need more.

Three Types of Waste

Waste Type What Happens How Much

Together, these waste patterns mean a traditional server uses only 20-40% of GPU memory effectively. That directly limits how many concurrent users you can serve.

PagedAttention: Virtual Memory for KV Cache

PagedAttention breaks KV cache into fixed-size pages (called blocks), just like an OS manages RAM:

Key Concepts

OS Concept PagedAttention Equivalent

How It Works

Instead of allocating one big contiguous chunk per request, PagedAttention:

Divides KV cache into blocks — each block holds KV pairs for a fixed number of tokens (e.g., 16 tokens)

Allocates blocks on demand — only when new tokens need to be stored

Maps logical to physical — a block table tracks where each request's blocks live in GPU memory

Blocks don't need to be contiguous — they can be scattered across GPU memory

PagedAttention Memory Layout:

Physical GPU Memory (blocks):

[A:0][B:2][A:1][C:0][B:0][free][A:2][B:1][free][C:1][free][free]

Block Tables:

Request A: logical [0,1,2] → physical [0, 2, 6]

Request B: logical [0,1,2] → physical [4, 7, 1]

Request C: logical [0,1] → physical [3, 9]

Free blocks: [5, 8, 10, 11] ← available for any request

The Magic: No Pre-allocation

Traditional server:

Request A arrives → "What's the max context? 8K? Allocate 8K tokens worth of KV cache NOW"

Request A actually uses → 1,200 tokens

Waste → 6,800 tokens × 2 (K+V) × layers × head_dim × dtype = massive

PagedAttention:

Request A arrives → Allocate 1 block (16 tokens)

Request A generates token 17 → Allocate 1 more block

Request A generates token 33 → Allocate 1 more block

...

Request A uses 1,200 tokens → 75 blocks allocated (1,200/16)

Waste → at most 15 tokens (last block partially filled) ≈ 1.2%

Near-zero waste. Instead of 65%, you waste less than 4% (only the last block's internal fragmentation).

🔧

vLLM: PagedAttention in Production

vLLM (Virtual LLM) is the inference engine built around PagedAttention. It's the most popular open-source LLM serving solution.

python

from vllm import LLM, SamplingParams

Start vLLM — PagedAttention is automatic

llm = LLM(
model="meta-llama/Llama-3-8B-Instruct",
    gpu_memory_utilization=0.90,  # Use 90% of GPU for KV cache
    max_model_len=8192,
    block_size=16,  # PagedAttention block size (tokens per block)

)

Serve multiple requests — vLLM handles KV cache management

prompts = [
"Explain quantum computing in simple terms",
    "Write a Python function to sort a list",
    "What's the capital of France?",

]

params = SamplingParams(temperature=0.7, max_tokens=512)
outputs = llm.generate(prompts, params)

vLLM Architecture

┌─────────────────────────────────────────┐

│ vLLM Engine │

│ │

│ ┌─────────┐ ┌───────────┐ ┌───────┐ │

│ │Scheduler│→ │KV Cache │→ │Model │ │

│ │ │ │Manager │ │Runner │ │

│ │(decides │ │(PagedAttn │ │(runs │ │

│ │ which │ │ block │ │ the │ │

│ │ requests│ │ alloc/ │ │ model)│ │

│ │ to run) │ │ free) │ │ │ │

│ └─────────┘ └───────────┘ └───────┘ │

│ ↑ │

│ ┌─────────┐ │

│ │Request │ Incoming prompts │

│ │Queue │← from API │

│ └─────────┘ │

└─────────────────────────────────────────┘

The scheduler is the key component. It uses the KV cache manager to:

Know how many free blocks are available

Decide which requests to process (continuous batching)

Preempt low-priority requests by swapping their blocks to CPU memory

📊

Copy-on-Write: Sharing KV Cache

PagedAttention enables something powerful: sharing KV cache blocks across requests.

Parallel Sampling

When you generate multiple outputs for the same prompt (e.g., n=4 in the API), all four outputs share the same prompt KV cache:

Prompt: "Write a poem about rain" (encoded, KV cached in blocks 0-5)

Output 1: "Rain falls softly..."  → shares blocks [0-5], unique blocks [6,7]
Output 2: "The clouds weep..."    → shares blocks [0-5], unique blocks [8,9]
Output 3: "Drops on glass..."     → shares blocks [0-5], unique blocks [10,11]
Output 4: "Grey skies pour..."    → shares blocks [0-5], unique blocks [12,13]

Without sharing: 4 × 6 = 24 prompt blocks

With sharing: 6 + 0 = 6 prompt blocks (4x savings on prompt!)

The shared blocks use copy-on-write: if a request ever needs to modify a shared block (doesn't happen in practice for KV cache), it copies the block first.

Prefix Caching

System prompts are identical across requests. PagedAttention can cache them:

System prompt: "You are a helpful assistant..." → blocks [0-3]

Request 1: system + "What is Python?" → shares [0-3], unique [4,5,6]

Request 2: system + "Explain Docker" → shares [0-3], unique [7,8,9]

Request 3: system + "Write a haiku" → shares [0-3], unique [10,11]

1000 concurrent users with same system prompt:

Without prefix caching: 1000 × 4 = 4000 blocks for system prompts

With prefix caching: 4 blocks total ← insane savings

Throughput Impact: The Numbers

The original vLLM paper showed dramatic improvements:

Metric HuggingFace TGI vLLM (PagedAttention) Improvement

Benchmarked on Llama 13B, A100 80GB, ShareGPT dataset.

The improvement comes entirely from better memory management — no model changes, no approximations, no quality loss.

Why More Memory = More Throughput

When KV cache wastes 65% of memory, you can only fit a few requests simultaneously. When waste drops to 4%, you fit many more requests — and the GPU stays busy with useful work instead of sitting idle.

Traditional: 80 GB GPU → 30 GB for model → 50 GB for KV cache → 35% utilized → ~17 GB useful
PagedAttention: 80 GB GPU → 30 GB for model → 50 GB for KV cache → 96% utilized → ~48 GB useful

48 / 17 = 2.8x more effective KV cache = 2.8x more concurrent requests

Continuous Batching: The Other Half

PagedAttention enables continuous batching — dynamically adding and removing requests from a batch without waiting for the longest one to finish:

Static batching (traditional):

Batch = [A(500 tokens), B(2000 tokens), C(100 tokens)]

GPU busy for 2000 tokens → A and C finish early, GPU idles for their slots

Throughput: limited by slowest request

Continuous batching (vLLM):

Step 1: Process [A, B, C]

Step 50: C finishes → immediately add D to the batch → Process [A, B, D]

Step 250: A finishes → immediately add E → Process [E, B, D]

Step 500: D finishes → add F → Process [E, B, F]

GPU never idles — always running a full batch

Without PagedAttention, continuous batching is hard — you'd need to constantly move KV cache around in memory as requests enter and leave. With paged memory, you just update the block table.

🔬

Try It Yourself

bash

Install vLLM

pip install vllm

Serve a model with PagedAttention (automatic)

python -m vllm.entrypoints.openai.api_server \

--model meta-llama/Llama-3-8B-Instruct \
    --gpu-memory-utilization 0.9 \
    --max-model-len 8192 \
    --block-size 16

Test with OpenAI-compatible API

curl http://localhost:8000/v1/completions \

-H "Content-Type: application/json" \
    -d '{
        "model": "meta-llama/Llama-3-8B-Instruct",
        "prompt": "The future of AI is",
        "max_tokens": 100,
        "temperature": 0.7
    }'

Check memory utilization

curl http://localhost:8000/metricsgrep "cache_utilization"

gpu_cache_usage_perc: 0.85 ← 85% utilized, not 35%!

🛡️

Practical Takeaways

Traditional KV cache allocation wastes 60-80% of GPU memory — pre-allocated, contiguous, mostly empty

PagedAttention uses OS virtual memory principles — pages, page tables, on-demand allocation

Waste drops from 65% to < 4% — only the last block per request has internal fragmentation

Copy-on-write enables KV cache sharing — parallel sampling and prefix caching save massive memory

vLLM builds continuous batching on top — requests enter and leave the batch dynamically

2-4x throughput improvement — same GPU, same model, same quality, just better memory management

📦

What's Next?

Episode 77: RoPE & Position Encoding — Transformers have no built-in notion of word order. "The cat sat on the mat" and "mat the on sat cat the" look identical without position information. RoPE (Rotary Position Encoding) elegantly solves this by rotating vectors — and it's the reason modern models can handle 128K+ context windows.

← Previous

Ep 75: FlashAttention

Next →

Ep 77: RoPE & Position Encoding

Next: Episode 77 — RoPE & Position Encoding

Transformers process all tokens in parallel. No left-to-right reading. So how does AI know word order? Position encoding.

This is part of a 98-episode series covering AI engineering from tokens to production deployment.