mlsanityData to 14 Oct 2026

Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot

arXiv 2406.06893 ↗First posted 11 Jun 2024stat.ML cs.IT cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

The transformer architecture has prevailed in various deep learning settings due to its exceptional capabilities to select and compose structural information. Motivated by these capabilities, Sanford et al. proposed the sparse token selection task, in which transformers excel while fully-connected networks (FCNs) fail in the worst case. Building upon that, we strengthen the FCN lower bound to an average-case setting and establish an algorithmic separation of transformers over FCNs. Specifically, a one-layer transformer trained with gradient descent provably learns the sparse token selection task and, surprisingly, exhibits strong out-of-distribution length generalization. We provide empirical simulations to justify our theoretical findings.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 44 of its 67 references that are in the map. First posted on arXiv 11 Jun 2024.

Builds on

44 of 67 references.

References · 44

  1. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  3. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  4. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,103
  5. 2022In-context Learning and Induction Headscited by 964
  6. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  7. 2023Progress measures for grokking via mechanistic interpretabilitycited by 839
  8. 2022A Survey on In-context Learningcited by 721
  9. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  10. 2018Universal Transformerscited by 647
  11. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  12. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
32 more
  1. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  2. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
  3. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 298
  4. 2022Transformers Learn Shortcuts to Automatacited by 268
  5. 2023Looped Transformers as Programmable Computerscited by 237
  6. 2019Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernelcited by 213
  7. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  8. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 170
  9. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 155
  10. 2022Transformer Language Models without Positional Encodings Still Learn Positional Informationcited by 150
  11. 2023Representational Strengths and Limitations of Transformerscited by 133
  12. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  13. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  14. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 117
  15. 2023In-Context Convergence of Transformerscited by 115
  16. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  17. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  18. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 86
  19. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  20. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  21. 2023Transformers as Support Vector Machinescited by 74
  22. 2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimalitycited by 74
  23. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 63
  24. 2023Positional Description Matters for Transformers Arithmeticcited by 56
  25. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  26. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  27. 2021On the Expressive Power of Self-Attention Matricescited by 47
  28. 2020The EOS Decision and Length Extrapolationcited by 46
  29. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 46
  30. 2019Location Attention for Extrapolation to Longer Sequencescited by 33
  31. 2023Trainable Transformer in Transformercited by 17
  32. 2020On the Ability and Limitations of Transformers to Recognize Formal Languagescited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 7; 2025: 10; 2026: 5.

22 papers.

Sort:

By area:

  1. 2025Training Dynamics of In-Context Learning in Linear Attentioncited by 46
  2. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 29
  3. 2024Attention layers provably solve single-location regressioncited by 17
  4. 2024On the Training Convergence of Transformers for In-Context Classification of Gaussian Mixturescited by 15
  5. 2025Gating is Weighting: Understanding Gated Linear Attention through In-context Learningcited by 12
  6. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  7. 2024Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selectioncited by 9
  8. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  9. 2024How Transformers Get Rich: Approximation and Dynamics Analysiscited by 8
  10. 2025The Role of Sparsity for Length Generalization in Transformerscited by 8
  11. 2025Quantitative Bounds for Length Generalization in Transformerscited by 8
  12. 2025Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspectivecited by 5
10 more
  1. 2025On the Robustness of Transformers against Context Hijacking for Linear Classificationcited by 4
  2. 2024Neural Networks Generalize on Low Complexity Datacited by 3
  3. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 3
  4. 2025Towards Understanding Transformers in Learning Random Walkscited by 2
  5. 2026Incremental Learning of Sparse Attention Patterns in Transformerscited by 2
  6. 2026Transformers Provably Learn to Internalize Chain-of-Thoughtcited by 2
  7. 2025Attention with Trained Embeddings Provably Selects Important Tokenscited by 1
  8. 2026Provably Learning Attention with Queriescited by 1
  9. 2026Theory on Attention Dynamics for Out-of-Distribution In-Context Learningcited by 0
  10. 2026Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learningcited by 0