Overcoming a Theoretical Limitation of Self-Attention

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 7654 - 7664 May 22-27, 2022 c⃝2022 Association for Computational Linguistics Overcoming a Theoretical Limitation of Self-Attention David Chiang and Peter Cholak University of Notre Dame {dchiang,cholak}@nd.edu Abstract Although transformers are remarkably effec- tive for many tasks, there are some surprisingly easy-looking regular languages that they strug- gle 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 in- put strings get longer and longer. We exam- ine 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 ques- tion by constructing a transformer that recog- nizes PARITY with perfect accuracy, and sim- ilarly for FIRST. Second, we use layer nor- malization to bring the cross-entropy of both models arbitrarily close to zero. Third, when transformers need to focus on a single posi- tion, as for FIRST, we find that they can fail to generalize to longer strings; we offer a sim- ple remedy to this problem that also improves length generalization in machine translation. 1 Introduction Although transformers (Vaswani et al., 2017) are remarkably effective for many tasks, there are some surprisingly easy-looking formal languages that they struggle with. Hahn (2020) tries to explain some of these by showing (his Lemma 5) that changing a single input symbol only changes the output of a transformer encoder by 𝐴���(1/𝐴���), where 𝐴��� is the input string length. Thus, for a language where acceptance depends on a single input sym- bol, a transformer might accept or reject strings with perfect accuracy, but for large 𝐴���, it must do so with low confidence, giving accepted strings a probability just above ½ and rejected strings a probability just below ½. More precisely, as 𝐴��� increases, the cross-entropy approaches its worst possible value of 1 bit per string. Here, we examine this limitation using two sim- ple regular languages: PARITY = {𝐴��� ∈ Σ∗ | 𝐴��� has an odd number of 1s} FIRST = {𝐴��� ∈ Σ∗ | 𝐴���1 = 1} where (here and throughout the paper) Σ = {0, 1}. Hahn’s lemma applies to PARITY because the net- work must attend to all the symbols of the string, and a change in any one of them changes the correct answer. We have chosen FIRST as one of the sim- plest examples of a language that the lemma applies to. It only requires attention on the first symbol, but the lemma still applies because a change in this symbol changes the correct answer. Although the lemma might be interpreted as lim- iting the ability of transformers to recognize these languages, we show three ways that this limitation can …

Content truncated to 500 words