Source-linked AI summary
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
William Merrill, Ashish Sabharwal
TL;DR
The paper asks what computational problems transformers can solve under realistic precision and resource assumptions, addressing gaps left by earlier characterizations. It proves that log-precision transformers can be simulated by uniform constant-depth threshold circuits, and shows that suitable advice enables recognition of any non-uniform TC0 language. The results identify a potential parallelism tradeoff while noting important asymptotic and tightness limitations.
Problem
The paper seeks a principled characterization of transformer computational power and a uniform upper bound that avoids the interpretive problems of prior non-uniform results.
Method
The paper models transformers with O(log n)-bit intermediate values and O(log n)-space-computable subnetworks, then constructs circuits by induction over transformer layers.
Results
Log-precision transformers are simulable by uniform constant-depth threshold circuits, and transformers with suitable polynomial-size advice can recognize any non-uniform TC0 language.
Takeaways & Limitations
The findings frame bounded precision, threshold computation, and parallelism as central to understanding transformer abilities and limitations.
Takeaways & Limitations
The upper bound is asymptotic, may not rule out difficult problems for practical transformers at relatively small n, and its tightness is left unanswered.
Abstract
from arXiv · showhide
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 $\mathsf L \neq \mathsf 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.
1 Introduction
This paper characterizes transformers under logarithmic precision and argues that their parallelizable architecture creates a tradeoff between scalable training and computational expressiveness. It derives a uniform threshold-circuit upper bound and connects that result to practical limitations and advice-based capabilities.
- Motivation: Prior transformer characterizations either assumed infinite precision and arbitrarily powerful feedforward subnets or imposed restrictive attention mechanisms.These assumptions motivate a more practically interpretable characterization.
- Motivation: Non-uniform AC0 and TC0 bounds are difficult to interpret because these classes include undecidable problems and cannot be directly compared with standard algorithmic complexity classes.The paper therefore asks whether uniform upper bounds can be derived.
- Assumptions: O(log n) precision, together with O(log n)-space-computable subnetworks, is presented as a modest assumption that supports positional encodings and position pointers.The paper argues that fixed practical precision is small relative to long input sequences.
- Main result: Log-precision transformers can be simulated by uniform constant-depth threshold circuits, placing their computational power within uniform TC0.This yields a direct comparison with natural complexity classes and contrasts with infinite-precision Turing-completeness.
- Implications: The proposed parallelism tradeoff links transformers’ computational shallowness to their high parallelizability, which supports massive-scale training but may restrict expressiveness.The paper presents this as a potential weakness of scaling language models and calls for further characterization of relevant reasoning capabilities.
- Instruction following and advice: Transformers can evaluate TC0 circuits when supplied with suitable instructions and can recognize any non-uniform TC0 language with appropriate polynomial-size advice.This provides a complementary lower-bound perspective on their capabilities.
2 Implications of Our Findings
Log-precision transformers fall within logspace-uniform TC0, which yields concrete boundaries on the problems they can solve and motivates a tradeoff between massive parallelizability and representation power.
- Log-precision transformers are in the complexity class logspace-uniform TC0.The result provides a uniform circuit characterization of their computation.
- The paper interprets TC0 membership as arising from transformer parallelizability and proposes a tradeoff between massive parallelism and representation power.The authors speculate that similarly parallelizable architectures may obey similar restrictions.
- Assuming logspace-uniform TC0 ≠ P, transformers cannot perfectly solve universal context-free recognition, linear equalities, or other P-complete reasoning problems.The listed examples include arbitrary context-free grammar recognition and linear equalities.
- Assuming logspace-uniform TC0 ≠ NP, transformers cannot perfectly solve propositional satisfiability or Horn-clause satisfiability.SAT is NP-complete, and the passage identifies HORN-SAT among the affected problems.
- These negative results are asymptotic and concern exact solutions, although known hardness-of-approximation results can extend some conclusions beyond exact computation.For sufficiently small inputs, log-precision transformers may still solve difficult problems.
3 Circuit Computation
The paper formalizes circuits as directed acyclic computation graphs and defines AC0, TC0, serialization, and logspace uniformity to connect transformer computation with circuit complexity.
- A circuit is a directed acyclic computation graph whose internal nodes compute functions from a specified set and whose output nodes determine the result.Circuit size counts gates, while depth is the longest input-to-output path.
- Circuit families recognize variable-length binary strings by assigning one circuit C_n to each input length n.Recognition requires C_|x|(x) = 1 exactly when x belongs to the language.
- AC0 uses polynomial-size, constant-depth circuits with NOT, AND, and OR gates, while TC0 replaces these with threshold gates and includes AC0.Threshold gates test whether the number of true inputs meets a specified threshold.
- Circuit serializations list leaves and then internal gates in topological order, using pointers to previously defined gates and Polish notation for gate functions.Threshold serialization additionally encodes each gate’s arity and threshold parameter.
- A threshold circuit serialization is in prefix form when all input markers precede all threshold gates.The threshold gate’s parameter k is represented after the direction marker using unary encoding padded to the gate’s argument count.
- Uniform circuit families require a resource-constrained Turing machine to map 1^n to the circuit for input size n; logspace uniformity uses O(log n) space.The generalized definition allows the recognized input size to be a function I(n).
4 Bounded-Precision Transformers
This section formalizes transformers with bounded intermediate precision and space, defining layers as parallel attention heads combined by an activation function. It motivates O(log n)-precision as a model of practical fixed-width computation.
- A transformer is a constant-depth neural architecture whose layers compute self-attention followed by elementwise transformation.
- Precision and space: A p-precision function bounds inputs, outputs, and workspace by p bits and requires computation by a p-space-bounded Turing machine.
- Precision and space: The model applies p-precision to bounded-arity operations and to approximate summation over n p-precision floats.
- Attention heads: A p-precision attention head uses a binary similarity function and approximate addition to aggregate values across the input sequence.
- Transformer layers: A transformer layer computes k attention heads in parallel and combines their outputs with the previous-layer representation through an activation function.
- Bounded-precision transformers: The formal transformer is a fixed-depth cascade of p-precision layers with position-wise broadcasted embeddings.
- Precision and space: For fixed vocabulary, the binary input has N = n log|Σ| bits, so O(log N)-precision is treated as O(log n)-precision.
- Relationship to practical transformers: Bounded-precision practical transformers are included when their primitive operations use O(log n)-size numbers and O(log n) space.
5 Log-Precision Transformers as Non-Uniform Threshold Circuits
The section first establishes a non-uniform TC0 simulation for log-precision transformers, removing restrictions on attention functions while exploiting bounded-width intermediate values.
- Log-precision transformers with arbitrary attention functions can be simulated by non-uniform TC0 circuits, without saturated-attention restrictions.
- The result extends prior TC0 simulations of saturated-attention transformers to unrestricted attention under the log-precision assumption.
- Any function on c log n input bits can be computed by an AND/OR circuit of depth 3 and polynomial size, including multiple output bits together.
- Any c log n-precision depth-d transformer has a non-uniform threshold-circuit simulation of depth 3 + (9 + 2d⊕)d.
- The simulation computes each transformer layer inductively by parallel circuits for attention components, approximate sums, and layer outputs.
- Log precision limits every layer vector to O(log n) bits, enabling the bounded-input circuit construction for intermediate functions.
- The resulting circuit depth is 3 + (9 + 2d⊕)d for a depth-d transformer.
6 Log-Precision Transformers as Uniform Threshold Circuits
The section upgrades the non-uniform simulation to a logspace-uniform construction by generating the circuit description with an O(log n)-space Turing machine.
- Any c log n-precision depth-d transformer is simulated by a logspace-uniform threshold circuit of depth 3 + (9 + 2d⊕)d.
- A linear-space-computable function on c log n-bit inputs has a depth-3 circuit generated from 1^n using at most c log n + log m space.
- The uniform construction enumerates input nodes and all DNF terms using binary counters, then computes output-node connections by evaluating the function in log space.
- The machine uses O(log n) space to construct the circuit, with the circuit size bounded by n^c + c log n + m and depth 3.
- The inductive construction repeats the layer simulation for every token while retaining only O(log n)-sized indices and counters.
- For each transformer layer, the construction generates circuits for attention scores, normalization, approximate sums, and activation outputs with regular node indexing.
- Because the depth is constant in n, any log-precision transformer is simulable by a uniform TC0 circuit family.
7 Lower Bounds for Instruction Following and Advice Transformers
The lower-bound construction shows that transformers can evaluate serialized TC0 circuits when given circuit instructions, while emphasizing that this does not establish tightness of the uniform TC0 upper bound.
- 7 Lower Bounds for Instruction Following and Advice Transformers: The authors leave open whether the uniform TC0 upper bound is tight, but construct transformers that evaluate TC0 circuits when supplied with their instructions.
- 7 Lower Bounds for Instruction Following and Advice Transformers: The construction solves the Circuit Value Problem for depth-d TC0 circuits using a depth-2d transformer.
- 7 Lower Bounds for Instruction Following and Advice Transformers: This demonstrates that transformers can evaluate Boolean formulae, contrasting with the stated limitation of LSTMs.
- 7 Lower Bounds for Instruction Following and Advice Transformers: The construction uses serialized circuit nodes, arguments, and gate tokens, with positional information encoding pointers and gate parameters.
- 7 Lower Bounds for Instruction Following and Advice Transformers: For every depth-d threshold circuit, a depth-2d transformer with fractional positional embeddings, saturated attention, and thresholded linear pooling computes its output.
- 7 Lower Bounds for Instruction Following and Advice Transformers: Two transformer layers evaluate each circuit depth by retrieving referenced node values, counting true arguments, and thresholding against each gate’s threshold.
- 7.1 Instruction Following: The result gives a non-trivial instruction-following lower bound: transformers can follow any instruction represented by a constant-depth threshold circuit.
- 7.1 Instruction Following: TC0 includes counting and arithmetic problems beyond regular languages, expanding the known instruction types transformers can follow with hand-constructed weights.
8 Conclusion
The paper concludes that log-precision transformers with soft or hard attention can be simulated by uniform constant-depth threshold circuits, revealing a tradeoff between parallelism and expressiveness.
- Log-precision transformers with any attention mechanism can be re-expressed as polynomially many threshold gates at constant depth.
- If L ⊂P, transformers cannot compute all polynomial-time functions and are far from universal.
- The result suggests that highly parallelizable architectures may sacrifice expressiveness.
- Because parallelism is essential to pretraining massive models, similar limitations may affect large language models beyond transformers.
A Iterated p-Precision Float Addition
The appendix represents p-precision floats as signed mantissa–exponent pairs, maps them to integers for addition, and truncates the result back to a float. With logarithmic precision, this iterated addition is computable by a polynomial-size constant-depth uniform threshold circuit, with bounded approximation error.
- A p-bit string encodes a float as a signed p/2-bit mantissa and signed p/2-bit exponent, representing m · 2^e.
- Exact sums may require more bits than the input precision, so truncation is needed when converting the integer sum back to a float.
- Float addition maps floats to integers, adds them exactly, and maps the sum back with possible precision loss.
- Integer conversion rescales each float by 2^-Imin, producing an integer representation suitable for threshold-circuit summation.
- When overflow is excluded, the truncated result is either exact or within a multiplicative factor of 1 ± 2^-p/2+2.
- Iterated addition of up to n O(log n)-precision floats is computable by a constant-depth uniform threshold circuit of polynomial size.