← All problems
#26 Multi Head Cross Attention Hard

Implement multi-head cross-attention, the building block used in encoder-decoder transformers such as T5, BART, and Whisper, as well as the text-conditioning layers of diffusion models like Stable Diffusion. Given decoder queries Q of shape (M, H, D) and encoder keys K / values V of shape (N, H, D), compute, for each head h, scaled dot-product attention where every one of the M queries attends to all N encoder positions:

\[ \text{head}_h = \text{softmax}\!\left(\frac{Q_h K_h^{\top}}{\sqrt{D}}\right) V_h \]

There is no causal mask — encoder positions are fully visible to every decoder query — and the query length M may differ from the key/value length N. All tensors use float32.

Multi-Head Cross-Attention: decoder queries attend to encoder keys/values Encoder K, V (N positions) K[0], V[0] K[1], V[1] ... K[N-1], V[N-1] Decoder Q (M queries, may differ from N) Q[0] Q[1] Q[M-1] for each head h: S = Q_h K_h^T / sqrt(D) A = softmax(S, dim=-1) O_h = A V_h no causal mask M may differ from N

Implementation Requirements

Example

With M = 2, N = 3, H = 2, D = 2. Tensors are laid out as (position, head, dim). Per-head views:

\(Q_0\) (2×2): \[ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \qquad Q_1\text{ (2}\times\text{2):} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \] \(K_0\) (3×2): \[ \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} \qquad K_1\text{ (3}\times\text{2):} \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ 1 & 1 \end{bmatrix} \] \(V_0\) (3×2): \[ \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix} \qquad V_1\text{ (3}\times\text{2):} \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} \]

Output (values rounded to 4 decimals): \[ \text{output}_0\text{ (head 0, 2}\times\text{2):} \begin{bmatrix} 3.0000 & 4.0000 \\ 3.4067 & 4.4067 \end{bmatrix} \qquad \text{output}_1\text{ (head 1, 2}\times\text{2):} \begin{bmatrix} 9.0000 & 10.0000 \\ 9.4067 & 10.4067 \end{bmatrix} \]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.