PagedAttention — What If Your GPU Memory Managed Itself Like an Operating System.

You launch an LLM serving endpoint. Your GPU has 80GB of memory. The model weights take maybe 26GB. You'd expect the rest — over 50GB — to go toward serving as many concurrent users as possible. Instead, your throughput is terrible, half your requests are queued, and a memory profiler shows something strange: most of that "free" 50GB isn't actually holding any data. It's just reserved. Sitting there. Empty. On purpose.

That's not a bug. That's how every LLM serving system worked before September 2023. And the reason is almost comically simple once you see it — which is exactly the kind of problem operating-systems researchers love, and exactly the kind of problem a group at UC Berkeley decided to go solve by stealing an idea that's older than the GPU itself.

The problem: memory reserved for a future that might not happen.

When a transformer generates text, it doesn't want to recompute attention over the entire conversation at every single step — that would be quadratically expensive and get slower with every token. So it caches the key and value vectors it already computed, at every layer, at every attention head, for every token so far. This is the KV cache, and for any request that's more than a couple hundred tokens long, it is usually the single largest thing sitting in GPU memory — bigger, per request, than you'd guess, and it keeps growing for as long as the request keeps generating.

Here's the part that turns this from "big" into "a systems crisis." Nobody knows in advance how long any given request is going to run. Maybe it stops after 40 tokens. Maybe it goes to 4,000. The old way of dealing with that uncertainty — used by HuggingFace's default serving path, FasterTransformer, and Orca alike — was to just reserve memory for the worst case: allocate one big contiguous slab of memory sized for the model's maximum context length, for every request, the moment it arrives. If the model supports 4096 tokens, you reserve 4096 tokens' worth of KV cache — whether the request ends up using 40 tokens of it or all 4096.

Researchers at UC Berkeley, working with Stanford and ICSI, measured exactly how bad this gets in production-style serving systems. The number is not subtle: 60% to 80% of allocated KV cache memory was never used. Reserved, blocked off, unavailable to any other request — and empty.

Imagine a hotel that, the moment any guest checks in, locks an entire wing of rooms in case they decide to stay for a year — even if 90% of guests check out after two nights. The hotel isn't full. It just looks full, because it reserved space for guests who never show up.

Two very specific kinds of waste.

The paper doesn't just say "wasted memory" and move on — it names the waste using the same vocabulary operating-systems textbooks have used for fifty years, because it's the same problem.

Internal fragmentation is memory allocated to a request that the request itself never uses. Reserve 4096 tokens, generate 300, and 3796 tokens' worth of memory sat locked to that one request for its entire life, unusable by anyone else, even though it was always empty.

External fragmentation is the second, sneakier kind. Even memory that legitimately gets freed — a request finishes, its slab is released — leaves behind an irregularly-sized hole. A new request that needs a different amount of memory might not fit cleanly into any existing hole, even though the total free memory across all the holes combined would be more than enough. The problem isn't "not enough memory." It's "the free memory is the wrong shape."

And this isn't a cosmetic inefficiency — it's the actual ceiling on how many users you can serve. Concurrent request capacity is bounded by how many KV caches fit in GPU memory at once. If 70% of that memory is empty reservation, you're serving less than a third of the users you could be, on the exact same hardware.

The big idea: steal it from the operating system.

Here's where the paper gets its name, and where the insight becomes obvious in hindsight — always the sign of a good one. Operating systems solved this exact shape of problem decades ago. A process needs memory of an unpredictable, growing size. You don't want to reserve a huge contiguous block up front (wasteful), and you don't want processes to fight over irregular gaps in physical RAM (fragmentation). The answer the OS world landed on, ages ago, is virtual memory paging: chop memory into small, fixed-size pages, let a process believe its memory is one tidy contiguous block, and quietly scatter the real, physical pages anywhere in RAM — tracked by a page table that translates one view into the other.

PagedAttention does the identical thing to the KV cache:

• Split the KV cache into fixed-size blocks — 16 tokens each, by default.
• Store those blocks anywhere in GPU memory — never require them to sit next to each other.
• Give each sequence a block table — the "page table" — mapping its logical block order (block 0, block 1, block 2…) to wherever the actual physical block lives.
• Allocate a new block only when a sequence has actually generated enough tokens to need one. Never allocate for a hypothetical future.

The effect on waste is immediate and almost embarrassingly clean. Internal fragmentation is now capped at a single, partially-filled block — at most 15 empty token-slots out of a 16-slot block, never thousands. Measured waste drops from 60–80% down to under 4%. External fragmentation basically vanishes too, because every block is the identical size — any free block, from any previous request, can satisfy any new request's next allocation. There's no such thing as "a hole the wrong shape" anymore, because every hole is the same shape.

It's not a new idea. It's the oldest idea in memory management, applied to a brand-new place nobody had pointed it at yet.

The hard part: attention math over scattered memory.

Chopping storage into blocks is the easy half. The genuinely hard systems problem — the part that makes this a real contribution and not just "use a hash map" — is that attention itself now has to read from memory that refuses to sit still. A normal attention kernel assumes it can point at one flat tensor and stream straight through it. PagedAttention's kernel instead has to, for every single query, walk the block table, chase down wherever each logical block's physical block actually lives, fetch it, accumulate that block's contribution to the attention score — and repeat for the next block, which could be anywhere else in memory entirely.

scores = []
for logical_idx, physical_idx in enumerate(block_table):
    k_block = kv_pool.K[physical_idx]      # fetch wherever it actually lives
    scores.append(query @ k_block.T)       # partial attention scores

scores = softmax(concat(scores))           # normalize over ALL positions, as usual

output = 0
for logical_idx, physical_idx in enumerate(block_table):
    v_block = kv_pool.V[physical_idx]
    output += scores[logical_idx] @ v_block

The trade is the same one operating systems have always made: pay a small, bounded indirection cost per memory access, in exchange for eliminating a much larger structural waste. vLLM's real kernel fuses the block-table lookup directly into the same pass that does the score computation and the weighted sum, so in practice the overhead is small relative to what you gain from fitting dramatically more concurrent sequences into the same GPU.

The scheduler that makes blocks worth having.

A paged memory manager is only half the system. The other half is the scheduler, and vLLM's is built specifically to exploit what paging just made possible. Older serving systems used static batching: a batch of requests starts together, and the whole batch runs until the slowest member finishes — even if every other request in that batch finished five steps ago and its GPU slot has just been sitting idle since.

vLLM instead does iteration-level scheduling: a fresh decision, every single forward pass, about which sequences continue, which just finished (and free their blocks immediately), and which brand-new requests get admitted into whatever capacity just opened up. This only works cleanly because of paging — if memory were still one big contiguous reservation, freeing a finished sequence and immediately handing that space to a differently-sized new arrival would run straight back into the fragmentation problem. Because every block is uniform, any freed block fits any new request instantly. Paged memory and fine-grained scheduling are a matched pair; you need both to actually cash in the throughput gain.

The part that surprised me: sharing memory for free.

Here's the detail that elevates this from "a good fix for waste" to "a genuinely clever systems design." Because a block table is just a mapping — exactly like a page table — nothing stops multiple sequences from pointing at the same physical block.

The clean example: parallel sampling — one prompt, several independent completions requested at once (generate 4 candidate answers, pick the best one). Every completion shares the identical prompt, so their KV cache for those prompt tokens is identical too. Instead of duplicating that memory once per completion, every completion's block table can point at the same physical blocks for the shared prefix, with a reference count tracking how many logical blocks currently point at each physical block.

The catch: once generation starts, each completion diverges and appends its own new tokens. If two completions shared a block and one just wrote a new token into it, it would silently corrupt the other completion's cache. The fix, again lifted straight from operating systems: copy-on-write. Reading a shared block is free — no copy needed. The instant a sequence needs to write into a block that's currently shared, the memory manager makes a private copy of just that one block for the writer, decrements the original's reference count, and every other sequence sharing the original block never even notices.

The same trick handles beam search, where candidate beams share a common ancestor path and only diverge at branch points, and shared system prompts across many different users — a long identical instruction can be computed once and its blocks shared read-only across every request using it. The paper reports up to 55% memory savings and as much as 2.2× throughput in these sharing-heavy workloads, stacked on top of the baseline fragmentation fix.

What happens when memory runs out anyway.

Paging doesn't manufacture memory from nothing — it just stops wasting what's there. Under heavy load, the scheduler sometimes has to reclaim a running sequence's memory to make room. vLLM picks between two strategies:

• Swap — copy the sequence's blocks out to CPU RAM, and back in when it resumes. Preserves everything computed so far (cheap to resume), costs PCIe bandwidth.
• Recompute — drop the cache entirely, and when the sequence resumes, just re-run the prefill from the prompt plus whatever had already been generated. Costs GPU compute instead of transfer bandwidth — often the winning choice for short sequences.

Which is faster depends on the ratio of KV cache size to prefill cost for that specific sequence and hardware — not a one-size-fits-all rule, and still an active area of production tuning.

The results: does the theory survive contact with real GPUs?

The headline number from the SOSP 2023 paper: vLLM delivers 2–4× higher throughput than FasterTransformer and Orca — the strongest serving systems of the time — at the same latency target. And the gap gets wider for longer sequences, bigger models, and fancier decoding (beam search, parallel sampling) — exactly the cases where the old reserve-the-max strategy was bleeding the most memory.

• KV cache waste: 60–80% (old contiguous systems) → <4% (PagedAttention).
• Throughput vs. FasterTransformer / Orca: 2–4×, at equal latency.
• Memory savings from sharing (parallel sampling / beam search): up to 55%, with up to 2.2× additional throughput.

Community benchmarks against naive HuggingFace generate() (no batching optimization at all) have reported gains well beyond that — but that's a much easier baseline to clear than FasterTransformer/Orca, so treat those bigger numbers as directional, not as a controlled comparison the way the paper's own figures are.

The honest tradeoffs — nothing here is free.

Every systems technique that adds a layer of indirection pays for it somewhere, and this is no exception:

• Extra indirection on the hot path. Every attention call now resolves a block table before it can fetch anything — small per call, but paid at every layer, for every token, every time.
• Kernel lock-in. Because the KV cache is no longer a plain contiguous tensor, you can't drop in an unmodified attention kernel from elsewhere — someone has to teach it to understand block tables first. That slows how fast the serving framework can adopt brand-new attention-kernel research.
• A real tuning knob. Smaller blocks tighten the fragmentation cap but add bookkeeping; bigger blocks cut indirection but let waste creep back into a bigger "last partial block." 16 tokens is a sane default, not a proof of optimality.

This exact critique is the pitch behind vAttention (Microsoft Research + IISc), which argues PagedAttention buys its fragmentation fix at the cost of software complexity and kernel portability — and proposes instead using the CUDA driver's own virtual-memory APIs to keep each sequence's cache virtually contiguous (so unmodified kernels keep working) while still allocating physical pages on demand underneath. It's a nice case study in how systems research iterates: PagedAttention proved software-level paging works here; vAttention asks whether the driver can just do it for you, the way it always has for ordinary process memory.

Why should you care?

1. If you serve LLMs, this is why vLLM exists. PagedAttention is the core mechanism inside vLLM, one of the most widely deployed open-source LLM serving frameworks — and the reason it can pack dramatically more concurrent requests onto the same GPUs than naive serving.
2. The economics are direct, not abstract. More concurrent requests per GPU at the same latency target means a lower cost per served token. That's the entire reason "2–4× throughput" matters commercially, not just academically.
3. It's why "just pick a bigger GPU" isn't the whole story. Before fixing the allocation strategy, more memory just meant more empty reservation. Fixing how memory is used mattered more than how much of it you had.

The one-paragraph version.

Every LLM serving system pre-2023 reserved KV cache memory for the worst-case sequence length, wasting 60–80% of it to fragmentation. PagedAttention borrows OS-style virtual memory paging wholesale: fixed-size KV blocks stored non-contiguously in GPU memory, and a per-sequence block table that maps logical order to physical location — the same trick a CPU's page table has always played. Waste drops to under 4%. Because block tables are just mappings, multiple sequences can share physical blocks via copy-on-write, making beam search and parallel sampling almost free in memory terms. The net effect, measured against the strongest serving systems of the time: 2–4× more throughput on the same hardware — which is why nearly every serving stack shipped since has adopted some form of paged or block-based KV cache management.

The napkin takeaway.

If serving an LLM is running a hotel, then:

• Old serving systems = lock an entire wing the moment any guest checks in, in case they stay a year
• PagedAttention = give every guest a room key that works on any room, hand out rooms one night at a time as they're actually needed, and let guests traveling together share a room's charge until they each want their own

Same hotel. Same number of rooms. One version turns away three guests it had space for. The other doesn't.

Paper: "Efficient Memory Management for Large Language Model Serving with PagedAttention" — Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica. UC Berkeley, with Stanford and ICSI. SOSP 2023. arXiv:2309.06180, September 2023. Longer technical walkthrough on this site: PagedAttention — how vLLM stopped wasting 80% of your GPU memory.