Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 5767–5791 July 9-14, 2023 ©2023 Association for Computational Linguistics Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions Satwik Bhattamishra♠ Arkil Patel♢ Varun Kanade♠ Phil Blunsom♠♣ ♠University of Oxford ♢Mila and McGill University ♣Cohere {satwik.bmishra, varun.kanade, phil.blunsom}@cs.ox.ac.uk arkil.patel@mila.quebec Abstract Despite the widespread success of Transform- ers on NLP tasks, recent works have found that they struggle to model several formal lan- guages when compared to recurrent models. This raises the question of why Transformers perform well in practice and whether they have any properties that enable them to generalize better than recurrent models. In this work, we conduct an extensive empirical study on Boolean functions to demonstrate the follow- ing: (i) Random Transformers are relatively more biased towards functions of low sensitiv- ity. (ii) When trained on Boolean functions, both Transformers and LSTMs prioritize learn- ing functions of low sensitivity, with Trans- formers ultimately converging to functions of lower sensitivity. (iii) On sparse Boolean func- tions which have low sensitivity, we find that Transformers generalize near perfectly even in the presence of noisy labels whereas LSTMs overfit and achieve poor generalization accu- racy. Overall, our results provide strong quan- tifiable evidence that suggests differences in the inductive biases of Transformers and recurrent models which may help explain Transformer’s effective generalization performance despite relatively limited expressiveness. 1 Introduction Transformers (Vaswani et al., 2017) have sup- planted recurrent models across a range of NLP tasks (Liu et al., 2019; Brown et al., 2020). In particular, effective large-scale pretrained models have predominantly been Transformer-based mod- els and have found application in other areas such as computer vision and protein folding. Given the irrefutable importance of understanding these ar- chitectures, a significant effort has been devoted to analyze the inner workings of large-scale pre- trained Transformers. However, the cause behind the difference in performance between Transform- ers and recurrent models has largely been unclear. A line of work has attempted to understand neu- ral sequence models through the lens of formal language theory. These works have sought to un- derstand the expressive power of these architectures and identify differences in their ability to general- ize across various formal languages. A notable result by Hahn (2020) showed that Transformers are limited in their ability to express the PARITY language1 while it is well known that small-sized RNNs can express such languages. Across empiri- cal studies, Transformers have been found to per- form worse or comparably to LSTMs in almost all formal languages previously considered in the liter- ature (Bhattamishra et al., 2020a; Delétang et al., 2022; Chiang and Cholak, 2022). In particular, Transformers have been shown to struggle with the PARITY language and certain other regular lan- guages. This leads to a natural question: Why do Transformers perform so well in practice if they are arguably less expressive and perform worse than LSTMs across certain formal languages? Although recurrent models such as LSTMs have been …

Content truncated to 500 words