Overcoming a Theoretical Limitation of Self-Attention
Open accessAbstract
Although transformers are remarkably effective for many tasks, there are some surprisingly easy-looking regular languages that they struggle with.Hahn shows that for languages where acceptance depends on a single input symbol, a transformer's classification decisions become less and less confident (that is, with crossentropy approaching 1 bit per string) as input strings get longer and longer.We examine this limitation using two languages: PAR-ITY, the language of bit strings with an odd number of 1s, and FIRST, the language of bit strings starting with a 1.We demonstrate three ways of overcoming the limitation suggested by Hahn's lemma.First, we settle an open question by constructing a transformer that recognizes PARITY with perfect accuracy, and similarly for FIRST.Second, we use layer normalization to bring the cross-entropy of both models arbitrarily close to zero.Third, when transformers need to focus on a single position, as for FIRST, we find that they can fail to generalize to longer strings; we offer a simple remedy to this problem that also improves length generalization in machine translation.
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?
Models trained from scratch show little to no length generalization on parity.
“and parity (Bhattamishra et al., 2020;Chiang & Cholak, 2022;Ruoss et al., 2023;Delétang et al., 2023)”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Chiang & Cholak, 2022
Section 5.1 reports that standard transformers trained from scratch were unable to learn PARITY. It does not report a parity-specific test of generalization from shorter to longer strings; the length-generalization results in that section concern FIRST. Thus the paper supports poor learning on parity, but not the claim’s specific length-generalization finding. (LLM, conf=0.85)
Experimental — accuracy not yet measuredLLMs can occasionally exhibit unpredictable reasoning hallucinations spanning both long-range and short-range dependencies, which potentially arise from the limitations of soft attention, where attention becomes diluted across positions as sequence length increases.
“Moreover, recent research has exposed that LLMs can occasionally exhibit unpredictable reasoning hallucinations spanning both long-range and short-range dependencies, which potentially arise from the limitations of soft attention [52, 111], where attention becomes diluted across positions as sequence length increases.”
From A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions (2025) · cites this paper as [52]
Split into 2 atoms — 0 confirmed, 2 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measuredThe log n attention scaling was proposed by Chiang & Cholak (2022) and Nakanishi (2025), used in practice in Qwen (Bai et al., 2023), and given additional theoretical justification by Chen et al. (2026).
“The log n factor was proposed by Chiang & Cholak (2022) and Nakanishi (2025) and has been used in practice in Qwen (Bai et al., 2023).Chen et al. (2026) provide additional theoretical justification for this choice.”
From Exact-Solution Volume and Length Generalization in Transformers (2026) · cites this paper as Chiang & Cholak (2022)
Chiang & Cholak (2022) construct exact transformers for FIRST and PARITY, but report that standard training fails on PARITY, and that FIRST does not necessarily extrapolate to longer inputs without log n-scaling.
“Chiang & Cholak (2022) construct exact transformers for FIRST (whether the first symbol is a 1) and PARITY (whether the number of 1's is odd), but report that standard training fails on PARITY, and that FIRST does not necessarily extrapolate to longer inputs without log n-scaling.”
From Exact-Solution Volume and Length Generalization in Transformers (2026) · cites this paper as Chiang & Cholak (2022)
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
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017) · arXiv · doi:10.48550/arxiv.1706.03762 · Cited by 120,404 · see citing works
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946 · see citing works
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 48,293 · see citing works
PyTorch: An Imperative Style, High-Performance Deep Learning Library
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019) · arXiv · doi:10.48550/arxiv.1912.01703 · Cited by 31,473 · see citing works
BLEU: a method for automatic evaluation of machine translation
Papineni, K., Roukos, S., Ward, T., & Zhu, W.-J. (2001) · Proceedings of the 40th Annual Meeting on Association for Computational Linguistics - ACL '02 · doi:10.3115/1073083.1073135 · Cited by 21,344 · see citing works
Learning Internal Representations by Error Propagation
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1985) · doi:10.21236/ada164453 · Cited by 16,501 · see citing works
Layer NormalizationPreprint
Ba, J., Kiros, J., & Hinton, G. E. (2016) · arXiv.org · doi:10.48550/arxiv.1607.06450 · Cited by 13,745 · see citing works
Convolutional Sequence to Sequence Learning
Gehring, J., Auli, M., Grangier, D., Yarats, D., & Dauphin, Y. N. (2017) · arXiv · doi:10.48550/arxiv.1705.03122 · Cited by 2,850 · see citing works
Learning Deep Transformer Models for Machine Translation
Wang, Q., Li, B., Xiao, T., Zhu, J., Li, C., Wong, D. F., & Chao, L. S. (2019) · Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/p19-1176 · Cited by 673 · see citing works
Theoretical Limitations of Self-Attention in Neural Sequence Models
Hahn, M. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00306 · Cited by 165 · see citing works
Are Transformers universal approximators of sequence-to-sequence functions?Preprint
Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., & Kumar, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.10077 · Cited by 149 · see citing works
On the Ability and Limitations of Transformers to Recognize Formal Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.576 · Cited by 48 · see citing works
On the Computational Power of Transformers and Its Implications in Sequence Modeling
Bhattamishra, S., Patel, A., & Goyal, N. (2020) · Conference on Computational Natural Language Learning · doi:10.18653/v1/2020.conll-1.37 · Cited by 39 · see citing works
Pérez, J., Barceló, P., & Marinković, J. (2021) · Journal of Machine Learning Research · Cited by 20 · see citing works
Weiss, G., Goldberg, Y., & Yahav, E. (2021) · arXiv · doi:10.48550/arxiv.2106.06981 · Cited by 18 · see citing works
Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent
Merrill, W., Ramanujan, V., Goldberg, Y., Schwartz, R., & Smith, N. A. (2021) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2021.emnlp-main.133 · Cited by 17 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- Toan Q. Nguyen and Julian Salazar. 2019. Transform- ers without tears: Improving the normalization of self-attention. In Proc. International Workshop on Spoken Language Translation. · DOI
Cited by
Sorted by citations
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2025) · ACM Transactions on Information Systems · doi:10.1145/3703155 · Cited by 2,142 · see citing works
TransNeXt: Robust Foveal Visual Perception for Vision Transformers
Shi, D. (2024) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52733.2024.01683 · Cited by 452 · see citing works
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2023) · arXiv · doi:10.48550/arxiv.2311.05232 · Cited by 2,516 · see citing works
Hallucination is Inevitable: An Innate Limitation of Large Language Models
Xu, Z., Jain, S., & Kankanhalli, M. (2024) · arXiv · doi:10.48550/arxiv.2401.11817 · Cited by 180 · see citing works
“Attention mechanism, a key component of transformer-based LLMs, can also contribute to hallucination [36], possibly because attention across tokens is diluted as the sequence length grows [10, 22].”
BackgroundA taxonomy and review of generalization research in NLP
Hupkes, D., Giulianelli, M., Dankers, V., Artetxe, M., Elazar, Y., Pimentel, T., Christodoulopoulos, C., Lasri, K., Saphra, N., Sinclair, A., et al. (2023) · Nature Machine Intelligence · doi:10.1038/s42256-023-00729-y · Cited by 121 · see citing works
MemFlow: Optical Flow Estimation and Prediction with Memory
Dong, Q., & Fu, Y. (2024) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52733.2024.01804 · Cited by 50 · see citing works
Deng, Y., Tu, Z., Yao, J., Zhang, M., Zhang, T., & Zheng, X. (2025) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2025.3569086 · Cited by 43 · see citing works
What Formal Languages Can Transformers Express? A Survey
Strobl, L., Merrill, W., Weiss, G., Chiang, D., & Angluin, D. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00663 · Cited by 31 · see citing works
Self-citationRandomized Positional Encodings Boost Length Generalization of Transformers
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J. (2023) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2023.acl-short.161 · Cited by 24 · see citing works
Liu, F., Shen, S.-Y., Fu, Z.-W., Wang, H.-Y., Zhou, A.-M., & Qi, J.-Y. (2022) · Entropy · doi:10.3390/e24071010 · Cited by 21 · see citing works
Modality-collaborative Transformer with Hybrid Feature Reconstruction for Robust Emotion Recognition
Chen, C., & Zhang, P. (2024) · ACM Transactions on Multimedia Computing Communications and Applications · doi:10.1145/3640343 · Cited by 18 · see citing works
Automatic Speech Disfluency Detection Using wav2vec2.0 for Different Languages with Variable Lengths
Liu, J., Wumaier, A., Wei, D., & Guo, S. (2023) · Applied Sciences · doi:10.3390/app13137579 · Cited by 17 · see citing works
Tracking With Saliency Region Transformer
Liu, T., Li, J., Wu, J. X., Zhang, L., Chang, J., Wan, J., & Lian, L. (2023) · IEEE Transactions on Image Processing · doi:10.1109/tip.2023.3340604 · Cited by 12 · see citing works
Towards A Unified Conformer Structure: from ASR to ASV Task
Liao, D., Jiang, T., Wang, F., Li, L., & Hong, Q. (2023) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49357.2023.10095433 · Cited by 11 · see citing works
What Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10 · see citing works
“…which functions are possible to represent by a Transformer 10 , but this representation is not always “simple” enough to be learnable, and not always uniform (Hahn, 2020; Merrill et al., 2022; Chiang & Cholak, 2022; Pérez et al., 2021; Bhattamishra et al., 2020; Ebrahimi et al., 2020).”
BackgroundSimplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
Bhattamishra, S., Patel, A., Kanade, V., & Blunsom, P. (2023) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2023.acl-long.317 · Cited by 10 · see citing works
Beyond Intentions: A Critical Survey of Misalignment in LLMs
Qu, Y., Huang, S., Long, L., Nie, P., & Yao, Y. (2025) · Computers, materials & continua/Computers, materials & continua (Print) · doi:10.32604/cmc.2025.067750 · Cited by 9 · see citing works
Liu, Z., Kou, J., Zhang, W., Gu, C., Fang, X., Huang, Z., Hao, Y., Li, H., Lu, X., Yin, A., et al. (2024) · International Conference on Universal Village (UV) · doi:10.1109/uv63228.2024.11189137 · Cited by 9 · see citing works
Why are Sensitive Functions Hard for Transformers?
Hahn, M., & Rofin, M. (2024) · arXiv · doi:10.48550/arxiv.2402.09963 · Cited by 6
Simulating Hard Attention Using Soft Attention
Yang, A., Strobl, L., Chiang, D., & Angluin, D. (2026) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl.a.597 · Cited by 4 · see citing works
Self-citationStrobl, L., Angluin, D., Chiang, D., Rawski, J., & Sabharwal, A. (2025) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00736 · Cited by 4 · see citing works
Self-citationTrustworthiness of large language models: hallucinations
Brunello, N. (2026) · Elsevier eBooks · doi:10.1016/b978-0-443-33592-1.00007-3 · Cited by 3 · see citing works
Irie, K., Csordás, R., & Schmidhuber, J. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.588 · Cited by 3 · see citing works
Evaluating Transformer’s Ability to Learn Mildly Context-Sensitive Languages
Wang, S., & Steinert‐Threlkeld, S. (2023) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2023.blackboxnlp-1.21 · Cited by 3 · see citing works
Kou, J., Lu, X., Yin, A., Zhang, W., Fang, X., Li, Y., Pan, T., Zhang, L., Cheng, G., Yuan, H., et al. (2024) · International Conference on Universal Village (UV) · doi:10.1109/uv63228.2024.11189154 · Cited by 2 · see citing works
Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
Svete, A., Dayan, B., Cotterell, R., Vieira, T., & Eisner, J. M. (2022) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2022.emnlp-main.567 · Cited by 2 · see citing works
Pushdown Layers: Encoding Recursive Structure in Transformer Language Models
Murty, S., Sharma, P., Andreas, J., & Manning, C. D. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.195 · Cited by 2 · see citing works
Chi, T.-C., Fan, T.-H., Rudnicky, A. I., & Ramadge, P. J. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.397 · Cited by 1 · see citing works
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
Detecting and Correcting Hallucinations in LLMs via Substantive Uncertainty and Iterative Validation
Chen, Z., Cheng, Y., & Gao, Y. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-3352-7_14 · Cited by 1 · see citing works
Diffusion-based Kriging Model with Graph-enhanced Attention
Zhang, M., Yang, G., Zhu, Z., Jin, G., Wang, M., & Bai, X. (2026) · International World Wide Web Conference (WWW) · doi:10.1145/3774904.3792104 · Cited by 1 · see citing works
An efficient deep attention framework for multi-rotor UAVs fault diagnosis
Mowla, M. N., Asadi, D., Khaneghaei, M., & Sohel, F. (2026) · Applied Mathematics and Computation · doi:10.1016/j.amc.2026.130170 · Cited by 1 · see citing works
Language models need inductive biases to count inductively
Chang, Y., & Bisk, Y. (2024) · arXiv · doi:10.48550/arxiv.2405.20131
“This mechanism closely resembles the construction in Chiang & Cholak (2022) for recognizing PARITY, which crucially depends on 1) a beginning-of-sequence (BOS) symbol and 2) uniform attention over tokens that are either the BOS or identical to self.”
BackgroundMethodInfluentialExact-Solution Volume and Length Generalization in Transformers
Zhu, Y. J., & Chiang, D. (2026) · arXiv · doi:10.48550/arxiv.2610.07676
“The upper bound of zero, meaning that P ARITY is not solvable by the class of transformers considered here, is consistent with previous theoretical results (Kozachinskiy et al., 2026b) and experiments (Chiang & Cholak, 2022; Hahn & Rofin, 2024).”
Self-citationAddressing the Length Bias Challenge in Document-Level Neural Machine Translation
Zhuocheng, Z., Gu, S., Zhang, M., & Yang, F. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.773
Unraveling Feature Extraction Mechanisms in Neural Networks
Sun, X., Li, J., & Lü, W. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.650
Mitros, J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-04558-4_14
Efficient Occupancy Prediction Guided Point Cloud Geometry Compression
Wang, X., Zhang, Y., Liu, T., Liu, X., Xu, K., Wan, J., Guo, Y., & Wang, H. (2025) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2025.3624369
The Role of Logic and Automata in Understanding Transformers
Lin, A. W., & Barceló, P. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-09524-4_2
Three Tiers of Computation in Transformers and in Brain Architectures
Graham, E., & Granger, R. (2026) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3844612
HEFT: Hierarchical Enhanced Fusion Transformer for RGB-D Salient Object Detection
Tan, H., Wen, S., Zhu, L., Huang, H., Zhang, L., Li, J., & Hu, T. (2025) · International Conference on Advanced Robotics and Mechatronics (ICARM) · doi:10.1109/icarm65671.2025.11293468
Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth
Yuan, M., Sun, W., Rezaeian, A. H., Singh, J., Ghoshal, S., Wang, Y., Ballesteros, M., & Benajiba, Y. (2026) · Conference of the European Chapter of the Association for Computational Linguistics · doi:10.18653/v1/2026.eacl-long.87
Circuit Complexity of Hierarchical Knowledge Tracing
Liu, N.-S., Baraniuk, R. G., & Sonkar, S. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-29760-0_8
Fu, S., & Wu, Z. (2026) · Food Reviews International · doi:10.1080/87559129.2026.2698084
RAGnRoll: Learning to Iteratively Retrieve and Generate Attributable Answer Snippets
Djeddal, H., Soulier, L., Pinel-Sauvagnat, K., Katrenko, S., Erbacher, P., & Tamine, L. (2026) · ACM Transactions on Information Systems · doi:10.1145/3831679
Vision transformer for reference-based super-resolution
Yakovenko, A., Denisov, A., Vatolin, D. S., & Kustarev, P. (2026) · Scientific and technical journal of information technologies mechanics and optics · doi:10.17586/2226-1494-2026-26-5-1065-1072
- Authors
- Chiang, D., & Cholak, P.
- Affiliations
- University of Notre Dame (US)
- Venue
- Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
- Published
- 2022
- Pages
- 7654-7664
- ISSN
- 0736-587X (ISSN-L)
- OpenAlex
- W4285206226
- Cited by
- 39
- References
- 16
- Citations by year
- 2026: 8 · 2025: 9 · 2024: 8 · 2023: 11 · 2022: 3
- FWCI
- 10.66
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- Locations
- Proceedings of the conference - Association for Computational Linguistics. Meeting (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Office of the Director of National Intelligence (FA8650-17-C-9116)
- Intelligence Advanced Research Projects Activity
- NIH Office of the Director
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Keywords
- self-attention, transformer models, regular languages, mother tongue, cross-entropy, length generalization, layer normalization, machine translation
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
