The Parallelism Tradeoff: Limitations of Log-Precision 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.

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.

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.

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.

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}$¹¹1Assuming 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},}$²²2Takes 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)³³3Assuming 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}}$

• •

  AI planning Bylander (1991)

• •

  Permanent computation⁴⁴4Assuming 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.

Prior formal characterizations of transformers either make unrealistically strong assumptions Pérez et al. (2019); Dehghani et al. (2019) or place unrealistic restrictions Hahn (2020); Hao et al. (2022); Merrill et al. (2022). In contrast, we make only one assumption—namely, all intermediate values in the transformer are limited to $\mathrm{O}(\log n)$ bits, where $n$ is the number of input tokens. We next discuss some implications of this assumption and what our findings mean for practical transformers.

As mentioned above, our bounds are asymptotic in nature and thus apply when $n$ is sufficiently large. In practice, transformers use fixed precision at each computation node, which is more restrictive than precision growing with the input sequence length $n$, as $\mathrm{O}(\log n)$ bits. However, this constant could be large and thus, for relatively small $n$, our results do not rule out practical transformers solving difficult problems. Our results, however, do show that as $n$ grows sufficiently large, log-precision transformers are fundamentally limited to problems within $\mathsf{TC}^{0}$ and cannot accurately solve various commonly studied problems mentioned earlier under “What Transformers Cannot Compute”. Extending our analysis to small $n$ will help close the gap to practice.

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.

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.

A circuit family generalizes a circuit to take variable-length binary strings as input. Formally, a circuit family is a sequence of circuits $C_{n}:\{0,1\}^{n}\to\{0,1\}$ for $n\in\mathbb{N}$. A circuit family implicitly recognizes a formal language defined as follows:

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

For $k\in\mathbb{N}$, a threshold gate $\theta_{\leq k}$ takes $m$ input bits and returns whether $\sum_{i=1}^{m}x_{i}\leq k$. We define $\theta_{\geq k}$ analogously. For example, $\theta_{{\leq}3}(110011)=0$.

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.

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.

To serialize $\{\wedge,\vee\}$-circuits, we use the following grammar, where the $i$ parameter is passed through $\mathrm{Gate}[i]$ nonterminals to track the index of the gate in left-to-right order:

In the $\mathrm{Arg}[i]$ rule, we enforce that $j<i$ so that arguments must be pointers to already defined gates. As an example of this serialization language, the circuit for $x_{1}\vee\neg x_{2}\vee x_{3}$ is represented as⁷⁷7Spaces here (and in the grammar) are added for readability. We will ignore these spaces when passing circuit serializations as inputs to a transformer in § 7.

    X X X NOT &1 OR & &111 &11

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.⁸⁸8We 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:

In the rewrite rule for $\mathrm{Gate}[i]$, $m\in\mathbb{N}$ is the arity of the gate, and $k\leq m$ is its threshold. The span 1^k after $\mathrm{Dir}$ can be interpreted semantically as a unary encoding of the parameter $k$ for a threshold gate, padded by 0’s to the number of total arguments of gate $i$. For simplicity, we imagine $\neg$ gates are represented as unary $\theta_{\leq 0}$ gates. Thus, the circuit $\theta_{\geq 1}(x_{1},\neg x_{2})$ would be represented as

    X X <= 00 &1 >= 10 & &11

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.

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 problems⁹⁹9Consider 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}$.

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

Furthermore, we will refer to a circuit family as uniform if it is uniformly computable with $S(n)=\mathrm{O}(\log n)$ (cf. Arora and Barak, 2009). We can define uniform versions of $\mathsf{AC}^{0}$ and $\mathsf{TC}^{0}$ by adopting the previous definitions exactly, but also enforcing uniformity. For the rest of the paper we will clarify whether we mean the uniform or non-uniform variant of $\mathsf{TC}^{0}$ when unclear from context, since both classes will come up.

Algorithm. We first print $2c\log n$ nodes representing unnegated and negated input nodes.¹⁵¹⁵15We 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.

Now, we construct nodes computing each of the $m$ output nodes. We loop over $k\in[m]$, constructing a single node for each $k$. We loop over all $x\in\{0,1\}^{c\log n}$ analogously above to construct a list of arguments. By our linear-space computability assumption and because $x$ has $c\log n$ bits, we can compute $f(x)$ as a subroutine in $\mathrm{O}(\log n)$-space to obtain $f_{k}(x)$. If $f_{k}(x)=1$, we print node $2c\log n+j$ as an argument of node $k$.

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

Log Space. To complete the proof, we justify that $M$ uses $\mathrm{O}(\log n+\log m)$ space. Looping over $x\in\{0,1\}^{c\log n}$ is accomplished by treating $x$ as a binary number initialized to $0$ and incrementing it at each step. Thus, the loop pointer for building the DNF terms takes $c\log n$ space to store. For building the $m$ output nodes, we maintain a similar loop pointer as well as an index $k\leq m$, taking $c\log n+\log m$ space. Thus, the overall algorithm uses $c\log n+\log m$ space.

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.

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

For a vector $\mathbf{x}$ and scalar $y$, let $\langle\mathbf{x},y\rangle$ be the vector appending $y$ onto $\mathbf{x}$.¹⁶¹⁶16I.e., $\langle\mathbf{x},y\rangle_{i}=x_{i}$ for $1\leq i\leq\left\lvert\mathbf{x}\right\rvert$, and $y$ if $i=\left\lvert\mathbf{x}\right\rvert+1$. For $\sigma\in\Sigma$, let $v(\sigma)$ be the one-hot embedding of $\sigma$ into $\mathbb{R}^{\left\lvert\Sigma\right\rvert}$. For $w\in\Sigma^{*}$ and $i\geq 1$, the fractional positional embedding at token $i$ is

We imagine $f(\mathbf{h}_{i}^{\ell},\mathbf{h}_{j}^{\ell})$ is computed via saturated attention (cf. Merrill et al., 2022), which provides a simple model of the types of attention we can expect to be learned in transformers (Merrill et al., 2021). First, queries are computed as $\mathbf{q}_{i}=\mathbf{Q}\mathbf{h}_{i}^{\ell}$, and then keys $\mathbf{k}_{j}=\mathbf{K}\mathbf{h}_{j}^{\ell}$ Define the dot-product attention score $\sigma_{ij}=\mathbf{q}_{i}^{\top}\mathbf{k}_{j}$. We can then define saturated attention as

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.

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

We use input node to mean a token of type X and gate node to mean a token of type $\mathrm{Dir}$. We call a token of type & an argument.

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.

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 $0$ 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 &1^j.

Inductive Case: Gate Nodes. By our inductive assumption over prior layers, all tokens corresponding to circuit nodes at depth $\leq\ell$ contain their appropriate value. We now construct $2$ transformer layers to evaluate gate nodes at depth $\ell+1$.

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.

At this point, we have both the count of true inputs to gate node $i$ ($c_{i}/m_{i}$) and, from the base case, the threshold parameter of gate $i$ ($k_{i}/m_{i}$). Thresholding $(c_{i}-k_{i})/m_{i}$ at $0$ allows us to decide, based on whether $\mathrm{Dir}$ is <= or >=, whether the current gate node should output a $0$ or a $1$. Repeating this for all gates at layer $\ell+1$ completes the inductive step: we can evaluate all gate nodes in this layer. ∎