The KV cache and context growth

During autoregressive generation, every new token must use information from earlier tokens. Recomputing all their intermediate attention states on every step would waste enormous work. The KV cache stores the prior key and value states so the model can reuse them.

Reuse does not make the history disappear. Under standard full attention, the new query still attends over the cached keys and values of the growing context. That distinction—less recomputation, but more state and longer reads—is the foundation of KV-cache engineering.

What you will understand by the end

• What the KV cache stores and which computation it avoids.
• Why full-attention decode still grows more expensive as attended context grows.
• How to calculate KV bytes per logical token and map logical demand to physical slots.
• Why KV capacity can constrain concurrency without necessarily setting the useful batch.
• How block allocation, prefix reuse, eviction, quantization, and offload solve different problems.

Why the cache exists

In a decoder-only transformer, each attention layer projects token states into queries, keys, and values. Once a past token has been processed, its K and V do not change when a future token arrives. Caching them avoids recalculating those past projections and hidden states.

WITHOUT KV CACHE
Each step recomputes hidden states and K/V for the full prefix.
Work for earlier tokens is repeated.

WITH KV CACHE
Each step computes hidden state and K/V for the new token only,
but its query still attends over the relevant cached history.

New-token projection and MLP work: roughly constant with context length
Full-attention work and KV reads: grow with attended context length

For ordinary full attention, caching changes the attention work per decode step from quadratic in sequence length to linear. Summing those linear steps across a growing output still gives roughly quadratic attention work in the generated length. The Transformers cache explanation shows this distinction directly.

Why keys and values, but not old queries?

The current token contributes a fresh query. That query is matched against past and current keys and uses their values. A past query is not needed again, so only prior K/V states are retained.

For standard decoder-only full attention, every processed prompt token and every accepted output token adds one K/V position in each KV-storing layer. Some architectures let a layer reuse another layer's KV state, so not every attention layer necessarily owns a separate allocation. This remains a scoped model, not a universal cache law:

• sliding-window attention can discard positions outside the active window;
• hybrid models may use different cache types and window sizes by layer;
• speculative decoding can stage proposals that are later rejected;
• eviction, compression, and distributed placement change retained state.

Size the cache from resident tokens

For a decoder-only model whose full-attention layers share one KV shape:

KV bytes per logical token
  ≈ 2 × KV-storing layers × KV heads × head dimension × bytes per element

logical resident positions
  = sum of retained token positions across active requests

physical KV slots
  = unique allocated token slots
  + block rounding or reserved-capacity overhead

physical KV bytes
  ≈ model-specific bytes per slot × physical KV slots
  + cache metadata

The leading 2 represents keys and values. GQA and MQA reduce KV heads; lower KV precision reduces bytes per element. The formula must be adapted for sliding-window, hybrid-attention, Mamba, encoder–decoder, and sharded models. vLLM's hybrid KV-cache manager documents why different layer types need different allocation rules and why layers that share KV state do not each require their own allocation.

Logical resident positions describe request-level demand. Physical allocation can be lower when requests share prefix blocks, higher because of block rounding, padding, static reservation, or metadata, and uneven across devices under sharding. Without block sharing or static over-reservation, logical positions remain a useful first-order approximation of physical slots.

Using batch × maximum context is a conservative uniform-batch bound, not a realistic continuous-batching estimate. Real requests have different prompt and output lengths and join and leave over time. Their summed resident tokens are the useful serving quantity.

KV is one part of device memory

The deployment budget is broader than weights plus cache:

required device memory
  = model weights
  + runtime and workspace memory
  + temporary activation, graph, and communication buffers
  + KV-cache pools
  + measured safety margin

Serving runtimes reserve or allocate some fraction of the usable remainder to KV storage. TensorRT-LLM, for example, exposes a configurable fraction of free GPU memory for its KV pool rather than assuming every byte after weights is automatically available.

Remaining KV capacity determines how many token positions can be resident. At long context or high concurrency, that budget may constrain the service. It does not necessarily set the useful batch: TTFT, inter-token latency, compute, bandwidth, scheduler settings, admission controls, or interconnect may bind first.

KV traffic and the decode regime

Caching shifts decode from recomputing prior states toward reading weights and retained K/V. Low-batch dense decode is therefore often bandwidth-sensitive, especially at long context. It is not automatically memory-bound merely because a cache exists. Effective batch size, attention architecture, context length, precision, kernels, hardware, interconnect, and scheduling determine the active bottleneck.

This also explains why attention variants matter. GQA and MQA store fewer K/V heads, reducing both bytes per resident token and K/V traffic per full- attention step.

Five different KV-memory levers

Technique	What it changes	What it does not inherently change
Block or paged allocation	Fragmentation and reservation waste	Intrinsic K/V bytes per token
Prefix caching	Repeated prefill computation; may share matching blocks	Decode work after the reused prefix
Shorter context, windowing, or eviction	Number of retained token positions	Bytes per retained element
KV quantization	Bytes stored per K/V element	Resident token count; quality is not guaranteed
Offload	Location of KV state	Total state; it trades GPU capacity for transfer cost

These mechanisms should not be described as if they all “shrink the KV cache.” They act on allocation waste, duplicate work/state, token count, representation size, or memory tier.

Block allocation reduces waste

Block-managed KV caches allocate storage on demand and do not require one physically contiguous worst-case region per request. A block table maps logical token positions to physical blocks, which can substantially reduce fragmentation and support block sharing. Block rounding, metadata, lookup, and kernel overhead remain, and block size is a runtime choice rather than a durable 16-token constant.

The original PagedAttention paper reported near-zero KV-memory waste in its vLLM design and substantial throughput improvements over the systems it evaluated. That result characterizes that implementation and comparison; the durable lesson is that block allocation reduces allocation waste, not intrinsic K/V bytes.

Prefix caching reuses matching prefixes

When requests contain a substantial exact compatible prefix, the runtime can reuse already computed KV blocks. This avoids repeated prefill computation and may let requests share physical prefix blocks. It does not help unique prefixes and does not reduce the later decode attention over each request's context.

Reuse depends on details:

• only matching cache identities are reusable, including tokens and relevant model/runtime metadata;
• block granularity can leave an unmatched partial block;
• blocks must remain resident and may be evicted under pressure;
• routing must send a request where the reusable state is available;
• hit rate determines the practical benefit.

vLLM's automatic prefix-caching design caches complete matching blocks and uses eviction when blocks are needed. It includes LoRA, multimodal identity, and optional cache salts in cache identity. In multi-tenant systems, salting or trust-group isolation helps prevent timing-based disclosure of cached prefixes.

Quantization and offload require tradeoff tests

KV quantization reduces bytes per stored element but requires supported runtime kernels and a compatible hardware/backend combination. Scales may need calibration, and the exact model and workload need a quality evaluation. The vLLM quantized-KV guide documents per-tensor and per-head schemes and recommends dataset-based calibration for its highest-quality pathway.

Offload moves KV blocks to host or another memory tier. It can free GPU capacity but adds transfer latency and bandwidth demand. Neither technique is a free concurrency multiplier.

Practical guidance

1. Calculate model-specific KV bytes per slot, accounting for KV-storing layer types, cross-layer sharing, KV heads, numeric format, and device placement.
2. Estimate logical resident positions under representative prompts, outputs, concurrency, and scheduling, then account for shared physical blocks and allocation overhead—not only max context × max batch.
3. Include runtime workspaces, graph and communication buffers, and a measured margin in the device budget.
4. Measure KV token capacity and occupancy alongside TTFT, inter-token latency, throughput, queueing, and allocation failures.
5. Choose the lever that matches the problem: allocation waste, repeated exact prefixes, excessive retained tokens, bytes per element, or memory tier.
6. For prefix reuse, measure hit rate, eviction, routing locality, and isolation. For KV quantization or offload, measure latency and task quality.

Common mistakes

• Calling cached decode constant-cost. New-token MLP/projection work is roughly stable, but full-attention work and KV reads grow with attended context.
• Reducing device memory to weights plus KV. Runtime and temporary buffers are real consumers.
• Sizing every request at maximum length. It is a safe bound but often a poor model of continuous traffic.
• Treating all KV optimizations as equivalent. Paging, prefix reuse, truncation, quantization, and offload change different quantities.
• Turning one prefix-cache win into a universal multiplier. Benefit follows exact-prefix reuse, residency, routing, and workload shape.

Summary

• The KV cache stores prior keys and values to avoid recomputing past token states.
• Under full attention, each new token still attends over the retained history, so per-step attention work and KV traffic grow with context length.
• Estimate logical resident positions, then convert them to physical slots by accounting for shared blocks, allocation rounding, reservation, metadata, and device placement.
• KV capacity can constrain long-context or high-concurrency service; it does not automatically determine the useful batch or the active bottleneck.
• Block allocation reduces waste, prefix caching reuses matching work/state, windowing reduces resident tokens, quantization reduces bytes per element, and offload moves state.

Knowledge check

With a KV cache, why can the 1,000th generated token cost more than the 10th?

The model computes new K/V and non-attention work only for the new token, but under full attention its query still reads and attends over the relevant cached history. That history is much larger at token 1,000. Caching avoids recomputation; it does not make the attention portion constant with context length.

A model serves one request but OOMs at concurrency 64. What should you establish before choosing a fix?

Confirm from runtime metrics that KV allocation is actually exhausting device memory, then measure the resident-token distribution and complete memory budget. If fragmentation is high, block allocation helps. If repeated prefixes dominate, prefix reuse may save duplicate work and blocks. Shorter windows or eviction reduce resident tokens; KV quantization reduces bytes per element; offload moves state at a latency cost. They are not interchangeable.

When is prefix caching likely to help, and what must you measure?

It helps when substantial exact compatible prefixes repeat and their blocks remain available where subsequent requests are routed. Measure cache-hit rate, block residency and eviction, routing locality, latency, throughput, and KV pressure. In multi-tenant service, also define cache-salt or trust-group isolation.

Primary sources

• Hugging Face Transformers: Caching — cached attention mechanics and sequence-length cost.
• TensorRT-LLM KV Cache System — pools, block reuse, eviction, offload, memory fraction, and salting.
• vLLM Hybrid KV Cache Manager — layer-specific allocation for hybrid attention models.
• PagedAttention — block-managed KV memory and the original vLLM evaluation.
• vLLM Automatic Prefix Caching — exact block identity, eviction, and isolation.
• vLLM Quantized KV Cache — schemes, support, and calibration.

Related chapters

• Attention variants (MHA/MQA/GQA/MLA) — how KV-head count changes storage and traffic
• Transformer and attention intuition — where K and V originate
• Prefill and decode — phase-dependent performance regimes
• Batching and concurrency — how resident requests share execution
• Inside an NVIDIA GPU — the memory hierarchy holding KV state