A nonfinal token has inverse-length influence under bounded soft attention

There are constants $B_k<\mathrm{\infty }$ such that $\mathrm{\parallel }{y}_j^{(k)}{\mathrm{\parallel }}_2\le B_k$ for every position $j$, input length $n$, and input pair. At layer zero this follows from $y_j^{(0)}=v_{x_j}+p_j$ and the bounded token and positional embeddings. If it holds at layer $k-1$, each value vector has norm at most $\mathrm{\parallel }{V}_{k,h}\mathrm{\parallel }{B}_{k-1}$ and each attention output is a convex combination of those values by [F1]; the fixed globally Lipschitz positionwise map is bounded on this resulting bounded set. Induction gives all $B_k$.

Consequently every dot-product score at every layer has absolute value at most some $A_k<\mathrm{\infty }$. For any row with $n$ keys, its softmax weight $a_j$ is at most $e^{2A_k}\mathrm{/}n$, since its numerator is at most $e^{A_k}$ and its denominator is at least $n{e}^{-A_k}$.

We prove by induction on $k$ that for constants $D_k,E_k$ independent of $n$, the changed position satisfies $\mathrm{\parallel }{y}_i^{(k)}-y_i^{\mathrm{\prime }(k)}{\mathrm{\parallel }}_2\le D_k$, while every $j\mathrm{\ne }i$ satisfies $\mathrm{\parallel }{y}_j^{(k)}-y_j^{\mathrm{\prime }(k)}{\mathrm{\parallel }}_2\le E_k\mathrm{/}n$. This holds at $k=0$ because only the bounded token embedding at $i$ changes. Assume it holds at $k-1$ and fix a query position $j\mathrm{\ne }i$ and one head. Its query changes by $O(1\mathrm{/}n)$. Its key at position $i$ can change by $O(1)$, while all other keys change by $O(1\mathrm{/}n)$, using the fixed linear matrices and the induction hypothesis. Hence its score-difference vector $\mathrm{\Delta }$ has $\mathrm{\mid }{\mathrm{\Delta }}_i\mathrm{\mid }\le K$ and $\mathrm{\mid }{\mathrm{\Delta }}_r\mathrm{\mid }\le K\mathrm{/}n$ for $r\mathrm{\ne }i$, for a constant $K$ independent of $n$.

Interpolate the two score vectors linearly. All interpolated scores remain in $[-A_k,A_k]$, so the distinguished key has softmax weight at most $e^{2A_k}\mathrm{/}n$ throughout by step 2.1. For softmax probabilities $a_r(t)$, differentiation gives $a_r^{\mathrm{\prime }}(t)=a_r(t)({\mathrm{\Delta }}_r-{\sum }_s{a}_s(t){\mathrm{\Delta }}_s)$; therefore ${\sum }_r\mathrm{\mid }{a}_r^{\mathrm{\prime }}(t)\mathrm{\mid }\le 2{\sum }_r{a}_r(t)\mathrm{\mid }{\mathrm{\Delta }}_r\mathrm{\mid }=O(1\mathrm{/}n)$, and integration yields $\mathrm{\parallel }a-a^{\mathrm{\prime }}{\mathrm{\parallel }}_1=O(1\mathrm{/}n)$.

The head values are uniformly bounded by step 1.1. Splitting the difference of the two weighted sums into (i) the change of values under the first attention row and (ii) the change of attention weights applied to the second value list gives $\mathrm{\parallel }{b}_{j,k,h}-b_{j,k,h}^{\mathrm{\prime }}{\mathrm{\parallel }}_2=O(1\mathrm{/}n)$: the changed value at $i$ has weight $O(1\mathrm{/}n)$, all other value changes are $O(1\mathrm{/}n)$, and the total weight change is $O(1\mathrm{/}n)$ by step 4.1. The positionwise map is Lipschitz, so $\mathrm{\parallel }{y}_j^{(k)}-y_j^{\mathrm{\prime }(k)}{\mathrm{\parallel }}_2=O(1\mathrm{/}n)$ for every $j\mathrm{\ne }i$. At $j=i$, boundedness from step 1.1 gives a constant difference. This proves the induction claim.

Since $i<n$, the induction bound gives $\mathrm{\parallel }{y}_n^{(L)}-y_n^{\mathrm{\prime }(L)}{\mathrm{\parallel }}_2\le E_L\mathrm{/}n$. For a logit perturbation $\mathrm{\Delta }$, the softmax derivative is $p_r({\mathrm{\Delta }}_r-{\sum }_s{p}_s{\mathrm{\Delta }}_s)$, whose ${\mathrm{\ell }}^1$ norm is at most $2\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_{\mathrm{\infty }}\le 2\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_2$; hence the prediction probabilities differ by at most a constant times $1\mathrm{/}n$. Taking $C=E_L$ completes the hidden-state bound and supplies the stated probability bound.