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.
solve(Q, K, V, output, num_heads, seq_len, head_dim, block_size, num_selected).Q has shape (num_heads, head_dim): a single decode query per head.K and V have shape (num_heads, seq_len, head_dim).b of head h with the unscaled dot product Q[h] · mean(K[h, t] for t in block b), and keep the min(num_selected, num_blocks) highest-scoring blocks, breaking ties toward the smaller block index.1 / sqrt(head_dim).output buffer of shape (num_heads, head_dim).
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].
num_heads ≤ 64seq_len ≤ 8,192head_dim ≤ 128block_size ≤ 256num_selected; if num_selected ≥ num_blocks every block is selectedfloat32num_heads = 32, seq_len = 8,192, head_dim = 128, block_size = 64, num_selected = 32