Transformer-based language models such as BERT (Devlin et al., 2018) have achieved the state-of-the-art performance on various NLP tasks, but are computationally prohibitive. A recent line of works use various heuristics to successively shorten sequence length while transforming tokens through encoders, in tasks such as classification and ranking that require a single token embedding for prediction. We present a novel solution to this problem, called Pyramid-BERT where we replace previously used heuristics with a coreset based token selection method justified by theoretical results. The core-set based token selection technique allows us to avoid expensive pre-training, gives a space-efficient fine tuning, and thus makes it suitable to handle longer sequence lengths. We provide extensive experiments establishing advantages of pyramid BERT over several baselines and existing works on the GLUE benchmarks and Long Range Arena (Tay et al., 2020) datasets. Transformers (Vaswani et al., 2017) have gradually become a key component for many state-of-the-art natural language representation models. A recent Transformer based model BERT (Devlin et al., 2018), and its variations, achieved the state-of-the-art results on various natural language processing tasks, including machine translation (Wang et al., 2019a; Liu et al., 2020), question-answering (De-vlin et al., 2018; Yang et al., 2019), text classification (Goyal et al., 2020; Xu et al., 2019), semantic role labeling (Strubell et al., 2018), and so on. However, it takes substantial computational resources to pre-train, fine-tune, or infer such models. The complexity of Transformers is mainly due to a pipeline of encoders, each of which contains a multi-head self-attention layer. The self-attention operation scales quadratically with the input sequence length, which is a bottleneck especially for long-sequence data. Given this challenge, intensive efforts have been focused on compressing and accelerating Transformers to reduce the cost of pre-training and fine-tuning. This work is particularly inspired by the sequence-level NLP tasks such as text classification and ranking. The state-of-the-art Transformer models for these tasks utilize a single embedding from the top encoder layer, such as the CLS token, for prediction. Under such regime, retaining full-length sequence till the last encoder creates unnecessary complexity. We follow a line of works detailed in Section 2 that aim to gradually reduce the sequence length in the pipeline of encoders. On a high level, the existing works have two components: Select : a mechanism in charge of reducing the sequence length, either by pruning or pooling, Train-Select : a training or fine-tuning procedure dedicated to this mechanism. Our main contribution is a novel solution for Select , motivated from the following observation: As we consider the token representations in top layers, they have increasing redundancy among themselves. We provide a quantitative study demonstrating this in Figure 1. A collection of tokens with high redundancy can intuitively be represented by a small core-set , composed of a subset of the tokens. Inspired by this, our solution for Select is based on the idea of core-sets . We provide a theoretically motivated approach that becomes more effective as the redundancy in the representation increases. This concept separates our work from previous art that provide heuristic techniques for sequence length reduction, or approaches that require expensive training. All of these can in fact be shown to fail in toy examples with high redundancy, e.g. the same representation duplicated multiple times. For Train-Select there is some variety in previous art. Some require a full pre-training procedure, and others require a fine-tuning procedure that works 8798 on the full uncompressed model, meaning one that keeps all tokens until the final encoder layer. The high quality of our solution to Select allows us to simply avoid this additional training phase altogether. The result of this simplification is quite impactful. We obtain a speedup and memory reduction not only to the inference but to the training process itself. This makes it possible to use standard hardware (and training scripts) in the training procedure even for very long sequences. In Section 6 we provide an empirical comparison of our technique with SOTA alternatives and show that it is superior in eliminating redundancy among the tokens, and thus greatly improves the final classification accuracy. In particular, our experiments on the GLUE benchmarks show that our method achieves up to 3 3 . 5 X inference speedup while maintaining an accuracy (mean value over all GLUE datasets) drop of 1 . 5% , whereas the best baseline suffers a 2 . 5% drop. We show that our method can be combined with long-text Transformers such as Big Bird (Zaheer et al., 2020) and Performers (Choromanski et al., 2020) to further alleviate the quadratic space complexity of the self-attention mechanism. Empirical experiments on the Long Range Arena (LRA) (Tay et al., 2020) show that our model achieves a better trade-off between space complexity reduction and accuracy in comparison to its competitors. In particular, when working with Performers and reducing the space complexity by 70%, while baselines suffer a drop in accuracy of 4% or more, our technique actually improves the accuracy as it acts as a regularizer. Concluding, our paper provides a novel, theoretically justified technique for sequence length reduction, achieving a speedup and memory reduction for both training and inference of transformers, while suffering significantly less in terms of predictive performance when compared to other existing techniques. Our methods are vetted via thorough empirical studies comparing it against SOTA methods and examining its different components. There have been a number of interesting attempts, that were aimed at model compression for Transformers, which can be broadly categorized into three directions. The first line of work focus on the redundancy of model parameters. Structure pruning (McCarley, 2019; Michel et al., 2019; Voita et al., 2019; Wang et al., 2019b; Fan et al., 2019; Wu et al., 2021a), which removes coherent groups of weights to preserve the original structure of the network, is one common strategy. In addition, various types of distillation techniques (Sanh et al., 2019; Sun et al., 2019; Jiao et al., 2019; Wang et al., 2020b) have been proposed to remove encoders by training a compact Transformer to reproduce the output of a larger one. Other strategies include weight quantization (Bhandare et al., 2019; Zafrir et al., 2019; Shen et al., 2020; Fan et al., 2020) and weight sharing (Dehghani et al., 2018; Lan et al., 2019). The second line of work focus on reducing the quadratic operation of the self-attention matrices. The quadratic time and space complexity of the attention mechanism with respect to the input sequence serves the main efficiency bottleneck of Transformers, and thus is prohibitively expensive for training long-sequence data. One popular approach is to sparsify the self-attention operation by restricting each token to only attend a subset of tokens (Child et al., 2019; Kitaev et al., 2020; Ye et al., 2019; Qiu et al., 2019; Ainslie et al., 2020; Zaheer et al., 2020; Beltagy et al., 2020). In particular, the most recent Big Bird (Zaheer et al., 2020) and Longformer (Beltagy et al., 2020) introduce sparse models which scale linearly with the input sequence. Another popular approach (Wang et al., 2020a; Choromanski et al., 2020) is to approximate the self-attention to reduce its quadratic complexity to linear, where the most recent Performers (Choro-manski et al., 2020) provides an unbiased linear estimation of the attention matrices. The third line, which our work lies in, focus on the redundancy in maintaining a full-length sequence of token-level representation across all encoders (Dai et al., 2020; Pietruszka et al., 2020; Ye et al., 2021; Kim and Cho, 2020). This work is particularly inspired by the sequence-level NLP tasks such as text classification and ranking, where the state-of-the-art approach utilizes a single embedding from the top encoder layer of a Transformer, such as the CLS token, for prediction. Under such regime, retaining the full-length sequence till the last encoder creates unnecessary complexity. Dai et al. (2020) applied a simplest strided mean pooling to each sliding window of the sequence to gradually compress tokens. The paper proposed a specialized pre-training procedure for this process that achieves a good balance between speedup and accuracy drop. In comparison we aim to avoid the costly pre-training step and focus on a method that 8799 requires only a lightweight fine-tuning. Wu et al. (2021b) define a centroid attention operator that given centroids, computes their embeddings via an attention mechanism. These centroids are cho-sen either as a random subset of the original tokens, or via strided mean pooling. This results in a similar technique to that of Dai et al. (2020), in terms of having a naive sequence length reduction method. Pietruszka et al. (2020) provide a variant of length 2 strided mean pooling where instead of taking the unweighted average of each pair, they provide learnable weights via a differentiable linear function. In our experiment we did not compare our methods with (Wu et al., 2021b; Pietruszka et al., 2020) since both worked on a limited (non-standard) collection of datasets and at the time of writing this paper, did not provide code allowing us to reproduce their result. Since our paper is focused on techniques to select a subset of tokens and these papers use either random sampling or pooling, we do not believe a thorough comparison is required. Ye et al. (2021) proposed a reinforcement-learning based technique to rank the tokens, thereby allowing it to remove the least important ones. This RL policy must be trained in an expensive process that requires the full network structure. Since we focus on methods to improve both training and inference, we do not include it in our experiments. Vision Transformers (Pan et al., 2021; Heo et al., 2021), which apply various types of pooling techniques to reduce input length, are specially designed for image data and thus non-trivial to compare with our method. Early exiting approaches (Xin et al., 2020; Zhou et al., 2020), which allow samples to exit early based on redundancy, are orthogonal to our technique. Goyal et al. (2020) developed an attention based mechanism to progressively eliminate tokens in the intermediate encoders in the fine-tuning, while maintaining the classification accuracy. Background. A Transformer model, e.g. BERT, takes a sequence of tokens as input for each input sentence. The sequence of tokens consists of a CLS token followed by the tokens generated by to-kenizing the input sentence. For batch processing, an appropriate sequence length N is chosen, and shorter input sentences are padded to achieve an uniform length N . The embedding layer E embeds each token into a vector of real numbers of a fixed dimension. For each input sentence, the token embeddings are transformed through a pipeline of encoders and the self-attention mechanism. Each encoder takes all the N embeddings as input, and outputs updated N embeddings of the same dimension. The time and space complexity of the self-attention scales quadratically with the input sequence length N . Motivation. The state-of-the-art BERT utilizes only the CLS token from the top encoder layer for tasks such as classification and ranking. A natural question is: do we need to propagate all the token embeddings through the entire pipeline of encoders when only the top layer CLS embedding is used for prediction? In general, yes, since the self-attention transforms all the embeddings together, updating each one by capturing information from all the others. However, if two or more tokens are exact duplicates of each other, ignoring the positional embedding, then one can easily remove the duplicates from the input and modify the self-attention appropriately to get the same CLS embedding at the top layer, and hence the same prediction. This would reduce the number of FLOPs carried out in each self-attention layer. In general, input sentences do not contain duplicate tokens. However, a preliminary study of token embeddings show that as the embeddings propagate through the pipeline of encoders, they become more similar to the CLS token, Figure 1 (top row). A deeper investigation shows that they also become more similar with each other and form clusters among themselves, Figure 1 (bottom row). In this work, we exploit these observations, and present pyramid BERT, a novel BERT architecture, that reduces computational and space complexity of fine-tuning and inference of BERT while incurring minimal performance degradation. The pyra-8800 Figure 2: Illustration of Pyramid-BERT. Architecture. The pyramid BERT successively selects subsets of tokens in each encoder layer to propagate them to the next encoder. An illustration of pyramid BERT is shown in Figure 2. It involves two main components over BERT: (a) A sequence-length configuration: a monotonically decreasing sequence (cid:96) = ( (cid:96) 1 , (cid:96) 2 ,    , (cid:96) L ) that specifies the number of tokens to retain in each of the L encoders, for all the input examples. (b) A core-set based token selection methodology which in each j -th encoder, given (cid:96) j  1 token embeddings from the ( j  1) -th encoder selects a subset of it of size (cid:96) j to propagate them to the next encoder. Note that the rest of pyramid BERT architecture is same as the BERT, and it has exactly the same number of parameters as the BERT. In Section 4, we provide a theoretical derivation of the core-set based token selection methodology by minimizing an upper bound of successive token selection loss. To computationally perform the core-set based token selection, we provide a greedy k -center algorithm in Section 5.1. In Section 5.2, we present a simple yet effective approach to select the sequence-length configuration (cid:96) for a desired time/space complexity reduction. Problem Definition. We are interested in a C class classification problem defined over a compact space X and a label space Y = { 1 , 2 ,    , C } . We consider a loss function L w (  ,  ) : X  Y  R which is parametrized over the hypothesis class ( w ) , the parameters of the transformer network (e.g. BERT), and a set of training data points sampled i.i.d. over the space Z = X  Y as { x i , y i } i  [ n ]  p Z where [ n ] = { 1 , 2 ,    , n } . Let T denote a token selection algorithm. For an example input x , let the input and output embeddings of the token selection algorithm T at encoder j be (cid:101) S j and S j respectively. The size of the two sets are | (cid:101) S j | = (cid:96) j  1 , and | S j | = (cid:96) j . In particular, at each encoder j , the algorithm T selects (cid:96) j embeddings of the input set (cid:101) S j as the output set S j , and eliminates the remaining (cid:96) j  1 (cid:96) j embeddings in (cid:101) S j . Let (cid:101) S = { (cid:101) S j } j  [ L ] , and S = { S j } j  [ L ] . Given the underlying BERT parameters w , the sequence length configuration (cid:96) , and the classification loss L w , pyramid BERT solves the token selection problem by minimizing the population risk as follows: min {S : S j  (cid:101) S j , | S j | (cid:96) j } j  [ L ] E x ,y  p Z (cid:2) L w ( x , y, (cid:101) S , S ) (cid:3) . (1) Method. In order to design an optimal token selection algorithm T , we consider the following upper bound of the token selection loss defined in (1): E x ,y  p Z [ L ( x , y, (cid:101) S , S )] (cid:124) (cid:123)(cid:122) (cid:125) pyramid BERT population risk  1 n n (cid:88) i =1 L ( x i , y i ) (cid:124) (cid:123)(cid:122) (cid:125) BERT training error + (cid:12)(cid:12)(cid:12)(cid:12) E x ,y  p Z [ L ( x , y, (cid:101) S , S )]  1 n n (cid:88) i =1 L ( x i , y i , (cid:101) S i , S i ) (cid:12)(cid:12)(cid:12)(cid:12) (cid:124) (cid:123)(cid:122) (cid:125) pyramid BERT generalization error + 1 n n (cid:88) i =1 (cid:12)(cid:12)(cid:12)(cid:12) L ( x i , y i )  L ( x i , y i , (cid:101) S i , S i ) (cid:12)(cid:12)(cid:12)(cid:12) (cid:124) (cid:123)(cid:122) (cid:125) pyramid BERT token selection loss . (2) For ease of notation, we write L w as L . The above bound follows immediately from the triangle inequality. For the first two terms in the above bound: the BERT training error is a constant for fixed parameters w , and the generalization error of models like BERT is known to be small (Hao et al., 2019; Jakubovitz et al., 2019). Therefore, we re-define the token selection problem, Equation 1, to minimize the third term, the pyramid BERT token selection loss 1 n n (cid:88) i =1 min {S i : | ( S ij ) | (cid:96) j } (cid:12)(cid:12)(cid:12) (cid:12) L ( x i , y i )  L ( x i , y i , (cid:101) S i , S i ) (cid:12)(cid:12)(cid:12) (cid:12) . To solve Equation 3, we first optimize a slightly different token selection algorithm T  for a model pyramid  BERT. In pyramid  the embedding sequence length is not reduced across the encoder layers. Let (cid:101) S  j and S  j denote the set of input and output embeddings of T  , where the size of the two sets is equal to the input sequence length N , | (cid:101) S  j | = | S  j | = N . Given an input set (cid:101) S  j in encoder j , the algorithm T  first selects a subset of it of size (cid:96) j , which is exactly same as S j selected by T in pyramid BERT. Next, instead of eliminating the remaining N  (cid:96) j embeddings in (cid:101) S  j as is done by T , the T  replaces them with their nearest embedding in S j to form the output set S  j . The unique embeddings of the output set S  j of pyramid  BERT are exactly same as the embeddings of output set S j of pyramid BERT, that is unique(S  j ) = S j . We make the following observation. Remark 1 A pyramid  BERT can be reduced to a pyramid BERT with a weighted self attention network. The weighted self attention network weighs attention scores according to the duplicity of the tokens in the embeddings of pyramid  BERT. Given the above remark, we optimize the token selection problem for pyramid  BERT. In the theorem below, we give an upper bound for the token selection loss stated in (3) for pyramid  BERT. The proof relies on  -Lipschitz continuity of the encoder and classification layers. A function f is  -Lipschitz continuity if, (cid:107) f ( x )  f ( x (cid:48) ) (cid:107)   (cid:107) x  x (cid:48) (cid:107) , for all x, x (cid:48)  domain(f) . Theorem 1 If the classification layer is  C Lipschitz, and for all j  [ L ] , the encoder E j is  j -Lipschitz continuous for all its parameters, and T  is a token selection algorithm such that the unique elements of the output embedding set unique(S  j ) is a  -cover of the input embedding set (cid:101) S  j , and the N  (cid:96) j remaining elements in (cid:101) S  j \ S  j are replaced in S  j by their nearest elements in unique(S  j ) , then for all i such that x i is bounded, the following holds: (cid:12)(cid:12)(cid:12) L ( x i , y i )  L ( x i , y i , (cid:101) S  i , S  i ) (cid:12)(cid:12)(cid:12)   CL (cid:88) j =1 (cid:18) ( N  (cid:96) j ) L (cid:89) a = j  a (cid:19) . We visualize the concept of  -cover in Figure 3. The set of red points (i.e., token embeddings in our case) with radius  covers the entire set of points. Theorem 1 suggests that we can bound the token selection loss of algorithm T  for pyramid  BERT with the  -cover core-set token selection. The loss Figure 3: Illustration of  cover core-set. goes to zero as the covering radius  goes to zero. A proof of the theorem is given in Appendix A.2. From Remark 1, the optimal choice of token selection for pyramid BERT is same as the optimal choice of unique tokens selected in pyramid  BERT, up to weighing of self-attention. However, in numerical experiments we found that fine-tuning pyramid BERT with the core-set based token selection performs better than weighing the self-attention. The  -cover core-set token selection problem is equivalent to the k -Center problem (also called min-max facility location problem) (Wolf, 2011). We explain how we solve the k-Center problem using a greedy approximation algorithm in 5.1. Given a pre-trained BERT, we create a fine-tuned pyramid BERT as follows. For the core-set selection module shown in Figure 2, we implement a k -Center-greedy-batchm algorithm, Section 5.1, to approximately select the core-set of embeddings. We fine-tune all the trainable parameters of the pyramid BERT for different choices of sequence-length configurations (cid:96) , according to approach given in Section 5.2. We select the optimal configuration (cid:96) satisfying the required inference speed-up or the space complexity reduction. The selected optimal choice of (cid:96) is kept fixed during inference. We note that our practical implementation of pyramid BERT, proposed here, is not exactly the same as the theoretical token selection algorithm analyzed in the previous section. In Appendix A.1, we justify the differences between the two. The  -cover core-set problem is equivalent to k Center problem which is NP-Hard. However, it is possible to obtain a 2  OPT solution of k -Center using a greedy approach (Cook et al., 2009). The greedy approach selects the core-set of size k one-by-one, making it un-parallelizable, and hence runs 8802 Algorithm 1: k -Center-greedy-batchm Data: Input set (cid:101) S , the number of centers to add per iteration m . slow on GPUs. For pyramid BERT, we developed a parallelizable version of this greedy approach, Algorithm 1, which selects m centers at a time. For the sequence-length configuration (cid:96) , we restrict the sequences to be exponentially decaying. Specifically, a valid sequence is determined by two parameters. The target pruning ratio 0 < p < 1 , and the index of the layer after which we stop reducing the sequence length 1  i prune-upto  L . The sequence lengths are defined as l j = (cid:24) N  p min( j,i prune-upto ) i prune-upto (cid:25) , j = 0 , 1 ,    , L, (5) where j = 0 corresponds to the input layer. We found that this strategy provides a good balance between the need to reduce the length quickly while retaining information. It involves hyperparameter tuning with two HPs: p, i prune-upto , and allows for an efficient training procedure. In Appendix B we provide a study comparing this restriction to possible alternatives showing its advantages. In addition we discuss how it compares to recent approaches (Goyal et al., 2020; Ye et al., 2021). We plug-in our core-set based token selection method and the other competitive methods into encoder layers of a backbone Transformer, and after fine-tuning evaluate their performance on a wide range of natural language classification tasks. Specifically, we conduct the evaluations on two popular benchmarks: (1) the General Language Understanding Evaluation (GLUE) benchmark (Wang et al., 2018), and (2) the Long Rang Arena (LRA), a collection of challenging long range context tasks (Tay et al., 2020). For the backbone Transformer, we choose BERT Base (De-vlin et al., 2018) for the GLUE benchmarks, and two state-of-the-art long-text Transformers Big Bird (Zaheer et al., 2020) and Performers (Choro-manski et al., 2020) for the LRA. For dataset statistics such as the number of classes and input sequence length, and the details of the backbone Transformers, see Appendix C. For sequence-length configurations, we generate a set F of 30 sequence-length configurations using Equation 5, the details of which are listed in Table 9 Appendix C. The high level idea is to cover multiple tradeoffs between efficiency and accuracy. For each token selection method, we show the predictive performance for 1 . 5 X , 2 X , 3 X , and 3 . 5 X speedup. Similarly, we show the predictive performance for 30% and 70% space complexity reductions of the attention layer. The reason we consider the space reduction for the attention layer alone is that its quadratic complexity serves the main bottleneck for long sequences. For details on how to get the performance at different speedup and mathematical formula for computing speedup and space complexity reduction, see Appendix C. 6.1 Baseline Methods We compare our method with following five methods: (1) Attention-select ( Att ): An attention based mechanism from Goyal et al. (2020). (2) Average-pool ( Pool ): A strided mean pooling applied to each sliding window of the sequence (Dai et al., 2020).(3) First-k-select ( 1st ): Selects the first k tokens, a strategy often considered with long documents. (4) Input-first-k-select ( 1st-I ): Selects the first k tokens, but rather than gradually reducing the sequence length in the encoder layers, performs a single truncation directly on the input. (5) Random-select ( Rand ): Selects a random subset of tokens. For all of the methods (including ours), the CLS token is always retained during the token selection. For our core-set based token selection, we try 6 values of m  { 1 , (cid:100) 0 . 1 k (cid:101) , (cid:100) 0 . 2 k (cid:101) , (cid:100) 0 . 3 k (cid:101) , (cid:100) 0 . 4 k (cid:101) , ( k  1) } where k = l j , for j = 1 , 2 ,    , L . In particular, m = k  1 selects all k  1 tokens (centers) in one iteration given the first selected token is always the CLS token. And m = 1 selects one token (center) per iteration which corresponds to the most fine-grained but also the slowest token selection strategy. We denote the strategy of m = k  1 as Coreset-select-k-1 ( CSk -1 ), and the others as 8803 Coreset-select-x where x  { 1 , 0 . 1 , 0 . 2 , 0 . 3 , 0 . 4 } . We use Coreset-select-opt ( CS-opt ) to represent the best value from the Coreset-select-k-1 and Coreset-select-x . In what follows, in tables presenting results we refer to the methods by their shortened (bold) names. To fairly evaluate our method against the baselines, we use the same set of hyperparameters for all the methods, for a given dataset. For details, see Appendix D. The code for Pyramid-BERT is made available as a supplementary material with the submission. The training and inference jobs are run separately on a NVIDIA Tesla V 100 GPU machine and a Intel Xeon Platinum 8000 series CPU machine respectively. All the accuracy and speedup scores are averaged over 20 trials. We first examine the trade-off between accuracy and speedup. The accuracy results for 3 X and 1 . 5 X speedup are summarized in Table 1 and 2 respectively. The results for 3 . 5 X and 2 X speedup are given in the Table 11 and 13 in Appendix E. We observe that as the speedup increases the gap between our Coreset-select-opt and its competitors becomes large, where for 3 X speedup, Coreset-select-opt outperforms the second best method Attention-select by 1% accuracy in average and beats the standard baselines by 2% or more. The Average-pool performs the worst in average across the GLUE benchmarks, specially on the COLA dataset. For detailed justification, see Appendix E. To better understand the performance of Coreset-select-opt with different values of m , an ablation study is shown in Section 7. For mild speedup of 1 . 5 X , we note that all methods (except Average-pool ) suffer only a small loss in accuracy and our method suffers no loss. A similar situation occurs when viewing the tradeoff between space complexity and accuracy, where we provide results for a memory reduction of 70% and 30% in the Tables 3 and 16 (in  E). We show results on the following three datasets of LRA benchmark: (1) byte-level text classification using real-world data (IMDB), (2) Pathfinder task (long range spatial dependency problem), and (3) image classification on sequences of pixels converted from CIFAR-10. For baselines, we include First-k-select and Random-select methods, but fail to include Attention-select . Attention-select requires a full attention matrix for selecting tokens which is not available in Big Bird (Zaheer et al., 2020) and Performers (Choromanski et al., 2020). In addition, the Transformers including Big Bird and Performers in LRA have shallow architectures because of no pre-training: the default number of encoders for text classification, path finder, and image classification datasets are four, four, and one, respectively. Thus, for both baselines and our method, we only reduce sequence length in the input layer , which is before the first encoder. For the sequence-length configurations, see Appendix C.2. For Average-pool , due to its worst performance on the GLUE benchmarks and the shallow architectures of the models in LRA, we exclude it from the baselines. The results of accuracy scores for space complexity reduction at 70% and 30% are presented in Table 4 and Table 18 (in Appendix E), respectively. The Coreset-select-opt here represents the Coreset-select with m = 1 because of its superior performance over other m  {(cid:100) 0 . 1 k (cid:101)} , (cid:100) 0 . 2 k (cid:101) , (cid:100) 0 . 3 k (cid:101) , (cid:100) 0 . 4 k (cid:101)} . We observe a similar pattern as discussed in GLUE benchmark evaluations: at high space complexity reduction 70% , Coreset-select-opt significantly outperforms its competitors First-k-select and Random-select by 12% and 2 . 5% in average for Big Bird ( 12 . 3% and 5 . 5% in average for Performers ). Moreover, on CIFAR-10, our Coreset-select-opt is even better than the Big Bird and Performers without any sequence reduction with accuracy gain 2 . 4% and 2 . 6% , respectively (simi-larly for Performers on PATHFINDER-32). On the other hand, different from the GLUE evaluations, Coreset-select-k-1 does not show any significant advantages over the baseline methods. Our conjecture is that the input in the LRA datasets contain too many noisy or low level information which is not helpful for predicting the target. For an example, each pixel of an image (CIFAR-10) or a character in the byte-level text classification represents a token as the input. Our Coreset-select based strategy with m = 1 does the most fine-grained token-level selection than its baselines and thus filter out the noisy information. Note, we do not include accuracy and speedup tables because of insignificant gains observed in speedup due to the shallow architectures of Transformers in LRA. We conduct four ablation studies to better study pyramid-BERT: (1) Performance comparisons for Coreset-select with different values of m , the number of centers to add per iteration. (2) Justification on the token importance measured by the Coreset-select . (3) Comparison of applying Coreset-select at both fine-tuning and inference versus at only inference to justify the necessity of fine-tuning in selecting tokens. (4) Exploring the position to plug-in the Coreset-select in the encoder. The result for the first ablation study is presented in Table 5 We can see that Coreset-select with m = 1 gives the best performance but with the smallest speedup for MNLI-M/MM datasets. Next, we conduct a study to validate the importance of tokens measured by our Coreset-select strategy. We consider a trained BERT that has been fine-tuned on a downstream dataset without any sequence length reduction. During inference, given a encoder j and input example consist of a sequence of tokens, we eliminate the k -th most important token measured by the core-set selection method with 1  k  L , and obtain a classification output (prediction label). The classification outputs for all input examples are then compared with those generated by BERT without any sequence length reduction. The comparison between the two classification outputs is measured by the mutual information (Shannon, 2001). Larger mutual information indicates more similarity between the two classification outputs. The importance score is specifically the order of tokens (centers) added by the core-set selection method. For a batch of size m tokens that are added at the same time, their importance is determined by the maximum distance between the token and its nearest centers that have already been added. The expectation is that the 8805 Figure 4: Demonstration of token importance measured by the Coreset-select-1 based token selection method on SST-2 dev set. importance of tokens is negatively correlated with the corresponded mutual information. For an example, reducing the least important token for each input example should make the classification outputs have the least difference from those generated without reducing any token, and thus result in the largest mutual information. A result on SST-2 dataset is presented in Figure 4. The input sequence length L is set as 64 , and thus k  [1 , 64] . The encoder index j takes value { 1 , 3 , 6 , 9 } . Since the target variable of SST-2 is a relatively balanced binary value, the largest mutual information, which corresponds to no difference between the classification outputs, is ln (2)  0 . 69 . For the token selection method, we choose Coreset-select with m = 1 . The pattern shown in the figure aligns with our expectation that the importance of tokens is negatively correlated with the mutual information. Same pattern is observed for Coreset-select-k-1 . See Figure 5. Next, we study the difference between applying Coreset-select at both fine-tuning and inference, and at only inference. Table 6 justifies the necessary of fine-tuning in sequence length reduction. Finally, we study the position to insert the Coreset-select method in the encoder. Two choices of position have been considered. The first option is to plug-in the token selection method right after the attention layer and before the feed-forward network, and the second option is to place it at the end of the encoder. The results is shown in Table 7. The experiment shows that placing the token selection method right after the attention layer gives better performance than placing it at the end of encoder. We provide pyramid-BERT, a theoretically justified technique for sequence length reduction, achieving speedup and memory reduction for both training and inference of transformers, while incurring significantly less accuracy drop than competitive methods. However, this technique can be applied only for classification and ranking tasks which use single embedding from the top layer for prediction. Also, our token selection approach requires fine-tuning the network. An interesting future study would be to eliminate the need of fine-tuning.
abstain abstain objective abstain method abstain other abstain abstain abstain abstain abstain abstain abstain objective abstain objective objective abstain method method abstain abstain abstain abstain abstain result abstain result result abstain abstain abstain result result result objective result other other other other other other other other other other method method other other other objective other other other other abstain method other other abstain method abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method method abstain method method abstain abstain abstain abstain abstain other abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method abstain abstain abstain result result abstain abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain result method abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method abstain abstain abstain abstain result abstain abstain abstain