Core Mechanics of LLM Inference Serving: A Deep Dive into KV Cache and PagedAttention

Training large models grabs the headlines, but inference is where the compute bill actually lands in production. Every conversation, every agent step, every autocomplete is a request for the GPU to generate tokens. The gap between a rough inference serving stack and an excellent one is not 10%. When vLLM launched, the team reported throughput gains of up to 24x over Hugging Face Transformers.

Where does such a massive gap come from? The answer isn't faster matrix multiplication — it's three things most application developers never touch: how the KV cache is stored in GPU memory, how requests are batched, and how work is scheduled across the two phases of generation.

Two Phases: Prefill and Decode

An LLM generates one token at a time, and each new token depends on all previous tokens. Under the hood, a single request goes through two phases with completely different performance characteristics.

The Prefill phase processes the entire prompt in a single forward pass. All prompt tokens flow through the model in parallel, meaning large matrix multiplications keep the GPU's compute units busy. Prefill is compute-bound. Its output is the first generated token, so prefill time largely determines time to first token (TTFT).

The Decode phase generates every subsequent token, one forward pass per token. At each step, each request processes just one new token, but to compute attention it must read the keys and values of all previous tokens. So each step loads the model weights plus the request's full cached history from GPU memory, does relatively little math, and produces one token. Decode is memory-bound: the bottleneck is how fast bytes move from GPU memory (HBM), not how fast the GPU computes. vLLM's tuning docs describe this split exactly this way: "compute-bound (prefill) and memory-bound (decode)."

This asymmetry drives almost every design decision that follows. Because decode is bound by memory bandwidth, the main way to get more performance out of the GPU is to decode multiple requests simultaneously. Loading the weights once and using them for 64 requests is far better than loading them 64 times. Batch size is the lever, and what limits batch size is memory — specifically, the KV cache.

Time to First Token (TTFT) and Inter-Token Latency (ITL) are the two key metrics for measuring LLM serving experience, but they are dominated by different phases. TTFT measures the time from when a request is sent to when the first token comes back, and is primarily determined by the prefill phase — the longer the prompt, the larger the model, and the higher the concurrency, the longer prefill queuing and computation take. ITL measures the interval between two consecutive output tokens and is primarily determined by the decode phase — it depends on memory bandwidth, batch size, and the volume of KV cache reads. A serving stack may have very low TTFT (fast prefill scheduling) but very high ITL (an overly large decode batch slows each step), or vice versa. Pricing and SLAs for cloud APIs from Google, Anthropic, and others typically impose separate limits on these two. Understanding this split helps you target the right fix during tuning: to lower TTFT, optimize prefill scheduling, enable prefix caching, and reduce prompt length; to lower ITL, control batch size, improve memory bandwidth utilization, and use chunked prefill to prevent long prompts from cutting in line.

What the KV Cache Is, and How Big It Actually Gets

In a Transformer's attention layers, each token is projected into a query, a key, and a value. When generating the n-th token, the model compares the n-th token's query against the keys of tokens 1 through n-1 and takes a weighted blend of their values. Those keys and values never change once computed, so recomputing them every step is wasted work. Inference engines store them in the KV cache. Prefill fills the cache for the prompt, and each decode step appends the new token's K and V.

How much memory does this need? A simple product:

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

Plugging in the published configuration of Llama 3.1 8B: 32 layers, 8 key/value heads (the model uses grouped-query attention, where 32 query heads share 8 KV heads), head dimension 128, and bf16 values at 2 bytes each:

2 × 32 × 8 × 128 × 2 = 131,072 bytes = 128 KiB per token

That sounds small until you multiply by context length: 1K tokens is 128 MiB, 8K tokens is 1 GiB, 32K tokens is 4 GiB, and 128K tokens (the model's maximum context) is 16 GiB.

The model weights are roughly 8 billion parameters × 2 bytes ≈ 16 GB. The memory required for a single full-context conversation is about equal to the entire model. The weights are shared across all requests, whereas the KV cache is per-request and grows with every generated token.

(Grouped-query attention is itself a KV cache optimization. With 32 KV heads instead of 8, every number above would be four times larger.)

The vLLM launch post gave a sense of scale for an older model: a single sequence's KV cache in LLaMA-13B can reach 1.7 GB. It also described the cache as dynamic: "its size depends on sequence length, and sequence length is highly variable and unpredictable." That unpredictability is the real problem.

Grouped-Query Attention (GQA), proposed by Ainslie et al. in 2023, is a compromise between multi-head attention (MHA) and multi-query attention (MQA). In standard MHA, each query head has its own independent key and value heads, and the KV cache scales proportionally to the number of heads; MQA has all query heads share a single set of K/V, which greatly shrinks the cache but loses quality. GQA groups query heads, with each group sharing one K/V head — Llama 3.1 8B, for example, splits 32 query heads into 8 groups, each with 4 query heads sharing 1 KV head. This shrinks the KV cache by 4x relative to MHA while staying close to MHA in quality. This is also why, given the same number of layers and head dimension, different models can have vastly different KV cache sizes: the number of KV heads is the key multiplier. When choosing or deploying a model, the number of KV heads should be treated as an inference cost metric just as important as parameter count.

The Problem: Memory Fragmentation

When generation begins, you don't know whether the answer will be 20 tokens or 2000. Early serving systems handled this the most direct way possible: reserve a contiguous chunk of GPU memory for each request, large enough to hold the maximum possible length.

The problems come in several forms: over-reservation — a request that finishes in 200 tokens still occupies space for 2048, and reserved-but-unused memory can't be used by anyone else; internal fragmentation — even within the reserved range, the unused tail sits idle for the entire lifetime of the request; external fragmentation — gaps left between contiguous allocations of different sizes that are too small to use.

The vLLM team measured it: existing systems waste 60%–80% of KV cache memory to fragmentation and over-reservation. Since memory limits batch size, and batch size limits decode throughput, a large portion of the GPU's potential is simply thrown away.

PagedAttention: Bringing Virtual Memory to the KV Cache

Operating systems solved this exact problem decades ago. Programs want a large, contiguous address space, but physical memory is fragmented. The OS divides memory into fixed-size pages, gives each process a contiguous virtual address space, and maintains a page table mapping virtual pages to physical locations.

PagedAttention, introduced in the vLLM paper (SOSP 2023, arXiv:2309.06180), applies the same idea to the KV cache. In the authors' words: "you can think of blocks as pages, tokens as bytes, and sequences as processes."

Here's how it works: KV memory is divided into fixed-size blocks, each holding the keys and values for a fixed number of tokens; each request sees a sequence of logical blocks that are contiguous from its own perspective; a block table maps each logical block to a physical block located anywhere in GPU memory; physical blocks are allocated on demand, only when the request's current block fills up; and the attention kernel is rewritten to follow the block table, gathering each request's K and V from wherever its blocks happen to live.

The payoff: memory waste only occurs in the request's last, not-yet-full block. The vLLM post reports this results in "under 4% waste." Nearly all KV memory now stores real data, so many more requests fit into a batch. The paper's headline result is that vLLM "improves the throughput of popular LLMs by 2-4x" compared to FasterTransformer and Orca at the same latency level, with even larger gains for longer sequences, larger models, and more complex decoding.

Sharing Comes for Free

Once memory is addressed indirectly through a block table, two requests can point to the same physical block. This matters for decoding strategies that create multiple outputs from a single prompt, such as parallel sampling ("give me 4 candidate answers") or beam search. The prompt's KV blocks are stored once and shared, with reference counting. Blocks are copied only when a branch needs to write (copy-on-write, another OS technique). The vLLM team reports this reduces memory usage for these methods "by up to 55%," meaning "up to 2.2x improvement in throughput."

Continuous Batching

Freeing up memory only helps if the scheduler actually fills it with work. Classic static, or request-level, batching doesn't do that.

With static batching, the server collects a batch of requests and runs them together until all of them finish. But generation lengths vary enormously. The Orca paper (OSDI '22) describes the problem precisely: under request-level scheduling, "a request that finishes earlier than the other requests in the batch cannot be returned to the client, and newly arrived requests must wait for the current batch to finish completely."

Orca's solution was iteration-level scheduling, now commonly called continuous batching. The scheduler reorganizes the batch on every model iteration (i.e., every decode step): requests that just produced their final token immediately leave the batch and return their results; newly arrived requests join at the next iteration; the batch stays full and the GPU stays busy.

Continuous batching and PagedAttention reinforce each other. Continuous batching constantly admits and evicts requests of unpredictable length — exactly the workload that fragments contiguous memory. Paged blocks make admitting new requests cheap: it takes only a few free blocks, not one large contiguous region.

When Memory Still Runs Out

Even with paging, a burst of many long requests can fill the KV cache. At that point vLLM preempts some requests to free their blocks. In vLLM V1, the default preemption mode is recomputation: a preempted request's KV is discarded and rebuilt later, rather than swapped to CPU memory, "because the overhead of recomputation is lower in the V1 architecture." If your logs show preemption warnings, the docs suggest giving vLLM more memory (gpu_memory_utilization, default 0.92), reducing max_num_seqs or max_num_batched_tokens, or sharding the model across more GPUs.

Beam Search and Parallel Sampling are two typical categories of "one prompt, multiple outputs" decoding strategies. Beam search maintains k candidate sequences, expanding and keeping the k with the highest probability at each step, aiming for a higher-quality single answer; parallel sampling independently samples multiple complete sequences from the same prompt to generate diverse candidates (such as "give me 4 versions"). What they have in common is that the prefix KV is identical, with differences arising only after the fork point. In traditional systems without block-level sharing, each of the k sequences holds a complete KV copy, so memory overhead grows linearly with k. PagedAttention's reference counting and copy-on-write let blocks before the fork be shared, with new blocks created only after the fork, significantly reducing memory and increasing batch capacity. This is also why vLLM's throughput gains are especially pronounced in beam search and parallel sampling scenarios.

Prefix Caching and Chunked Prefill

Two more techniques complete the picture. The first directly affects how you should write your prompts.

Automatic Prefix Caching

Real traffic is highly repetitive at the start. Every agent request typically begins with the same system prompt, the same tool definitions, and perhaps the same retrieved documents. Running prefill on those identical tokens over and over is pure waste.

With prefix caching, vLLM keeps the KV blocks from previous requests and reuses them. The design doc explains how matches are found: vLLM "hashes each kv-cache block by the tokens in the block and the tokens in the prefix before the block." Because the hash includes everything before the block, a block only matches when the entire prefix up to that block is identical. A lookup table maps hashes to cached physical blocks, so a new request whose first 3000 tokens match a previous request can skip straight to prefilling only the new suffix.

Cached blocks that are no longer in use are not immediately freed. They remain available for reuse and are evicted in LRU order when memory is needed. For multi-tenant deployments, vLLM supports an optional per-request cache_salt, mixed into the first block's hash, so different tenants can't reuse or probe each other's cached prefixes.

The docs note that prefix caching is "widely used by many public endpoints (e.g., OpenAI, Anthropic, etc.)." This is the mechanism behind the discounted "cached input" pricing those APIs offer.

The practical lesson for prompt design: put stable content first and variable content last. System prompt, tool definitions, long reference documents, then the user's actual question. Changing a single token early in the prompt (say, a timestamp in the system prompt) breaks the hash chain from that point onward and forces a full prefill.

cache_salt is a security parameter vLLM provides for multi-tenant scenarios. The default behavior of prefix caching is that as long as two requests have exactly the same prefix tokens, they hit the same cached blocks. This poses a potential risk in shared deployments — an attacker can craft specific prompts to probe whether another tenant has sent a certain prefix (a timing side channel). cache_salt mixes a random or secret string provided by the caller into the first block's hash, so that even when token content is identical, requests with different salts cannot hit each other's caches. In production facing untrusted users, you should always generate an independent salt per tenant or session and keep it safe. This follows the same idea as private cache keys in web caching and is the necessary trade-off between cache reuse and tenant isolation.

Chunked Prefill

Remember that prefill is compute-intensive and decode is memory-intensive. If a 10,000-token prompt arrives while 60 users are streaming responses, a naive scheduler runs that giant prefill as one step, and every streaming user sees a stall.

Chunked prefill splits a large prefill into small chunks and mixes them into the same step as decode. The vLLM docs describe the V1 strategy: each step has a token budget, max_num_batched_tokens; the scheduler prioritizes decode requests, and it "batches all pending decode requests before scheduling any prefill operations"; any remaining budget goes to pending prefills, and prefills that don't fit are chunked "automatically."

This improves inter-token latency because streams don't stall, and it improves GPU utilization because compute-intensive and memory-intensive work share each step. The budget is the tuning knob. Smaller values (the docs give 2048 as an example) favor smooth streaming output. Larger values favor time to first token, and the docs suggest going above 8192 on large GPUs for throughput. In vLLM V1, chunked prefill is "enabled by default whenever possible."

Putting It All Together: The Life of a Request in vLLM

Here's what happens to a request in a modern serving engine: the request arrives and is tokenized; the scheduler checks the prefix cache, and matching leading blocks are reused, so only the remainder needs prefill; at the next iteration, if enough free KV blocks exist, the scheduler admits the request, preempting another if necessary; its prefill runs, chunked if it's long, alongside other requests' decode steps within the token budget; each decode step appends one new token's K and V to the request's current block, allocating a new physical block only when that block fills; and when the request emits its stop token, it immediately leaves the batch, its blocks' reference counts drop, and they become cached-but-evictable.

Every step targets the same scarce resource: GPU memory for the KV cache, and gets the GPU to handle as many requests as memory allows.

What This Means If You Don't Run GPUs

Even if you only call a hosted API, these mechanics show up in your bills and latency charts: long prompts cost double — they consume compute during prefill (TTFT) and then memory on every decode step, so trim unnecessary context; prompt structure affects cost — stable prefixes hit the cache, and dynamic content at the top of the prompt breaks it; output length affects throughput more than you'd think — every generated token is a full decode step that occupies KV memory; TTFT and tokens per second are different metrics, driven by different phases, and a provider may be strong on one and weak on the other.

Key Takeaways

• Inference has two phases: prefill (parallel, compute-intensive, determines TTFT) and decode (one token per step, memory-intensive).
• The KV cache is the bottleneck. For Llama 3.1 8B, that's 128 KiB per token, or 16 GiB at a full 128K context — roughly the size of the model itself.
• Contiguous allocation wastes 60–80% of KV memory. PagedAttention uses fixed-size blocks and a block table, like OS virtual memory, cutting waste to under 4% and delivering 2–4x throughput in the paper.
• Continuous batching (Orca's iteration-level scheduling) reorganizes the batch every step, with finished requests leaving immediately and new requests joining immediately.
• Prefix caching reuses KV blocks for identical prefixes via chained block hashing, so put stable prompt content first.
• Chunked prefill prioritizes decode scheduling and splits long prompts so one big prompt doesn't block everyone else.

One-line Summary

Starting from the two-phase asymmetry of Prefill/Decode, this piece breaks down the core vLLM mechanics: KV Cache, PagedAttention, and continuous batching.

Paragraph Summary

LLM inference serving performance hinges on three things — the KV cache, batching, and scheduling — not faster matrix multiplication. The article first explains that inference splits into a compute-intensive Prefill phase (which determines time to first token) and a memory-intensive Decode phase, an asymmetry that makes batch size the throughput lever while KV cache size is the real bottleneck on batch size — for Llama 3.1 8B, a single request's KV cache at full 128K context is about 16 GiB, comparable to the model weights. Traditional contiguous allocation wastes 60-80% of KV memory to over-reservation and internal/external fragmentation; vLLM's PagedAttention borrows OS virtual memory paging, mapping logical blocks to physical blocks via a block table to cut waste below 4%, and shares blocks through copy-on-write in scenarios like beam search. Continuous batching reorganizes the batch every iteration, prefix caching reuses identical prefixes, and chunked prefill keeps long prompts from blocking streaming output — together forming the core mechanics of a modern inference serving stack.