Inside vLLM Architecture: How PagedAttention and Continuous Batching Solved the KV Cache Crisis

Executive Summary: The Memory Wall in Generative AI

The exponential growth of Large Language Model (LLM) serving in production infrastructure has collided head-on with a physical constraint: the GPU Memory Wall. While model training is predominantly compute-bound, LLM inference during autoregressive generation is strictly memory-bandwidth and capacity bound.

In early serving frameworks like vanilla Hugging Face Transformers, enterprise deployments routinely squandered 60% to 80% of GPU High-Bandwidth Memory (HBM) on internal and external memory fragmentation within the Key-Value (KV) cache. Because output sequence lengths cannot be predicted in advance, systems pre-allocated contiguous memory blocks sized to the maximum context window (e.g., 4K or 8K tokens), preventing additional requests from batching together on multi-GPU nodes.

The development of vLLM—originating from UC Berkeley’s Sky Computing Lab and published at SOSP 2023—fundamentally transformed LLM serving economics. Inspired by operating system virtual memory paging, vLLM introduced PagedAttention: an attention algorithm that stores continuous keys and values in non-contiguous physical memory blocks managed by dynamic block tables.

+-----------------------------------------------------------------------------------------+
|                              THE LLM INFERENCE MEMORY SHIFT                             |
+-----------------------------------------------------------------------------------------+
|    TRADITIONAL STATIC KV ALLOCATION               vLLM PAGEDATTENTION ALLOCATION        |
|  +--------------------------------+             +------------------------------------+  |
|  | Request 1: [Tokens][UNUSED...] |             | Block Table:                       |  |
|  | (Pre-allocated 4K Tokens)      |             | [Block 0] -> Physical Frame #14    |  |
|  +--------------------------------+             | [Block 1] -> Physical Frame #02    |  |
|  | Request 2: [Tokens][UNUSED...] |             | [Block 2] -> Physical Frame #89    |  |
|  | (Pre-allocated 4K Tokens)      |             +------------------------------------+  |
|  +--------------------------------+                               |                     |
|  |  60% - 80% VRAM WASTED!        |                               v                     |
|  |  - Internal Fragmentation      |             +------------------------------------+  |
|  |  - External Memory Gaps        |             | Physical GPU Memory Pool:          |  |
|  |  - Severe Concurrency Limits   |             | [Frame #02][Frame #14][Frame #89]  |  |
|  +--------------------------------+             | <4% Memory Fragmentation Waste!    |  |
|       Batch Size Capped at 4-8                  | High Concurrency: Batch Size 32-64 |  |
+-----------------------------------------------------------------------------------------+

Coupled with Continuous Batching (Iteration-Level Scheduling), Prefix Caching, and Chunked Prefill, vLLM slashes memory waste to under 4%, unlocking 2x to 4x throughput improvements across enterprise clusters.

---

Technical Mechanics: The KV Cache Memory Bottleneck

During transformer generation, each token generated attends to all previous tokens in the sequence. To avoid recomputing attention vectors of past tokens at every generation step, the model caches Key and Value projection vectors in GPU VRAM:

$$\text{KV Cache Size per Token} = 2 \times 2 \times n_{\text{layers}} \times n_{\text{heads}} \times d_{\text{head}} \times b_{\text{bytes}}$$

For a typical 70-billion parameter model (such as Llama-3-70B using 80 layers, 8 Key/Value heads via Grouped-Query Attention, and a head dimension of 128 in FP16 precision):

$$\text{KV Cache per Token} = 2 \times 2 \times 80 \times 8 \times 128 \times 2 = 655,360 \text{ bytes} \approx 640 \text{ KB per token}$$

A single sequence with an 8,192 token context window requires over 5.24 GB of VRAM per concurrent user.

Why Static Allocation Paralyzed Inference Systems

Prior to vLLM, memory allocators suffered from two structural pathologies:

1. Internal Fragmentation: Because generation lengths are unknown upfront, engines reserved space for the maximum context limit. If the user's prompt and completion totaled only 500 tokens, the remaining 7.5K token capacity sat idle, blocking other queries.
2. External Fragmentation: Memory allocators like PyTorch's native caching allocator require contiguous physical memory chunks. As requests of variable lengths completed, memory became fragmented, causing allocation failures even when free VRAM was technically available.

---

Architectural Anatomy: PagedAttention Virtual Memory Paging

PagedAttention solves this by adapting Virtual Memory Paging to the GPU tensor domain.

                           PAGEDATTENTION ARCHITECTURAL PIPELINE
+----------------------------------------------------------------------------------------------------+
|                                    Logical Token Sequence                                          |
|                [Token 0 ... Token 15] [Token 16 ... Token 31] [Token 32 ... Token 47]              |
|                     Logical Block 0        Logical Block 1        Logical Block 2                  |
+----------------------------------------------------------------------------------------------------+
                                                  |
                                                  v
+----------------------------------------------------------------------------------------------------+
|                                     Virtual Block Table                                            |
|                        Maps Logical Blocks to Non-Contiguous Physical Frames                       |
|                             { Block 0: #14, Block 1: #02, Block 2: #89 }                           |
+----------------------------------------------------------------------------------------------------+
                                                  |
                                                  v
+----------------------------------------------------------------------------------------------------+
|                                 Physical GPU HBM Memory Pool                                       |
|  [Frame #00] [Frame #01] [Frame #02 (LB 1)] [Frame #03] ... [Frame #14 (LB 0)] ... [Frame #89 (LB 2)]|
+----------------------------------------------------------------------------------------------------+
                                                  |
                                                  v
+----------------------------------------------------------------------------------------------------+
|                              Custom PagedAttention CUDA Kernel                                     |
|             (Gathers non-contiguous Key/Value vectors on-the-fly during Attention QK^T)            |
+----------------------------------------------------------------------------------------------------+

The Block Table Mapping Subsystem

1. Physical Blocks: vLLM divides GPU KV cache memory into fixed-size physical blocks (typically storing 16 tokens).
2. Logical Blocks: Prompt and generated tokens are structured as logical block streams.
3. On-Demand Allocation: When a new token is generated, vLLM allocates blocks dynamically from a global free-list and updates the sequence's Block Table.

# Conceptual Python representation of PagedAttention block table lookup
class PagedKVCacheManager:
    def __init__(self, block_size: int = 16, num_physical_blocks: int = 10000):
        self.block_size = block_size
        self.free_blocks = list(range(num_physical_blocks))
        self.block_tables = {}

    def allocate_slot(self, request_id: str, seq_len: int) -> int:
        logical_block_idx = seq_len // self.block_size
        block_offset = seq_len % self.block_size

        if request_id not in self.block_tables:
            self.block_tables[request_id] = []

        if block_offset == 0:
            physical_block_id = self.free_blocks.pop(0)
            self.block_tables[request_id].append(physical_block_id)
            
        return self.block_tables[request_id][logical_block_idx]

CUDA Shared Memory Optimization in PagedAttention

At the hardware execution level, standard multi-head attention computes dot products across contiguous arrays in GPU High-Bandwidth Memory (HBM). Because HBM accesses incur substantial latency (several hundred clock cycles), standard implementations rely on SRAM shared memory inside Streaming Multiprocessors (SMs) to stage tiles of Query, Key, and Value matrices.

PagedAttention achieves near-peak memory bandwidth efficiency by reorganizing how thread warps fetch KV blocks:

• Block-Level Memory Coalescing: Each physical block of 16 tokens is mapped into a 128-byte aligned structure. When a thread warp fetches Key vectors for a block, memory requests are coalesced into minimal 32-byte memory transactions.
• Dynamic Warp Resharding: Different warps within a thread block compute attention scores over distinct physical blocks in parallel, writing partial softmax reductions into SM shared memory before executing a final normalized reduction across blocks.
• Prefix Caching via Radix Trees: For agentic workflows sharing massive system prompts, vLLM constructs a prefix tree (Radix Tree) of block hashes. When a new prompt arrives, the scheduler hashes token chunks and traverses the tree. Matching blocks are referenced directly via pointer increments in the block table, eliminating redundant prefill computation entirely.

By eliminating contiguous memory requirements, memory waste drops to under 4%.

---

Continuous Batching: Iteration-Level Scheduling

Classical serving engines operated on Static Batching: holding a batch until the slowest sequence completed. Because output lengths vary, static batching created massive scheduling bubbles where GPU cores sat idle waiting on outlier requests.

STATIC REQUEST-LEVEL BATCHING (Massive Idle Waste):
Req 1 (20 tokens):  [====================]
Req 2 (500 tokens): [==================================================]
Req 3 (50 tokens):  [=========================]
                     ^
                     |--- Huge Idle GPU Bubbles! All slots locked waiting for Req 2 ---|

vLLM CONTINUOUS (ITERATION-LEVEL) BATCHING:
Iteration N:   [Req 1 Step 20 - FINISHED!] ===> Evicted immediately!
Iteration N+1: [Req 4 ADMITTED!] (Fills empty slot instantly!)
Iteration N+2: [Req 3 Step 50 - FINISHED!] ===> Evicted immediately!
Iteration N+3: [Req 5 ADMITTED!] (Fills empty slot instantly!)
Result: GPU operates at 100% saturation; zero compute cycles wasted!

vLLM re-evaluates workloads at every single decode step. When a sequence generates an <EOS> token, its memory blocks return to the free-list, and a queued request is admitted instantly.

---

Empirical Benchmarks & Production Performance

Benchmarking Llama-3-70B-Instruct across an 8x NVIDIA H100 SXM cluster demonstrates massive throughput gains:

vLLM delivers a 3.4x throughput increase over baseline frameworks while slashing tail latency.

---

Cluster Architecture & Production Deployment Playbook

1. Production vLLM Startup Configuration

# Launch vLLM OpenAI-Compatible Server for Llama-3-70B
vllm serve meta-llama/Meta-Llama-3-70B-Instruct \
    --tensor-parallel-size 4 \
    --max-model-len 8192 \
    --gpu-memory-utilization 0.92 \
    --block-size 16 \
    --enable-prefix-caching \
    --enable-chunked-prefill \
    --max-num-seqs 256 \
    --dtype bfloat16 \
    --port 8000

2. Tuning Chunked Prefill for Smooth Streaming

Enabling Chunked Prefill splits large prompts into token chunks (e.g., 2,048 tokens), interleaving prompt processing with active decode steps to eliminate Inter-Token Latency (ITL) spikes:

--enable-chunked-prefill \
--max-num-batched-tokens 4096

3. Monitoring VRAM Telemetry

curl -s http://localhost:8000/metrics | grep -E "vllm:num_requests_running|vllm:gpu_cache_usage_factor"

---

Semantic FAQ Section

How does PagedAttention reduce GPU memory waste?

Traditional serving frameworks pre-allocate contiguous memory for maximum sequence lengths, wasting 60% to 80% of VRAM on ungenerated tokens. PagedAttention treats GPU memory like operating system virtual memory, breaking the KV cache into fixed-size physical blocks (e.g., 16 tokens) allocated dynamically on demand, which reduces memory waste to under 4%.

What is continuous batching and how does it differ from dynamic batching?

Dynamic batching groups requests arriving within a short time window and executes them until all sequences complete, leaving GPU cores idle as shorter sequences finish early. Continuous batching (iteration-level scheduling) operates at every token generation step, evicting completed sequences immediately and admitting new waiting requests without pause.

What is prefix caching in vLLM?

Prefix caching allows the inference engine to retain the KV cache blocks of shared prompt prefixes (such as complex system prompts, few-shot examples, or document context in RAG applications) in physical GPU memory. Subsequent requests sharing the same prefix reuse the pre-computed blocks, slashing Time to First Token (TTFT) by over 80%.

Does PagedAttention change the mathematical output of the LLM?

No. PagedAttention is an exact attention algorithm, not an approximation. It alters only where and how Key and Value vectors are addressed in physical memory, yielding identical token outputs to standard multi-head attention.

What is Chunked Prefill and why is it important for interactive chat?

Processing massive input prompts requires substantial compute and can block the GPU for hundreds of milliseconds, delaying token delivery for concurrent chat users. Chunked prefill divides large prompts into smaller batches and interleaves them with active token decode steps, maintaining low and predictable inter-token latency across all streams.