Implement a KV Cache for Generation

Free with account Updated Nov 16, 2026 · 5 min read
On this page

    Problem statement

    Add a KV cache to a causal self-attention layer. Write a KVCache that stores keys and values for one sequence, and an attend_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

    Without a cache, every step recomputes keys and values for the whole prefix. With one, only the new token is projected.
    Without a cache, every step recomputes keys and values for the whole prefix. With one, only the new token is projected.
    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

    1. One sequence or a batch with different lengths? (One.)
    2. Preallocate to a maximum length, or grow dynamically? (Preallocate.)
    3. Is there positional encoding inside attention (RoPE)? (Not here; note the offset.)
    4. What happens when the cache is full? (Raise an error; sliding windows are a follow-up.)
    5. Per layer or for the whole model? (Per layer: each layer has its own cache.)