Token Sample Complexity of Attention

As context windows in large language models continue to expand, it is essential to characterize how attention behaves at extreme sequence lengths. We introduce token sample complexity: the rate at which attention computed on $n$ tokens converges to its infinite-token limit. We estimate finite-$n$ convergence bounds at two levels: pointwise uniform convergence of the attention map, and convergence of moments for the transformed token distribution. For compactly supported (and more generally sub-Gaussian) distributions, our first result shows that the attention map converges uniformly on a ball of radius $R$ at rate $C(R)/\sqrt{n}$, where $C(R)$ grows exponentially with $R$. For large $R$, this estimate loses practical value, and our second result addresses this issue by establishing convergence rates for the moments of the transformed distribution (the token output of the attention layer). In this case, the rate is $C'(R)/n^{\beta}$ with $\beta<\tfrac{1}{2}$, and $C'(R)$ depends polynomially on the size of the support of the distribution. The exponent $\beta$ depends on the attention geometry and the spectral properties of the token distribution. We also examine the regime in which the attention parameter tends to infinity and the softmax approaches a hardmax, and in this setting, we establish a logarithmic rate of convergence. Experiments on synthetic and real data support our predictions and show that the predicted slowdown is reflected in downstream accuracy.

Large language models can now process very long inputs, but it is not always clear how much useful information is gained by adding more and more tokens. This paper studies that question for attention, the mechanism that lets a Transformer decide which parts of an input to focus on. We introduce token sample complexity: a way to measure how quickly attention stabilizes as the number of input tokens grows. Our theory shows that this stabilization can be much slower than the standard statistical intuition would suggest. The rate depends not only on the model’s attention weights, but also on the geometry of the token representations, through a quantity we call the attention horizon. When this horizon is large, attention becomes more selective and more tokens may be needed before the model behaves like it would with the full context. We support these predictions with experiments on synthetic data, real text representations from Transformer models, and an end-to-end classification task. The results show that the same slowdown can be observed in logits, predictions, and accuracy. Overall, the paper gives a quantitative way to understand when longer contexts are likely to improve model behavior, and when the gains may become slow or limited.