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

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

## 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 (most cited first, 30 of 42)

- [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)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Bayesian Deep Learning and a Probabilistic Perspective of Generalization](https://mlsanity.com/paper/2002.08791/) (2020)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [SGD on Neural Networks Learns Functions of Increasing Complexity](https://mlsanity.com/paper/1905.11604/) (2019)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks](https://mlsanity.com/paper/2106.04537/) (2021)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Is SGD a Bayesian sampler? Well, almost](https://mlsanity.com/paper/2006.15191/) (2020)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)

## Built on by (most cited first, 30 of 70)

- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Looped Transformers are Better at Learning Learning Algorithms](https://mlsanity.com/paper/2311.12424/) (2023)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [In-Context Learning through the Bayesian Prism](https://mlsanity.com/paper/2306.04891/) (2023)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions](https://mlsanity.com/paper/2310.03016/) (2023)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [IsoBench: Benchmarking Multimodal Foundation Models on Isomorphic Representations](https://mlsanity.com/paper/2404.01266/) (2024)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [How are Prompts Different in Terms of Sensitivity?](https://mlsanity.com/paper/2311.07230/) (2023)
- [Out-of-Domain Generalization in Dynamical Systems Reconstruction](https://mlsanity.com/paper/2402.18377/) (2024)
- [Deep neural networks have an inbuilt Occam's razor](https://mlsanity.com/paper/2304.06670/) (2023)
- [Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling](https://mlsanity.com/paper/2402.00522/) (2024)
- [Language Models Need Inductive Biases to Count Inductively](https://mlsanity.com/paper/2405.20131/) (2024)
- [Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers](https://mlsanity.com/paper/2404.16367/) (2024)
- [A distributional simplicity bias in the learning dynamics of transformers](https://mlsanity.com/paper/2410.19637/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [How Muon's Spectral Design Benefits Generalization: A Study on Imbalanced Data](https://mlsanity.com/paper/2510.22980/) (2025)
- [Progressive distillation induces an implicit curriculum](https://mlsanity.com/paper/2410.05464/) (2024)
- [Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architectures](https://mlsanity.com/paper/2512.20607/) (2025)
- [Transformers Learn Low Sensitivity Functions: Investigations and Implications](https://mlsanity.com/paper/2403.06925/) (2024)
- [Towards Understanding Inductive Bias in Transformers: A View From Infinity](https://mlsanity.com/paper/2402.05173/) (2024)
- [Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wild](https://mlsanity.com/paper/2503.10065/) (2025)
- [Representation Potentials of Foundation Models for Multimodal Alignment: A Survey](https://mlsanity.com/paper/2510.05184/) (2025)
- [On the Optimal Memorization Capacity of Transformers](https://mlsanity.com/paper/2409.17677/) (2024)
- [Binned Spectral Power Loss for Improved Prediction of Chaotic Systems](https://mlsanity.com/paper/2502.00472/) (2025)
- [The Expressive Limits of Diagonal SSMs for State-Tracking](https://mlsanity.com/paper/2603.01959/) (2026)
- [The Mystery of the Pathological Path-star Task for Language Models](https://mlsanity.com/paper/2410.13779/) (2024)

## 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.