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

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 attention (GUHAT), which generalizes UHAT; and averaging hard attention (AHAT). We show that UHAT and GUHAT Transformers, viewed as string acceptors, can only recognize 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 subsumes 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, implying that AHAT can recognize languages that UHAT and GUHAT cannot.

## introduction the transformer architecture for neural networks @xcite has yielded remarkable advances in performance on a variety of benchmark 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 @xcite , @xcite , @xcite , and @xcite have uncovered meaningful 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 recognize formal languages. all three models use hard attention-meaning that each attention head attends 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 attention value. in the first two models we study, the attention mechanism returns the value at exactly one position (for example, the leftmost) in case several positions tie for the maximum attention value. the first such model, which we call generalized unique hard attention transformers (guhat) and was defined by @xcite , imposes no restrictions on the nature of activation values or the functions the network uses to compute them. the second model, unique hard attention transformers (uhat), was defined and studied by @xcite and is a more concrete version of guhat that incorporates restrictions on the nature of activation values and computations. in the third model, which we call averaging hard attention transformers (ahat), the attention mechanism returns the uniform average of the values at positions with the maximum attention value. this is the definition of hard attention used by @xcite , @xcite , and @xcite . 1 our main contribution is to prove that guhat and uhat can only recognize formal languages in ac 0 , the class of formal languages recognized by a family of boolean circuits of constant depth and polynomial size, whereas ahat can recognize formal languages outside of ac 0 . more formally, we prove that any formal language recognized using a guhat is also recognized by a family of boolean circuits of constant depth and polynomial size, establishing ac 0 as an upper bound on the expressiveness of uhat and guhat. we also show that every uhat can be simulated by an ahat, establishing uhat as a subclass of ahat. based on the classical results of @xcite , our upper bound subsumes @xcite results that guhat cannot recognize the dyck languages or the parity language, neither of which belongs to ac 0 . furthermore, our result combines with @xcite ahat implementation of the majority language and @xcite ahat implementation of dyck-1 (neither of which is in ac 0 ) to show that ahat can recognize languages that guhat cannot. recently, @xcite have given an upper bound on the power of ahat: namely, that every formal language recognizable using averaging hard attention is recognizable using a family of circuits of constant depth and polynomial size with boolean and majority gates; that is, a family of circuits in the complexity class tc 0 , known to be a strict superset of ac 0 . taken together, our paper establishes the following relationships between the three models we consider of hard-attention transformers. let σ be a fixed finite alphabet of symbols, and let @xmath0, which should be rejected. the input function is defined as f (σ, i, n) = (σ, i, n) for each σ ∈ σ and @xmath5..n]. for our example input, the initial (layer 0) activation values are shown in the first row of figure 1 . these activation values are not rational-valued vectors, of course, but the guhat model imposes no restriction on the form these values can take. for each position @xmath6, this selects the activation at the correct corresponding position, ni. for position n, it selects the activation at position n. the layer 1 activation values for our example input are shown in the second row of figure 1 . this indicates that positions 2 and 4 found mismatched symbols, and positions 1, 3, and 5 did not. layer 2 gathers the relevant information from layer 1 into the last position. the layer 2 attention function is defined by f att 2,1 ((r, i), (s, j)) = s. this directs the attention at every position to the leftmost activation value (s, j) from layer 1 such that @xmath7. in our example, the leftmost such position is 2, with its activation of (1, 2). if the input sequence had instead been a valid palindrome, none of the positions @xmath8..n -1] would have been marked with (1, i) by layer 1. in this case, the leftmost position with @xmath9, which has the activation value of (1, n). we define the layer 2 activation function as f act 2 ((r, i), (s, j)) = (i, j). for our example input, the activation values for layer 2 are shown in the third row of figure 1 . the activation value at position n will be (n, n) if and only if no earlier position found a symbol mismatch, so the model output function is simply g((i, j)) = {@xmath10. with the input sequence abcca@xmath1, the activation for position 6 at layer 2 is (6, 6) and the output value is 1. generalizing this construction to an arbitrary alphabet σ, we have the following. proposition 2. for any finite alphabet σ, the language palindromes over σ is in guhat. ## a normal form for guhat despite the abstractness and generality of the guhat model, we can define a normal form representation and show that every transformer t in guhat is equivalent to a transformer in guhat in this normal form with the same number of layers and heads. the key idea is to preserve in the activation values all the information from previous layers that has been used to compute them, by requiring that the input and activation functions just return the tuple of their arguments. we also require that attention values be integers in the smallest relevant range. definition 13. a guhat with k layers and h heads is in informative normal form if and only if the following conditions are satisfied. lemma 1. for any transformer @xmath11, there exists a transformer @xmath12. moreover, t has the same number of layers and heads as t . proof. let t be a guhat with k layers and h heads, with input alphabet σ, input function f , attention functions f att k,h , activation functions f act k , and output function g. we describe how to construct functions for an equivalent transformer t in guhat in informative normal form, which also has k layers and h heads. we assume that n is the input length. for t the input function f (σ, i, n) is defined to return the triple (σ, i, n). note that there are at most |σ|n possible initial activation values. we also define a function t 0 that translates initial activation values for t into initial activation values for t by t 0 (σ, i, n) = f (σ, i, n). now, we induct on the layers of t and t . assume that we have defined attention and activation functions for t for layers before k (where the initial activation values are treated as ''layer 0''), and a translation function t k-1 that translates all possible activation values for t from the previous layer into activation values for t from the previous layer. to define the attention function for t for layer k for head h, we enumerate all the possible pairs ŷi and ŷj of activation values of t at layer k -1, and determine the corresponding attention values of t , which we denote by by construction, t is in informative normal form, and it has k layers and h heads. it is not difficult to see that for any input x, the translations t k (ŷ) of the activation values ŷ of t are equal to the corresponding activation values of t , and the outputs t (x) = t (x) are equal as well. thus, l( t ) = l(t ). to illustrate the construction of t in the proof of lemma 1, we briefly show how an informative normal form version of the transformer for palindromes from section 5 would process the input @xmath13, 6, 6)), @xcite , (c, 4, 6))), which is mapped to (6, 2) by t 2 . the previous example's output function compares 6 and 2 and returns 0, rejecting the input x. theorem 1. every language in guhat is recognized by a family of circuits in ac 0 . let l be a language over σ that is in guhat. by lemma 1, we may assume that l is recognized by guhat transformer t in informative normal form. assume t has k layers and h heads. what we describe below is a family of circuits to recognize the end-marked language l@xmath3 at the end of the input string using constant gates. let @xmath14. the key step of the proof is to bound the number of bits needed to represent attention and activation values for an input sequence of length n by o(log n), where the suppressed constants depend on k and h. lemma 2. let t be a guhat in informative normal form with k layers and h heads, and alphabet σ. let @xmath15. then for any input of length n and any @xmath16..k], the activation values at layer k can be represented by (h + 1) k (2ℓ(n) + s) bits, and for @xmath17, the attention scores at layer k can be represented by proof. for an input sequence of length n, the initial activation values are (σ, i, n), where σ ∈ σ ∪ {$} and @xmath18..n]. this can be represented by a string of 2ℓ(n) + s bits. at each successive layer, the activation values are a tuple of (h + 1) values from the previous layer, which multiplies the number of bits required to represent them by (h + 1). also, the range of attention scores is bounded by the number of ordered pairs of activation values at the previous layer, so attention values can be represented by twice the number of bits to represent an activation value at the previous layer. it is worth observing that the bounds provided by lemma 2 do not hold in the case of ahat. attention scores may be the result of the average of an arbitrary subset of the possible inputs, which means that there are exponentially more possible activation values at each layer. the following elementary facts about boolean circuits will be useful. lemma 3. an arbitrary boolean function f of n inputs and m outputs can be computed by a depth 3 circuit of size at most m(n2 n + 2 n + n). proof. express each output z i of f as a disjunctive normal form (dnf) formula of at most 2 n terms, each with at most n literals. convert each dnf formula to a circuit with one or gate with inputs from an and gate for each term, each of whose inputs is either an input to the function, or the result of applying a not gate to an input. in each such circuit, the or gate has at most 2 n input wires, each and gate has at most n input wires, and each of at most n not gates has one input wire, for a total size bounded by n2 n + 2 n + n. the final circuit consists of these m separate circuits computing in parallel, and its size is at most m times the size of each one. the longest possible path to an output from an input is through a not, an and, and the or gate, for a depth of at most 3. corollary 1. if a boolean function f has at most c log n inputs and at most d log n outputs, then it may be computed by a boolean circuit of depth 3 and size at most with the o(log n) bound on the number of bits to represent activation and attention values, lemma 2 yields circuits of constant depth and size polynomial in n for the input, attention, activation, and output functions. additional circuitry is necessary to implement the comparison of attention scores and selection of the activation value to attend to for each position, layer, and head. we construct the overall circuit c sn according to the layers of t , starting with the input function. let the inputs to t be x i for @xmath19..n]. the inputs to c sn are x i,j for @xmath20..n] and @xmath21..s], where x i,j are the bits of h(x i ), representing the binary encoding of input symbol x i . at layer 0 for position i, the value of y (0 i, n) is achieved by having the input wires x i,j for @xmath22..s] followed by a sequence of constants 0 or 1 representing bin(i, n) and bin(n, n) for a total of 2ℓ(n) + s wires representing the value inducting on layers, we assume that for some @xmath23..k] the circuit c sn has been constructed to contain the wires representing all the activation values y (k-1) i for @xmath24..n] at layer k -1. the portion of the circuit computing the representations of activation values at layer k is described as follows. fix a position @xmath25..n] and a head @xmath26..h]. for each @xmath27..n], there is a circuit a i,j,k,h that has as input the wires for the activation values y (k-1) i and y (k-1) j and as output, wires representing the nonnegative integer attention score a i,j,k,h in binary. each of these circuits a i,j,k,h has 2(h + 1) k-1 (2ℓ(n) + s) inputs and outputs by lemma 2, and therefore can be computed using depth 3 and size polynomial in n, by corollary 1. all hn 2 such circuits for layer k operate in parallel, for overall depth 3 and size polynomial in n. we next describe the circuit that implements the pooling function f uha . for each pair j, @xmath28..n], there is a circuit d i,j,j ,k,h whose inputs are the outputs of a i,j,k,h and a i,j ,k,h and whose output is a single wire g i,j,j ,k,h with a value of 1 if a i,j,k,@xmath29,j ,k,h and 0 otherwise. because of the bounds on the number of inputs and outputs, each of these circuits can have depth 3 and size polynomial in n by corollary 1. these n 2 circuits all compute in parallel. 3 then for each position j, whether j maximizes a i,j,k,h can be computed by an and gate whose inputs are g i,j,j ,k,h for all @xmath30..n]. let the output of this and gate be denoted m i,j,k,h . then m i,j,k,@xmath31,j,k,h . this increases the depth by 1. for each j, an indicator z i,j,k,h is computed by an and gate whose inputs are m i,j,k,h and not(m i,j ,k,h ) for all @xmath32. thus, z i,j,k,@xmath33,j,k,h . this increases the depth by 2. finally, these indicator values are used to combine the layer k -1 activation values in a selection circuit, yielding the representation of the activation value b i,k,@xmath34,j,k,@xmath35. in general, such a selection circuit takes as input t selector bits z 1 , . . . , z t , where exactly one z @xmath36, and t input values w 1 , . . . , w t , where each w r consists of s bits. it outputs s bits representing the selected w j (for which z @xmath37. letting w r,s denote bit s of w r , the computation can be described as v r,@xmath38,s ∧ z r for @xmath39..t] and @xmath40..s], which can be computed by one layer of ts and gates in parallel. then the bits of the output are u @xmath41,s for @xmath42..s], which can be computed by one layer of s or gates in parallel. thus, the selection circuit adds 2 to the depth, and a polynomial in n to the size. because each activation function for a guhat in informative normal form simply returns its arguments, no further computation is needed for the activation values. the representation of the activation value y (k) i is just the sequence of wires representing y (k-1) i followed by those representing b i,k,1 , through b i,k,h . to produce the output of the circuit, we note that the representation of y (l) n has o(log n) bits and the output of g is a single bit, so g can be implemented by a boolean circuit of constant depth and size polynomial in n, by corollary 1. this concludes the proof of theorem 1. @xcite prove that the parity, equality, and majority languages are not in ac 0 , which immediately implies the following. ## discussion and conclusions we have defined formal language recognition by the encoder portion of a transformer network using generalized unique hard attention (guhat), unique hard attention (uhat), and averaging hard attention (ahat), and shown that languages in uhat and guhat are recognizable by constant depth, polynomial size families of circuits, that is, families of circuits in the complexity class ac 0 . this strengthens the negative result of hahn (2020) that the languages parity and dyck-k are not in guhat, and provides a simpler and more general proof. combined with prior results of @xcite showing that the language majority is in ahat, or @xcite showing that the language dyck-1 is in ahat, this shows that ahat contains languages that are not in guhat or uhat. many intriguing open questions remain. what classical closure properties hold for the classes of languages guhat, uhat, and ahat? closure under complement just requires complementing the output function g, and closure under pairwise union and intersection should be straightforward using a parallel approach; but what about closure under homomorphism, inverse homomorphism, concatenation, or kleene star? we briefly observe that guhat and uhat cannot be closed under both kleene star and concatentation lest they contain all regular languages, including parity. existing formal models and indeed practical implementations of transformers vary in their representation of position information, whether as an absolute representation of position, a ratio (e.g., position i in a sequence of length n as i/n), through angle information (e.g., position i by the pair (cos θ i , sin θ i ) where θ @xmath43, or as an arbitrary learned embedding. in the uhat and ahat models, the choice of positional encoding can facilitate positional comparison (e.g., an angle-based encoding allows for equality testing via dot products) or make it uncomputable (e.g., if positional encodings enumerate turing machines that halt on their own encodings). it remains to be understood what effect such differences in position representation have on the expressive power of a model. more generally, is it possible to prove that soft attention, which we have not addressed here, is strictly more powerful than even averaging hard attention? @xcite 3) present a construction for a soft attention transformer that recognizes dyck-k. this construction crucially uses specialized encodings of position and layer normalization, whose formal power remains to be understood. finally, given the success that transformers have had as models of natural language, it is perhaps surprising that these models' expressive power seems to be best characterized (or at least bounded) in terms of circuit complexity. mathematical explorations of natural language have most commonly used the approach to language complexity afforded by the chomsky hierarchy and its refinements, which is based on automata and formal grammars. the apparent incomparability of these approaches suggests that the exploration of different types of transformer models might offer a new approach to the study of the formal properties of natural language.