Problems
Loading...
Step 5 of 7
QSA Block Indexer
Hard

Qwen Sparse Attention decides which earlier tokens each query will read by first scoring compressed key blocks with a small indexer. The indexer is multi-query attention with HH query heads and one key head shared by every head. Keys are averaged over non-overlapping blocks of rr tokens before any positional encoding, so each block carries a single key placed at its start position, while every query keeps its own token position.

For token ii with hidden state xix_i and indexer head hh,

q^ih=RMSNorm⁡(WQhxi;γq),ki=WKxi\hat q_i^h=\operatorname{RMSNorm}\left(W_Q^hx_i;\gamma_q\right),\qquad k_i=W_Kx_i k^b=RMSNorm⁡(1r∑t=pbpb+r−1kt;γk),pb=br,0≤b<⌊T/r⌋\hat k_b=\operatorname{RMSNorm}\left(\frac{1}{r}\sum_{t=p_b}^{p_b+r-1}k_t;\gamma_k\right),\qquad p_b=br,\qquad 0\le b<\left\lfloor T/r\right\rfloor qih=PRoPE⁡(q^ih,i),kˉb=PRoPE⁡(k^b,pb)q_i^h=\operatorname{PRoPE}\left(\hat q_i^h,i\right),\qquad \bar k_b=\operatorname{PRoPE}\left(\hat k_b,p_b\right) Iib={∑h=1HReLU⁡(⟨qih,kˉb⟩)pb+r−1≤i−∞otherwiseI_{ib}=\begin{cases}\sum_{h=1}^{H}\operatorname{ReLU}\left(\langle q_i^h,\bar k_b\rangle\right) & p_b+r-1\le i\\ -\infty & \text{otherwise}\end{cases}

Here TT is the sequence length, xi∈Rdmodelx_i\in\mathbb{R}^{d_{\text{model}}} is row ii of the hidden states, WQh∈Rdh×dmodelW_Q^h\in\mathbb{R}^{d_h\times d_{\text{model}}} is the query projection of head hh, WK∈Rdh×dmodelW_K\in\mathbb{R}^{d_h\times d_{\text{model}}} is the shared key projection, γq\gamma_q and γk\gamma_k are the query and key norm weights of length dhd_h, and pbp_b is the position of the first token in block bb. A trailing group of fewer than rr tokens is not a block.

Every norm is the zero-centered form RMSNorm⁡(v;γ)=v/mean⁡(v2)+10−6⊙(1+γ)\operatorname{RMSNorm}(v;\gamma)=v/\sqrt{\operatorname{mean}(v^2)+10^{-6}}\odot(1+\gamma). PRoPE⁡(v,p)\operatorname{PRoPE}(v,p) rotates the leading rotary-dimension features of vv at position pp in the rotate-half layout with frequencies θ−2j/drot\theta^{-2j/d_{\text{rot}}} for the given base θ\theta, and leaves the remaining features unchanged. The starter code supplies both operations as complete helpers.

Return the score matrix II as a tensor of shape (T,⌊T/r⌋)(T,\lfloor T/r\rfloor) with the dtype of the hidden states, holding minus infinity wherever a block is not yet complete at the query.

Loading visualization...

Examples

Input: hidden_states = [[1,0],[0,1],[1,1],[-1,0.5]], query_projections = [[[1,0],[0,1]]], key_projection = [[0.5,1],[1,-0.5]], query_norm_weight = [0,0], key_norm_weight = [0,0], block_size = 2, rotary_dim = 2, rope_base = 10000

Output: tensor([[-inf, -inf], [0.0000, -inf], [0.0000, -inf], [1.2005, 0.0000]], dtype=torch.float64)

Explanation: Query 0 sits inside block 0, so both blocks are minus infinity. Block 0 becomes visible at query 1, where its rotated dot product is negative and ReLU clips it to 0. Block 1 holds tokens 2 and 3, so it appears only at query 3, which scores 1.2005 for block 0 and 0 for block 1.

Input: hidden states shape (5, 3), query projections shape (2, 4, 3), key projection shape (4, 3), zero norm weights, block_size = 2, rotary_dim = 2, rope_base = 10000

Output: tensor([[-inf, -inf], [3.2535, -inf], [0.0000, -inf], [0.0000, 0.0000], [1.4158, 2.4498]], dtype=torch.float64)

Input: hidden states shape (6, 3), query projections shape (2, 4, 3), key projection shape (4, 3), nonzero norm weights, block_size = 3, rotary_dim = 4, rope_base = 100

Output: tensor([[-inf, -inf], [-inf, -inf], [0.0000, -inf], [2.7959, -inf], [1.9751, -inf], [1.2661, 0.5275]], dtype=torch.float64)

Hint 1

Pool the first num_blocks * block_size\texttt{num\_blocks * block\_size} key rows with .reshape\texttt{.reshape} followed by .mean(dim=1)\texttt{.mean(dim=1)}.

Hint 2

The pooled keys take the positions torch.arange(num_blocks) * block_size\texttt{torch.arange(num\_blocks) * block\_size} in the rotary helper.

Hint 3

Compare each block's last position with every query position by broadcasting, then write minus infinity with masked_fill\texttt{masked\_fill}.

Requirements

  • Return one PyTorch tensor of shape sequence length by number of complete blocks, with the dtype and device of the hidden states.
  • Hold minus infinity exactly where the last token of a block comes after the query, and a finite score of zero or more everywhere else.
  • Keep the supplied normalization and rotary helpers unchanged.
  • Leave every input tensor unchanged.

Constraints

  • The hidden states have shape (T,dmodel)(T,d_{\text{model}}) with 1≤T≤121\le T\le 12.
  • The query projections have shape (H,dh,dmodel)(H,d_h,d_{\text{model}}) with H≥1H\ge 1, and the key projection has shape (dh,dmodel)(d_h,d_{\text{model}}).
  • Both norm weights have length dhd_h, and dhd_h is even.
  • The block size is a positive integer and may exceed TT, in which case there are no complete blocks and the result has zero columns.
  • The rotary dimension is an even integer between 00 and dhd_h, and the RoPE base is positive.
  • All tensors share one dtype, float32 or float64, hold finite values, and may be noncontiguous.