1. Implement single-step decode with a KV cache in PyTorch, for causal multi-head attention.
The full question
Implement single-step decode with a KV cache in PyTorch, for causal multi-head attention. Then say what changes for a long-context serving system.
Model answer
The cache stores past K/V so each new token attends over history without recomputing it:
import torch, torch.nn.functional as F
class KVCacheAttention:
def __init__(self, n_heads, head_dim):
self.n_heads, self.head_dim = n_heads, head_dim
self.k_cache, self.v_cache = None, None # each: B, H, T, hd
def step(self, x, wq, wk, wv, wo):
# x: B,1,D -> one new token
B, _, D = x.shape
q = (x @ wq).view(B, 1, self.n_heads, self.head_dim).transpose(1, 2)
k = (x @ wk).view(B, 1, self.n_heads, self.head_dim).transpose(1, 2)
v = (x @ wv).view(B, 1, self.n_heads, self.head_dim).transpose(1, 2)
self.k_cache = k if self.k_cache is None else torch.cat([self.k_cache, k], dim=2)
self.v_cache = v if self.v_cache is None else torch.cat([self.v_cache, v], dim=2)
att = (q @ self.k_cache.transpose(-2, -1)) / self.head_dim**0.5 # B,H,1,T
out = F.softmax(att, dim=-1) @ self.v_cache # B,H,1,hd
return out.transpose(1, 2).reshape(B, 1, D) @ wo
Points that get probed: no causal mask is needed at decode because the new query legitimately attends to all past positions; the cache grows by one position per step; RoPE would be applied to q and the new k before appending. What changes at serving scale: torch.cat reallocating every step is unacceptable, so real systems pre-allocate paged blocks (paged attention) and index into them; the cache is the dominant memory consumer, so you compress it (MLA/GQA) and reuse shared prefixes across requests; and you batch many sequences of different lengths together (continuous batching), which needs per-sequence length bookkeeping and a scheduler that admits and evicts under a memory budget.
Follow-ups: Why does paged allocation help fragmentation and admission control? Where would you slot in a rolling-window cache if the model used sliding-window attention?