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

Introduction

The Transformer architecture for neural networks (Vaswani et al., 2017) 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 Pérez et al. (2019), Yun et al. (2020), Hahn (2020), and Merrill et al. (2022) 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 Hahn (2020), 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 Yao et al. (2021) 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 Pérez et al. (2019), Yun et al. (2020), and Merrill et al. (2022).Merrill et al. (2022) call it saturated hard attention.

Our main contribution is to prove that GUHAT and UHAT can only recognize formal languages in AC0, 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 AC0. 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 AC0 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 Furst et al. (1984), our upper bound subsumes Hahn’s (2020) results that GUHAT cannot recognize the DYCK languages or the PARITY language, neither of which belongs to AC0. Furthermore, our result combines with Pérez et al.’s (2019) AHAT implementation of the MAJORITY language and Bhattamishra et al.’s (2020) AHAT implementation of DYCK-$1$ (neither of which is in AC0) to show that AHAT can recognize languages that GUHAT cannot. Recently, Merrill et al. (2022) 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 TC0, known to be a strict superset of AC0. Taken together, our paper establishes the following relationships between the three models we consider of hard-attention Transformers.

Preliminaries

Let $\Sigma$ be a fixed finite alphabet of symbols, and let \$be a distinct end-of-sequence symbol not in$\Sigma$. The set of strings of symbols over$\Sigma$of length$n$is denoted by$\Sigma^{n}$, and the set of all finite strings over$\Sigma$is denoted$\Sigma^{*}$. A (formal) language over$\Sigma$is any subset of$\Sigma^{*}$.

Circuit Complexity

Our analysis of UHAT and GUHAT is carried out within the framework of circuit complexity, in which the complexity of a computational system is measured by the size, depth, and types of gates of a Boolean circuit implementing that system. In this section we review the basic concepts, definitions, and results of circuit complexity used by our analysis. A detailed overview is provided in Chapter 6 of Arora and Barak (2009).

Boolean circuits are a formal model of computational systems based on logic gates. Roughly speaking, a Boolean circuit consists of binary-valued input and output layers, with feedforward connectionsWe consider only acyclic circuits. to one another via intermediate gates that implement logical operations. We use the following definition of Boolean circuits.

A Boolean circuit with $n$ inputs and $m$ outputs is a labeled directed acyclic graph satisfying the following conditions. There are $n$ distinguished input vertices labeled with the variables $x_{1},x_{2},\ldots,x_{n}$. Each input vertex has fan-in . The rest of the vertices are gates, each having a label from Constant-0, Constant-1, NOT, AND, or OR. The Constant-0 and Constant-1 gates have fan-in , NOT gates have fan-in $1$, and AND and OR gates have unbounded fan-in. Finally, the labels $z_{1},z_{2},\ldots,z_{m}$ are applied to some (not necessarily distinct) vertices; these are the outputs.

We refer to the edges of a Boolean circuit as wires. The size of a circuit is the number of wires it contains, and the depth of a circuit is the maximum length of a directed path of wires from an input vertex to an output. A Boolean circuit $C$ computes a Boolean function from $\{0,1\}^{n}$ to $\{0,1\}^{m}$; we denote its output on input $x=x_{1}x_{2}\dots x_{n}$ by $C(x)$.

Observe that a Boolean circuit has a fixed number of input vertices, and therefore can only take as input bit strings of a fixed length. We would like to define circuit computation for a map defined on all of $\{0,1\}^{*}$. To that end, we allow different circuits for inputs of different lengths.

A family of circuits is a sequence $\{C_{n}\}$, where for each integer $n\geq 0$, $C_{n}$ is a Boolean circuit with $n$ inputs and one output. A map $f$ from $\{0,1\}^{*}$ to $\{0,1\}$ is computed by a family of circuits $\{C_{n}\}$ if and only if for all $n$ and all $x\in\{0,1\}^{n}$, $f(x)=C_{n}(x)$.

The class AC0 is defined by setting restrictions on the size and depth of circuits within a family of Boolean circuits.

A family of circuits is of constant depth if there exists a constant $K$ such that the depth of $C_{n}$ is bounded by $K$ for all $n$. A family of circuits is of polynomial size if there exists a constant $c$ such that the size of $C_{n}$ is bounded by $n^{c}+c$ for all $n$. The set AC0 is the set of families of Boolean circuits of both constant depth and polynomial size.

2 Non-AC0 Languages

Having defined the class AC0, we present some examples of languages not belonging to this class. First, the following three languages were shown by Furst et al. (1984) to fall outside AC0.

We define the following languages over the alphabet $\{0,1\}$. The language PARITY is the set of all strings containing an even number of $1$s; MAJORITY is the set of strings with at least as many $1$s as s; and EQUALITY is the set of strings with exactly as many $1$s as s.

Additionally, we show later in this paper (Corollary 3) that DYCK-$1$ also falls outside AC0.

The language DYCK-$k$ is the set of strings over an alphabet of $k$ types of pairs of brackets that are correctly nested and matched. For example, DYCK-$2$ over the alphabet $\{(,),\}$ can be described by a context free grammar with productions $S\to\varepsilon$, $S\to(S)$, $S\to[S]$, and $S\to SS$. The language DYCK-$(k,D)$ is the set of strings in DYCK-$k$ in which the depth of nesting of brackets never exceeds $D$. The language SHUFFLE-$k$ is the shuffle (arbitrary interleaving) of strings from $k$ versions of DYCK-$1$ each using a different type of bracket pair.

Finally, we define PALINDROMES, a language shown in Section 5 to be in GUHAT.

The language PALINDROMES is the set of strings equal to their reverses, which can be described by the context free grammar with productions $S\to\varepsilon$, $S\to\sigma$, and $S\to\sigma S\sigma$ for each alphabet symbol $\sigma$.

Hard Attention Transformers

We now define the three kinds of hard attention Transformers studied in this paper: GUHAT, UHAT, and AHAT. These formalisms are models of computation inspired by the encoder portion of the Transformer architecture. They conceptualize Transformers as cascading layers of feature extractors that convert a sequence of embeddings into increasingly higher-level representations.

We begin by presenting a general framework that subsumes the three hard attention Transformer models. Formally, a generalized Transformer is a device that maps a string x\in\Sigma^{*}\$to$1$or , signifying that$x$ is accepted or rejected, respectively. Each such device is parameterized by a collection of functions described as follows.

A generalized Transformer with $K$ layers and $H$ attention heads is a tuple $T=(\Sigma,\mathcal{A},f,f^{\operatorname{att}}_{k,h},f^{\operatorname{pool}},f^{\operatorname{act}}_{k},g\,\mid k\in[1..K],h\in[1..H])$ where

$\mathcal{A}$ is the set of activation values,

$f_{k}^{\operatorname{act}}:\mathcal{A}^{H+1}\to\mathcal{A}$ is the activation function for layer $k$, and

$g:\mathcal{A}\to\{0,1\}$ is the model output function.

On input $x_{1}x_{2}\dots x_{n}$ where x_{n}=\$, a string$y^{(0)}_{1}y^{(0)}_{2}\dots y^{(0)}_{n}\in\mathcal{A}^{n}$ of initial activation values is given by

for all $i$. Each layer $k$ then produces a string $y^{(k)}=y^{(k)}_{1}\allowbreak y^{(k)}_{2}\allowbreak\dots\allowbreak y^{(k)}_{n}\allowbreak\in\mathcal{A}^{n}$ of activation values from the previous activation values $y^{(k-1)}=y^{(k-1)}_{1}y^{(k-1)}_{2}\dots y^{(k-1)}_{n}$ as follows. First, each attention head $h$ produces an $n\times n$ matrix of attention scores $a_{i,j,k,h}$ given by

for all positions $i,j$ of the input string. Next, the pooling function converts each row of attention scores into an activation value based on $y^{(k-1)}$:

Finally, the layer output $y^{(k)}$ is computed using the layer’s activation function:

When $y^{(k)}$ has been computed for all $k\in[1..K]$, the final output of the generalized Transformer $T(x)$ is computed by applying the model output function to the last symbol of $y^{(K)}$; that is,

If $T(x)=1$, we say that $T$ accepts $x$; otherwise, we say that $T$ rejects $x$. The language recognized by $T$, denoted $L(T)$, is the set of strings $x\in\Sigma^{*}$ such that $T$ accepts x\$.

The formalism we have presented above is fully generalized in the sense that we have placed no restrictions on the activation values $\cal{A}$ or the functions $f$, $f_{k,h}^{\operatorname{att}}$, $f^{\operatorname{pool}}$, $f_{k}^{\operatorname{act}}$, or $g$, other than to specify their domains and co-domains. The three hard attention Transformer models are derived by placing restrictions upon these elements.

2 Unique and Averaging Hard Attention

The first restriction we consider is on the form of the pooling function. We consider two types of pooling functions: the unique hard attention function, used in GUHAT and UHAT, and the averaging hard attention function, used in AHAT.

In unique hard attention, the pooling function simply selects the activation value from the previous layer corresponding to the argmax of the row of attention scores. In case of a tie, the leftmost activation value is selected.

Averaging hard attention is similar to unique hard attention, except that in the case of a tie, the selected activation values are averaged.

The GUHAT model is defined as the class of generalized Transformers that use unique hard attention.

A generalized unique hard attention Transformer is a generalized Transformer whose pooling function is $f^{\operatorname{UHA}}$. We use the term GUHAT to refer to the class of generalized unique hard attention Transformers, and also to the class of languages they recognize.

The GUHAT model mostly follows the definitions of Hahn (2020). It is slightly generalized in allowing the input function $f$ to depend on the input length $n$, and in allowing the activation function $f_{k}^{\operatorname{act}}$ to depend on the layer $k$, but these generalizations are immaterial. In particular, it is not necessary to assume that the input length $n$ is provided to the input function: if the input function were $f(\sigma,i)=(\sigma,i)$, the subsequent layer could direct attention at every position to position $n$ (because it uniquely contains the end-of-sequence symbol \$), at which point the value of$n$ is available at every position.

3 Restricted Models: UHAT and AHAT

GUHAT allows the activation values $\cal{A}$ and the functions $f$, $f_{k,h}^{\operatorname{att}}$, $f_{k}^{\operatorname{act}}$, and $g$ to take on any arbitrary mathematical value. In practical applications of Transformer networks, however, these components are restricted in specific ways. Many variations of hard attention Transformers attempt to incorporate these restrictions into theoretical models, though they do not entirely agree on the details of these restrictions.

The UHAT and AHAT models adopt many of these restrictions, largely following the definitions of Yao et al. (2021). For the sake of computability, we require activation values to be vectors of rational numbers. Following Pérez et al. (2019), we restrict scalars to be rational as well. Next, we assume that the input function $f$ is decomposed into a token embedding function and a position embedding function. Mirroring the more familiar description of attention functions in terms of query, key, and value matrices, we use a bilinear form for attention functions proposed in Luong et al. (2015). In addition to the unique and averaging hard attention mechanisms, we allow the pooling function to be future-masked (where for position $i$ only those positions $j$ with $j\leq i$ are considered in the attention computation) or past-masked (similarly for $j\geq i$). Finally, we assume that activation functions and the model output function are computed by feedforward neural networks with ReLU activation. These restrictions are summarized below.

the pooling function may be future-masked or past-masked;

each activation function is computed by a feedforward neural network with ReLU activation;

the output function $g$ is computed by a feedforward neural network with ReLU activation followed by a softmax layer, with $g(y)=1$ if and only if the output of the network on input $y$ is greater than or equal to $1/2$.

Because $\Sigma$ is finite, we may assume that the token embedding function is given by a table lookup. Our formulation of position embedding is somewhat more general than the definition of Yao et al. (2021), who take the position embedding to be a scalar defined as $p(i,n)=i/n$ that occupies one position of the initial activation vector.

The UHAT and AHAT models are defined to be restricted Transformers that satisfy the above conditions and use unique and averaging hard attention, respectively.

A unique hard attention Transformer is a restricted Transformer whose pooling function is $f^{\operatorname{UHA}}$ or a future- or past-masked version thereof. An averaging hard attention Transformer is a restricted Transformer whose pooling function is $f^{\operatorname{AHA}}$ or a future-or past-masked version thereof. We use the terms UHAT and AHAT, respectively, for these classes of Transformers, and also for the classes of languages they recognize.

UHAT is clearly a subclass of GUHAT because the former imposes restrictions on the form of the input, attention, activation, and output functions. We suspect, but do not prove, that this inclusion is proper. Moreover, we briefly argue below that UHAT is properly contained in AHAT.

Since AHAT recognizes non-AC0 languages (Pérez et al., 2019; Bhattamishra et al., 2020), it suffices to show that $\text{UHAT}\subseteq\text{AHAT}$. Let $T$ be a UHAT of dimension $d$ recognizing $L$. We define a UHAT $\hat{T}$ of dimension $d+2$ recognizing $L$ that has no ties in its attention values. Since the pooling functions $f^{\operatorname{UHA}}$ used in UHAT and $f^{\operatorname{AHA}}$ used in AHAT are identical in the absence of ties, replacing the pooling function of $\hat{T}$ with $f^{\operatorname{AHA}}$ gives us an AHAT recognizing $L$.

Let $N$ be a sufficiently large integer depending on $n$, specified below. Each activation value $\hat{y}_{i}^{(k)}$ in $\hat{T}$ is $y_{i}^{(k)}$ from $T$ with two additional constant components, set to $1$ and $i/N$ by the input function. The attention function $\hat{f}_{k,h}^{\operatorname{att}}(\hat{y}_{i}^{(k-1)},\hat{y}_{j}^{(k-1)})$ computes $a_{i,j,k,h}$ using the original attention function and activation values, subtracting the value $j/N$. This is achievable with a bilinear map.

4 Prior Results for These Models

Hahn (2020) shows that the languages $1^{*}$ and $\{a^{n}b^{n}\mid n\geq 1\}$ are in GUHAT, and the languages PARITY and DYCK-$k$ for all $k\geq 1$ are not in GUHAT. Pérez et al. (2019) show that even without positional information, the language MAJORITY is in AHAT. Bhattamishra et al. (2020) show that SHUFFLE-$k$ is in AHAT, which implies that DYCK-$1$ is in AHAT. Yao et al. (2021) show that the language DYCK-$(k,D)$ is in UHAT. The latter two results use positional masking, but no other positional information.

PALINDROMES in GUHAT

Let us now illustrate how a GUHAT computes by way of example. In this section, we describe a GUHAT with $2$ layers and $1$ head that recognizes the language PALINDROMES over the alphabet $\Sigma=\{a,b,c\}$. Broadly speaking, this Transformer works as follows. The first layer is responsible for comparing each symbol of the input string with the corresponding symbol on the opposite side of the string, and marking whether the two symbols match. The second layer reads these markings, searching for a mismatch identified by the first layer. If one is found, the model output function returns ; otherwise, it returns $1$. For intuition, we simultaneously illustrate the Transformer’s computation on the input abcca\$, which should be rejected.

The input function is defined as $f(\sigma,i,n)=(\sigma,i,n)$ for each $\sigma\in\Sigma$ and $i\in[1..n]$. For our example input, the initial (layer ) 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.

We define the attention function for layer $1$, $f_{1,1}^{\operatorname{att}}((\sigma,i,n),(\sigma^{\prime},j,n))$, to be $\{(j=n-i)\vee(i=j=n)\}$. For each position $i<n$, this selects the activation at the correct corresponding position, $n-i$. For position $n$, it selects the activation at position $n$.

We define the activation function for layer $1$ as

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_{2,1}^{\operatorname{att}}((r,i),(s,j))=s$. This directs the attention at every position to the leftmost activation value $(s,j)$ from layer $1$ such that $s=1$. 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 $i\in[1..n-1]$ would have been marked with $(1,i)$ by layer $1$. In this case, the leftmost position with $s=1$ would have been the final position $n$, which has the activation value of $(1,n)$.

We define the layer $2$ activation function as $f_{2}^{\operatorname{act}}((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))=\{i=j\}$. With the input sequence abcca\$, the activation for position$6$at layer$2$is$(6,2)$and the output value is . For a valid palindrome such as$abcba\$$, the activation for position$6$at layer$2$is$(6,6)$and the output value is$1$. Generalizing this construction to an arbitrary alphabet$\Sigma$, we have the following.

For any finite alphabet $\Sigma$, the language PALINDROMES over $\Sigma$ 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.

A GUHAT with $K$ layers and $H$ heads is in informative normal form if and only if the following conditions are satisfied.

The input function is $f(\sigma,i,n)=(\sigma,i,n)$.

For each layer $k\in[1..K]$, the activation values are $(H+1)$-tuples of activation values at layer $k-1$, and the activation function is defined by

For each layer $k\in[1..K]$ and attention head $h\in[1..H]$, the attention function $f^{\operatorname{att}}_{k,h}$ returns an integer in $[0..N-1]$, where $N$ is the total number of possible ordered pairs of activation values at layer $k-1$.

For any Transformer $T\in\text{GUHAT}$, there exists a Transformer $\hat{T}\in\text{GUHAT}$ in informative normal form such that $L(T)=L(\hat{T})$. Moreover, $\hat{T}$ has the same number of layers and heads as $T$.

Let $T$ be a GUHAT with $K$ layers and $H$ heads, with input alphabet $\Sigma$, 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 $\hat{T}$ in GUHAT in informative normal form, which also has $K$ layers and $H$ heads. We assume that $n$ is the input length.

For $\hat{T}$ the input function $\hat{f}(\sigma,i,n)$ is defined to return the triple $(\sigma,i,n)$. Note that there are at most $|\Sigma|n$ possible initial activation values. We also define a function $t_{0}$ that translates initial activation values for $\hat{T}$ into initial activation values for $T$ by $t_{0}(\sigma,i,n)=f(\sigma,i,n)$.

Now, we induct on the layers of $T$ and $\hat{T}$. Assume that we have defined attention and activation functions for $\hat{T}$ for layers before $k$ (where the initial activation values are treated as “layer ”), and a translation function $t_{k-1}$ that translates all possible activation values for $\hat{T}$ from the previous layer into activation values for $T$ from the previous layer. To define the attention function for $\hat{T}$ for layer $k$ for head $h$, we enumerate all the possible pairs $\hat{y}_{i}$ and $\hat{y}_{j}$ of activation values of $\hat{T}$ at layer $k-1$, and determine the corresponding attention values of $T$, which we denote by $v_{k,h}(\hat{y}_{i},\hat{y}_{j})=f^{\operatorname{att}}_{k,h}(t_{k-1}(\hat{y}_{i}),t_{k-1}(\hat{y}_{j}))$. We make a list of all the distinct resulting values and sort them into increasing order. Then we define $\hat{f}^{att}_{k,h}(\hat{y}_{i},\hat{y}_{j})$ to be the rank of $v_{k,h}(\hat{y}_{i},\hat{y}_{j})$ in this sorted list. The activation function for $\hat{T}$ for layer $k$ is, by definition,

The translation function for layer $k$ is defined by

that is, we translate each of the component activation values using $t_{k-1}$ and then apply the activation function of $T$.

Finally, the output function for $\hat{T}$ is defined by $\hat{g}(\hat{y})=g(t_{K}(\hat{y}))$, that is, we translate the layer $K$ activation value $\hat{y}$ of $\hat{T}$ to the layer $K$ activation value of $T$, and apply the output function of $T$.

By construction, $\hat{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}(\hat{y})$ of the activation values $\hat{y}$ of $\hat{T}$ are equal to the corresponding activation values of $T$, and the outputs $\hat{T}(x)=T(x)$ are equal as well. Thus, $L(\hat{T})=L(T)$. ∎

To illustrate the construction of $\hat{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 x=abcca\$. Because the attention functions in that example return or$1$, their translation is simplified.

The initial activation values and layer $1$ attention function are the same as in the example. The resulting layer $1$ activation sequence, consisting of a sequence of paired initial activations and attention values, is

The translation $t_{1}$ maps $((x_{i},i,n),(x_{j},j,n))$ to $(0,i)$ if $x_{i}=x_{j}$ and $(1,i)$ if $x_{i}\neq x_{j}$. When applied to the above activation sequence, this yields the previous example’s layer $1$ activation sequence.

The layer $2$ translation function maps a layer $2$ activation value

to $(i,k)$. For layer $2$ and position $6$ the activation value for this input is

which is mapped to $(6,2)$ by $t_{2}$. The previous example’s output function compares $6$ and $2$ and returns , rejecting the input $x$.

From GUHAT to Circuits

In this section we show that for every language $L\in\text{GUHAT}$, we can construct a family of Boolean circuits of constant depth and polynomial size that also recognizes $L$. This will prove the following, which is our main result.

Every language in GUHAT is recognized by a family of circuits in AC0.

Let $L$ be a language over $\Sigma$ 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.

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$.

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.

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)$.

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$. ∎

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 $(d\log n)(n^{c}(c\log n)+n^{c}+c\log n)$.

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 next describe the circuit that implements the pooling function $f^{\operatorname{UHA}}$. For each pair $j,j^{\prime}\in[1..n]$, there is a circuit $D_{i,j,j^{\prime},k,h}$ whose inputs are the outputs of $A_{i,j,k,h}$ and $A_{i,j^{\prime},k,h}$ and whose output is a single wire $g_{i,j,j^{\prime},k,h}$ with a value of $1$ if $a_{i,j,k,h}\geq a_{i,j^{\prime},k,h}$ and 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.In fact, comparison of two $b$-bit integers can be done with a Boolean circuit of constant depth and size polynomial in $b$, but that is not necessary for the present purpose. 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^{\prime},k,h}$ for all $j^{\prime}\in[1..n]$. Let the output of this AND gate be denoted $m_{i,j,k,h}$. Then $m_{i,j,k,h}=1$ if and only if the position $j$ maximizes $a_{i,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 $\text{NOT}(m_{i,j^{\prime},k,h})$ for all $j^{\prime}<j$. Thus, $z_{i,j,k,h}=1$ if and only if $j$ is the leftmost position that maximizes $a_{i,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,h}=y_{j}^{(k-1)}$ such that $z_{i,j,k,h}=1$. In general, such a selection circuit takes as input $t$ selector bits $z_{1},\ldots,z_{t}$, where exactly one $z_{j}=1$, and $t$ input values $w_{1},\ldots,w_{t}$, where each $w_{r}$ consists of $S$ bits. It outputs $S$ bits representing the selected $w_{j}$ (for which $z_{j}=1$). Letting $w_{r,s}$ denote bit $s$ of $w_{r}$, the computation can be described as $v_{r,s}=w_{r,s}\wedge z_{r}$ for $r\in[1..t]$ and $s\in[1..S]$, which can be computed by one layer of $tS$ AND gates in parallel. Then the bits of the output are $u_{s}=\bigvee_{r=1}^{S}v_{r,s}$ for $s\in[1..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_{i}^{(k)}$ is just the sequence of wires representing $y_{i}^{(k-1)}$ 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_{n}^{(L)}$ 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.

Furst et al. (1984) prove that the PARITY, EQUALITY, and MAJORITY languages are not in AC0, which immediately implies the following.

GUHAT does not contain the languages PARITY, MAJORITY, or EQUALITY.

To see that the DYCK-$k$ languages are also not in AC0, we reduce from the EQUALITY language.

For all $k\geq 1$, the language DYCK-$k$ is not in AC0, and is therefore not in GUHAT.

It suffices to prove this for $k=1$. Assume that there is a family $\{C_{n}\}$ of Boolean circuits in AC0 that recognizes DYCK-$1$. We may assume that the binary symbol encoding is $h([)=0$ and $h(])=1$. We show how to use this to construct a family $\{E_{n}\}$ of Boolean circuits in AC0 that recognizes the EQUALITY language, a contradiction.

$E_{n}$ is constructed from $C_{3n}$ as follows. If the inputs to $E_{n}$ are $x_{1},\ldots,x_{n}$, then $E_{n}$ consists of $C_{3n}$ with its first $n$ inputs set to the constant , its middle $n$ inputs set to $x_{1},\ldots,x_{n}$, and its last $n$ inputs set to the constant $1$.

Let $x$ be any element of $\{0,1\}^{n}$. If the number of occurrences of is not equal to the number of occurrences of $1$ in $x$, then the input to $C_{3n}$ has unequal numbers of $[$ and $]$ symbols, which is not in DYCK-$1$ and $x$ is rejected. If the number of occurrences of is equal to the number of occurrences of $1$ in $x$, then in any prefix of the input to $C_{3n}$, the number of occurrences of $]$ is less than or equal to the number of occurrences of $[$. At the end of the input, the number of occurrences of $[$ is equal to the number of occurrences of $]$, so the input to $C_{3n}$ is in DYCK-$1$ and $x$ is accepted. Thus $\{E_{n}\}$ is a family of Boolean circuits in AC0 that recognizes the language EQUALITY, a contradiction. ∎

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 AC0. 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 Pérez et al. (2019) showing that the language MAJORITY is in AHAT, or Bhattamishra et al. (2020) 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\theta_{i},\sin\theta_{i})$ where $\theta_{i}=\pi i/2n$), 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? Yao et al. (2021, Theorem B.3) present a construction for a soft attention Transformer that recognizes DYCK-$k$. This construction crucially employs 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 employed 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.

Acknowledgements

We thank the reviewers and the action editor for their work in reviewing this paper.

References