Google

In contrast to standard self-attention, sparse attention assumes that only some entries within the attention weight vector $$\begin{bmatrix} \alpha_{i,0} & \dots & \alpha_{i,i} \end{bmatrix}$$ are non-zero. The remaining entries are simply ignored in the computation. This is formalized by defining a set $$G \subseteq \{0, \dots, i\}$$, which represents the specific indices of these non-zero entries. Consequently, any subsequent output calculations for position $$i$$ will only utilize the indices present in the set $$G$$.

Sparse Attention Weights Assumption

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

Based on the provided scenario, what is the effective weight applied to the value vector `v_5` when calculating the final output for position 8, and why?

Evaluating Vector Contributions in an Optimized Attention Mechanism

An optimized attention mechanism is calculating the output for a token at position `i=5`. The set of indices designated to contribute to this calculation is `G = {1, 2, 4}`. Explain why the value vector for the token at position `j=3`, denoted as `v_3`, is not included in the final weighted sum.

Selective Computation in Optimized Attention

In sparse attention, the set $$G$$ denotes the specific subset of indices for which the attention weights are non-zero and will be computed. For a given token at position $$i$$ in a causal model, this set is a subset of all preceding positions, formally expressed as $$G \subseteq \{0, \dots, i\}$$. This set effectively defines the sparsity pattern by identifying which key-value pairs the current query will attend to.

Index Set of Non-Zero Attention Weights ($$G$$)

A causal model is calculating the output for the token at position `i=3`. The model's attention mechanism is optimized to only consider a subset of previous positions. The set of contributing indices is `G = {0, 2}`. The attention weights for these indices are `α_3,0 = 0.6` and `α_3,2 = 0.4`. The value vectors for the relevant positions are: `v_0 = [1, 0]`, `v_1 = [2, 2]`, and `v_2 = [0, 3]`. Based on this information, what is the final output vector for position 3?

Learn Before

Related