Overcoming a Theoretical Limitation of Self-Attention

David ChiangPeter Cholak

article2022ACL136 citations

Proves that standard transformers can recognize challenging regular languages like PARITY with perfect accuracy and shows that scaling attention logits by the logarithm of sequence length resolves severe length generalization failures in practice.

Listen

Modern natural language processing systems rely heavily on transformer architectures, yet recent theoretical analyses have highlighted fundamental limitations in how these models process information. In particular, prior work established that transformers experience rapidly decaying confidence when classifying sequences whose outcome depends on individual input positions, resulting in near-random uncertainty as input lengths grow. Understanding whether this represents a hard barrier to transformer capabilities is critical as artificial intelligence applications encounter increasingly long documents and data sequences.

The article evaluates these theoretical limits by examining whether transformer encoders can accurately recognize two formal languages—one tracking whether a binary string has an odd number of ones (PARITY) and another checking whether the string begins with a one (FIRST)—while also investigating practical methods to overcome confidence loss and length generalization failures.

The authors approach the problem through a combination of mathematical proofs, explicit model constructions, and empirical experiments. They design exact, hand-crafted transformer networks and implement them using standard deep learning frameworks. They test these constructions across sequences ranging up to 1,000 tokens, train models from scratch under various conditions, and validate their findings on a real-world, low-resource English-to-Vietnamese machine translation task.

The investigation yields four central findings. First, transformers can theoretically achieve 100% classification accuracy on both benchmark tasks across arbitrary lengths, disproving the notion that transformers are fundamentally incapable of recognizing such patterns. Second, while unnormalized models suffer from severe confidence degradation as sequences lengthen, incorporating exact layer normalization drives classification error metrics arbitrarily close to zero regardless of string length. Third, standard transformers trained on short sequences fail dramatically when generalizing to longer sequences—for instance, models trained on length-10 strings perform near random guessing on length-1,000 strings because attention becomes diluted across irrelevant tokens. Fourth, introducing a simple structural modification that scales attention calculations by the logarithm of sequence length completely resolves length generalization issues on the synthetic benchmark and provides a statistically significant improvement of 1.0 BLEU point when translating longer sentences in machine translation.

These findings demonstrate that expressivity, confidence, and learnability are distinct issues that must be addressed separately in model design. The practical takeaway is that transformer attention mechanisms naturally dilute focus over long sequences, creating operational risks when models encounter data longer than their training samples. The proposed logarithmic scaling directly counteracts this degradation with minimal computational overhead and zero parameter cost.

Organizations developing or deploying transformer-based systems should implement and evaluate logarithmic attention logit scaling, particularly in applications where production input lengths exceed training distributions. Further empirical testing across larger models and broader natural language benchmarks is recommended to measure broader performance impacts.

The primary limitation of the study is that its foundational proofs assume ideal conditions, such as exact normalization without numerical stability constants, and hand-crafted weights that standard optimization algorithms cannot readily discover from scratch for complex global patterns. Nevertheless, the empirical validation in machine translation provides strong confidence that the core diagnosis and recommended attention modification offer meaningful real-world benefits.

University of Notre Dame self-attention layer length generalization positional encodings

arXiv: 2202.12172

Paper: Attention Is All You Need, Ashish Vaswani et al. (2017). The source assumes the Transformer’s self-attention architecture, so this paper provides the foundational model whose limits it investigates.

Paper: Tighter Bounds on the Expressivity of Transformer Encoders, David Chiang et al. (2023). Building on results about specific language-recognition limits, this paper tightens the formal expressivity bounds for transformer encoders.
Paper: Randomized Positional Encodings Boost Length Generalization of Transformers, Anian Ruoss et al. (2023). Extending the source’s concern with generalizing to longer inputs, this work tests randomized positional encodings as a remedy across algorithmic tasks.
Paper: A Length-Extrapolatable Transformer, Yutao Sun et al. (2023). This work carries the source’s length-generalization theme into long-context modeling, proposing an architecture designed to improve as test inputs grow beyond training lengths.

Cover for Overcoming a Theoretical Limitation of Self-Attention

Abstract

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 cross-entropy approaching 1 bit per string) as input strings get longer and longer. We examine this limitation using two languages: PARITY, 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.

Keywords

self-attention layer length generalization positional encodings regular languages transformer encoder attention logits

1 Introduction
2 Background
2.1 Notation
2.2 Transformers
2.2.1 Input layer
2.2.2 Encoder layers
2.2.3 Output layer
3 Exact Solutions
3.1 FFNN for PARITY
3.2 Transformer for PARITY
3.3 Transformer for FIRST
3.4 Experiments
4 Layer Normalization
4.1 Removing centering
4.2 Reducing cross-entropy
4.3 Experiments
5 Learnability
5.1 Experiments: standard transformers
5.2 Flawed transformer for FIRST
5.3 Log-length scaled attention
5.4 Experiments: scaled attention
6 Related Work
7 Conclusion
Acknowledgements
References
A Correctness of PARITY Construction
B Scale-Invariance of PARITY and FIRST Constructions

Knowls

Knowl 1 — A two-layer transformer recognizes PARITY at every length
model/method
Let $w$ be a bit string of length $m$ , let $N=m+1$ be the number of encoder positions including the CLS token, and let $k$ be the number of $1$ s in $w$ . A transformer with two layers, two attention heads per layer, and hidden dimension $9$ recognizes PARITY exactly for arbitrary $m$ . Its input representation uses coordinates $1$ – $3$ for indicators of token $0$ , token $1$ , and CLS; coordinate $4$ is the position $i/N$ ; and coordinate $5$ is $\cos(\pi i)$ , for positions $i=0,\ldots,m$ .

In the first layer, one attention head has zero queries and keys, so it averages uniformly over all $N$ positions. Its values place $k/N$ and $1/N$ in coordinates $6$ and $7$ at every position; the other head contributes zero. The position-wise ReLU network then writes $\mathbb{I}[i=k]/N$ into coordinate $8$ . It can do this using the combination $\bigl(\operatorname{ReLU}(k-i+1)-2\operatorname{ReLU}(k-i)+\operatorname{ReLU}(k-i-1)\bigr)/N$ , which equals the required indicator for integer $i$ and $k$ .

In the second layer, two heads use opposite signs of coordinate $5$ as their keys, thereby favoring opposite position parities. They read coordinate $8$ with opposite value signs and combine their results in coordinate $9$ at CLS. The resulting output logit is positive exactly when $k$ is odd and negative when $k$ is even; the sigmoid classifier therefore recognizes PARITY with perfect accuracy at every length. The logit magnitude shrinks as $N$ grows, so perfect classification does not entail high confidence.
Knowl 2 — A transformer recognizes FIRST by selecting the first input position
model/method
For a bit string $w$ , FIRST accepts exactly when its first bit is $1$ . Use an input representation with indicators for token $0$ , token $1$ , and CLS, plus an indicator for whether the position is $i=1$ (the first input symbol, since CLS is at position $0$ ). A first-layer position-wise ReLU network creates an additional coordinate equal to $1$ only when both $i=1$ and $w_i=1$ ; the first attention layer itself contributes zero.

A second-layer attention head gives the first input position a logit advantage $c>0$ over all other positions and uses values that are zero away from that position. If $N$ is the number of positions including CLS, the CLS output logit for a nonempty string is
$s=\frac{e^c}{e^c+N-1}\left(\mathbb{I}[w_1=1]-\frac12\right).$
The output sigmoid is greater than $1/2$ exactly when $w_1=1$ , so this two-layer construction has perfect accuracy for arbitrary input lengths. Its logit approaches zero as the length grows, which makes its confidence deteriorate despite the correct decisions.
Knowl 3 — Layer normalization with zero epsilon can make cross-entropy arbitrarily small
theoretical result
Suppose a transformer with layer normalization parameter $\epsilon=0$ recognizes a language $\mathcal{L}$ , meaning that its output logit has the correct sign on every input. For every target cross-entropy $\eta>0$ , there is a transformer with layer normalization that still recognizes $\mathcal{L}$ and has cross-entropy at most $\eta$ on every input, independently of input length.

The construction appends a layer whose attention has zero values and whose feedforward network reduces the output representation to two coordinates containing the original logit $s$ and its negation, with all remaining coordinates zero. With $d$ activation coordinates, zero-epsilon layer normalization maps this vector to coordinates $\operatorname{sgn}(s)\sqrt{d/2}$ and $-\operatorname{sgn}(s)\sqrt{d/2}$ , with the other coordinates zero. Scaling the final classifier then makes the probability assigned to the correct class arbitrarily close to one. This result depends on $\epsilon=0$ : a positive epsilon makes layer normalization Lipschitz-continuous, so the argument does not remove the limitation associated with Hahn’s lemma.
Knowl 4 — Paired positive and negative coordinates preserve the exact constructions under layer normalization
model/method
The exact PARITY and FIRST constructions can be adapted to use layer normalization after residual connections by representing every activation $x$ as the concatenated vector $[x;-x]$ and making corresponding changes to the attention and feedforward weights. Each such vector has mean zero, so layer normalization does not change it by centering; it only applies a positive scale factor.

For these two constructions, that scaling does not change the output decision. Their feedforward networks have no bias terms and are homogeneous under positive scaling, while the constant in each attention query can absorb scaling of the attention inputs. Thus the paired-coordinate construction preserves the correct output signs while allowing layer normalization to be used.
Knowl 5 — Multiplying attention logits by log sequence length stabilizes FIRST and permits low cross-entropy
model/method
Let $N$ be the number of positions in the input to an attention layer, including CLS, and let $d$ be the attention dimension. The paper modifies scaled dot-product attention by multiplying every attention logit by $\log N$ :
$\operatorname{Att}(q,K,V)=V^{\mathsf T}\operatorname{softmax}\left(\frac{\log N}{\sqrt d}Kq\right),$
where $q$ is the query vector, $K$ contains the key vectors, and $V$ contains the value vectors. In a one-layer FIRST construction whose non-first positions also have nonzero values, this scaling makes the CLS logit positive exactly when the first input bit is $1$ , for every input length.

Moreover, for every $\eta>0$ , a transformer using this attention rule can recognize FIRST with cross-entropy at most $\eta$ , with or without layer normalization. In the construction without layer normalization, the absolute value of the FIRST logit is bounded below by $1/4$ and above by $1/2$ , independent of length; scaling the output classifier can therefore make the cross-entropy arbitrarily small. With layer normalization, the paired-coordinate modification preserves a length-independent positive lower bound on the logit magnitude, allowing the same output scaling.
Knowl 6 — Standard attention can fail to generalize FIRST from short to long strings
empirical result
Transformers trained on FIRST can have difficulty transferring from shorter training strings to longer test strings, even though the language is determined by one position. In the reported experiments, models trained from scratch on strings of lengths $10$ , $30$ , $100$ , or $300$ were tested on strings of length $1000$ . Standard attention did not yield perfect test accuracy; for training length $10$ , accuracy was hardly better than random guessing.

The paper’s explanation is that a learned model may retain nonzero values at positions other than the first. Their contributions can then compete with the first-position signal, whose attention weight is diluted as the sequence grows. In a simplified model, correctly selecting the first position requires an attention-logit advantage that grows with the sequence length. Figure 4 reports 20-run averages, with 100 training and 100 length-1000 test strings per epoch: scaling attention logits by $\log N$ enabled perfect test accuracy and cross-entropy for all four training-length settings.

Knowl 7 — Log-length attention improves long-sentence machine translation BLEU

data/table

In low-resource English-to-Vietnamese machine translation, the authors compared a baseline transformer with one whose attention logits were scaled by the logarithm of sequence length. They used the Witwicky implementation with its default settings, including layer normalization after residual connections with $\epsilon=10^{-5}$ , and evaluated with BLEU. When training and test sentence-length distributions matched, scaling made no significant difference. When training used sentences of at most 20 tokens and testing used sentences longer than 20 tokens, scaling improved BLEU by one point, a statistically significant gain ( $p<0.01$ ). Token counts below are reported as in the paper.

Knowl 8 — The reported training setup did not learn PARITY, and the exact solution was parameter-sensitive
empirical result
The authors report that their standard transformer training setup did not learn PARITY, consistent with earlier experimental findings; they also tried other settings without success. The reported setup used the same number of layers and heads and the same fixed positional encodings as the corresponding exact construction, $d_{\mathrm{model}}=16$ , feedforward hidden dimension $d_{\mathrm{FFNN}}=64$ , layer normalization with $\epsilon=10^{-5}$ after residual connections, PyTorch’s default initialization, and Adam with learning rate $3\times10^{-4}$ . They did not use dropout because it did not appear helpful.

A sensitivity test helps explain why the constructed solution may be hard to find by gradient descent. Starting from the PARITY construction with layer normalization and $\epsilon=0$ , they varied the value-network parameter responsible for computing $k/N$ , where $k$ is the number of ones and $N$ is the number of input positions including CLS. The correct value, $1$ , gives zero cross-entropy and perfect accuracy, but both metrics oscillate sharply near that value; even small perturbations make the solution difficult to recover.
Knowl 9 — Exact recognition does not prevent cross-entropy from approaching one bit
empirical result
The authors implemented the exact PARITY and FIRST constructions and verified perfect accuracy on strings with lengths sampled from $[1,1000]$ . Figure 2 evaluates cross-entropy on 1,000 random strings at each plotted length. Without layer normalization, cross-entropy for both languages quickly approaches the one-bit-per-string upper bound, even though the predicted class remains correct. With layer normalization and $\epsilon=10^{-5}$ , cross-entropy is initially better but still increases with length. With $\epsilon=0$ , it is independent of length and can be made as small as desired by the output scaling described in the theoretical construction.

Coverage note — No substantial contributed result is omitted; proof-only calculations and redundant zero-valued entries from the full parameter matrices are not reproduced.

References

1.Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. arXiv:1607.06450.
2.Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020a. On the ability and limitations of Transformers to recognize formal languages. In Proc. EMNLP, pages 7096–7116.
3.Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020b. On the computational power of Transformers and its implications in sequence modeling. In Proc. CoNLL, pages 455–475.
4.Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proc. NAACL HLT, pages 4171–4186.
5.Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. 2017. Convolutional sequence to sequence learning. In Proc. ICML, pages 1243–1252.
6.Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Trans. ACL, 8:156–171.
7.Andrej Karpathy. 2016. 3e-4 is the best learning rate for Adam, hands down. Twitter.
8.Diederik P. Kingma and Jimmy Lei Ba. 2015. Adam: A method for stochastic optimization. In Proc. ICLR.
9.William Merrill, Vivek Ramanujan, Yoav Goldberg, Roy Schwartz, and Noah A. Smith. 2021. Effects of parameter norm growth during transformer training: Inductive bias from gradient descent. In Proc. EMNLP, pages 1766–1781.
10.Toan Q. Nguyen and Julian Salazar. 2019. Transformers without tears: Improving the normalization of self-attention. In Proc. International Workshop on Spoken Language Translation.
11.Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proc. ACL, pages 311–318.
12.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 Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An imperative style, high-performance deep learning library. In Proc. NeurIPS.
13.Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021. Attention is Turing-complete. Journal of Machine Learning Research, 22(75):1–35.
14.D. E. Rumelhart, G. E. Hinton, and R. J.Williams. 1986. Learning Internal Representations by Error Propagation, pages 318–362. MIT Press, Cambridge, MA, USA.
15.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 Proc. NeurIPS, pages 5998–6008.
16.Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F. Wong, and Lidia S. Chao. 2019. Learning deep Transformer models for machine translation. In Proc. ACL, pages 1810–1822.
17.Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like Transformers. In Proc. ICML.
18.Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. 2020. Are Transformers universal approximators of sequence-to-sequence functions? In Proc. ICLR.

Citation

MLA

Chiang, D., and P. Cholak. “Overcoming a Theoretical Limitation of Self-Attention”. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2022, pp. 7654–64, https://doi.org/10.18653/v1/2022.acl-long.527.

APA

Chiang, D., & Cholak, P. (2022). Overcoming a Theoretical Limitation of Self-Attention. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 7654–7664. https://doi.org/10.18653/v1/2022.acl-long.527

Chicago

Chiang, D., and P. Cholak. 2022. “Overcoming a Theoretical Limitation of Self-Attention”. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 7654–64. https://doi.org/10.18653/v1/2022.acl-long.527.

Harvard

Chiang, D. and Cholak, P. (2022) “Overcoming a Theoretical Limitation of Self-Attention”, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, pp. 7654–7664. Available at: https://doi.org/10.18653/v1/2022.acl-long.527.

Vancouver

1. Chiang D, Cholak P (2022) Overcoming a Theoretical Limitation of Self-Attention. In: Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, pp 7654–7664

BibTeX

@inproceedings{chiang-cholak-2022-overcoming,
    title = "Overcoming a Theoretical Limitation of Self-Attention",
    author = "Chiang, David  and
      Cholak, Peter",
    editor = "Muresan, Smaranda  and
      Nakov, Preslav  and
      Villavicencio, Aline",
    booktitle = "Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
    month = may,
    year = "2022",
    address = "Dublin, Ireland",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/2022.acl-long.527/",
    doi = "10.18653/v1/2022.acl-long.527",
    pages = "7654--7664"
}

Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

	Train/test lengths matched	Train short, test long
Training tokens	3M+3M	1M+1M
Test tokens	32k+34k	24k+25k
Baseline BLEU	32.6	11.4
Log-length-scaled BLEU	32.5	12.4

Overcoming a Theoretical Limitation of Self-Attention

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — A two-layer transformer recognizes PARITY at every length

Knowl 2 — A transformer recognizes FIRST by selecting the first input position

Knowl 3 — Layer normalization with zero epsilon can make cross-entropy arbitrarily small

Knowl 4 — Paired positive and negative coordinates preserve the exact constructions under layer normalization

Knowl 5 — Multiplying attention logits by log sequence length stabilizes FIRST and permits low cross-entropy

Knowl 6 — Standard attention can fail to generalize FIRST from short to long strings

Knowl 7 — Log-length attention improves long-sentence machine translation BLEU

Knowl 8 — The reported training setup did not learn PARITY, and the exact solution was parameter-sensitive

Knowl 9 — Exact recognition does not prevent cross-entropy from approaching one bit

References

Citation

BibTeX

Access the Paper