The Parallelism Tradeoff: Limitations of Log-Precision Transformers

The Parallelism Tradeoff: Limitations of Log-Precision Transformers William Merrill Center for Data Science New York University, New York, NY, USA willm@nyu.edu Ashish Sabharwal Allen Institute for AI Seattle, WA, USA ashishs@allenai.org Abstract Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interest- ing open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedfor- ward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This pro- vides insight on the power of transformers using known results in complexity theory. For example, if L ̸= P (i.e., not all poly-time prob- lems 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 par- allelizability. We thus speculatively introduce the idea of a fundamental parallelism trade- off: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training mod- els at massive scale, this suggests a potential inherent weakness of the scaling paradigm. 1 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 capabili- ties, and building trust in deployed transformer- based systems. Early theoretical work on transformers es- tablished their Turing completeness, albeit with assumptions like infinite precision and arbitrarily powerful feedforward subnets (P´erez et al., 2019; Dehghani et al., 2019). On the other hand, a strand of more recent work uses techniques from cir- cuit 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 that transform- ers restricted to hard attention are very limited: they can only solve problems in a weak com- plexity class (non-uniform AC0) 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 TC0) as an upper bound. This motivates analyzing a setting that strikes a middle ground: Can we characterize transformers whose precision and feedforward nets’ computa- tional 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 con- sidered circuit classes, which makes these classes non-realizable and the findings difficult to in- terpret. This is …

Content truncated to 500 words