KV Cache & PagedAttention

An internal coding assistant receives a repository question with system instructions, file excerpts, a failing test, and earlier tool results. When it emits its next token, it still needs to attend to that history. Recomputing every old attention state at every step would turn one response into repeated replay.

Request A keeps the attention's Key (K) and Value (V) vectors after their first computation. Each decode step appends one new K/V pair and reads the cached history. That running state is the KV cache (Key-Value cache). Grouped-Query Attention (GQA) and Multi-Query Attention (MQA) already shrink each token's footprint.

The remaining problem is placement. The cache grows with every token and concurrent request, so variable-length traffic can strand expensive GPU memory. PagedAttention, introduced with vLLM, borrows operating-system paging so live request state sits in small reusable blocks instead of one oversized contiguous reservation per request.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Follow Request A from its first K/V write through block allocation, preemption, reuse, and cross-machine transfer. At each boundary, ask whether the limit is cache bytes, block placement, scheduler time, or transfer bandwidth.

What problem does the KV cache solve, and what new problem does it create?

Answer

It avoids recomputing old keys and values at every decode step, which makes token generation much faster. It creates a GPU-memory problem because cached K/V state grows with sequence length, layers, KV heads, precision, and concurrent requests.

---

Why the KV cache exists

Request A relies on two ideas from earlier lessons. Transformer self-attention computes Query, Key, and Value vectors so the current token can weigh earlier tokens.^{[2]Reference 2Attention Is All You Need.https://arxiv.org/abs/1706.03762} Autoregressive generation then produces one token at a time, with each new token able to attend to everything that came before it.

Autoregressive generation

Call the assistant's first request A. Suppose it has already processed $t-1$ tokens. What must the next step carry forward? Without a KV cache, it would re-run the Key and Value projections for every earlier token. With a cache, A writes $k_t$ and $v_t$ once, then later queries read those stored vectors.

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

$\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}$

The current token's query $q_t$ is scored against every key in $K_{1:t}$ (dot product, scaled by $\sqrt{d_k}$). Softmax turns those scores into weights, and $V_{1:t}$ is blended with those weights. $K_{1:t}$ and $V_{1:t}$ are the Key and Value matrices for tokens 1 through $t$.

Without a cache, generating token $t$ recomputes Key and Value vectors for every earlier token. Per-step projection work grows with sequence length, making the full sequence quadratic in those projections. Caching removes that repeated work, but attention still has to read the growing history.

KV cache: cache K, V from previous steps

At step $t$, compute $q_t, k_t, v_t$ for the new token and append $k_t, v_t$ to the cache. Request A's first five tokens look like this:

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 sensitive to memory bandwidth even after caching.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Why doesn't the KV cache make long-context decode constant time?

Answer

The cache removes repeated K/V projection work for old tokens, but each new query still attends over the cached history. As the cache grows, the model must read more K/V state per token, so decode remains sequence-length-sensitive and can become memory-bandwidth-sensitive.

---

Those five tokens already show the next problem: even a tiny request writes a growing tensor into GPU memory. Real serving multiplies that cost by layers, KV heads, and concurrent requests.

KV cache memory analysis

Before writing a general formula, compare three concrete caches. Llama 3 uses GQA with 8 KV heads at every size; GPT-3 175B uses full multi-head attention (MHA).^{[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783[4]Reference 4Language Models are Few-Shot Learners.https://arxiv.org/abs/2005.14165}

Memory footprint examples (FP16)

For Llama 3 70B, one 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. Memory capacity can cap throughput before raw FLOPs do.

Llama 3 70B has 64 query heads but only 8 KV heads.^{[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783} If it stored a KV head per query head, the cache would be 2.5 MiB per token in FP16. GQA-8 drops that to 320 KiB per token.

At 4K context, that's 10 GiB versus 1.25 GiB for a single request. The architecture has already bought an 8× reduction before the allocator makes any decision.

Each token stores a Key vector and a Value vector across every layer and KV head:

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

For each token, store Key and Value (the $2$) across every layer and KV head. Each vector has $d_{\text{head}}$ dimensions, and $P_{\text{bytes}}$ is the stored precision. In MHA, $n_{\text{kv-heads}} = n_{\text{heads}}$. GQA and MQA use fewer KV heads, which shrinks the cache directly.^{[5]Reference 5GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.https://arxiv.org/abs/2305.13245[6]Reference 6Fast 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.

For Llama 3 70B (80 layers, 8 KV heads, head dimension 128, FP16), how many bytes does one token add?

Answer

Use $2 \times 80 \times 8 \times 128 \times 2 = 327{,}680$ bytes, or 320 KiB per token. That is Llama 3 70B's per-token cache, so a 4K-token sequence needs 1.25 GiB.

---

GQA shrinks bytes per token. It doesn't stop a naive allocator from reserving far more than those bytes. That's the next failure.

The memory fragmentation problem

In a naive serving system, each request gets one contiguous KV buffer. The engine doesn't know when generation will stop, so it often reserves the configured maximum sequence length, such as 8192 tokens, up front.

Request A stops after 600 tokens. What can Request B use from A's untouched tail? Nothing. The space belongs to A until its whole request ends.

Types of waste

That reservation wastes memory in three ways the vLLM paper names:^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

1. Internal fragmentation: Request A reserves 8192 slots and finishes after 600 tokens. The unused tail sits inside A's buffer and can't be handed to request B.
2. External fragmentation: As A, B, and later requests enter and leave, free memory becomes scattered holes. Total free bytes may be enough for a new request, but no single contiguous region is large enough.
3. Reservation waste: Even slots that will eventually fill are held for A's entire lifetime, so B can't use them while A is still running.

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

Why does naive contiguous KV allocation waste memory on variable-length requests?

Answer

The engine often reserves the maximum possible sequence length for each request before it knows when generation will stop. Short requests leave unused tail space, and completed requests can leave scattered free gaps that aren't useful for a new large contiguous reservation.

---

If max-length reservations waste most of the pool, the next question is how to allocate only live tokens without needing one huge contiguous region.

PagedAttention (vLLM)

Virtual memory for KV cache

PagedAttention adapts OS paging to LLM serving.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} The KV cache is divided into fixed-size blocks. After its ablation, 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}

Blocks are assigned only as requests need them, and they don't have to sit next to each other in physical memory. When a request finishes, its blocks go back to the pool immediately. Waste is mostly the final partially filled block.

• Logical Blocks: The sequence as the model sees it (contiguous indices 0, 1, 2...).
• Physical Blocks: Where the data lives in GPU memory (non-contiguous, scattered).
• Block Table: The map from logical block indices to physical block addresses.

The toy manager later uses block_size = 4 so you can watch request A fill a block. Production defaults are larger.

What does the block table do in PagedAttention?

Answer

It maps each request's logical token blocks, such as tokens 0-15 and 16-31, to physical GPU blocks that may live anywhere in the shared pool. The model sees a contiguous logical sequence while the allocator packs non-contiguous physical memory efficiently.

Efficiency gains

Live-token cache utilization is the fraction of the KV pool that holds tokens still needed by live requests, not GPU SM occupancy, tensor-core MFU, or end-to-end throughput. A nearly full live-token pool can still leave decode slow if kernels, batch shape, or prefill interference bind first.

Because only the last partially filled block of each sequence can sit unused (plus a little block-table metadata), the vLLM authors report near-zero waste, under 4% on their traces.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} On top of that packing gain, the paper's headline result is 2-4× higher throughput at comparable latency versus FasterTransformer and Orca, with bigger gains on longer sequences and more complex decoding.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Those ratios belong to one dated experiment, not to every serving stack. The authors ran OPT 13B/66B/175B and LLaMA 13B on Google Cloud A2 instances with NVIDIA A100 GPUs, drove arrivals from synthetic ShareGPT and Alpaca traces, compared against custom-scheduled FasterTransformer and Orca variants, and measured normalized end-to-end latency over long traces while checking model accuracy. Re-run the comparison at your model, precision, prompt/output distribution, concurrency, and latency SLO before turning a paper ratio into a capacity promise.

On ShareGPT, the same paper's detailed plots go as high as 22× versus FasterTransformer, because that baseline combined contiguous reservations with coarse request-level batching. Treat that as a workload- and baseline-specific result, not a universal speedup.

Block size is a real trade-off. Smaller blocks cut tail waste and make sharing finer, but they add block-table lookups and can hurt kernel efficiency. Larger blocks are more regular to read, 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}

Why isn't the smallest possible block size always best?

Answer

Smaller blocks reduce unused tail space, but they create more block-table entries and less regular memory access for kernels. Larger blocks are easier for kernels to consume but waste more space in the final partially filled block, so the best size depends on traffic lengths and kernel efficiency.

Paging changes the kernel contract

Non-contiguous physical blocks recover stranded HBM, but the attention kernel must follow the block table and gather K/V from those addresses. PagedAttention therefore needs paged-attention kernels; a contiguous-cache kernel isn't a drop-in consumer.

The original vLLM microbenchmark measured 20-26% higher attention-kernel latency than FasterTransformer's contiguous kernel, from block-table walks, extra branches, and variable lengths.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180} That's a kernel-only comparison. End-to-end throughput still rose in the paper's A100 experiments because recovered HBM admitted larger batches, so measure allocator capacity and kernel speed together.

vAttention is a counter-design. It reserves a contiguous virtual-address range for each KV cache and backs virtual pages with physical GPU memory on demand through CUDA virtual-memory APIs.^{[7]Reference 7vAttention: Dynamic Memory Management for Serving LLMs without PagedAttentionhttps://arxiv.org/abs/2405.04437} The kernel still sees contiguous virtual addresses, so existing contiguous attention kernels can run without a paged-KV interface. Complexity moves into virtual-memory mapping, page commitment, and platform support.

Neither layout wins by definition. PagedAttention has broad serving-engine adoption and explicit block-sharing. A contiguous-virtual design may reuse more existing kernels but depends on the runtime, driver, page granularity, and workload. Compare end-to-end throughput, latency, memory utilization, and implementation constraints on the target stack.

What cost does non-contiguous PagedAttention introduce, and how does vAttention change the trade-off?

Answer

PagedAttention needs kernels that follow block tables across non-contiguous physical storage. vAttention keeps a contiguous virtual address range while mapping physical pages on demand, which can reuse contiguous-cache kernels but shifts complexity into GPU virtual-memory management.

---

Implementation sketch

The manager below is a CPU-side sketch of the block table. vLLM keeps this bookkeeping on the host; custom CUDA kernels on the GPU follow the table when they read K and V.

PagedKVCacheManager starts with a stack of free physical IDs, highest first, so the first pop() returns 19 in a 20-block pool. allocate hands request A one block. Each append_slot returns the physical block index and slot offset for the new token. When A later needs a fifth token with block_size = 4, the manager pops block 18.

allocate grabs one block. append_slot pulls the next block only when the current one is full. free returns every block A held, so B can keep running while those IDs go back on the stack. This toy pool has no variable-sized holes; a production runtime still has weights, kernels, and allocator state outside the KV block pool.

Tracing a small example

The manager uses block_size = 4 and num_blocks = 20. Free IDs form a stack, so pop() yields 19, then 18, then 17.

First, Request A arrives. allocate("A") pops physical block 19, giving the table {"A": [19]} and sequence length 0.

After four generated tokens, block 19 holds offsets 0 through 3, and seq_lens["A"] = 4.

At token five, token_idx = 4 and 4 % 4 == 0, so block 19 is full. append_slot("A") pops 18, writes at offset 0, and leaves the table as {"A": [19, 18]}, matching A (18, 0) in the output.

Next, Request B arrives. allocate("B") pops block 17, so the tables are {"A": [19, 18], "B": [17]}.

Finally, A finishes. free("A") returns 19 and 18; B still holds 17, leaving 19 free IDs in the 20-block pool.

Blocks are grabbed one at a time and returned when the request completes. Real engines add a reference count per physical block (for shared prefixes) and copy-on-write when a sequence writes into a shared block.

PagedAttention doesn't change the attention math. It changes how K and V sit in HBM so the GPU can find them without stranding empty tails. Throughput rises when that recovered memory admits more live work.

In the toy manager, when is a new physical block allocated?

Answer

A request starts with one block. During decode, append_slot allocates another block only when the current sequence length is a positive multiple of block_size, meaning the previous block is full.

Packing live blocks raises the admission ceiling. Now push Request A until it needs one more block and the pool has none. The scheduler still has to decide how A gives up its place and gets it back.

Preemption when the pool is empty

vLLM pairs PagedAttention with a scheduler. Memory is a shared pool, so an exhausted pool turns allocation into a scheduling decision: delay A, evict another request, or recover A's cache later.

In a heavily 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.^{[8]Reference 8Optimization 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.^{[8]Reference 8Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html}

Recompute spends extra FLOPs; swap spends PCIe bandwidth. Both paths make A pay before it can resume, so frequent preemption belongs in the capacity plan rather than in the happy-path throughput estimate.

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 Llama 3 70B (80 layers, 8 KV heads, head dimension 128, FP16 cache) with an 8K context window. 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% leftover 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.

Why doesn't PagedAttention increase capacity for requests that all use the full maximum context?

Answer

If every request fills every reserved token slot, there is little fragmentation to remove. PagedAttention helps most when request lengths vary, related branches can share blocks, or requests finish early, because the scheduler can allocate based on actual blocks in use.

---

Packing live blocks raises how many requests fit. It doesn't keep the GPU busy when one long decode holds a static batch hostage. To see the second bottleneck, keep the same Request A and compare its finish time with a longer Request B.

Continuous batching (iteration-level batching)

PagedAttention pairs especially well with continuous batching (also called iteration-level scheduling). The dedicated continuous batching lesson owns the scheduler. This lesson stays on the memory interaction.

Static batching limitations

A needs 20 decode iterations while B needs 200. In traditional static batching, the system waits for $N$ requests, bundles them, and processes that batch until all requests finish. A completes early, but its slot remains tied to B's long tail, so the shorter request contributes no useful work for the remaining iterations.

The continuous batching approach

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

That replacement keeps a batch slot productive instead of waiting for B. Continuous batching and PagedAttention solve different bottlenecks, but they work especially well together: one keeps compute busy, and the other makes A's freed memory reusable immediately.

Continuous batching turns the batch into a sliding window of live work. 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.^{[9]Reference 9Orca: A Distributed Serving System for Transformer-Based Generative Models.https://www.usenix.org/conference/osdi22/presentation/yu}

That number compares iteration-level scheduling to request-level FasterTransformer on that model, not to PagedAttention. vLLM then showed that Orca-style scheduling still needs paged memory: otherwise variable lengths reintroduce fragmentation as the batch churns.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Why do continuous batching and PagedAttention work well together?

Answer

Continuous batching creates and removes active requests at every decode iteration. PagedAttention can recycle finished requests' KV blocks immediately, so memory availability tracks actual live tokens instead of stale static reservations.

---

Iteration-level admission creates and frees live sequences constantly. Block tables also make a different trick possible: sharing physical blocks. That sharing has two very different policies.

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.^{[10]Reference 10Automatic Prefix Cachinghttps://docs.vllm.ai/en/stable/design/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.

Why is PagedAttention block sharing not the same as cross-request prefix caching?

Answer

Copy-on-write safely shares blocks for already-related decoding branches. Cross-request reuse also needs an exact-prefix matching and isolation policy before an independent request may reference previously cached blocks.

RadixAttention (SGLang)

Newer engines like SGLang extend this with RadixAttention.^{[11]Reference 11SGLang: 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. On a cache hit, it reuses existing KV blocks immediately, so no prefix recomputation is needed. On a miss, it computes only the new tokens.

That makes it particularly effective for multi-turn chat and agentic workloads where long prompt prefixes repeat across calls.^{[11]Reference 11SGLang: 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.^{[12]Reference 12FlashInfer: 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[13]Reference 13FlashAttention: 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.^{[13]Reference 13FlashAttention: 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.^{[12]Reference 12FlashInfer: 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.

How should you explain PagedAttention versus FlashAttention in one sentence?

Answer

PagedAttention manages where cached K/V tensors live in HBM and how they are shared; FlashAttention is an IO-aware kernel for computing attention without materializing huge intermediate score matrices.

---

Reducing KV cache at the architecture level

Return to Request A's per-token bill. PagedAttention can pack those bytes, but it can't make the tensor payload smaller. That requires changing how much K/V state the model produces in the first place.

PagedAttention optimizes how memory is managed by changing allocation. Model architecture changes optimize how much memory is needed in the first place.

Grouped-Query Attention (GQA) shrinks the baseline cache. Instead of a Key and Value head per query head, GQA groups query heads so they share KV heads. Ainslie et al. found intermediate group counts recovered much of MHA quality while keeping MQA-like inference benefits after uptraining; other models still need their own quality evaluation.^{[5]Reference 5GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.https://arxiv.org/abs/2305.13245}

Llama 3 70B is the worked example: 64 query heads, 8 KV heads, so each token's cache is 8× smaller than full MHA with those query heads.^{[3]Reference 3The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783}

Multi-Head Latent Attention (MLA) takes a different architectural route: it jointly compresses keys and values into a learned low-rank latent representation, so its cache contract isn't just a smaller n_kv_heads value.^{[14]Reference 14DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Modelhttps://arxiv.org/abs/2405.04434} MLA can shrink the cache further, but it needs an MLA-aware model and execution path. It isn't a serving switch for a GQA checkpoint.

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.

Why are GQA and PagedAttention complementary rather than competing optimizations?

Answer

GQA reduces the number of KV heads, shrinking bytes per token. PagedAttention packs those bytes efficiently across variable-length requests. One lowers the amount of cache; the other lowers waste in how that cache is allocated.

---

Practical considerations

Start capacity planning with two separate ledgers. The weights are static parameters loaded once at startup and shared across requests. The KV cache is per-request state that grows as each conversation proceeds. If a GPU is sized for weights alone, a handful of long conversations can still trigger an out-of-memory error.

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[15]Reference 15DistServe: 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 (splitting a long prompt across iterations) keeps large prompts from monopolizing one step.^{[8]Reference 8Optimization and Tuning.https://docs.vllm.ai/en/latest/configuration/optimization.html[16]Reference 16Sarathi-Serve: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills.https://arxiv.org/abs/2308.16369} At larger scale, disaggregated serving can still split prefill and decode across pools to keep time to first token (TTFT) and inter-token latency smoother.^{[15]Reference 15DistServe: 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. A Llama 3 70B-shaped GQA cache at 128K tokens needs 40 GiB in FP16. At that scale, KV memory can rival or exceed the room left after loading weights, so long-context serving may need distribution, KV-cache quantization, explicit compression, or smaller admitted contexts.

• Compression / eviction: Research systems such as SnapKV^{[17]Reference 17SnapKV: Compressing KV Cache by Selecting Global Attention Patterns.https://arxiv.org/abs/2403.19925} and H2O^{[18]Reference 18H2O: 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.

The right lever depends on where Request A's bytes are stuck. Ask which boundary is limiting before choosing a technique.

Quantize local blocks. KIVI's 2-bit path uses per-channel quantization for keys and per-token quantization for values: its experiments found persistent high-magnitude key channels, but no matching fixed pattern in values. It also keeps a recent-token residual in full precision.^{[19]Reference 19KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachehttps://arxiv.org/abs/2402.02750} That changes the representation and bytes stored in each local KV block. Logical token positions and block-table mapping stay the same, while quality and latency still need validation on your engine. Check kernel support, dequantization cost, and task quality on the deployed model.

Compress transfers. SnapKV and H2O change which tokens remain in a runtime cache. CacheGen addresses a different boundary: it encodes precomputed KV into compact, bandwidth-adaptive bitstreams, streams chunks, and decodes them back into regular KV tensors before attention.^{[20]Reference 20CacheGen: KV Cache Compression and Streaming for Fast Large Language Model Servinghttps://arxiv.org/abs/2310.07240} Storage and on-wire bytes change; attention math, the local KV footprint after reconstruction, and the block allocator stay the same.

Disaggregate the data plane. Mooncake separates prefill and decode, pools CPU/DRAM/SSD resources with GPU workers, and transfers paged KV blocks over RDMA when a reuse decision justifies the movement.^{[21]Reference 21Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving.https://arxiv.org/abs/2407.00079} Blocks change location and scheduler path, but bytes per token stay fixed and remote transfer still costs time. Measure time to first token, inter-token latency, throughput, and network traffic under the target workload.

Compare these as separate interventions with the same model, hardware, precision, prompt/output distribution, concurrency, and correctness target before changing a capacity or latency promise.

3. Distributed inference

In tensor parallelism (TP), a runtime may shard KV heads across ranks when the model layout permits it. TP splits a layer's weights (and often its KV heads) across GPUs so each rank holds a slice. 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.

In tensor-parallel serving, do physical KV block IDs need to match on every GPU?

Answer

No. Each rank stores its local KV layout, sharded or replicated as configured, so physical block IDs can differ. The scheduler must keep logical token-block mapping consistent so each rank knows which local block corresponds to the same logical positions.

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.

---

KV-cache serving rules

• In memory-limited serving, KV cache capacity can cap batch size before raw compute does.
• Naive contiguous allocation used only 20.4-38.2% of KV memory for live tokens on the vLLM paper's traces, about 60-80% waste.^{[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 leftover space to the last partial block.
• Copy-on-write supports forked branches; reuse across independent requests also needs compatible prefix matching and isolation.
• GQA and MQA reduce the number of KV heads; MLA changes the cached representation; PagedAttention packs that state across variable-length requests.^{[14]Reference 14DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Modelhttps://arxiv.org/abs/2405.04434}

Request A's cache now has a complete lifecycle: PagedAttention turns fragmented allocation into a compact block pool. GQA, MLA, quantization, and compression reduce or reshape the payload; disaggregation changes where it lives. When requests share a system prompt, tool schema, or repo guide, Prefix Caching and Prompt Caching adds matching and isolation rules that can skip repeated prefill.

For a production trace, inspect block-pool occupancy, copy-on-write forks, and isolation keys together, then compare measured numbers with the serving table.