# Token Sample Complexity of Attention

arXiv: https://arxiv.org/abs/2512.10656 · HTML: https://mlsanity.com/paper/2512.10656/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 11 Dec 2025.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [Datasets: A Community Library for Natural Language Processing](https://mlsanity.com/paper/2109.02846/) (2021)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [A mathematical perspective on Transformers](https://mlsanity.com/paper/2312.10794/) (2023)
- [The emergence of clusters in self-attention dynamics](https://mlsanity.com/paper/2305.05465/) (2023)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization](https://mlsanity.com/paper/2305.19420/) (2023)
- [In-Context Convergence of Transformers](https://mlsanity.com/paper/2310.05249/) (2023)
- [Understanding and Improving Transformer From a Multi-Particle Dynamic System Point of View](https://mlsanity.com/paper/1906.02762/) (2019)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [A Mathematical Theory of Attention](https://mlsanity.com/paper/2007.02876/) (2020)
- [Emergence of meta-stable clustering in mean-field transformer models](https://mlsanity.com/paper/2410.23228/) (2024)
- [Clustering in Causal Attention Masking](https://mlsanity.com/paper/2411.04990/) (2024)
- [A Unified Perspective on the Dynamics of Deep Transformers](https://mlsanity.com/paper/2501.18322/) (2025)
- [Quantitative Clustering in Mean-Field Transformer Models](https://mlsanity.com/paper/2504.14697/) (2025)
- [How do Transformers perform In-Context Autoregressive Learning?](https://mlsanity.com/paper/2402.05787/) (2024)
- [Stochastic Deep Networks](https://mlsanity.com/paper/1811.07429/) (2018)
- [Approximation capability of neural networks on spaces of probability measures and tree-structured domains](https://mlsanity.com/paper/1906.00764/) (2019)

## Built on by (most cited first, 3 of 3)

- [Softmax as Linear Attention in the Large-Prompt Regime: a Measure-based Perspective](https://mlsanity.com/paper/2512.11784/) (2025)
- [Any-Dimensional Learning by Sampling](https://mlsanity.com/paper/2607.07680/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

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)/√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β with β<tfrac12, and C'(R) depends polynomially on the size of the support of the distribution. The exponent β 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.