mlsanityData to 14 Oct 2026

Attention layers provably solve single-location regression

arXiv 2410.01537 ↗First posted 2 Oct 2024stat.ML cs.LGcited by 17

Not on the map. Why?

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.

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

51 of 67 references.

References · 51

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  4. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  5. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  6. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  7. 2016Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddingscited by 1,312
  8. 2023Inference-Time Intervention: Eliciting Truthful Answers from a Language Modelcited by 1,302
  9. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,026
  10. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  11. 2023Vision Transformers Need Registerscited by 871
  12. 2022Discovering Latent Knowledge in Language Models Without Supervisioncited by 767
38 more
  1. 2022Transformers learn in-context by gradient descentcited by 732
  2. 2018On Lazy Training in Differentiable Programmingcited by 675
  3. 2020Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuningcited by 671
  4. 2021A Survey of Transformerscited by 401
  5. 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 341
  6. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  7. 2023Emergent Linear Representations in World Models of Self-Supervised Sequence Modelscited by 319
  8. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 279
  9. 2022cosFormer: Rethinking Softmax in Attentioncited by 213
  10. 2013Exploiting Similarities among Languages for Machine Translationcited by 191
  11. 2019BERT Post-Training for Review Reading Comprehension and Aspect-based Sentiment Analysiscited by 176
  12. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  13. 2019Adaptively Sparse Transformerscited by 155
  14. 2015End-to-End Attention-based Large Vocabulary Speech Recognitioncited by 151
  15. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  16. 2021Learned Token Pruning for Transformerscited by 139
  17. 2019Utilizing BERT for Aspect-Based Sentiment Analysis via Constructing Auxiliary Sentencecited by 122
  18. 2020Infinite attention: NNGP and NTK for deep attention networkscited by 121
  19. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  20. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  21. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  22. 2021An Interpretability Illusion for BERTcited by 97
  23. 2022Vision Transformers provably learn spatial structurecited by 93
  24. 2021Sparse is Enough in Scaling Transformerscited by 86
  25. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 86
  26. 2022Formal Algorithms for Transformerscited by 72
  27. 2024Theory, Analysis, and Best Practices for Sigmoid Self-Attentioncited by 64
  28. 2023Learning time-scales in two-layers neural networkscited by 57
  29. 2023A Study on ReLU and Softmax in Transformercited by 53
  30. 2019Attentional Encoder Network for Targeted Sentiment Classificationcited by 48
  31. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  32. 2023Deep Transformers without Shortcuts: Modifying Self-attention for Faithful Signal Propagationcited by 45
  33. 2023Replacing softmax with ReLU in Vision Transformerscited by 44
  34. 2017A Regularized Framework for Sparse and Structured Neural Attentioncited by 38
  35. 2023Simplifying Transformer Blockscited by 37
  36. 2024Implicit Diffusion: Efficient Optimization through Stochastic Samplingcited by 24
  37. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 22
  38. 2023Leveraging the two timescale regime to demonstrate convergence of neural networkscited by 19

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 9; 2026: 7.

17 papers.

Sort:

  1. 2025The emergence of sparse attention: impact of data distribution and benefits of repetitioncited by 25
  2. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  3. 2025Statistical Advantage of Softmax Attention: Insights from Single-Location Regressioncited by 7
  4. 2025Transformers Provably Learn Sparse XOR with Polylogarithmic Parameterscited by 3
  5. 2025Attention-based clusteringcited by 3
  6. 2025Bayes optimal learning of attention-indexed modelscited by 3
  7. 2024Learning with Hidden Factorial Structurecited by 2
  8. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 2
  9. 2026Specialization of softmax attention heads: insights from the high-dimensional single-location modelcited by 2
  10. 2025Attention with Trained Embeddings Provably Selects Important Tokenscited by 1
  11. 2026Provably Learning Attention with Queriescited by 1
  12. 2025Ordinary Least Squares as an Attention Mechanismcited by 0
5 more
  1. 2025Minimax Rates for Learning Pairwise Interactions in Attention-Style Modelscited by 0
  2. 2026Gaussian Match-and-Copy: A Minimalist Benchmark for Studying Transformer Inductioncited by 0
  3. 2026A Comparative Analysis of Attention versus State-Space Models for In-Context Learningcited by 0
  4. 2026Attention Function as an Intrinsic Inductive Bias: How Models' Behavior Diverges in Novel Contextscited by 0
  5. 2026Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learningcited by 0