Implement a KV Cache for Generation
On this page
Problem statement
Add a KV cache to a causal self-attention layer. Write a
KVCachethat stores keys and values for one sequence, and anattend_step(x_new, cache, ...)that processes new tokens: the whole prompt at once (prefill), then one token at a time (decode). The outputs must equal those of full attention over the whole sequence computed without a cache.
A common follow-up to "implement attention" in ML coding rounds for inference and AI infra roles. It checks whether you understand why generation is expensive and how serving engines avoid recomputation.
Example

prompt: 4 tokens → prefill: one call with t = 4, cache.len = 4
decode: tokens 5, 6, 7 one at a time, cache.len = 5, 6, 7
check: concatenated outputs == full attention over all 7 tokens → True
Constraints (assumed)
- One sequence (batching is a follow-up); fixed
max_len. - NumPy only; weights (D, D); D divisible by the number of heads.
- Causal attention.
What this question tests
- Understanding the prefill vs decode split (see Prefill, Decode and the KV Cache).
- Absolute positions in the mask (and for RoPE, if used).
- Memory layout and preallocation instead of repeated concatenation.
- A correctness test against a reference.
Questions to ask first
- One sequence or a batch with different lengths? (One.)
- Preallocate to a maximum length, or grow dynamically? (Preallocate.)
- Is there positional encoding inside attention (RoPE)? (Not here; note the offset.)
- What happens when the cache is full? (Raise an error; sliding windows are a follow-up.)
- Per layer or for the whole model? (Per layer: each layer has its own cache.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.