The Parallelism Tradeoff: Limitations of Log-Precision Transformers

Introduction

This work aims to characterize the computational model implicit in transformer neural networks (Vaswani et al., 2017), which form the basis of recent breakthroughs in large language models such as BERT Devlin et al. (2019), T5 Raffel et al. (2020), and GPT-3 Brown et al. (2020). What computational primitives can the transformer’s components implement, and what problems can the full system solve in aggregate? These questions are important for interpreting transformers in a principled way, understanding potential limitations of their reasoning capabilities, and building trust in deployed transformer-based systems.

Early theoretical work on transformers established their Turing completeness, albeit with assumptions like infinite precision and arbitrarily powerful feedforward subnets (Pérez et al., 2019; Dehghani et al., 2019). On the other hand, a strand of more recent work uses techniques from circuit complexity theory to derive strong limitations on the types of problems transformers can solve given restrictions on the form of attention allowed in the transformer. Specifically, Hahn (2020) and Hao et al. (2022) showed transformers restricted to hard attention are very limited: they can only solve problems in a weak complexity class (non-uniform $\mathsf{AC}^{0}$) that doesn’t even contain basic problems like majority of $n$ bits. Merrill et al. (2022) extended this to a more general class of “saturated attention” transformers with a floating point datatype, and showed a larger class of problems (non-uniform $\mathsf{TC}^{0}$) as an upper bound. This motivates analyzing a setting that strikes a middle ground: Can we characterize transformers whose precision and feedforward nets’ computational power are realistically bounded, but where attention is also realistically expressive?

An important practical limitation of these prior results is the “non-uniform” nature of the considered circuit classes, which makes these classes non-realizable and the findings difficult to interpret. This is because non-uniform $\mathsf{AC}^{0}$ and $\mathsf{TC}^{0}$, while highly limited in computation, also contain some problems that are not even decidable, i.e., for which there doesn’t exist any exact algorithm. Thus, non-uniform classes cannot be directly compared with standard algorithmic complexity classes such as $\mathsf{P}$, $\mathsf{NP}$, etc. This motivates our second key question: Can we derive uniform upper bounds on transformers?

Our main contribution is proving that log-precision transformers can be simulated by uniform constant-depth threshold circuits. Thus, such transformers can only solve problems in uniform $\mathsf{TC}^{0}$. This characterization is strikingly weak compared to the Turing-completeness of infinite-precision transformers. Since we believe log precision is more realistic for practical transformers than infinite precision, these results point to the conclusion that transformers are not Turing-complete in practice.

In contrast to past results, our upper bound on transformers is a uniform circuit class, enabling direct comparison of log-precision transformers to many natural complexity classes. These connections reveal specific problems that define the upper limits of log-precision transformers’ capabilities, as discussed further in § 2.

Intuitively, our upper bound says that log-precision transformers are computationally shallow, and that this shallowness can be understood to emerge from their parallelizability. Transformers’ inherent parallelism is useful for training them efficiently at massive scale, but may limit the complexity of the computations they can express. We introduce the term parallelism tradeoff to capture this idea, which represents a potential fundamental weakness of the current paradigm of scaling language models. Formally characterizing reasoning capabilities relevant to language models and understanding whether they likely fall outside upper bounds implied by the tradeoff would clarify the practical implications of this limitation of scaling.

It could also be that the limitations of parallelism are not a curse but a blessing, if they constrain the hypothesis space in a way useful for learning. We have no evidence that this is true, but mention it as an alternate interpretation of the results that could be clarified in future work.

Instruction Following and Advice Transformers.

We also consider an instruction following setting (Brown et al., 2020) where the transformer is provided the description of a task along with an input on which to execute the instruction. We construct a practically parameterizable transformer that can execute instructions perfectly if they are provided in the form of $\mathsf{TC}^{0}$ circuits. This complements recent work that studies transformers’ ability to follow other forms of instructions such as regular expressions (Finlayson et al., 2022).

Based on the fundamental property that transformers can correctly evaluate any given $\mathsf{TC}^{0}$ circuit on a given input, we introduce the notion of advice transformers akin to advice taking Turing machines. We show that transformers can recognize any (non-uniform) $\mathsf{TC}^{0}$ language if provided appropriate poly-size advice.

In summary, our findings provide new insights on both the abilities and the limitations of transformers, and bring out bounded precision, threshold computations, and parallelism as key notions for understanding the implicit computational model of transformers in practice.

Roadmap.

Before diving into technical details, we discuss in § 2 the implications of our results on both fundamental as well as practical abilities of transformers. § 3 provides a brief primer on circuits as a model of computation. It then discusses a way of serializing a circuit into a string; we later show how to generate such serializations using a resource-bounded algorithm, which is the key to proving containment of transformers in uniform circuit classes. § 4 defines our formal model of bounded-precision transformers. § 5 derives our first formal bound on log-precision transformers. This bound involves non-uniform circuit families, similar in spirit to prior results in this area. § 6 proves our more technical main result: the first uniform circuit complexity upper bound for transformers (specifically, uniform $\mathsf{TC}^{0}$). Finally, § 7 provides a lower bound on transformers, introduces the notion of an Advice Transformer, and connects these to the machine learning problems of Instruction Learning and Following.

Implications of Our Findings

Before diving into technical details, we discuss the general implications of our findings on the abilities and limitations of transformers. We will focus here on our main result (Thm. 2), which shows that log-precision transformers are in the complexity class logspace-uniform $\mathsf{TC}^{0}$.

One interpretation of complexity classes such as $\mathsf{NC}^{0}$, $\mathsf{AC}^{0}$, and $\mathsf{TC}^{0}$ is sets of poly-time solvable problems that are parallelizable to a very high degree—they can be solved in parallel in constant time with enough parallel processors. This gives some intuitive explanation of our result: log-precision transformers end up in $\mathsf{TC}^{0}$ because they were designed to be highly parallelizable. Since parallelism is an important property of today’s dominant paradigm of training models at massive scale, this points to the conclusion that any massively scaled up model—transformer or otherwise—will likely obey restrictions similar to the ones derived here for log-precision transformers. There is thus an important tradeoff between the massive parallelizability of today’s networks and their representation power.

What Transformers Can/Cannot Compute.

Our result places log-precision transformers in the complexity class logspace-uniform $\mathsf{TC}^{0}$. This has immediate implications on the kinds of problems such transformers can and cannot accurately solve.

Consider any problem $X$ that is complete for a complexity class $\mathsf{C}$ that contains logspace-uniform $\mathsf{TC}^{0}$. By definition of completeness, every problem log-precision transformers can solve perfectly is efficiently reducible to $X$ and is thus no harder than $X$. This implies that—despite their massive size—the computation performed by such transformers is, for instance, no harder than solving basic $\mathsf{L}$-complete problems like graph connectivity: the problem of checking whether there is a path between two nodes in an undirected graph (Lewis and Papadimitriou, 1982; Reingold, 2008).

By the same token, if $\mathsf{C}$ is strictly larger than logspace-uniform $\mathsf{TC}^{0}$, then such transformers cannot perfectly solve $X$. Thus, log-precision transformers cannot perfectly solve the following reasoning problems:

Linear equalities: find $\mathbf{x}$ s.t. $\mathbf{A}\mathbf{x}=\mathbf{b}$Assuming logspace-uniform $\mathsf{TC}^{0}\neq$ $\mathsf{P}$. Follows because these problems are $\mathsf{P}$-complete Greenlaw et al. (1991).

Universal context-free recognition${}^{\ref{footnote:neqP},}$Takes both a grammar and a string as input and return whether the grammar generates the string. Jones and Laaser (1976) demonstrate $\mathsf{P}$-completeness.

Propositional satisfiability (SAT)Assuming logspace-uniform $\mathsf{TC}^{0}\neq$ $\mathsf{NP}$. Follows because SAT is $\mathsf{NP}$-complete (cf. Biere et al., 2009).

Horn-clause satisfiability (HORN-SAT)${}^{\ref{footnote:neqP}}$

Permanent computationAssuming logspace-uniform $\mathsf{TC}^{0}\neq$ $\mathsf{\#P}$. Follows because permanent is $\mathsf{\#P}$-complete (Valiant, 1979). Allender (1999) shows permanent is not in logtime-uniform $\mathsf{TC}^{0}$.

This highlights the limits of practical transformers with limited-precision arithmetic, indicating that they are far from being universal or all-powerful as suggested by some prior studies.

One important caveat about these negative results is that they are asymptotic in nature—they apply for “large enough” input size $n$. It’s possible for log-precision transformers to solve such problems easily when $n$ is small. Further, these negative results are about exact solutions, but they often also extend beyond this when formal hardness-of-approximation results are known.

Limitations of Our Formal Model.

Our formal model is based on a binary classification view of transformers. However, our results apply directly to multi-class classification as well and can be extended to generation problems by viewing, for instance, next word prediction in NLP as a multi-class classification problem. However, if the transformer decoder is allowed to condition on its previous output in a generation problem, then this would violate our formal setup.

1 Potential Applications

Elhage et al. (2021) propose extracting circuitsTheir sense of “circuit” is not exactly the formal sense we use in this paper, though the goal of capturing transformers’ implicit computational mechanism is the same. that capture the computational structure of transformers. Our results suggest threshold circuit families are a good formalism for expressing mechanisms extracted from transformers. Constructively converting transformers to threshold circuits is beyond the scope of the current paper, although we hope to explore this in more detail in future work.

Testing Separation Candidates in Complexity Theory.

Thm. 2 also motivates a paradigm for quickly testing complexity theory conjectures. If a problem is believed to separate $\mathsf{TC}^{0}$ and $\mathsf{NC}^{1}$, a transformer can be trained on problem instances. If the transformer generalizes perfectly to harder instances than it was trained on, this gives an empirical hint that the problem is in $\mathsf{TC}^{0}$, providing evidence against the conjecture.

Circuit Computation

Let $\{0,1\}^{*}$ be the set of finite binary strings. For $x\in\{0,1\}^{*}$, let $\left\lvert x\right\rvert$ be its length. We refer to a function from $\{0,1\}^{*}$ to $\{0,1\}^{*}$ as a boolean function. Boolean functions can implement arithmetic operations if we define a semantics for binary strings as numbers. We will treat the intermediate values in a transformer as binary strings, and the internal operations as boolean functions.

Circuits are a model of computation for computing boolean functions of fixed-length binary strings.For a mini-tutorial on circuit complexity theory and its relevance to transformers, see Merrill et al. (2022). Formally, a circuit is a directed acyclic computation graph. The leaf nodes represent binary variables and their negations. The internal nodes represent functions in some set $\mathcal{G}$, and the directed edges represent the flow of function outputs into inputs of other functions. One or more nodes in the circuit are marked such that their value is the output of the circuit.

For a set of functions $\mathcal{G}$, a $\mathcal{G}$-circuit is a directed acyclic computation graph where the internal nodes have labels from $\mathcal{G}$.

The size of a circuit is the total number of gates in it, including negation. The depth of a circuit is the length of the longest path from any input node to any output node.

Circuit Families.

A circuit family $C_{n}$ recognizes $L\subseteq\{0,1\}^{*}$ if, for all $x\in\{0,1\}^{*}$, $C_{\left\lvert x\right\rvert}(x)=1$ if and only if $x\in L$.

We now define classes of languages by constraining the complexity of the circuit families needed to recognize them:

Let non-uniform $\mathsf{AC}^{0}$ be the set of $L\subseteq\{0,1\}^{*}$ such that $L$ is recognizable by a poly-size, constant-depth $\{\neg,\wedge,\vee\}$-circuit family.

The gates $\neg$, $\wedge$, and $\vee$ are all just special cases of thresholds, so we can imagine $\mathsf{TC}^{0}$ circuits to have access to these as well. Thus, $\mathsf{TC}^{0}$ circuits can implement $\mathsf{AC}^{0}$ circuits.

Circuit Serialization.

We identify a circuit with its serialization in a formal language that identifies each node’s label and adjacency list. We will adopt a specific grammar for concreteness, but our construction can be adapted to other string representations of circuits.

We define a circuit serialization as a traversal of a circuit ordered by some topological sort. In this serialization, leaf nodes (variables) are represented by the string X. An internal node (gate) is represented in Polish notation by the function it computes (AND, OR, or NOT) followed by a list of pointers to its arguments. Each argument $\texttt{\&1}^{j}$ of gate $i$ encodes (in a unary) a zero-indexed pointer to the $j$-th gate in the circuit, where $j<i$. The final node is interpreted as the circuit output.

By convention (cf. § 3), negations in $\mathsf{AC}^{0}$ circuits are usually taken to occur at the beginning of the circuit, rather than after $\wedge$ or $\vee$ nodes.We can apply De Morgan’s laws to force any $\mathsf{AC}^{0}$ circuit to have this property. Our serialization grammar does not enforce this property, but of course any circuit with this property can be serialized by our grammar.

It is a bit more complicated to serialize threshold circuits. Formally, a threshold circuit serialization is generated by the following grammar:

We say a threshold circuit serialization is in prefix form if all inputs (X) come before all threshold gates (<= or >=), as is the case in this example.

Uniformity.

The circuit families we have defined above are non-uniform, meaning that we do not enforce that the circuits processing different input sizes must be related in any way. In degenerate cases, non-uniform circuit families can solve undecidable problemsConsider the unary language $1^{n}$ such that Turing machine $n$ (under some arbitrary enumeration) halts. This problem is in non-uniform $\mathsf{AC}^{0}$ since we can hard-code the right answer for each $n$ in $C_{n}$. because they have infinite description length, making them a physically unrealizable model of computation. Complexity theorists have thus introduced uniform circuit families. Uniform circuit families are a realizable model of computation with relations to classes in computational complexity and formal language theory.

Intuitively, in a uniform circuit family, the circuits for different input sizes must be “somewhat similar” to each other. We formalize this (cf. Arora and Barak, 2009) by saying that there exists a resource-constrained Turing machine that maps the input $1^{n}$ to a serialization of circuit $C_{n}$.

A language $L$ is $(S(n),I(n))$-space uniformly computable by a circuit model $M$ iff there exists a Turing machine that, for all $n\geq 0$, uses $S(n)$ space to map $1^{n}$ to an $M$-circuit recognizing $L$ on inputs of size $I(n)$.

This notion of uniformity is more general than the standard notion in that the input size $I(n)$ is a function of the problem complexity $n$. The reason for this is that we will apply uniformity to subcomputations with different input sizes $I(n)$ within a larger computation of input size $n$. The standard notion of uniformity corresponds to $I(n)=n$.

Bounded-Precision Transformers

A transformer (Vaswani et al., 2017) is a neural network architecture made up of a constant number of transformer layers. A transformer layer is a module that computes self-attention over a sequence followed by an elementwise transformation of the output vectors.

We will assume that each transformer is resource bounded in terms of the precision of each value it computes and, for some of our results, the space it uses for the computation of key operations such as embedding, attention, and activation. Specifically, we will assume precision $p$, i.e., the values at all layers, as well as the outputs of all key intermediate operations in it (attention, activation, arithmetic operators, etc.), are represented using $p$ bits. This is a realistic assumption as, in practice, today’s transformers are typically limited to the 64-bit precision of the underlying hardware. Formally, we define $p$-precision as follows:

A $k$-ary function $f:x_{1},\ldots,x_{k}\mapsto y$ is $p$-precision if $x_{1},\ldots,x_{k},y\in\{0,1\}^{*}$ have size at most $p$ bits, and $f$ can be computed by a $p$-space-bounded Turing machine.

This says the size of the function input and output are bounded below $p$. Similarly, the intermediate space used by the computation must also be bounded below $p$. Thus, higher precision computations cannot somehow be hidden inside $f$.

Def. 6 naturally applies to functions with bounded arity $k$. We will also need to define $p$ precision for the summation operator in the transformer, which adds $n$ different floats of size $p$.Our proof also goes through if the transformer weights are integers, as is sometimes done (Dettmers et al., 2022). Adding $n$ floats can blow up the precision needed to represent their sum. For example, imagine adding the floating points $1\cdot 2^{0}+1\cdot 2^{c}$. We obtain $(2^{c}+1)\cdot 2^{0}$, whose mantissa takes $c+1$ bits to represent. In practice, computers do not preserve full precision in such situations: instead, small terms like $1\cdot 2^{0}$ are discarded. Thus, we define the transformer’s addition operation $\oplus$ to be similarly approximate (and thus preserve precision); see § A.

2 Transformer Definition

3 Attention Heads

The core building block of a transformer is an attention head. We define this at a high level of abstraction as follows:

A $p$-precision attention head is specified by a binary $p$-precision similarity function $s:\{0,1\}^{p}\times\{0,1\}^{p}\to\{0,1\}^{p}$.

Let $\mathbf{h}_{1},\ldots,\mathbf{h}_{n}\in\{0,1\}^{p}$ be the input sequence to a $p$-precision attention head, and let $\oplus$ be approximate floating-point addition (§ A).

4 Transformer Layers

A $p$-precision transformer layer is then a tuple of heads and a function $f$ used to combine them.

5 Transformer Encoder

Finally, we define a transformer of depth $d$ as a cascade of $d$ transformer layers:

For a position embedding function $\phi$ and $w\in\Sigma^{n}$, let $\phi(w)$ be the position-wise broadcasted embedding of $w$: for $1\leq i\leq n$, $\phi_{i}(w)\triangleq\phi(w_{i},i)$.

A transformer $\left(\phi,\langle L^{1},\cdots L^{d}\rangle\right)$ computes the following function of a string $w\in\Sigma^{*}$:

We will use $n$ to denote the length of $w$, and take the transformer’s depth $d$ to be fixed w.r.t. $n$.

Log-Precision Transformers as Non-Uniform Threshold Circuits

We first show that log-precision transformers can be simulated by non-uniform threshold circuits, before presenting the more technical uniform version of the results in §6. The initial non-uniform result extends the findings of Merrill et al. (2022), who showed that saturated attention transformersSaturated attention is uniform attention over a subset of the prior layer nodes. can be simulated in $\mathsf{TC}^{0}$. Here, we remove the simplifying saturated attention assumption and other restrictions on the underlying datatype. Instead, we show that our log-precision assumption is enough to prove that a transformer can be simulated in $\mathsf{TC}^{0}$ with any attention function.

Like Hao et al. (2022), we construct a circuit using a DNF representation of $f$ on inputs of size $c\log n$, except we use a combined DNF representation for all output bits of $f$. The DNF formula has at most $2^{c\log n}=n^{c}$ terms. The circuit has a NOT gate for each input bit, an AND gate for each DNF term, and, for each of the $m$ output bits, an OR gate combining the outputs of those AND gates (i.e., DNF terms) for which that bit is $1$. ∎

We now use Lem. 1 to prove the following non-uniform result. We note that the proof goes through even if the notion of $p$-precision (Def. 6) is relaxed to not require computability in space $p$. This requirement will, however, become important for our subsequent result in § 6.

Any $c\log n$-precision depth-$d$ transformer operating on inputs in $\Sigma^{n}$ can be simulated by a threshold circuit family of depth $3+(9+2d_{\oplus})d$.

Let $w\in\Sigma^{n}$ be the input of a $c\log n$-precision transformer. We show by induction that we can construct a composition of constant-depth, poly-size threshold circuits to compute each layer of this transformer. Thus, any constant-depth transformer will be computable by a constant-depth threshold circuit.

In the base case of layer and token $i$, we construct gates representing the constant $i$ encoded in binary. We can then compute $\mathbf{h}_{i}^{0}=\phi(w_{i},i)$ using Lem. 1, yielding a poly-size depth-3 circuit.

Aggregating the circuit over all $d$ layers, the overall circuit depth is $3+(9+2d_{\oplus})d$. ∎

Any log-precision transformer can be simulated by a non-uniform $\mathsf{TC}^{0}$ circuit family.Here, a $\mathsf{TC}^{0}$ circuit family is a constant-depth, poly-size circuit family computing some function $\{0,1\}^{*}\to\{0,1\}^{*}$. While we define $\mathsf{TC}^{0}$ for decision problems in Def. 4, it is standard and well-defined to extend the same term to refer to circuit families computing functions as well (Hesse, 2001).

Log-Precision Transformers as Uniform Threshold Circuits

We first extend Lem. 1 to respect uniformity:

We give the proof in the form of an algorithm to construct a circuit as a function of $n$ and then justify its correctness and space complexity.

Algorithm. We first print $2c\log n$ nodes representing unnegated and negated input nodes.We ignore the initial unnegated input nodes when considering the size of the circuit.

Now, we need to show how to construct nodes corresponding to $n^{c}$ DNF terms. To this end, we loop over all possible inputs $x\in\{0,1\}^{c\log n}$ by maintaining the $c\log n$ bit binary representation of $x$ (initialized with $0^{c\log n}$) and incrementing it by $1$ at each step of the loop. We create a new $\wedge$ node $i$ with $c\log n$ arguments, defined as follows. For $j\in[c\log n]$, we create an argument pointer to (unnegated) node $j$ if $x_{j}=1$ and to (negated) node $c\log n+j$ otherwise.

Correctness. We show that this Turing machine maps input $n$ to a serialized circuit computing $f$ on inputs of size $n$. The first layer simply produces unnegated and negated input values. The second layer then produce all possible DNF terms. Finally, node $k$ of the third layer computes the disjunction over all terms $x$ such that $f_{k}(x)=1$. Thus, node $k$ of the third layer computes $f_{k}$.

Thus, $M$ uses $c\log n+\log m$ space to map $1^{n}$ to a circuit of size at most $n^{c}+c\log n+m$ and depth $3$ that computes $f$ on size $c\log n$ inputs. ∎

We can leverage this lemma to derive the uniform analog of Thm. 1, as follows.

Any $c\log n$-precision depth-$d$ transformer operating on inputs in $\Sigma^{n}$ can be simulated by a logspace-uniform threshold circuit family of depth $3+(9+2d_{\oplus})d$.

In the base case, we use log space to track a counter maintaining the current token $i$ (between $1$ and $n$) throughout the circuit construction. We construct gates encoding the constant $i$ in binary. We can then apply Lem. 2 to construct a Turing machine that maps $1^{n}$ to a constant-depth threshold circuit computing $\mathbf{h}^{0}_{i}=\phi(w_{i},i)$.

Because the depth derived in Thm. 2 is constant with respect to $n$, it follows that:

Any log-precision transformer can be simulated by a uniform $\mathsf{TC}^{0}$ circuit family.

Lower Bounds for Instruction Following and Advice Transformers

So far, we have shown that uniform $\mathsf{TC}^{0}$ is an upper bound for log-precision transformers. Is this upper bound tight, i.e., also a lower bound? While we do not answer this question here, we address a related question as a first step: we construct a transformer that can evaluate $\mathsf{TC}^{0}$ circuits on binary inputs, showing that transformers can compute any $\mathsf{TC}^{0}$ function when their input is augmented with the right “instructions”.

More formally, we consider the Circuit Value Problem (CVP) (Ladner, 1975), also referred to as the Circuit Evaluation Problem, where the input is a boolean circuit $C$ and a string $x\in\{0,1\}^{n}$, and the task is to return the value of $C(x)\in\{0,1\}$. This problem is known to be complete for the class $\mathsf{P}$ under $\mathsf{AC}^{0}$ reductions (Ladner, 1975). We will assume $C$ is serialized as described in § 3 and prove that log-precision transformers can evaluate any $\mathsf{TC}^{0}$ circuit. Note that this is an extension of the typical CVP since the circuit has threshold gates, not just standard AND/OR gates.

It is known that LSTMs cannot evaluate boolean formulae (Merrill, 2020), a special case of the CVP. In contrast, we show that transformers can.

To demonstrate the practicality of our lower bound construction, we will not just prove the existence of transformers that can evaluate $\mathsf{TC}^{0}$ circuits but also specify concrete choices for the positional embedding scheme and the class of attention functions that are sufficient to do so.

Saturated Attention.

After normalization, saturated attention creates a distribution that is uniform over a subset of positions. Thus, it is capable of parameterizing hard attention, uniform attention over the full sequence, and various attention patterns in between.

Simple Pooling Functions.

For simplicity, we assume pooling functions $f$ are thresholded linear functions of their inputs. Thus, they could be implemented by a feedforward neural net. Without loss of generality, we let attention heads have a value function, which can be folded into the pooling function from the last layer (see § 4).

Terminology.

We are now ready to present the main result. Our construction below is specific to circuits serialized in prefix form (see §3), but it can be extended to other serializations as well.

For all $d$, there exists a transformer with fractional positional embeddings, saturated attention, thresholded linear pooling functions, and depth $2d$ that, for any threshold circuit $C$ of depth $d$ serialized in prefix form, maps input $\langle C,x\rangle$ to the value $C(x)$.

Base Case: Input Nodes. We use an attention layer to attend uniformly over all positions with value returns $1$ if $w_{i}=\texttt{X}$ and otherwise. This head computes $\#(\texttt{X})/n$, where $\#(\texttt{X})$ is the number of occurrences of X in $w$. A second layer, then, at input node $i$, computes the positional embedding of the token representing input value $x_{i}$:

We attend to this position to retrieve $x_{i}$. After these layers, each input node $i$ stores its value $x_{i}$.

We also use the base-case layers to construct an attention head that, at the $i$-th node, counts the fraction of tokens (out of $n$) that are nodes to the left of the current node. Thus, the column corresponding to node $i$ stores the value $i/n$.

At each gate node $i$, we use two more attention heads to find the index of the next & to the right and then count the fraction of tokens before it that are 1. This head thus computes $k_{i}/m_{i}$ where $k_{i}$ is the threshold value of gate $i$ and $m_{i}$ is its arity.

Finally, using the first attention layer, we have each 1 node attend to the first argument symbol & to its left and retrieve its index $p/n$. Then, in the second attention layer, each argument attends uniformly over all nodes with values $p/n$. The net effect is for each argument to store $j/n$, i.e., the pointer it is encoding in unary as &1j.

In the first attention layer, each argument token attends to the closest gate node $i$ to its left, which is the gate it belongs to. Recall from the base case that argument token & already stores $j/n$, where $j$ is the pointer value it encodes. Each argument token now attends with query $j/n$ to retrieve from node $j$ its already computed value.

The second attention layer applies at gate nodes, not arguments. At gate $i$ of arity $m_{i}$, we set the attention $s(i,j)$ to indicate whether argument $j$ belongs to gate node $i$, which holds for exactly $m_{i}$ arguments. We set the attention value at argument $j$ to be the binary value of node $j$, which was retrieved in the previous paragraph. Thus, the attention head computes $c_{i}/m_{i}$, where $c_{i}$ is the number of arguments of node $i$ that are $1$. We repeat this for all gate nodes.

Depth-$2d$ transformers can solve CVP for depth-$d$ $\mathsf{TC}^{0}$ circuits.

1 Instruction Following

CVP is closely related to instruction learning (Brown et al., 2020) and instruction following tasks (Finlayson et al., 2022). The latter task setup provides a transformer two inputs: a regular expression $r$ as an “instruction”, and $z\in\{0,1\}^{*}$. The goal of the task is to return whether $z$ belongs to the regular language represented by $r$. Viewed from this lens, the circuit evaluation setup asks: Can transformers follow instructions provided in the form of a circuit? As discussed below, our result says the answer is yes for all constant depth threshold circuits. This, to the best of our knowledge, provides the first non-trivial lower bound for transformers in the instruction learning setting.

Formally, an instruction $I$ is any descriptionFormally, a function description is a fixed-size program to compute that function under some model of computation. of a function $f_{I}$ of $\{0,1\}^{*}$. We say a transformer correctly follows an instruction $I$ if, for all $x\in\{0,1\}^{*}$, it correctly computes $f_{I}(x)$ on input $\langle I,x\rangle$. A non-uniform instruction description is a family of length-specific descriptions $\{I_{n}\}_{n=1}^{\infty}$. We say a transformer correctly follows a non-uniform instruction family $\{I_{n}\}$ if, for all $n$ and all $x\in\{0,1\}^{n}$, it correctly computes $f_{I}(x)$ on input $\langle I_{n},x\rangle$. The non-uniform description $\{I_{n}\}$ may take any form. When it forms a $\mathsf{TC}^{0}$ circuit family, we refer to it as a $\mathsf{TC}^{0}$ instruction description. Since Thm. 3 constructs a transformer that can evaluate any $\mathsf{TC}^{0}$ circuit, it follows that:

There exists a depth-$2d$ transformer that can correctly follow any depth-$d$ $\mathsf{TC}^{0}$ instruction description.

Thus, transformers with simple position embeddings, attention, and pooling functions can simulate any instruction provided in the form of a $\mathsf{TC}^{0}$ circuit. We note that while it is unknown whether the class of regular languages, considered by Finlayson et al. (2022), is contained in $\mathsf{TC}^{0}$, the other side is known: there are problems computable by $\mathsf{TC}^{0}$ circuits that are not computable by a regular language. These include problems involving counting and arithmetic, which are beyond regular languages. Our results thus expand the known kinds of instructions transformers are able to follow, at least with hand-constructed weights.

2 Advice Transformers

We can also view circuit evaluation abilities of transformers (Lem. 3) from the lens of advice taking Turing machines which, in addition to their usual input, are also provided an input length dependent (but input independent) advice string. For instance, $\mathsf{P}/\mathsf{poly}$ is the class of problems decidable in polynomial time when the Turing machine is given an advice string of size polynomial in the input length (cf. Arora and Barak, 2009).

Non-uniform $\mathsf{TC}^{0}\subseteq\mathsf{T}/\mathsf{poly}$ .

Since non-uniform $\mathsf{TC}^{0}$ even contains some undecidable languages (Arora and Barak, 2009, Claim 6.8), $\mathsf{T}/\mathsf{poly}$ is clearly a very powerful class and a strict superset of $\mathsf{T}$, the class of decision problems recognized by transformers (which are all decidable). Thus, a problem in $\mathsf{T}/\mathsf{poly}$ cannot always be solved by a transformer on its own. However, if given a description of how to do so (“advice”) in the form of a $\mathsf{TC}^{0}$ circuit, our result shows that a transformer could solve that problem.

Conclusion

Answering two open questions from Merrill et al. (2022), we prove log-precision transformers with any (including soft) attention can be simulated by uniform constant-depth threshold circuits. This establishes thresholded addition as a fundamental operation for understanding the computational model of transformers: any log-precision transformer can be re-expressed as a polynomial number of threshold gates stacked to a constant depth. This result also establishes potential limits on the computational power of log-precision transformers; e.g., if $\mathsf{L}\subset\mathsf{P}$, transformers cannot compute all poly-time functions. They are certainly very far from being universal. The intuition at the heart of this result is that forcing a model to be highly parallelizable likely sacrifices its expressiveness. Since parallelism seems essential to pretraining any massive model at scale, any large language model—transformer or otherwise—may suffer from a similar tradeoff.

Acknowledgments

The authors are grateful for the valuable feedback from the anonymous reviewers and the TACL action editor Dan Gildea. They also thank Paul Beame and colleagues at AI2 including Kyle Richardson, Michal Guerquin, Peter Clark, Tushar Khot, and especially Matthew Finlayson, whose empirical findings about instruction learning inspired § 7. Feedback from Sam Bowman, Arya McCarthy, Roma Patel, and Lena Strobl, and discussions with the FLaNN, ML for Code (MILA), and Foundations of Language Processing (Umeå) research groups helped improve earlier drafts. The authors also appreciate Rahul Santhanam’s feedback. This work was funded in part by NSF award 1922658. William Merrill was supported by an NSF graduate research fellowship and by AI2.

References

Appendix A Iterated p𝑝p-Precision Float Addition

We interpret a $p$-bit string $x$ as a $p$-precision float by taking the first $p/2$ bitsWe assume w.l.o.g. that $p$ is even. of $x$ as a signed integer $m$ encoding the mantissa and the remaining $p/2$ bits of $x$ as another signed integer $e$ encoding the exponent. A float with mantissa $m$ and exponent $e$, denoted $\langle m,e\rangle$, encodes $m\cdot 2^{e}$.

We define float addition by mapping the floats to integers, adding the integers exactly, and then mapping the sum back to a float (with possible loss of precision). Let $I^{\max}_{q}=2^{q}-1$ be the greatest $q$-bit signed integer, and $I^{\min}_{q}=-I^{\max}_{q}$. Let $F_{p}^{\max}$ be the greatest value representable by a $p$-precision float. Since the exponent of a float $\phi$ can be negative and represent a fraction, we rescale $\phi$ by $2^{-I^{\min}_{p/2}}$ when mapping it to an integer $g_{p}(\phi)$:

The integer mapping of a $p$-bit float $\phi=\langle m,e\rangle$ is defined as $g_{p}(\phi)=m\cdot 2^{e-I^{\min}_{p/2}}$.

when $e\leq I^{\max}_{p/2}$; otherwise (i.e., when $z>F_{p}^{\max}$), we set $m=e=I_{p/2}^{\max}$ to properly handle overflow.

We define the sum of $k$ $p$-precision floats as

We first verify that Def. 14 closely approximates exact addition.

Let $\phi=\langle e,m\rangle$ be a float such that $\left\lvert\phi\right\rvert\leq F_{p}^{\max}$ and $e\geq I_{p/2}^{\min}$. Then $\phi$ and $f_{p}(g_{p}(\phi))$ differ by a factor of at most $1\pm 2^{-p/2+2}$.

Let $z=g_{p}(\phi)$, which is well-defined because of the precondition $e\geq I^{\min}_{p/2}$ of the lemma. Let $\phi^{\prime}=\langle m^{\prime},e^{\prime}\rangle=f_{p}(z)$.

Recall that the value of $\phi$ is $g_{p}(\phi)\cdot 2^{-I^{\min}_{p/2}}=z\cdot 2^{-I^{\min}_{p/2}}$. By the above argument, we also have that the value of $\phi^{\prime}$ is within $(z\pm\delta)\cdot 2^{-I^{\min}_{p/2}}$, which is within $z\cdot(1\pm 2^{-p/2+2})\cdot 2^{-I^{\min}_{p/2}}$. Thus, $\phi$ and $\phi^{\prime}$ are within a factor of $1\pm 2^{-p/2+2}$ of each other. ∎

Finally, we show that, with log precision, computing $\oplus$ (Def. 14) is in uniform $\mathsf{TC}^{0}$.