When you ask a chatbot a question, most of the GPU's effort isn't thinking — it's remembering. To avoid recomputing everything it has already seen, a transformer stores the key and value vectors of every past token at every layer. That store, the KV cache, is what makes generation fast. It is also what makes serving many users at once an engineering nightmare: the cache is huge, it grows and shrinks with every request, and managing it badly wastes most of your GPU memory. Modern inference engines like vLLM and SGLang exist, at their core, to manage this memory well.

What the KV cache actually is#

In a transformer, each token is processed through every layer, and each layer computes a key (K) and value (V) vector for it. When generating the next token, the model only needs attention over past tokens — so it caches their K and V vectors instead of recomputing them. This turns each decoding step into a cheap operation over cached data rather than a full re-read of the prompt.

The catch is size. The memory for one token's cache is:

2 (K and V) × layers × heads × head dimension × bytes per value

For a typical 8B-class dense model in FP16 (say 32 layers, 32 heads, head dimension 128), the math is 2 × 32 × 32 × 128 × 2 bytes ≈ 0.5 MB per token. Scale that to a 4,096-token conversation and you need ~2 GB of GPU memory per request just for the cache — before the model weights are even loaded. Older dense 70B-class models without grouped-query attention ran closer to 2–3 MB per token, so a single 32K-token request could demand tens of gigabytes of cache alone.

And here's the crux: the cache size is dynamic. A request starts with a short prompt, grows token by token during generation, and shrinks when it finishes. A serving system must pack dozens of these growing, shrinking caches onto one GPU at the same time. Throughput is, in practice, limited not by raw compute but by how many caches fit in memory — serving is memory-bound, not compute-bound.

The old way: contiguous buffers and 60–80% waste#

Early serving systems gave each request a single contiguous chunk of GPU memory for its KV cache, sized to the maximum sequence length (max_seq_len). That was simple — and brutally wasteful. The problems, measured in the PagedAttention paper (Figure 2), were threefold:

  • Internal fragmentation: most requests finish well before max_seq_len, so the unused tail of each allocation sits idle.
  • External fragmentation: as requests of different lengths start and stop, free memory becomes scattered into holes too small to use.
  • Reserved slots: conservative pre-allocation for worst-case beams and samples.

Together, these wasted the majority of allocated KV memory — analyses put total waste in the 60–80% range in naive systems. The GPU had the FLOPs to serve more users; it simply had nowhere to put their caches.

PagedAttention: virtual memory for GPUs#

The 2023 paper "Efficient Memory Management for Large Language Model Serving with PagedAttention" (Kwon et al., UC Berkeley; arXiv 2309.06180, presented at SOSP '23) made the key observation: this is exactly the problem operating systems solved in the 1960s with virtual memory paging. So it borrowed the solution wholesale.

Instead of one contiguous buffer per request, PagedAttention splits each sequence's KV cache into fixed-size blocks — typically 16 tokens each in vLLM — stored anywhere in physical GPU memory, not necessarily adjacent. A per-request block table maps logical block indices to physical block locations, exactly like a CPU page table maps virtual to physical addresses. New blocks are allocated on demand as generation proceeds, so waste is bounded by a fraction of one block. A fused attention kernel then computes attention directly over these non-contiguous blocks, using the block table for addressing — no need to gather the data into a contiguous region first.

The results, reported in the paper: near-zero KV cache waste and 2–4× higher throughput than the state-of-the-art systems of the time (FasterTransformer and Orca) at the same latency. The gains were most pronounced with longer sequences, larger models, and more complex decoding algorithms — precisely the workloads that matter most.

The bonus: sharing via copy-on-write#

Paging unlocked a second win almost for free. Because blocks are referenced through a table, multiple sequences can point at the same physical blocks. The paper's block manager adds reference counting, enabling:

  • Shared prompts: a batch of requests with the same system prompt stores that prompt's KV once, not once per request.
  • Parallel sampling: generating n completions from one prompt shares the entire prompt's blocks; when one completion diverges, copy-on-write duplicates only the changed blocks.
  • Beam search: beams share everything up to the point where they fork.

The paper also demonstrated significant memory savings on beam-search workloads from sharing alone — one detailed analysis of the paper cites savings of around 55%. This is also the mechanism behind the cross-request prefix caching now offered by major providers — Anthropic's prompt caching, for example, has been reported to cut costs by up to 90% and latency by up to 85% on cache-heavy long-prompt workloads (numbers from provider documentation, workloads vary).

Beyond paging: radix trees and continuous batching#

PagedAttention didn't end the story; it changed what serving engines optimize. Two ideas built directly on it:

Radix-tree prefix caching (SGLang's RadixAttention). vLLM's block-hashed prefix caching matches prefixes at block granularity — a 103-token prompt with 16-token blocks can only reuse 96 of them; the trailing 7 tokens must be recomputed. SGLang organizes cached KV in a radix tree (a compressed trie keyed by token sequences), which supports longest-prefix matches at any token boundary and naturally handles branching structures like tree-of-thought or multi-turn conversations. Blocks (or tree nodes) remain reference-counted and are evicted LRU when the pool fills.

Continuous batching. Older static batching waited for the slowest request in a batch to finish before admitting new ones. Modern engines admit and retire requests at every decoding step — and that flexibility is what makes demand paging pay off: memory freed by a finished request is immediately reusable by an incoming one, because there are no fixed-size slots to reshape.

When the cache pool does fill, engines choose between preemption strategies: drop a running sequence's KV and recompute its prefill later (cheap in memory, costs compute — fine for short prompts), or swap the KV to CPU RAM over PCIe and page it back (saves recompute, costs bandwidth — better for long prompts).

Why this matters to you#

If you're building on LLM APIs, these internals surface as dollars:

  • Batch size is the lever. Throughput per GPU roughly tracks how many requests' KV caches fit at once, so memory efficiency directly sets API pricing.
  • Share prefixes deliberately. Keeping a stable system prompt and putting shared context first maximizes prefix-cache hits — whether that's vLLM's block hash, SGLang's radix tree, or a provider's prompt cache.
  • Beware the long tail. A request that fills most of one block's worth of waste is cheap; the real cost is sequences that balloon to hundreds of thousands of tokens, where the KV cache can exceed the model weights many times over. That's why long-context serving is priced the way it is.

The takeaway: generating the next token is cheap compute over expensive memory. The labs that serve models at scale aren't mainly in a FLOPs race — they're in a memory-management race, and paging is how they won the first round.

Word on sources: the core facts here come from the PagedAttention paper (arXiv 2309.06180); the prefix-caching and SGLang details from the Modular inference handbook and SGLang documentation; the eviction/strategy overview from the vanta inference-caching skill notes. The per-token memory arithmetic is illustrative — exact figures vary by architecture (GQA grouping, dtype, RoPE) — so treat the MB-per-token figures as order-of-magnitude, not spec sheets.