Simplicity Bias in Transformers and their Ability to Learn Sparse B oolean Functions (2023)

Abstract: Despite the widespread success of Transformers on NLP tasks, recent works have found that they struggle to model several formal languages 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 following: (i) Random Transformers are relatively more biased towards functions of low sensitivity. (ii) When trained on Boolean functions, both Transformers and LSTMs prioritize learning functions of low sensitivity, with Transformers ultimately converging to functions of lower sensitivity. (iii) On sparse Boolean functions 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 accuracy. Overall, our results provide strong quantifiable 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.

## introduction transformers @xcite have supplanted recurrent models across a range of nlp tasks @xcite . in particular, effective large-scale pretrained models have predominantly been transformer-based models and have found application in other areas such as computer vision and protein folding. given the irrefutable importance of understanding these architectures, a significant effort has been devoted to analyze the inner workings of large-scale pretrained transformers. however, the cause behind the difference in performance between transformers and recurrent models has largely been unclear. a line of work has attempted to understand neural sequence models through the lens of formal language theory. these works have sought to understand the expressive power of these architectures and identify differences in their ability to generalize across various formal languages. a notable result by @xcite showed that transformers are limited in their ability to express the parity language foot_0 while it is well known that small-sized rnns can express such languages. across empirical studies, transformers have been found to perform worse or comparably to lstms in almost all formal languages previously considered in the literature @xcite @xcite . in particular, transformers have been shown to struggle with the parity language and certain other regular languages. 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 shown to perform better on formal languages such as parity, we find that they struggle to generalize well on several sparse boolean functions such as sparse parities. we find a clear contrast between the generalization abilities of transformers and lstms on various k-sparse boolean functions which have low sensitivity. additionally, through extensive empirical analysis, we provide strong evidence to suggest differences in the bias towards low complexity functions between transformers and recurrent models. based on our results, we hypothesize that one of the reasons behind transformer's practical effectiveness could be that they are more biased towards simple functions in comparison to recurrent models which may lead to better generalization. in particular, we focus on a complexity measure called sensitivity @xcite , which measures how likely it is that a function value changes due to a 'small' change in input. sensitivity is related to several other complexity measures; functions with low sensitivity have low kolmogorov complexity, 2 simpler fourier spectra, and can be represented by decision trees of small depths. the relationship between sensitivity and generalization has also been previously studied in the literature @xcite . 3 while measures such as kolmogorov complexity are uncomputable, sensitivity can be tractably estimated and extensions of sensitivity can be used to estimate the complexity of functions in more realistic nlp tasks @xcite . our contributions. we investigate the bias in (a) parameter space by analyzing randomly initialized models, and (b) learning procedure by examining the sensitivity of models during the training process. motivated by our findings indicating differences between the biases of transformers and lstms, we evaluate their performance on functions of low sensitivity. ## sensitivity experiments in this section, we conduct various experiments to investigate the differences in the bias of transformers and rnns towards functions of low sensitivity. 6 from here onward, whenever sensitivity is mentioned, we will refer to the length normalized version of average sensitivity s defined in eq. ( 3 ). the first part of this section deals with analyzing the sensitivity of random transformers and rnns while the second part investigates the sensitivity of models trained to fit random boolean functions. ## experiments on sparse boolean functions our results in the previous section indicate that relative to lstms, random transformers are biased towards low-sensitivity functions and transformers are biased towards learning boolean functions of low sensitivity. motivated by this difference in bias, we conduct experiments geared towards answering the following question: is there any difference between the ability of transformers and lstms to learn sparse boolean functions which have low sensitivity? 5.1 setup. boolean functions. we focus on k-sparse boolean functions which have low sensitivity when k ≪ n (refer to section 3 for definition). we first consider certain boolean functions which are widely studied in the analysis of boolean functions. the first one is sparse parities which can be interpreted as the k-sparse variation of standard parity. we denote an instance of sparse parities as parity-(n, k) where n denotes the length of the input string and k denotes the number of relevant bits. we denote an instance of standard parity as parity-n where n denotes the length of the input string and the output is computed based on the number of ones in all indices. learning parity-(n, k) with gradient-based methods has well-known hardness resultsrequiring at least n ω(k) computational steps to find the correct target function @xcite . the other two boolean functions we consider are sparse majorities (denoted by maj-(n, k)) and the dictator function (denoted by dict-n). the output of the dictator function depends only on a single input bit, making it arguably one of the simplest boolean functions with very low sensitivity. in maj-(n, k), the output for a string of length n is determined by whether the number of ones is greater than the number of zeros in the k relevant indices. the second set of boolean functions we consider is random k-sparse functions (denoted by juntas-(n, k)). for each instance of juntas-(n, k), the function is determined by randomly choosing k indices and assigning labels to each of the 2 k distinct inputs randomly. 7 noisy labels. we also conduct experiments to examine the ability of the models to learn in the presence of noise. in these experiments, labels of training data are flipped with a certain probability η. thus, about 1η fraction of the training data is clean and η fraction of the training data has incorrect labels. the validation set is clean without any modifications. the goal is to investigate whether a model is robust to noise during the training process. training details. the training and validation sets are created by uniformly sampling bit strings over {0, 1} n . in our experiments, we consider transformers with 1-6 layers, 4-8 heads and width (usually referred to as d_model) within 8-128. we consider transformers with both learnable and absolute positional encodings. for lstms, we consider up to 6 layers and widths (also referred to as hidden_size) within 8-256. the size of the token embeddings is kept the same as the width. we also consider the presence of learnable positional embeddings as a hyperparameter. we use batch sizes of 100 and 500 in all our experiments and tune across learning @xmath0, 5e-2, . . . , 1e-6}. for each dataset, we extensively tune the models across various hyperparameters, details of which are provided in appendix g. ## discussion and final remarks a natural question that arises from our results is whether transformers are performing better because the tasks are more suited to their architecture. perhaps yes. one could argue that a number of regular languages that transformers struggle to learn @xcite are more suited to recurrent architecture. transformers have been shown to perform poorly on languages that require modular counting. dfas, which are often considered to be formal abstractions of recurrent models, can represent these more efficiently. for instance, languages like standard parity can be represented with a two-state dfa while representing sparse parities would require a larger number of states. in contrast, for circuits that have recently been related to transformers @xcite , representing sparse parities would be easier than representing standard parity. our results indicate that previous works might have overestimated the performance of lstms by considering regular languages which are more suited for autoregressive architectures. the question of which formal languages are more closely associated with practical tasks is not entirely clear. prior works on analysis with formal languages have primarily followed chomsky hierarchy owing to the conjecture that natural languages are mildly context-sensitive. while regular languages such as parity have high sensitivity (@xmath1, practical tasks are often structured and have typically much lower sensitivity @xcite . in tasks such as sentiment analysis, the label often depends on a sparse subset of input tokens. when practical text datasets such as sst are labelled with random noise, then it can be shown that their sensitivity would be concentrated around 1/2. as shown in fig. 23 , models take much longer to fit such datasets whereas, in the case of the true labels, they only need a few epochs to fit the dataset. our results indicate that while transformers perform poorly on certain regular languages, they generalize more effectively than recurrent models on various sparse boolean functions. moreover, we showed that random transformers as well as those trained with gradient-based algorithms are biased towards functions of low sensitivity. our results add to the body of work that suggests that there is a form of implicit regularization in the procedure used to train neural models which prevent them from overfitting despite their incredible capacity.