← All problems
#112 Attention With Sinks Medium

Implement Attention with Sinks for a given set of matrices. This is the attention pattern used in StreamingLLM to enable long-context inference: each query attends to a small number of leading sink tokens plus a sliding window of the most recent tokens. Combining a fixed prefix (sinks) with a moving window keeps the KV cache bounded while preserving the anchor tokens that stabilize the softmax distribution.

Given query matrix Q, key matrix K, and value matrix V, each of shape M × d, compute for every query position i:

\( \text{score}_{i,j} = \frac{Q_i \cdot K_j}{\sqrt{d}} \)

The set of allowed key positions for query i is:

\( \mathcal{A}_i = \{\, j : j \le i \;\wedge\; (\, j < \text{num_sinks} \;\vee\; j \ge i - \text{window_size} + 1 \,) \,\} \)

Softmax is applied only over these allowed positions and the output is the weighted sum of the corresponding values:

\( \text{output}_i = \sum_{j \in \mathcal{A}_i} \operatorname{softmax}\!\left(\text{score}_{i,\mathcal{A}_i}\right)_j \cdot V_j \)

key position → query position 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 sink window masked num_sinks = 2, window_size = 3

Implementation Requirements

Example 1:

Input:
Q (4×4): \[ \begin{bmatrix} 1.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 1.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 1.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 1.0 \end{bmatrix} \] K (4×4): \[ \begin{bmatrix} 1.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 1.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 1.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 1.0 \end{bmatrix} \] V (4×4): \[ \begin{bmatrix} 1.0 & 2.0 & 3.0 & 4.0 \\ 5.0 & 6.0 & 7.0 & 8.0 \\ 9.0 & 10.0 & 11.0 & 12.0 \\ 13.0 & 14.0 & 15.0 & 16.0 \end{bmatrix} \] num_sinks: 1, window_size: 2

Output:
output (4×4): \[ \begin{bmatrix} 1.0000000 & 2.0000000 & 3.0000000 & 4.0000000 \\ 3.4898374 & 4.4898372 & 5.4898376 & 6.4898376 \\ 5.7111764 & 6.7111769 & 7.7111769 & 8.7111759 \\ 8.6149015 & 9.6149015 & 10.6149025 & 11.6149025 \end{bmatrix} \]

Query 3 attends to positions {0, 2, 3}: position 0 is a sink, positions 2 and 3 fall inside the causal window [i - window_size + 1, i] = [2, 3], and position 1 is neither a sink nor in the window, so it is masked out.

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.