--- title: "PagedAttention: how vLLM manages the KV cache" description: "A systems guide to PagedAttention, KV blocks, block tables, copy-on-write, fragmentation, and what vLLM’s memory manager changes." canonical_url: "https://fanout.sh/blog/pagedattention-vllm-kv-cache" md_url: "https://fanout.sh/blog/pagedattention-vllm-kv-cache.md" last_updated: "2026-08-03" access: "public" --- # PagedAttention: how vLLM manages the KV cache A systems guide to PagedAttention, KV blocks, block tables, copy-on-write, fragmentation, and what vLLM’s memory manager changes. - Author: Suraj Gaud - Published: 2026-08-03 - Track: Inference engineering - Tags: PagedAttention, vLLM, KV cache, LLM inference, GPU memory PagedAttention is often introduced with one sentence: it is virtual memory for the KV cache. The analogy is useful, but it skips the part an inference engineer needs. What is being paged? Why did contiguous allocation waste so much memory? What changes inside attention, and what stays exactly the same? This guide follows the[PagedAttention paper](https://arxiv.org/abs/2309.06180)and the[vLLM design documentation](https://docs.vllm.ai/en/latest/design/paged_attention/). ## The problem is a cache with an unknown ending Every active sequence carries keys and values from earlier tokens. The cache grows during generation and disappears when the request ends. The server knows the prompt length, but it does not know the final output length. Two requests that start together may finish hundreds of decoding steps apart. A simple allocator can reserve one large contiguous region for each request. That makes addressing easy, but it asks the server to guess how much each sequence will eventually need. Guess low and the cache must move or be reallocated. Guess high and scarce GPU memory sits empty while other requests wait. The effect reaches the scheduler. Unusable cache capacity reduces the number of sequences that can be batched, which reduces serving throughput. ## Contiguous allocation wastes memory in two ways Internal fragmentation is empty space inside an allocation. If a request reserves room for 2,048 output tokens and stops after 120, most of that reservation was never useful. External fragmentation is free memory split into pieces that cannot satisfy a larger contiguous request, even when the pieces add up to enough bytes. The original vLLM evaluation found both over-reservation and fragmentation in earlier serving systems. Its exact throughput results belong to that hardware and workload, not every modern deployment. The durable finding is simpler: KV memory must grow and shrink with live sequences, while contiguous reservations assume a stable size. Use Fanout’s[KV-cache calculator](/labs/kv-cache)first if the underlying tensor size is unfamiliar. PagedAttention changes allocation, not the bytes required by each stored key and value. ## Logical blocks separate a sequence from physical memory PagedAttention divides a sequence’s KV cache into fixed-size logical blocks. Each block holds the keys and values for a fixed number of tokens. The sequence sees logical block 0, then 1, then 2. Those blocks do not need to sit next to one another in GPU memory. A block table maps each logical block to a physical KV block. The attention kernel uses that table to find the keys and values needed for the current query. This indirection is the main move. The sequence stays logically contiguous while the allocator can place physical blocks wherever capacity is available. The server can now allocate cache as tokens arrive. It does not need to reserve room for the maximum possible output on the first decoding step. ## Walk one request through the allocator Suppose a block holds 16 token positions and a prompt contains 30 tokens. Prefill produces the prompt’s keys and values. The cache manager assigns two physical blocks and records them in the request’s block table. The first block is full. The second contains 14 tokens and two empty positions. The next two decoded tokens fill those positions. Only when the second block becomes full does the allocator request a third physical block. If the request ends at 34 total tokens, the final block contains two live positions and 14 unused ones. That last block is the principal internal waste. With fixed-size blocks, the waste is bounded by less than one block per sequence rather than by a speculative maximum-length reservation. ## PagedAttention changes addressing inside attention Ordinary attention conceptually reads the query, compares it with cached keys, and combines cached values. PagedAttention preserves that computation. What changes is how the kernel locates the cache. It reads keys and values block by block through the request’s logical-to-physical mapping. The tokens can therefore be logically adjacent without being physically adjacent. This is why PagedAttention is more than placing a general allocator in front of an unchanged kernel. The kernel must understand the block layout and gather the correct cache fragments efficiently. The[Fanout PagedAttention paper note](/daily/2026-07-21-pagedattention)is a useful companion when you want the paper’s figures beside this allocator walkthrough. ## Copy-on-write makes shared prefixes practical Parallel sampling and beam search can create several sequences with the same prompt. Copying the prompt cache for every branch would repeat a large amount of identical state. Paged allocation lets several logical block tables point to the same physical prompt blocks. Reference counts record how many sequences share each block. When one branch needs to modify a shared final block, the manager allocates a new block and copies only that block. The other branch keeps the original. That is copy-on-write at KV-block granularity. The benefit depends on the workload. It is most visible when branches share a long prefix and diverge only in their generated suffixes. Prefix caching uses a related idea across requests, but it adds cache lookup and validity rules. Reusing memory is safe only when the model, adapters, prompt tokens, and relevant cache state match. ## Better memory use creates room for a larger batch PagedAttention does not make one token’s key and value vectors smaller. It makes the available cache pool easier to allocate and share. That distinction matters when reading throughput claims. If an engine fits more live sequences into the same GPU memory, it has more candidates to place in each decoding iteration. The GPU can do useful work for more users at once. The gain therefore travels through a chain: 1. Reduce wasted or duplicated KV capacity. 1. Admit more active sequences without exceeding the cache budget. 1. Form larger or steadier execution batches. 1. Raise throughput while holding a latency target. Break any link in that chain and the realized gain may shrink. A compute-saturated workload will not improve merely because some cache blocks became free. ## The block size is a real tradeoff Smaller blocks reduce the unused tail in each request. They also create larger block tables and more allocation metadata. Larger blocks reduce bookkeeping and can make memory access simpler, but they waste more capacity when many requests end with nearly empty final blocks. There is no universal block size detached from the kernel, model, workload, and hardware. The right question is not “which block size is best?” It is “which size gives this engine the best latency and throughput under the sequence lengths we actually serve?” That answer comes from workload replay, not the operating-system analogy. ## PagedAttention does not solve admission control Efficient allocation still has a hard capacity limit. If live sequences require more KV blocks than the pool contains, the scheduler must queue, preempt, recompute, swap, or reject work. Current[vLLM optimization guidance](https://docs.vllm.ai/en/latest/configuration/optimization/)warns that preemption and recomputation can damage end-to-end latency. A healthy server therefore watches more than nominal free memory. - KV-cache utilization - Running and waiting sequences - Preemption count - Prompt and output length distributions - Time to first token - Inter-token latency The allocator and scheduler form one control loop. Memory decides which sequences can remain active; scheduling decides which active tokens execute next. ## Keep the tensor formula beside the allocator model PagedAttention answers where the cache lives. It does not replace the calculation for how much cache a token creates. For a conventional decoder cache, the useful starting point remains: 2 × layers × KV heads × head dimension × tokens × batch × bytes per element Grouped-query attention can reduce the KV-head term. Lower-precision cache formats can reduce bytes per element. Neither change is caused by paging. The[KV-cache formula guide](/blog/kv-cache-formula-llm-inference-memory)works through those units and separates cache memory from model-weight memory. Keep both models in your capacity sheet: tensor bytes determine demand, while block allocation determines how efficiently the pool satisfies it. ## What to inspect in a real serving engine Start with the request’s block table. Confirm when blocks are allocated, freed, shared, and copied. Then inspect the scheduler. Find the token budget for one iteration, the admission rule, and what happens when no free cache block remains. Finally, replay your own prompt and output distributions. Average lengths hide the long requests that occupy blocks for the most iterations. PagedAttention’s lasting lesson is not that GPU memory should imitate an operating system. It is that a dynamic sequence workload needs a dynamic memory model, and that model must extend from the allocator into the attention kernel and scheduler. That allocator-to-scheduler boundary is central to Fanout’s[inference engineering roadmap](/inference-eng). It is where a model-level cache becomes a production capacity decision. --- This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included. Browse the public content map: https://fanout.sh/sitemap.md