KV cache write (prefill fill, decode append)

Why you'd careThe thing you have already noticed

Two things you have watched. First: the answer pauses, then arrives in a rush — a second of nothing, then 40 tokens a second. Second: a self-hosted server that was serving twenty happy users grinds when three of them paste in long documents, or throws an out-of-memory error even though the weights fit in VRAM with room to spare. Both are the KV cache. The pause is prefill writing keys and values for every prompt token at once; the rush is decode, which reads that stored state and appends exactly one key/value pair per step. The memory is the cache itself: on a 70B model with 80 layers and 8 key/value heads at fp16 it costs about 320 KiB per token, per sequence, and nothing reclaims it until the request ends.

In and outWhat goes in, what comes out

What is preserved is exact: the stored vectors are the values a full recomputation would produce, so reuse costs nothing in quality. What is discarded is everything else from those positions — queries, attention weights, MLP activations, the residual stream. You keep only what future tokens need to attend to, which is why you cannot go back and inspect what the model was doing at token 40. Quantizing the cache to fp8 makes even the kept part lossy.

ConceptThe idea underneath

A transformer layer turns each token's hidden state into three projections: Q = xW_Q, K = xW_K, V = xW_V. Attention then computes softmax(Q K^T / sqrt(d_k) + M) V, where M is the causal mask that stops a position attending to anything after it. The mask is the load-bearing detail: it makes K and V at position i depend only on tokens up to i, so once written they never need to change. Q is different — a query is used only at the step that produced it, which is why nothing caches queries.

Decode therefore has one new query row and a full history of keys and values. Reading them from a cache costs one dot product per cached position per head. Recomputing them would mean re-running the entire projection stack over the whole prefix, at every step.

The arithmetic is worth stating precisely, because it is often garbled. At step t, the cached version costs about O(d^2) for the new token's projections plus O(t*d) for attention. The uncached version costs O(t*d^2) plus O(t^2*d). Summed over n generated tokens, caching takes projection work from O(n^2 d^2) down to O(n d^2), and attention work from cubic down to quadratic. The common shorthand that decode without a cache is "quadratic per token" is only half right — the quadratic term is attention, while the term that dominates at realistic model sizes is the linear-in-prefix projection cost. Either way, the cache removes a whole factor of n from generation.

At a glanceSee it

Prefill writes every prompt position at once; decode appends one key and value pair per step.

The knobsHyperparameters and nuance

• max_model_len(vLLM) — the per-sequence context ceiling the block manager plans against. Too high and the engine admits fewer concurrent sequences, or refuses to start because worst-case KV will not fit; too low and long requests are rejected outright with a context-length error.
• kv_cache_dtype(vLLM: auto, fp8, fp8_e4m3, fp8_e5m2, plus several backend-specific quantised options) — halves the per-token footprint against fp16, roughly doubling context or concurrency. The cost is real but narrow: long-range retrieval degrades before short-form quality moves at all, and models without fp8 calibration degrade further.
• gpu_memory_utilization(vLLM, default 0.92) — the fraction of the card the engine claims; everything left after weights and peak activations becomes cache. Too low gives a tiny pool with constant preemption; too high means OOM at peak, or crowding out another process on the GPU.
• max_num_seqs(vLLM, default 128) — a hard ceiling on concurrent sequences regardless of free blocks. Set above what your context lengths can support and the scheduler thrashes; set it too low and the GPU idles with memory to spare.
• max_tokens/ max_completion_tokens (API-side) — every generated token appends a key/value pair per layer, so this is the per-request memory bound the scheduler reserves against, not merely an output-length limit.

EffectHow this stage moves the answer

On its own the cache changes nothing about the answer; the reuse is arithmetically exact. Three things around it do. First, kv_cache_dtype: storing keys and values in fp8 halves the footprint and degrades long-range retrieval before it touches anything else, so a model still writes fluently but starts failing to quote the middle of a 64k-token document. Second, memory pressure: when the pool runs out the engine preempts a running sequence and either swaps or discards its cache, and a sequence that resumes in a different batch shape sees a different floating-point reduction order — enough to flip a token at a near-tie and send the rest of the completion elsewhere. Third, and worst, some servers silently left-truncate a prompt that would exceed max_model_len rather than returning an error. The model then answers confidently about a document whose opening pages it never saw.

EvalsWhat it does to your measurements

This stage sets the shape of every latency number you report. Time to first token is prefill, which is compute-bound and scales with prompt length; inter-token latency is decode, which is memory-bandwidth-bound and creeps upward as the cache grows. A single average-latency figure hides both effects. Long-context suites are the accuracy-sensitive ones: needle-in-a-haystack style retrieval and RULER move when KV precision changes, while short-form knowledge scores do not budge — which is exactly how an fp8 cache regression escapes a standard eval sweep. The silent invalidator is batch composition. Attention reductions are summed in an order that depends on how the batch is tiled, so even greedy decoding is not bit-reproducible between batch size 1 and batch size 64. Re-running an eval on a busier server and getting different completions is usually this, not a model change.

Failure modesWhen it goes wrong

• Throughput collapses when a few users send very long promptsKV is charged per token per sequence, so one 100k-token context consumes the block budget of dozens of short chats.
• Out-of-memory only under load, never at startupweights and activations fit; the cache is what grows, and its pool was sized once at boot from gpu_memory_utilization.
• The answer quietly ignores the start of a long documentthe server left-truncated the prompt to fit max_model_len instead of rejecting it.
• Long-context accuracy drops after a change that touched nothing elsefp8 KV quantization was enabled; short prompts look fine and retrieval beyond about 32k tokens degrades.
• Inter-token latency grows steadily through a single long generationevery decode step reads the whole cache, so decode is bandwidth-bound and gets slower as the sequence lengthens.

PapersWhere this comes from

• Fast Transformer Decoding: One Write-Head is All You NeedShazeer, 2019 (arXiv 1911.02150). Identified that the KV cache, not arithmetic, is the decode bottleneck, and introduced multi-query attention to shrink it — the origin of every later attempt to make this stage cheaper.
• Efficiently Scaling Transformer InferencePope et al., 2022 (arXiv 2211.05102). Gave the analytic model of prefill as compute-bound and decode as memory-bound, including the KV footprint arithmetic that the per-token numbers on this page come from.
• GQA: Training Generalized Multi-Query Transformer Models from Multi-Head CheckpointsAinslie et al., 2023 (arXiv 2305.13245). Established the interpolation between multi-head and multi-query attention that gives modern models 8 key/value heads, which is why the 70B figure above is 320 KiB per token rather than 2.5 MiB.

RelatedGo deeper