On the Power of Saturated Transformers: A View from Circuit Complexity
Authors:
Preprint
Abstract
Transformers have become a standard architecture for many NLP problems. This has motivated theoretically analyzing their capabilities as models of language, in order to understand what makes them successful, and what their potential weaknesses might be. Recent work has shown that transformers with hard attention are quite limited in capacity, and in fact can be simulated by constant-depth circuits. However, hard attention is a restrictive assumption, which may complicate the relevance of these results for practical transformers. 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 show that saturated transformers transcend the limitations of hard-attention transformers. With some minor assumptions, we prove that the number of bits needed to represent a saturated transformer memory vector is $O(\log n)$, which implies saturated transformers can be simulated by log-depth circuits. Thus, the jump from hard to saturated attention can be understood as increasing the transformer's effective circuit depth by a factor of $O(\log n)$.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- 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
- A Formal Hierarchy of RNN Architectures2020
- BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding2019
- Sequential Neural Networks as Automata2019
- On the Practical Computational Power of Finite Precision RNNs for Language Recognition2018
- Rational Recurrences2018
- Parity, circuits, and the polynomial-time hierarchy1981