The first time we load-tested vLLM for a multi-tenant embedding-and-completion service, we watched nvidia-smi and assumed something was leaking. Four Mistral-7B instances on two A100s, steady 512-token requests, and the KV cache was consuming 11GB out of the 80GB we’d left after weights. Every generation step the kv_cache pool grew, and around 42 concurrent requests we started seeing CUDA out of memory despite gpu_memory_utilization set to 0.85. That was the moment we stopped treating KV cache as an implementation detail and started treating it as the resource the scheduler actually manages.

The math is unforgiving. A single token needs 2 * n_layers * n_kv_heads * head_dim * dtype_size bytes per request. For Llama-3-8B with GQA (8 KV heads, head_dim 128, fp16) that’s about 8KB per token. An 8K-token context holds 64MB of cache per request; 512 such requests is 32GB of VRAM before a single token is generated. Pre-PagedAttention frameworks sized this as one contiguous buffer per request at max length, so a 256-token request reserved space for 32K tokens. NVIDIA’s earlier numbers and our own runs both put that fragmentation waste at 60–80% of the KV pool.

PagedAttention fixes this by making memory the unit of scheduling, not the sequence. The KV cache is carved into fixed 16-token blocks. Each request has a logical page table mapping token positions to physical blocks; the decoder only allocates the next physical block when the current one fills. Two things follow that are worth internalizing because everything downstream depends on them:

1. The number of free blocks, not the batch size, is the concurrency governor. Your true capacity is gpu_memory_utilization * free_memory / (block_size * bytes_per_token) blocks. Everything else — prefill, scheduling, eviction — is an argument over who owns blocks.
2. A block is the unit of sharing. A prompt prefix shared across 30 requests occupies one physical block set once, not 30 times. vLLM’s radix cache keys blocks by content hash precisely so this works, and it’s the reason a RAG prompt template with a stable system prefix gets cached and the per-doc suffix doesn’t.

The scheduler looks roughly like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class BlockManager:
    def __init__(self, num_gpu_blocks, block_size=16):
        self.free = set(range(num_gpu_blocks))
        self.block_size = block_size
        self.tables: dict[str, list[int]] = {}   # request_id -> physical blocks

    def can_allocate(self, request_id: str, num_tokens: int) -> bool:
        needed = (num_tokens + self.block_size - 1) // self.block_size
        return len(self.free) >= needed

    def allocate(self, request_id: str, num_tokens: int) -> list[int]:
        needed = (num_tokens + self.block_size - 1) // self.block_size
        blocks = []
        while len(blocks) < needed and self.free:
            blocks.append(self.free.pop())
        self.tables[request_id] = blocks
        return blocks

    def free_request(self, request_id: str) -> None:
        self.free.update(self.tables.pop(request_id, []))

Once blocks are the unit of allocation, eviction becomes a real scheduling policy rather than “drop the oldest sequence.” The eviction order we run in production:

• Finished requests first. Sounds trivial, but max_num_seqs was inflating TTFT because a finished request’s blocks weren’t reclaimed until the next scheduling step. Reclaim on decode completion cut p95 TTFT by 18%.
• Longest-idle prefix blocks before live sequence blocks. When the radix cache needs space, evict least-recently-used internal nodes; never touch blocks backing an in-flight generation.
• Swap to CPU only as a pressure valve. The swap queue moves idle-sequence blocks to pinned host memory. It saves us from OOM but it is not free: swap-in during a prefill is the single biggest tail-latency event we see, pushing p99 time-to-first-token from 220ms to 1.9s when it kicks in under load.

The numbers that justify all of this from our 2024–2025 runs (vLLM 0.6–0.8, 8×A100, mixed Llama-3-8B / Qwen2.5-72B traffic): with PagedAttention we held 1.4x higher sustained throughput at 4x lower p99 latency than the contiguous-buffer baseline we ran it against, and gpu_memory_utilization=0.90 with a 1% idle-request swap budget let us serve 1,120 concurrent 2K-token requests on an 8-GPU node without a single OOM over a 48-hour soak.

Three operational rules from that soak:

• Set gpu_memory_utilization to 0.90–0.95 only after profiling CUDA contexts. For the 8B model the kernels/context overhead was ~6%; for the 72B it was ~9%. Anything above those ceilings and the allocator starts evicting weights, and performance collapses non-linearly.
• Alert on swap_in/swap_out token counters, not on “swap present.” A steady trickle is normal; a burst above a few hundred tokens per second is a sign your block pressure is wrong and your TTFT distribution is about to fork.
• Keep enable_prefix_caching on, but rehash the prompt template weekly. We once shipped a system prompt with a UUID in it, silently disabling radix hits on 40% of traffic for three days before we noticed throughput dipped.

PagedAttention didn’t make KV cache cheap — it made it accountable. Once every byte is a block that a scheduler can count, allocate, share, and evict, you can reason about serving capacity the way you reason about a memory allocator: with numbers, not vibes.