← All problems
#115 Fused QKV RoPE KV Cache Update Medium

Implement the fused QKV projection + rotary embedding + KV-cache update that every LLaMA-style attention layer runs at the start of a decoding step. A batch of B sequences each contribute a single new token, whose hidden state is row b of x (shape [B, d_model]). One fused weight matrix W_qkv (shape [d_model, (H_q + 2 × H_kv) × D]) produces the query, key, and value projections in a single matrix multiply. Rotary positional embeddings are applied to the query and key (never to the value), and the rotated key and the value are written into the slot positions[b] of the paged KV cache. All tensors are float32 except positions, which is int32.

For each sequence b, let qkv = x[b] × W_qkv. The first H_q × D values of qkv are the query heads, the next H_kv × D values are the key heads, and the last H_kv × D values are the value heads (grouped-query attention uses H_kv ≤ H_q). Each group is reshaped row-major into [heads, D].

Rotation uses the precomputed table cos_sin_cache of shape [S_max, D], whose row p stores D/2 cosines followed by D/2 sines. With p = positions[b], c = cos_sin_cache[p, 0 : D/2] and s = cos_sin_cache[p, D/2 : D], the rotate-half transform of a head vector t of length D is:

\( \text{RoPE}(t)_{j} = t_{j}\,c_{j} - t_{j + D/2}\,s_{j}, \qquad \text{RoPE}(t)_{j + D/2} = t_{j + D/2}\,c_{j} + t_{j}\,s_{j}, \qquad 0 \le j < D/2 \)

The outputs are then, for every sequence b, every query head hq, and every KV head h:

\( \text{Q_out}[b, hq, :] = \text{RoPE}(q[b, hq, :]) \)

\( \text{K_cache}[b, h, \text{positions}[b], :] = \text{RoPE}(k[b, h, :]), \qquad \text{V_cache}[b, h, \text{positions}[b], :] = v[b, h, :] \)

Every other slot of K_cache and V_cache must keep the value it had on entry.

qkv = x[b] · W_qkv → (H_q + 2·H_kv)·D values x[b] [d_model] · W_qkv Q (H_q · D) K (H_kv · D) V (H_kv · D) cos_sin_cache[pos[b]] cos = [0 : D/2], sin = [D/2 : D] RoPE rotate-half (Q and K only) Q_out[b] [H_q, D] K_cache[b, :, pos[b], :] V_cache[b, :, pos[b], :] one (b, h) row of the cache: S_max slots pos[b] only slot pos[b] is written — every other slot keeps its previous contents

Implementation Requirements

Example

Input: B = 1, d_model = 2, H_q = 1, H_kv = 1, D = 2, S_max = 2

\(x\) (\(1 \times 2\)): \[ x = \begin{bmatrix} 1.0 & 0.0 \end{bmatrix} \] \(W_\text{qkv}\) (\(2 \times 6\)): \[ W_\text{qkv} = \begin{bmatrix} 1.0 & 0.0 & 0.0 & 1.0 & 1.0 & 1.0 \\ 0.0 & 1.0 & 1.0 & 0.0 & 2.0 & 2.0 \end{bmatrix} \] \(\text{cos_sin_cache}\) (\(2 \times 2\)): \[ \text{cos_sin_cache} = \begin{bmatrix} 1.0 & 0.0 \\ 0.5403023 & 0.8414710 \end{bmatrix} \] \(\text{positions} = \begin{bmatrix} 1 \end{bmatrix}\), and \(K_\text{cache}\), \(V_\text{cache}\) (each \(1 \times 1 \times 2 \times 2\)) start filled with zeros.

Intermediate steps: the fused projection gives \[ qkv = x \cdot W_\text{qkv} = \begin{bmatrix} 1.0 & 0.0 & 0.0 & 1.0 & 1.0 & 1.0 \end{bmatrix} \] so \(q = \begin{bmatrix} 1.0 & 0.0 \end{bmatrix}\), \(k = \begin{bmatrix} 0.0 & 1.0 \end{bmatrix}\), \(v = \begin{bmatrix} 1.0 & 1.0 \end{bmatrix}\). With \(\text{positions}[0] = 1\) we read \(c = 0.5403023\), \(s = 0.8414710\), giving \[ \text{RoPE}(q) = \begin{bmatrix} 0.5403023 & 0.8414710 \end{bmatrix}, \qquad \text{RoPE}(k) = \begin{bmatrix} -0.8414710 & 0.5403023 \end{bmatrix} \]

Output: \[ \text{Q_out}[0] = \begin{bmatrix} 0.5403023 & 0.8414710 \end{bmatrix} \] \[ \text{K_cache}[0, 0] = \begin{bmatrix} 0.0 & 0.0 \\ -0.8414710 & 0.5403023 \end{bmatrix}, \qquad \text{V_cache}[0, 0] = \begin{bmatrix} 0.0 & 0.0 \\ 1.0 & 1.0 \end{bmatrix} \] Slot 0 of both caches is untouched; only slot 1 is written.

Constraints

References

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.