# Why are Sensitive Functions Hard for Transformers?

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

## Key facts

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

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [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)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [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)
- [A Modern Look at the Relationship between Sharpness and Generalization](https://mlsanity.com/paper/2302.07011/) (2023)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [How Does Sharpness-Aware Minimization Minimize Sharpness?](https://mlsanity.com/paper/2211.05729/) (2022)
- [On the Maximum Hessian Eigenvalue and Generalization](https://mlsanity.com/paper/2206.10654/) (2022)
- [Spectral Bias in Practice: The Role of Function Frequency in Generalization](https://mlsanity.com/paper/2110.02424/) (2021)
- [Sensitivity as a Complexity Measure for Sequence Classification Tasks](https://mlsanity.com/paper/2104.10343/) (2021)

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

- [Let's Think Dot by Dot: Hidden Computation in Transformer Language Models](https://mlsanity.com/paper/2404.15758/) (2024)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Transformers Learn Low Sensitivity Functions: Investigations and Implications](https://mlsanity.com/paper/2403.06925/) (2024)
- [How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias](https://mlsanity.com/paper/2505.00926/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [The Counting Power of Transformers](https://mlsanity.com/paper/2505.11199/) (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)
- [The Role of Sparsity for Length Generalization in Transformers](https://mlsanity.com/paper/2502.16792/) (2025)
- [On Inductive Biases That Enable Generalization of Diffusion Transformers](https://mlsanity.com/paper/2410.21273/) (2024)
- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [Benefits and Limitations of Communication in Multi-Agent Reasoning](https://mlsanity.com/paper/2510.13903/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [The Transformer Cookbook](https://mlsanity.com/paper/2510.00368/) (2025)
- [When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers](https://mlsanity.com/paper/2607.20594/) (2026)
- [Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics](https://mlsanity.com/paper/2503.06366/) (2025)
- [Parity, Sensitivity, and Transformers](https://mlsanity.com/paper/2602.05896/) (2026)
- [Training the Untrainable: Introducing Inductive Bias via Representational Alignment](https://mlsanity.com/paper/2410.20035/) (2024)
- [You Do Not Fully Utilize Transformer's Representation Capacity](https://mlsanity.com/paper/2502.09245/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Geometric Generality of Transformer-Based Gr"obner Basis Computation](https://mlsanity.com/paper/2504.12465/) (2025)
- [Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models](https://mlsanity.com/paper/2505.10606/) (2025)

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