← All problems
#119 Block Sparse KV Selection Hard

Implement one decode step of block-sparse attention with query-aware KV selection, the technique used by sparse-attention inference kernels such as NSA and Quest. Reading the whole KV cache for every generated token is bandwidth-bound, so the cache is split into contiguous blocks of block_size positions, each block is summarized by its mean-pooled key, and only the num_selected blocks whose summary looks most relevant to the current query are read at full resolution. Attention is then computed over the positions of the selected blocks only.

For each head h, with num_blocks = ceil(seq_len / block_size) and block b covering positions [b * block_size, min((b + 1) * block_size, seq_len)):

\[ \bar{k}_{h,b} = \frac{1}{|b|}\sum_{t \in b} K_{h,t} \qquad \sigma_{h,b} = Q_h \cdot \bar{k}_{h,b} \] \[ S_h = \text{top-}num\_selected\ \text{blocks by } \sigma_{h,b} \qquad P_h = \{\, t : t \in b,\; b \in S_h \,\} \] \[ o_h = \sum_{t \in P_h} \frac{\exp\!\left(\frac{Q_h \cdot K_{h,t}}{\sqrt{head\_dim}}\right)} {\sum_{u \in P_h} \exp\!\left(\frac{Q_h \cdot K_{h,u}}{\sqrt{head\_dim}}\right)} V_{h,t} \]

Each head selects its own blocks. The tail block may be partial when seq_len is not a multiple of block_size, and its mean-pooled key must average only the positions that exist. If num_selected is at least num_blocks every block is kept and the attention becomes dense. Selection must be deterministic: when two blocks have equal scores, the block with the smaller index is selected. All tensors are float32.

Query-aware block selection (block_size = 4, num_selected = 2) K cache block 0 block 1 block 2 block 3 tail partial mean key Q · mean 0.4 2.1 -0.7 0.2 1.5 selected skip read skip skip read Q·K / √d Q·K one softmax over both blocks the softmax denominator covers only the selected positions, so scores of skipped blocks never enter the normalization; every head picks its own blocks

Implementation Requirements

Example

With num_heads = 2, seq_len = 4, head_dim = 2, block_size = 2, num_selected = 1:

\(Q\) (2×2): \[ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \] \(K_0 = K_1\) (4×2, identical for both heads): \[ \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \qquad V_0 = V_1\text{ (4}\times\text{2):} \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ 7 & 8 \end{bmatrix} \]

Output (2×2): \[ \begin{bmatrix} 2 & 3 \\ 6 & 7 \end{bmatrix} \]

The pooled keys are [1, 0] for block 0 (positions 0–1) and [0, 1] for block 1 (positions 2–3). Head 0 scores them [1, 0] and keeps block 0, so it attends to positions 0 and 1 with equal weights and returns ([1, 2] + [3, 4]) / 2 = [2, 3]. Head 1 scores them [0, 1] and keeps block 1, returning ([5, 6] + [7, 8]) / 2 = [6, 7].

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.