Saturated Transformers are Constant-Depth Threshold Circuits
Authors:
- William MerrillWMWilliam Merrill
- Ashish SabharwalASAshish Sabharwal
Preprint
Abstract
Transformers have become a standard neural network architecture for many NLP problems, motivating theoretical analysis of their power in terms of formal languages. Recent work has shown that transformers with hard attention are quite limited in power (Hahn, 2020), as they can be simulated by constant-depth AND/OR circuits (Hao et al. 2021). However, hard attention is a strong assumption, which may complicate the relevance of these results in practice. In this work, we analyze the circuit complexity of transformers with saturated attention: a generalization of hard attention that more closely captures the attention patterns learnable in practical transformers. We first show that saturated transformers transcend the known limitations of hard-attention transformers. We then prove saturated transformers with floating-point values can be simulated by constant-depth threshold circuits, giving the class $\mathsf{TC}^0$ as an upper bound on the formal languages they recognize.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent2021
- Self-Attention Networks Can Process Bounded Hierarchical Languages2021
- Theoretical Limitations of Self-Attention in Neural Sequence ModelsTransactions of the Association for Computational Linguistics, 2020
- On the Ability and Limitations of Transformers to Recognize Formal Languages2020
- RNNs can generate bounded hierarchical languages with optimal memory2020
- BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding2019
- On the Practical Computational Power of Finite Precision RNNs for Language Recognition2018
- Rational Recurrences2018
- ON ACC and threshold circuits2002
- Parity, circuits, and the polynomial-time hierarchy1981