Problems
Loading...
Step 6 of 7
QSA Token Selection
Hard

Qwen Sparse Attention turns the indexer's block scores into one set of key positions per query and runs ordinary attention only over that set. Each query keeps its best-scoring complete blocks, expands them into their tokens, and always adds the tokens of the block it is currently inside.

With block size rr and token budget KK, the number of blocks kept per query and the selected blocks are

KB=Kr,Bi=TopK⁡KB({Iib}b)K_B=\frac{K}{r},\qquad \mathcal B_i=\operatorname{TopK}_{K_B}\left(\{I_{ib}\}_{b}\right)

and the token set of query ii is

Si=⋃b∈Bi{br,…,br+r−1} ∪ {r⌊i+1r⌋,…,i}\mathcal S_i=\bigcup_{b\in\mathcal B_i}\{br,\dots,br+r-1\}\ \cup\ \left\{r\left\lfloor\tfrac{i+1}{r}\right\rfloor,\dots,i\right\}

Every head hh then attends over the same set,

oih=∑j∈Sisoftmax⁡j∈Si(⟨qih,kjh⟩d)vjho_i^h=\sum_{j\in\mathcal S_i}\operatorname{softmax}_{j\in\mathcal S_i}\left(\frac{\langle q_i^h,k_j^h\rangle}{\sqrt{d}}\right)v_j^h

Here IibI_{ib} is the score of block bb for query ii, minus infinity when the block is not complete at the query, qihq_i^h, kjhk_j^h and vjhv_j^h are the query, key and value vectors of head hh at positions ii and jj with positions already encoded, and dd is the head width. The second part of the union is the tail of the current block, which is empty when i+1i+1 is a multiple of rr.

Only blocks with a finite score can be selected, so a query with fewer finite blocks than KBK_B keeps all of them. Among equal scores the earlier block wins. In the test inputs, minus infinity is written as the string -inf.

Return a tuple of the attention output, shaped (sequence length, heads, head width) with the dtype of the queries, and the boolean selection mask of shape (sequence length, sequence length) whose entry (i,j)(i,j) is true exactly when j∈Sij\in\mathcal S_i.

Loading visualization...

Examples

Input: block_scores = [["-inf","-inf"],[0.5,"-inf"],[1,"-inf"],[0,0]], block_size = 2, token_budget = 2, queries = [[[1,0]],[[0,1]],[[1,1]],[[1,-1]]], keys = [[[1,0]],[[0,1]],[[1,1]],[[-1,0]]], values = [[[1,0]],[[0,1]],[[2,2]],[[-1,1]]]

Output: (tensor([[[1.0000, 0.0000]], [[0.3302, 0.6698]], [[1.2552, 1.2552]], [[0.8044, 0.1956]]], dtype=torch.float64), tensor([[True, False, False, False], [True, True, False, False], [True, True, True, False], [True, True, False, False]]))

Explanation: The budget of 2 tokens keeps one block. Query 0 has no complete block and reads only its own tail. Query 2 keeps block 0 and its tail token 2. Query 3 closes block 1, so its tail is empty, and blocks 0 and 1 tie at 0, so the earlier block wins and query 3 reads tokens 0 and 1 only.

Input: block scores shape (8, 4) with many zero ties, block_size = 2, token_budget = 4, queries, keys and values shape (8, 2, 2)

Output: (tensor of shape (8, 2, 2), tensor of shape (8, 8) with row sizes [1, 2, 3, 4, 5, 4, 5, 4])

Input: block scores shape (10, 3), block_size = 3, token_budget = 3, queries, keys and values shape (10, 1, 2)

Output: (tensor of shape (10, 1, 2), tensor of shape (10, 10) with row sizes [1, 2, 3, 4, 5, 3, 4, 5, 3, 4])

Hint 1

torch.sort(scores, dim=1, descending=True, stable=True)\texttt{torch.sort(scores, dim=1, descending=True, stable=True)} keeps the earlier block first among equal scores.

Hint 2

torch.isfinite\texttt{torch.isfinite} separates blocks that may be selected from blocks that are still incomplete.

Hint 3

Fill the logits outside the mask with minus infinity before torch.softmax\texttt{torch.softmax} so each row normalizes over its own set.

Requirements

  • Return a tuple of two PyTorch tensors, the attention output first and the selection mask second.
  • The attention output has shape sequence length by heads by head width, with the dtype and device of the queries.
  • The selection mask is a boolean tensor of shape sequence length by sequence length, shared by every head.
  • Select at most the budget divided by the block size blocks per query, never select a block whose score is minus infinity, and prefer the earlier block among equal scores.
  • Leave every input tensor unchanged.

Constraints

  • The block scores have shape (T,⌊T/r⌋)(T,\lfloor T/r\rfloor) with 1≤T≤121\le T\le 12, are finite and nonnegative exactly for blocks with br+r−1≤ibr+r-1\le i, and are minus infinity otherwise.
  • The block size rr is a positive integer and may exceed TT, in which case the score matrix has zero columns.
  • The token budget KK is a positive multiple of rr, so expanding the selected blocks never exceeds the budget.
  • Queries, keys and values share the shape (T,H,d)(T,H,d) with H≥1H\ge 1 and d≥1d\ge 1.
  • All floating-point tensors share one dtype, float32 or float64, and may be noncontiguous.
  • In the Run panel, type minus infinity as the quoted string "-inf" inside the block scores.