Why are Sensitive Functions Hard for Transformers?
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Hahn & Rofin (2024) report that fitted PARITY solutions become much sharper as input length grows than fitted solutions for FIRST and MAJORITY.
“Hahn & Rofin (2024) report that fitted PARITY solutions become much sharper as input length grows than fitted solutions for FIRST and MAJORITY”
From Exact-Solution Volume and Length Generalization in Transformers (2026) · cites this paper as Hahn & Rofin (2024)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 38
- Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. 2023. Generalization on the unseen, logic rea- soning and degree curriculum. In International Con- ference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31-60. PMLR.
- Maksym Andriushchenko, Francesco Croce, Maximil- ian Müller, Matthias Hein, and Nicolas Flammarion. 2023. A modern look at the relationship between sharpness and generalization. In International Con- ference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 840-902. PMLR.
- Dana Angluin, David Chiang, and Andy Yang. 2023. Masked hard-attention transformers and boolean rasp recognize exactly the star-free languages. arXiv preprint arXiv:2310.13897. · arXiv
- Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. 2022. Exploring length generalization in large language models. Advances in Neural Infor- mation Processing Systems, 35:38546-38556.
- Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. CoRR, abs/1607.06450. · arXiv
- David Chiang, Peter Cholak, and Anand Pillay. 2023. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Ma- chine Learning Research, pages 5544-5562. PMLR.
- Alex Damian, Eshaan Nichani, and Jason D. Lee. 2023. Self-stabilization: The implicit bias of gradient de- scent at the edge of stability. In The Eleventh Inter- national Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. Open- Review.net.
- Ronald De Wolf. 2008. A brief introduction to fourier analysis on the boolean cube. Theory of Computing, pages 1-20.
- Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. 2022. Inductive biases and vari- able creation in self-attention mechanisms. In In- ternational Conference on Machine Learning, pages 5793-5831. PMLR.
- Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2023. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Thirty-seventh Conference on Neural Information Processing Systems.
- Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. 2020. Sharpness-aware min- imization for efficiently improving generalization. arXiv preprint arXiv:2010.01412. · arXiv
- Sara Fridovich-Keil, Raphael Gontijo Lopes, and Re- becca Roelofs. 2022. Spectral bias in practice: The role of function frequency in generalization. In Ad- vances in Neural Information Processing Systems, volume 35, pages 7368-7382.
- Michael Hahn. 2020. Theoretical limitations of self- attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171.
- Michael Hahn, Dan Jurafsky, and Richard Futrell. 2021. Sensitivity as a complexity measure for se- quence classification tasks. Transactions of the As- sociation for Computational Linguistics, 9:891-908. · DOI
- Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810.
- Yiding Jiang, Behnam Neyshabur*, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. 2020. Fantastic generalization measures and where to find them. In International Conference on Learning Representa- tions.
- J. Kahn, G. Kalai, and N. Linial. 1988. The influence of variables on boolean functions. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 68-80.
- Simran Kaur, Jeremy Cohen, and Zachary Chase Lip- ton. 2023. On the maximum hessian eigenvalue and generalization. In Proceedings on, pages 51-65.
- PMLR.
- Shengqiao Li. 2010. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics & Statistics, 4(1):66-70.
- Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Pa- pailiopoulos, and Samet Oymak. 2023. Transform- ers as algorithms: Generalization and stability in in- context learning. In Proceedings of the 40th Inter- national Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19565-19594.
- PMLR.
- Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Kr- ishnamurthy, and Cyril Zhang. 2023. Transformers learn shortcuts to automata. In The Eleventh Inter- national Conference on Learning Representations.
- William Merrill and Ashish Sabharwal. 2023a. The expressive power of transformers with chain of thought. In NeurIPS 2023 Workshop on Mathemat- ics of Modern Machine Learning.
- William Merrill and Ashish Sabharwal. 2023b. A logic for expressing log-precision transformers. In Thirty- seventh Conference on Neural Information Process- ing Systems.
- William Merrill and Ashish Sabharwal. 2023c. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545.
- William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022. Saturated transformers are constant- depth threshold circuits. Trans. Assoc. Comput. Lin- guistics, 10:843-856.
- Ryan O'Donnell. 2014. Analysis of Boolean Func- tions. Cambridge University Press.
- Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Te- jani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. Pytorch: An imperative style, high-performance deep learn- ing library. In Advances in Neural Information Pro- cessing Systems, volume 32.
- Nasim Rahaman, Aristide Baratin, Devansh Arpit, Fe- lix Draxler, Min Lin, Fred Hamprecht, Yoshua Ben- gio, and Aaron Courville. 2019. On the spectral bias of neural networks. In Proceedings of the 36th In- ternational Conference on Machine Learning, vol- ume 97 of Proceedings of Machine Learning Re- search, pages 5301-5310. PMLR.
- Lena Strobl. 2023. Average-hard attention transform- ers are constant-depth uniform threshold circuits. CoRR, abs/2308.03212. · DOI
- Lena Strobl, William Merrill, Gail Weiss, David Chi- ang, and Dana Angluin. 2023. Transformers as rec- ognizers of formal languages: A survey on expres- sivity. CoRR, abs/2311.00208. · DOI
- Sho Takase, Shun Kiyono, Sosuke Kobayashi, and Jun Suzuki. 2022. On layer normalizations and resid- ual connections in transformers. arXiv preprint arXiv:2206.00330. · arXiv
- Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in neural information pro- cessing systems, pages 5998-6008.
- Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In International Con- ference on Machine Learning, pages 11080-11090.
- PMLR.
- Kaiyue Wen, Tengyu Ma, and Zhiyuan Li. 2022. How does sharpness-aware minimization minimize sharp- ness? CoRR, abs/2211.05729. · DOI
- Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. 2023. What algorithms can transformers learn? a study in length generalization. arXiv preprint arXiv:2310.16028. · arXiv
Cited by
Sorted by citations
Iformer: Irregular Spatial–Spectral Transformer for Hyperspectral Image Classification
Ahmad, M. I., & Mazzara, M. (2026) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2026.3710374 · Cited by 4 · see citing works
Spectral Sparsity: A Unifying Framework for Scalable Model Interpretability Using Codes
Kang, J., Tsui, D., Erginbas, Y. E., Butler, L., Aghazadeh, A., & Ramchandran, K. (2025) · IEEE BITS the Information Theory Magazine · doi:10.1109/mbits.2026.3692444 · Cited by 1 · see citing works
Exact-Solution Volume and Length Generalization in Transformers
Zhu, Y. J., & Chiang, D. (2026) · arXiv · doi:10.48550/arxiv.2610.07676
“Hahn & Rofin (2024) report that fitted P ARITY solutions become much sharper as input length grows than fitted solutions for F IRST and M AJORITY (whether there are more 1 ’s than 0 ’s).”
Extracting Moore Machines from Transformers Using Queries and Counterexamples
Adriaensen, R., & Maene, J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-91398-3_31 · Cited by 1 · see citing works
Geometric generality of Transformer-based Gröbner basis computation
Kambe, Y., Maeda, Y., & Vaccon, T. (2026) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/835/16758
Sar, A., Roy, S., Gupta, K., Kaushish, A., Choudhury, T., & Kumar, A. (2025) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata66926.2025.11402353
You can’t be neutral on a moving train
Heinz, J. N., & Rawski, J. (2026) · Behavioral and Brain Sciences · doi:10.1017/s0140525x26104798
- Authors
- Hahn, M., & Rofin, M.
- Affiliations
- Saarland University (DE)
- ORCID
- Hahn, Michael
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- Pages
- 14973-15008
- ISSN
- 0736-587X (ISSN-L)
- arXiv
- 2402.09963
- OpenAlex
- W4402671165
- Cited by
- 6
- References
- 0
- Citations by year
- 2026: 3 · 2025: 3
- FWCI
- 1.77
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Proceedings of the conference - Association for Computational Linguistics. Meeting (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Keywords
- transformer models, input sensitivity, loss landscape, parity function, formal languages, inductive bias, expressiveness, length generalization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
