Articles
KV Cache Management Interview Questions: Prefix Sharing, Eviction, and Memory Pressure
Prepare for KV cache interview questions on prefix sharing, block allocation, eviction, GPU memory pressure, and serving trade-offs.
Three requests arrive with the same long system instruction and different user questions. A prefix cache might save prefill work by reusing the shared key/value state. A fourth request arrives while GPU memory is nearly full. Which blocks may be reused, which may be evicted, and which must remain because an active decode still needs them? That is the practical core of a KV cache management interview.
This guide answers those questions with a synthetic block-pool exercise. For the underlying mechanics, start with Explain KV cache in Transformer inference, then return to the ownership and memory-pressure decisions here.
Evidence boundary: Official vLLM and Hugging Face documentation supports the named implementation mechanisms below. The block counts and memory figures are illustrative arithmetic, not measured throughput or a claim about a particular production model or employer's interview process.
The short answer: cache state has a lifecycle
During autoregressive generation, a decoder stores attention keys and values for previous tokens so later tokens do not recompute the entire prefix at every step. The KV cache grows as live token positions accumulate, subject to architecture details such as layer count, KV heads, head dimension, dtype, and sliding-window behavior. Model weights and activations still consume memory too. A request that fits alone may fail when several long sequences run together.
Prefix sharing reuses identical previously computed prompt blocks across compatible requests. It can reduce prefill computation and time to first token, but it does not make all future decode tokens shared. Once requests diverge, each grows its own KV state. Cached blocks that no active request references may be retained for likely reuse; when memory is needed, those retained blocks are candidates for eviction. Active blocks are different: reclaiming them without a supported preemption, recompute, or offload path would break a live generation.
Make the state categories explicit: active-and-referenced; cached-but-unreferenced; free or reclaimable; and queued demand not yet admitted. An interview answer that says “use LRU” before identifying these categories risks evicting the wrong thing. The scheduler and cache manager need a coherent policy for who gets GPU capacity next.
What makes two prefixes actually shareable?
A repeated sentence is not sufficient. Reuse depends on the same tokenized prefix under a compatible model and execution configuration, including tokenizer, model or adapter, positional context, and any multimodal inputs that affect the computation. vLLM's current automatic prefix-caching design hashes full blocks using the parent block hash, token IDs, and relevant extra hashes. Its documentation says it caches full blocks and discusses additional values such as LoRA IDs, multimodal hashes, and cache salts. These are vLLM details, not a universal contract for every inference server.
Consider a common system instruction followed by three user messages. If the instruction maps to four full blocks, those blocks can be reused after the first compatible request computes them. A request with a changed first token diverges immediately; it cannot borrow downstream blocks merely because later text happens to match. A request whose difference occurs after the four-block common prefix can reuse those four blocks but must compute its own suffix and decode state.
This explains why prompt layout matters. Stable instructions and static examples should appear before per-user material if doing so is semantically correct and permitted by the application. Moving dynamic timestamps or tenant identifiers into the first line can destroy common-prefix locality. Do not reorder content solely for cache efficiency if it changes behavior, authorization, or the model's required instruction hierarchy.
There is a security boundary too. vLLM documents optional per-request cache salting to isolate reuse across trust groups. A cross-tenant cache hit can create timing signals even when raw KV values are not directly returned. A cache key must cover the relevant computational and isolation context; a shared prompt string is not permission to share across customers. If salts differ, expect lower reuse and budget accordingly.
Trace three requests through a block pool
Use a deliberately small thought experiment. A pool has 24 blocks. A common prompt prefix fills four blocks. Request A adds two private prompt blocks and one decode block; B adds three private blocks and one decode block; C adds one private block and one decode block. Suppose all three are active. The shared prefix occupies four physical blocks, not twelve, while the private and decode blocks occupy nine more. The total in this simplified ledger is 13 blocks.
This arithmetic is conditional. It assumes full-block prefix reuse, no extra allocations, and compatible requests. A real engine's block sizes, partially filled blocks, preallocation, allocator metadata, attention architecture, and scheduler policy change the exact number. The purpose is to show the accounting method: shared physical prefix plus each request's private live state, not the naive sum of full prompt lengths.
| State in toy pool | Blocks | Reclaimable now? |
|---|---|---|
| Shared prefix referenced by A, B, and C | 4 | No, while any request uses it |
| A's private prompt and decode state | 3 | No, while A is active |
| B's private prompt and decode state | 4 | No, while B is active |
| C's private prompt and decode state | 2 | No, while C is active |
| Capacity not yet occupied | 11 | Yes, subject to admission reserve |
Now A finishes. Its private blocks can be freed or retained as cached reusable state depending on the engine; the four shared prefix blocks remain referenced by B and C. If B and C finish too, the common prefix can remain cached but unreferenced. It may accelerate another request, yet it is not sacred capacity. When a new request needs space, the manager can reclaim such blocks according to its policy.
vLLM's documented prefix-cache design describes a free queue and LRU eviction of cached blocks selected for reuse as capacity is allocated. Do not generalize its exact queue mechanics to other engines. The interview invariant is broader: an eviction candidate must not be required by a live request, and the cache metadata must cease claiming the block's old identity before the memory is reassigned.
A memory budget that exposes the trade-off
For another toy calculation, assume each block represents 8 MiB of KV storage and the pool has 24 blocks. The pool is 192 MiB. If 13 blocks are live, 104 MiB of this toy pool is occupied and 88 MiB remains; these numbers deliberately ignore model weights, activations, fragmentation, and other GPU allocations. A fourth request needing 12 blocks does not fit without reclaiming or delaying something, even though the machine might have free memory elsewhere.
Do not call 8 MiB a typical block size. Real bytes per token depend on layers, KV heads, head dimension, and precision; the relation can change with grouped-query attention or sliding windows. A useful first-order estimate is proportional to live tokens times layers times KV heads times head dimension times two for K and V times bytes per element, subject to implementation-specific layout. Then reserve additional headroom rather than allocating until a GPU out-of-memory error occurs.
Estimate peak concurrent live tokens, not just average prompt length. A workload with a few very long generations may dominate capacity while short requests wait. Distinguish prefill tokens from generated tokens, and track how cancellations or finished sequences release references. A scheduler that admits too many long prompts can create a large simultaneous decode footprint even if average traffic looks modest.
For an interview, show both a resource ledger and a request policy. If the fourth request needs more blocks than the free pool plus safe-to-evict cached blocks, either queue it, reject it under overload, preempt or recompute a supported request, move state to a slower tier, or reduce the allowed context/generation budget. Each choice has a user-visible latency or quality consequence.
What does eviction actually remove?
The word “eviction” can describe several operations. Evicting an unreferenced reusable prefix merely sacrifices a future cache hit; an active request can continue. Preempting an active sequence means its generation stops making progress until state is restored or recomputed. Offloading moves some KV state to another memory tier and trades GPU capacity for transfer cost. Reducing maximum context or output length limits demand before it is allocated.
Do not answer that all full cache blocks are interchangeable. A block may be referenced by several requests; its reference count or equivalent ownership record matters. In the toy pool, B and C still use the four shared blocks after A finishes. Evicting them because “A is done” would corrupt the remaining requests. Only after the last reference is gone can those blocks become an ordinary cached reuse candidate.
Hugging Face's Transformers cache documentation describes offloaded and quantized cache strategies. Offloading can save GPU memory but introduces transfer overhead; quantization can reduce storage but may not improve latency for short contexts when memory is plentiful. These are available strategy families, not a free universal fix. Benchmark on the actual model, sequence-length distribution, hardware, and latency objective.
Likewise, prefix retention policy has a hit-rate versus capacity trade-off. Keeping many cold prefixes can starve new work; evicting aggressively makes repeated long prompts pay prefill cost again. A simple LRU can be a reasonable baseline, but tenancy, request priority, prefix length, and reuse frequency may justify different quotas or admission rules. State how you would measure the result before proposing complexity.
What should happen under GPU memory pressure?
First establish whether the pressure is KV cache or another allocation. Watch free KV blocks, live token counts, queued requests, cache-hit ratio, time to first token, inter-token latency, and OOM or preemption counts. vLLM publishes production metrics, but metric names and labels can change across releases; map the measurements to your deployed version. If the queue grows while KV blocks are full, adding CPU workers alone will not create GPU KV capacity.
Then classify reclaimable bytes. Reuse unreferenced cached blocks before treating active sequences as disposable, if the engine's allocator supports that behavior. Keep a reserve for decode growth of already admitted requests. If a request can grow far beyond its prompt, admission based only on prompt tokens can overpromise capacity. Set maximum output tokens or reserve pessimistically enough to avoid mid-generation failure.
If pressure persists, compare responses: shorten allowed contexts, apply per-tenant concurrency limits, queue with a deadline, scale GPU replicas, use supported preemption/recompute, or test quantized/offloaded KV. Long-context throughput and latency can move in opposite directions. An optimization that raises maximum concurrency might worsen time to first token; a prefix cache that improves average latency might create unpredictable cold-miss tails.
The failure drill is specific. Drive a warm-prefix workload, then add unique long prompts until memory pressure rises. Cancel one request and verify its private blocks become available without invalidating another request's shared prefix. Force eviction of unreferenced cached blocks, then repeat the original prompt and observe a miss rather than wrong output. Finally test two tenants with different salts and verify no cross-tenant reuse.
How do you distinguish a bad cache from a bad workload?
Measure eligible prefix tokens as well as observed hits. A low hit ratio can be expected when prompts are highly personalized or begin with dynamic content. A high hit ratio with poor latency can still occur if the private suffix and decode dominate. An average hit ratio hides whether one tenant benefits while another suffers. Segment by prompt template, model, adapter, tenant boundary, context length, and time since warmup.
Separate capacity and locality experiments. For locality, hold concurrency steady and compare stable versus shuffled prompt prefixes. For capacity, hold the prompt distribution steady and vary concurrent live tokens. That isolates “prefixes do not match” from “useful blocks are evicted before reuse.” Track prefill work, queue wait, decode throughput, and tail latency together.
Do not confuse API-level prompt caching with server-side KV reuse. A provider may expose billing or token-accounting semantics for cached prompts, while a particular engine manages physical GPU KV blocks. The interview question here is about the latter. Ask whether the interviewer means within-request KV reuse, cross-request prefix sharing, or a hosted API's cache product before selecting metrics or guarantees.