vLLM Architecture: PagedAttention and the Scheduler

The Illusion of Contiguity: How vLLM Solves Memory Fragmentation

Large Language Model (LLM) inference is often misunderstood as a compute-bound problem. In reality, for long sequences, it is a memory-bound problem dominated by the Key-Value (KV) cache. Traditional serving frameworks allocate memory for the maximum possible sequence length upfront, leading to severe fragmentation where most allocated memory sits idle. This article, Part 1 of the Production vLLM series, examines how vLLM eliminates this inefficiency through two coupled mechanisms: PagedAttention, a virtualized memory management system for the KV cache, and a Scheduler that packs requests into available physical blocks with minimal overhead.

The Cost of Static Allocation

To understand PagedAttention, one must first understand the failure mode of static allocation. In an autoregressive LLM, the model generates one token at a time. For each new token, the model must attend to all previous tokens' keys and values. This data is stored in the KV cache.

If a framework allocates memory for a sequence length of 2048 tokens for every request, but the average sequence length is 512, up to 75% of the GPU memory dedicated to KV caching may remain unused in worst-case scenarios. Conversely, if the framework allocates only what is needed, it risks running out of memory (OOM) when a sequence grows longer than expected, requiring expensive reallocation or eviction. This is the "memory fragmentation" problem: physical GPU memory is available, but it is scattered in small, unusable chunks that cannot satisfy a contiguous allocation request.

PagedAttention: Virtualizing the KV Cache

The pagedattention mechanism in vLLM applies the concept of virtual memory paging, familiar from operating systems, to the GPU's KV cache. Instead of allocating a single contiguous tensor of size [batch_size, seq_len, num_heads, head_dim], vLLM divides the KV cache into fixed-size blocks.

The Block Table

Each request is assigned a Block Table, a list of physical block IDs. A logical sequence position $i$ maps to a specific block and an offset within that block. For example, if block size is 16, tokens 0–15 reside in Block 0, tokens 16–31 in Block 1, and so on.

The critical innovation is that these physical blocks do not need to be contiguous in GPU memory. They can be scattered across the global memory space. When the attention mechanism computes, it fetches keys and values from these disparate blocks.

# Conceptual representation of Block Table
# Logical Position -> Physical Block ID
block_table = {
    "request_1": [101, 102, 103],  # 3 blocks * 16 tokens = 48 tokens max
    "request_2": [205, 206]        # 2 blocks * 16 tokens = 32 tokens max
}

This indirection allows vLLM to allocate blocks on-demand. As a sequence grows, the scheduler simply appends a new physical block ID to the request's block table. If no contiguous free memory exists, the scheduler finds any free block. This eliminates fragmentation because the allocator never needs to find a large contiguous chunk; it only needs to find individual blocks.

Attention Kernel Implementation

The PagedAttention kernel modifies the standard attention mechanism to handle this non-contiguous memory layout. Instead of reading from a single contiguous buffer, the kernel:

1. Takes the block table as input.
2. For each query token, calculates the physical address of its corresponding key and value blocks.
3. Reads the data, handling potential cache misses across block boundaries.

This operation is computationally cheap because the memory access pattern remains coalesced within each block, and the overhead of indirection is negligible compared to the arithmetic intensity of the attention computation.

The Scheduler: Packing Requests into Blocks

PagedAttention provides the mechanism for flexible memory usage, but the llm scheduler determines which requests get memory and when. The scheduler’s primary job is to pack as many requests as possible into the available GPU memory blocks without causing OOM errors.

vLLM supports two scheduling policies, each optimizing for different trade-offs between throughput and latency:

1. First-Come-First-Served (FCFS)

The default policy. Requests are scheduled in the order they arrive. The scheduler checks if the next request can fit into the remaining free blocks. If yes, it allocates blocks from the pool. If no, the request waits. This policy maximizes throughput because it keeps the GPU busy with as many active requests as possible, but it can lead to latency spikes if a large request blocks smaller ones.

2. Priority Scheduling

Requests are assigned priorities. Higher-priority requests are scheduled before lower-priority ones. This is useful for multi-tenant environments where certain users or tasks have SLA requirements. The scheduler still respects the block capacity constraints, but it may preempt lower-priority requests to make room for higher-priority ones.

Preemption: The Safety Valve

The most sophisticated aspect of the scheduler is preemption. If the GPU is full and a new high-priority request arrives, the scheduler can forcibly evict lower-priority requests from the KV cache.

The block manager coordinates this process by tracking which physical blocks belong to which requests. When a request is preempted:

1. Its physical blocks are returned to the free pool.
2. The request’s state is saved to CPU memory (or disk, depending on configuration).
3. The request is moved to a "waiting" queue.
4. Once the new request finishes or releases memory, the preempted request is restored to GPU memory and resumed.

This ensures that the system never crashes due to OOM, but it introduces latency overhead for preempted requests. The scheduler must balance the cost of preemption (context switch, data transfer) against the benefit of admitting new requests.

Why This Matters for Infrastructure

For ML engineers, understanding this architecture clarifies why vLLM outperforms traditional frameworks like HuggingFace Transformers or TensorRT-LLM in long-sequence scenarios. The gain is not in the speed of matrix multiplication, but in the density of request packing. By treating the KV cache as a pageable resource, vLLM allows you to serve more concurrent users with the same GPU hardware.

However, this introduces complexity. Engineers must tune the gpu_memory_utilization parameter, which controls the fraction of GPU memory reserved for the KV cache. Setting it too high increases the risk of preemption storms; setting it too low underutilizes the GPU. Understanding the block size (default 16) and the scheduler policy is essential for optimizing production deployments.

Conclusion

vLLM’s architecture effectively applies OS concepts to deep learning infrastructure. PagedAttention solves the memory fragmentation problem by virtualizing the KV cache, allowing non-contiguous memory allocation. The Scheduler leverages this flexibility to pack requests efficiently, using preemption as a last resort to maintain stability. Together, these mechanisms enable high-throughput LLM serving that scales linearly with batch size, rather than being bottlenecked by static memory allocation.