The Parallelism Tradeoff: Limitations of Log-Precision Transformers (2023)

Abstract: Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedforward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory. For example, if L≠P (i.e., not all poly-time problems can be solved using logarithmic space), then transformers cannot even accurately solve linear equalities or check membership in an arbitrary context-free grammar with empty productions. Our result intuitively emerges from the transformer architecture’s high parallelizability. We thus speculatively introduce the idea of a fundamental parallelism tradeoff: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training models at massive scale, this suggests a potential inherent weakness of the scaling paradigm.

## introduction this work aims to characterize the computational model implicit in transformer neural networks @xcite , which form the basis of recent breakthroughs in large language models such as bert @xcite , t5 @xcite , and gpt-3 @xcite . 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 transformerbased systems. early theoretical work on transformers established their turing completeness, albeit with assumptions like infinite precision and arbitrarily powerful feedforward subnets @xcite . 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, @xcite and @xcite showed that transformers restricted to hard attention are very limited: they can only solve problems in a weak complexity class (non-uniform ac 0 ) that doesn't even contain basic problems like majority of n bits. @xcite 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 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 ac 0 and 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 p, np, etc. this motivates our second key question: can we derive uniform upper bounds on transformers? we show that one can achieve both of these goals by making the modest assumption that all values in the transformer have o(log n) precision (where n is the number of input tokens), and, similarly, that transformer's subnetworks are computable in o(log n) space. log precision is enough to represent the positional encodings at the input layer of the transformer, and to encode pointers to all other positions in the sequence at later transformer layers. assuming log precision across all layers captures the idea that the hidden representations contain a constant number of hidden states whose precision (16 or 32 bits) is small relative to the length of the input (2048 in gpt-3). on long sequences, the precision will not be enough to losslessly encode the full input sequence into a single vector. instead, the processing of the sequence must somehow be distributed in each layer and performed in parallel. upper bound on transformers. our main contribution is proving that log-precision transformers can be simulated by uniform constantdepth threshold circuits. thus, such transformers can only solve problems in uniform 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. ## 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 (theorem 2), which shows that log-precision transformers are in the complexity class logspace-uniform tc 0 . the parallelism tradeoff. one interpretation of complexity classes such as nc 0 , ac 0 , and 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 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. ## circuit computation let {0, 1} * be the set of finite binary strings. for @xmath0, 1} * , let |x| 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. 6 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 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. definition 1. for a set of functions g, a g-circuit is a directed acyclic computation graph where the internal nodes have labels from g. ## bounded-precision transformers a transformer @xcite 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. ## 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 @xcite , who showed that saturated attention transformers foot_8 can be simulated in 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 tc 0 with any attention function. hao et al. observed that any boolean function of o(log n) bits can be computed by a poly(n) size circuit. we extend this to m-bit outputs, which is both more convenient and more efficient than constructing m separate boolean circuits: lemma 1 (extended from @xcite . let f : {0, 1} * → {0, 1} m be a function. for all @xmath1, there exists an and/or circuit of size at most n c + c log n + m and depth 3 that computes f on inputs of size c log n. proof. like @xcite , 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 @xmath2. 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 lemma 1 to prove the following non-uniform result. we note that the proof goes through even if the notion of p-precision (definition 6) is relaxed to not require computability in space p. this requirement will, however, become important for our subsequent result in §6. theorem 1 (non-uniform). any c log n-precision depth-d transformer operating on inputs in σ n can be simulated by a threshold circuit family of depth 3 + (9 + 2d ⊕ )d. proof. let @xmath3. 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 0 and token i, we construct gates representing the constant i encoded in binary. we can then compute h 0 @xmath4, i) using lemma 1, yielding a poly-size depth-3 circuit. in the inductive case of computing layer h ℓ+1 i for 1 ≤ ℓ + 1 ≤ d, we note that each vector output of layer h ℓ i has size (at most) c log n bits because of the log-precision assumption. we first fix a head a ℓ+1 ik (definition 8) to simulate. applying lemma 1, we can compute s(h ℓ i , h ℓ j ) with a poly-size depth-3 circuit, in parallel for all j. since n floats with c log n precision can be approximately added in tc 0 ( §a), we can construct a tc 0 circuit of depth d ⊕ to compute z j . since s(h ℓ i , h ℓ j ), z i , and h ℓ i all have c log n bits, we can compute s(h ℓ i ,h ℓ j ) z i h ℓ j with a poly-size depth-3 circuit; foot_9 we do this in parallel for all j. next, we again use the fact that approximate addition of n floats is in tc 0 to compute a ℓ+1 ih as the approximate sum over j with a depth-d ⊕ circuit. we now simulate a layer h ℓ+1 i (definition 10) in terms of its constituent heads. since all arguments of g have size c log n, we apply lemma 1 to compute g with a poly-size depth-3 circuit, yielding h ℓ+1 i . we repeat this in parallel for all i. this completes the inductive step new to compute all values in the ℓ + 1-st layer with a circuit depth of 9 + 2d ⊕ . aggregating the circuit over all d layers, the overall circuit depth is 3 + (9 + 2d ⊕ )d. ## lower bounds for instruction following and advice transformers so far, we have shown that uniform 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 tc 0 circuits on binary inputs, showing that transformers can compute any tc 0 function when their input is augmented with the right ''instructions''. more formally, we consider the circuit value problem (cvp) @xcite , also referred to as the circuit evaluation problem, where the input is a boolean circuit c and a string @xmath5, 1} n , and the task is to return the value of c(x) ∈ {0, 1}. this problem is known to be complete for the class p under ac 0 reductions @xcite . we will assume c is serialized as described in §3 and prove that log-precision transformers can evaluate any 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 @xcite , 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 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. ## conclusion answering two open questions from @xcite , 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 l ⊂ 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.