Paged Attention and KV Cache Fragmentation

KV cache fragmentation, both internal and external, is the memory bottleneck that decides how much a large language model actually costs to serve. PagedAttention, the technique introduced by Kwon et al. in 2023, is the architectural fix that made the problem tractable, and understanding it in mechanical detail explains most of what has happened in LLM serving infrastructure since.

Start with what the KV cache actually does. During generation, a transformer stores the key and value tensors for every token it has already processed, so that each new token can attend to that history without recomputing it from scratch. Skipping the cache makes the cost of generating a sequence scale quadratically with its length, since every new token would force a fresh pass over everything before it. That's a non-starter for production serving.

The memory bill for that cache follows a straightforward formula: batch size times sequence length times number of layers times two (one tensor for keys, one for values) times hidden dimension times bytes per value. Every term in that product moves in the wrong direction as usage grows. A 70B-parameter model running an 8K-token context burns something like 20 GB of KV cache for a single request; batch that to 32 concurrent requests and the number climbs past 640 GB, more memory than any single GPU has ever shipped with. At scale, the cache can become a dominant factor in total memory footprint, which flips the usual intuition: the constraint on a serving cluster is rarely the model, it's the cache the model needs to run.

Worse, that footprint isn't fixed. It grows token by token as a request generates and collapses the moment the request finishes, so no static allocation plan can guess it correctly ahead of time. And because memory is the ceiling on how many requests a GPU can batch together at once, this is never just a memory problem. It's a throughput problem wearing a memory problem's clothes, and throughput is what determines the actual dollar cost of serving a model.

The two fragmentation modes that previous systems failed to solve

Systems that predate PagedAttention, Orca and FasterTransformer among them, handled this by allocating memory for the maximum context length the model could support, not the length any given request would actually use. That single design decision produces two distinct kinds of waste.

Internal fragmentation is the idle capacity sitting inside a reservation that generation never fills. On the ShareGPT dataset, the average decode length runs around 415 tokens, a fraction of the multi-thousand-token maximums these systems reserved by default. Every request that ends early leaves the rest of its slot empty and unusable by anyone else.

External fragmentation occurs when the cache needs a contiguous block of memory and the pattern of requests finishing and starting leaves the free memory scattered into small, disconnected gaps. The GPU might have plenty of free memory in aggregate, but if none of the gaps are big enough to hold a new request's cache, that memory is stranded.

Together with a third, smaller drag, memory reserved for tokens a live request hasn't generated yet, these effects added up to real numbers: prior serving systems wasted somewhere between 60% and 80% of allocated KV cache memory to fragmentation and over-allocation. Sit with that figure for a second, because it's the whole reason this problem got serious attention. That waste caps how many requests fit in a batch, which caps throughput, which sets the price per token a provider has to charge to break even.

The reason nobody had fixed this earlier wasn't laziness. Contiguous allocation was baked into how attention kernels were written from the start; solving fragmentation meant rethinking the relationship between where a sequence's tokens live logically and where its data physically sits in memory, a much deeper change than a config tweak.

How PagedAttention maps an OS concept onto GPU memory

PagedAttention, described by Kwon and coauthors in their 2023 paper, borrows an idea operating systems have used for decades: virtual memory. An OS gives each process the illusion of a clean, contiguous address space while quietly backing it with physical memory pages that can be scattered anywhere, and swapped in or out as needed. PagedAttention does the same thing for the KV cache.

The cache gets split into fixed-size blocks, each holding a set number of key-value pairs per attention head. A request sees its own cache as one continuous sequence, but underneath, its blocks can sit anywhere in GPU memory. A block table, functioning exactly like a page table in an operating system, tracks which physical block corresponds to which logical position in the sequence. New blocks get allocated only as a sequence actually grows, and freed the instant a request finishes.

That design kills both fragmentation modes at once. External fragmentation disappears because every block is the same fixed size: a freed block always fits whatever new block needs it, there's no length mismatch left over. Internal fragmentation shrinks to almost nothing because the system never allocates more blocks than the current sequence actually needs; there's no reservation for a maximum that may never be reached.

The results match the theory; vLLM, the implementation built around this idea, cuts KV cache waste to under 4% and delivers 2 to 4 times the throughput of FasterTransformer and Orca at matched latency, figures reported in the PagedAttention paper. The block table also opens a door nobody was using before: since physical pages are addressable independently of any one request, multiple requests that share a prefix, identical system prompts, or parallel beam-search branches, can literally point at the same physical block and only diverge where their content actually differs. That's a form of shared-page semantics familiar from OS memory management, applied to attention.

None of this is free of trade-offs, though. Block size is a real dial, not a fixed constant: bigger blocks improve kernel parallelism and hardware efficiency but bring back a sliver of internal fragmentation at the tail end of each sequence, while smaller blocks minimize that waste at the cost of a heavier block table to track. Every serving system built on this idea has to pick a number and live with it.

The non-contiguous memory layout PagedAttention introduces and its overhead

PagedAttention trades a contiguous virtual memory layout for a non-contiguous one. The kernel doing attention math can no longer just stride through one flat buffer. It has to follow pointers through the block table to find where each piece of the sequence actually lives, which is harder to write correctly and harder to keep fast.

That indirection has a real performance tax. Non-contiguous memory access reduces how much parallelism the GPU's memory system can extract, since gathering scattered pages is inherently slower than streaming one long, predictable buffer.

Microsoft Research's response, vAttention, published at ASPLOS 2025, takes the position that the virtual layout should stay contiguous while physical allocation still happens dynamically underneath it, recovering the simplicity of a flat buffer without giving back the memory efficiency PagedAttention earned. FlashInfer addresses the non-contiguity overhead through its own kernel design choices. Neither approach should be read as a correction of the other; they're different bets on where the trade-off between simplicity and efficiency should sit.

Whatever the overhead, the industry's verdict has already been cast in adoption numbers. TensorRT-LLM and Hugging Face's TGI have implemented vLLM-style PagedAttention. When that many independent serving stacks converge on the same design, the throughput gain is telling you it's worth the plumbing cost, for most production workloads at least.

A fragmentation problem that paging itself creates: block-level eviction mismatch

Paged memory doesn't make GPU memory infinite. Pushing batch size and context length far enough still fills up the GPU's HBM. Some blocks need to be evicted to make room for new requests.

The older eviction literature runs into a wall. Most eviction schemes rank which tokens to drop by looking at attention scores, the product of query and key matrices that tells you how much a given token mattered. FlashAttention, though, the kernel nearly everyone uses in production, never materializes those scores during inference; it fuses the computation so the intermediate result simply doesn't exist to inspect. Eviction methods built around attention scores can't plug into that pipeline cleanly.

Compounding the mismatch, token-level eviction schemes tend to drop different numbers of tokens from different blocks, which leaves some blocks partially empty. That's the exact structural problem PagedAttention was invented to eliminate, reappearing one layer down: fragmentation, no longer between allocations, but now living inside the paged blocks themselves.

PagedEviction, a 2025 paper out of Argonne National Laboratory and Illinois Institute of Technology (Chitty-Venkata et al., arXiv:2509.04377), addresses this directly with block-aware, structured eviction: instead of trimming individual tokens, it evicts whole blocks at a time, working from the key and value tensors themselves rather than requiring stored attention scores. That means it integrates with vLLM's PagedAttention without touching the CUDA attention kernels underneath. Tested on Llama-3.1-8B-Instruct, Llama-3.2-1B-Instruct, and Llama-3.2-3B-Instruct against the LongBench benchmark suite, the method shows better memory efficiency and better accuracy on long-context tasks than the baselines it's compared to.

A related, complementary idea is entropy-guided caching, which allocates cache budget per layer according to how broad or narrow that layer's attention pattern runs; layers whose attention spreads wide get more cache budget than layers that focus tightly. Streaming LLM's approach sits nearby conceptually: it keeps a handful of "attention sink" tokens, a small set of attention sink tokens at the start of a sequence, plus a sliding window of recent tokens, and discards the rest.

An eviction algorithm designed with no awareness of the paged memory model can quietly undo the benefit paging was built to deliver. The two have to be designed together, not bolted on in sequence.

Quantization as a way to stretch paged memory further

If paging solves how memory gets allocated, quantization attacks how much memory each token actually costs. A single Llama 3.1 70B request at 128K context needs roughly 42.9 GB of KV cache at BF16 precision (2 times 80 layers times 8 KV heads times 128 head_dim times 131,072 tokens times 2 bytes per value, if you want to run the arithmetic yourself). Dropping to FP8 halves that number to about 21.5 GB. Dropping again to NVFP4, available on Blackwell hardware like the B200 and RTX 5090, halves it once more to roughly 10.7 GB. Each step doubles how many concurrent requests fit on the same GPU.

NVFP4 comes with a hard compatibility line, though: it's Blackwell-only. Try to run it on an H100 or A100 and, depending on the vLLM version, it either throws an error or silently misbehaves. That's not a minor footnote for anyone planning a deployment across mixed hardware generations.

FP8 has its own failure mode, and it's a sharp one. A vLLM blog post from April 2026 documents a 128K needle-in-a-haystack test where FP8 accuracy collapsed from a 91% BF16 baseline down to just 13%, traced back to imprecise FP32 accumulation during the computation. Fixing that accumulation step restores accuracy close to the BF16 baseline while keeping FP8's decode-speed advantage, so the failure was fixable, but it shows quantization isn't a free lunch you can flip on without checking the output.

There's a subtler performance trap too, specific to models using sliding-window attention layers. In that architecture, the FP8 inter-token latency slope came in at 96% of the BF16 slope, meaning users saw almost no decode speedup despite the memory footprint being cut in half. The break-even point where FP8's memory savings actually translate into a throughput win didn't arrive until past 700K tokens, well beyond most real workloads.

Even with those caveats, FP8 KV cache is fast becoming the default rather than the exception: vLLM, SGLang, and TensorRT-LLM all ship it, and DeepSeek V4 defaults to FP8 for the non-RoPE dimensions of its KV cache, keeping BF16 only for the RoPE components. Quantization and paging are complementary, and each carries its own failure mode that needs separate scrutiny.

Lossless compression on top of quantized paged caches, the research frontier

Beyond quantization, which throws away precision on purpose, there's a separate line of work trying to squeeze the cache further without losing any information. ZipNN and similar prior efforts applied entropy coding to floating-point representations and showed meaningful size reductions, but that work did not target the lower-precision formats that production KV caches increasingly use.

A 2025 paper out of Intel (arXiv:2508.19263) extends that same idea down to FP8 and FP4, separating the exponent and mantissa components of each value and compressing them independently with entropy coding, closing the gap the earlier work left open. A related approach combines this kind of lossless coding with a lower-precision quantization step and reports total compression several times over when measured against the original BF16 cache, depending on the target size chosen, a result for the whole pipeline, not just the quantization step in isolation.

A third approach, TurboAngle (arXiv:2603.27467, March 2026), takes yet another angle, literally: it compresses KV cache entries by quantizing angular components. Tested across a range of models, it achieves fully lossless compression, meaning zero degradation in perplexity, on four of them, and near-lossless quality (perplexity increase under 0.002) on two more, all at somewhere between 3.28 and 3.67 bits per element for the angle representation.

What makes this relevant to paging specifically is that lossless compression like this can operate at the block level, which respects the uniform block structure PagedAttention depends on. Token-level eviction disrupts that structure, as covered above; block-level compression doesn't. Stacking paged allocation, FP8 quantization, and lossless entropy coding together produces a layered defense against the cache's memory footprint, each layer handling a different dimension of it, none of them requiring a rewrite of the serving system's architecture.

Offloading paged KV blocks to CPU DRAM and NVMe

Eventually, even the best-managed paged cache runs out of room on the GPU itself, and the only option left is to move data somewhere slower. A three-tier hierarchy handles this: hot blocks tied to active generation stay on GPU HBM, running around 3.35 TB/s; warm blocks that finished but might get reused sit on CPU DRAM, closer to 63 GB/s; cold blocks that are unlikely to be touched again land on NVMe SSD. Bandwidth drops by roughly two orders of magnitude at each step down.

Offloading from HBM to DRAM costs a little performance but not much, and it buys real headroom, though that headroom is capped by however much DRAM the host machine actually has, which is its own limited resource relative to how fast context lengths keep growing. Extending the hierarchy down to NVMe buys far more capacity, cheaply, but introduces a much bigger I/O overhead problem, because the gap in bandwidth between DRAM and NVMe is steep.

The root of that inefficiency traces directly back to paging itself. Research from Ren et al. (CHEOPS '25 / EuroSys '25, Rotterdam) found that the fragmented, non-contiguous layout PagedAttention creates inside GPU memory turns into a flood of tiny, random I/O operations the moment that data needs to be written out to or restored from NVMe. GPU Direct Storage helps, but it still depends on the CPU to kick off each individual I/O operation; that dependency makes the CPU the bottleneck even when the SSD underneath has plenty of raw bandwidth to spare.

That's the sharper irony in this whole story: the non-contiguous layout that solved fragmentation on the GPU becomes a liability the moment it has to be serialized down to block storage. Solve one tier's fragmentation problem and a new one appears one layer down, in the I/O pattern instead of the memory layout.

A 2026 paper called Tutti (arXiv:2605.03375) takes a direct swing at this, using peer-to-peer DMA paths so that when the inference engine evicts KV cache blocks from GPU memory, those tensors get persisted to local NVMe storage without routing every single transfer through the CPU as an intermediary. It's a narrow fix aimed at a narrow but very real bottleneck, and it fits the broader pattern this whole subject keeps demonstrating: every fix to KV cache memory management buys efficiency at one tier and hands a new, more specific problem to the next one down.