Saturated Transformers are Constant-Depth Threshold Circuits (2022)

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 attention 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 attention: 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 transformers. 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.

## introduction opening the ''black box'' @xcite 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 @xcite ; for example, recurrent neural networks (rnns). due to their autoregressive formulation, formal linguistic analysis of rnns has often characterized their power by relating them to automatatheoretic classes of formal languages @xcite @xcite . recently, however, rnns have largely been overtaken in nlp by a new class of models: transformers @xcite . transformers are not autoregressive, and therefore less naturally resemble 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, @xcite and @xcite derive theoretical limitations of transformers with hard attention, meaning the attention distributions focus all probability mass on one index. together, their results show that ac 0 -the class of languages recognizable by constant-depth circuit familiesupper 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, @xcite showed how transformers can solve synthetic counting tasks by using uniform attention patterns, which hard attention does not allow. motivated by this potential disconnect between theory and practice, we aim to extend circuitbased analysis to transformers with saturated attention: a generalization of hard attention that has been argued to approximate attention patterns acquired through gradient descent @xcite . broadly speaking, saturated attention goes beyond hard attention in that it can ''tie'' across a subset of positions, rather than selecting just one position. the tied positions are then aggregated by averaging. qualitatively, saturated attention heads can ''count'': a capability observed in transformers in practice @xcite . further, @xcite show that transformer training dynamics lead attention heads in several pretrained transformers to approximate saturated attention. in summary, saturated attention strictly generalizes hard attention and should more closely reflect the attention patterns acquired in practical transformers. our main contributions are twofold. first, we show that saturated transformers can recognize languages outside ac 0 . then, as depicted in ## roadmap in §3, we formally define our model of the transformer, including defining saturated attention in contrast to hard attention. §4 introduces circuits in theoretical computer science and relevant complexity measures and classes for them. in §5, we first briefly analyze saturated transformers with rational values where the embedding, scoring, and activation functions are allowed to be any size-preserving function. we find such transformers to be universally powerful. we also observe that when the positional embeddings are computed in time linear in the sequence length, saturated rational-valued transformers are exactly as powerful as the complexity class of their activation functions, because the full input sequence can be pooled to a single position, and an activation function can be used as an oracle over the full input sequence. however, this setup relies on the use of unrealistic embedding functions. to move to a more realistic model of computation, we then focus on saturated transformers whose values are restricted to be floats, which have a coarser granularity and, thus, cannot encode the full input sequence into a single position. building on results of @xcite , we demonstrate in §6 that saturated transformers with float activations transcend the theoretical limitations of hard-attention transformers. in particular, we will show that they can recognize the majority language, which lies outside ac 0 . we experimentally validate that transformers can learn to recognize the majority language. taken together, these results suggest that the very weak characterization of hard-attention transformers does not hold in practice for saturated or soft attention. in §7, we show that, on input sequences of length n, the size of each state vector in a transformer over floats is o(log n) bits, similar to saturated lstms (cf. @xcite . thus, the full transformer state at any given layer has size o(n log n), although each feedforward block can only locally access a small, o(log n) ''piece''. thus, while hierarchical representations can be implemented in a transformer (e.g., to process arbitrary-depth dyck languages or reverse strings as in @xcite ), our result implies that they must be distributed in some way across n state vectors, rather than represented compactly within a single vector. finally, in §8, we use the bounded size of transformer representations to upper bound the formal languages that can be recognized by saturated transformers with floating-point values. in particular, we show that such transformers can be simulated by constant-depth threshold circuits, and thus only recognize languages in tc 0 . informally, this suggests that moving from hard attention to saturated attention can be thought of as extending the implicit class of circuit gates available in the network to include threshold gates. our results make progress in the analysis of transformers by deriving upper bounds for a more realistic model of transformers than has previously been analyzed. roberta, t5, and other pretrained transformers have been shown to be approximately saturated @xcite , so our results imply that tc 0 may be a meaningful upper bound on the computation expressible within such networks. our analysis also motivates future work further refining the circuit characterization of saturated transformers, as well as comparing transformers with soft and saturated attention. ## definitions and notation we will often use w to refer to a string over any generic alphabet σ, that is, @xmath0. semantically, w corresponds to the string a transformer receives as input. in contrast, we use x and other symbols to refer to binary strings in {0, 1} * . these binary strings will represent intermediate values within the transformer computation, rather than the raw input to the transformer. ## circuit complexity circuit complexity is a branch of computational complexity theory that studies circuit families as a model of computation. 6 intuitively, circuits are useful for formally studying the types of computational problems that can be efficiently solved with parallelism, as the depth of a circuit corresponds to the runtime of a program on an idealized, fully parallel computer. we review background on circuits, circuit families, and relevant complexity measures and classes. circuits for a fixed n, a circuit is a computation graph, where leaves correspond to input bits x i and their negations ¬x i , and the internal nodes are logic gates (typically ∧ and ∨), with one labeled as the output node. the gates can conventionally be taken to have either binary or unbounded fan-in. the circuit computes a function f : {0, 1} @xmath1, 1} by substituting the input values into the leaf nodes, propagating the computation through the graph, and returning the value of the output node. figure 1 shows an example circuit that takes inputs of length 5, and returns whether they contain the bigram 11. circuit families a circuit family is an ordered set of circuits {c n } @xmath2. we say a circuit family recognizes a formal language l ⊆ {0, 1} * iff, for all @xmath3, foot_5 circuit complexity two important notions of complexity for a circuit are its size and depth. the size of a circuit is the number of gates. the depth is the longest path from an input node to the output node. for a circuit family, both quantities can be expressed as functions of the input size n. a circuit complexity class is a set of formal languages that can be recognized by circuit families of a certain size, depth, and set of gates. in particular, we will discuss the classes ac 0 and tc 0 . definition 7. ac 0 is the set of languages l ⊆ {0, 1} * such that there exists a circuit family recognizing l with unbounded arity {∧, ∨} gates, poly(n) size, and o(1) depth. intuitively, ac 0 represents the class of problems that are highly parallelizable when the computational primitives are standard logic gates. in contrast, tc 0 will also represent highly parallelizable computation, but when the gates are expanded to include threshold gates. for a bitstring @xmath4, 1} * , define the threshold gate θ ≥k (x) to return 1 @xmath5, and equivalently @xmath6. for example, θ ≥3 (110011) = 1. definition 8. tc 0 is the set of languages l ⊆ {0, 1} * such that there exists a circuit family recognizing l with unbounded arity {∧, ∨, θ} gates, poly(n) size, and o(1) depth. it is known that ac 0 ⊂ tc 0 ⊆ nc 1 , where nc 1 denotes the languages recognizable by o(log n)depth circuits with bounded gate arity. whether or not the latter containment between tc 0 and nc 1 is strict is an open question. whereas parity and other basic regular languages are outside ac 0 @xcite , tc 0 properly contains parity, although it is unknown whether it contains all the regular languages. between ac 0 and tc 0 lies the class acc 0 @xcite . ## aren't transformers universal? we now begin our analysis of saturated transformers. @xcite and @xcite were able to give upper bounds on the power of hard attention without imposing any constraints on the embedding, scoring, and activation functions. the same will not be the case with saturated attention: any bounds on transformers will require leveraging some properties constraining their internal functions. one property we use will be size preservation. we will first show, though, that size preservation is not enough on its own: deriving a nontrivial upper bound will depend on subtle assumptions about the transformer's datatype. with rational values and size-preserving internal functions, we will show saturated transformers can recognize any formal language, namely, the class @xmath7, 1} * }. our construction resembles the universal approximation construction of @xcite , which relies on the ability of the transformer to uniquely encode the full input string into a single value vector. after the full sequence is encoded locally into a single vector, the activation block can be used as a black box to recognize any language. theorem 1. ahat(q) = all. proof. we construct a 1-layer rational-valued transformer with a single head to recognize every string w in any formal language @xmath8. we will omit ℓ, h subscripts. let p i denote the ith prime number. the embedding layer encodes each input token according to since p i ∼ i log i for large i by the prime number theorem (cf. goldstein, 1973), the number of bits needed to represent the denominator of φ(w i , i) is since i had size log i, this implies φ is sizepreserving. now, we define a single uniform attention head that sums across all i, outputting w @xmath9. the denominator q of this sum is the product @xmath10. observe that w @xmath11. thus, we can define a function f that extracts the input sequence w from q by checking whether, for each i, p i divides q. we let g be a function recognizing l, and set @xmath12. the output of the transformer will now compute whether @xmath13, since f outputs an encoding of the original input sequence w, and g decides whether @xmath14. note that any function solving a decision problem is size-preserving, hence @xmath15. theorem 1 says that our transformer architecture parameterized with a rational datatype can recognize any formal language. but a construction of this form feels unrealistic for two reasons. first, it requires the embedding layer to implement an unconventional prime encoding scheme in the embedding layer. second, we are using the activation layer as a black box to recognize any language-even uncomputable ones! on the other hand, the feedforward subnetworks used in practice in transformers cannot even implement all computable functions when the weights are fixed independent of the sequence length n. we can get around both these issues by instead restricting the datatype to floats, which is the direction we will pursue in the remaining sections. foot_6 ## beyond hard attention, with floats we now move to the setting of saturated transformers over floats. @xcite identified that hard-attention transformers can only recognize languages within ac 0 . in contrast, saturated transformers over floats can recognize the ''majority'' language maj, which is known to lie outside ac 0 @xcite . @xcite show how maj can be recognized by transformers. in theorem 3, we offer a simpler construction that leverages only a single uniform attention head, as opposed to the model of transformers they were considering. thus, this construction is achievable with saturated attention. theorem 3. ahat(f) ⊆ ac 0 . proof. let # σ (w) ∈ n denote the number of σ tokens in string @xmath16, 1} * . let #(w) denote a count vector where each element corresponds to some σ ∈ {0, 1}. we define maj as follows: we will construct a 1-layer transformer with a single head to recognize maj, omitting ℓ, h subscripts from s, f, x, b. figure 2 gives the same construction in rasp @xcite . let x @xmath17, i) be a 1-hot encoding of w i . for all i, j, set s(x i , x j ) = 1, resulting in a single head attending everywhere: figure 2 : a program recognizing maj in rasp, a programming language designed to abstract away details of transformer computation @xcite . frac{0,1} measure the fraction of inputs that are 0 or 1. then maj checks whether @xmath18. finally, set f (b i ) to return whether # 1 (w)/ @xmath19, which, for @xmath20, is true iff @xmath21. notably, the construction in theorem 3 is not just possible within our generalized transformer framework, but can also be implemented by the standard parameterization of φ, s, and f in real transformers @xcite . the uniform attention pattern can be implemented by setting all query and key attention parameters to 0. then, we can use the affine transformation that aggregates the head outputs to compute the tuple: this tuple is then passed through layer normalization @xcite , resulting in a new tuple t 1 , t 2 . crucially, t 1 > t 2 iff the same applies to the quantities in the original tuple. thus, a linear classifier can decide whether t 1 > t 2 to successfully recognize the language, as per definition 5. ## size of transformer values the theoretical limits on hard-attention transformers were derived by @xcite by bounding the size in bits of the representation v ℓ,i at each layer ℓ and position i. specifically, they show that the value v ℓ,i is representable in o(log n) bits on input sequences of length n. thus, each value can only contain limited information about the input sequence, intuitively explaining their upper bound on hard-attention transformers. inspired by their analysis, this section will show that, in a saturated transformer, each v ℓ,i also has a size of o(log n) bits. later in §8, we will use this property to show that saturated attention transformers are limited in the formal languages they can recognize. ## threshold circuit simulation we have proved that each value vector in a saturated transformer over floats has o(log n) size. now, we show how this implies saturated transformers can be simulated by tc 0 circuits. our results heavily leverage the following lemmas: lemma 2 @xcite . any function f : {0, 1} @xmath22, 1} d can be computed by a boolean circuit of depth 3 and size at most (2 c + c + 1)d. so that our results are self-contained, we reproduce a proof of this lemma in appendix d. applying lemma 2 to a size-preserving function with at most c log n input bits immediately yields: corollary 2.1. any size-preserving function with at most c log n input bits can be computed by a boolean circuit of depth 3 and polynomial size. in other words, such functions can be computed with ac 0 circuits. in addition, we will show that the sum of n floats of size at most c log n can be computed by tc 0 circuits. lemma 3. let v 1 , • • • , v n be a sequence of floats, each with size at most c log n for some c. then the sum n @xmath23. proof. let the integers p i , q i be the numerator and denominator of v i . we first compute q max , the maximum q i , using an ac 0 circuit that compares all pairs q i , q j , and returns the first q i such that q @xmath24. we then use the fact that multiplication and right shift (q i is a power of 2) are in tc 0 , in order to compute in parallel for all i. note that q max and q i are both powers of 2, so the division will be exact. next, we leverage the fact that the sum of n integers of size o(log n) is in tc 0 @xcite , in order to compute the numerator of the sum @xmath25. we select the denominator as @xmath26. finally, we can add an ac 0 circuit that ''reduces'' the fraction by removing shared trailing zeros from p , q , which is possible by corollary 2.1. thus, we have constructed a tc 0 circuit to compute the sum of n floats with size o(log n). we now construct a tc 0 circuit that simulates a saturated transformer over floats. theorem 5. ahat(f) ⊆ tc 0 . proof. for each n, we construct a tc 0 circuit that simulates a saturated transformer on inputs of size n. we construct the circuit modularly, with one subcircuit for the attention mechanism, and another for the feedforward subnetwork. attention head fix a single head in some layer. we will construct a tc 0 subcircuit that simulates the attention mechanism at position i. the head attends over vectors v 1 , • • • , v n . for all j, v j has size o(log n) by theorem 4. in parallel for each j, we compute the scores a i,@xmath27, v j ) with an ac 0 circuit by corollary 2.1. we then compute a i,max max j a i,j with an ac 0 circuit by comparing all v j pairwise, and selecting the first v k such that v @xmath28. we then compute ''masked'' values u i,j for each j via an ac 0 circuit by lemma 2: we then compute the sum s i n @xmath29,j by lemma 3. by lemma 1, s i has size o(log n). now, we similarly define using an analogous sum construction with z i,j instead of u i,j , we can use a tc 0 circuit to compute |m(a)|: the number of j such that a i,@xmath30,max . finally, since dividing floats is in tc 0 (cf. §9), we can compute the head output as s i /|m(a)|, which has size o(log n) by size preservation of division. feedforward as input, f receives v i as well as h head outputs, all of which have size o(log n). as the total size of the input is o(log n), we can use corollary 2.1 to compute the output of f with an ac 0 circuit. the size of the output is o(log n) by size preservation of f . the same idea holds for φ as well as the linear classification head. we have simulated each transformer component with a tc 0 subcircuit, completing the proof. ## conclusion compared with hard attention, saturated attention adds theoretical power to transformers. we showed that saturated attention lets transformers recognize languages outside ac 0 , which is the upper bound with hard attention. further, while saturated transformers with rational values and size-preserving internal functions can recognize any language, we characterize the limits of sizepreserving saturated transformers with floats. specifically, saturated transformers with float values fall in tc 0 , a more powerful circuit class than ac 0 . thus, going from hard to saturated attention can be understood as augmenting the model with threshold gates. this illustrates one way that the circuit complexity paradigm characterizes the power of transformers. going forward, there are many interesting open questions that circuit analysis can answer, such as comparing the power of saturated and soft attention, and refining existing upper bounds for transformers in terms of uniform circuit families. recall that a transformer is a tuple σ, d, α, l, h, φ, s ℓ,h , f ℓ . in contrast to ahat(d) (cf. definition 6), we will now work with a different class of transformer languages ahat(d, t (m)) we will allow the embedding functions to be linear in the sequence length, and explore the effect of varying the complexity of the other internal functions. let ftime(t (m)) be the set of functions computable by a turing machine in t (m) time. 10 definition 10. let ahat(d, t (n)) be the class of languages l ⊆ σ * such that there exists a transformer σ, d, α, l, h, φ, s ℓ,h , f ℓ that recognizes l, where φ runs in time linear in the sequence length n, and s ℓ,h , f ℓ ∈ ftime(t (m)). for any t (m) m, we will show transformers ahat(d, t (m)) have the complexity of their activation functions. formally: theorem 2 (formal version of theorem 2). for @xmath31, q} and t (m) m, ahat(d, t (m)) ⊆ time(t (m)). proof. first, observe that ahat(d, t (m)) ⊆ time(t (m)), since the embedding function and saturated attention can be computed in time linear in the input sequence length, and the other internal functions can be computed in ftime(t (m)) by construction. we now show time(m) ⊆ ahat(d, t (m)). we adopt a 1-layer transformer construction, and thus omit ℓ, h subscripts. we define three components of the embedding function φ : σ × @xmath32: each of these components is computable in time linear in n. define three heads b 1,i , b 2,i , b 3,i . without loss of generality, consider b h,i to act on φ(w i , i) h alone, rather than the full embeding vector. b 1,i is defined as a uniform head, while b 2,i and b 3,i are computed with s h (v i , v j ) = v j . thus, finally, we discuss how to set f to compute whether @xmath33. let p be the function that extracts the numerator of a float or rational number, which is computable in o(m) time on float of size m. within f , we compute @xmath34,i ). at this point, we proceed in two cases depending on the datatype d: so, time(t (m)) ⊆ ahat(d, t (m)).