In the early days of the Large Language Model (LLM) explosion—think late 2022 and early 2023—we were all collectively obsessed with model weights. We talked about parameter counts like they were horsepower: 7B, 13B, 70B, 175B. But as engineering teams moved from "Look, it can write a poem!" to "We need to serve 10,000 concurrent users without going bankrupt," the conversation shifted abruptly.
We hit a wall. And it wasn't a compute wall; it was a memory wall.
If you've ever tried to host a Llama 3 or Mistral instance on a cluster of A100s or H100s, you’ve likely stared at a dashboard in frustration. Your GPU utilization is hovering at a measly 20-30%, but your system is refusing new requests because it's "out of memory." This paradox—being compute-idle but memory-starved—is the dragon that PagedAttention and Continuous Batching were designed to slay.
Today, we’re going deep into the stack. We’re going to look at why traditional LLM serving was fundamentally broken and how the engineers at UC Berkeley (and the vLLM team) borrowed a 50-year-old concept from Operating Systems to revolutionize AI infrastructure.
The KV Cache: The Trillion-Dollar Bottleneck
To understand the solution, we have to respect the problem. In an autoregressive transformer, generating a token is not a one-shot deal. To generate token $N$, the model needs to look at tokens $1$ through $N-1$.
Mathematically, this happens through the Attention mechanism. As the model processes each token, it generates Key (K) and Value (V) tensors. These tensors are stored in the "KV Cache" so that the model doesn't have to recompute them for every single new token in a sequence.
Here is the engineering reality: The KV cache is massive. For a model like Llama-2-7B, stored in FP16, the KV cache requires:
2 (K and V) * 2 (bytes) * layers * num_heads * head_dimper token.- For a single request with a 2048 context length, you're looking at roughly 1GB to 2GB of VRAM just for the cache of one user.
If you have an 80GB A100, you’d think you could fit 40-80 users. But in the "old" way of doing things, you’d be lucky to fit 10. Why? Fragmentation and Over-provisioning.
The "Static" Sin
Before PagedAttention, we used static memory allocation. When a request came in, the server would ask: "What is the maximum length this request could be?" If the max length was set to 2048, the server would reserve a contiguous block of VRAM for 2048 tokens immediately.
There were three types of waste here:
- Internal Fragmentation: The request might only actually generate 100 tokens, but we reserved space for 2048. That 1948-token space is dead air.
- Reservation Waste: Even if we eventually use the space, it sits empty while the model is still generating the first few tokens.
- External Fragmentation: Small gaps between large contiguous blocks that are too small to fit any new request, even though the total free memory is high.
This inefficiency meant that up to 60-80% of VRAM was wasted. This is the technical equivalent of booking an entire hotel floor because you might invite some friends later, while people are queuing out the door in the rain.
Enter PagedAttention: The OS Philosophy Applied to AI
The breakthrough of PagedAttention (introduced by the vLLM paper) was the realization that we don't need the KV cache to be contiguous in physical memory.
In a traditional Operating System, we use Virtual Memory. Your RAM is divided into "pages," and a "page table" maps a process's logical address space to physical frames in RAM. PagedAttention brings this exact architecture to the GPU.
How it Works Under the Hood
Instead of one giant block, PagedAttention divides the KV cache for each sequence into small, fixed-size blocks. Each block can hold the KV tensors for a fixed number of tokens (e.g., 16 tokens).
- The Logical View: The model thinks it’s writing to a continuous sequence of tokens.
- The Physical View: The blocks are scattered all over the VRAM, wherever there was a free "slot."
- The Block Table: A mapping layer that tracks which logical tokens are stored in which physical blocks.
When the model needs to perform the attention calculation for a new token, the PagedAttention kernel fetches these non-contiguous blocks on the fly.
# A simplified conceptual look at the Block Table structure
block_table = {
"request_id_1": [physical_block_7, physical_block_12, physical_block_2],
"request_id_2": [physical_block_5, physical_block_1],
}
Why this is a "Holy Grail" moment:
Because blocks are fixed-size and mapped dynamically, internal fragmentation is limited to the very last block of a sequence. For a block size of 16, the average waste is only 8 tokens.
Suddenly, your memory utilization jumps from 20% to near 100%. You can now pack 4x to 5x more requests into the same GPU. This isn't just a minor optimization; it changes the unit economics of AI businesses.
Continuous Batching: Ending the "Waiting for the Slowest" Problem
While PagedAttention solved the memory problem, we still had a scheduling problem.
Traditional batching (often called Static Batching) works like a bus. The bus waits at the station until it's full (or a timer hits), then it drives to the destination. If one passenger (a request) wants to go 100 miles, and everyone else wants to go 5 miles, the bus can't pick up new passengers until the 100-mile passenger is dropped off and the bus returns to the station.
In LLM terms: If you batch 8 requests together, and 7 of them finish in 10 tokens, but 1 of them takes 500 tokens, the 7 "finished" slots sit idle and useless until that last request is done. This is called tail latency bottleneck.
Iteration-Level Scheduling
Continuous Batching (pioneered by the Orca paper and implemented in vLLM and TGI) changes the "bus" into a "moving walkway."
Instead of waiting for the entire batch to finish, the scheduler operates at the iteration level. After every single token generation step (one "pass" through the model), the scheduler looks at the queue:
- Did any request finish? Kick it out.
- Is there room for a new request? Pull it in.
By inserting new requests into the batch "mid-flight," the GPU remains constantly saturated.
The Orchestration Challenge
Implementing this is an engineering nightmare. You have to manage:
- The Prefill Phase: Taking a new user's long prompt and processing it all at once to get the initial KV cache. This is compute-bound and uses high-throughput kernels.
- The Decode Phase: Generating one token at a time for existing requests. This is memory-bandwidth bound.
A modern serving engine like vLLM or TensorRT-LLM has to balance "Prefills" and "Decodes" in the same batch. If you take too many new requests (prefills), you'll starve the existing users and their "Time Per Output Token" (TPOT) will spike. If you take too few, your "Time To First Token" (TTFT) will suffer.
The Infrastructure Impact: Scale and Complexity
When you combine PagedAttention and Continuous Batching, the infrastructure requirements for serving LLMs shift from "standard web serving" to "high-performance distributed systems."
1. The Block Manager
The Block Manager is now the "brain" of your inference server. It manages a physical pool of memory. When the scheduler wants to add a request, it asks the Block Manager: "Do I have enough free blocks to handle the initial prompt and at least $N$ tokens of generation?"
If memory runs low, the Block Manager has to implement Eviction Policies. It might "preempt" a request (stop it, save its state, and resume later) or even swap blocks from GPU VRAM to CPU RAM—reminiscent of "swap space" in Linux.
2. Distributed PagedAttention
When a model is too big for one GPU (e.g., Llama-3-70B requires ~140GB in FP16), we use Tensor Parallelism. Now, the PagedAttention mechanism has to stay synchronized across multiple GPUs. Each GPU stores a portion of the "Heads" of the KV cache, but they all must agree on the block mapping.
3. Sharing is Caring: Prefix Caching
One of the most elegant features enabled by PagedAttention is Automatic Prefix Caching.
Imagine you’re building a coding assistant. Every request includes a massive 4,000-token "system prompt" describing the codebase. In the old world, you’d store that 4,000-token KV cache separately for every single user. With PagedAttention, because memory is just a collection of blocks, the system can recognize that the first 250 blocks (4,000 tokens) are identical for every user. It simply points every request’s Block Table to the same physical blocks in VRAM.
Memory savings: Infinite. You only store the system prompt once, no matter how many users are active.
Show Me The Code: A Conceptual PagedAttention Kernel
While the actual CUDA kernels for PagedAttention are hundreds of lines of optimized C++, we can visualize the logic. The core idea is that the attention operation must now perform a "look-up" per block rather than a simple pointer increment.
// Conceptual pseudo-code for a PagedAttention Kernel
__global__ void paged_attention_kernel(
float* out, // Output buffer
float* query, // Query tensor for the current token
float* key_cache_pool, // Giant pool of all physical K-blocks
int** block_table, // Mapping: [request_id][logical_block_idx] -> physical_block_id
int block_size // e.g., 16
) {
int tid = threadIdx.x;
int req_id = blockIdx.x;
// Instead of iterating over a contiguous array,
// we iterate over the block table.
for (int logical_idx = 0; logical_idx < num_blocks_this_req; ++logical_idx) {
int physical_block_id = block_table[req_id][logical_idx];
// Load the key/value data from the specific physical block
float* k_block = key_cache_pool + (physical_block_id * block_size);
// Perform dot-product attention...
// ... (standard attention math here)
}
}
The magic is in the block_table lookup. This adds a tiny bit of overhead (memory indirection), but it is dwarfed by the massive gains in throughput and the reduction in VRAM pressure.
The Performance Hype vs. Reality
When vLLM first dropped, the benchmarks were staggering: 24x higher throughput than standard HuggingFace Text Generation Inference (TGI) at the time.
But as with all things in engineering, there are trade-offs.
The Latency/Throughput Trade-off
Continuous batching maximizes throughput (total tokens generated per second across all users). However, if you saturate your GPU to 95% utilization, individual latency (how fast one person gets their tokens) will go up.
In a saturated system:
- TTFT (Time to First Token) increases because new prompts have to wait for a "slot" in the continuous batch.
- TPOT (Time Per Output Token) increases because the GPU is context-switching and managing more memory traffic.
Modern engineering teams spend most of their time tuning the "Scheduler Policy." Do you prioritize the user who has been waiting longest? Or do you prioritize the user who is almost finished to free up their memory blocks faster?
Why This Matters for the Future of AI
The significance of PagedAttention and Continuous Batching cannot be overstated. They represent the transition of LLM serving from "research code" to "industrial-grade infrastructure."
- Cost Reduction: By increasing throughput by 5x-10x, the cost per request drops by 80-90%. This is what makes $20/month unlimited ChatGPT-style subscriptions viable.
- Long Context Windows: As we move toward 128k and 1M token contexts, managing the KV cache becomes the primary engineering challenge. You simply cannot handle long-context models without a paging-style memory manager.
- Real-time Interactivity: Continuous batching allows for much more responsive "streaming" of tokens, which is essential for the "feel" of AI agents.
The Next Frontier: Speculative Decoding and Beyond
We are already seeing the next layer of this stack. Speculative Decoding (where a tiny model guesses the next 5 tokens and a big model verifies them in one go) is being integrated directly into PagedAttention schedulers.
When you combine a PagedAttention memory manager, a Continuous Batching scheduler, and Speculative Decoding, you get a system that is orders of magnitude faster than what we had just 18 months ago.
Final Thoughts
The story of PagedAttention is a classic engineering lesson: The most "cutting edge" problems often have "old school" solutions.
We didn't need a new branch of mathematics to fix LLM throughput. We needed the 1960s philosophy of virtual memory and paging. By decoupling the logical sequence of a conversation from the physical constraints of HBM (High Bandwidth Memory), we've turned GPUs from rigid, wasteful engines into fluid, dynamic compute pools.
If you’re building or deploying LLMs today, you aren't just managing models; you're managing memory. And in the world of high-scale inference, the block is the new unit of currency.