← All problems
#96 INT8 KV Cache Attention Medium

Implement decode-phase multi-head attention where the key and value caches are stored as int8 with per-token scale factors. This memory layout halves KV-cache bandwidth versus float32 and is used in production LLM serving systems such as TensorRT-LLM and vLLM. Given a query tensor Q for a single new token, int8 key cache K_int8, int8 value cache V_int8, and per-token scales k_scale and v_scale, dequantize the caches and compute scaled dot-product attention to produce output. All non-integer tensors use float32.

Implementation Requirements

Example

With num_heads = 1, seq_len = 3, head_dim = 4:

Input:
\(Q\) (1×4): \[ \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \] \(K\_int8\) (1×3×4): \[ \begin{bmatrix} 10 & 0 & 0 & 0 \\ 0 & 10 & 0 & 0 \\ 0 & 0 & 10 & 0 \end{bmatrix} \] \(k\_scale\) (1×3): \(\begin{bmatrix} 0.1 & 0.1 & 0.1 \end{bmatrix}\)  ⇒  \(K\_float\) (1×3×4): \[ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \] \(V\_int8\) (1×3×4): \[ \begin{bmatrix} 10 & 20 & 30 & 40 \\ 50 & 60 & 70 & 80 \\ 90 & 100 & 110 & 120 \end{bmatrix} \] \(v\_scale\) (1×3): \(\begin{bmatrix} 0.1 & 0.1 & 0.1 \end{bmatrix}\)  ⇒  \(V\_float\) (1×3×4): \[ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{bmatrix} \]

Scores = \(Q \cdot K\_float^T / \sqrt{4}\) = \(\begin{bmatrix} 0.5 & 0.5 & 0.5 \end{bmatrix}\), so softmax weights = \(\begin{bmatrix} 1/3 & 1/3 & 1/3 \end{bmatrix}\).

Output (1×4): \[ \begin{bmatrix} 5.00 & 6.00 & 7.00 & 8.00 \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.