Google

For language models employing sparse attention, the output for a query token $$\mathbf{q}_i$$ at position $$i$$ is calculated as a weighted sum of value vectors. This computation is restricted to a specific subset of indices, $$G \subseteq \{0, \dots, i\}$$, where the attention weights are considered non-zero. The formula for the sparse attention output is:

$$\mathrm{Att}_{\mathrm{sparse}}(\mathbf{q}_i, \mathbf{K}_{\le i}, \mathbf{V}_{\le i}) = \sum_{j \in G} \alpha'_{i,j} \mathbf{v}_j$$

Here, $$\mathbf{K}_{\le i} = \begin{bmatrix} \mathbf{k}_0 \\ \vdots \\ \mathbf{k}_{i} \end{bmatrix}$$ and $$\mathbf{V}_{\le i} = \begin{bmatrix} \mathbf{v}_0 \\ \vdots \\ \mathbf{v}_{i} \end{bmatrix}$$ represent the keys and values up to position $$i$$. The summation iterates only over the indices $$j$$ in the sparse set $$G$$, applying the non-zero sparse attention weights $$\alpha'_{i,j}$$ to their corresponding value vectors $$\mathbf{v}_j$$.

Sparse Attention Output Formula

In sparse attention, the attention weights are normalized exclusively over the subset of indices defined by the set $$G$$. This redistribution of probability mass means that the weights which would have been assigned to ignored tokens are now allocated among the tokens in set $$G$$. As a result, the sparse attention weights, $$\alpha'_{i,j}$$, for any token $$j \in G$$ are greater than their counterparts, $$\alpha_{i,j}$$, in a standard dense attention calculation: $$\alpha'_{i,j} > \alpha_{i,j}$$

Comparison of Sparse and Dense Attention Weights

A language model computes an output vector for a specific token by taking a weighted sum of value vectors from a predefined subset of previous token positions. The formula for this is: `Output = Σ_{j ∈ G} α'_{i,j} v_j`, where `G` is the set of included indices. If a new token position, `k`, is added to the set `G`, which term in the formula must be recomputed for all `j` in the newly expanded set, and why is this re-computation necessary for the formula to remain valid?

Analysis of Sparse Attention Formula Components

A language model is computing the output for a token at position `i=4`. The full set of available previous value vectors is `{v_0, v_1, v_2, v_3}`. Based on the provided sparse attention formula, identify which of these value vectors will be completely ignored in the calculation and explain your reasoning by referencing the components of the formula.

Analyzing the Impact of the Sparse Index Set

A language model is calculating an output vector using a sparse attention mechanism. The computation for the current token only considers a subset of previous tokens, identified by the index set G = {0, 2, 3}. Given the value vectors and corresponding attention weights below, what is the correct output vector? 

Value Vectors:
- v_0 = [2, 1]
- v_1 = [4, 5]
- v_2 = [6, 0]
- v_3 = [1, 3]

Attention Weights for the included set G:
- α'_0 = 0.5
- α'_2 = 0.2
- α'_3 = 0.3

Learn Before

Related