Self-Attention with a KV Cache for Incremental Decoding
Problem statement
During autoregressive generation, a transformer produces one token at a time. Recomputing keys and values for the whole prefix at every step is wasteful, so decoders keep a key/value cache: each step projects only the new token(s), appends their keys and values to the cache, and attends over everything cached so far.
Implement one multi-head causal self-attention layer with a KV cache in numpy, and a driver that feeds it a prompt followed by decoding steps.
def cached_attention(Wq, Wk, Wv, Wo, n_heads: int, chunks: list) -> list:
...
Wq,Wk,Wv,Woare $d_{model} \times d_{model}$ matrices (nested lists). Use the row-vector convention: $q = x W_q$, $k = x W_k$, $v = x W_v$.chunksis a list of token blocks; block $i$ is an $m_i \times d_{model}$ list of input vectors. The first block is the prompt (prefill); later blocks are decoding steps, usually one token each, occasionally a few.- For each block, in order: project only the new tokens to $Q, K, V$; append the new $K, V$ rows to the cache; then the new token at absolute position $p$ (counting from 0 across all blocks) attends to cached positions $0, \dots, p$. Tokens inside a multi-token block must not see later tokens of the same block.
- Heads: $d_h = d_{model} / n_{heads}$, and head $j$ uses columns $j d_h$ to $(j+1) d_h - 1$ of $Q$, $K$ and $V$. Scores are $q \cdot k / \sqrt{d_h}$, turned into weights with a numerically stable softmax. Concatenate the head outputs in head order and multiply by $W_o$.
- No biases, no positional encodings, no dropout.
Return a list with one entry per block: that block's $m_i \times d_{model}$ outputs as nested lists. Answers are checked with a relative and absolute tolerance of $10^{-6}$.
Constraints
- $d_{model} \in \{2, 4, 8, 16\}$, $n_{heads} \in \{1, 2, 4\}$ dividing $d_{model}$
- At most 30 tokens in total; input entries can be as large as a few hundred in magnitude
Examples
Example 1 (identity weights, one head, $d_{model} = 4$):
chunks = [[[1, 0, 0, 0], [0, 1, 0, 0]], # prompt: 2 tokens
[[0, 0, 2, 0]]] # one decoding step
output (rounded): [[[1.0, 0.0, 0.0, 0.0], [0.3775, 0.6225, 0.0, 0.0]],
[[0.1065, 0.1065, 1.574, 0.0]]]
Token 0 sees only itself. Token 1 scores $[0, 1] / \sqrt 4 = [0, 0.5]$ against positions 0 and 1. The decoding token scores $[0, 0, 4] / 2 = [0, 0, 2]$, so it puts weight $e^2/(2 + e^2) \approx 0.787$ on itself.
Example 2 (a consistency check): feeding a 5-token sequence as one prefill block, or as a 2-token block followed by three 1-token blocks, must produce exactly the same 5 output rows.
Show hint
Which of the per-token quantities in causal self-attention never change once a token has been processed?
Relevant roles: LLM Engineer, Deep Learning Engineer, ML Engineer and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium