mlsanityData to 14 Oct 2026

Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions

arXiv 2211.12316 ↗First posted 22 Nov 2022cs.LG cs.CLcited by 70

Not on the map. Why?

Abstract (arXiv)

Despite the widespread success of Transformers on NLP tasks, recent works have found that they struggle to model several formal languages when compared to recurrent models. This raises the question of why Transformers perform well in practice and whether they have any properties that enable them to generalize better than recurrent models. In this work, we conduct an extensive empirical study on Boolean functions to demonstrate the following: (i) Random Transformers are relatively more biased towards functions of low sensitivity. (ii) When trained on Boolean functions, both Transformers and LSTMs prioritize learning functions of low sensitivity, with Transformers ultimately converging to functions of lower sensitivity. (iii) On sparse Boolean functions which have low sensitivity, we find that Transformers generalize near perfectly even in the presence of noisy labels whereas LSTMs overfit and achieve poor generalization accuracy. Overall, our results provide strong quantifiable evidence that suggests differences in the inductive biases of Transformers and recurrent models which may help explain Transformer's effective generalization performance despite relatively limited expressiveness.

Key facts. Cited by 70 papers in the map (data through 14 Oct 2026). Builds on 42 of its 78 references that are in the map. First posted on arXiv 22 Nov 2022.

Builds on

42 of 78 references.

References · 42

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  6. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,372
  7. 2018On the Spectral Bias of Neural Networkscited by 1,341
  8. 2017A Closer Look at Memorization in Deep Networkscited by 942
  9. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 629
  10. 2017Deep Neural Networks as Gaussian Processescited by 622
  11. 2020Bayesian Deep Learning and a Probabilistic Perspective of Generalizationcited by 480
  12. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
30 more
  1. 2022Neural Networks and the Chomsky Hierarchycited by 217
  2. 2022Exploring Length Generalization in Large Language Modelscited by 206
  3. 2019SGD on Neural Networks Learns Functions of Increasing Complexitycited by 204
  4. 2018Sensitivity and Generalization in Neural Networks: an Empirical Studycited by 189
  5. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  6. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 183
  7. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  8. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  9. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  10. 2021Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networkscited by 117
  11. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  12. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  13. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  14. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 88
  15. 2020A Formal Hierarchy of RNN Architecturescited by 62
  16. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  17. 2020Is SGD a Bayesian sampler? Well, almostcited by 50
  18. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  19. 2019On the Computational Power of RNNscited by 35
  20. 2021Memorisation versus Generalisation in Pre-trained Language Modelscited by 32
  21. 2021Sensitivity as a Complexity Measure for Sequence Classification Taskscited by 28
  22. 2019Neural networks are a priori biased towards Boolean functions with low entropycited by 24
  23. 2020On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languagescited by 22
  24. 2020TraDE: Transformers for Density Estimationcited by 18
  25. 2018On Evaluating the Generalization of LSTM Models in Formal Languagescited by 17
  26. 2018Evaluating the Ability of LSTMs to Learn Context-Free Grammarscited by 16
  27. 2019Learning Curves for Deep Neural Networks: A Gaussian Field Theory Perspectivecited by 11
  28. 2020Choppy: Cut Transformer For Ranked List Truncationcited by 11
  29. 2022What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environmentcited by 9
  30. 2018A Comparative Study of Rule Extraction for Recurrent Neural Networkscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 11; 2024: 24; 2025: 18; 2026: 17.

70 papers.

Sort:

By area:

  1. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  2. 2023Looped Transformers are Better at Learning Learning Algorithmscited by 149
  3. 2023Representational Strengths and Limitations of Transformerscited by 133
  4. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  5. 2023In-Context Learning through the Bayesian Prismcited by 83
  6. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 80
  7. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  8. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 63
  9. 2024Neural Redshift: Random Networks are not Random Functionscited by 43
  10. 2024IsoBench: Benchmarking Multimodal Foundation Models on Isomorphic Representationscited by 38
  11. 2024Why Do You Grok? A Theoretical Analysis of Grokking Modular Additioncited by 36
  12. 2023How are Prompts Different in Terms of Sensitivity?cited by 35
38 more
  1. 2024Out-of-Domain Generalization in Dynamical Systems Reconstructioncited by 33
  2. 2023Deep neural networks have an inbuilt Occam's razorcited by 28
  3. 2024Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modelingcited by 25
  4. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  5. 2024Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformerscited by 24
  6. 2024A distributional simplicity bias in the learning dynamics of transformerscited by 24
  7. 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
  8. 2025How Muon's Spectral Design Benefits Generalization: A Study on Imbalanced Datacited by 19
  9. 2024Progressive distillation induces an implicit curriculumcited by 15
  10. 2025Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architecturescited by 15
  11. 2024Transformers Learn Low Sensitivity Functions: Investigations and Implicationscited by 14
  12. 2024Towards Understanding Inductive Bias in Transformers: A View From Infinitycited by 13
  13. 2025Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wildcited by 13
  14. 2025Representation Potentials of Foundation Models for Multimodal Alignment: A Surveycited by 11
  15. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  16. 2025Binned Spectral Power Loss for Improved Prediction of Chaotic Systemscited by 10
  17. 2026The Expressive Limits of Diagonal SSMs for State-Trackingcited by 9
  18. 2024The Mystery of the Pathological Path-star Task for Language Modelscited by 8
  19. 2025When Do Neural Networks Learn World Models?cited by 8
  20. 2023MLRegTest: A Benchmark for the Machine Learning of Regular Languagescited by 7
  21. 2024IM-Context: In-Context Learning for Imbalanced Regression Taskscited by 7
  22. 2024ALTA: Compiler-Based Analysis of Transformerscited by 7
  23. 2025Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformerscited by 6
  24. 2024Investigating Recurrent Transformers with Dynamic Haltcited by 5
  25. 2025Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspectivecited by 5
  26. 2026Long-Tail Knowledge in Large Language Models: Taxonomy, Mechanisms, Interventions and Implicationscited by 5
  27. 2025To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Modelscited by 4
  28. 2024A rationale from frequency perspective for grokking in training neural networkcited by 3
  29. 2024Early learning of the optimal constant solution in neural networks and humanscited by 3
  30. 2024Exploiting the equivalence between quantum neural networks and perceptronscited by 3
  31. 2024Neural Networks Generalize on Low Complexity Datacited by 3
  32. 2025Transformers Provably Learn Sparse XOR with Polylogarithmic Parameterscited by 3
  33. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  34. 2025Review of Hallucination Understanding in Large Language and Vision Modelscited by 2
  35. 2025Adam or Gauss-Newton? A Comparative Study In Terms of Basis Alignment and SGD Noisecited by 2
  36. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differentlycited by 2
  37. 2026How Far Ahead Do LLMs Plan? Uncovering the Latent Horizon in Chain-of-Thought Reasoningcited by 2
  38. 2026Solomonoff inductioncited by 2

50 most cited of 70 All 70 (JSON)