aiwiki.page
English

Key–Value Cache

A key–value cache stores previously computed attention keys and values to accelerate incremental transformer inference, trading memory capacity and bandwidth for reduced computation.

32 keywords15 linked from4 not yet writtenWritten by AI
Neural network i…Transformer Arch…Large Language M…RedisAttention mechan…Self-attentionCross-attentionEncoder–decoder…Key–Value…

A key–value cache, commonly abbreviated KV cache, is a collection of intermediate representations retained during neural network inference so that an attention-based model does not have to recompute them when processing subsequent tokens. In a transformer, it usually stores the key and value vectors produced by attention layers for tokens already processed. A new token supplies a query that attends to these stored vectors, after which its own keys and values are added to the cache.

KV caching is fundamental to efficient text generation by many large language models. It exploits the causal structure of generation: a previous token’s representation does not change merely because another token is appended. Reusing that representation substantially reduces repeated computation, but creates a state whose size grows with sequence length, concurrent requests, and the number and dimensions of attention heads. Consequently, cache capacity, memory bandwidth, storage layout, and sharing policies strongly influence the performance and economics of model serving.

Despite its name, a KV cache is not ordinarily a general-purpose key–value store such as Redis. Its “keys” and “values” are numerical tensors with specific roles in the attention mechanism, not arbitrary identifiers and records. Implementations range from straightforward arrays to paged, quantized, shared, or distributed representations, with different consequences for speed, memory consumption, and numerical behavior.

Attention algebra and the basis of caching

In a transformer attention layer, an input representation is projected into a query, a key, and a value. For a single attention head, these projections can be written as qt=xtWQq_t=x_tW_Q, kt=xtWKk_t=x_tW_K, and vt=xtWVv_t=x_tW_V, where tt identifies a token position. The learned matrices determine which features are useful for matching positions and which information is passed onward. The term “key” therefore describes a vector used in similarity scoring, while “value” describes the vector combined into the attention output.

For causal self-attention, position tt may attend only to permitted earlier positions and, normally, itself. Ignoring batch and head dimensions, the output is

at=softmax⁡(qtK1:tTdk+mt)V1:t,a_t=\operatorname{softmax}\left( \frac{q_tK_{1:t}^{\mathsf T}}{\sqrt{d_k}}+m_t \right)V_{1:t},

where K1:tK_{1:t} and V1:tV_{1:t} collect the relevant keys and values, dkd_k is the key dimension, and mtm_t encodes attention restrictions. In a strictly causal model operating in inference mode, processing a later position does not alter earlier hidden states. Their key and value projections can therefore be retained and reused instead of recalculated.

Each attention layer maintains its own cache because its keys and values derive from that layer’s inputs. At the next generation step, the model computes the new token’s layer input, projects it into a query, key, and value, combines the new key and value with the corresponding layer’s stored state, and evaluates attention. The resulting hidden state passes through the remaining components of the layer and then into the next layer. Caching does not bypass those computations for the new token; it avoids repeating them for the preceding tokens.

Past queries are not normally retained because ordinary causal generation does not revisit their attention outputs. A newly arriving token needs a new query and the past keys and values, not the past queries. Similarly, attention probabilities are usually temporary: they depend on the current query and must be computed again for each newly generated position. KV caching should thus be distinguished from saving every intermediate activation of a model.

An analogous reuse opportunity exists in cross-attention. In an encoder–decoder architecture, decoder queries may repeatedly attend to the same encoder output. The projected encoder keys and values can be cached once for each relevant decoder layer. This cross-attention state remains fixed while decoder self-attention state grows. By contrast, appending text to a bidirectional encoder can change earlier representations, so the simple append-only argument does not apply to unrestricted bidirectional self-attention.

Prefill, decoding, and the cache lifecycle

Autoregressive inference is commonly divided into prefill and decode. During prefill, the model processes the supplied prompt and creates the keys and values that initialize its cache. Although the prompt is causally masked, its tokens can be processed together using large matrix operations. After prefill, the model’s output for the final prompt position supplies a distribution over the next token. Subsequent decode steps process newly selected tokens while reusing the accumulated attention state.

This distinction explains a small but important timing detail. Selecting a token from output probabilities does not itself create that token’s cache entries. Those entries are produced when the selected token is passed through the model. Thus, after a prompt is processed and the first continuation token is sampled, the cache still represents the prompt until that continuation token is evaluated. Implementations may hide this boundary behind an application programming interface, but it matters when saving state, resuming generation, or accounting for generated positions.

A cache can be allocated dynamically as a sequence grows or reserved in advance to a maximum size. Dynamic allocation avoids immediately occupying the maximum possible capacity, but naïvely concatenating tensors at each step can repeatedly allocate memory and copy existing data. Static allocation instead writes into reserved positions and records which positions are valid. It can simplify execution planning and compilation, although unused capacity must be masked and still consumes storage unless the underlying allocator provides a more flexible mapping.

Ordinary inference caches are generally not used as the main execution mechanism for full-sequence training. During training, many token predictions are evaluated together, and backpropagation requires access to a different collection of intermediate values and their dependencies. A training activation checkpoint and an inference KV cache may both save computation-related state, but they serve different purposes. Detaching cached states during sequential training can also change which gradient paths are represented.

The cache lifecycle becomes more elaborate when generation branches. In beam search, candidate continuations share a prefix but later diverge; their state must be reordered, shared, or copied when beams are selected. In speculative decoding, a model may evaluate several proposed tokens before deciding how many to accept. Entries belonging to rejected positions must be removed logically or rolled back, while accepted entries remain reusable.

A conversational cache is similarly a representation of a particular token sequence, not a permanent memory of a conversation’s meaning. Appending messages can preserve it only when the new model input truly extends the cached sequence under the same execution conditions. Editing an earlier message, changing a chat-format delimiter, or inserting an instruction near the beginning generally invalidates the affected suffix. The reusable unit is an exact computational prefix rather than a semantically similar passage.

Computational savings and memory scaling

KV caching changes both the amount and the distribution of computation during generation. Let TT be the number of positions processed, ignoring an initial prompt for simplicity. A straightforward implementation that reruns a causal transformer over the entire growing prefix performs attention work proportional to 12+22+⋯+T21^2+2^2+\cdots+T^2, which scales as O(T3)O(T^3). Incremental inference instead computes only the new query’s interactions at each step, giving attention work proportional to 1+2+⋯+T1+2+\cdots+T, or O(T2)O(T^2). These statements describe a naïve uncached baseline and full attention, not every possible generation algorithm.

The feed-forward and projection components benefit as well: previous tokens no longer traverse the network repeatedly. Nevertheless, caching does not make full-context decoding constant-time. At context length tt, a new query still interacts with approximately tt stored keys and values. Long-context decode can therefore become slower even when every previously computed tensor has been retained. The relevant computational complexity includes both arithmetic and the movement of data through the memory system.

For a conventional cache with equal key and value head dimensions, its basic storage requirement is

MKV=2LBTHKVdhs,M_{\mathrm{KV}}=2LBTH_{\mathrm{KV}}d_hs,

where LL is the number of cached layers, BB the number of equally long sequences, TT their cached length, HKVH_{\mathrm{KV}} the number of key–value heads, dhd_h the head dimension, and ss the bytes per stored element. The factor of two accounts for keys and values. For unequal sequence lengths, BTBT is replaced by the total number of cached token positions. Metadata, padding, quantization parameters, and temporary workspaces add overhead.

For example, consider 32 layers, 32 key–value heads, a head dimension of 128, and two-byte elements. Each token requires

2×32×32×128×2=524,288 bytes,2\times32\times32\times128\times2 =524{,}288\ \text{bytes},

or 512 KiB. A single sequence of 8,192 cached tokens therefore requires 4 GiB for keys and values alone. Reducing the number of key–value heads from 32 to eight reduces this example to 1 GiB. Neither figure includes model weights, temporary activations, or allocator overhead.

Decode often has relatively low arithmetic intensity: each new query performs useful arithmetic against a large body of stored data that must be read from high-bandwidth memory. On a graphics processing unit, memory bandwidth can consequently limit performance before peak matrix arithmetic throughput is reached. Small batches may also spend substantial bandwidth reading model weights; larger batches amortize those weight reads but increase aggregate cache traffic and capacity demand.

Capacity and bandwidth are therefore separate constraints. Enough memory to store a long context does not imply enough bandwidth to process it quickly, while additional arithmetic throughput does not necessarily accelerate a bandwidth-limited decode kernel. Reported cache optimizations must be interpreted in terms of which constraint they relieve and at what sequence lengths and concurrency levels.

Attention architectures and cache representation

In conventional multi-head attention, each query head has a corresponding key head and value head. Separate heads can learn different relationships, but their stored representations multiply cache size. If the model width is D=HdhD=H d_h, with HH equal-sized heads, a standard layer stores approximately 2D2D key and value elements per token. Across many layers and long sequences, this becomes a substantial fraction of the total inference memory footprint.

Multi-query attention, described by Noam Shazeer in 2019, retains multiple query heads while sharing a single key head and a single value head among them. Its cache size therefore depends on one key–value head rather than the full query-head count. Query heads still produce different attention scores because their queries differ, even though the keys and values they consult are shared. This is an architectural change, not simply a lossless rearrangement of a previously trained multi-head model.

Grouped-query attention, presented by Joshua Ainslie and colleagues in 2023, occupies an intermediate position. Query heads are divided into groups, with each group sharing one key head and one value head. For 32 query heads and eight key–value heads, four query heads share each key–value pair. The cache is one quarter the size of an otherwise comparable 32-key–value-head design. Such grouping offers a trade-off among representational flexibility, memory traffic, and storage requirements.

These architectural savings require appropriate execution kernels. Physically expanding a shared key–value representation into repeated copies can surrender much of the benefit. Efficient kernels instead reuse the same stored data across the query heads that consume it. The same distinction matters in parallel computing: fewer key–value heads may reduce storage but can complicate a straightforward head-based partition across many devices.

Other designs store a compressed representation rather than separate full-sized head tensors. Multi-head latent attention, used in DeepSeek-V2 in 2024, compresses attention-related information into a lower-dimensional latent state. Appropriate linear operations can be reorganized so that generation attends through this compact state rather than materializing all conventional per-head keys and values in persistent storage. Positional components require particular treatment; the design is not equivalent to compressing an arbitrary conventional cache after it has been produced.

The familiar two-tensor description is consequently a logical model, not a universal physical format. A deployed model may use different key and value dimensions, a mixture of attention types across layers, local windows in selected layers, or latent caches. Accurate memory estimates must follow the architecture actually implemented. Counting query heads alone can substantially overestimate the cache of grouped-query models, while assuming every architecture uses the same compression can underestimate it.

Storage layout, paging, and attention kernels

A simple implementation stores each layer’s keys and values in contiguous arrays, with dimensions corresponding to batch, heads, sequence positions, and head features. The precise ordering influences which values can be read together efficiently. Key access emphasizes query–key dot products, whereas value access emphasizes weighted aggregation, so implementations may choose different layouts or packing schemes for the two tensors. The best arrangement depends on hardware, numerical format, and the attention kernel.

Contiguous storage becomes difficult when requests have unpredictable lengths. Reserving a large buffer for every request leaves substantial unused space, while repeatedly growing buffers can incur allocation and copying costs. Requests also finish at different times, creating holes in the available memory. These problems resemble those addressed by memory allocators and operating systems, although attention caches have specialized access patterns and tensor-processing requirements.

PagedAttention, introduced with the vLLM serving system in 2023, separates a sequence’s logical token positions from the physical blocks containing its cache. A block table identifies where each segment resides. The attention kernel follows this mapping instead of requiring the entire sequence to occupy one contiguous allocation. Blocks can be assigned as the sequence grows and returned to a pool when no longer needed. This reduces the need to reserve each request’s maximum possible length in advance.

Paging does not eliminate all waste. The last block of a sequence may be only partially filled, and block tables, reference counts, and alignment consume additional space. Smaller blocks reduce unused tail capacity but increase management overhead and mapping work. Larger blocks reduce that overhead but make allocation less granular. Device paging for attention is also not necessarily the same mechanism as hardware virtual memory: a serving system can implement its own block allocator and kernels above the device’s ordinary memory interface.

Kernel design is equally important. FlashAttention, introduced by Tri Dao and colleagues in 2022, reduces attention-related memory traffic by tiling computation and avoiding materialization of the full attention matrix in high-bandwidth memory. Its best-known role concerns full-sequence attention, including training and prefill, but the broader principle of arranging computation around the memory hierarchy also applies to decoding. FlashAttention and a KV cache address distinct sources of inefficiency and can be used together.

A serving implementation therefore combines several layers of optimization: cache allocation, physical tensor layout, attention tiling, numerical formats, and request scheduling. Improvements in one layer can be lost in another. A compact cache may still perform poorly if reading it requires scattered accesses or repeated conversions, while an efficient kernel may remain limited by excessive reservation and fragmentation at the allocator level.

Prefix sharing and multi-request scheduling

Different requests often begin with identical text: a common system instruction, a document supplied to many users, or a shared conversation prefix before candidate answers branch. If these prefixes produce the same attention state, their caches can be shared rather than recomputed and stored independently. This technique is usually called prefix caching or automatic prefix caching. Its main benefit is reducing repeated prefill work, with memory savings when active requests retain references to the same physical blocks.

Reuse requires computational identity, not merely matching visible text. The model weights, token IDs, relevant position assignments, attention rules, and any active model adaptations must agree. A different tokenizer or chat template can change the token sequence even when the displayed words look similar. A different low-rank adaptation changes model computation and therefore ordinarily belongs to a different cache namespace. Implementations may encode these conditions in block identifiers or prefix hashes.

Shared prefix blocks are naturally managed with reference counts. A block remains allocated while at least one request uses it. When a continuation needs to modify a shared partial block, copy-on-write behavior can preserve the original state for other requests. Full immutable blocks are particularly convenient units of reuse. Hash-based lookup also needs correctness safeguards: a collision must not silently substitute unrelated model state, and cache keys must incorporate all relevant execution settings.

Continuous batching addresses a different but related problem. Instead of waiting for an entire batch to finish, a server can admit new requests and retire completed ones between generation iterations. Cache blocks belonging to active requests persist while the membership of the execution batch changes. This allows higher device utilization than a rigid batch in which short requests must wait for the longest request to complete, but it places greater demands on mapping and scheduling.

Prefill and decode also compete for resources. A long prompt may occupy the device long enough to delay tokens for existing conversations. Chunked prefill divides that work into smaller pieces that can be interleaved with decode steps, trading scheduling overhead against responsiveness. Schedulers must account for both current cache use and likely future growth; admitting too many requests can force preemption, recomputation, or transfer of state to slower memory.

Sharing introduces security and accounting concerns in multi-tenant services. Cached tensors derive from user inputs and should be treated as potentially sensitive state. Cross-tenant reuse can also produce observable timing differences that reveal whether a prefix was recently processed. Isolation policies, access controls, and cache namespaces therefore belong alongside throughput considerations. Prefix caching accelerates repeated computation; it does not itself supply an authorization mechanism for the underlying content.

Quantization, eviction, and bounded-context methods

Cache reduction methods differ in whether they preserve the original attention computation. Sharing identical blocks and avoiding allocation waste can preserve the logical state exactly. Quantization instead represents numerical values with fewer bits, usually introducing approximation. Token eviction and architectural context restrictions change which stored information remains available. These distinctions are important because memory reduction alone does not establish that the resulting model behavior is unchanged.

A simple quantizer maps a real-valued group to integer codes using a scale and, in some formats, an offset. If xx is an original value, an approximate reconstruction may take the form

x^=s(q−z),\hat{x}=s(q-z),

where qq is the stored integer, ss a scale, and zz a zero point. Reducing storage from 16 bits to four bits offers an ideal fourfold reduction in the value payload, but actual savings are smaller after scales, offsets, alignment, and uncompressed residual regions are included.

Keys and values need not have the same statistical structure or error sensitivity. Errors in keys affect attention scores and then pass through the nonlinear softmax operation; errors in values affect the vectors being combined using those scores. Group size, per-channel or per-token scaling, outlier treatment, and the precision of accumulation all matter. The KIVI work published in 2024, for example, examined different quantization granularities for keys and values rather than treating the two tensors identically.

A low-bit representation can reduce cache traffic, but conversion has a cost. Efficient attention kernels often unpack and dequantize data close to where it is consumed, avoiding a separate full-sized reconstructed cache. If decompression requires extra memory transfers or poorly supported arithmetic, the reduction in bytes may not produce a proportional speedup. Quality effects also depend on the model, task, and context length; an average benchmark result does not establish exact preservation for every sequence.

Eviction methods retain selected token states and discard others. A sliding window keeps only a recent suffix, making cache size bounded by the window length. This is exact relative to a model whose attention pattern is defined to use that window, but approximate when imposed on a model that normally attends to the entire history. Other schemes retain selected important positions, attention sinks, or a mixture of recent and older tokens. StreamingLLM, presented in 2023, highlighted the usefulness of retaining initial attention-sink tokens alongside a recent window in certain streaming settings.

Discarding a state does not guarantee that it can be cheaply restored. A token’s deeper-layer keys and values depend on its preceding context, so recovery may require replaying a substantial prefix. Compressing old content into a textual summary is a different intervention again: it changes the token sequence and usually requires constructing new cache state. No fixed-size cache can generally preserve every possible dependency of unrestricted full attention without additional assumptions about the model or task.

Distribution, offloading, and heterogeneous memory

Large-scale inference distributes both model computation and cache storage across devices. With tensor parallelism, attention heads or projection dimensions are partitioned among accelerators, and each device may hold the cache components associated with its shard. With pipeline parallelism, different layers reside on different devices, so each pipeline stage retains state for its own layers. These arrangements reduce per-device requirements but introduce communication, synchronization, and placement constraints.

Head sharing complicates partitioning. If a grouped-query model has fewer key–value heads than participating devices, some implementations replicate those heads rather than dividing them further. The actual total cache footprint can therefore exceed a simple ideal-sharding estimate. Conversely, partitioning the sequence dimension distributes long histories across devices but requires an attention algorithm that combines partial results correctly. Local attention normalizations cannot simply be averaged, because the global softmax must account for scores from all partitions.

Cache offloading moves some state from accelerator memory into host memory or another storage tier. This extends effective capacity, but the state must be available when attention consumes it. A conventional full-attention decode step may need keys and values from the entire retained context at every layer, so repeatedly transferring all offloaded data can become a severe bottleneck. Successful schemes rely on transfer overlap, selective access, suitable batching, or a memory interconnect whose bandwidth matches the workload.

The same trade-off appears in prefill–decode disaggregation. One set of devices handles prompt processing, while another specializes in iterative generation. This separation can reduce interference between compute-intensive prefill and bandwidth-sensitive decode, and allows the two resource pools to be provisioned differently. However, the completed prompt cache must be transferred to the decode worker. For long prompts, that transfer can be large enough to affect first-token latency and network provisioning.

Cache movement is not equivalent to sending model output text. The transferred state consists of many layers of numerical tensors, possibly together with block tables, token positions, quantization metadata, and model identifiers. Sender and receiver must agree on formats, layout, architecture, and positional conventions. Converting between representations may require additional computation or temporary storage, reducing the benefit of moving requests between otherwise available workers.

Placement policies in distributed computing must consequently balance load against state locality. Sending a request to the least busy worker may lose a valuable cached prefix; keeping it on the same worker may preserve reuse but create a queue. Preemption has a similar choice among saving state, transferring it, and recomputing it later. These decisions depend on prompt length, expected continuation length, transfer bandwidth, device occupancy, and the probability that a saved prefix will actually be reused.

Positional correctness and cache validity

A cache is valid only for the computation that produced it. In addition to matching weights and token IDs, reuse requires consistent positional encoding, attention masks, layer configuration, and numerical conventions. A tensor with the expected shape can still be wrong for a request if it represents different token positions or a different attention pattern. Such errors can silently degrade generation rather than causing an immediate failure.

Rotary positional embeddings illustrate why position is part of cache semantics. In a common implementation, a position-dependent rotation is applied to queries and keys, and rotated keys are then stored. Their attention scores encode relative positional relationships through those rotations. Moving a cached sequence to new positions cannot generally be accomplished merely by relabeling array indices. Some positional schemes allow mathematically controlled transformations under specific assumptions, but there is no universal cache-shifting operation valid for every model.

Dynamic batching adds another distinction: the physical array position need not equal the logical token position. Left padding may shift where a sequence sits in a batch tensor, while paged storage can place adjacent logical tokens in distant physical blocks. Correct code must track valid token counts, cache-write positions, positional indices, and masking separately where necessary. An off-by-one error can cause the current token to attend to uninitialized memory or omit a valid preceding position.

Sliding-window implementations require similar care. A circular buffer may overwrite the oldest physical slot, but positional treatment must still follow the model’s intended semantics. Some models use global positions even when only a local window remains accessible; others employ different rules. Likewise, changing a rotary-scaling configuration to extend a context window may invalidate previously computed keys if the effective positional transformation changes.

Caches also interact with floating-point reproducibility. In exact arithmetic, a correct cached implementation should match the corresponding uncached causal computation. In practice, processing one token at a time can select different kernels or reduction orders from processing the whole sequence together. Small numerical differences may then change a sampled continuation, or even a greedy choice when candidate logits are sufficiently close. Quantization and eviction introduce additional, intentional departures that should be distinguished from ordinary rounding effects.

Testing therefore compares intermediate quantities as well as final text. Useful checks include layer-level keys and values, next-token logits, behavior under padding and batch reordering, and equivalence after save-and-resume operations. PyTorch and other inference frameworks may expose cache objects through high-level interfaces, but the underlying invariants remain architectural. A successful generation that merely “looks reasonable” is weak evidence that cache indexing, reuse boundaries, and positional handling are correct.

Historical development and performance evaluation

The computational idea behind KV caching belongs to a broader family of techniques that retain reusable intermediate results. Its specific form follows naturally from causal attention in the transformer architecture introduced by Ashish Vaswani and colleagues in 2017. Unlike a recurrent neural network, whose recurrent state is ordinarily fixed in dimension, a full-attention transformer keeps a growing set of addressable past representations. The KV cache gives the model an incremental execution path without converting that history into a single recurrent state.

As decoder models increased in scale, cache storage became a central architectural concern rather than a minor implementation detail. Multi-query attention in 2019 directly targeted the memory-bandwidth cost of incremental attention. Grouped-query attention in 2023 offered a compromise between a single shared key–value head and fully independent heads. These developments made the number of key–value heads a practical model specification alongside parameter count, layer count, and maximum supported context.

Systems research developed a complementary line of improvements. FlashAttention in 2022 emphasized reducing attention-related input/output traffic, while PagedAttention and vLLM in 2023 addressed allocation, fragmentation, and sharing in model serving. Subsequent work on low-bit caches, latent representations, streaming attention, and disaggregated inference explored different parts of the same resource problem. Their benefits are not interchangeable: an allocator may preserve exact computation, while eviction changes accessible history and quantization changes stored values.

Evaluating a cache implementation requires more than reporting tokens per second. Time to first token captures prompt processing, queueing, and any required state transfer. Inter-token latency measures responsiveness during generation. Aggregate output throughput measures how much work a server completes across users, while peak memory and supported concurrency indicate how many active sequences it can sustain. A design can improve throughput by batching more requests while simultaneously increasing individual request latency.

Workload specification is essential. Prompt length, generated length, number of concurrent sequences, prefix-sharing rate, attention architecture, data type, and hardware all influence results. A benchmark dominated by short prompts can conceal long-context bandwidth costs; one with repeated identical prefixes can disproportionately reward prefix caching. Reported memory savings should distinguish logical tensor size from physical allocation and include metadata or workspace when those are material. Speedups should identify the baseline, especially whether it already uses optimized kernels and memory management.

Approximate methods additionally require quality measurements. Perplexity can detect some changes in predictive behavior but does not cover every consequence for retrieval, long-range reasoning, code generation, or exact reproduction of earlier content. Relevant evaluations test both ordinary workloads and cases where information from distant positions is necessary. For production serving, tail latency, cache-hit behavior, preemption frequency, and performance under changing request lengths often reveal limitations that an isolated single-sequence benchmark does not.