KV Cache and Paged Attention: Why LLM Serving Is Memory-Bound

TL;DR

When an LLM deployment falls over at 100 concurrent users, the video argues the model is almost never the culprit — GPU memory management during inference is. Inference splits into a compute-bound prefill phase (process the whole prompt, produce the first token) and a memory-bound decode phase (emit one token at a time, re-reading the whole context from VRAM each step). The KV cache is what makes decode tractable — it stores the key/value matrices of every prior token so the 1000th token doesn't recompute the first 999 — and it is explicitly a memory-for-compute trade. That trade then creates the real bottleneck: naive serving pre-allocates one contiguous VRAM block per request sized to the maximum possible output length, so a request that could use 300 tokens holds 2048, and the video states research shows 60–80% of KV cache memory is wasted to internal fragmentation, external fragmentation, and duplicated system prompts. Paged attention (from vLLM) fixes this by lifting a fifty-year-old OS idea wholesale: break the KV cache into fixed 16-token pages, let them live anywhere in VRAM non-contiguously, and keep a lightweight block table mapping logical → physical pages. Once memory is paged and blocks are hashed by token sequence, prefix caching falls out for free — requests sharing a system prompt point at the same physical pages. The operator payload is three vLLM flags (--gpu-memory-utilization, --enable-prefix-caching, --enable-chunked-prefill) plus speculative decoding as a latency-only bonus, all framed as "more throughput out of a GPU you already have."

Concepts introduced

• Prefill and Decode Phases — the two-phase decomposition of inference (compute-bound prefill, memory-bound decode) that every other technique here is an optimization of.
• KV Cache — the memory-for-compute trade that turns quadratic re-attention into a lookup, and in doing so relocates the bottleneck to VRAM.
• KV Cache Fragmentation — the waste taxonomy (internal, external, duplication) that explains why the naive allocator loses 60–80% of the cache budget; the diagnosis before the cure.
• Paged Attention — OS virtual-memory paging applied to the KV cache; the cure, and the substrate that makes cross-request prefix sharing possible at all.
• Speculative Decoding — spend idle decode-phase compute on a draft model to buy latency; quality-neutral, throughput-negative at high concurrency.

Held, not dropped (touched by the capture, no concept page yet — spin out on demand):

• Chunked prefill — a real named technique with a durable core (interleave the compute-bound and memory-bound phases so neither unit idles), but the capture treats it as one vLLM flag. Recorded as a claim on Prefill and Decode Phases rather than promoted to its own page.
• vLLM as an artifact — the engine itself, its defaults, and its flag surface. The concepts above are engine-independent; vLLM's specific defaults (0.9 utilization, 16-token pages, 2048 batched tokens) are held as source-attributed observations, not as durable structure.
• GuideLLM — the benchmarking tool named for sizing --gpu-memory-utilization before commit.
• N-gram speculation — the zero-draft-model speculator for structured/repetitive output.
• Memory-bandwidth-bound vs compute-bound (roofline) — the video gestures at "spare compute idle between memory reads" without naming the roofline model that formalizes it. This is the general principle under both chunked prefill and speculative decoding, and probably deserves a page once a second source corroborates.
• Continuous / in-flight batching — implied by "packing more concurrent requests" but never named in the capture.

Key claims

• Inference has two phases with opposite bottlenecks: prefill is compute-bound, decode is memory-bound. principle → Prefill and Decode Phases. Durable and architectural — it follows from the shape of autoregressive attention, not from any engine's implementation.
• Caching prior tokens' key/value matrices trades memory for compute. principle → KV Cache. The video is careful to name it a trade, not a free win — the cost is paid in VRAM, which is precisely where the next bottleneck appears.
• Optimizing serving means optimizing memory, not the model. principle → KV Cache. Stated as the video's opening thesis: "your model is most likely not the culprit."
• Pre-allocating a contiguous block sized to max output length wastes most of the KV budget. observation → KV Cache Fragmentation. The video states research shows 60–80% of the KV-cache slice is wasted in traditional systems; the figure is attributed to the source and is worth grounding against the PagedAttention paper.
• Non-contiguous, on-demand, fixed-size pages plus an indirection table eliminate fragmentation. principle → Paged Attention. Not novel to LLMs — it is virtual memory. That it transfers is the load-bearing insight.
• A 13B model needs ~26 GB of weights, 65% of an A100 40 GB, before any user connects. observation → Paged Attention. The source's arithmetic; check-worthy (captions render the card as "A140 gigabyte").
• vLLM's default page size is 16 tokens. observation → Paged Attention. Engine default as of the source; check-worthy and version-dependent.
• Set --gpu-memory-utilization to 0.95 on stable workloads, 0.8 under bursty load. best practice → Paged Attention. Context: vLLM, default 0.9; "best" only once you know your load shape — 0.95 packs more concurrent requests but leaves no headroom, and 0.8 is a concession to OOM under burst. The video's own guardrail is the right one: benchmark your specific model before you commit. Stripped of the load-shape context this is just a number to copy-paste, and it will OOM someone.
• Enable prefix caching when requests share a long prefix. best practice → Prompt Caching, Paged Attention. Context: RAG pipelines, multi-turn chat, and coding agents — workloads that re-send a fat system prompt. The video claims 75–95% hit rates for those workloads. For one-shot heterogeneous prompts there is no prefix to share and the mechanism is moot.
• Prefix caching hit rates of 75–95% are common in RAG / multi-turn chat / coding agents. observation → Prompt Caching. The source's number; check-worthy.
• Enable chunked prefill for throughput-heavy workloads; production sees ~50% throughput gain. best practice → Prefill and Decode Phases. Context: throughput-heavy serving where long prompts arrive alongside active decode streams and cause visible stutter. The 50% figure is the source's claim observation and is check-worthy. Not indicated when a single stream's latency is all that matters.
• Speculative decoding's output is mathematically identical to the large model alone. observation → Speculative Decoding. A strong, groundable claim (it is the advertised property of rejection-sampling verification); attributed to the source, not adjudicated here.
• Reach for speculative decoding when interactive latency matters more than raw throughput. best practice → Speculative Decoding. Context: low-to-moderate concurrency, where the GPU has idle compute between memory reads. The video is unusually honest that the gains shrink at high concurrency because a full batch already saturates the GPU — the technique spends spare compute, and at scale there is none spare. Inverting this context turns a latency win into pure overhead.

Why this builds on Prompt Caching

The vault already holds Prompt Caching, written from Anthropic's Claude Cookbooks — an API-consumer's view: mark a stable prefix as cacheable, order stable-first/volatile-last, pay less and wait less. Its aliases already include "prefix caching" and "KV cache reuse", which is the tell: the existing page names the technique by its effect and takes the mechanism on faith.

This capture supplies the mechanism from underneath, and it is not a decoration — it explains the existing page's rules rather than restating them:

• Why the prefix must be a prefix. Because paged attention hashes each 16-token KV block by its token sequence; a cache hit is a block-hash match, and the first differing token breaks the chain of matching blocks. "Stable content first" is not a stylistic convention — it is a consequence of block-level content addressing.
• Why sharing works across requests, not just across turns. Because the block table is an indirection: two requests' logical page 0 can point at one physical page. Prompt caching's economics ("the prefix is the dominant cost") are a serving-layer property, not a per-session one.
• Why it is a cache at all. The KV cache exists because decode is memory-bound; prompt caching is that same cache, reused across request boundaries instead of within one.

So: builds_on Prompt Caching, novel with respect to everything else — the vault had no representation of the serving layer (prefill/decode, VRAM budgeting, fragmentation, speculative decoding) at all. Two independent sources (Anthropic's cookbooks, IBM's vLLM explainer) now converge on prefix reuse being the single biggest inference-economics lever, arriving from opposite directions — one from the API surface, one from the allocator. That convergence is worth recording: it is the same claim reached without shared assumptions.

One genuine tension worth naming, though not a contradicts against any page: Prompt Caching presents cache reuse as an unqualified structural saving ("recomputing an identical prefix on every call is pure waste"). This capture makes the price visible — the KV cache is a memory-for-compute trade, and cached prefixes occupy physical VRAM pages that could otherwise hold concurrent requests. At the API boundary the trade is invisible because someone else is paying it. Anyone running their own serving stack pays it directly, and the --gpu-memory-utilization knob is exactly where that bill arrives.

Illustrated walkthrough

A caveat on faithfulness: the transcript is auto-generated captions and garbles several terms. "Page detention" is paged attention; "A140 gigabyte card" is an A100 40 GB; "the LLM project" is the vLLM project; "Ingram" is n-gram; "KVQ" is K, V, Q; "LLM imprints" is LLM inference. Reconstructions below are marked where they were needed.

• t=00:15 — Board opens with a curve: TTFT on the y-axis, concurrent users on the x-axis, bending sharply upward. "GPU VRAM" is written top-centre. Spoken over it: one user is fast, ten users see latency climb, "at a hundred, you're watching GPU memory spike and throughput tank. And every cycle is wasted money." The thesis lands at t=00:17 — "Your model is most likely not the culprit here, but rather how your memory is being used during inference."

• t=00:46 — Two terms written down the left margin, KV cache and Paged attention, joined by a brace to a single word beneath: vLLM. The framing is that both techniques come out of one open-source inference engine.

• t=01:36 — Prefill phase written in green, centre-board. "That lag before your first token is the model processing your prompt." Annotated compute bound at t=01:45: the model runs the input through every transformer layer to build a representation of everything you said before it can emit a single output token.

• t=02:20 — The board now reads Prefill phase (boxed, compute bound) → Decode phase, with the token boxes T1 T2 beginning to trail off to the right. Decode is Memory Bound (t=02:21): every generation step reaches back into GPU memory to retrieve that request's growing context. Punchline at t=02:37: "if memory is fragmented, if it's full, if it is being recomputed, it will become latency you can see."

• t=04:00 — Attention decomposed in gold on the right: Q V (and K), with the query glossed as the current token asking "What's relevant to me?" and key/value as the answer. The problem stated at t=03:27: autoregressive generation produces one token at a time but must re-run attention over all previous tokens every step. Without a cache, the 1000th token recomputes keys and values for all 999 before it. The KV cache stores those matrices so each new token only computes its own K, V, Q and then attends over cached history. Explicitly named a memory-for- compute trade-off at t=04:10, "proven to be worth it for long sequences" — followed immediately by "memory is the real bottleneck in LLM serving."

• t=04:42 — A horizontal VRAM bar is drawn; the first segment is labelled 65%. Spoken: a 13B model (Llama 13B) takes ~26 GB of weights on an A100 40 GB card — 65% of available memory before a single user hits an endpoint. The remaining 35% must hold the KV cache for every active request.

• t=05:30 — Left: the VRAM bar now reads 65% weights. Right: a tall box labelled 2048 with a small scribbled-in region at its base labelled 300. This is the naive allocator: max context 2048 tokens reserved, average user sends 200 and gets 300 back, so ~1,500 tokens of reserved memory sit empty per request. At t=05:32 the claim that research shows traditional systems waste 60–80% of the KV-cache slice.

• t=07:38 — The full diagnosis is on the board and being struck through one line at a time in green: Internal Frag. External Frag. Duplications. Below, the VRAM bar has been subdivided: 65% weights | … | a small slice labelled usable inside the 35%. The TTFT curve is now labelled naive. Paged attention "applies the exact same insight that operating systems use for RAM, virtual memory paging": fixed pages (default 16 tokens), non-contiguous, allocated on demand, with a lightweight block table mapping the logical addresses the model sees to the physical addresses in VRAM. (The block-table diagram itself is in the ~20 s window the sampler missed.)

• t=08:40 → t=09:36 — Board wiped; new heading Tuning vLLM Deployments, then three numbered flags appear in gold:

  • 01 Tune --gpu-memory-utilization — the fraction of remaining VRAM given to the KV cache. Default 0.9; push to 0.95 on stable workloads to pack more concurrent requests; pull to 0.8 if OOM under burst. Benchmark first — the video points at GuideLLM, "an open source part of the vLLM project" (reconstructed; captions say "the LLM project").
  • 02 --enable-prefix-caching — paged attention hashes each KV block by its token sequence, so requests sharing a system prompt point to the same physical memory; vLLM computes and stores it once. RAG pipelines, multi-turn chat, and coding agents are said to hit 75–95% cache-hit rates, with TTFT dropping dramatically because shared prefill is skipped entirely.
  • 03 --enable-chunked-prefill + Set max_num_batched_tokens > 2048 — by default vLLM runs prefill to completion before resuming decode, which makes streamed tokens stutter when a long prompt arrives. Chunked prefill prioritizes decode requests in the batch, then fills the remaining compute budget with prefill chunks. 50% throughput improvement claimed in production deployments. (Captions garble this as "inflate decode request first"; read "prioritizes decode requests first".)

• t=10:14 — --speculative-model written left; on the right, two circled LLM nodes, the upper one emitting boxed tokens T1 T2 T3. During decode the GPU has spare compute idle between memory reads (this is the memory-bound phase paying off) — so a small draft model proposes a run of tokens and the large model verifies them in one forward pass. Accepted tokens ship; wrong ones are corrected. Output quality is asserted to be mathematically identical to running the large model alone. Two honest caveats are given at t=10:26: gains shrink at very high concurrency because the batch already keeps the GPU busy, so "reach for this when interactive latency matters more than raw throughput"; and vLLM ships a zero-cost n-gram speculator (--speculative-model ngram) for structured or repetitive outputs.

Linked from

• This Week
• KV Cache
• KV Cache Fragmentation
• Paged Attention
• Prefill and Decode Phases
• Prompt Caching
• Speculative Decoding