Implement Grouped-Query Attention
Problem statement
Many recent decoder-only LLMs replace standard multi-head attention (MHA) with grouped-query attention (GQA): there are $H$ query heads but only $H_{kv}$ key/value heads, and each group of $H / H_{kv}$ consecutive query heads shares one key/value head. $H_{kv} = H$ recovers MHA and $H_{kv} = 1$ is multi-query attention (MQA).
Implement the forward pass of causal GQA self-attention for a single sequence. (The interview asked for PyTorch; our runner has numpy, and the tensor operations map one-to-one: np.repeat on the head axis is torch.repeat_interleave.)
xis $T \times D$.Wqis $D \times (H d_h)$,WkandWvare $D \times (H_{kv} d_h)$,Wois $(H d_h) \times D$. $H$ =n_heads, $H_{kv}$ =n_kv_headsdivides $H$, and $d_h$ = (columns ofWq) / $H$.- $Q = xW_q$, $K = xW_k$, $V = xW_v$. Query head $h$ is the column block $[h d_h, (h+1) d_h)$ of $Q$; KV head $g$ is the same block of $K$ and $V$.
- Query head $h$ uses KV head $g = \lfloor h / (H / H_{kv}) \rfloor$.
- Per query head: scores $Q_h K_g^{\top} / \sqrt{d_h}$, a causal mask (position $i$ attends only to $j \le i$), a numerically stable row softmax, then multiply by $V_g$.
- Concatenate the $H$ head outputs in head order and multiply by $W_o$. No biases, no dropout.
Return the $T \times D$ output as a list of lists. Afterwards, be ready to explain how much KV-cache memory GQA saves compared with MHA and MQA.
def gqa_forward(x, Wq, Wk, Wv, Wo, n_heads, n_kv_heads) -> list:
...
Constraints
- $1 \le T \le 24$, $1 \le D \le 16$, $1 \le H \le 8$, $H_{kv}$ divides $H$, $1 \le d_h \le 8$.
- Some tests have attention scores in the thousands, so the softmax must subtract the row maximum.
- Outputs are compared with a relative tolerance of $10^{-7}$.
Examples
Example 1 (MQA, $T = 2$, $D = 2$, $H = 2$, $H_{kv} = 1$, $d_h = 1$):
x = [[1, 0], [0, 1]] Wq = [[1, 0], [0, 1]] Wk = [[1], [1]] Wv = [[1], [2]]
Wo = [[1, 0], [0, 1]]
output: [[1.0, 1.0], [1.5, 1.5]]
Both query heads read the single KV head: $K = [1, 1]^{\top}$ and $V = [1, 2]^{\top}$. Position 0 sees only itself (value 1 in both heads); at position 1 both keys score equally, so each head averages the values to 1.5.
Example 2 ($T = 1$): with a single position the softmax weight is 1, so the output is $x W_v$ copied to every query head of the group, then multiplied by $W_o$. For x = [[0.5, -1]], Wv = [[2, 0], [1, 1]], $H = 2$, $H_{kv} = 1$, $d_h = 2$ and Wo = [[1, 0], [0, 1], [1, 1], [0, 2]], the head output is $[0, -1]$, the concatenation is $[0, -1, 0, -1]$ and the answer is [[0.0, -3.0]].
Show hint
Once each query head knows which key/value head it reads, how much of the remaining code is ordinary multi-head attention?
Relevant roles: LLM Engineer, Deep Learning Engineer, Research Scientist and ML Engineer.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium