Implement Grouped-Query Attention

HardML Coding

Reported in interviews at Alibaba Datadog Google Mistral AI Startups Com

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.)

  • x is $T \times D$. Wq is $D \times (H d_h)$, Wk and Wv are $D \times (H_{kv} d_h)$, Wo is $(H d_h) \times D$. $H$ = n_heads, $H_{kv}$ = n_kv_heads divides $H$, and $d_h$ = (columns of Wq) / $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