The space complexity of the standard Key-Value (KV) cache, which grows linearly with the number of tokens $$m$$ as $$O(L \cdot \tau \cdot d_h \cdot m)$$, can be reduced by caching fewer tokens. For instance, sliding window attention utilizes a fixed-size window $$m_w$$ to store keys and values only for the local context. This restricts the caching mechanism's space complexity to a constant $$O(L \cdot \tau \cdot d_h \cdot m_w)$$, making it more manageable regardless of the overall sequence length.

Reducing KV Cache Complexity via Windowed Caching

An engineer is deploying a large autoregressive model for a chatbot. They observe that as a conversation with a user gets longer, the model's memory consumption increases steadily, eventually leading to performance issues. This is because the model stores key and value vectors for every token in the conversation history to speed up the generation of the next token. Based on this mechanism, what is the fundamental relationship between the length of the conversation history (in tokens) and the amount of memory required for this storage?

Based on the provided model specifications, determine which model will require a larger key-value cache to process an input sequence of 1000 tokens and justify your reasoning.

KV Cache Memory Footprint Comparison

An autoregressive model uses a mechanism to store key and value vectors for previously processed tokens to speed up inference. For a sequence of 100 tokens, this storage mechanism consumes 200 MB of memory. Assuming all other model parameters remain constant, how much memory would this mechanism consume for a sequence of 400 tokens? Explain your reasoning.

Calculating Memory Growth for Token Caching

The memory footprint of the Key-Value (KV) cache can be decreased not only by reducing the number of tokens cached (represented by the sequence length, $$m$$) but also along other architectural dimensions. A widely adopted approach to achieve this is by enabling the sharing of keys and values across the various attention heads within a multi-head self-attention mechanism.

Reducing KV Cache Complexity via Head Sharing

The memory footprint of the Key-Value (KV) cache for a specific context window size can be quantified. The total size is proportional to the product of four key parameters: the number of layers in the model ($$L$$), the number of attention heads per layer ($$\tau$$), the dimensionality of each head's key/value vectors ($$d_h$$), and the size of the context window ($$m_w$$). The overall memory complexity is therefore given by the formula: $$O(L \cdot \tau \cdot d_h \cdot m_w)$$.

Formula for KV Cache Memory Size

During inference, the space complexity of the Key-Value (KV) cache is directly proportional to the number of tokens for which keys and values are stored. This relationship is captured by the formula $$O(L \cdot \tau \cdot d_h \cdot m)$$, where $$L$$ is the number of layers, $$\tau$$ is the number of attention heads, $$d_h$$ is the head dimension, and $$m$$ is the number of tokens being cached.

Google

The Key-Value (KV) cache is a crucial component for efficient autoregressive inference in Transformer models. It functions as a memory store for the key and value vectors representing all previously processed tokens. At each generation step, instead of recomputing these vectors for the entire preceding sequence, the model generates a new representation for the current token and has it attend to the historical representations stored in the cache. This mechanism of storing and reusing past context significantly improves inference speed and is fundamental to the model's operation.

Key-Value (KV) Cache in Transformer Inference

Reference of Foundations of Large Language Models Course

Space Complexity of the KV Cache

The procedure for updating the Key-Value (KV) cache at a given position is an essential operation during autoregressive sequence generation. Specifically, at a new position $$i'$$, the newly generated key vector ($$\mathbf{k}_{i'}$$) and value vector ($$\mathbf{v}_{i'}$$) are appended to their respective cache matrices, $$\mathbf{K}$$ and $$\mathbf{V}$$. Using a function $$\mathrm{Append}(\mathbf{a}, \mathbf{b})$$ that adds a row vector $$\mathbf{b}$$ to a matrix $$\mathbf{a}$$, the update rule is defined as $$\mathbf{K} = \mathrm{Append}(\mathbf{K}, \mathbf{k}_{i'})$$ and $$\mathbf{V} = \mathrm{Append}(\mathbf{V}, \mathbf{v}_{i'})$$. This mechanism maintains a history of key-value pairs, enabling a Transformer decoder to attend to past context efficiently.

Updating the KV Cache

In Transformer-based language models, which operate as autoregressive systems, each new token is generated based on all preceding tokens. This process necessitates a Key-Value (KV) cache to store the representations of past tokens, allowing the model to attend to this history efficiently. When analyzing the generation of a sequence, represented as Pr(y|x), from the standpoint of KV cache computation, the inference process can be naturally separated into two distinct phases.

Two-Phase Inference from a KV Cache Perspective

During each step `i` of autoregressive generation, the model computes a new query ($q_i$), key ($k_i$), and value ($v_i$) vector from the current input token. The new key-value pair ($k_i, v_i$) is appended to the KV Cache, which holds the pairs for all preceding tokens. The attention operation is then performed using the new query $q_i$ and the complete set of keys and values stored in the cache up to the current step, denoted as $K_{\leq i}$ and $V_{\leq i}$. This process generates the output for step `i` by allowing the current token to attend to itself and all previous tokens in the sequence.

Single-Step Generation with a KV Cache

In a standard self-attention implementation, the Key-Value (KV) cache for each sequence is stored as a single, contiguous block of memory. While this approach allows for efficient data access, it requires reserving a large, continuous space. This requirement leads to memory fragmentation as sequences of varying lengths are dynamically allocated and deallocated, creating small, unusable memory gaps that complicate future allocations.

Memory Allocation for KV Caching in Standard Self-Attention

The Key-Value (KV) cache in Transformer models is a dynamic data structure whose size is determined by several dimensions. These dimensions include the number of layers in the model ($$L$$), the number of attention heads per layer ($$\tau$$), and the length of the input sequence. Each attention head also contributes a key/value vector of a specific dimensionality ($$d_h$$), making the overall cache a multi-dimensional entity.

Multi-Dimensional Structure of the KV Cache

An autoregressive language model generates text one word at a time. To generate the 100th word, it must relate it to all 99 previous words. A common optimization involves storing in memory the intermediate representations for each of the first 99 words as they are generated.

Which statement best analyzes the primary computational advantage of this optimization compared to re-computing everything from scratch at step 100?

Based on the scenario provided, identify the most likely cause of this performance degradation. Describe a caching mechanism that would resolve this issue by avoiding redundant computations. Explain what information should be stored in this cache and how it would be used at each step of generating a new word.

Chatbot Performance Degradation

An autoregressive Transformer model is in the process of generating the 50th token of a sequence. It has already computed and stored the key and value vectors for the first 49 tokens in a cache. Describe the essential self-attention computations performed at this 50th step, and explain how this process differs from what would be required if no cache were used.

Computational Steps in Cached Inference

You operate a GPU-based LLM inference service that uses continuous batching to serve many concurrent chat sessions. Each request has (a) a prompt that must be processed before generation starts and (b) a variable-length generated response. Production telemetry shows two symptoms: (1) latency spikes occur when many new requests arrive with long prompts that share a common system prefix (e.g., the same 200-token policy header), and (2) after several hours of mixed traffic, the service sometimes fails to admit a new long request even though ~25–35% of GPU memory is reported free.

Write an engineering recommendation memo that proposes a coherent end-to-end approach to reduce both the latency spikes and the admission failures. Your memo must explicitly connect: how the KV cache is created and grows across the prompt-processing stage versus token-by-token generation; how reusing KV states for shared prompt prefixes changes the amount of prompt work performed; why the observed “free memory but cannot allocate” symptom can occur in KV-cache allocation; and how a paged/block-based KV-cache allocator would change the failure mode and memory utilization. Conclude by stating at least two concrete tradeoffs/risks (e.g., memory overhead, eviction policy complexity, access patterns) and how you would validate the improvement with metrics or experiments.

Diagnosing and Redesigning KV-Cache Memory Behavior in a Multi-Tenant LLM Serving Stack

You operate an internal LLM inference service for a company knowledge assistant. Traffic has two dominant patterns: (1) many users start chats with the same 300-token “policy + safety + tool instructions” system prompt, then ask different questions; (2) a smaller set of power users submit long, unique prompts (2,000–4,000 tokens). The server uses continuous batching and must keep p95 latency low. Recently, you observe that GPU memory monitoring often shows ~25% free memory, yet new long requests intermittently fail to start or cause sharp throughput drops after the system has been running for hours.

Write an evaluation recommending a concrete inference-time caching and memory-management approach that addresses both compute and memory issues. Your answer must explain, in one coherent argument, how (a) KV cache growth differs between the initial prompt processing and token-by-token generation, (b) prefix caching changes the amount of prefilling work for shared-prefix requests and what it costs in memory, and (c) memory fragmentation can cause “free memory but allocation failure,” including how paged KV caching (PagedAttention) would change allocation behavior. Conclude with a justified recommendation (e.g., enable/disable prefix caching, use paged KV caching, and any constraints such as eviction policy or what to cache) and explicitly discuss the tradeoffs you are accepting.

Choosing a KV-cache strategy for shared-prefix traffic under GPU memory pressure

You operate an internal LLM inference service for employees. Traffic has two dominant patterns: (1) many requests start with the same 200-token “policy + tool instructions” prefix and then diverge, and (2) a smaller number of ad‑hoc requests have long, unique prompts (2,000–6,000 tokens). The service uses continuous batching and must keep p95 latency stable.

A proposed redesign includes: (a) prefix caching that stores the KV cache state for the shared 200-token prefix so future requests can skip recomputing that portion of the prompt, and (b) PagedAttention (paged KV caching) so each sequence’s KV cache grows in fixed-size pages rather than requiring a single contiguous allocation.

Write an evaluation that explains, in one coherent argument, how this redesign changes GPU compute and memory behavior across BOTH the prefilling phase and the token-by-token decoding phase. Your answer must:
- Explain what work is avoided (and what is not avoided) when a request hits the prefix cache, and how that changes prefilling cost and time-to-first-token.
- Explain why decoding still depends on the KV cache and how KV cache growth during decoding interacts with variable output lengths.
- Analyze how memory fragmentation can arise in a standard contiguous KV allocation scheme under this workload, and how paged KV allocation changes the failure/throughput profile.
- Identify at least two concrete tradeoffs/risks introduced by combining prefix caching with paged KV caching (e.g., memory overhead, eviction behavior, page table/indirection costs, cache hit-rate sensitivity), and recommend one operational policy (e.g., what to cache/evict or when to disable caching) to keep p95 latency stable.

Assume the model is an autoregressive Transformer decoder and that the KV cache stores keys/values for all previously processed tokens (prompt + generated tokens).

Evaluating a serving design that combines prefix caching with paged KV memory under mixed prompt lengths

You are on-call for an internal LLM chat-completions service used by multiple product teams. Traffic has two dominant patterns: (1) many requests share an identical 250-token system prompt (policy + formatting) but have different user messages; (2) a smaller set of power users send very long, unique prompts (2,000–6,000 tokens). The service uses continuous batching and standard contiguous KV-cache allocation per sequence.

Symptoms over a 2-hour window:
- P50 time-to-first-token (TTFT) is good, but P99 TTFT spikes when long prompts arrive.
- During spikes, GPU monitoring shows ~25–35% total memory free, yet new long requests sometimes fail to start with an out-of-memory/allocation error.
- When failures happen, short requests still decode, but overall throughput drops.

You are allowed to change only inference-time memory/caching strategy (no model changes). Propose a concrete design that addresses BOTH (a) the TTFT spikes and (b) the allocation failures, using KV-cache behavior across prefilling vs decoding, prefix caching, and a fragmentation-aware KV memory scheme. In your answer, explain the causal chain from the current design to the observed symptoms, and justify the tradeoffs your design makes (e.g., memory overhead vs compute saved, and any impact on decoding performance).

Stabilizing latency and GPU memory in a chat-completions service with shared system prompts

You are the on-call engineer for an internal LLM gateway that serves two workloads on the same GPU pool: (A) a chat product where every request begins with the same 600-token system prompt, and (B) an agent workflow that sends highly variable prompts (50–4000 tokens) and often streams 800–1500 generated tokens. The serving stack uses continuous batching and stores each sequence’s KV cache in GPU memory during generation.

After a traffic spike, you observe the following symptoms over a 30-minute window:
1) Median time-to-first-token (TTFT) increases sharply, but tokens/second during streaming generation degrades only mildly.
2) GPU memory monitoring shows ~25% free memory, yet new long agent requests frequently fail to start with an out-of-memory allocation error.
3) When you temporarily disable reuse of the shared 600-token system prompt (i.e., you always recompute it per request), TTFT gets worse but the OOM allocation failures become less frequent.

Assume the model is a standard autoregressive Transformer with a KV cache; inference consists of an initial prompt-processing stage that populates the KV cache followed by token-by-token generation that appends to the KV cache.

As the incident owner, propose ONE coherent serving change (a single design choice, not a list) that best explains and addresses all three symptoms at once. Your answer must (i) identify the most likely root cause linking TTFT behavior and the “free memory but OOM” paradox, and (ii) justify why your chosen change improves the situation by explicitly referencing how it affects KV-cache allocation during prompt processing vs. token-by-token generation, and how it interacts with shared-prefix reuse.

Post-incident analysis: KV-cache growth, fragmentation, and shared-prefix reuse in a streaming LLM service

You are the on-call engineer for an internal LLM gateway that serves two high-volume products on the same GPU pool: (A) a customer-support chat agent and (B) a report generator. Both products use the same 220-token system prompt, but user prompts vary from 20–2,000 tokens. Typical outputs are 50 tokens for (A) and 1,500 tokens for (B). The serving stack uses continuous batching and stores each request’s KV cache in a single contiguous allocation that grows as decoding proceeds.

Over the last week, you observe two symptoms that often occur together during peak hours:
1) New long requests fail to start with an out-of-memory error even when monitoring shows ~25% of GPU memory is free.
2) P99 token latency during streaming generation increases steadily over time, especially when many long outputs are in flight.

A teammate proposes a quick fix: “Enable prefix caching for the shared system prompt; that will reduce compute and should also fix the memory issues.” Another teammate proposes: “Switch KV cache allocation to a paged/block-based scheme (PagedAttention-style) to eliminate fragmentation; prefix caching is optional.”

As the incident lead, choose which proposal you would implement first (prefix caching first vs paged KV caching first), and justify your decision by explicitly connecting: (i) what happens in prefilling vs decoding, (ii) how the KV cache grows and is reused across decoding steps, (iii) why the system can OOM despite free memory (fragmentation), and (iv) how your chosen change affects both memory behavior and end-to-end latency for these two products. Your answer should also name one concrete risk/tradeoff introduced by your chosen change.

Learn Before

Related

Learn After