KV cache: reuse past projections, retain growing reads

Summary

A KV cache retains past keys and values so causal decoding need not project the same past positions again. Each new query still reads its allowed prefix.

Suppose three input positions are already cached. Process four more inputs, one at a time, with no eviction. Which work disappears, which work grows, and how much storage is needed?

The mechanism

For each new input, compute its Q, K and V, append K/V, then attend over valid positions. Q serves the current query; it is not normally retained in the persistent KV cache. The current forward pass predicts the next output token.

Earlier representations remain valid because causal masking prevents dependence on later inputs. Reuse requires compatible model weights, prefix, positions and attention rules.

Three positions already cached

Write one new pair while reading the growing cache

Derivation

Follow four processed inputs after prefix length three. Each appends one K/V pair per KV head; its query reads all valid positions.

Decode step	Cache before	Append once	Newest query reads
Input 4	Positions 1–3	K₄, V₄1 new pair	Positions 1–4 4 pairs
Input 5	Positions 1–4	K₅, V₅1 new pair	Positions 1–5 5 pairs
Input 6	Positions 1–5	K₆, V₆1 new pair	Positions 1–6 6 pairs
Input 7	Positions 1–6	K₇, V₇1 new pair	Positions 1–7 7 pairs

4 appends · 4 + 5 + 6 + 7 = 22 pair reads

appends stay constant per processed input; the newest query reads a growing prefix. Counts exclude creation of the initial three-position cache.

Check: Why are there only four new pairs but twenty-two attended pairs over the four steps?

Read it this way: At decode position 8, write one new key/value pair while attention reads eight available pairs. Persistent storage grows with the prefix.
How many old pairs are read when only one new pair is written?

Only four new position pairs are projected per KV head, rather than repeating projections over all 22 prefix positions. Newest-query attention still visits $4 + 5 + 6 + 7 = 22$ pairs per query head. A full-square recomputation baseline would form $4^{2} + 5^{2} + 6^{2} + 7^{2} = 126$ score entries, including masked entries. That baseline is not a claim about every uncached implementation.

The memory cost

Persistent K and V each have shape [B, G, S, d_head] per layer. For $L$ layers, $G$ KV heads, valid length $S$ and $b$ bytes per element:

KV cache size = 2 (K and V) * num_layers * num_kv_heads * d_head * sequence_length * batch_size * dtype_bytes

Take $L = 80$ , $G = 8$ , d_head=128, $S = 8192$ , $B = 1$ , $b = 2$ :

2 * 80 * 8 * 128 * 8192 * 1 * 2 = 2,684,354,560 bytes
										 = 2.5 GiB
										 = 2.68435456 GB

Batch 32 needs 80 GiB of ideal payload. Quadrupling that batch’s context to 32768 positions needs 320 GiB. These exclude allocator overhead, metadata and temporary buffers; the example is not a universal 70B layout.

Change stored heads or precision

1. Reduce KV heads from eight to one

New task: reduce persistent cache through architecture design or checkpoint adaptation.

Picture and change: change learned K/V projections and query-to-group mapping together. Do not relabel eight independent heads as one.

Check: ideal batch-one payload becomes $2.5/8 = 0.3125$ GiB. Original outputs are not guaranteed; train or adapt, then evaluate.

Use when: the model design can change.

2. Store one-byte rather than two-byte elements

New task: reduce logical cache bytes without changing head count.

Picture and change: quantize writes, store scale metadata and use compatible reads. Keep positions and valid length unchanged.

Check: ideal payload halves to 1.25 GiB, excluding metadata. Measure output error and kernel costs.

Use when: logical payload, not fragmentation alone, exceeds capacity.

Failure and transfer

Changed weights or incompatible position encodings can invalidate cached keys. Bidirectional re-encoding can change earlier hidden states, making their old K/V stale.

Does fourfold context require fourfold persistent Q storage?

Check your answer

No. KV payload and each new query’s allowed read grow fourfold. The new Q still represents one position; it is not a growing persistent prefix cache.

What an interviewer expects you to say

State the operation before its complexity. Across lengths one through $T$ , cached dense attention visits $\sum t = O (T^{2})$ newest-query pairs. Repeated full-prefix projection also accumulates quadratically; full-square score recomputation accumulates $\sum t^{2} = O (T^{3})$ entries. Sliding windows or other attention rules change these counts.

Multi-query and grouped-query attention

MHA uses $G = H$ KV heads for $H$ query heads. MQA uses $G = 1$ ; GQA shares each KV head among a query group. At fixed other dimensions, their payload ratios to MHA are $1/ H$ and $G / H$ . Quality and runtime effects require evaluation, not a universal compromise claim.

Paged attention (vLLM)

Paged storage allocates blocks on demand and can reduce fragmentation relative to reserved contiguous buffers. Compatible identical prefixes may share blocks under a correct cache identity and ownership policy. Paging alone does not halve logical bytes per valid token.

Common confusions

Cache capacity does not establish context quality. KV reuse describes a causal attention mechanism, not every possible model or reusable inference state.

Why decoding is memory-bound

Small-batch decode can be limited by weight bandwidth; long contexts can expose KV traffic. Batching reuses weights but retains per-sequence cache work. Quantization and speculative verification have kernel, error and acceptance costs; verification is not free. Profile the workload using GPU memory accounting.

References: cache explanation, Pope et al., and PagedAttention.

Related: FlashAttention, Speculative decoding. Related interview: How would you reduce LLM inference cost by 10x?.