Saturated Transformers are Constant-Depth Threshold Circuits

Saturated Transformers are Constant-Depth Threshold Circuits William Merrill∗† Ashish Sabharwal∗ Noah A. Smith∗‡ ∗Allen Institute for AI, USA †New York University, USA ‡University of Washington, USA willm@nyu.edu {ashishs, noah}@allenai.org Abstract Transformers have become a standard neural network architecture for many NLP problems, motivating theoretical analysis of their power in terms of formal languages. Recent work has shown that transformers with hard atten- tion are quite limited in power (Hahn, 2020), as they can be simulated by constant-depth AND/OR circuits (Hao et al., 2022). However, hard attention is a strong assumption, which may complicate the relevance of these results in practice. In this work, we analyze the circuit complexity of transformers with saturated at- tention: a generalization of hard attention that more closely captures the attention patterns learnable in practical transformers. We first show that saturated transformers transcend the known limitations of hard-attention transform- ers. We then prove saturated transformers with floating-point values can be simulated by constant-depth threshold circuits, giving the class TC0 as an upper bound on the formal languages they recognize. 1 Introduction Opening the ‘‘black box’’ (Alishahi et al., 2020) of the representations within neural networks is an important step towards building systems with robust and interpretable behavior. In NLP, one part of this question is analyzing the languages that networks can model, and the mechanisms they use to represent linguistic structure and dependencies. One path toward this goal is via formal analysis of specific network architectures (Merrill, 2021); for example, recurrent neural networks (RNNs). Due to their autoregressive formulation, formal linguistic analysis of RNNs has often character- ized their power by relating them to automata- theoretic classes of formal languages (Weiss et al., 2018; Peng et al., 2018; Merrill, 2019, inter alia). Recently, however, RNNs have largely been over- taken in NLP by a new class of models: transform- ers (Vaswani et al., 2017). Transformers are not autoregressive, and therefore less naturally resem- ble automata, posing challenges to characterizing their linguistic capacity or inductive biases in the same terms as RNNs. Instead, some recent work has related them to circuit complexity classes, a direction that we continue to pursue in this paper. Drawing on classical circuit lower bound results, Hao et al. (2022) and Hahn (2020) derive theo- retical limitations of transformers with hard at- tention, meaning the attention distributions focus all probability mass on one index. Together, their results show that AC0—the class of languages recognizable by constant-depth circuit families— upper bounds the formal languages hard-attention transformers can recognize. However, hard attention is a strong assumption, making it unclear how these results transfer to practical transformers. For example, Bhattamishra et al. (2020) showed how transformers can solve synthetic counting tasks by using uniform atten- tion patterns, which hard attention does not allow. Motivated by this potential disconnect between theory and practice, we aim to extend circuit- based analysis to transformers with saturated at- tention: a generalization of hard attention that has been argued to approximate attention patterns ac- quired through gradient descent (Merrill et al., …

Content truncated to 500 words