Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity Yiding Hao, Dana Angluin, and Robert Frank Yale University New Haven, CT, USA {yiding.hao, robert.frank, dana.angluin}@yale.edu Abstract This paper analyzes three formal models of Transformer encoders that differ in the form of their self-attention mechanism: unique hard attention (UHAT); generalized unique hard at- tention (GUHAT), which generalizes UHAT; and averaging hard attention (AHAT). We show that UHAT and GUHAT Transformers, viewed as string acceptors, can only recog- nize formal languages in the complexity class AC0, the class of languages recognizable by families of Boolean circuits of constant depth and polynomial size. This upper bound sub- sumes Hahn’s (2020) results that GUHAT cannot recognize the DYCK languages or the PARITY language, since those languages are outside AC0 (Furst et al., 1984). In contrast, the non-AC0 languages MAJORITY and DYCK-1 are recognizable by AHAT networks, imply- ing that AHAT can recognize languages that UHAT and GUHAT cannot. 1 Introduction The Transformer architecture for neural networks (Vaswani et al., 2017) has yielded remarkable advances in performance on a variety of bench- mark tasks in natural language processing. These advances have spurred considerable interest in understanding the capabilities and limitations of the Transformer architecture. While Transformer networks are extremely complex when deployed at scale, theoretical studies such as those of P´erez et al. (2019), Yun et al. (2020), Hahn (2020), and Merrill et al. (2022) have uncovered mean- ingful insights about the expressive power of Transformers by formulating abstract models of the self-attention mechanism and analyzing their computational power. In this work, we analyze three restricted models of self-attention based on their ability to recog- nize formal languages. All three models use hard attention—meaning that each attention head at- tends only to the position or positions with the highest attention score, with no attention paid to any of the other positions—but differ in how they behave in the case of ties in the maximum at- tention value. In the first two models we study, the attention mechanism returns the value at ex- actly one position (for example, the leftmost) in case several positions tie for the maximum at- tention value. The first such model, which we call generalized unique hard attention Transform- ers (GUHAT) and was defined by Hahn (2020), imposes no restrictions on the nature of activa- tion values or the functions the network uses to compute them. The second model, unique hard attention Transformers (UHAT), was defined and studied by Yao et al. (2021) and is a more concrete version of GUHAT that incorporates restrictions on the nature of activation values and computa- tions. In the third model, which we call averaging hard attention Transformers (AHAT), the atten- tion mechanism returns the uniform average of the values at positions with the maximum atten- tion value. This is the definition of hard attention used by P´erez et al. (2019), Yun et al. (2020), and Merrill et al. (2022).1 Our main contribution is to prove that GUHAT and UHAT can only recognize formal …

Content truncated to 500 words