The Parallelism Tradeoff: Limitations of Log-Precision Transformers
This work addresses a foundational problem in theoretical machine learning by identifying potential inherent weaknesses in the scaling paradigm for transformers, which is incremental in linking architecture to complexity theory.
The paper tackles the problem of characterizing the computational power of transformer neural nets by proving that log-precision transformers can be simulated by constant-depth logspace-uniform threshold circuits, revealing limitations such as inability to solve linear equalities or check membership in arbitrary context-free grammars if L ≠ P.
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.