mlsanityData to 7 Oct 2026

Why are Sensitive Functions Hard for Transformers?

arXiv 2402.09963 ↗First posted 15 Feb 2024cs.LGcited by 74

Not on the map. Why?

Abstract (arXiv)

Empirical studies have identified a range of learnability biases and limitations of transformers, such as a persistent difficulty in learning to compute simple formal languages such as PARITY, and a bias towards low-degree functions. However, theoretical understanding remains limited, with existing expressiveness theory either overpredicting or underpredicting realistic learning abilities. We prove that, under the transformer architecture, the loss landscape is constrained by the input-space sensitivity: Transformers whose output is sensitive to many parts of the input string inhabit isolated points in parameter space, leading to a low-sensitivity bias in generalization. We show theoretically and empirically that this theory unifies a broad array of empirical observations about the learning abilities and biases of transformers, such as their generalization bias towards low sensitivity and low degree, and difficulty in length generalization for PARITY. This shows that understanding transformers' inductive biases requires studying not just their in-principle expressivity, but also their loss landscape.

Key facts. Cited by 74 papers in the map (data through 7 Oct 2026). Builds on 31 of its 48 references that are in the map. First posted on arXiv 15 Feb 2024.

Builds on

31 of 48 references.

References · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Layer Normalizationcited by 5,579
  4. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
  5. 2018On the Spectral Bias of Neural Networkscited by 1,321
  6. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  7. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  8. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  9. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  10. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  11. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  12. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
19 more
  1. 2021Thinking Like Transformerscited by 182
  2. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 151
  3. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  4. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  5. 2023Representational Strengths and Limitations of Transformerscited by 132
  6. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  7. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
  8. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  9. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  10. 2023A Modern Look at the Relationship between Sharpness and Generalizationcited by 91
  11. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  12. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  13. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  14. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  15. 2022How Does Sharpness-Aware Minimization Minimize Sharpness?cited by 64
  16. 2022On the Maximum Hessian Eigenvalue and Generalizationcited by 57
  17. 2021Spectral Bias in Practice: The Role of Function Frequency in Generalizationcited by 36
  18. 2021Sensitivity as a Complexity Measure for Sequence Classification Taskscited by 28
  19. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 11; 2025: 31; 2026: 32.

74 papers.

Sort:

By area:

  1. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 186
  2. 2025How Linguistics Learned to Stop Worrying and Love the Language Modelscited by 50
  3. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  4. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  5. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  6. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  7. 2025ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMscited by 16
  8. 2024Transformers Learn Low Sensitivity Functions: Investigations and Implicationscited by 13
  9. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  10. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 10
  11. 2025Lost in Transmission: When and Why LLMs Fail to Reason Globallycited by 9
  12. 2026The Expressive Limits of Diagonal SSMs for State-Trackingcited by 9
38 more
  1. 2024The Mystery of the Pathological Path-star Task for Language Modelscited by 8
  2. 2025The Role of Sparsity for Length Generalization in Transformerscited by 8
  3. 2024On Inductive Biases That Enable Generalization of Diffusion Transformerscited by 7
  4. 2025The Counting Power of Transformerscited by 7
  5. 2025Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithmscited by 7
  6. 2025Benefits and Limitations of Communication in Multi-Agent Reasoningcited by 7
  7. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  8. 2025Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematicscited by 5
  9. 2025The Transformer Cookbookcited by 5
  10. 2026When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformerscited by 5
  11. 2025You Do Not Fully Utilize Transformer's Representation Capacitycited by 4
  12. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  13. 2026Parity, Sensitivity, and Transformerscited by 4
  14. 2024Training the Untrainable: Introducing Inductive Bias via Representational Alignmentcited by 3
  15. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  16. 2025Geometric Generality of Transformer-Based Gr"obner Basis Computationcited by 3
  17. 2026Context-Free Recognition with Transformerscited by 3
  18. 2026On the Spatiotemporal Dynamics of Generalization in Neural Networkscited by 3
  19. 2026Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidthcited by 3
  20. 2024Extracting Moore Machines from Transformers using Queries and Counterexamplescited by 2
  21. 2025Emergent Stack Representations in Modeling Counter Languages Using Transformerscited by 2
  22. 2025Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Modelscited by 2
  23. 2025Is In-Context Learning Learning?cited by 2
  24. 2026Unlearnable phases of mattercited by 2
  25. 2026Can Vision-Language Models Solve the Shell Game?cited by 2
  26. 2026Can Transformers Really Do It All? On the Compatibility of Inductive Biases Across Taskscited by 2
  27. 2024Reorganizing attention-space geometry with expressive attentioncited by 1
  28. 2025Provably Overwhelming Transformer Models with Designed Inputscited by 1
  29. 2025Discovering Learning-Friendly Generation Orders for Sequential Computationcited by 1
  30. 2025Rethinking Memorization Measures and their Implications in Large Language Modelscited by 1
  31. 2025Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMscited by 1
  32. 2025Hierarchical Resolution Transformers: A Wavelet-Inspired Architecture for Multi-Scale Language Understandingcited by 1
  33. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differentlycited by 1
  34. 2026How Far Ahead Do LLMs Plan? Uncovering the Latent Horizon in Chain-of-Thought Reasoningcited by 1
  35. 2026On the Ability of Transformers to Verify Planscited by 1
  36. 2026Fine-tuning vs. In-context Learning in Large Language Models: A Formal Language Learning Perspectivecited by 1
  37. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  38. 2026The two clocks and the innovation window: When and how generative models learn rulescited by 1

50 most cited of 74 All 74 (JSON)