KV Cache & PagedAttention

Multi-Query Attention (MQA) and Grouped-Query Attention (GQA) shrink each token's key-value (KV) footprint. Serving still has to keep that smaller cache from wasting memory as variable-length requests enter and leave a batch.

When a coding assistant answers a repository question, it has to remember the system instructions, open files, failing test output, issue context, and previous tool results. Each new token the model generates would require re-reading that whole history from scratch if it didn't have a way to remember what it already computed.

That memory is called the KV cache (Key-Value cache). It stores the intermediate results the model needs to attend back to earlier tokens without recomputing them. The cache makes generation fast, but it creates a hard engineering problem: it consumes a huge amount of expensive GPU memory, and that consumption grows with every token and every simultaneous request.

Managing this memory efficiently is central to LLM serving. PagedAttention, introduced with vLLM, borrows ideas from operating-system paging to reduce fragmentation and pack active request state more tightly.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

---

Why the KV Cache Exists

Two earlier ideas matter here. First, Transformer self-attention: the model computes Query, Key, and Value vectors to decide which earlier tokens matter for the current token.^{[2]Reference 2Attention Is All You Need.https://arxiv.org/abs/1706.03762} Second, autoregressive generation: the model produces one token at a time, and each new token can attend to every token that came before it. If those prerequisites are fresh, the rest follows naturally.

Autoregressive generation

Without a KV cache, generating each new token is like re-reading the entire conversation from scratch every time you want to say one more sentence. The KV cache is like keeping a running notebook: each time you process a token, you jot down a summary (Key) and the relevant content (Value). When the next token needs to reference earlier context, you flip through the notebook instead of re-reading everything. The notebook grows with each token, which is why memory management matters so much.

In a Transformer model, generating the next token requires attending to all previous tokens in the sequence.^{[2]Reference 2Attention Is All You Need.https://arxiv.org/abs/1706.03762} The attention mechanism for a query token $q_t$ at step $t$ is defined as:

$\text{Attention}(q_t, K_{1:t}, V_{1:t}) = \text{softmax}\left(\frac{q_t K_{1:t}^T}{\sqrt{d_k}}\right) V_{1:t}$

To understand this formula: the current token's query $q_t$ is compared against all previous keys $K_{1:t}$ (via dot product, scaled by $\sqrt{d_k}$). The softmax function then determines which previous tokens are most relevant, and those tokens' values $V_{1:t}$ are blended accordingly. Without caching, the keys and values would need to be recomputed from scratch at every step.

Here $K_{1:t}$ and $V_{1:t}$ represent the Key and Value matrices for all tokens from position 1 to $t$.

Without caching, generating token $t$ would require recomputing the Key and Value vectors for all $t-1$ previous tokens at every single step. That means the cost of generating each new token grows linearly with sequence length, giving a quadratic total cost for the full sequence. The KV cache eliminates the repeated K/V projection work, but the attention operation still has to read the full cached history for each new token.

KV cache: cache K, V from previous steps

The KV cache solves this by storing the Key ($K$) and Value ($V$) vectors for all previous tokens in GPU memory. At step $t$, we only need to compute $q_t, k_t, v_t$ for the current token, and append $k_t, v_t$ to the cache.

With the KV cache, the decode phase (generating one new token at a time) still scales linearly per step in sequence length because each new token attends over all cached tokens. As cache reads grow, long-context decode can become memory-bandwidth-sensitive even after caching.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

---

KV cache memory analysis

The size of the KV cache isn't trivial. Count the bytes for a concrete model first, then write the general formula.

Memory footprint examples (FP16)

For the 80-layer, 8-KV-head GQA example, a single 4K-context request already consumes 1.25 GiB of KV cache. A batch of 128 such requests would need 160 GiB of High Bandwidth Memory (HBM), before weights and runtime buffers. That's beyond a single 80 GB-class accelerator, so memory capacity can cap throughput before raw FLOPs do.

If you plug in 80 layers, 64 KV heads, head dimension 128, and FP16 precision, you get 2.5 MiB per token. Keeping the layers, head dimension, and precision fixed but reducing the KV heads from 64 to 8 drops that to 320 KiB per token. At 4K context, that's the difference between 10 GiB and 1.25 GiB of cache for a single request.

Where do these numbers come from? The memory required per token follows a simple rule:

$$\text{Bytes per token} = 2 \times n_{\text{layers}} \times n_{\text{kv-heads}} \times d_{\text{head}} \times P_{\text{bytes}}$$

To interpret this formula: for each token, we store a Key and Value vector (hence the "2") across every layer and every KV head. Each vector has $d_{\text{head}}$ dimensions, and $P_{\text{bytes}}$ is the precision size. For plain Multi-Head Attention (MHA), $n_{\text{kv-heads}} = n_{\text{heads}}$. For Grouped-Query Attention (GQA) or Multi-Query Attention (MQA), the number of KV heads is smaller, which directly shrinks the cache.^{[3]Reference 3GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.https://arxiv.org/abs/2305.13245[4]Reference 4Fast Transformer Decoding: One Write-Head is All You Need.https://arxiv.org/abs/1911.02150}

Where:

• $2$: For both Key and Value matrices
• $n_{\text{layers}}$: Number of transformer layers
• $n_{\text{kv-heads}}$: Number of KV heads. In MHA this equals the number of attention heads; in GQA/MQA it's smaller
• $d_{\text{head}}$: Dimension of each head
• $P_{\text{bytes}}$: Stored K/V payload precision (2 bytes for FP16, 1 byte for FP8/INT8)

This is the tensor-payload calculation. A deployed engine may also reserve quantization scales, block tables, temporary workspaces, communication buffers, graph memory, and allocator headroom. Use the formula to reason about slopes, then profile the runtime before setting admission limits.

---

The memory fragmentation problem

In a naive serving system, memory for the KV cache is allocated as a single, contiguous buffer for each request. Because the system can't know ahead of time how many tokens the model will generate before stopping, it often reserves enough memory to accommodate the configured maximum possible sequence length (for instance, 4096 tokens).

Types of waste

This pessimistic allocation wastes memory in three distinct ways:

1. Internal Fragmentation: This occurs when a request reserves the maximum space (e.g., 4096 tokens) but finishes generation early (e.g., after just 200 tokens). The remaining 3896 pre-allocated slots sit empty but can't be used by any other request.
2. External Fragmentation: Over time, as requests of various sizes enter and leave the system, free memory becomes scattered in small gaps between the allocated buffers. Even if the total free memory is large enough to handle a new request, the system can't launch it because there's no single contiguous block large enough to hold it.
3. Reservation Waste: Because the system guarantees contiguous memory for the maximum possible length, it can't oversubscribe memory based on average sequence lengths. This forces the system to operate highly conservatively.

In the vLLM paper's evaluation traces, existing contiguous allocators used only 20.4-38.2% of KV memory to hold live token states, which means the rest was lost to fragmentation and over-reservation.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} That directly limits the maximum batch size and throttles throughput.

---

PagedAttention (vLLM)

Virtual memory for KV cache

PagedAttention adapts the concept of paging from operating systems to LLM serving.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} Instead of contiguous buffers, the KV cache is divided into fixed-size blocks. Block size is a runtime choice. After its ablation study, the original vLLM evaluation used a default of 16 tokens per block.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Naive KV cache allocation reserves one large contiguous region for each request's maximum possible sequence, even when the request uses only part of it. Most reserved space can go unused. PagedAttention assigns fixed-size blocks only as requests need them, and those blocks don't have to sit next to each other in physical memory. When a request finishes, its blocks are immediately available for the next request. Waste is mostly limited to each request's final partially filled block.

• Logical Blocks: The sequence of tokens as seen by the model (contiguous indices 0, 1, 2...).
• Physical Blocks: Where the data lives in GPU memory (non-contiguous, scattered).
• Block Table: A mapping that translates logical block indices to physical block addresses.

This allows the system to allocate memory dynamically, one block at a time, only when needed.

Efficiency gains

In the vLLM paper, waste stays under 4% because only the last partially filled block of each sequence can be underutilized, plus a small amount of block-table metadata.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} On top of that memory-efficiency gain, the paper reports 2-4× higher throughput at comparable latency versus systems such as FasterTransformer and Orca, with bigger gains on longer sequences and more complex decoding workloads.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Block size is a real trade-off. Smaller blocks reduce tail waste and improve sharing granularity, but they increase block-table lookups and can reduce GPU kernel efficiency. Larger blocks improve memory access regularity, but they waste more space in the final block. In vLLM's ablation, block sizes from 16 to 128 worked best on ShareGPT-like traces, shorter Alpaca-like traces favored 16 or 32, and the default landed at 16.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

---

Implementation sketch

This Python code simulates how a PagedAttention manager allocates and tracks blocks for requests. The logic shows how variable-length requests map to fixed-size memory pools. In a real system (vLLM), this manager runs on the CPU, while custom CUDA kernels handle the actual attention computation on the GPU.

The PagedKVCacheManager takes the block size and total block count as initialization parameters. When requests arrive, it takes a request ID and assigns logical blocks, returning the physical block index and slot offset where the new token's Key and Value tensors should be written as tokens are generated.

allocate only grabs a single block to start. As append_slot is called during the autoregressive generation loop, new blocks are pulled from free_blocks strictly on-demand. When the request completes, free returns all blocks to the shared pool. In this fixed-size toy pool, no variable-sized gap is stranded; a production runtime must also account for tensors and allocator state outside this KV block pool.

Tracing a small example

The next trace shows what happens when two requests arrive in a manager with block_size = 4 and num_blocks = 20.

Request A arrives. allocate("A") pops physical block 19 from free_blocks. The block table becomes {"A": [19]}. The sequence length is 0.

Request A generates four tokens. append_slot("A") is called four times. The first three tokens fit into block 19 at offsets 0, 1, and 2. On the fourth call, token_idx = 3, which is still within block 19 (offset 3). After the fourth token, seq_lens["A"] = 4.

Request A generates a fifth token. Now token_idx = 4 and 4 % 4 == 0, so the current block is full. append_slot("A") pops a new block (18, the next index off the free stack) from free_blocks, appends it to the block table, and writes the fifth token at offset 0 inside block 18. The block table is now {"A": [19, 18]}, which matches the A (18, 0) line in the output above.

Request B arrives. allocate("B") pops block 17. Block table: {"A": [19, 18], "B": [17]}.

Request A finishes. free("A") returns blocks 19 and 18 to free_blocks. They are immediately available for the next incoming request, without leaving a variable-sized gap in this fixed-block pool.

This trace shows the core dynamic: blocks are grabbed one at a time, only when needed, and returned instantly when the request completes.

Real engines add two important pieces we omitted for clarity: a reference count per physical block (for shared prefixes) and copy-on-write when a sequence needs to write into a block that's currently shared.

Treating PagedAttention as an attention-speedup trick is a common mistake. It doesn't change the attention math. It reduces KV-cache allocation waste and enables block sharing, which lets more useful work fit in the same GPU memory. What changes is how the K and V tensors are laid out in HBM so the GPU can find them without wasting space.

---

vLLM architecture

vLLM combines PagedAttention with a scheduler that manages the lifecycle of requests. Because memory is now a shared resource managed much like an operating system's virtual memory, the scheduler must gracefully handle preemption when the GPU's memory capacity is fully exhausted.

Preemption: current recompute, legacy swap

In a highly loaded multi-tenant system, the GPU block pool can still become exhausted. Current vLLM V1 preempts work by freeing its KV blocks, rescheduling the request, and recomputing its cache later. The official optimization guide warns that this recovery path can hurt end-to-end latency.^{[5]Reference 5Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html}

The original vLLM paper and legacy V0 runtime also evaluated CPU swapping. Keeping both designs separate makes the tradeoff clear:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

1. Recomputing (current vLLM V1): Discard the preempted request's KV blocks and rebuild them later by rerunning prior work. This spends extra FLOPs, but avoids Peripheral Component Interconnect Express (PCIe) transfer overhead.
2. Swapping (legacy vLLM V0): Move KV blocks from GPU HBM to CPU RAM, then swap them back in later. This preserves previous work, but consumes PCIe bandwidth. The vLLM V1 guide says V1 removed this built-in path; the official optimization guide says V1 defaults to recomputation because it has lower overhead.^{[5]Reference 5Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html}

Once GPU space opens up, the request resumes after its cache is rebuilt. Other runtimes may still expose offload or swap designs, but either recovery path costs latency. Capacity planning should avoid frequent preemption.

Suppose a two-rank deployment serves an 80-layer model with 8 KV heads, head dimension 128, FP16 cache, and an 8K context window. From the table earlier, that cache adds 320 KiB per token, or 2.5 GiB per full request across the model. If the KV heads are evenly sharded over the two ranks, each rank stores 1.25 GiB of that request. Applying the paper's under-4% tail-waste result as an estimate gives about 1.30 GiB per rank.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Don't derive an admission limit from advertised HBM minus model weights alone. Profile how much per-rank memory remains after weights, kernels, communication buffers, graphs, and safety headroom. If that measured KV budget is 8 GiB per rank, only six fully occupied 8K requests fit under the simplified estimate below. PagedAttention doesn't change this full-context case much; it changes variable-length traffic by allocating blocks for live state rather than reserving every maximum-length tail.

---

Continuous batching (iteration-level batching)

PagedAttention pairs especially well with continuous batching (also called iteration-level scheduling).

Static batching limitations

In traditional static batching, the system waits for $N$ requests to arrive, bundles them into a batch, and processes them together until all requests in the batch are completed. Because sequences have variable lengths, the shorter requests finish early, leaving GPU compute units idle while waiting for the longest request to complete.

The continuous batching approach

Continuous batching, made explicit in systems like Orca, reevaluates the active batch at every decode iteration.^{[6]Reference 6Orca: A Distributed Serving System for Transformer-Based Generative Models.https://www.usenix.org/conference/osdi22/presentation/yu} As soon as one request emits an End-of-Sequence (EOS) token and finishes, the scheduler ejects it, frees its KV cache blocks, and admits another waiting request into the running batch.

By operating at the iteration level rather than the request level, the engine avoids leaving slots idle just because one request finished earlier than the others. Continuous batching and PagedAttention solve different bottlenecks, but they work especially well together: one keeps compute busy, and the other makes memory reuse immediate.

Continuous batching transforms the batch from a static grouping into a sliding window of active computations. Orca reported up to 36.9× higher throughput than FasterTransformer at the same latency target on GPT-3 175B, because late arrivals can join ongoing work and early finishers can leave immediately.^{[6]Reference 6Orca: A Distributed Serving System for Transformer-Based Generative Models.https://www.usenix.org/conference/osdi22/presentation/yu} PagedAttention makes that scheduling policy much easier to sustain under tight memory budgets.

---

How serving engines build on PagedAttention

Copy-on-write for branches, prefix caching across requests

Block tables make shared physical blocks possible, but they don't by themselves decide which independently arriving requests may reuse state. In the original vLLM design, copy-on-write lets output sequences forked from the same prompt, such as parallel sampling or beam-search candidates, share their prompt blocks until a branch writes divergent state.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Reusing a system prompt across separate user requests requires an additional prefix cache policy: retain completed prefix blocks, match an exactly compatible token prefix, apply isolation keys where needed, and only then map new requests to the cached state. vLLM documents this cross-request feature as Automatic Prefix Caching.^{[7]Reference 7Automatic Prefix Cachinghttps://docs.vllm.ai/en/latest/features/automatic_prefix_caching/} The next lesson covers those matching and isolation rules in depth.

Suppose 100 requests are allowed to reuse the same 1000-token system-instruction prefix:

• Without prefix caching: Store 100 copies of the reusable prefix blocks.
• With compatible prefix caching: Store one physical prefix copy and map permitted requests to those read-only blocks until their unique continuation begins.

If all 100 requests qualify, that arrangement saves roughly 99% of prefix-block storage in this example. It doesn't save unique user input or generated-token cache, and it must not cross tenant or adapter boundaries without an isolation policy.

RadixAttention (SGLang)

Newer engines like SGLang extend this with RadixAttention.^{[8]Reference 8SGLang: Efficient Execution of Structured Language Model Programshttps://arxiv.org/abs/2312.07104} Instead of discarding KV state after each generation call, the runtime keeps a least-recently used (LRU) cache of KV entries for all requests inside a radix tree.

• Hit: Reuse existing KV blocks immediately (no recomputation needed).
• Miss: Compute only the new tokens.

That makes it particularly effective for multi-turn chat and agentic workloads where long prompt prefixes repeat across calls.^{[8]Reference 8SGLang: Efficient Execution of Structured Language Model Programshttps://arxiv.org/abs/2312.07104}

FlashInfer and kernel optimization

FlashInfer is a kernel library for serving workloads that accelerates attention over paged KV caches and variable-length sequences.^{[9]Reference 9FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving.https://arxiv.org/abs/2501.01005} It doesn't replace PagedAttention at the memory-manager level. Instead, it speeds up the GPU kernels that consume those layouts during decode.

PagedAttention vs. FlashAttention

These names are easy to mix up, but they solve different problems.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180[10]Reference 10FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.https://arxiv.org/abs/2205.14135}

• PagedAttention: A KV-cache layout and allocation strategy. It places cached K/V tensors in blocks and supports block sharing; a prefix-cache policy decides cross-request reuse.
• FlashAttention: An IO-aware attention kernel. It tiles attention so the GPU does less wasteful movement between HBM and on-chip memory, especially during full attention computation.^{[10]Reference 10FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.https://arxiv.org/abs/2205.14135}

Modern serving stacks often use both or close variants together.^{[9]Reference 9FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving.https://arxiv.org/abs/2501.01005} PagedAttention makes the cache fit and stay shareable. FlashAttention-style kernels make attention itself faster once those tensors are in place.

---

Reducing KV cache at the architecture level

PagedAttention optimizes how memory is managed by changing allocation. It doesn't change the mathematical size of the tensors. Model architecture changes optimize how much memory is needed in the first place.

Grouped-Query Attention (GQA) is a structural technique that can sharply shrink baseline cache size. Instead of maintaining a separate Key and Value head for every single Query head (as in traditional Multi-Head Attention), GQA groups multiple Query heads together to share a Key and Value head. Ainslie et al. found intermediate group counts recovered much of MHA quality while retaining MQA-like inference benefits after uptraining; other models still require their own quality evaluation.^{[3]Reference 3GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.https://arxiv.org/abs/2305.13245}

By sharing KV heads, the memory footprint required for each token drops proportionally to the group size. For the 80-layer example above, moving from 64 distinct KV heads down to 8 (a group size of 8) reduces the per-token KV cache memory by exactly 8 times.

GQA reduces the size of the problem, while PagedAttention solves the allocation of the problem. They are complementary when the selected model architecture and serving runtime support both.

---

Practical considerations

Confusing the KV cache with the model weights is another common mistake. The weights are static parameters loaded once at startup and shared across every request. The KV cache is per-request state that grows as the conversation proceeds. If you size a GPU for weights alone and forget the cache, you'll hit out-of-memory errors the moment you try to serve more than a handful of long conversations.

1. The prefill vs. decode bottleneck

LLM inference still has two useful workload categories:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180[11]Reference 11DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

• Prefill: Processing the input prompt. For sufficiently large prompt batches, dense matrix multiplications often make this phase compute-heavy and highly parallelizable.
• Decode: Generating tokens one by one. At common serving batch sizes, repeatedly loading weights and growing KV state often makes this phase memory-bandwidth-sensitive.

PagedAttention manages KV blocks for prompt tokens and generated tokens. Its capacity benefit becomes especially visible during decode, where request lengths diverge and each new token grows the cache. The current vLLM V1 guide describes unified scheduling rather than separate prompt-phase and output-phase queues, while chunked prefill keeps large prompts from monopolizing one iteration.^{[5]Reference 5Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html} At larger scale, disaggregated serving can still separate these workloads to keep time to first token (TTFT) and inter-token latency smooth.^{[12]Reference 12Sarathi-Serve: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills.https://arxiv.org/abs/2308.16369[11]Reference 11DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving.https://arxiv.org/abs/2401.09670}

2. Context window limits

Even with PagedAttention, the KV cache still grows linearly with context length. The 80-layer, 8-KV-head, 128-dim GQA example from earlier needs 40 GiB of KV cache at 128K context in FP16. At that scale, KV memory can rival or exceed the room left after loading weights, so long-context serving may require distribution, KV-cache quantization, explicit compression, or smaller admitted contexts.

• Compression / eviction: Research systems such as SnapKV^{[13]Reference 13SnapKV: Compressing KV Cache by Selecting Global Attention Patterns.https://arxiv.org/abs/2403.19925} and H2O^{[14]Reference 14H2O: Heavy-Hitter Oracle for KV Cache Eviction in LLMs.https://arxiv.org/abs/2310.16786} reduce the cache by keeping only the tokens that seem most useful for future attention.
• Quantization: Storing KV cache in FP8 instead of FP16 halves the bytes per cached value, which roughly doubles KV-cache-limited capacity when the cache is the bottleneck.

3. Distributed inference

In Tensor Parallelism (TP), a runtime may shard KV heads across ranks when the model layout permits it. If the number or grouping of KV heads doesn't divide cleanly across ranks, a runtime may replicate some KV state instead. Capacity planning must use the actual deployed layout, not assume ideal division.

Paged allocation still happens per rank, but logical block growth has to stay aligned across ranks so token positions 0-15, 16-31, and so on map to the correct local KV blocks on every worker.

The physical block IDs don't have to match across GPUs. Consistent logical bookkeeping is the invariant: each rank must know which local block corresponds to each logical block for its shard of the cache.

Exact coordination is runtime-specific. Capacity planning needs a safer rule: profile each rank's local KV allocation after sharding or replication instead of assuming the global tensor-payload bytes divide perfectly by TP degree.

The helper below is deliberately pessimistic. It isn't a runtime simulator; it prevents an optimistic admission limit when you haven't verified the deployed engine's physical layout.

---

Mastery check

Key concepts

• KV cache: Stores old Keys and Values so decode doesn't recompute them on every step.
• Fragmentation: Lost usable HBM from empty tails, scattered gaps, or worst-case reservations.
• PagedAttention: Splits cache into fixed-size logical and physical blocks connected by a block table.
• Continuous batching: Rebuilds active batch each decode step so finished requests free slots immediately.
• Copy-on-write: Lets forked decoding branches share existing blocks until one branch needs a private write; independent request reuse requires prefix-cache matching.

What strong answers show

• Foundational: Explains why the KV cache speeds decode but still grows with sequence length and active requests.
• Foundational: Calculates bytes per token from layers, KV heads, head dimension, and precision.
• Intermediate: Distinguishes internal fragmentation, scattered free gaps, and worst-case reservation waste in a naive contiguous allocator.
• Intermediate: Explains how PagedAttention uses logical blocks, physical blocks, and a block table to allocate only live cache state.
• Advanced: Connects PagedAttention to continuous batching, branch copy-on-write, optional cross-request prefix caching, and scheduler-level preemption decisions.
• Advanced: Separates allocator optimizations from architecture optimizations such as GQA, MQA, and KV-cache quantization.
• Advanced: Explains why prefill and decode remain different bottlenecks even after PagedAttention.

Follow-up questions

When KV serving breaks down

KV cache is treated like model weights

• Symptom: Capacity planning looks fine on paper, then long chats trigger OOM as soon as concurrency rises.
• Cause: Static weights were counted, but dynamic per-request KV growth was ignored.
• Fix: Budget GPU memory for weights and for worst realistic live KV state at your target concurrency.

Fragmentation is blamed on batching alone

• Symptom: Throughput stalls even after scheduler tuning.
• Cause: The batch policy improved, but the allocator still strands large empty tails and gaps.
• Fix: Evaluate scheduler behavior and allocator behavior separately. PagedAttention helps because it changes memory packing, not because it changes the attention math.

Throughput numbers are quoted without workload shape

• Symptom: Benchmarks look amazing, but production gains disappoint.
• Cause: Reported speedups depended on sequence-length skew, latency target, or decoding workload that did not match your route mix.
• Fix: Compare serving systems under the same latency target, prompt lengths, output lengths, and concurrency pattern.

Prefill and decode are collapsed into one bottleneck

• Symptom: Teams optimize decode memory layout, but TTFT still swings wildly.
• Cause: Decode is often memory-bandwidth-sensitive, but prefill is a separate compute-heavy phase that can still interfere with live traffic.
• Fix: Track prefill and decode separately, then decide whether you need chunked prefill, disaggregation, or cache compression.

Legacy swap or offload is assumed to be free recovery

• Symptom: A runtime uses CPU swap or another offload path and latency explodes.
• Cause: Moving cache preserved work, but PCIe transfer and restore time were ignored. Current vLLM V1 removed KV-cache swapping and recomputes preempted work instead.
• Fix: Treat offload as a runtime-specific tradeoff, not a free safety valve. Compare it against recompute under your actual prompt lengths and hardware path.

PagedAttention is expected to shrink bytes per token

• Symptom: A team adopts vLLM but still can't fit the desired context length.
• Cause: Allocation waste dropped, but the mathematical KV footprint per token stayed the same.
• Fix: Use GQA, MQA, KV quantization, or cache compression when the per-token cache itself is too large.

---

KV-cache serving rules

• In memory-limited serving configurations, KV cache capacity can limit batch size before raw compute does.
• Naive contiguous allocation can waste roughly 60-80% of KV memory on real traces.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}
• Fixed-size non-contiguous blocks avoid variable-sized KV gaps and bound per-sequence tail waste within the block pool.
• Copy-on-write supports forked branches; reuse across independent requests also requires compatible prefix matching and isolation.
• Techniques like GQA reduce the size of the KV cache, while PagedAttention makes that smaller cache pack efficiently.

The memory-capacity story is complete: PagedAttention turns fragmented KV allocation into a compact block pool, which can raise serving throughput when memory is the cap. The next step is to reuse cache work across compatible requests. In Prefix Caching and Prompt Caching, you'll see how repeated policy text, tool schemas, and shared instructions can avoid repeated prefill work without bypassing isolation rules.

Practice drill

Before moving on, build a one-page serving note for a route that handles long code-assistant sessions:

1. Calculate KV bytes per token for one candidate model, then recalculate after switching from full multi-head KV to GQA, MQA, FP8 KV, or another cache-compression choice.
2. Sketch a block table for three live requests where one finishes, one is canceled, and one forks into two tool-use branches.
3. Write acceptance criteria for prefix reuse: exact token prefix, matching release and tenant isolation key, read-only shared blocks, and copy-on-write on divergence.

If the note can't explain both bytes-per-token pressure and allocator waste, the serving design isn't ready for a capacity review.