# Minimax Rates for Learning Pairwise Interactions in Attention-Style Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 40 of its 64 references that are in the map.
- First posted on arXiv 13 Oct 2025.

## Builds on (most cited first, 30 of 40)

- [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)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Massive Activations in Large Language Models](https://mlsanity.com/paper/2402.17762/) (2024)
- [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)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [Infinite attention: NNGP and NTK for deep attention networks](https://mlsanity.com/paper/2006.10540/) (2020)
- [A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity](https://mlsanity.com/paper/2302.06015/) (2023)
- [Attention Score is not All You Need for Token Importance Indicator in KV Cache Reduction: Value Also Matters](https://mlsanity.com/paper/2406.12335/) (2024)
- [Theory, Analysis, and Best Practices for Sigmoid Self-Attention](https://mlsanity.com/paper/2409.04431/) (2024)
- [Active-Dormant Attention Heads: Mechanistically Demystifying Extreme-Token Phenomena in LLMs](https://mlsanity.com/paper/2410.13835/) (2024)
- [Asymptotic theory of in-context learning by linear attention](https://mlsanity.com/paper/2405.11751/) (2024)
- [On the Role of Attention in Prompt-tuning](https://mlsanity.com/paper/2306.03435/) (2023)
- [Bridging the Divide: Reconsidering Softmax and Linear Attention](https://mlsanity.com/paper/2412.06590/) (2024)
- [Nonparametric inference of interaction laws in systems of agents from trajectory data](https://mlsanity.com/paper/1812.06003/) (2018)
- [Sparse Attention with Linear Units](https://mlsanity.com/paper/2104.07012/) (2021)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [Emergence of meta-stable clustering in mean-field transformer models](https://mlsanity.com/paper/2410.23228/) (2024)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [SimA: Simple Softmax-free Attention for Vision Transformers](https://mlsanity.com/paper/2206.08898/) (2022)
- [Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems](https://mlsanity.com/paper/2109.15142/) (2021)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [Learning interaction kernels in heterogeneous systems of agents from multiple trajectories](https://mlsanity.com/paper/1910.04832/) (2019)

## Abstract (arXiv)

We study the convergence rate of learning pairwise interactions in single-layer attention-style models, where tokens interact through a weight matrix and a nonlinear activation function. We prove that the minimax rate is M^-frac2β2β+1, where M is the sample size and β is the H"older smoothness of the activation function. Importantly, this rate is independent of the embedding dimension d, the number of tokens N, and the rank r of the weight matrix, provided that rd ≤ (M/log M)^frac12β+1. These results highlight a fundamental statistical efficiency of attention-style models, even when the weight matrix and activation are not separately identifiable, and provide a theoretical understanding of attention mechanisms and guidance on training.