← All problems
#114 Multi Head Latent Attention Hard

Implement one decode step of Multi-Head Latent Attention (MLA), the attention variant used by DeepSeek-V2/V3. Instead of caching a full key and value vector per head, MLA caches a single low-rank latent vector c of size kv_lora_rank per position, shared by every head, plus a small rotary key k_pe of size rope_dim that is also shared. Keys and values are reconstructed on the fly from the latent through the per-head up-projections W_UK and W_UV.

Materializing every key and value would defeat the purpose of the compressed cache, so production kernels use weight absorption: fold W_UK into the query and run the whole attention in latent space. For a single decode query with per-head query q = [q_nope | q_pe] and cache row kv_cache[s] = [c[s] | k_pe[s]]:

\[ \tilde{q}_h = q\_nope_h W\_UK_h \qquad s_{h,t} = \frac{\tilde{q}_h \cdot c_t + q\_pe_h \cdot k\_pe_t}{\sqrt{head\_dim + rope\_dim}} \] \[ a_h = \text{softmax}(s_h) \qquad o_h = \left( \sum_{t=0}^{seq\_len-1} a_{h,t}\, c_t \right) W\_UV_h \]

Note that c plays the role of both key and value, and that the rotary term uses the same k_pe for every head. All tensors are float32.

MLA decode: one shared latent cache serves all heads kv_cache (seq_len rows) c[0] (kv_lora_rank) c[1] ... c[seq_len-1] k_pe k_pe ... k_pe no per-head K / V stored queries q[0] = nope | pe q[1] q[num_heads-1] per head h: q~ = q_nope · W_UK[h] s = (q~·c + q_pe·k_pe) * scale a = softmax(s) l = sum_t a[t] * c[t] out[h] = l · W_UV[h] scale = 1/sqrt(head_dim+rope_dim) attention runs entirely in latent space: c[t] acts as both key and value, and W_UV is applied once per head after the weighted sum, not per position

Implementation Requirements

Example

With num_heads = 2, seq_len = 2, kv_lora_rank = 2, head_dim = 2, rope_dim = 1:

\(q\) (2×3, last column is q_pe): \[ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \qquad kv\_cache\text{ (2}\times\text{3, last column is } k\_pe\text{):} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix} \] \(W\_UK_0\) (2×2): \[ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \qquad W\_UK_1\text{ (2}\times\text{2):} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \] \(W\_UV_0\) (2×2): \[ \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \qquad W\_UV_1\text{ (2}\times\text{2):} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \]

Output (2×2, values rounded to 4 decimals): \[ \begin{bmatrix} 2.0000 & 3.0000 \\ 0.6405 & 0.3595 \end{bmatrix} \]

Head 0 scores are equal, so its attention is uniform and the latent result is [0.5, 0.5]. Head 1 sees scores [0.5774, 0], giving weights [0.6405, 0.3595], which pass through the identity W_UV unchanged.

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.