# Attention layers provably solve single-location regression

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 67 references that are in the map.
- First posted on arXiv 2 Oct 2024.

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

- [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 Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [Inference-Time Intervention: Eliciting Truthful Answers from a Language Model](https://mlsanity.com/paper/2306.03341/) (2023)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [Vision Transformers Need Registers](https://mlsanity.com/paper/2309.16588/) (2023)
- [Discovering Latent Knowledge in Language Models Without Supervision](https://mlsanity.com/paper/2212.03827/) (2022)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning](https://mlsanity.com/paper/2012.13255/) (2020)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Emergent Linear Representations in World Models of Self-Supervised Sequence Models](https://mlsanity.com/paper/2309.00941/) (2023)
- [Transformers learn to implement preconditioned gradient descent for in-context learning](https://mlsanity.com/paper/2306.00297/) (2023)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Exploiting Similarities among Languages for Machine Translation](https://mlsanity.com/paper/1309.4168/) (2013)
- [BERT Post-Training for Review Reading Comprehension and Aspect-based Sentiment Analysis](https://mlsanity.com/paper/1904.02232/) (2019)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [Adaptively Sparse Transformers](https://mlsanity.com/paper/1909.00015/) (2019)
- [End-to-End Attention-based Large Vocabulary Speech Recognition](https://mlsanity.com/paper/1508.04395/) (2015)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Learned Token Pruning for Transformers](https://mlsanity.com/paper/2107.00910/) (2021)
- [Utilizing BERT for Aspect-Based Sentiment Analysis via Constructing Auxiliary Sentence](https://mlsanity.com/paper/1903.09588/) (2019)
- [Infinite attention: NNGP and NTK for deep attention networks](https://mlsanity.com/paper/2006.10540/) (2020)

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

- [The emergence of sparse attention: impact of data distribution and benefits of repetition](https://mlsanity.com/paper/2505.17863/) (2025)
- [Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networks](https://mlsanity.com/paper/2506.02651/) (2025)
- [Statistical Advantage of Softmax Attention: Insights from Single-Location Regression](https://mlsanity.com/paper/2509.21936/) (2025)
- [Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters](https://mlsanity.com/paper/2502.07553/) (2025)
- [Attention-based clustering](https://mlsanity.com/paper/2505.13112/) (2025)
- [Bayes optimal learning of attention-indexed models](https://mlsanity.com/paper/2506.01582/) (2025)
- [Learning with Hidden Factorial Structure](https://mlsanity.com/paper/2411.01375/) (2024)
- [Incremental Learning of Sparse Attention Patterns in Transformers](https://mlsanity.com/paper/2602.19143/) (2026)
- [Specialization of softmax attention heads: insights from the high-dimensional single-location model](https://mlsanity.com/paper/2603.03993/) (2026)
- [Attention with Trained Embeddings Provably Selects Important Tokens](https://mlsanity.com/paper/2505.17282/) (2025)
- [Provably Learning Attention with Queries](https://mlsanity.com/paper/2601.16873/) (2026)
- [Ordinary Least Squares as an Attention Mechanism](https://mlsanity.com/paper/2504.09663/) (2025)
- [Minimax Rates for Learning Pairwise Interactions in Attention-Style Models](https://mlsanity.com/paper/2510.11789/) (2025)
- [Gaussian Match-and-Copy: A Minimalist Benchmark for Studying Transformer Induction](https://mlsanity.com/paper/2602.07562/) (2026)
- [A Comparative Analysis of Attention versus State-Space Models for In-Context Learning](https://mlsanity.com/paper/2609.32341/) (2026)
- [Attention Function as an Intrinsic Inductive Bias: How Models' Behavior Diverges in Novel Contexts](https://mlsanity.com/paper/2609.39188/) (2026)
- [Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learning](https://mlsanity.com/paper/2610.20337/) (2026)

## Abstract (arXiv)

Attention-based models, such as Transformer, excel across various tasks but lack a comprehensive theoretical understanding, especially regarding token-wise sparsity and internal linear representations. To address this gap, we introduce the single-location regression task, where only one token in a sequence determines the output, and its position is a latent random variable, retrievable via a linear projection of the input. To solve this task, we propose a dedicated predictor, which turns out to be a simplified version of a non-linear self-attention layer. We study its theoretical properties, by showing its asymptotic Bayes optimality and analyzing its training dynamics. In particular, despite the non-convex nature of the problem, the predictor effectively learns the underlying structure. This work highlights the capacity of attention mechanisms to handle sparse token information and internal linear structures.