Introduction to Transformers Introduction to Transformers: an NLP Perspective Tong Xiao xiaotong@mail.neu.edu.cn NLP Lab., Northeastern University, Shenyang, China NiuTrans Research, Shenyang, China Jingbo Zhu zhujingbo@mail.neu.edu.cn NLP Lab., Northeastern University, Shenyang, China NiuTrans Research, Shenyang, China Abstract Transformers have dominated empirical machine learning models of natural language processing. In this paper, we introduce basic concepts of Transformers and present key techniques that form the recent advances of these models. This includes a description of the standard Transformer architecture, a series of model refinements, and common applications. Given that Transformers and related deep learning techniques might be evolving in ways we have never seen, we cannot dive into all the model details or cover all the technical areas. Instead, we focus on just those concepts that are helpful for gaining a good understanding of Transformers and their variants. We also summarize the key ideas that impact this field, thereby yielding some insights into the strengths and limitations of these models. 1 arXiv:2311.17633v1 [cs.CL] 29 Nov 2023 Xiao and Zhu Contents 1 Background 4 2 The Basic Model 4 2.1 The Transformer Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Positional Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Multi-head Self-attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Layer Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Feed-forward Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Attention Models on the Decoder Side . . . . . . . . . . . . . . . . . . . . . 13 2.7 Training and Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Syntax-aware Models 17 3.1 Syntax-aware Input and Output . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Syntax-aware Attention Models . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Multi-branch Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Multi-scale Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Transformers as Syntax Learners . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Improved Architectures 29 4.1 Locally Attentive Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 Deep Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Numerical Method-Inspired Models . . . . . . . . . . . . . . . . . . . . . . . 39 4.4 Wide Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Efficient Models 45 5.1 Sparse Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2 Recurrent and Memory Models . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3 Low-dimensional Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.4 Parameter and Activation Sharing . . . . . . . . . . . . . . . . . . . . . . . 60 5.5 Alternatives to Self-Attention . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.6 Conditional Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.7 Model Transfer and Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.8 Sequence Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.9 High Performance Computing Methods . . . . . . . . . . . . . . . . . . . . 77 6 Applications 80 6.1 Language Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.2 Text Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.3 Speech Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.4 Vision Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.5 Multimodal Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7 Summary 89 2 INTRODUCTION TO TRANSFORMERS Appendices A Sinusoidal Positional Encoding 96 96 Xiao and Zhu 1. Background Transformers are a type of neural network (Vaswani et al., 2017). They were originally known for their strong performance in machine translation, and are now a de facto standard for building large-scale self-supervised learning systems (Brown et al., 2020; Devlin et al., 2019). The past few years have seen the rise of Transformers not only in natural language processing (NLP) but also in several other fields, such as computer vision and multi-modal processing. As Transformers continue to mature, these models are playing an increasingly important role in the research and application of artificial intelligence (AI). Looking back at the history of neural networks, Transformers have not been around for a long time. While Transformers are “newcomers” in NLP, they were developed on top of several ideas, the origins of which can be traced back to earlier work, such as word embedding (Bengio et al., 2003; Mikolov et al., 2013) and attention mechanisms (Bahdanau et al., 2014; Luong et al., 2015). As a result, Transformers can benefit from the advancements of different sub-fields of deep learning, and provide an elegant way to combine these neural models. On the other hand, Transformers are unique, and differ from previous models in several ways. First, they do not depend on recurrent or convolutional neural networks for modeling sequences of words, but use only attention mechanisms and feed-forward neural networks. Second, the use of self-attention in Transformers makes it easier to deal with global contexts and dependencies among words. Third, Transformers are very flexible architectures and can be easily modified to accommodate different tasks. The widespread use of Transformers motivates the development of cutting-edge techniques in deep learning. For example, there are significant refinements in self-attention mechanisms, which have been incorporated into many state-of-the-art NLP systems. The resulting techniques, together with the progress in self-supervised learning, have led us to a new era of AI: we are beginning to obtain models of universal language understanding, generation and reasoning. This has been evidenced by recent Transformer-based large language models (LLMs) which demonstrate amazing performance across a broad variety of tasks (Bubeck et al., 2023). This paper provides an introduction to Transformers while reflecting the recent developments in applying these models to different problems. However, Transformers are so successful that there have been numerous related studies and we cannot give a full description of them. Therefore, we focus this work on the core ideas of Transformers, and present a basic description of the common techniques. We also discuss some recent advances in Transformers, such as model improvements for efficiency and accuracy considerations. Because the field is very active and new techniques are coming out every day, it is impossible to survey all the latest literature and we are not attempting to do so. Instead, we focus on just those concepts and algorithms most relevant to Transformers, aimed at the people who wish to get a general understanding of these models. 2. The Basic Model Here we consider the model presented in Vaswani et al. (2017)’s work. We start by considering the Transformer architecture and discuss the details of the sub-models subsequently. 4 Introduction to Transformers 2.1 The Transformer Architecture Figure 1 shows the standard Transformer model which follows the general encoder-decoder framework. A Transformer encoder comprises a number of stacked encoding layers (or encoding blocks). Each encoding layer has two different sub-layers (or sub-blocks), called the self-attention sub-layer and the feed-forward neural network (FFN) sub-layer. Suppose we have a source-side sequence x = x1...xm and a target-side sequence y = y1...yn. The input of an encoding layer is a sequence of m vectors h1...hm, each having dmodel dimensions (or d dimensions for simplicity). We follow the notation adopted in the previous chapters, using H ∈ R m×d to denote these input vectors1. The self-attention sub-layer first performs a self-attention operation Attself(·) on H to generate an output C: C = Attself(H) (1) Here C is of the same size as H, and can thus be viewed as a new representation of the inputs. Then, a residual connection and a layer normalization unit are added to the output so that the resulting model is easier to optimize. The original Transformer model employs the post-norm structure where a residual connection is created before layer normalization is performed, like this Hself = LNorm(C + H) (2) where the addition of H denotes the residual connection (He et al., 2016a), and LNorm(·) denotes the layer normalization function (Ba et al., 2016). Substituting Eq. (1) into Eq. (2), we obtain the form of the self-attention sub-layer Layerself(H) = Hself = LNorm(Attself(H) + H) (3) The definitions of LNorm(·) and Attself(·) will be given later in this section. The FFN sub-layer takes Hself and outputs a new representation Hffn ∈ R m×d . It has the same form as the self-attention sub-layer, with the attention function replaced by the FFN function, given by Layerffn(Hself) = Hffn = LNorm(FFN(Hself) + Hself) (4) Here FFN(·) could be any feed-forward neural networks with non-linear activation functions. The most common structure of FFN(·) is a two-layer network involving two linear transformations and a ReLU activation function between them. For deep models, we can stack the above neural networks. Let Hl be the output of layer l. Then, we can express Hl as a function of Hl−1. We write this as a composition of two sub-layers Hl = Layerffn(Hl self) (5) Hl self = Layerself(Hl−1 ) (6) 1. Provided hj ∈ R d is a row vector, we have H =    h1 . . . hm   . 5 Xiao and Zhu Self-Attention Layerself(·) Add & LayerNorm Feed-Forward Network Layerffn(·) Add & LayerNorm Word Position x1 . . . xm Self-Attention Layerself(·) Add & LayerNorm Encoder-Decoder Attention Layercross(·) Add & LayerNorm Feed-Forward Network Layerffn(·) Add & LayerNorm Softmax(S LWo) Word Position y0 y1 . . . yn−1 L× Encoder ×L Decoder . . . Pr(·|y0...yn−1, x1...xm) Pr(·|y0, x1...xm) . . . Figure 1: The Transformer architecture (Vaswani et al., 2017). There are L stacked layers on each of the encoder and decoder sides. An encoding layer comprises a selfattention sub-layer and an FFN sub-layer. Both of these sub-layers share the same structure which involves a core function (either Layerself(·) or Layerffn(·)), followed by a residual connection and a layer normalization unit. Each decoding layer has a similar architecture with the encoding layers, but with an additional encoder-decoder attention sub-layer sandwiched between the self-attention and FFN sub-layers. As with most sequence-to-sequence models, Transformer takes x1...xm and y0...yi−1 for predicting yi. The representation of an input word comprises a sum of a word embedding and a positional embedding. The distributions {Pr(·|y0...yi−1, x1...xm)} are generated in sequence by a Softmax layer, which operates on a linear transformation of the output from the last decoding layer. 6 Introduction to Transformers If there are L encoding layers, then HL will be the output of the encoder. In this case, HL can be viewed as a representation of the input sequence that is learned by the Transformer encoder. H0 denotes the input of the encoder. In recurrent and convolutional models, H0 can simply be word embeddings of the input sequence. Transformer takes a different way of representing the input words , and encodes the positional information explicitly. In Section 2.2 we will discuss the embedding model used in Transformers. The Transformer decoder has a similar structure as the Transformer encoder. It comprises L stacked decoding layers (or decoding blocks). Let S l be the output of the l-th decoding layer. We can formulate a decoding layer by using the following equations S l = Layerffn(Sl cross) (7) S l cross = Layercross(HL , S l−1 self) (8) S l self = Layerself(S l−1 ) (9) Here there are three decoder sub-layers. The self-attention and FFN sub-layers are the same as those used in the encoder. Layercross(·) denotes a cross attention sub-layer (or encoder-decoder sub-layer) which models the transformation from the source-side to the target-side. In Section 2.6 we will see that Layercross(·) can be implemented using the same function as Layerself(·). The Transformer decoder outputs a distribution over a vocabulary Vy at each target-side position. This is achieved by using a softmax layer that normalizes a linear transformation of S L to distributions of target-side words. To do this, we map SL to an n × |Vy| matrix O by O = S L · Wo (10) where Wo ∈ R d×|Vy| is the parameter matrix of the linear transformation. Then, the output of the Transformer decoder is given in the form    Pr(·|y0, x) . . . Pr(·|y0...yn−1, x)    = Softmax(O) =    Softmax(o1) . . . Softmax(on)    (11) where oi denotes the i-th row vector of O, and y0 denotes the start symbol ⟨SOS⟩. Under this model, the probability of x given y can be defined as usual, log Pr(y|x) = Xn i=1 log Pr(yi|y0...yi−1, x) (12) This equation resembles the general form of language modeling: we predict the word at time i given all of the words up to time i − 1. Therefore, the input of the Transformer decoder is shifted one word left, that is, the input is y0...yn−1 and the output is y1...yn. 7 Xiao and Zhu The Transformer architecture discussed above has several variants which have been successfully used in different fields of NLP. For example, we can use a Transformer encoder to represent texts (call it the encoder-only architecture), can use a Transformer decoder to generate texts (call it the decoder-only architecture), and can use a standard encoderdecoder Transformer model to transform an input sequence to an output sequence. In the rest of this chapter, most of the discussion is independent of the particular choice of application, and will be mostly focused on the encoder-decoder architecture. In Section 6, we will see applications of the encoder-only and decoder-only architectures. 2.2 Positional Encoding In their original form, both FFNs and attention models used in Transformer ignore an important property of sequence modeling, which is that the order of the words plays a crucial role in expressing the meaning of a sequence. This means that the encoder and decoder are insensitive to the positional information of the input words. A simple approach to overcoming this problem is to add positional encoding to the representation of each word of the sequence. More formally, a word xj can be represented as a d-dimensional vector xpj = xj + PE(j) (13) Here xj ∈ R d is the embedding of the word which can be obtained by using the word embedding models. PE(j) ∈ R d is the representation of the position j. Vanilla Transformer employs the sinusoidal positional encoding models which we write in the form PE(i, 2k) = sin(i · 1 100002k/d ) (14) PE(i, 2k + 1) = cos(i · 1 100002k/d ) (15) where PE(i, k) denotes the k-th entry of PE(i). The idea of positional encoding is to distinguish different positions using continuous systems. Here we use the sine and cosine functions with different frequencies. The interested reader can refer to Appendix A to see that such a method can be interpreted as a carrying system. Because the encoding is based on individual positions, it is also called absolute positional encoding. In Section 4.1 we will see an improvement to this method. Once we have the above embedding result, xp1...xpm is taken as the input to the Transformer encoder, that is, H0 =    xp1 . . . xpm    (16) Similarly, we can also define the input on the decoder side. 2.3 Multi-head Self-attention The use of self-attention is perhaps one of the most significant advances in sequence-tosequence models. It attempts to learn and make use of direct interactions between each 8 Introduction to Transformers (a) RNN (b) CNN (r = 3) (c) Self-attention Figure 2: Information flows in recurrent, convolutional and self-attention models, shown as arrow lines between positions. pair of inputs. From a representation learning perspective, self-attention models assume that the learned representation at position i (denoted by ci) is a weighted sum of the inputs over the sequence. The output ciis thus given by ci = Xm j=1 αi,jhj (17) where αi,j indicates how strong the input hiis correlated with the input hj . We thus can view ci as a representation of the global context at position i. αi,j can be defined in different ways if one considers different attention models. Here we use the scaled dot-product attention function to compute αi,j , as follows αi,j = Softmax(hih T j /β) = exp(hih T j /β) Pm k=1 exp(hih T k /β) (18) where β is a scaling factor and is set to √d. Compared with conventional recurrent and convolutional models, an advantage of selfattention models is that they shorten the computational “distance” between two inputs. Figure 2 illustrates the information flow in these models. We see that, given the input at position i, self-attention models can directly access any other input. By contrast, recurrent and convolutional models might need two or more jumps to see the whole sequence. We can have a more general view of self-attention by using the QKV attention model. Suppose we have a sequence of κ queries Q =    q1 . . . qκ   , and a sequence of ψ key-value pairs (K =    k1 . . . kψ    , V =    v1 . . . vψ   ). The output of the model is a sequence of vectors, each corresponding to a query. The form of the QKV attention is given by Attqkv(Q, K, V) = Softmax(QKT √ d )V (19) 9 Xiao and Zhu We can write the output of the QKV attention model as a sequence of row vectors C =    c1 . . . cκ    = Attqkv(Q, K, V) (20) To apply this equation to self-attention, we simply have Hq = HWq(21) Hk = HWk(22) Hv = HWv(23) where Wq,Wk,Wv ∈ R d×d represents linear transformations of H. By considering Eq. (1), we then obtain C = Attself(H) = Attqkv(Hq, Hk, Hv) = Softmax(Hq [Hk] T √ d )Hv(24) Here Softmax(Hq [Hk] T √ d ) is an m×m matrix in which each row represents a distribution over {h1, ..., hm}, that is row i = αi,1 ... αi,m (25) We can improve the above self-attention model by using a technique called multi-head attention. This method can be motivated from the perspective of learning from multiple lower-dimensional feature sub-spaces, which projects a feature vector onto multiple subspaces and learns feature mappings on individual sub-spaces. Specifically, we project the whole of the input space into τ sub-spaces (call them heads), for example, we transform H ∈ R m×d into τ matrices of size m × d τ , denoted by {Hhead 1 , ..., Hhead τ }. The attention model is then run τ times, each time on a head. Finally, the outputs of these model runs are concatenated, and transformed by a linear projection. This procedure can be expressed by C = Merge(Chead 1 , ..., Chead τ )Wc (26) (27) For each head h, Chead h = Softmax(H q h [Hk h ] T √ d )Hv h (28) H q h = HWqh (29) Hk h = HWkh (30) Hv h = HWvh (31) 10 Introduction to Transformers Here Merge(·) is the concatenation function, and AttQKV(·) is the attention function described in Eq. (20). Wq h ,Wk h ,Wv h ∈ R d× d τ are the parameters of the projections from a d-dimensional space to a d τ -dimensional space for the queries, keys, and values. Thus, H q h , Hk h , Hv h , and Chead h are all m × d τ matrices. Merge(Chead 1 , ..., Chead τ ) produces an m × d matrix. It is then transformed by a linear mapping Wc ∈ R d×d , leading to the final result C ∈ R d×d . While the notation here seems somewhat tedious, it is convenient to implement multihead models using various deep learning toolkits. A common method in Transformer-based systems is to store inputs from all the heads in data structures called tensors, so that we can make use of parallel computing resources to have efficient systems. 2.4 Layer Normalization Layer normalization provides a simple and effective means to make the training of neural networks more stable by standardizing the activations of the hidden layers in a layer-wise manner. As introduced in Ba et al. (2016)’s work, given a layer’s output h ∈ R d , the layer normalization method computes a standardized output LNorm(h) ∈ R d by LNorm(h) = g ⊙ h − µ σ + ϵ + b (32) Here µ ∈ R d and σ ∈ Rd are the mean and standard derivation of the activations. Let hk be the k-th dimension of h. µ and σ are given by µ = 1 d · X d k=1 hk (33) σ = vuut 1 d · X d k=1 (hk − µ) 2 (34) Here g ∈ R d and b ∈ Rd are the rescaling and bias terms. They can be treated as parameters of layer normalization, whose values are to be learned together with other parameters of the Transformer model. The addition of ϵ to σ is used for the purpose of numerical stability. In general, ϵ is chosen to be a small number. We illustrate the layer normalization method for the hidden states of an encoder in the following example (assume that m = 4, d = 3, g = 1, b = 0, and ϵ = 0.1). h1 h2 h3 h4     1 1 2 0.9 0.9 0 0.7 0.8 0 3 1 7     µ = 1.3, σ = 0.5 µ = 0.6, σ = 0.4 µ = 0.5, σ = 0.4 µ = 3.7, σ = 2.5 =⇒     1−1.3 0.5+0.1 1−1.3 0.5+0.1 2−1.3 0.5+0.1 0.9−0.6 0.4+0.1 0.9−0.6 0.4+0.1 0−0.6 0.4+0.1 0.7−0.5 0.4+0.1 0.8−0.5 0.4+0.1 0−0.5 0.4+0.1 3−3.7 2.5+0.1 1−3.7 2.5+0.1 7−3.7 2.5+0.1     As discussed in Section 2.1, the layer normalization unit in each sub-layer is used to standardize the output of a residual block. Here we describe a more general formulation for this structure. Suppose that F(·) is a neural network we want to run. Then, the post-norm structure of F(·) is given by Hout = LNorm(F(Hin) + Hin) (35) 11 Xiao and Zhu Core Function F(·) Add & LayerNorm . . . . . . Hin F(·) LNorm(·) Hout Hin LNorm(·) F(·) Hout (a) Post-norm (b) Pre-norm Figure 3: The post-norm and pre-norm structures. F(·) = core function, LNorm(·) = layer normalization, and ⊕ = residual connection. where Hin and Houtput are the input and output of this model. Clearly, Eq. (4) is an instance of this equation. An alternative approach to introducing layer normalization and residual connections into modeling is to execute the LNorm(·) function right after the F(·) function, and to establish an identity mapping from the input to the output of the entire sub-layer. This structure, known as the pre-norm structure, can be expressed in the form Hout = LNorm(F(Hin)) + Hin (36) Both post-norm and pre-norm Transformer models are widely used in NLP systems. See Figure 3 for a comparison of these two structures. In general, residual connections are considered an effective means to make the training of multi-layer neural networks easier. In this sense, pre-norm Transformer seems promising because it follows the convention that a residual connection is created to bypass the whole network and that the identity mapping from the input to the output leads to easier optimization of deep models. However, by considering the expressive power of a model, there may be modeling advantages in using post-norm Transformer because it does not so much rely on residual connections and enforces more sophisticated modeling for representation learning. In Section 4.2, we will see a discussion on this issue. 2.5 Feed-forward Neural Networks The use of FFNs in Transformer is inspired in part by the fact that complex outputs can be formed by transforming the inputs through nonlinearities. While the self-attention model itself has some nonlinearity (in Softmax(·)), a more common way to do this is to consider additional layers with non-linear activation functions and linear transformations. Given an input Hin ∈ R m×d and an output Hout ∈ Rm×d , the Hout = FFN(Hin) function in Transformer has the following form Hout = HhiddenWf + bf (37) Hhidden = ReLU(HinWh + bh) (38) 12 Introduction to Transformers Sub-model # of Parameters Time Complexity × Encoder Multi-head Self-attention 4d 2 O(m2 · d) L Feed-forward Network 2d · dffn + d + dffn O(m · d · dffn) L Layer Normalization 2d O(d) 2L Decoder Multi-head Self-attention 4d 2 O(n2 · d) L Multi-head Cross-attention 4d 2 O(m · n · d) L Feed-forward Network 2d · dffn + d + dffn O(n · d · dffn) L Layer Normalization 2d O(d) 3L Table 1: Numbers of parameters and time complexities of different Transformer modules under different setups. m = source-sequence length, n = target-sequence length, d = default number of dimensions of a hidden layer, dffn = number of dimensions of the FFN hidden layer, τ = number of heads in the attention models, and L = number of encoding or decoding layers. The column × means the number of times a sub-model is applied on the encoder or decoder side. The time complexities are estimated by counting the number of multiplication of floating-point numbers. where Hhidden ∈ R m×dffn is the hidden states, and Wh ∈ Rd×dffn, bh ∈ Rdffn, Wf ∈ Rdffn×d and bf ∈ R d are the parameters. This is a two-layer FFN in which the first layer (or hidden layer) introduces a nonlinearity through ReLU(·) 2 and the second layer involves only a linear transformation. It is common practice in Transformer to use a larger size of the hidden layer. For example, a common choice is dffn = 4d, that is, the size of each hidden representation is 4 times as large as the input. Note that using a wide FFN sub-layer has been proven to be of great practical value in many state-of-the-art systems. However, a consequence of this is that the model is occupied by the parameters of the FFN. Table 1 shows parameter numbers and time complexities for different modules of a standard Transformer system. We see that FFNs dominate the model size when dffn is large, though they are not the most time consuming components. In the case of very big Transform models, we therefore wish to address this problem for building efficient systems. 2.6 Attention Models on the Decoder Side A decoder layer involves two attention sub-layers, the first of which is a self-attention sublayer, and the second is a cross-attention sub-layer. These sub-layers are based on either the post-norm or the pre-norm structure, but differ by designs of the attention functions. Consider, for example, the post-norm structure, described in Eq. (35). We can define the cross-attention and self-attention sub-layers for a decoding layer to be Scross = Layercross(Henc, Sself) = LNorm(Attcross(Henc, Sself) + Sself) (39) Sself = Layerself(S) = LNorm(Attself(S) + S) (40) 2. ReLU(x) = max{0, x}. 13 Xiao and Zhu where S ∈ R n×d is the input of the self-attention sub-layer, Scross ∈ R n×d and Sself ∈ Rn×d are the outputs of the sub-layers, and Henc ∈ R m×d is the output of the encoder 3. As with conventional attention models, cross-attention is primarily used to model the correspondence between the source-side and target-side sequences. The Attcross(·) function is based on the QKV attention model which generates the result of querying a collection of key-value pairs. More specifically, we define the queries, keys and values as linear mappings of Sself and Henc, as follows S q self = SselfWq cross (41) Hk enc = HencWk enc (42) Hv enc = HencWv enc (43) where Wq cross,Wk enc,Wvenc ∈ R d×d are the parameters of the mappings. In other words, the queries are defined based on Sself, and the keys and values are defined based on Henc. Attcross(·) is then defined as Attcross(Henc, Sself) = Attqkv(S q self, Hk enc, Hvenc) = Softmax(S q self[Hk enc] T √ d )Hv enc (44) The Attself(·) function has a similar form as Attcross(·), with linear mappings of S taken as the queries, keys, and values, like this Attself(S) = Attqkv(S q , S k , S v ) = Softmax(S q [S k ] T √ d + M)S v (45) where S q = SWq dec, S k = SWk dec, and S v = SWv dec are linear mappings of S with parameters Wq dec,Wk dec,Wv dec ∈ R d×d . This form is similar to that of Eq. (20). A difference compared to self-attention on the encoder side, however, is that the model here needs to follow the rule of left-to-right generation (see Figure 2). That is, given a target-side word at the position i, we can see only the target-side words in the left context y1...yi−1. To do this, we add a masking variable M to the unnormalized weight matrix S q [S k]T √ d +M. Both M and S q [S k]T √ d +M are of size n×n, and so a lower value of an entry of M means a larger bias towards lower alignment scores for the corresponding entry of S q [S k]T √ d + M. In order to avoid access to the right context given i, M is defined to be M(i, k) = ( 0 i ≤ k −∞ i > k (46) 3. For an encoder having L encoder layers, Henc = HL. 14 Introduction to Transformers i − 3 i − 2 i − 1 i i + 1 (a) Encoder-side Self-attention i − 3 i − 2 i − 1 i i + 1 (b) Decoder-side Self-attention Table 2: Self-attention on the encoder and decoder sides. Each line connects an input and an output of the self-attention model, indicating a dependency of an output state on an input state. For encoder self-attention, the output at any position is computed by having access to the entire sequence. By contrast, for decoder selfattention, the output at position i is computed by seeing only inputs at positions up to i. where M(i, k) indicates a bias term for the alignment score between positions i and k. Below we show an example of how the masking variable is applied (assume n = 4). Softmax(S q [S k ] T √ d + M) = Softmax(     2 0.1 1 1 0 0.9 0.9 0.9 0.2 0.8 0.7 2 0.3 1 0.3 3     +     0 −∞ −∞ −∞ 0 0 −∞ −∞ 0 0 0 −∞ 0 0 0 0     ) = Softmax(     2 −∞ −∞ −∞ 0 0.9 −∞ −∞ 0.2 0.8 0.7 −∞ 0.3 1 0.3 3     ) =     1 0 0 0 0.3 0.7 0 0 0.2 0.4 0.4 0 0.05 0.1 0.05 0.8     (47) As noted in Section 2.3, it is easy to improve these models by using the multi-head attention mechanism. Also, since decoders are typically the most time-consuming part of practical systems, the bulk of the computational effort in running these systems is very much concerned with the efficiency of the attention modules on the decoder side. 2.7 Training and Inference Transformers can be trained and used in a regular way. For example, we can train a Transformer model by performing gradient descent to minimize some loss function on the training data, and test the trained model by performing beam search on the unseen data. 15 Xiao and Zhu Below we present some of the techniques that are typically used in the training and inference of Transformer models. • Learning Rate Scheduling. As standard neural networks, Transformers can be directly trained using back-propagation. The training process is generally iterated many times to make the models fit the training data well. In each training step, we update the weights of the neural networks by moving them a small step in the direction of negative gradients of errors. There are many ways to design the update rule of training. A popular choice is to use the Adam optimization method (Kingma and Ba, 2014). To adjust the learning rate during training, Vaswani et al. (2017) present a learning rate scheduling strategy which increases the learning rate linearly for a number of steps and then decay it gradually. They design a learning rate of the form lr = lr0 · min n −0.5 step , nstep · (nwarmup) −1.5 (48) where lr0 denotes the initial learning rate, and nstep denotes the number of training steps we have executed, and nwarmup denotes the number of warmup steps. In the first nwarmup steps, the learning rate lr grows larger as training proceeds. It reaches the highest value at the point of nstep = nwarmup, and then decreases as an inverse square root function (i.e., lr0 · n −0.5 step ). • Batching and Padding. To make a trade-off between global optimization and training convergency, it is common to update the weights each time on a relatively small collection of samples, called a minibatch of samples. Therefore, we can consider a batch version of forward and backward computation processes in which the whole minibatch is used together to obtain the gradient information. One advantage of batching is that it allows the system to make use of efficient tensor operations to deal with multiple sequences in a single run. This requires that all the input sequences in a minibatch are stored in a single memory block, so that they can be read in and processed together. To illustrate this idea, consider a minimatch containing four samples whose source-sides are A B C D E F M N R S T W X Y Z We can store these sequences in a 4 ×6 continuous block where each “row” represents a sequence, like this A B C D E F M N □ □ □ □ R S T □ □ □ W X Y Z □ □ Here padding words □ are inserted between sequences, so that these sequences are aligned in the memory. Typically, we do not want padding to affect the operation of 16 Introduction to Transformers the system, and so we can simply define □ as a zero vector (call it zero padding). On the other hand, in some cases we are interested in using padding to describe something that is not covered by the input sequences. For example, we can replace padding words with the words in the left (or right) context of a sequence, though this may require modifications to the system to ensure that the newly added context words do not cause additional content to appear in the output. • Search and Caching. At test time, we need to search the space of candidate hypotheses (or candidate target-side sequences) to identify the hypothesis (or target-side sequence) with the highest score. yˆ = arg max y score(x, y) (49) where score(x, y) is the model score of the target-side sequence y given the source-side sequence x. While there are many search algorithms to achieve this, most of them share a similar structure: the search program operates by extending candidate targetside sequences in a pool at a time. In this way, the resulting algorithm can be viewed as a left-to-right generation procedure. Note that all of the designs of score(x, y), no matter how complex, are based on computing Pr(y|x). Because the attention models used in Transformer require computing the dot-product of each pair of the input vectors of a layer, the time complexity of the search algorithm is a quadratic function of the length of y. It is therefore not efficient to repeatedly compute the outputs of the attention models for positions that have been dealt with. This problem can be addressed by caching the states of each layer for words we have seen. Figure 4 illustrates the use of the caching mechanism in a search step. All the states for positions < i are maintained and easily accessed in a cache. At position i, all we need is to compute the states for the newly added word, and then to update the cache. 3. Syntax-aware Models Although Transformer is simply a deep learning model that does not make use of any linguistic structure or assumption, it may be necessary to incorporate our prior knowledge into such systems. This is in part because NLP researchers have long believed that a higher level of abstraction of data is needed to develop ideal NLP systems, and there have been many systems that use structure as priors. However, structure is a wide-ranging topic and there are several types of structure one may refer to See (2018)’s work. For example, the inductive biases used in our model design can be thought of as some structural prior, while NLP models can also learn the underlying structure of problems by themselves. In this sub-section we will discuss some of these issues. We will focus on the methods of introducing linguistic structure into Transformer models. As Transformer can be applied to many NLP tasks, which differ much in their input and output formats, we will primarily discuss modifications to Transformer encoders (call them syntax-aware Transformer encoders). Our discussion, however, is general, and the methods can be easily extended to Transformer decoders. 17 Xiao and Zhu ... y0 ... y1 Cache ... y1 ... y2 (b) decoding step 2 ... y0 ... y1 (a) decoding step 1 ... y0 ... y1 ... y1 ... y2 Cache ... y2 ... y3 (c) decoding step 3 Figure 4: Illustration of the caching mechanism in Transformer decoders. Rectangles indicate the states of decoding layers or sub-layers. At step i, all the states at previous steps are stored in a cache (see dotted boxes), and we only need to compute the states for this step (see blue rectangles and arrows). Then, we add the newly generated states to the cache, and move on to step i + 1. 3.1 Syntax-aware Input and Output One of the simplest methods of incorporating structure into NLP systems is to modify the input sequence, leaving the system unchanged. As a simple example, consider a sentence where each word xj is assigned a set of κ syntactic labels {tag1 j , ...,tagκ j } (e.g., POS labels and dependency labels). We can write these symbols together to define a new “word” xj/tag1 j/.../tagκj Then, the embedding of this word is given by xpj = e(xj/tag1 j/.../tagκj ) + PE(j) (50) where e(xj/tag1 j /.../tagκ j ) ∈ R d is the embedding of xj/tag1 j /.../tagκ j . Since xj/tag1 j /.../tagκ j is a complex symbol, we decompose the learning problem of e(xj/tag1 j /.../tagκ j ) into easier problems. For example, we can develop κ embedding models, each producing an embedding given a tag. Then, we write e(xj/tag1 j /.../tagκ j ) as a sum of the word embedding and tag embeddings e(xj/tag1 j/.../tagκj ) = xj + e(tag1 j ) + ... + e(tagκ j ) (51) where {e(tag1 j ), ..., e(tagκ j )} are the embeddings of the tags. Alternatively, we can combine these embeddings via a neural network in the form e(xj/tag1 j/.../tagκj ) = FFNembed(xj , e(tag1 j ), ..., e(tagκ j )) (52) where FFNembed(·) is a feed-forward neural network that has one layer or two. 18 Introduction to Transformers We can do the same thing for sentences on the decoder side as well, and treat yi/tag1 i /.../tagκ i as a syntax-augmented word. However, this may lead to a much larger target-side vocabulary and poses a computational challenge for training and inference. Another form that is commonly used to represent a sentence is syntax tree. In linguistics, the syntax of a sentence can be interpreted in many different ways, resulting in various grammars and the corresponding tree (or graph)-based representations. While these representations differ in their syntactic forms, a general approach to use them in sequence modeling is tree linearization. Consider the following sentence annotated with a constituency-based parse tree S . ! VP ADJP JJ interesting VBZ ’s NP PRP It We can write this tree structure as a sequence of words, syntactic labels and brackets via a tree traversal algorithm, as follows (S (NP (PRP It )PRP )NP (VP (VBZ ’s )VBZ (ADJP (JJ interesting )JJ )ADJP )VP (. ! ). )S This sequence of syntactic tokens can be used as an input to the system, that is, each token is represented by word and positional embeddings, and then the sum of these embeddings is treated as a regular input of the encoder. An example of the use of linearized trees is tree-to-string machine translation in which a syntax tree in one language is translated into a string in another language (Currey and Heafield, 2018; Li et al., 2017). Linearized trees can also be used for tree generation. For example, we can frame parsing tasks as sequence-to-sequence problems to map an input text to a sequential representation of its corresponding syntax tree (Choe and Charniak, 2016; Vinyals et al., 2015). See Figure 5 for illustrations of these models. It should be noted that the methods described here are not specific to Transformer but could be applied to many models, such as RNN-based models. 3.2 Syntax-aware Attention Models For Transformer models, it also makes sense to make use of syntax trees to guide the process of learning sequence representations. In the previous section we saw how representations of a sequence can be computed by relating different positions within that sequence. This allows us to impose some structure on these relations which are represented by distributions of attention weights over all the positions. To do this we use the encoder self-attention with 19 Xiao and Zhu Encoder Decoder (ADJP (JJ Great )JJ (. ! ). )ADJP ⟨SOS⟩ 很好很好！ (a) Tree-to-String Machine Translation Encoder Decoder Great ! ⟨SOS⟩ (ADJP (JJ Great )JJ (. ! ). (ADJP (JJ Great )JJ (. ! ). )ADJP (b) Constituency Parsing Figure 5: Illustration of tree linearization on either the encoder or decoder side. For treeto-string machine translation, the encoder takes sequential representation of an input parse tree, and the decoder outputs the corresponding translation. For parsing, the encoder takes a sentence, and the decoder outputs the corresponding syntax tree. an additive mask AttSynself(H) = Softmax(Hq [Hk] T √ d + M)Hv (53) or alternatively with a multiplicative mask AttSynself(H) = Softmax(Hq [Hk] T √ d ⊙ M)Hv(54) where M ∈ R m×m is a matrix of masking variables in which a larger value of M(i, j) indicates a stronger syntactic correlation between positions i and j. In the following description we choose Eq. (54) as the basic form. One common way to design M is to project syntactic relations of the input tree structure into constraints over the sequence. Here we consider constituency parse trees and dependency parse trees for illustration. Generally, two types of masking methods are employed. 20 Introduction to Transformers • 0-1 Masking. This method assigns M(i, j) a value of 1 if the words at positions i and j are considered syntactically correlated and a value of 0 otherwise (Bai et al., 2021; Zhang et al., 2020). To model the relation between two words in a syntax tree, we can consider the distance between their corresponding nodes. One of the simplest forms is given by M(i, j) = ( 1 ω(i, j) ≤ ωmax 0 otherwise (55) where ω(i, j) is the length of the shortest path between the nodes of the words at positions i and j. For example, given a dependency parse tree, ω(i, j) is the number of dependency edges in the path between the two words. For a constituency parse tree, all the words are leaf nodes, and so ω(i, j) gives a tree distance between the two leaves in the same branch of the tree. ωmax is a parameter used to control the maximum distance between two nodes that can be considered syntactically correlated. For example, assuming that there is a dependency parse tree and ωmax = 1, Eq. (55) enforces a constraint that the attention score between positions i and j is computed only if they have a parent-dependent relation4. • Soft Masking. Instead of treating M as a hard constraint, we can use it as a soft constraint that scales the attention weight between positions i and j in terms of the degree to which the corresponding words are correlated. An idea is to reduce the attention weight as ω(i, j) becomes larger. A very simple method to do this is to transform ω(i, j) in some way that M(i, j) holds a negative correlation relationship with ω(i, j) and its value falls into the interval [0, 1] M(i, j) = DNorm(ω(i, j)) (56) There are several alternative designs for DNorm(·). For example, one can compute a standardized score of −ω(i, j) by subtracting its mean and dividing by its standard deviation (Chen et al., 2018a), or can normalize 1/ω(i, j) over all possible j in the sequence (Xu et al., 2021b). In cases where parsers can output a score between positions i and j, it is also possible to use this score to compute M(i, j). For example, a dependency parser can produce the probability of the word at position i being the parent of the word at position j (Strubell et al., 2018). We can then write M(i, j) as M(i, j) = Prparent(i|j) (57) or alternatively M(i, j) = max{Prparent(i|j),Prparent(j|i)} (58) where Prparent(i|j) and Prparent(j|i) are the probabilities given by the parser. See Figure 6 for an example of inducing a soft masking variable from a dependency parse tree. 4. For multiplicative masks, M(i, j) = 0 does not mean that the attention weight between j and i is zero because the Softmax function does not give a zero output for a dimension whose corresponding input is of a zero value. A method to “mask” an entry of Softmax( HHT √ d ) is to use an additive mask and set M(i, j) = −∞ if ω(i, j) > ωmax. 21 Xiao and Zhu The concert was wonderful ! (a) Dependency Parse Tree (b) Mask M (darker color means larger value) The concert was wonderful ! The concert was wonderful ! Figure 6: Priors induced from a dependency parse tree. The row i of the matrix M represents a distribution that describes how much weight we can give to M(i, j) in terms of the syntactic distance between i and j. 3.3 Multi-branch Models Introducing syntax into NLP systems is not easy. This is partially because automatic parse trees may have errors, and partially because the use of syntax may lead to strong assumption of the underlying structure of a sentence. Rather than combining syntactic and word information into one “big” model, it may be more flexible and effective to build one model to encode syntax and a different one to encode word sequences. One way to achieve this is through the use of multiple neural networks (called branches or paths), each dealing with one type of input. The outputs of these branches are then combined to produce an output (Fan et al., 2020; Lin et al., 2022b; Xie et al., 2017). Various methods have therefore been used to combine different types of input for neural models like Transformer. One commonly-used approach is to build two separate encoders, in which one model is trained to encode the syntactic input (denoted by t), and the other is trained to encode the usual input (denoted by x). Figure 7 (a) illustrates this multi-encoder architecture. The syntactic encoder Encodesyn(t) is based on models presented in Sections 3.1 and 3.2, and the text encoder Encodetext(x) is a standard Transformer encoder. The representations generated by these encoders are then fed into the combination model as input, and combined into a hybrid representation, given by Hhybrid = Combine(Hsyn, Htext) = Combine(Encodesyn(t),Encodetext(x)) (59) There are several designs for Combine(·), depending on what kind of problems we apply the encoders to. For example, if we want to develop a text classifier, Combine(·) can be a simple pooling network. For more complicated tasks, such as machine translation, Combine(·) can be a Transformer encoder as well, and we can fuse information from different sources by performing self-attention on [Hsyn, Htext]. 22 Introduction to Transformers Encodesyn(·) Encodetext(·) t x Combine(·) ... (a) Multi-encoder x ... Branch1Branch2 t (b) Multi-branch as a Sub-model x ... Head1 t (c) Multi-head Attention Figure 7: Multi-branch architectures. There are two inputs: a sentence (denoted by x) and the syntax tree of the sentence (denoted by t). In the multi-encoder architecture (see sub-figure (a)), two encoders are constructed to encode x and t, respectively. A combination model then takes the outputs of the encoders and produces a combined representation of x and t. The idea of multi-branch networks can be used for designing sub-models of the encoder. A simple example is that we create multiple paths in parallel for some layers of the encoder (see sub-figure (b)). Another example is multi-head attention (see sub-figure (c)) where we use different heads to learn different representations. While we restrict attention to syntactic models in this section, the general multi-encoder architecture can be used in many problems where inputs from additional sources are required. For example, one can use one encoder to represent a sentence, and use another encoder to represent the previous sentence in the same document. We thus have a contextaware model by combining the two encoders (Li et al., 2020a; Voita et al., 2018). Furthermore, the architectures of the encoders do not need to be restricted to Transformer, and we can choose different models for different branches. For example, as a widely-used 2-branch encoding architecture, we can use a CNN-based encoder to model local context, and a Transformer encoder to model global context (Wu et al., 2020). Sub-models of a Transformer model can also be multi-branch neural networks. See Figure 7 (b) for an example involving two self-attention branches. One is the standard self-attention network Attself(H). The other is the syntax-aware self-attention network AttSynself(H). The output of the self-attention model is a linear combination of the outputs of these two branches (Xu et al., 2021b), given by Hself = α · Attself(H) + (1 − α) · AttSynself(H) (60) 23 Xiao and Zhu where α is a coefficient of combination. Hself can be used as usual by taking a layer normalization function and adding a residual connection, and so the overall architecture is the same as standard Transformer models. Multi-head attention networks can also be viewed as forms of multi-branch models. Therefore, we can provide guidance from syntax to only some of the heads while keeping the rest unchanged (Strubell et al., 2018). This approach is illustrated in Figure 7 (c) where only one head of the self-attention sub-layer makes use of syntax trees for computing attention weights. 3.4 Multi-scale Models In linguistics, syntax studies how sentences are built up by smaller constituents. Different levels of these constituents are in general organized in a hierarchical structure, called syntactic hierarchy. It is therefore possible to use multiple levels of syntactic constituents to explain the same sentence, for example, words explain how the sentence is constructed from small meaningful units, and phrases explain how the sentence is constructed from larger linguistic units. Multi-scale Transformers leverage varying abstraction levels of data to represent a sentence using diverse feature scales. A common approach is to write a sentence in multiple different forms and then to combine them using a multi-branch network (Hao et al., 2019). For example, consider a sentence The oldest beer-making facility was discovered in China. We can tokenize it into a sequence of words, denoted by xwords = The oldest beer-making facility was discovered in China . Alternatively, we can write it as a sequence of phrases by using a parser, denoted by xphrases = [The oldest beer-making facility]NP [was discovered in China]VP [.]. The simplest way to build a multi-scale model is to encode xwords and xphrases using two separate Transformer encoders. Then, the outputs of these encoders are combined in some way. This leads to the same form as Eq. (59), and we can view this model as an instance of the general multi-encoder architecture. Both xwords and xphrases can be viewed as sequences of tokens, for example, xwords has nine word-based tokens, and xphrases has three phrase-based tokens5. However, involving all possible phrases will result in a huge vocabulary. We therefore need some method to represent each phrase as an embedding in a cheap way. By treating phrase embedding as a sequence modeling problem, it is straightforward to learn sub-sequence representations simply by considering the sequence models described in the previous chapters and this chapter. Now we have a two-stage learning process. In the first stage, we learn the embeddings 5. xphrases comprises three tokens The oldest beer-making facility, was discovered in China, and .. 24 Introduction to Transformers of input units on different scales using separate models. In the second stage, we learn to encode sequences on different scales using a multi-branch model. More generally, we do not need to restrict ourselves to linguistically meaningful units in multi-scale representation learning. For example, we can learn sub-word segmentations from data and represent an input sentence as a sequence of sub-words. This results in a hierarchical representation of the sentence, for example, sub-words → words → phrases. While the learned sub-words may not have linguistic meanings, they provide a new insight into modeling words and phrases, as well as a new scale of features. Also, we do not need to develop multiple encoders for multi-scale modeling. An alternative approach is to take representations on different scales in the multi-head self-attention attention modules, which makes it easier to model the interactions among different scales (Guo et al., 2020; Li et al., 2022b). A problem with the approaches described above, however, is that the representations (or attention weight matrices) learned on different scales are of different sizes. For example, in the above examples, the representation learned from xwords is a 9 × d matrix, and the representation learned from xphrases is a 3 × d matrix. A simple solution to this problem is to perform upsampling on the phrase-based representation to expand it to a 9 × d matrix. Likewise, we can perform downsampling on the word-based representation to shrink it to a 3 × d matrix. Then, the combination model Combine(·) can be the same as those described in Section 3.3. It is worth noting that multi-scale modeling is widely discussed in several fields. For example, in computer vision, multi-scale modeling is often referred to as a process of learning a series of feature maps on the input image (Fan et al., 2021; Li et al., 2022e). Unlike the multi-branch models presented here, the multi-scale vision Transformer models make use of the hierarchical nature of features in representing images. Systems of this kind are often based on a stack of layers in which each layer learns the features on a larger scale (e.g., a higher channel capacity) from the features produced by the previous layer. 3.5 Transformers as Syntax Learners So far we have discussed syntax trees as being constraints or priors on the encoding process so that we can make use of linguistic representations in learning neural networks. It is natural to wonder whether these neural models can learn some knowledge of linguistic structure from data without human design linguistic annotations. This reflects one of the goals of developing NLP systems: linguistic knowledge can be learned from data and encoded in models. In order to explore the linguistic properties learned by NLP systems, a simple method is to examine the syntactic behaviors of the outputs of the systems. For example, we can examine whether the outputs of language generation systems have grammatical errors. Another example is to ask these systems to accomplish tasks that make sense for linguistics, though they are not trained to do so (Brown et al., 2020). However, examining and explaining how model predictions exhibit syntactic abilities is not sufficient to answer the question. It is also the case that the neural networks have learned some knowledge about language, but it is not used in prediction (Clark et al., 2019). Therefore, we need to see what is modeled and learned inside these neural networks. 25 Xiao and Zhu ... ... Input (Pre-training) Loss (Pre-training) (a) Training the Transformer Model ... ... Input (Probing Training) Predictor Loss (Probing Training) (b) Training the Probing Predictor ... ... Input (Probing) Predictor Output (Probing) (c) Probing on New Data Figure 8: An overview of probing for Transformer-based models. Given a Transformer model (e.g., a Transformer-based language model), we first optimize the model parameters on some unlabeled data. Then, we develop a predictor which takes the states of a hidden layer of the Transformer model and generates outputs for a probing task (see sub-figure (a)). The predictor can be trained as usual in which only the parameters of the predictor are optimized and the parameters of the Transformer model are fixed (see sub-figure (b)). The Transformer model and the predictor are used together to make predictions on new data for probing (see sub-figure (c)). One approach to examining the latent linguistic structure in Transformer models is to develop probes to see whether and to what extent these models capture notions of linguistics, such as dependency relations and parts-of-speech. A general approach to probing is to extract the internal representations of the models and probe them for linguistic phenomena. For Transformer, it is usually achieved by examining the attention map and/or output of an attention layer. Then, we construct a probing predictor (or probing classifier) that takes these internal representations as input and produces linguistic notions as output (Belinkov, 2022). The probing predictor can be based on either simple heuristics or parameterized models optimized on the probing task. Recent work shows that large-scale Transformer-based language models exhibit good behaviors, called emergent abilities, in various probing tasks. However, we will not discuss details of these language modeling systems in this chapter, but leave them in the following chapters. Nevertheless, we assume here that we have a Transformer encoder that has been well trained on unlabeled data and can be used for probing. Figure 8 illustrates the process of probing. Many probing methods have been used in recent work on analyzing and understanding what is learned in neural encoders. Here we describe some of the popular ones. • Trees. Given a trained Transformer encoder, it is easy to know how “likely” two words of a sentence have some linguistic relationship by computing the attention 26 Introduction to Transformers weight between them. We can use this quantity to define a metric measuring the syntactic distance between the two words at positions i and j ds(i, j) = 1 − α(i, j) (61) By using this metric it is straightforward to construct the minimum-spanning tree for the sentence, that is, we connect all the words to form a tree structure with the minimum total distance. The tree structure can be seen as a latent tree representation of the sentence that is induced from the neural network. While this dependency-treelike structure can be used as a source of learned syntactic information in downstream tasks, it says nothing about our knowledge of syntax. An approach to aligning the representations in the encoder with linguistic structure is to learn to produce syntax trees that are consistent with human annotations. To do this, we need to develop a probing predictor that can be trained on tree-annotated data. Suppose that there is a human annotated dependency tree of a given sentence. For each pair of words, we can obtain a distance ω(i, j) by counting the number of edges between them. Then, we can learn a distance metric based on the internal representations of the encoder to approximate ω(i, j). A simple form of such a metric is defined to be the Euclidean distance (Manning et al., 2020). Let A ∈ R d×ks be a parameter matrix. The form of the Euclidean distance is given by ds(i, j) = q ||(hi − hj )A||2 2 (62) where hi and hj are the representations produced by an encoding layer at positions i and j 6 . Given a set of tree-annotated sentences S, we can optimize the model by Aˆ = arg max A X s∈S 1 |s| 2 X i∈s,j∈s ω(i, j) − d 2 s (i, j) (63) where |s| is length of the sentence s, and (i, j) indicates a pair of words in s. The optimized model is then used to parse test sentences via the minimum-spanning tree algorithm, and we can compare the parse trees against the human-annotated trees. To obtain directed trees, which are standard forms of dependency syntax, one can update the above model by considering the relative distance of a word to the root. More details can be found in Manning et al. (2020)’s work. Here the probing predictor functions similarly to a neural parser, trained to predict a syntax tree based on a representation of the input sentence. This idea can be extended to other forms of syntactic structure, such as phrase structure trees (Shi et al., 2016). • Syntactic and Semantic Labels. Many syntactic and semantic parsing tasks can be framed as problems of predicting linguistic labels given a sentence or its segments. A simple example is part-of-speech tagging in which each word of a sentence is labeled with a word class. A probe for part-of-speech tagging can be a classifier that takes a representation hj each time and outputs the corresponding word class. One general 6. In general, hi and hj are the outputs of the last layer of the encoder. Alternatively, they can be weighted sums of the outputs of all the layers. 27 Xiao and Zhu probing approach to these problems is edge probing (Tenney et al., 2019a,b). Given a sentence, a labeled edge is defined as a tuple (span1,span2, label) where span1is a span [i1, j1], and span2is another span [i2, j2] (optionally), and label is the corresponding label. Our goal is to learn a probe to predict label given span1 and span2. For example, for part-of-speech tagging, span1is a unit span [j, j] for each position j, span2is an empty span, and label is the part-of-speech tag corresponding to the j-th word of the sentence; for dependency parsing and coreference resolution, span1 and span2 are two words or entities, and label is the relationship between them; for constituency parsing, span1is a span of words, span2is an empty span, and label is the syntactic category of the tree node yielding span1. In simple cases, the probing model can be a multi-layer feed-forward neural network with a Softmax output layer. As usual, this model is trained on labeled data, and then tested on new data. • Surface Forms of Words and Sentences. Probing tasks can also be designed to examine whether the representations embed the surface information of sentences or words (Adi et al., 2016; Conneau et al., 2018). A simple sentence-level probing task is sentence length prediction. To do this, we first represent the sentence as a single vector h 7 , and then build a classifier to categorize h into the corresponding length bin. Similarly, probes can be built to predict whether two words at positions i and j are reordered in the sentence given hi and hj . Also, we can develop probes to address conventional problems in morphology. For example, we reconstruct the word at position j or predict its sense with the representation hj . In addition, probing tasks can be focused on particular linguistic problems, for example, numeracy (Wallace et al., 2019) and function words (Kim et al., 2019). • Cloze. Of course, we can probe neural models for problems beyond syntax and morphology. One perspective on large-scale pre-trained Transformer models is to view them as knowledge bases containing facts about the world. It is therefore tempting to see if we can apply them to test factual knowledge. A simple method is to ask a probe to recover the missing item of a sentence (Petroni et al., 2019). For example, if we have a cloze test Shiji was written by . we wish the probe to give an answer Sima Qian because there is a subject-objectrelation fact (Shiji, Sima Qian, written-by). This probe can simply be a masked language model that is widely used in self-supervised learning of Transformer encoders. In NLP, probing is closely related to pre-training of large language models. In general, we can see probing tasks as applications of these pre-trained language models, though probing is ordinarily used to give a quick test of the models. Ideally we would like to develop a probe that makes best use of the representations to deal with the problems. However, when 7. h can be computed by performing a pooling operation on {h1, ..., hm} 28 Introduction to Transformers a probe is complex and sufficiently well-trained, it might be difficult to say if the problem is solved by using the representations or the probe itself. A common way to emphasize the contribution of probes in problem-solving is to compare them with reasonable baselines or conduct the comparison on control tasks Belinkov (2022); Hewitt and Liang (2019). 4. Improved Architectures In this section we present several improvements to the vanilla Transformer model. Unlike the previous section, most of the improvements are from the perspective of machine learning, rather than linguistics. 4.1 Locally Attentive Models Methods of self-attention, as discussed Section 2.3, can also be viewed as learning representations of the entire input sequence. The use of this global attention mechanism can lead to a better ability to deal with long-distance dependencies, but this model has a shortcoming: local information is not explicitly captured. Here we consider a few techniques that attempt to model the localness of representations. 4.1.1 Priors of Local Modeling One of the simplest ways of introducing local models into Transformers is to add a penalty term to the attention function in order to discourage large attention weights between distant positions. On the encoder-side, this leads to a form that we have already encountered several times in this chapter. AttLocalself(H) = Softmax(Hq [Hk] T √ d − γ · G)Hv(64) where γ is the weight (or temperature) of the penalty term, and G ∈ R m×m is the matrix of penalties. Each entry G(i, j) indicates how much we penalize the model given positions i and j. A simple form of G(i, j) is a distance metric between i and j, for example G(i, j) = |i − j| (65) Or G(i, j) can be defined as a Gaussian penalty function (Yang et al., 2018) G(i, j) = (i − j) 2 2σ 2 i (66) where σiis the standard deviation of the Gaussian distribution. For different j, both of the above penalty terms increase, linearly or exponentially, away from the maximum at i with distance |i − j|. This method can be extended to the cross-attention model, like this AttLocalcross(H, S) = Softmax(S q [Hk] T √ d − γ · G)Hv(67) 29 Xiao and Zhu where G is an n × m matrix. Each entry of G can be defined as G(i, j) = (µi − j) 2 2σ 2 i (68) where µiis the mean of the Gaussian distribution over the source-side positions. Both µi and σi can be determined using heuristics. Alternatively, we can develop additional neural networks to model them and learn corresponding parameters together with other parameters of the Transformer model. For example, we can use a feed-forward neural network to predict µi given si. One alternative to Eq. (64) (or Eq. (67)) treats the penalty term as a separate model and combines it with the original attention model. For example, we can define the selfattention model as AttLocalself(H) = (1 − β) · Softmax(Hq [Hk] T √ d ) + β · Softmax(−γ · G) Hv(69) where β ∈ [0, 1] is the coefficient of the linear combination. Note that, to avoid empirical choices of the values of α and β, we can use gating functions to predict α and β and train these functions as usual. Another alternative is to use a multiplicative mask to incorporate the prior into modeling, as in Eq. (54). This is given by AttLocalself(H) = Softmax(Hq [Hk] T √ d ⊙ G′)Hv(70) Here G′ ∈ [0, 1]m×m is a matrix of scalars. The scalar G′(i, j) gives a value of 1 when i = j, and a smaller value as j moves away from i. G′(i, j) can be obtained by normalizing −G(i, j) over all j or using alternative functions. 4.1.2 Local Attention The term local attention has been used broadly to cover a wide range of problems and to refer to many different models in the NLP literature. The methods discussed above are those that impose soft constraints on attention models. In fact, local attention has its origins in attempts to restrict the scope of attention models for considerations of modeling and computational problems (Luong et al., 2015). Research in this area often looks into introducing hard constraints, so that the resulting models can focus on parts of the input and ignore the rest. For example, we can predict a span of source-side positions for performing the attention function given a target-side position (Sperber et al., 2018; Sukhbaatar et al., 2019; Yang et al., 2018). Also, attention spans can be induced from syntax trees, for example, knowing sub-tree structures of a sentence may help winnow the field that the model concentrates on in learning the representation. Thus, many of the syntax-constrained models are instances of local attention-based models (see Section 3.4) . In addition, the concept of local attention can be extended to develop a rich set of models, such as sparse attention models, although these models are often discussed in the context of efficient machine learning methods. We will see a few examples of them in Section 5. 30 Introduction to Transformers In deep learning, one of the most widely used models for learning features from a restricted region of the input is CNNs. It is thus interesting to consider methods of combining CNNs and Transformer models to obtain the benefits of both approaches, for example, CNNs deal with short-term dependencies, and self-attention models deal with long-term dependencies. One approach is to build a two-branch sequence model where one branch is based on CNNs and the other is based on self-attention models (Wu et al., 2020). Another approach is to incorporate CNN layers into Transformer blocks in some way that we can learn both local and global representations through a deep model (Gulati et al., 2020; Wu et al., 2019). 4.1.3 Relative Positional Embedding Relative positional embedding, also known as relative positional representation (RPR), is an improvement to the absolute positional embedding method used in standard Transformer systems (Huang et al., 2018; Shaw et al., 2018). The idea of RPR is that we model the distance between two positions of a sequence rather than giving each position a fixed representation. As a result, we have a pair-wise representation PE(i, j) for any two positions i and j. One simple way to define PE(i, j) is to consider it as a lookup table for all pairs of i and j. More specifically, let uπ be a d-dimensional representation for a given distance π. The form of PE(i, j) in the vanilla RPR method is given by PE(i, j) = uclip(j−i,krpr)(71) where clip(x, krpr) is a function that clips x in the interval [−krpr, krpr] clip(x, krpr) = max{−krpr, min{x, krpr}} (72) Thus, we have a model with parameters Urpr =         u−krpr . . . u0 . . . ukrpr         (73) While this matrix notation is used in a relatively informal way, we can view Urpr as a matrix ∈ R (2krpr+1)×d , and select a row corresponding to clip(j − i, krpr) when RPR is required for given i and j. Using the above method, we can define three RPR models PEq(i, j), PEk(i, j) and PEv(i, j) for queries, keys, and values, respectively. Then, following the form of Eq. (17), the output of the self-attention model at position i can be written as ci = Xm j=1 αi,j h v j + PEv (i, j) = Xm j=1 αi,jh v j + Xm j=1 αi,jPEv(i, j) (74) 31 Xiao and Zhu Self-attention Sub-layer FFN Sub-layer Self-attention Sub-layer FFN Sub-layer · · · block 1 block 2 x1 x2 · · · xm + + + PE(1) PE(2) · · · PE(m) (a) Transformer without RPR Self-attention Sub-layer FFN Sub-layer Self-attention Sub-layer FFN Sub-layer · · · block 1 block 2 x1 x2 · · · xm + + + PE(1) PE(2) · · · PE(m) 1 2 · · · m u−3 u−3 u−2 u−1 u0 u−3 u−2 u−1 u0 u1 u−2 u−1 u0 u1 u2 u−1 u0 u1 u2 u3 u0 u1 u2 u3 u3 5 4 3 2 1 j 1 2 3 4 5 i PE(i, j) (krpr = 3) · · · . . . · · · (b) Transformer with RPR Figure 9: Transformer encoders without and with relative positional representation (RPR). In RPR, each pair of positions is represented as a vector PE(i, j) using a model parameterized by Urpr. PE(i, j) is fed into each self-attention sub-layer so that we can make use of the positional information in intermediate steps of learning representations. where h v j is the j-th row vector of Hv P . This representation comprises two components: m j=1 αi,jh v j is the basic representation, and Pm j=1 αi,jPEv (i, j) is the positional representation. The attention weight αi,j is computed in a regular way, but with additional terms PEq(i, j) and PEk(i, j) added to each query and key. αi,j = Softmax( [h q i + PEq (i, j)][h k j + PEk (i, j)]T √ d ) (75) Figure 9 shows the Transformer encoder architectures with and without RPR. When RPR is adopted, PEq(i, j), PEk(i, j), PEv(i, j) are directly fed to each self-attention sublayer, and so we can make better use of positional information for sequence modeling. Note that, the use of the clipping function (see Eq. (72)) makes the modeling simple because we do not need to distinguish the relative distances for the cases |j − i| ≥ krpr. This clipped distance-based model can lead, in turn, to better modeling in local context windows. 32 Introduction to Transformers Eqs. (74) and (75) provide a general approach to position-sensitive sequence modeling. There are many variants of this model. In Shaw et al. (2018)’s early work on RPR, the positional representations for queries are removed, and the model works only with PEk(i, j) and PEv(i, j), like this αi,j = Softmax( h q i [h k j + PEk (i, j)]T √ d ) (76) By contrast, there are examples that attempt to improve the RPR model in computing attention weights but ignore PEv(i, j) in learning values (Dai et al., 2019; He et al., 2021). Instead of treating RPR as an additive term to each representation, researchers also explore other ways of introducing RPR into Transformer (Huang et al., 2020; Raffel et al., 2020). We refer the interested readers to these papers for more details. 4.2 Deep Models Many state-of-the-art NLP systems are based on deep Transformer models. For example, recent large language models generally comprise tens of Transformer layers (or more precisely, hundreds of layers of neurons), demonstrating strong performance on many tasks (Ouyang et al., 2022; Touvron et al., 2023a). By stacking Transformer layers, it is straightforward to obtain a deep model. However, as is often the case, training very deep neural networks is challenging. A difficulty arises from the fact that the error surfaces of deep neural networks are highly non-convex and have many local optima that make the training process likely to get stuck in them. While there are optimization algorithms that can help alleviate this problem, most of the practical efforts explore the use of gradient-based methods for optimizing deep neural networks. As a result, training a model with many Transformer layers becomes challenging due to vanishing and exploding gradients during back-propagation. Here we consider several techniques for training deep Transformer models. 4.2.1 Re-thinking the Pre-Norm and Post-Norm Architectures As introduced previously, a Transformer sub-layer is a residual network where a shortcut is created to add the input of the network directly to the output of this sub-layer. This allows gradients to flow more directly from the output back to the input, mitigating the vanishing gradient problem. In general, a residual connection in Transformer is used together with a layer normalization unit to form a sub-layer. This leads to two types of architecture, called post-norm and pre-norm. To be specific, recall from Section 2.4 that the post-norm architecture can be expressed as z l = LNorm(Fl (z l−1 ) + z l−1 ) (77) where z l and zl−1 are the output and input of the sub-layer l, and Fl (·) is the core function of this sub-layer. The pre-norm architecture takes the identity mapping z l outside the layer normalization function, given in the form z l = LNorm(Fl (z l−1 )) + z l−1 (78) Consider the difference between the information flow in these two architectures: 33 Xiao and Zhu • The post-norm architecture prevents the identity mapping of the input from adding to the output of the sub-layer. This is not a true residual network, because all the information is passed on through a non-linear function (i.e., the layer normalization unit). Thus, the post-norm architecture is not very “efficient” for back-propagation. Wang et al. (2019) show that the gradient of the loss of an L sub-layer Transformer network with respect to z l is given by ∂E ∂z l = ∂E ∂z L · L Y−1 k=l ∂LNorm(v k ) ∂vk · L Y−1 k=l 1 + ∂Fk(z k ) ∂z k (79) where z L is the output of the last layer, vk is a short for F k (z k−1 ), and E is the error measured by some loss function. ∂LNorm(v k) ∂vk and ∂Fk(z k) ∂z k are the gradients of the layer normalization function and the core function, respectively. Although the equation here appears a bit complex, we see that QL−1 k=l ∂LNorm(v k) ∂vk is simply a product of L − l factors. This means that the error gradient will be rescaled more times if L becomes larger, and there is a higher risk of vanishing and exploding gradients for a deeper model. • The pre-norm architecture describes a standard residual neural network where the input of a whole network is added to its output. We can write the gradient of the error at z l as ∂E ∂z l = ∂E ∂z L · 1 + L Y−1 k=l ∂Fk(LNorm(z k )) ∂z k ! = ∂E ∂z L + ∂E ∂z L · L Y−1 k=l ∂Fk(LNorm(z k )) ∂z k (80) It is easy to see that ∂E ∂z l receives direct feedback regarding the errors made by the model, because the first term of the summation on the right-hand side (i.e., ∂E ∂zL ) is the gradient of the model output which is independent of the network depth. The use of the pre-norm architecture also helps optimization during early gradient descent steps. For example, it has been found that pre-norm Transformer models can be trained by using a larger learning rate in the early stage of training instead of gradually increasing the learning rate from a small value (Xiong et al., 2020). While the pre-norm architecture leads to easier optimization of deep Transformer models, we would not simply say that it is a better choice compared to the post-norm architecture. In fact, both post-norm and pre-norm Transformer models have been successfully used in many applications. For example, the post-norm architecture is widely used in BERTlike models, while the pre-norm architecture is a more popular choice in recent generative large language models. Broadly, these two architectures provide different ways to design a deep Transformer model, as well as different advantages and disadvantages in doing so. The post-norm architecture forces the representation to be learned through more non-linear functions, but in turn results in a complicated model that is relatively hard to train. By contrast, the pre-norm architecture can make the training of Transformer models easier, but 34 Introduction to Transformers would be less expressive than the post-norm counterpart if the learned models are overly dependent on the shortcut paths. An improvement to these architectures is to control the extent to which we want to “skip” a sub-layer. A simple way to do this is to weight different paths rather than treating them equally. For example, a scalar factor of a residual connection can be introduced to determine how heavily we weight this residual connection relative to the path of the core function (He et al., 2016b; Liu et al., 2020a,b). A more general form of this model is given by z l = LNorm(Fl (z l−1 ) + β · z l−1 ) + γ · z l−1 (81) where β is the weight of the identity mapping inside the layer normalization function, and γ is the weight of the identity mapping outside the layer normalization function. Clearly, both the post-norm and pre-norm architectures can be seen as special cases of this equation. That is, if β = 1 and γ = 0, then it will become Eq. (77); if β = 0 and γ = 1, it will become Eq. (78). This model provides a multi-branch view of building residual blocks. The input to this block can be computed through multiple paths with different modeling complexities. When β and γ are small, the representation is forced to be learned through a “deep” model with multiple layers of cascaded non-linear units. In contrast, when β and γ are large, the representation is more likely to be learned using a “shallow” model with fewer layers. To determine the optimal choices of β and γ, one can give them fixed values by considering some theoretical properties or system performance on validation sets, or compute these values by using additional functions that can be trained to do so (Srivastava et al., 2015). It should be emphasized that many other types of architecture can be considered in the design of a Transformer sub-layer. It is possible, for instance, to introduce more layer normalization units into a sub-layer (Ding et al., 2021; Wang et al., 2022b), or, on the contrary, to simply remove them from a sub-layer (Bachlechner et al., 2021). 4.2.2 Parameter Initialization As with other deep neural networks, there is interest in developing parameter initialization methods for deep Transformer models in order to perform optimization on some region around a better local optimum. However, initialization is a wide-ranging topic for optimization of machine learning models, and the discussion of this general topic lies beyond the scope of this section. Here we will discuss some of the parameter initialization methods used in Transformer-based systems rather than the general optimization problems. While the parameters of a neural network can be set in various different ways, most practical systems adopt simple techniques to give appropriate initial values of model parameters. Consider, for example, the Xavier initialization for a parameter matrix W ∈ R din×dout (Glorot and Bengio, 2010). We define a variable η by η = gain · r 6 din + dout (82) where gain is a hyper-parameter which equals 1 by default. Then, each entry of W can be initialized by using a uniform distribution W ∼ U (−η, η) (83) 35 Xiao and Zhu or, alternatively, using a Gaussian distribution W ∼ Gaussian 0, η2 (84) This method can be easily adapted to initialize Transformer models having a large number of layers. One common way is to find a more suitable value of gain by taking into account the fact that the initial states of optimization might be different for neural networks of different depths. For example, one can increase the value of gain as the depth of the model grows. Then, gain can be defined as a function of the network depth in the form gain = a · L b (85) where a is the scalar, and L b is the network depth raised to the power of b. Typically, a and b can be positive numbers, which means that it is preferred to have larger initial values for the parameters for deeper models. For example, Wang et al. (2022a) show that, by choosing appropriate values for a and b, a very deep Transformer model can be successfully trained. Eq. (85) assigns gain the same value for all of the sub-layers. However, it is found that the norm of gradients becomes smaller when a sub-layer moves away from the output layer. This consistent application of gain across the entire model could result in under-training of the lower layers due to the gradient vanishing problem. For this reason, one can develop methods that are sensitive to the position of a sub-layer in the neural network. The general form of such methods is given by gain = a l b (86) Here l denotes the depth of a sub-layer. If l is larger (i.e., the sub-layer is closer to the output), gain will be smaller and the corresponding parameters will be set to smaller values. An example of this method can be found in Zhang et al. (2019)’s work. It is also, of course, straightforward to apply general methods of initializing deep multilayer neural networks to Transformer models. An example is to consider the Lipschitz constant in parameter initialization, which has been shown to help improve the stability of training deep models (Szegedy et al., 2014; Xu et al., 2020). Another approach is to use second-order methods to estimate the proper values of the parameters. For example, one can compute the Hessian of each parameter matrix to model its curvature (Skorski et al., 2021). For models with a large number of layers, it is also possible to pre-train some of the layers via smaller models and use their trained parameters to initialize bigger models (Chen et al., 2015). That is, we first obtain a rough estimation of the parameters in a cheap way, and then continue the training process on the whole model as usual. These methods fall into a class of training methods, called model growth or depth growth. As a simple example, consider a Transformer model (e.g., a Transformer encoder) of 2L sub-layers. We can train this model by using the shallow-to-deep training method (Li et al., 2020b). First, we train an L-sub-layer model (call it the shallow model) in a regular way. Then, we create a 2L-sub-layer model (call it the deep model) by stacking the shallow model twice, and further train this deep model. To construct deeper models, this procedure 36 Introduction to Transformers can be repeated multiple times, say, we start with a model of L sub-layers, and obtain a model of L 2 I after I iterations. Note that many of the pre-training models are used in the same manner. For example, for BERT-like methods, a transformer encoder is trained on large-scale data, and the optimized parameters are then used to initialize downstream systems. 4.2.3 Layer Fusion Another problem with training a deep Transformer model is that the prediction is only conditioned on the last layer of the neural network. While the use of residual connections enables the direct access to lower-level layers from a higher-level layer, there is still a “long” path of passing information from the bottom to the top. One simple way to address this is to create residual connections that skip more layers. For example, consider a group of L Transformer sub-layers. For the sub-layer at depth l, we can build l−1 residual connections, each connecting this sub-layer with a previous sub-layer. In this way, we develop a densely connected network where each sub-layer takes the outputs of all previous sub-layers (Huang et al., 2017). The output of the last sub-layer can be seen as some combination of the outputs at different levels of representation of the input. Following the notation used in the previous sub-sections, we denote the output of the sub-layer at depth l by z l , and denote the function of the sub-layer by Layerl(·). Then, z l can be expressed as z l = Layerl (z 1 , ..., z l−1 ) (87) We can simply view Layerl(·) as a function that fuses the information from {z 1 , ..., z l−1}. There are many possible choices for Layerl(·). For example, a simple form of Layerl(·) is given by Layerl(z 1 , ..., z l−1 ) = LNorm(F l (Z l )) (88) Z l = ϕ(z1 , ..., z l−1 ) (89) Here ϕ(·) takes the layer outputs {z 1 , ..., z l−1} and fuses them into a single representation Z l . A simple instance of ϕ(·) is average pooling which computes the sum of {z 1 , ..., z l−1} divided by l − 1. See Table 3 for more examples of ϕ(·). Taking a similar architecture of a Transformer sub-layer, we can also consider a postnorm form Layerl(z 1 , ..., z l−1 ) = LNorm(Z l ) (90) Z l = ϕ(Fl (z l−1 ), z 1 , ..., z l−1 ) (91) or a pre-norm form Layerl(z 1 , ..., z l−1 ) = Z l (92) Z l = ϕ(LNorm(Fl (z l−1 )), z 1 , ..., z l−1 ) (93) These models are very general. For example, a standard post-norm encoder sub-layer can be recovered as a special case of Eqs. (90-91), if we remove the dependencies of sublayers from 1 to l − 2, and define ϕ(·) to be ϕ(F l (z l−1 ), z 1 , ..., z l−1 ) = F l (z l−1 ) + z l−1 (94) 37 Xiao and Zhu Entry Function Average Pooling ϕ(z 1 , ..., z l−1 ) = 1 l−1 Pl−1 k=1 z k Weighted Sum ϕ(z 1 , ..., z l−1 ) = Pl−1 k=1 weightk · z k Feedforward Network ϕ(z 1 , ..., z l−1 ) = FFN([z 1 , ..., z l−1 ]) Self Attention ϕ(z 1 , ..., z l−1 ) = FFN([Attself(z 1 , ..., z l−1 )]) Table 3: Fusion functions. FFN(·) = feedforward neural network, [·] = concatenating the input vectors, and Attself(·) = self-attention function. All of the fusion functions can be followed by a layer normalization function, for example, we can write the weighted sum of {z 1 , ..., z l−1} as ϕ(z1 , ..., z l−1 ) = LNorm(Pl−1 k=1 weightk · z k ). Densely connected network makes the information easier to flow through direct connections between sub-layers, but the resulting models are a bit more complex, especially when we use parameterized fusion functions. In practice, we typically add dense connections only to some of the sub-layers, and so the overall networks are not very dense. For example, we only add connections from bottom sub-layers to the last few sub-layers. Thus, the prediction can be made by having direct access to different levels of representation (Wang et al., 2018a). 4.2.4 Regularization In machine learning, regularization is used to avoid overfitting in training deep neural networks. It is therefore straightforward to apply regularization techniques to Transformer models. Since the regularization issue has been extensively discussed in many papers and books on machine learning, here we consider specific methods applicable to training deep Transformer models. One approach to regularizing a deep Transformer model is to randomly skip sub-layers or layers during training (Huang et al., 2016; Pham et al., 2019). In each run of the model, such as running the backpropgation algorithm on a batch of samples, we select each of the sublayers with a probability ρ, and stack the selected sub-layers to form a “new” model. Thus, we essentially train different neural networks with shared architectures and parameters on the same dataset. In this way, a sub-layer learns to operate somewhat independently, and so overfitting is reduced by preventing the co-adaption of sub-layers. In fact, dropping out sub-layers (or layers) and dropping out neurons are two different methods on a theme. Sometimes, the method described here is called sub-layer dropout or layer dropout. At test time, we need to combine all the possible networks to make predictions of some output. A simple method to achieve this is to rescale the outputs of the stochastic components of the model (Li et al., 2021). As an example, suppose each sub-layer has a pre-norm architecture. Then, the output of the sub-layer at depth l is given by z l = ρ · LNorm(Fl (z l−1 )) + z l−1 (95) Another idea is to force the parameters to be shared across sub-layers. One of the simplest methods is to use the same parameters for all the corresponding sub-layers (Dehghani et al., 2018), for example, all the FFN sub-layers are based on the same feedforward 38 Introduction to Transformers network. This method has a similar effect as the methods that add norms of parameter matrices to the loss function for penalizing complex models. For practical systems, there can be significant benefit in adopting a shared architecture because we can reuse the same sub-model to build a multi-layer neural network and reduce the memory footprint. We will see more discussions on the efficiency issue in Section 5.4. 4.3 Numerical Method-Inspired Models A residual network computes its output through the sum of the identity mapping and some transformation of the input. Such a model can be interpreted as an Euler discretization of ordinary differential equations (ODEs) (Ee, 2017; Haber and Ruthotto, 2017). To illustrate this idea, we consider a general form of residual networks z l = fl z l−1 + z l−1 (96) where f l (z l−1 ) denotes a function takes an input variable z l−1 and produces an output variable in the same space. Clearly, a Transformer sub-layer is a special case of this equation. For example, for pre-norm Transformer, we have f l (·) = LNorm(F l (·)). For notational simplicity, we rewrite the above equation in an equivalent form z(l) = f z(l − 1), l+ z(l − 1) (97) We use the notations z(l) and f(z(·, l)) to emphasize that z(·) and f(·) are functions of l. Here we assume that l is a discrete variable. If we relax l to a continuous variable and z(l) to a continuous function of l, then we can express Eq. (97) as z(l) = △l · f z(l − △l), l+ z(l − △l) (98) This can be further written as z(l) − z(l − △l) △l = f z(l − △l), l(99) Taking the limit △l → 0, we have an ODE dz(l) dl = f z(l), l(100) We say that a pre-norm Transformer sub-layer (i.e., Eqs. (97) and (96)) is an Euler discretization of solutions to the above ODE. This is an interesting result! A sub-layer is actually a solver of the ODE. Eqs. (97) and (96) are standard forms of the Euler method. It computes a new estimation of the solution by moving from an old estimation one step forward along l. In general, two dimensions can be considered in design of numerical methods for ODEs. • Linear Multi-step Methods. A linear multi-step method computes the current estimation of the solutions by taking the estimations and derivative information from multiple previous steps. A general formulation of p-step methods can be expressed as z(l) = X p i=1 ai· z(l − i) + h X p+1 i=1 bi· f z(l − i), l − i + 1(101) 39 Xiao and Zhu where h is the size of the step we move each time8, that is, △l in Eqs. (98) and (99). {ai} and {bi} are coefficients of the solution points and derivatives in the linear combination. Given this definition, we can think of the Euler method as a single-step, low-order method of solving ODEs9. • (Higher-order) Runge-Kutta Methods. Runge-Kutta (RK) methods and their variants provide ways to compute the next step solution by taking intermediate results in solving an ODE. As a result, we obtain higher-order methods but still follow the form of single-step methods, that is, the estimated solution is dependent only on z(l − 1) rather than on the outputs at multiple previous steps. In fact, linear multi-step methods, though not explicitly mentioned, have been used in layer fusion discussed in Section 4.2. For example, taking Eqs. (92) and (93) and a linear fusion function, a pre-norm sub-layer with dense connections to all previous sub-layers can be expressed as Layerl(z 1 , ..., z l−1 ) = a1 · z l−1 + ... + al−1 · z1 + b1 · LNorm(Fl (z l−1 )) (102) This equation is an instance of Eq. (101) where we set h = 1 and remove some of the terms on the right-hand side. It is also straightforward to apply Runge-Kutta methods to Transformer (Li et al., 2022a). Given an ODE as described in Eq. (100), an explicit p-order Runge-Kutta solution is given by z(l) = z(l − 1) +X p i=1 γi· gi (103) gi = h · f z(l − 1) +X i−1 j=1 βi,j · gj , l − 1 + λi· h (104) Here gi represents an intermediate step which is present only during the above process. {γi}, {βi,j} and {λi} are coefficients that are determined by using the Taylor series of z(l). To simplify the model, we assume that the same function f is used for all {gi}. Then, we remove the dependency of the term l − 1 + λi· h in f, and rewrite Eq. (104) as gi = h · f z(l − 1) +X i−1 j=1 βi,j · gj (105) where f(·) is a function independent of i. 8. Let {t0, ..., ti} denote the values of the variable l at steps {0, ..., i}. In linear multi-step methods, it is assumed that ti = t0 + ih. 9. In numerical analysis, the local truncation error of a method of solving ODEs at a step is defined to be the difference between the approximated solution computed by the method and the true solution. The method is called order p if it has a local truncation error O(h p+1). 40 Introduction to Transformers z(l) f z(l − 1) (a) Pre-norm z(l) f f z(l − 1) 1 2 1 2 (b) RK2 z(l) f f f f z(l − 1) 1 6 1 2 2 6 2 6 1 6 1 2 (c) RK4 Figure 10: Pre-norm (a) and Runge-Kutta (b and c) sub-layer architectures. z(l−1) denotes the input of a sub-layer at depth l, z(l) denotes the output of the sub-layer, and f (in blue boxes) denotes the function f(·) = LNorm(F l (·)) As an example, consider the 4th-order Runge-Kutta (RK4) solution z(l) = z(l − 1) + 1 6 (g1 + 2g2 + 2g3 + g4) (106) g1 = h · f(z(l − 1)) (107) g2 = h · f(z(l − 1) + 1 2 g1) (108) g3 = h · f(z(l − 1) + 1 2 g2) (109) g4 = h · f(z(l − 1) + g3) (110) These equations define a new architecture of sub-layer. For example, by setting h = 1 and f(·) = LNorm(F l (·)), we obtain an RK4 Transformer sub-layer, as shown in Figure 10. This method leads to a deep model because each sub-layer involves four runs of f(·) in sequence. On the other hand, the resulting model is parameter efficient because we reuse the same function f(·) within the sub-layer, without introducing new parameters. So far in this sub-section our discussion has focused on applying dynamic systems to Transformer models by designing architectures of Transformer sub-layers. While the basic ODE model is continuous with respect to the depth l, these methods still follow the general framework of neural networks in which l is a discrete variable and the representational power of the models is largely determined by this hyper-parameter. An alternative approach is to use neural ODE models to relax the “depth” to a truly continuous variable. In this way, we can have a model with continuous depth for computing the solution of ODEs. However, as the discussion of neural ODE lies beyond the scope of this chapter, we refer the reader to related papers for more details (Chen et al., 2018c; Kidger, 2022). 41 Xiao and Zhu 4.4 Wide Models Most of the methods that we have studied so far in this section are examples of learning and using deep models. Another design choice we generally face is to determine the width for a neural network. Typically, the width of a Transformer model can be defined as the number of dimensions of a representation at some position of the input sequence, that is, the parameter d. Increasing this width is a common method to obtain a more complex and more powerful model. For example, in Vaswani et al. (2017)’s work, a wide model (called Transformer big) leads to significant improvements in translation quality for machine translation systems. More recently, wider models have been proposed to boost systems on large-scale tasks (Fedus et al., 2022b; Lepikhin et al., 2021). However, developing very wide Transformer models is difficult. One difficulty is that training such systems is computationally expensive. While the number of the model parameters (or model size) grows linearly with d, the time complexity of the models grows quadratic with d (see Table 1). In some NLP tasks, it is found empirically that the training effort that we need to obtain satisfactory performance is even an exponential function of the model size (Kaplan et al., 2020). These results suggest ways to improve the efficiency of training when we enlarge d. One simple method is to incrementally grow the model along the dimension of d, rather than training the model from scratch. Suppose we have an initial model involving a d1 × d1 parameter matrix W1, for example, the linear transformation of each query or key in some layer. We can train this model to obtain optimized W1 in a regular way. Then, we want to extend this model to a wider model where W1 is replaced by a d2 × d2 parameter matrix W2. Let us assume for simplicity that d2 = kd1. There are several ways to expand a d1 ×d1 matrix to a kd1 × kd1 matrix. The simplest of these may be to use W1 to fill W2. We can write W2 in the form W2 = k times    W1 ρ · · · W1 ρ . . . . . . W1 ρ · · · W1 ρ    k times (111) where ρ is a hyper-parameter that is used to control the norm of W2. For example, if ρ = k, W2 will have the same l1 norm as W1. The above equation provides a good starting point for training the wide model, and we can train W2 as usual after initialization. The procedure can be repeated a number of times for constructing a model with arbitrary width. Both this method and the depth growth method described in Section 4.2 are instances of the general method of model growth. In other words, we can obtain a larger model by extending a small model either vertically or horizontally, or both. Alternative methods for transforming W2 to W1 involve those considering other mathematical properties of the transformation (Chen et al., 2015). These models can fall under the reusable neural networks where we are concerned with models and algorithms for transferring parameters from small models to (significantly) larger models (Wang et al., 2023). A second difficulty in building a wide Transformer model is the large memory requirement. Since the feedforward network generally has a larger hidden layer than other parts of the model, it demands relatively more memory as the model becomes wider. Consider 42 Introduction to Transformers the feedforward network described in Section 2.5 Hout = FFN(Hin) = ReLU(Hin · Wh + bh) · Wf + bf (112) where Wh ∈ R d×dffn and Wf ∈ Rdffn×d are the parameters of the linear transformations. dffn is typically several times larger than d. Therefore, Wh and Wf will occupy the model if d and dffn have very large values. In some cases, the size of the feedforward network may exceed the memory capacity of a single device. This problem can be addressed by using the mixture-of-experts (MoE) models (Shazeer et al., 2017). An MoE model consists of M expert models {e1(·), ..., eM(·)}. Given an input hin ∈ R d , each expert model produces an output ek(hin). The output of the MoE model is a linear combination of {e1(hin), ..., eM(hin)}, given by hout = X M i=1 gi(hin) · ei(hin) (113) where g(·) is a gating model (also called routing model). Its output is a vector g(hin) = g1(hin) ... gM(hin) in which each entry gi(hin) indicates the weight of the corresponding expert model. In many applications, it is assumed that g(hin) is a sparse vector. This means that only a small number of expert models are involved in computing the output. A widelyused form of g(hin) is given by using the Softmax layer g(hin) = Softmax(hin · Wg) (114) where Wg ∈ R d×M is the parameter matrix of the layer. To enforce sparsity on g(hin), we can simply select the top-k entries of g(hin), that is, we set non-top-k entries to 0. An alternative method is to first perform top-k selection on hin · Wg and then normalize the top-k entries using the Softmax function. Let π be the set of the indices of the top-k expert models. The MoE model with top-k routing has the following form hout = X i∈π gi(hin) · ei(hin) (115) An advantage of this approach is that we can distribute different expert models to different processors, making it possible to execute these models on parallel computing machines. In each run of the MoE model, either during training or inference, we only need to activate and use k expert models rather than all of the expert models. In this way, the MoE approach is automatically learning a sparse model by limiting the number of active expert models each time in training and inference. The sparsity is determined by the hyperparameter k, say, a small value of k leads to a sparse model, and a large value of k leads to a dense model. Let us return to the discussion of Eq. (112). It is straightforward to apply the MoE approach to feedforward neural networks. To simplify the discussion, consider the linear 43 Xiao and Zhu Feed-Forward Network Add & LayerNorm . . . . . . FFN sub-layer Gating Model FFN1(·) FFN2(·) · · · FFNM(·) Hin Hin Hin · · · Hin P i∈π gi(Hin) · FFNi(Hin) Hout Figure 11: An illustration of the MoE model applied to an FFN sub-layer. There are M FFNs (call them expert models) and a gating model. Each FFN is weighted by the gating model. The output of the model is the sum of the weighted outputs of the top-k FFNs (denoted by π). Because these FFNs work independently and can be placed on different computing devices, the model can be easily scaled up as M is larger. transformation of the first layer as shown in Eq. (112), that is, Hin · Wh. We can approximate Hin · Wh in an MoE form Hin · Wh ≈ X i∈π gi(Hin) · ei(Hin) = X i∈π gi(Hin) · [Hin · Wi h ] (116) Here Wh is divided into M slides (or sub-matrices) {W1 h , ...,WM h }, written as Wh = W1 h ... WM h (117) Hence each expert model ei(Hin) = Hin · Wi h solves a sub-problem of the original linear mapping, and Eq. (116) can be thought of as a divide-and-conquer solution to the matrix multiplication problem. We can, of course, treat any feedforward neural network as an expert model, resulting in the following model Hout = X i∈π gi(Hin) · FFNi(Hin) (118) where FFNi(·) is a “small” feedforward neural network that has the same form as Eq. (112). This model is illustrated with an example in Figure 11. In practical implementations, all these expert models can be run in parallel on different devices, and so the resulting system is efficient. Note that, from a perspective of machine learning, MoE is a general approach to combining different neural networks, each of which is developed to address a different aspect 44 Introduction to Transformers of the problem (Masoudnia and Ebrahimpour, 2014; Yuksel et al., 2012). The application here is just a special instance of the general framework of MoE. The approach is also often used to improve the overall performance of predictors, which can be discussed in the field of ensemble learning (Zhou, 2012). Another difficulty in developing large Transformer models is the training instability problem. As with many other large neural networks, straightforward optimization of a Transformer model with a large number of parameters may lead to getting trapped in local minimums, and, occasionally, large spikes in the loss during training (Chowdhery et al., 2022; Fedus et al., 2022b; Lepikhin et al., 2021). Even with careful choices about hyperparameters, training strategies, and initial model parameters, we still encounter the situation that we have to restart the training at some point in order to jump out of the tough regions in optimization. One of the reasons for this training difficulty is that the usual implementations of the linear algebra operations, such as matrix multiplication, will be numerically unstable if they operates on very large vectors and matrices. It is therefore possible to improve the training by considering numerically stable methods instead. 5. Efficient Models Efficiency is an important consideration for many practical applications of Transformer models. For example, we may wish to run and/or train a Transformer model given memory and time constraints. Efficiency is not a single problem, but covers a wide range of problems. While these problems can be categorized in several different ways, there are two fundamental aspects one may consider in an efficiency problem. • Time and Space Efficiencies. For a given problem, we wish the model to be small and fast, and meanwhile to be as accurate as possible in solving the problem. For example, in some machine translation applications, we may learn a model with a small number of parameters to fit the model to limited memory, and may develop a fast search algorithm to achieve low-latency translation. A practical difficulty here is that improving efficiency often leads to worse predictions. In many cases, we need to seek a trade-off between efficiency and accuracy. • Scalability. When the problem is scaled up, we wish that the additional effort we made for solving this problem is as small as possible. For example, the training of a neural network is called efficient if it takes a reasonably short time to optimize it as more training samples are involved. Another example of efficiency is that used to measure the amount of resources consumed in processing more inputs. For example, a machine translation system is inefficient in translating long sentences if the memory footprint and latency grow exponentially with the number of input words. In this section, we will not discuss all the issues related to efficiency, which is a very broad topic. We instead consider the widely-used efficient approaches to Transformer-based sequence modeling and generation, some of which are refinements of model architectures, and some of which are model-free approaches and could be used in other systems as well. Most of the discussions here are focused on developing lightweight and fast Transformer models that are relatively robust to long input and output sequences. 45 Xiao and Zhu In general, the same optimization method can be applied to different modules of a Transformer system. To simplify the discussion, we will mostly consider self-attention sub-layers and FFN sub-layers in this section. Our discussion, however, is general and the methods presented here can be applied to other parts of a Transformer system, for example, cross-attention sub-layers. 5.1 Sparse Attention In practice, the attention approaches used in Transformer are time consuming, especially when the input sequences are long. To illustrate, consider a Transformer decoder that predicts a distribution of words at a time given the previous words. Suppose the sequence generated by the decoder is of size n and the input of a self-attention sub-layer is an n × d matrix S. First, S is linearly transformed to obtain the queries S q ∈ Rn×d , keys S k ∈ Rn×d , and values S v ∈ Rn×d . To simplify the notation in this sub-section, we use Q, K and V to represent S q , S k , and S v , respectively. The output of the self-attention sub-layer can then be computed using Attself(S) = AV (119) where A is an n × n attention matrix or attention map A = Softmax(QKT √ d + M) (120) M is a masking matrix that is used to prevent the model from seeing the right context words at each position, that is, for a position i, M(i, j) = 0 for j ≤ i, and M(i, j) = −∞ otherwise. Both the time and space complexities of the self-attention sub-layer are quadratic functions of n 10. Therefore, if n is large, the model would be computationally expensive. The usual implementation of the above model depends on dense matrix computation, for example, the dense matrix multiplications in Eqs. (119-120). One approach to reducing the amount of memory and the number of floating-point calculations in a dense computation system is to sparsify the problem. To do this, we assume that A is a sparse matrix, for example, only ϱ · n 2 entries of M have non-zero values, where ϱ indicates how sparse the matrix is, also called sparsity ratio. Since we only need to store these non-zero entries, the memory requirement of A can be reduced by using sparse matrix representations. Another advantage of using a sparse attention matrix is that the models of QKT √ d and AV can be simplified, as we consider only a “small” number of related positions when learning a representation. Given a position i, we define the attention field πi to be the set of positions that are considered in computing the representation at this position. We therefore only need to compute the dot-product attention between the given position i and each position j ∈ πi. This results in a sparse attention matrix A′ where A ′ (i, j) = ( some weight j ∈ πi and j ≤ i 0 otherwise (121) 10. More precisely, the amount of memory used by the self-attention function is n 2 + n · d, and so it will be dominated by the quadratic term n 2 if n >> d. 46 Introduction to Transformers A simple implementation of this model involves a slight modification to M, leading to a new masking variable M′ M′(i, j) = ( 0 j ∈ πi and j ≤ i −∞ otherwise (122) In practical implementation, a more efficient approach is to employ sparse operations for QKT and A′V by considering M′ and A′, respectively. That is, we save on computation for pairs of positions whose attention weights are non-zero, and skip the rest. There are several approaches that we can take to the sparse modeling of self-attention. We describe briefly some of them as follows • Span-based Attention/Local Attention. As discussed in Section 4.1, the use of context in sequence modeling is local in many cases. The basic idea of local attention is to span the attention weights to a restricted region of the input sequence. We can then write πi as πi = [a l i , ar i ] (123) where a l i and a r i and the left and right ends of πi. a r i − a l i + 1 determines how small the region is, and so we can use it to control the sparsity of the attention model, for example, if a r i − a l i + 1 << n, the model would be very sparse. a l i and a r i can be obtained by using either heuristics or machine learning methods. The reader may refer to related papers for more details (Luong et al., 2015; Sperber et al., 2018; Sukhbaatar et al., 2019; Yang et al., 2018). See Figure 12 (b) for an illustration of local attention. • Chunked Attention. When a problem is too difficult to solve, one can transform it into easier problems and solve each of them separately, as is often the case in practice. This motivates the chunked attention approach in which we segment a sequence into chunks and run the attention model on each of them (Parmar et al., 2018; Qiu et al., 2020). Given a sequence {1, ..., n}, we define {chunk1, ..., chunkq} to be a segmentation of the sequence. A chunk can be expressed as a span chunkk = [c l k , cr k ] (124) In the attention step, we treat each chunk as a sequence and perform self-attention on it as usual. In other words, the representation at position i is computed by using only the context in the chunk that i belongs to. In this sense, this model can be thought of as some sort of local attention model. Figure 12 (c) shows an illustration of this model. There remains the issue of how to segment the sequence. There are several ways to do this. For example, as discussed in Section 3.4, we can do segmentation from a linguistic perspective, and segment the sequence into linguistically motivated units. In practical systems, it is sometimes more convenient to segment the sequence into chunks that are of equal length. Thus, the sparsity of the model is controlled by the size of these chunks, for example, the use of smaller chunks would lead to a more sparse attention model. • Strided Attention. Since the chunked attention approach enforces a hard segmentation on the input sequence, it may lose the ability to learn representations from 47 Xiao and Zhu inputs in different chunks. An alternative way to achieve chunk-wise attention is to allow overlap between chunks (Ainslie et al., 2020; Beltagy et al., 2020; Child et al., 2019). This approach is analogous to the family of approaches that are commonly used to apply a local model to 1D or 2D data to generate outputs of the same shape. Like CNNs, we use a context window to represent the field of input of the attention model. The context window slides along the sequence, each time moving forward a step of size stride. As a special case, if stride equals the size of the context window, this model is the same as the chunked attention model mentioned above. If stride chooses a value smaller than the size of the context window, the attention model will become denser. Figure 12 (d) shows the case of strdie = 1 where the chunk overlapping is maximized. A way to achieve relatively sparser attention is to use a dilated context window. Figure 12 (e) shows an example of the dilated strided attention model, where the context window is discontinuous, with gaps of size 1. • Learning Attention Fields. Because the attention field πi can be any sub-set of {1, ..., n}, we can develop more general sparse attention models by considering attention maps beyond chunk-based patterns. The only question is how to determine which positions the model attends to for a given position. One simple approach is to use a computationally cheaper model to estimate the “importance” of each position. Then, attention weights are computed only for some of the positions which are thought to be most important (Zhou et al., 2021). A second approach is grouping: positions are grouped, and then the attention weights are computed only for positions in the same group. It is often relatively easy to achieve this by running clustering algorithms on keys and queries. For example, we can cluster keys and queries via k-means clustering. The centroids of the clusters can be treated as additional parameters of the attention model, and so can be learned during optimization (Roy et al., 2021). One benefit of learning attention fields is that the model can spread its attention broader over the sequence. This is a useful property for many NLP problems because word dependencies are sometimes long-range, not restricted to a local context window. See Figure 12 (f) for an example of the attention map learned through this model. Alternative approaches to learning to attend are to use sorting or hashing functions to group similar key and query vectors (Kitaev et al., 2020; Tay et al., 2020a). These functions can be either heuristically designed functions or neural networks with learnable parameters. By using these functions, we can reorder the sequence so that the inputs in the same group are adjacent in the reordered sequence. In this way, the resulting attention map follows a chunk-wise pattern, and the model is computationally efficient through the use of the chunked attention approach. • Hybrid Methods. Above, we have discussed a range of different sparse attention models. It is natural to explore methods that combine multiple models together to make use of their benefits in some way. A simple way to do this is to combine the attention fields of different models. For example, in Zaheer et al. (2020)’s system, the attention map is generated by considering three different sparse models, including 48 Introduction to Transformers local attention (chunked attention), global attention, and random attention11. The resulting model is still a sparse model, but is somewhat more robust as it involves multiple patterns from different perspectives of attention modeling. Another way of combining multiple attention models is to use different models for different heads in multi-head attention (Beltagy et al., 2020; Child et al., 2019). For example, one can use one head as a local attention model, and use another head as a global attention model (see Figure 12 (g-h)). One disadvantage of sparse models compared to dense models is that they are not computationally efficient on GPUs or CPUs. While sparse models can ideally reduce both the memory and computation requirements, the actual rate at which work can be done by sparse models is much slower than by dense models. In practice, it is difficult for sparse models to approach the peak FLOPS of a GPU or CPU12. Therefore, they are often used for the purpose of high memory efficiency, not really for the purpose of efficient computation. On the other hand, sparse models are still of great use to NLP practitioners in the context of memory-efficient Transformer, especially when Transformer systems are used to deal with extremely long sequences. 5.2 Recurrent and Memory Models For sequence generation problems, Transformer can also be thought of as a memory system. Consider again the general setting, in which we are given the states of previous i − 1 positions, and we wish to predict the next state. In self-attention, this is done by using the query at position i (i.e., qi) to access the key-value pairs of the previous positions (i.e., {(k1, v1), ...,(ki−1, vi−1)}). Then, we move to position i+1, and add (ki, vi) to the collection of key-value pairs. This procedure can be interpreted in terms of memory mechanisms. The Transformer model maintains a memory that retains the information of the past. When moving along the sequence, we repeat the same operation, each time generating some output by reading the memory, and then updating the memory so that new information could be stored in some way. This is illustrated in Figure 13. 5.2.1 Cache-based Memory The memory here can be viewed as a datastore of vectors. From a machine learning perspective, this is a non-parametric model, and the cost of accessing the model grows as a longer sub-sequence is observed. Clearly, such a variable-length memory will generally be infeasible if the model deals with a very, very long sequence. For the modeling problem of arbitrary length sequences, it is common to use a fix-length memory instead. As in many NLP problems, one of the simplest ways to do this is to consider a cache saving recent information, that is, we restrict the modeling to a context window. Let nc be the size of the context window. The model keeps track of the nc − 1 latest states to the current position, so that its closest successors can be considered at each step. This means that, for each position, a self-attention sub-layer attends to nc − 1 positions ahead, like this 11. Here the global attention model attends each word only to a special word which accounts for the entire sequence and is often placed at the beginning of the sequence. The random attention model attends each word to a random set of the words of the sequence. 12. FLOPS = floating point operations per second. 49 Xiao and Zhu (a) Standard Attention (b) Span-based Attention (c) Chunked Attention (d) Strided Attention (e) Dilated Strided Attention (f) Learning Attention Fields (g) Global Attention (h) Hybrid Methods Figure 12: Illustration of the attention maps of different models (self-attention on the decoder side). Dark cells mean A′ (i, j) ̸= 0 (i.e., i attends to j), and light cells mean A′(i, j) = 0 (i.e., i does not attend to j). In all these attention maps, we assume that every position attends to itself by default (see diagonals). 50 Introduction to Transformers 1 2 3 ... i − 2 i − 1 i i + 1 Memory ({1, ..., i − 1}) State Read (self-attention) Update Position i 1 2 3 ... i − 2 i − 1 i i + 1 Memory ({1, ..., i − 1, i}) State Read (self-attention) Update Position i + 1 Figure 13: Transformer as a memory system. At position i, the collection of the key-value pairs of positions {1, ..., i − 1} is used as a memory of the past information. The Transformer model accesses this memory to generate some output, and then adds the key-value pair of position i to the memory. Moving to the next position, we repeat the same procedure of memory access and update. 51 Xiao and Zhu Input Output i − 5 i − 4 i − 3 i − 2 i − 1 i If we stack multiple self-attention sub-layers, a larger context window would be considered. For example, a model involving two self-attention sub-layers has a context window of size 2nc − 1, as follows Layer 1 Layer 2 Output i − 5 i − 4 i − 3 i − 2 i − 1 i Therefore, we can take a sufficiently large context by using a multi-layer Transformer model. Note that the context window model here is essentially the same as the strided attention model presented in the preceding section. Systems of this type are often easy to implement: we slide a window along the sequence, and, in each move, we make predictions at the last position of the window (for inference), or back-propagate errors (for training). An alternative way to train this context window model is by chunked attention. We divide the sequence into chunks (or sub-sequences) which are of the same length nc. Then, we treat these chunks as individual training samples, and run the training program on each of them as usual. This approach, however, completely ignores the relationship between inputs in different chunks. One way to address this issue is to introduce dependence between chunks. For example, the Transformer-XL model allows every chunk to access one or more preceding chunks (Dai et al., 2019). In the simplest case, consider an example in which chunkk can see its successor chunkk−1. Each position in chunkk can attend to all its preceding positions in both chunkk and chunkk−1. In Transformer-XL, this approach is implemented in a simplified form. First, each position is constrained to attend to nc−1 previous positions so that the size of the attention field of a position is the same in the training and inference stages. Such a method turns the problem back to strided attention, making the implementation of the attention model straightforward. On the other hand, the difference between the standard strided attention model and the Transformer-XL model is that in Transformer-XL, we perform training in a chunk-wise manner. Once we finish the training on a chunk, we directly move to the next chunk, rather than sliding the context window a small step forward. Second, while this approach allows for connections between chunks, the parameters of the sub-network on chunkk−1 are fixed, and we only update the parameters of the sub-network on chunkk in the k-th step. See Figure 14 for an illustration. The above model is similar in spirit to recurrent models because all of them require the computation in one step to depend on the states of the preceding steps. However, it is 52 Introduction to Transformers Layer 1 Layer 2 Output i − 5 i − 4 i − 3 i − 2 i − 1 i i + 1 i + 2 i + 3 (a) Step k of chunk-wise training chunkk−1 chunkkchunkk+1 Layer 1 Layer 2 Output i − 5 i − 4 i − 3 i − 2 i − 1 i i + 1 i + 2 i + 3 (b) Step k + 1 of chunk-wise training chunkk−1 chunkkchunkk+1 Figure 14: Illustration of chunk-wise training (Dai et al., 2019). The input sequence is divided into chunks of the same length nc. Training is performed on these chunks, each time dealing with a chunk. In chunkk, the attention field for every position in this chunk is a left context window of size nc. Hence this model allows for attention across chunks, for example, position i − 2 in chunkk can attend to positions i−3 and i−4 in chunkk−1 (see sub-figure (a)). For training, errors are back-propagated only in the sub-network for chunkk, leaving other parts of the model unchanged. Here we use dashed lines to denote information flow that we consider in the forward pass but not in the backward pass. Once we finish the training on chunkk, we move to the next chunk, and repeat the same training procedure. 53 Xiao and Zhu not in the standard form of a recurrent model, in which the output of a recurrent unit in one step is the input in the next step. Instead, the “recurrence” is expressed by involving connections between two different layers, that is, the output of one layer in chunkk−1 is used as the input of a higher-level layer in chunkk. 5.2.2 Encoding Long-term Memory Another idea for representing the states of a sequence is to frame the task as an encoding problem. Instead of storing all the key-value vectors during left-to-right generation, we construct the memory of the entire “history” as a fixed number of encoded key-value vectors. These encoded key-value vectors can be either a small sub-set of {(k1, v1), ...,(ki−1, vi−1)} or a small set of newly-generated vectors that encodes {(k1, v1), ...,(ki−1, vi−1)}. One way to do the encoding is to apply a pooling operation to {(k1, v1), ...,(ki−1, vi−1)} (Rae et al., 2019). For example, by using average pooling, the memory contains only one key-value pair (k¯, v¯) k¯ = 1 i − 1 X i−1 j=1 kj (125) v¯ = 1 i − 1 X i−1 j=1 vj (126) This leads to a very efficient model, and we only need to update the vectors (k¯, v¯) at a time (Zhang et al., 2018). Let (k¯[i], v¯[i]) be the state of the memory at position i. A more general definition of (k¯[i], v¯[i]) is given in a recursive form k¯[i] = KMem(k¯[i − 1], ki−1) (127) v¯[i] = VMem(v¯[i − 1], vi−1) (128) where KMem(·) and VMem(·) are functions that update the memory by taking both the states of the memory at the previous position (i.e., k¯[i − 1] and v¯[i − 1]) and the new states (i.e., ki−1 and vi−1). There are many forms of the functions like KMem(·) and VMem(·) in common use. For example, if KMem(·) and VMem(·) are weighted sum functions, we can derive the same forms as Eqs. (125) and (126). If KMem(·) and VMem(·) are recurrent cells in RNNs or LSTM, we obtain a recurrent model of memory. Extension of the above model to memories having more than one key-value pair is straightforward. One approach is to use the memory to represent sub-sequences. Let {(k¯ 1, v¯1), ...,(k¯κ, v¯κ)} be a memory of size κ. Each (k¯j , v¯j ) is a snapshot of a chunk of length nc. Thus, this memory can encode a sequence with maximum length κ · nc. Then, we can compute (k¯ j , v¯j ) on the corresponding chunk using Eqs. (127) and (128). A second approach is to organize {(k¯ 1, v¯1), ...,(k¯κ, v¯κ)} into a priority queue. We design some function to assign a score to any given key-value pair. The key-value pair can be inserted into the priority queue through the push operation. Ideally, we wish to develop a scoring function to estimate the value of a key-value pair, for example, we use another neural network to evaluate the key-value pair. In this way, the memory is a collection of the most valuable key-value pairs over the input sequence. 54 Introduction to Transformers Although representing the memory as a set of vectors is an obvious choice for the model design in Transformer, the memory is discrete and its capacity is determined by the number of the vectors. An alternative form of memory is continuous memory. This type of model typically builds on the idea of function approximation, in which {k1, ..., ki−1} or {v1, ..., vi−1} is viewed as a series of data points, and a continuous function is developed to fit these data points. Then, we no longer need to store {k1, ..., ki−1} and {v1, ..., vi−1}. Instead, the memory is represented by the functions fitting these vectors. A simple method is to combine simple functions to fit complex curves of data points. For example, we can develop a set of basis functions and use a linear combination of them to approximate the key or value vectors (Martins et al., 2022). The resulting model is parameterized by these basis functions and the corresponding weights in the combination. It is also straightforward to use a short-term memory and a long-term memory simultaneously so that we can combine the merits of both. For example, we use a cache-based memory to capture local context, and use an efficient long-term memory that encodes the entire history to model long-range dependency. This idea is also similar to that used in combining different sparse attention models as discussed in the previous sub-section. 5.2.3 Retrieval-based Methods So far in this sub-section, we have discussed approaches based on fixed-length models. It is also possible to develop efficient memory models by improving the efficiency of accessing the memories, instead of just reducing the memory capacities. One way to achieve this is to store the past key-value pairs in a database (call it a vector database), and to find the most similar ones when querying the database. To be more precise, given a query q, we use the database to find a set of top-p relevant key-value pairs (denoted by Ωp) by performing similarity search based on the dot-product similarity measure between query and key vectors. Then, we attend q to Ωp as in standard self-attention models. The idea behind this method is to consider only a small number of elements that contribute most to the attention result. Therefore, the model is essentially a sparse attention model which is computationally efficient. Another advantage of this method is that it allows for fast similarity search over a very large set of vectors because of the highly optimized implementation of vector databases. Building a memory as a retrieval system can fall under the general framework called the retrieval-augmented approach. It provides a simple way to incorporate external memories into neural models like Transformer (Guu et al., 2020; Lewis et al., 2020; Wu et al., 2021). 5.3 Low-dimensional Models In many practical applications, Transformer models are “high-dimensional” models. This is not only because the input and/or output data is in high-dimensional spaces, but also because some of the intermediate representations of the data in the model are high-dimensional. As discussed in Section 5.1, this high dimensionality arises in part from the steps of computing the attention matrix as in Eq. (119) (for ease of presentation, we repeat the equation here) Attself(S) = AV (129) 55 Xiao and Zhu and the weighted sum of value vectors as in Eq. (120) A = Softmax(QKT √ d + M) (130) which involves large matrix multiplications QKT and AV when the length n and the hidden dimensionality d have large values. The AV and QKT operations have a time complexity of O(n 2 ·d) and a space complexity of O(n 2 + n · d). Several previously described approaches have reduced this complexity by using sparse models. In this sub-section, we focus on methods that approximate these operations via dense computation. One simple idea is to transform Q, K, and V into smaller matrices, and thus to reduce the computational burden of matrix multiplication. Since Q, K, and V are all in R n×d , we can achieve this by reducing either the n dimension or the d dimension, or both. 5.3.1 Reducing n Note that the output Attself(S) is required to be an n×d matrix, and so we cannot reduce the number of queries. We instead consider reducing the number of keys and values. Suppose n ′ is a number less than n, and K and V can be transformed into n ′ × d matrices K′ and V ′ in some way. We can obtain a “smaller” model simply by replacing K and V with K′ and V ′ , giving Attself(S) = AV ′ (131) A = Softmax(Q[K′ ] T √ d + M) (132) This model is in the standard form of self-attention, but has lower time and space complexities, that is, O(n ′ · n · d) < O(n 2 · d) and O(n ′ · n + n ′ · d) < O(n 2 + n · d). If n′ << n, the resulting model will be linear with n. The key problem here is how to obtain K′ and V ′ in a way that retains much of the information in K and V. There are several ways to do so. One simple method is to select the keys and values that are thought to be important. The importance of a key (or value) can be computed in terms of some computationally cheap measure. For example, we can sample a small number of query-key dot-products and estimate the importance of a key by collecting these dot-product results. The above method is straightforward but still requires sparse operations, such as sampling and collection. As an alternative, we can use dense computation to transform K and V to K′ and V ′ . A typical choice is to use CNNs (Liu et al., 2018). Let Conv(·) be a function describing a set of filters that slide along the n dimension. K′is then given by K′ = Conv(K,Wc, sizer, stride) (133) where Wc is the parameter matrix of the filters, sizer is the size of the receptive field, and stride is the number of units the filters are translated at a time. In general, we can achieve a high compression rate by choosing large values for sizer and stride. Likewise, we can compute V ′ using another convolutional function. It is worth noting that, if the parameter 56 Introduction to Transformers n ′ is fixed for all samples, compression of K and V along the length dimension is essentially the same as the fixed-length memory model as described in the preceding sub-section. The methods presented here are more general and could be applied to variable-length memories. We might also be tempted to model the attention function by considering the attention matrix A as a high-dimensional representation of data and then applying conventional dimensionality reduction methods. For many problems, it is found that A (or more precisely QKT) is a low-rank matrix. In this case, we can compress A while retaining as much information as possible. There are many ways to do so. For example, we might use a product of smaller matrices as an approximation to A via the SVD technique. However, this introduces computational overhead in using SVD compared with the standard attention model. A simpler idea to directly transform K and V into smaller-sized matrices via linear mappings, given by K′ = UkK (134) V ′ = UvV (135) where Uk ∈ R n ′×n and Uv ∈ R n ′×n are parameter matrices. Clearly, this leads to a model which is equivalent to that described in Eqs. (131) and (132). While such a method is intuitive and simple, it is proven to obtain a sufficiently small approximation error ϵ if n ′ is a linear function of d/ϵ2(Wang et al., 2020b). 5.3.2 Reducing d Another approach to working in a low-dimensional space is to reduce the d dimension. One of the simplest methods is to project all queries and keys onto a d ′ -dimensional space (d ′ < d), and to compute the dot-product of any key-value pair in the new space. For modeling, we only need to replace Q ∈ R n×d and K ∈ Rn×d by new representations Q′ ∈ Rn×d ′ and K′ ∈ R n×d ′ . We can easily modify Eq. (130) to use Q′ and K′in computing the attention matrix A = Softmax(Q′ [K′] T √ d + M) (136) Q′ and K′ are given by Q′ = QUq (137) K′ = KUk(138) where Uq ∈ R d×d ′ and Uk ∈ R d×d ′ are parameter matrices of linear transformations. It is also possible to exploit kernel methods to obtain an efficient dot-product attention model. The basic idea is to map all data points (represented as vectors) from one space to another space, so that the problem, which might be difficult to solve in the original space, is easier to solve in the new space. The “trick” of kernel methods is that we actually do not need to know the mapping function, but only need to know how to compute the inner product of vectors in the new space in one operation13. This operation of the inner product is usually called the kernel and denoted by K(·, ·). 13. In mathematical analysis, the inner product is a generalized notion of the dot-product. It is typically denoted by ⟨·, ·⟩. A formal definition of the inner product requires that ⟨·, ·⟩ satisfies several properties 57 Xiao and Zhu It is interesting to approximate A in a fashion analogous to K(·, ·) in kernel methods. To illustrate, note in Eq. (130) A is a fraction denoting the normalized attention weights. The numerator can be written in the form Ae = Mask(exp(QKT √ d )) (140) (141) Here Mask(·) is a function which has the same effect as using the additive masking variable M. Then, A can be expressed as A = D−1Ae (142) where D is an n × n diagonal matrix. Each entry of the main diagonal is the sum of the entries of the corresponding row in Ae , denoting the normalization factor of Softmax. Substituting this equation into Eq. (130), we have Attself(S) = D−1AVe (143) In this model, Ae(i, j) can be viewed as a similarity function over all query-key pairs in a d-dimensional space. Here we assume that this function, which is in the form of the dot-product of vectors, can be approximated by a kernel function Ae(i, j) = K(qi, kj ) = ⟨ϕ(qi), ϕ(kj )⟩ ϕ(·) is a mapping from R d to R d ′ . We can represent the queries and keys in the following form Q′ = ϕ(Q) =    ϕ(q1) . . . ϕ(qn)    (144) K′ = ϕ(K) =    ϕ(k1) . . . ϕ(kn)    (145) in a vector space. Although the inner product has different forms in different contexts, in the Euclidean space R d , it is the same thing as the dot-product, that is, given two vectors a ∈ R d and b ∈ R d , we have ⟨a, b⟩ = a · b = Xd i=1 ai · bi (139) 58 Introduction to Transformers Then, we develop a kernelized attention model by approximating the attention weight αi,j in the form αi,j ≈ ϕ(qi)ϕ(kj ) T Pn j ′=1 ϕ(qi)ϕ(kj ′) T (146) The key idea behind this kernelized attention model is that we can remove the Softmax function if the queries and keys are mapped to a new space. Using this approximation, the i-th output vector of the attention model (i.e., the i-th row vector of Attself(S)) is given by ci = Xn j=1 αi,j · vj ≈ Xn j=1 ϕ(qi)ϕ(kj ) T Pn j ′=1 ϕ(qi)ϕ(kj ′) T · vj = Pn j=1 ϕ(qi)ϕ(kj ) Tvj Pn j ′=1 ϕ(qi)ϕ(kj ′) T = ϕ(qi)( Pn j=1 ϕ(kj ) Tvj ) ϕ(qi)( Pn j ′=1 ϕ(kj ′) T) (147) Although the equation appears a bit complicated, the idea is simple: instead of attending the query to all keys to obtain the attention weight αi,j , we can compute the sum of the multiplications Pn j=1 ϕ(kj ) Tvj ∈ Rd ′×d and then multiply it with the kernelized query ϕ(qi). Returning to the notation used in Eq. (143), we define the i-th entry of D to be ϕ(qi) Pn j ′=1 ϕ(kj ′) T. Then, the attention model can be re-expressed in the form Attself(S) = D−1ϕ(Q)ϕ(K) TV = D−1Q′K′TV = D−1 Q′(K′TV) (148) Here we change the order of computation from left-to-right to right-to-left using parentheses. Given that Q′ ∈ R n×d ′ and K′ ∈ R n×d ′ , this model has time and space complexities of O(n·d·d ′ ) and O(n·d+n·d ′+d·d′ ), respectively. Therefore, the model is linear with respect to the sequence length n, and is sometimes called the linear attention model. One computational advantage of this model is that we need only compute the multiplication K′TV (i.e., Pn j=1 ϕ(kj ) Tvj ) and the corresponding normalization factor (i.e., Pn j ′=1 ϕ(kj ′) T) once. The results can then be used for any query (Katharopoulos et al., 2020). The memory needs to maintain Pn j=1 ϕ(kj ) Tvj and Pn j ′=1 ϕ(kj ′) T and update them when new key and value vectors come. Still, there are several problems regarding this kernelized model, for example, how to develop the feature map ϕ(·) to obtain a good approximation to the standard attention model. Interested readers may refer to Choromanski et al. (2020)’s work for more details. A second idea for reducing d is to take sub-space models, in which a problem in a ddimensional space is transformed into sub-problems in lower-dimensional spaces, and the solution to the original problem is approximated by some combination of the solutions to 59 Xiao and Zhu these sub-problems. In a general sub-space model, a d-dimensional key vector k can be mapped into a set of d ′ -dimensional vectors {K′ 1, ..., K′η}. To simplify modeling, we can do this by vector segmentation, that is, we segment k into η sub-vectors, each having d ′ = d η dimensions. We can transform all query and value vectors in the same way. Then, the attention model is applied in each of these sub-spaces. This method, however, does not reduce the total amount of computation. As presented in Lample et al. (2019)’s work, we can instead approximate the dot-product attention over a set of key-value pairs by considering top-p candidates in each sub-space. More precisely, we find p-best key-value pairs in each sub-space, which is computationally cheaper. The Cartesian product of these p-best key sets consists of p η product keys. Likewise, we obtain p η product values. The remaining work is simple: the d-dimensional queries attend to these d-dimensional product keys and values. An interesting difference between this sub-space model and the d-dimensional space model is that the generated product keys and values may be different from any of the original key-values {(k1, v1), ...,(ki−1, vi−1)}. This provides a way for learning new representations of the past information. So far we have discussed approaches to dimensionality reduction along either the n or d dimension. It is straightforward to combine them to develop a “lower-dimensional” model. As an example, suppose that we have the n → n ′ reduction for keys and values, and the d → d ′ reduction for queries and keys. The model takes the form Attself(S) = AV ′ A = Softmax(Q′K′T √ d ′ + M) (149) where Q′ ∈ R n×d ′ , K′ ∈ R n ′×d′ , and V ′ ∈ R n ′×d′ are low-dimensional representations for queries, keys and values. As usual, we can easily obtain these representations through the linear mappings of Q, K and V. The time and space complexities of this model are O(n ′ · n · d ′ ) and O(n ′ · n + n ′ · d ′ ). 5.4 Parameter and Activation Sharing Redundancy is common to most large-scale neural networks. As a result, many of these models are over-parameterized, making the training and inference less efficient. One common approach to redundancy reduction is to simplify the modeling by removing useless components of the models, for example, we can either prune a complex model or share sub-models among different components of it to obtain a reasonably small model. In this sub-section, we discuss methods of parameter and intermediate state sharing in Transformer models. We leave the discussion of model transfer and pruning to Section 5.7. Shared-parameter architectures are widely used in neural network-based systems. Wellknown examples include CNNs and RNNs, where the same set of parameters (or layers) is applied across different regions of the input. This produces a “big” neural network, parts of which have the same architecture and the same shared parameters. For Transformers as well as other sequence models, the sharing mechanism can be applied to different levels of modeling. A simple example, which might be not related to architecture design, is shared embedding. In machine translation, a typical strategy for dealing with words in two languages is to develop two separate embedding models. Alternatively, one can use a single 60 Introduction to Transformers embedding model for both languages. The parameters of the model are then learned during the training of both the source-side and target-side networks. Such a strategy is also often adopted in multi-lingual sequence models, such as language models that are able to deal with texts in many different languages. For multi-layer neural networks, a popular method is layer-wise sharing. Suppose there is a stack of layers, all of which have the same form S l = Layer(Sl−1 ; θ l ) (150) We can tie the parameters for some or all of these layers. For example, given a set of layers {l1, l2, ..., ln}, we enforce the constraint θ l1 = θl2 = ... = θln , so that we can obtain a smaller model and the optimization of the model can be easier. In practice, this shared-layer model is highly advantageous if many layers are involved, because we can repeat the same process many times to construct a very deep neural network (Dehghani et al., 2018). For example, sharing a single FFN sub-layer across the Transformer encoder is found to be effective in reducing the redundancy in machine translation systems (Pires et al., 2023). For Transformers, sharing can also be performed in multi-head attention. An example of this is multi-query attention (Shazeer, 2019). Recall from Section 2.3 that the output of a head h in standard multi-head self-attention can be written as Chead h = Attqkv(S q h , S k h , S v h ) = Attqkv(SWq h , SWk h , SWv h ) (151) Here S q h = SWq h , S k h = SWk h , and S v h = SWv v are the query, key, and value, which are obtained by linearly transforming the input S with distinct parameter matrices Wq h , Wk h , and Wv h . In multi-query attention, we share the same key and value across all the heads, but use different queries for different heads. The form of this model is given by Chead h = Attqkv(SWq h , SWk 0 , SWv 0 ) (152) Here the key SWk 0 and value SWv 0 are irrelevant to h. Hence we need only compute them once rather than computing them several times. As a result, we can make a significant saving in computational cost, especially if the number of heads is large. Multi-query attention has been successfully incorporated into recent large language models, such as Llama 2 (Touvron et al., 2023b) and Falcon14. By extending the idea of sharing to more general situations, any intermediate states can be shared across a neural network. For example, reusing neuron activations allows a submodel to be applied multiple times. For Transformers, sharing can be considered inside the process of self-attention. It is found that the attention maps of different layers are similar in some NLP tasks (Xiao et al., 2019). Therefore, it is reasonable to compute the attention map only once and then use it in the following layers. If we make a further generalization of the sharing mechanism, we can view it as a process by which we use the result produced previously rather than computing it on the fly. It is thus possible to reuse the information across different runs of a neural network. A related example is reversible residual networks, in which activations of one layer can 14. https://falconllm.tii.ae/index.html 61 Xiao and Zhu be recovered from the activations of the following layer (Gomez et al., 2017). Hence we only keep the output of the latest layer in the forward pass. Then, in the backward pass of training, we reconstruct the output of each layer from its successor. One advantage of this reversible treatment is that the information produced in the forward pass is shared implicitly, and the model is memory-efficient (Kitaev et al., 2020). 5.5 Alternatives to Self-Attention We have seen that the use of self-attention is a primary source of the large computation and memory requirements for Transformer systems. It is natural to wonder if there are efficient alternatives to self-attention models. Here we present briefly some of the Transformer variants in which self-attention sub-layers are not required and we instead replace them with other types of neural networks. 5.5.1 CNN as A Replacement of Self-Attention CNNs are simple and widely used neural networks, and are considered as potential alternatives to self-attention models. To apply CNNs to Transformers, all we need is to construct a convolutional sub-layer to replace the self-attention sub-layer in a Transformer block. While a filter of CNNs has a restricted receptive field and thus takes inputs from a “local” context window, large contexts can be easily modeled by stacking multiple convolutional sub-layers. One key advantage of CNNs is that the number of elementary operations required to run CNNs is a linear function of the sequence length n, compared with the quadratic function for self-attention networks. In practical systems, there have been many highly-optimized implementations for CNNs, making it easier to apply them to sequence modeling. For further improvements to memory efficiency, we can use lightweight CNN variants, for example, depth-wise CNNs (Wu et al., 2018a). 15 5.5.2 Linear Attention As with many practical approaches to sequence modeling, there is also considerable interest in developing linear models in order to speed up the processing of long sequences. While there are many ways to define a linear model, one general form that is commonly used in 15. In CNNs, a filter (or a set of filters) combines the input variables in the receptive field into an output variable (or a set of output variables) via linear mapping. Suppose that the input and output of a problem are represented as sequences of feature vectors. Given a filter having a d × k receptive field, we slide it along the sequence. At each step, the filter takes d × k input features and produces an output feature. This procedure is typically expressed by y = ReduceSum(x ⊙ W) (153) where x ∈ R k×d is the vector representation of the input, y ∈ R is the output feature, and W ∈ R k×d is the weight matrix. The function ReduceSum(·) computes the sum of all element-wise products between x and W. If we want the input and output to have the same number of features, we can design d filters and the number of parameters will be d 2 · k. In depth-wise CNNs, we tie the weights across different feature dimensions. More precisely, all the column vectors of W are the same. Thus, the number of the unique parameters of the model is reduced to d · k (each W corresponding to a filter having k unique parameters). 62 Introduction to Transformers sequence models is zi = f(a · zi−1 + b · si) (154) Here si represents some intermediate states of the model at step i, and zi represents the summary of the history states up to step i. It is easy to see that this is a recurrent model: the output at step i depends only on the input at the current step and the output at the previous step. As with the popular design choices in neural network-based systems, the linear part is followed by a transformation f(·) which can be either an activation function or a feedforward neural network. Note that, Eq. (154) defines a standard linear model only if f(·) is a linear function. The use of f(·) gives greater flexibility in modeling the problem, although the term linear model may not be applied if f(·) chooses a non-linear form. The above formula describes a linearly structured model which can be seen as an instance of a general family of mathematical models. Typically, it can be represented as a chain structure, or an ordered set of nodes. The model repeats the same computation process from the first node to the last, each time taking the information from the current and previous steps and producing an output vector that is used in the following time steps. As a result, the space and time cost of the model scales linearly with the length of the chain. We can extend Eq. (154) to a standard RNN model by simply making a linear transformation of the current input and the previous state, that is, zi = f(zi−1 · Wz + si · Ws). It is thus straightforward to apply RNN and its variants to Transformer to obtain a hybrid model. For example, we can use LSTM and GRUs in building some of the Transformer layers to combine the merits of both recurrent models and self-attentive models (Chen et al., 2018b). In fact, we may be more interested in developing linear attention models, so that we can obtain an efficient system, while still retaining the benefit of globally attentive sequence modeling. Part of the difficulty in doing this is that the form of self-attention is not linear. Let us take a moment to see how this difficulty arises. Recall that the result of self-attention can be written in the following form Attself = A · V = ψ(Q · KT) · V (155) Here ψ(·) is a function that is composed by taking the scaling, exponentiating, masking and normalization operations (i.e., ψ(a) = Normalize(Mask(exp( √a d )))). Because ψ(·) is a complex non-linear function, there is no obvious equivalent that simplifies the computation, and we have to calculate the two matrix multiplications separately (one inside ψ(·) and one outside ψ(·)). As a consequence, we need to store all the key-value pairs explicitly, and visit each of them given a query. Not surprisingly, this leads to a model whose computational cost grows quadratically with the sequence length n. Although in self-attention keys and values are coupled, they are used in separate steps. An elegant form of this model might be that allows for a direct interaction between the keys and queries, so that we can encode the context information in a way that is irrelevant to the queries. A trick here is that we can remove the non-linearity from ψ(·) by using a feature space mapping ϕ(·) on the queries and keys, and reformulate ψ(Q · KT) (i.e., A) in a form of matrix products. For example, recall from Section 5.3 that we can transform Q 63 Xiao and Zhu and K to Q′ = ϕ(Q) ∈ R n×d ′ and K′ = ϕ(K) ∈ R n×d ′ through the mapping ϕ(·). Then, we define the form of the attention model to be Attself ≡ ψ ′ (Q′· K′T) · V = Q′· K′T D · V = Q′· K′T· V D (156) where ψ ′ (a) = a D . From this definition, we see that, in the case of transformed queries and keys, the query-key product needs not be normalized via Softmax, but needs only be normalized via a simple factor D. Hence the model has a very simple form involving only matrix multiplication and division, allowing us to change the order of the operations using the associativity of matrix multiplication. This leads to an interesting procedure: keys and values are first encoded via K′T · V, and then each query attends to this encoding result. Given that K′T · V = Pn j=1 k ′T j · vj , we can write K′T · V in the form of Eq. (154), as follows µj = µj−1 + k ′T j · vj (157) Here µj ∈ R d ′×d is a variable that adds k ′T j · vj at a time. Likewise, we can define another variable νj ∈ R d ′ νj = νj−1 + k ′T j (158) Then, the output of self-attention for the j-th query can be written as (see also Eq. (147)) Attself,j = q ′ j · µn q ′ j · νn (159) Clearly, this is a linear model, because µn and νn are linear with respect to n. In simple implementations of this model, only µj and νj are kept. Each time a new query is encountered, we update µj and νj using Eqs. (157) and (158), and then compute Attself,j = q ′ j ·µj q ′ j ·νj 16 . One straightforward extension to the linear attention model is to allow Eqs. (157) and (158) to combine different terms with different weights. For example, we can redefine µj and νj as µj = a · µj−1 + (1 − a) · k ′T j · vj (160) νj = a · νj−1 + (1 − a) · k ′T j (161) and train the parameter a as usual. Also, we can treat a as a gate and use another neural network to compute a (Peng et al., 2021). Another model design is to add more terms to 16. In autoregressive generation, we generate a sequence from left to right. In this case, we need not consider the keys and values for positions > j. 64 Introduction to Transformers Eqs. (157) and (158) in order to give a more powerful treatment of the linear attention approach (Bello, 2020; Schlag et al., 2021). We have seen a general idea of designing linear models for the attention mechanism. The key design choice of such models is to remove the Softmax-based normalization, thereby taking linear forms of representations based on various intermediate states of the models. This motivates several recently developed alternatives to self-attention in which efficient inference systems are developed on the basis of recurrent models of sequence modeling (Peng et al., 2023; Sun et al., 2023). While these systems have different architectures, the underlying models have a similar form, as described in Eq. (154). Note that, by using the general formulation of recurrent models, we need not restrict the modeling to the standard QKV attention. Instead we may give new meanings and forms to the queries, keys, and values. The discussion here is also related to the memory models discussed in Section 5.2. From the memory viewpoint, the keys and values can be treated as encodings of the context. Therefore, in the linear attention model above we have a memory system in which two simple variables µj and νj are used to represent all the context information up to position j. This results in a fixed-length memory which is very useful in practice. There are also other linear approaches to encoding long sequences. For example, we can view the moving average model as an instance of Eq. (154), and average a series of state vectors of a Transformer system, either weighted or unweighted. 5.5.3 State-Space Models In control systems, state-space models (SSMs) are representations of a system whose input and output are related by some state variables (or states for short), and whose dynamics is described by first-order differential equations of these states. As a simple example, we consider a continuous time-invariant linear system which is given in the form of the state-space representation dz(t) dt = z(t) · A + s(t) · B (162) o(t) = z(t) · C + s(t) · D (163) Here s(t), o(t), and z(t) are the values of the input variable, output variable and state variable at time t 17. In a general setting, s(t), o(t), and z(t) may have different numbers of dimensions. To simplify the discussion here, we assume that s(t), o(t) ∈ R d and z(t) ∈ Rdz 18 . Eq. (162) is called the state equation, where A ∈ R dz×dz is the state matrix and B ∈ R d×dz is the input matrix. Eq. (163) is called the output equation, where C ∈ R dz×d is the output matrix and D ∈ R d×d is the feedforward matrix. These equations describe a continuous mapping from the variable s(t) to the variable o(t) over time. They are, therefore, often used to deal with continuous time series data. To apply this model to the sequence modeling problem discussed in this chapter, we need to modify the above equations to give a discrete form of the state-space representation. 17. We use boldface letters to emphasize that the variables are vectors. 18. In a general state-space model, all these variables are represented as vectors of complex numbers. Because the models defined on the field of complex numbers is applicable to case of real number-based statespaces, we restrict our discussion to variables in the multi-dimensional real number field. 65 Xiao and Zhu Suppose that {s0, s1, ..., sn} is a sequence of input data points sampled from s(t) with time step ∆t. Similarly, we define {z0, z1, ..., zn} and {o0, o1, ..., on} as sequences of the state and output vectors. Given this notation, we now have a discretized version of the SSM, written as zt = zt−1 · A + st · B (164) ot = zt· C + st · D (165) This formulation of the SSM defines an RNN with a residual connection. To be more precise, Eq. (164) describes a recurrent unit that reads the input at step t and the state at step t − 1, without using any activation function. Eq. (165) describes an output layer that sums both the linear transformations of the state zt and the identity mapping st. The parameters A, B, C, and D can be induced from A, B, C and D in several different ways, depending on how Eq. (162) is approximated by Eq. (164)19. One approach to time discretization, called bilinear transform or Tustin’s method, gives a model in which the parameters take the form A = (I − ∆t 2 · A) · (I − ∆t 2 · A) −1 (172) B = ∆t · B · (I − ∆t 2 · A) −1 (173) C = C (174) D = D (175) 19. The discretization process can be interpreted as a numerical method of solving the differential equation. Note that Eq. (162) is an ODE dz(t) dt = g(z(t), t) (166) where g(z(t), t) = z(t) · A + s(t) · B (167) There are many numerical approximations to the solutions to the ODE. For example, the Euler method of solving the ODE can be expressed in the form (see in Section 4.3) zt = zt−1 + ∆t · g(zt−1, t) (168) Substituting Eq. (167) into Eq. (168) yields zt = zt−1 + ∆t(zt−1 · A + st · B) = zt−1 · (I + ∆t · A) + st · (∆t · B) (169) This gives one of the simplest forms of the discretized state equations (Gu et al., 2022b), that is, A = I + ∆t · A (170) B = ∆t · B (171) 66 Introduction to Transformers An alternative approach is to use the Zero-Order-Hold (ZOH) discretization which has the form A = exp(∆t · A) (176) B = ∆t · B · (exp(∆t · A) − I) · (∆t · A) −1 (177) C = C (178) D = D (179) A detailed discussion of these approaches lies beyond the scope of this paper, and we refer the interested reader to standard textbooks on control theory for further details (˚Astr¨om and Wittenmark, 2013). The recurrent form of Eq. (164) makes it easy to compute the states and outputs over a sequence of discrete time steps. We can unroll zt and otin a feedforward fashion z0 = s0 · B o0 = s0 · B · C + s0 · D z1 = s0 · B · A + s1 · B o1 = s0 · B · A · C + s1 · B · C + s1 · D z2 = s0 · B · A 2 + s1 · B · A + s2 · B o2 = s0 · B · A 2 · C + s1 · B · A · C+ s2 · B · C + s2 · D ...... ...... It is easy to write zt = X t i=0 si· B · A t−i (180) ot = X t i=0 si· B · A t−i · C + st· D (181) Clearly, the right-hand side of Eq. (181) can be interpreted as a merged output of a convolutional layer and a linear layer. Given that X t i=0 si· B · A t−i · C = s0 s1 ... st · h B · A t · C B · A t−1 · C ... B · C i (182) we define a filter having the parameters Wssm = h B · A nmax · C B · A nmax−1 · C ... B · C i (183) where nmax is the maximum length of the sequence20. Then, the output of the state-space model for a sequence S =    s0 . . . sn    can be expressed as O = Conv(S,Wssm) + Linear(S, D) (184) 20. Here Wssm can be represented as an nmax × d × d tensor. 67 Xiao and Zhu where Conv(·) is the convolution operation, and Linear(·) is the linear transformation operation. Such a treatment of the state-space model enables the system to be efficiently implemented using fast parallel convolution algorithms. Unfortunately, the above model performs poorly in many cases. As with many deep neural networks, careful initialization of the model parameters plays an important role in such models. For example, restricting the state matrix to particular types of matrices is found to be useful for learning and generalizing on long sequences (Gu et al., 2022a). Another problem with the basic state-space model is that it involves multiplication of multiple matrices. If the sequence is long (i.e., n is a large number), computing A n will be computationally expensive and numerically unstable. One of the most popular approaches to developing practical state-space models for sequence modeling is diagonalization. The basic idea is that we can transform a state-space model into a new state-space where A (or A) is diagonalized. Given a state-space model parameterized by (A, B, C, D), we can define a new state-space model (UAU−1, BU−1, UC, D) by introducing an invertible matrix U. It is easy to prove that the two models are equivalent under the state-space transformation U21. By using this state-space transformation, and by noting that A (or A) can be written as a canonical form P−1ΛP22, we can enforce the constraint that A (or A) is a diagonal matrix, giving rise to diagonal state-space models. To illustrate, consider the filter used in the convolutional representation of the state-space model (see Eq. (182)). Assuming that A = P−1ΛP, we can write B · A t · C as B · A t · C = B · (P −1ΛP)t · C = B · (P −1ΛP) · (P−1ΛP)· · ·(P−1ΛP) · C = (B · P −1 ) · Λ t · (P · C) (186) Since Λ is a diagonal matrix, we can efficiently compute Λt by simply raising all the entries of Λ to the t-th power. We then have a computationally cheaper model, in which A ′ = Λ (187) B ′ = B · P −1 (188) C ′ = P · C (189) D ′ = D (190) More detailed discussions of diagonal state-space models in sequence modeling can be found in Gu et al. (2021)’s work. The application of state-space models to Transformer is simple. Each self-attention sublayer is replaced in this case by an SSM sub-layer as described in Eqs. (164) and (165). As we have seen there is a close relationship between state-space models and both CNNs and RNNs. For sequence modeling, we can deal with a sequence of tokens either sequentially 21. A state space transformation can be seen as a process of mapping all states from the old space to the new space, by s ′ (t) = s(t) · U (185) 22. Λ denotes a diagonal matrix. 68 Introduction to Transformers as in RNNs, or in parallel as in CNNs. This leads to a new paradigm that takes both the sequential view and the parallel view of the sequence modeling problem — for training, the system operates like CNNs to make use of fast parallel training algorithms; for prediction, the problem is re-cast as a sequential update problem which can be efficiently solved by using RNN-like models. It should be noted, however, that state-space models are found to underperform Transformer models for NLP problems, such as language modeling, although they have achieved promising results in several other fields. Further refinements are often needed to make them competitive with other widely used sequence models (Fu et al., 2022). While the formalism of state-space models is different from those we discussed in this chapter, it provides a general framework of sequence modeling in which the problem can be viewed from either of two different perspectives and we choose different ones for different purposes. Several recent sequence models were motivated by this idea, leading to systems exhibiting properties of both parallel training and RNN-style inference (Orvieto et al., 2023; Sun et al., 2023). 5.6 Conditional Computation So far in our discussion of efficient Transformer models, we have assumed that the model architecture is given before beginning the training of a model and is then fixed throughout. We now turn to the case of learning efficient model architectures. Without loss of generality, we can write a model in the form y = Model(x, g(x)) (191) where x and y are the input and output of the model. g(x) is a model function that returns the model architecture and corresponding parameters for the given input x. In general, we adopt the convention prevalent in learning problems of using a fixed model architecture and learning only the parameters, say, g(x) = θ. In this case, the goal of learning is to find the optimal values of the parameters given the model architecture and training data. On test data, we make predictions using the same model architecture along with the optimized parameters. A natural extension of this approach is to consider the learning of both the model architecture and parameters. In architecture learning, we would like to find a model function gˆ(x) that produces the optimal model architecture and parameter values given the input x. However, searching a hypothesis space of all possible combinations of architectures and parameter choices is extremely difficult, and so we need practical methods to achieve the goal. Two classes of methods can be applied. • Neural Architecture Search (NAS). In automated machine learning (AutoML), neural architecture search is the process of exploring a space of neural networks to find one that best fits some criterion (Elsken et al., 2019; Zoph and Le, 2016). Once the optimal neural network is determined, its parameters will be trained as usual, and then be applied to new data. In order to make search tractable, several additional techniques, such as search space pruning and fast search algorithms, are typically used. Applying neural architecture search to the development of efficient neural networks is straightforward (Howard et al., 2019; Tan and Le, 2019). We need only incorporate efficiency measures into the performance estimation of neural networks, 69 Xiao and Zhu for example, the search can be guided by a criterion that penalizes neural networks with high latency or excessive memory requirements. • Dynamic Neural Networks. The key idea of dynamic neural networks is to adapt a neural network dynamically to various inputs (Gupta et al., 2004; Han et al., 2021). Ideally, we would like to learn ˆg(·), and then, for any input xnew, we apply the model Model(xnew, gˆ(xnew)). As a result, at test time we may have different model structures and/or different parameters for different inputs. However, it is infeasible to develop a function ˆg(·) that can model arbitrary neural networks. In practice, ˆg(·) is often considered to represent a family of sub-networks of a super-network. The problem is therefore reframed as a simpler problem to learn to choose which sub-network is used for a given input. From a machine learning perspective, the approaches to neural architecture search are general and can be applied to any neural network. On the other hand, from a practical perspective, it is still difficult to find an efficient neural network that is sufficiently powerful and generalizes well. While neural architecture search provides interesting ideas for developing efficient Transformer models, we make no attempt to discuss it here. Instead, the reader can refer to the above papers to have a general idea of it, and refer to So et al. (2019), Wang et al. (2020a), and Hu et al. (2021)’s work for its application to Transformers. In this sub-section we focus on a particular family of approaches to dynamic neural networks, called conditional computation. This concept was originally motivated by the dynamic selection of neurons of a neural network (Bengio et al., 2015, 2013). More recently, it has often been used to refer to as a process of dynamically selecting parts of a neural network. A narrow view of conditional computation is to see g(·) as an adaptive neural network which dynamically reduces or grows the number of computation units (such as neurons and layers). As a result, computation can adapt to changing conditions, and we can seek a good accuracy-latency trade-off by this adaptation mechanism. A common way to achieve this is to learn how to skip some computation steps so that we can work with a necessary sub-set of the network (Xu and Mcauley, 2023). One of the simplest methods, sometimes called early stopping, is to stop the computation at some point during reading or generating a sequence. This technique is often used in practical sequence generation applications where a low latency is required. Suppose y1...ynmax is the longest sequence that the system can generate, and s1...snmax is the corresponding sequence of the states of the top-most Transformer layer. Then we develop a model fstop(·) that takes one hidden state si at a time and produces a distribution of a binary variable c ∈ {stop, nonstop} Pr(c|si) = fstop(si) (192) The generation process terminates if Pr(stop|si) is sufficiently large, for example Pr(stop|si) ≥ Pr(nonstop|si) + θstop (193) where θstop denotes the minimal margin for distinguishing the two actions23. This formulation is also related to the stopping criterion problem that is frequently discussed in search 23. An equivalent form of Eq. (193) is Pr(stop|si) ≥ 1+θstop 2 . 70 Introduction to Transformers algorithms for sequence generation. fstop(·) can be designed in several different ways. For example, in many practical applications, the stopping criterion is based on simple heuristics. Alternatively, we can define the function fstop(·) as a neural network and train it using labeled data. The above approach can be easily extended to handle situations in which some of the tokens are skipped. This learning-to-skip approach is typically used in the encoding stage in which all input tokens are given in advance. Let h1...hm be low-level representations of a sequence x1...xm. Like Eq. (192), we can develop a model Pr(c|si) (c ∈ {skip, nonskip}) to determine whether the token xi can be skipped. Figure 15 (a) and (b) show illustrations of early stopping and skipping. Note that the learning-to-skip method has overlap with other lines of research on training neural networks. For example, erasing some of the input tokens in training is found to be useful for achieving higher generalization of Transformer models (Kim and Cho, 2021; Shen et al., 2020). This method is also related to the downsampling methods which will be discussed in Section 5.8. A second approach to conditional computation is to resort to sparse expert models, or its popular instance — MoE (Yuksel et al., 2012). In deep learning, a model of this kind is typically built from a number of experts which are neural networks having the same structure but with different parameters. In this way, we can construct a big model by simply increasing the number of experts. When running this model, during either training or prediction, we activate only a small number of the experts by some routing algorithm (see Figure 15 (c)). An MoE model is an adaptive network since each time we have a new input, the model routes it to different experts. In Section 4.4, we presented the basic form of MoE, and showed how Transformer models can be scaled up by this sparse method. For a comprehensive review of the recent advances in MoE, we refer the interested reader to Fedus et al. (2022a)’s work. A third approach that can be used to adapt a Transformer model to changing input is to dynamically shrink the number of layers. Several methods have been proposed to do this in an attempt to improve inference efficiency. The simplest of these is to exit at some hidden layer by which we can still make accurate predictions for the sample (see Figure 15 (d) and (e)). To do this, we can either determine the appropriate depth for the entire sequence (call it a sentence-level depth-adaptive model), or use an adaptive depth for each token (call it a token-level depth-adaptive model). Here we consider token-level depth-adaptive models but the methods can be easily extended to sequence-level depth-adaptive models. Suppose there are L stacked layers at position i 24. We would ideally like to find a layer in the stack, which can be used as the last hidden layer for making predictions, and whose depth is as low as possible. However, we cannot simply use the L-th layer of the stack as the oracle for this problem, because we never know in advance what the last layer generates during inference. Instead, we need to determine whether the network should stop growing at depth i, considering the layers generated so far. Now suppose we have a Transformer decoder which produces a distribution over a vocabulary V at each step. As usual, we denote the output of the l-th layer at step i by s l i . For each s l i , we create an output layer that produces a distribution p l i over the vocabulary 24. A layer is a standard Transformer block consisting of a few sub-layers. 71 Xiao and Zhu y0 y1 y2 − − y1 y2 y3 stop (a) Early Stopping (Decoder) x1 x2 x3 x4 x5 h1 h2 h3 h4 h5 ... ... ... ... ... (b) Token Skipping (Encoder) x1 x2 x3 x4 x5 ... ... ... ... ... expert1 expert2 expert3 expert4 (c) MoE (Encoder) y0 y1 y2 y3 y4 y1 y2 y3 y4 y5 (d) Sentence-level Depth Adaptation (Decoder) y0 y1 y2 y3 y4 y1 y2 y3 y4 y5 (e) Token-level Depth Adaptation (Decoder) y0 y1 y2 y3 y4 y1 y2 y3 y4 y5 (f) Layer Skipping (Decoder) Figure 15: Methods of conditional computation, including early stopping, token skipping, MoE, sentence-level depth adaptation, token-level depth adaptation, and layer skipping. While these methods are illustrated using either the encoding or decoding process, most of them can be applied to both Transformer encoders and decoders. 72 Introduction to Transformers (call it an early exit classifier), given by p l i = Softmax(s l i · Wl o ) (194) where Wl o ∈ R d×|V | is the parameter matrix. Hence we have L − 1 additional output layers, each corresponding to a hidden layer from depth 1 to L − 1. At training time, we consider the cross-entropy losses of {p 1 i , ..., p L−1 i }, and train these layers together with the Transformer model. At test time, the depth of the network grows as usual, and we use {p 1 i , ..., p l i } and/or {s 1 i , ..., s l i } to determine whether we should exit at the l-th layer. There are several exit criteria, for example, • Common criteria are based on measures of the confidence of predictions. A simple method is to compute the entropy of p l i , and exit if this entropy is above a pre-defined value. • Alternatively, one can view the maximum probability of the entries of p l i as the confidence of the prediction. • Instead of considering the output of a single layer, we can also examine the change in the outputs or hidden states over a number of layers. For example, we can measure the similarity between p l−1 i and p l i or between s l−1 i and s l i . If the similarity is above a given threshold, then we say that the output of the neural tends to converge and the number of layers can stop growing. • The above method can be extended to examine the change in the predictions made by the classifiers associated with the layers. For example, the model can choose to exit if the predictions made by the classifiers remain unchanged for a number of layers. Discussions of these criteria can be found in the related papers (Schuster et al., 2022; Xin et al., 2020; Zhou et al., 2020). There are a variety of ways to improve these early exit methods. One is to explore other forms of the prediction for each layer. For example, we can develop a model that directly predicts how many layers we need to model the input (Elbayad et al., 2020). Another line of research on early exit focuses on better training for these models, for example, we can consider various loss functions for training the classifiers (Schuster et al., 2022; Schwartz et al., 2020). In addition, there is also interest in learning the combination of the outputs of multiple layers so that we can make predictions by using multiple levels of representation (Liao et al., 2021; Zhou et al., 2020). A problem with token-level adaptive-depth models is that the representations at certain depths may be absent in the previous steps. In this case, standard self-attention is not directly applicable, because we may not attend to the previous tokens in the same level of representation. For training, this can be addressed by using all the L layers of the full model. For inference, we can either duplicate the layer from which we exit to fill up the layer stack, or modify the self-attention model to enable it to attend to the representations of the previous tokens at different depths. It is also possible to select any sub-set of the layers for constructing a shallow network. The adaptive models therefore can be generalized to skipping models (see Figure 15 (f)). As with the early exit problem, the skipping problem can be framed as a learning task, in which a classifier is trained to decide whether a layer should be dropped. The learning-to-skip problem has been studied in the field of computer vision (Wang et al., 2018b; Wu et al., 73 Xiao and Zhu 2018b). However, learning a skipping model for large-scale, deep neural networks is difficult. For practical systems, it still seems reasonable to use heuristics or cheap models to obtain a neural network having skipped layers, which has been discussed in recent pre-trained NLP models (Del Corro et al., 2023; Wang et al., 2022c). 5.7 Model Transfer and Pruning Many large Transformer models have been successfully developed to address NLP problems. A common question is: can we transform a large, well-trained model into a smaller one that allows for more efficient inference? At a high level, this can be thought of as a transfer learning problem in which the knowledge is transferred from one model to another. But we will not discuss this general topic, which spans a broad range of issues and models, many outside the scope of this chapter. Instead, we narrow our discussion to two kinds of approaches that are widely used in learning small neural networks from large neural networks. 5.7.1 Knowledge Distillation Knowledge distillation is a process of compressing the knowledge in a large neural network (or an ensemble of neural networks) into a small neural network (Hinton et al., 2015). In supervised learning of neural networks, the objective functions are generally designed to represent some loss of replacing the true answer with the predicted answer. Hence we can minimize this loss so that the models are trained to output the true answer. While models are typically optimized on the training data in this manner, what we really want is to generalize them to new data. This is, however, difficult because we have no information about generalization in training with the ground-truth. In knowledge distillation, instead of forcing a model to stay close to the ground-truth output, we train this model to generalize. To do this, we directly transfer the knowledge (i.e., the generalization ability) of a pre-trained model to the model that we want to train. A frequently used approach to knowledge distillation is teacher-student training. A teacher model is typically a relatively large neural network that has already been trained and can generalize well. A student model is a relatively small neural network, such as a neural network with fewer layers, to which we transfer the knowledge. A simple way to distill the knowledge from the teacher model into the student model is to use the output of the teacher model as the “correct” answer for training the student model. Suppose we have a teacher Transformer model that can generate a sequence of distributions {Pr(·|y0, x), ..., Pr(·|y0...yn−1, x)} for the input x. To keep the notation simple, we denote the distribution Pr(·|y0...yi−1, x) as pei. Similarly, we denote the output of the student Transformer model for the same input as pi . As usual, we consider a loss function Loss(pei, pi) (such as the cross-entropy function) for computing some distance between pei and pi. Then, we can define the loss over the entire sequence as L(x, θ) = 1 n Xn i=1 Loss(pei, pi) (195) 74 Introduction to Transformers where θ denotes the parameters of the student model25. Using this loss, we can optimize θ, for any given set of source sequences P {x1, ..., xK}, in such a way as to minimize the quality N k=1 L(xk, θ). Several different extensions to this basic method have been developed to model the problem of knowledge transfer between two models. A simple way is to use the hidden states instead of the output probabilities as the training targets (Romero et al., 2014). In this case, the objective is to minimize the difference between some hidden states of the teacher model and the corresponding states of the student model. Rather than using the outputs of various layers as the targets for training the student model, another technique is to model the relations between samples and train the student model by minimizing some difference between the relation encodings of the teacher and student models (Park et al., 2019; Peng et al., 2019). For example, we can develop a relation encoding model based on the Transformer architecture. The goal is then to optimize the student model so that its corresponding relation encoding of a group of samples is as close as possible to that of the teacher model. For sequence generation problems, a special case of knowledge distillation, which can be viewed as a means of data augmentation, is often used for developing lightweight models (Kim and Rush, 2016). For example, consider the problem of transferring the translation ability of a well-developed machine translation model (i.e., the teacher model) to a new model (i.e., the student model). Given a set of source-side sentences {x1, ..., xK}, we can use the teacher model to translate each xk to a target-side sentence yek. Then, by treating xk and yek as paired sentences, we obtain a bilingual dataset consisting of {(x1, ye1), ...,(xK, yeK)}. We can use this bilingual dataset as the labeled dataset to train the student model as usual. One advantage of this data argumentation method is that it is architecture free, and we do not even need to understand the internal architectures of the teacher and student models. Hence we can apply this method if we have a black-box teacher model. More detailed discussions of knowledge distillation can be found in Gou et al. (2021) and Wang and Yoon (2021)’s surveys. 5.7.2 Structured Pruning Pruning is among the most popular of the model compression methods and has been applied to a broad range of systems. One common approach to pruning is unstructured pruning, by which we activate only some of the connections between neurons. However, as with most sparse models, models pruned in this way typically require special implementations and hardware support, which in turn reduces their efficiency in some applications. A simple but more aggressive way to do pruning is to use structured pruning. In deep learning, structured pruning is a technique that removes a group of neurons or connections together. For example, we can remove an entire layer of neuron from a neural network to obtain a shallower model. As multi-layer, multi-head neural networks, Transformers are naturally suited to structured pruning, and we can prune a Transformer network in several different ways. For example, we can prune some of the heads in multi-head attention (Michel et al., 2019; Voita et al., 2019), or some of the layers in the layer stack (Hou et al., 2020; Kim and Awadalla, 2020). 25. We omit the parameters of the teacher model because they are fixed throughout the training process. 75 Xiao and Zhu Formally, we can represent a neural network as a set of parameter groups {θ1, ..., θR}, each corresponding to a component or sub-model of the model. Our goal is to find a sub-set of {θ1, ..., θR} by which we can build a model that yields good performance, while having a lower model complexity. However, a simple search of such a model is infeasible because there are a combinatorially large number of possible model candidates and evaluating all of these models is computationally expensive. One approach to structured pruning is to randomly prune components of a model. One can run the random pruning process a number of times to generate a pool of model candidates and select the best one from the pool. Another approach is to use heuristics to decide which components are not important and can be removed. Common measures of the importance of a parameter group θr include various qualities based on norms of the weights or gradients of θr (Santacroce et al., 2023). We can prune θr if the values of these measures are below (or above) given thresholds. A third approach is to frame the pruning problem as an optimization task by introducing trainable gates indicating the presence of different components (Lagunas et al., 2021; McCarley et al., 2019; Wang et al., 2020c). The pruned model can be induced by using the trained gates. Note that, in many cases, pruning is not a post-processing step for a given trained model, but part of the training. 5.8 Sequence Compression In sequence modeling and generation problems, the time and space complexities are strongly influenced by the length of the input or output sequence, and we prefer the sequence to be short. This is particularly important for Transformer models, as their time and space complexities are quadratic with the sequence length, and the memory footprint and latency can be heavy burdens if the sequence is very long. In the previous subsections, we have discussed modifications to the Transformer architecture for dealing with long sequences. Here we instead consider methods for compressing the sequences into ones with acceptable lengths. One simple approach is to map the input sequence to a fixed-size representation. For example, using the recurrent models discussed in Section 5.2, we can encode a sequence of vectors into a single vector. This method can be easily extended to generate a “larger” representation so that this representation can retain more information of the original input. For example, we can select a fixed number of the hidden states over the sequence to form a new sequence of fixed-length. Another way to represent a variable-length sequence as a fixed-length sequence is to attend the input vectors to some hidden states, usually a fixed number of learnable hidden representations. In Jaegle et al. (2021)’s work, this is done by introducing r hidden representations {u1, ..., ur}, and then attending the input vectors {x1, ..., xm} to these hidden representations. The attention model can be a standard QKV attention model in which we view {u1, ..., ur} as queries and {x1, ..., xm} as keys and values. The output of this model is a sequence of r vectors, which can be used as fixed-length input to downstream systems. A second approach is to use downsampling to compress the sequence into a shorter one. A typical method of downsampling is strided convolution, which has been widely used in computer vision and speech processing. For example, suppose there is a sequence of m vectors ∈ R d . We can develop a filter with a width of 2 and a stride of 2. By taking the 76 Introduction to Transformers sequence as input, the filter produces a sequence of m 2 new vectors ∈ R d , and so we have a reduction rate of 2. Also, we can stack multiple convolutional layers or pooling layers to achieve a desired level of length reduction, called progressive downsampling. However, it seems inevitable that downsampling will lead to information loss (Burchi and Vielzeuf, 2021; Han et al., 2020). We need to consider a trade-off between the compressed sequence length and the performance of downstream systems (Xu et al., 2023b). In NLP, the problem of sequence compression is also closely related to the problem of tokenizing input strings. Therefore, tokenization is a practical approach that can be taken to address the length issue. Segmenting a string into small tokens (such as characters) generally reduces the sparsity of the data, which makes it easier to learn the embeddings of these tokens, but such approaches often lead to a long sequence. By contrast, we will have a shorter sequence if we segment the input string into larger units, but this will suffer from sparse data. In deterministic tokenization methods, which produce tokenization results using statistics collected from the entire dataset, the sequence length can be somehow controlled by adjusting some hyper-parameter, for example, in byte pair encoding (Sennrich et al., 2016), increasing the size of the vocabulary generally reduces the number of the resulting tokens. Another way to obtain an appropriate sequence of tokens is to use a model for choosing among tokenization candidates (Kudo, 2018; Provilkov et al., 2020). As with many probabilistic models for text generation, in this case, we can add priors to the criterion for tokenization selection so that we can express a preference for shorter sequences over longer sequences. A fourth approach to sequence compression is to drop some of the tokens in the sequence. For example, in many practical applications, we chop the sequence when its length exceeds a threshold. We can relate this to the early stopping and skipping approaches in conditional computation. Thus the methods discussed in Section 5.6 are directly applied. The token dropping methods can also be viewed as pruning methods, called token pruning. By discarding tokens that are less important for representing the entire sequence, token pruning can significantly reduce the sequence length while maintaining the performance of NLP systems on downstream tasks (Kim et al., 2023). 5.9 High Performance Computing Methods So far in this section, we have discussed efficient Transformer models from the perspectives of deep learning and NLP. However, we have not considered their efficiency on hardware. As modern hardware provides a variety of modes for running a program, the practical time and memory footprint savings generally depend on the specifications of hardware systems. One line of research on efficient use of computing resources explores methods of parallel computing. There have been many attempts to develop large-scale Transformer models by using a cluster of machines. Typically, scaling Transformers to models with billions or even tens of billions of parameters requires a careful design of parallelism strategies for sharding the big networks. More efficient implementations of such systems also need considerations of networking and communication in the cluster, as well as the utilization of sparse models that activate only a small sub-set of the parameters for each sample, enabling the use of very large models. Most of these methods have been studied in an extensive literature on how to scale up the training of deep neural networks like Transformers efficiently (Barham 77 Xiao and Zhu et al., 2022; Fedus et al., 2022b; Lepikhin et al., 2021). The results of these studies were foundational to many follow-on works on investigating the scaling laws for large language models (Brown et al., 2020; Chowdhery et al., 2022). Since large-scale distributed models are generic and not specialized to the case of Transformers, we skip the discussion of them here. The interested readers can refer to the above papers for more detailed discussions. In this sub-section we consider hardware-aware methods to seek greater computational efficiency for Transformer models. We first consider a simple but widely used method that aims to store and execute neural networks using lower or mixed-precision number representations (Gholami et al., 2022). Conventional neural networks are typically based on single-precision and/or double-precision floating-point representations of data. While singleprecision floating-point data types provide a sufficiently precise way to represent parameters and intermediate states in most cases, in some applications, they are not essential. As an alternative, one can use half-precision (or even lower-precision) formats in storing floatingpoint numbers for neural networks. The size of the resulting model is thus half the size of the original model. One advantage of using half-precision floating-point representations is that, although processing such data types requires new APIs of linear algebra operations and hardware support, it does not change the model architecture, and so we need only a slight modification to the systems. For example, half-precision floating-point representations can be applied to either training or inference of Transformers, or both. Recently, the deployment of large Transformer models has been further improved by quantizing these models. In signal processing, quantization is a process of mapping continuous values (i.e., floating-point representations) to a set of discrete values (i.e., fix-point representations) . This process is in general implemented using a system called quantizer. In the context of neural networks, a quantizer involves two functions — the quantization function and the de-quantization function. The quantization function maps a floating point number to a (lower-bit) integer. A simple quantization function is given by Q(x) = ⌊ x s ⌉ (196) where ⌊·⌉ is a rounding function26, x is the real-valued input, and s is the quantization step size that controls the level of quantization. The quantization function is coupled with a de-quantization function D(r) = s · r (197) With this notation, the quantizer can be expressed as D(Q(x)) = s · ⌊ x s ⌉. The difference between D(Q(x)) and x is called quantization error. A smaller value of s typically reduces the quantization error. In practice, however, we wish to choose an appropriate value of s in order to spread possible values of Q(r) evenly across values of an integer, for example, s = max{D(r)} 2 p−1 where p is the number of bits used to represent an integer and max{D(r)} is the maximum value for D(r). The above equations show one of the simplest cases of quantization. More general discussions of quantization can be found in books on digital signal processing and related surveys (Gray, 1998; Oppenheim and Schafer, 1975; Rabiner and Gold, 1975). 26. ⌊a⌉ returns the integer closest to a. 78 Introduction to Transformers Applying quantization to Transformers is relatively straightforward. The idea is that we quantize the inputs and model parameters using Q(x), and feed them to a quantized Transformer model in which all the layers operate on integer-valued tensors. In other words, we implement the model using integer-only arithmetic. However, the price to be paid for this compressed model, as with many approximation approaches to deep learning, is that its prediction is not as accurate as that of the standard Transformer model. Using integer operations to approximate continuous-valued operations generally leads to approximation errors. These errors will be accumulated if the quantized neural network is deep. Furthermore, Transformer models involve components (such as self-attention sub-layers) that require relatively complex linear algebra operations. Simply applying quantization to these sub-models will lead to high accuracy loss. One solution is to simplify the model architecture and develop new sub-models that is more feasible for quantization. Alternatively, a more common paradigm in quantized neural networks is to add de-quantization functions to the neural networks so that the output of a layer is floating-point tensors and can be used as usual in the following steps. Consider a simple example where we multiply a real-valued input matrix a with a real-valued parameter matrix A. We first quantize a and A, and multiply them using integer-based matrix multiplication. The result is then de-quantized to a real-valued matrix. In this way, we obtain an approximation D(Q(a) · Q(A)) to a · A in a very cheap way. However, sandwiching each layer between Q(·) and D(·) will lead to additional cost of running Q(·) and D(·). In some practical applications, the computational overhead introduced by Q(·) and D(·) is even bigger than the time saving of performing integerbased operations. In general, the benefit of quantizing neural networks would be larger than its cost if the neural networks are large. Therefore, in practice it is common to perform quantized computation only for operations whose computational costs are high. For example, in recent large language models, quantization is primarily applied to the multiplication of large matrices, yielding significant time and memory savings. While the quantization approaches can be used in both training and inference, a widelyused approach is to get Transformer models quantized after training (call it post-training quantization). In this approach, quantization is performed on well-trained floating-pointbased neural networks and there will be fewer quantization-related errors. However, these errors cannot be compensated for because they exist after training. A more promising idea is to involve quantization in training so that the model can learn to compensate for quantization-related errors (Jacob et al., 2018; Nagel et al., 2021). There have been several attempts to apply quantization-aware training to Transformers (Bondarenko et al., 2021; Stock et al., 2021; Yang et al., 2023b). In addition to computational efficiency, another important consideration for high-performance systems is the restrictions of the memory hierarchy. In general, better system design requires considering the speeds and sizes of different levels of memory. The problem is even more complicated when we train large Transformer models on modern hardware where both GPUs and CPUs are used. A general principle of system design is that memory transfer between different memory levels should be minimized. While we would ideally like to have a large high-level memory on which we can store all the data that we need to process, in many practical situations the size of the fast, on-chip memory is orders of magnitude smaller than the size of data. In this case, we can reorder the memory access in the algorithms so that the data used in nearby computation steps 79 Xiao and Zhu can be loaded into the high-speed memory at one time. This idea motivates the development of many fast linear algebra libraries. For example, there are matrix multiplication algorithms that are highly optimized for different shapes of input matrices. It is relatively straightforward to use these optimized linear algebra algorithms to build a Transformer system. But the modules of this system are not optimized as a whole for efficiency improvement. For example, a self-attention sub-layer involves a series of operations of scaling, normalization, and matrix multiplication. Although each of these operations has been implemented in several supported and efficient libraries of linear algebra, successive calls to them still require multiple times of memory transfer when we switch from one operation to another. In practice, a better approach would be that we keep some of the intermediate states in the on-chip memory, and reuse them in the following computation steps instead of fetching them again from the slow memory. For example, on modern GPUs, a simple way to achieve this is to merge multiple operations into a single operation, known as kernel fusion. For Transformer models, a general idea is to design data partitioning and layout strategies by which we maximize the computation on each data block loaded into the high-performance memory, while at the same time minimizing the memory transfer. There have been several attempts to use these strategies to improve the attention models in Transformers (Ivanov et al., 2021; Pope et al., 2023). Some of these methods, such as flash attention and paged attention, have been successfully incorporated into recent large language models (Dao et al., 2022; Kwon et al., 2023). 6. Applications Transformers have a wide range of applications, covering numerous NLP problems. While the Transformer model introduced by Vaswani et al. (2017) is based on a standard encoderdecoder architecture, it is mainly used in three different ways. • Decoder-only Models. By removing the cross-attention sub-layers from a Transformer decoder, the decoder becomes a standard language model. Hence this decoderonly model can be applied to text generation problems. For example, given a sequence of left-context tokens, we use the model to predict the next and following tokens. • Encoder-only Models. Transformer encoders can be treated as sequence models that take a sequence of tokens at once and produce a sequence of representations, each of which corresponds to an input token. These representations can be seen as some sort of encoding of the input sequence, and are often taken as input to a prediction model. This encoder+predictor architecture forms the basis of many NLP systems, for example, systems of sentence classification, sequence labeling, and so on. Pre-trained Transformer encoders can also be used to map texts into the same vector space so that we can compute the distance or similarity between any two texts. • Encoder-Decoder Models. Encoder-decoder models are typically used to model sequence-to-sequence problems. Applications include many tasks in NLP and related fields, such as machine translation and image captioning. Note that while most Transformer-based systems can fall into the above three categories, the same NLP problem can generally be addressed using different types of models. For example, recent decoder-only models have demonstrated good performance on a broad 80 Introduction to Transformers range of problems by framing them as text generation tasks, though some of these problems were often addressed by using encoder-decoder or encoder-only models. To illustrate how the above models are applied, this section considers a few applications where Transformers as chosen as the backbone models. 6.1 Language Modeling Language modeling is an NLP task in which we predict the next token given its preceding tokens. This is generally formulated as a problem of estimating the distribution of tokens at position i+ 1 given tokens at positions 0 ∼ i (denoted by Pr(·|x0, ..., xi) where {x0, ..., xi} denote the tokens up to position i). The best predicted token is the one which maximizes the probability, given by xˆi+1 = arg max xi+1∈V Pr (xi| x0, . . . , xi) (198) where V is the vocabulary. The prediction can be extended to the tokens following ˆxi+1 xˆk+1 = arg max xk+1∈V Pr (xk | x0, . . . , xi, xˆi+1, . . . , xˆk) (199) This model forms the basis of many systems for text generation: given the context tokens x1...xi, we generate the remaining tokens ˆxi+1...xˆk+1 to make the sequence complete and coherent. As discussed in Section 2.1, Transformer decoders are essentially language models. The only difference between the problem of decoding in an encoder-decoder Transformer and the problem of language modeling is that the Transformer decoder makes predictions conditioned on the “context” tokens on both the encoder and decoder sides, rather than being conditioned on preceding tokens solely on one side. To modify the Transformer decoder to implement a standard language model, the cross-attention sub-layers are simply removed and a Transformer decoding block can be expressed as S l = Layerffn(Sl self) (200) S l self = Layerself(S l−1 ) (201) Here S l denotes the output of the block at depth l. Layerself(·) denotes the self-attention sub-layer, and Layerffn(·) denotes the FFN sub-layer. We see that this decoding block has the same form as an encoding block. The difference between the decoding and encoding blocks arises from the masking strategies adopted in training, because the former masks the attention from a position i to any right-context position k > i whereas the latter has no such restriction. A Softmax layer is stacked on the top of the last block, and is used to produce the distribution over the vocabulary at each position. For inference, the Transformer decoder works in an auto-regressive manner, as described in Eq. (199). The training of this model is standard. We learn the model by repeatedly updating the parameters, based on the gradients of the loss on the training samples. This paradigm can be extended to the training of large Transformer-based language models, which have been widely applied in generative AI. However, training Transformer models at scale, including 81 Xiao and Zhu decoder-only, encoder-only, and encoder-decoder models, may lead to new difficulties, such as training instabilities. We will discuss these issues further in the following chapters, where large-scale pre-training is the primary focus. 6.2 Text Encoding For many NLP problems, a widely used paradigm is to first represent an input sequence in some form, and then make predictions for downstream tasks based on this representation. As a result, we separate sequence modeling or sequence representation from NLP tasks. One of the advantages of this paradigm is that we can train a sequence model that is not specialized to particular tasks, thereby generalizing well. Clearly, Transformer encoders are a type of sequence model, and can be used as text encoders. Consider a Transformer encoder with L encoding blocks. The output of the last encoding block can be seen as the encoding result. Here add a special token x0 to any sequence, indicating the beginning of a sequence (written as ⟨SOS⟩ or [CLS]). If there is a sequence of m + 1 input tokens x0x1...xm, the output of the encoder will be a sequence of m+ 1 vectors h L 0 h L 1 ...h L m. Since x0 is not a real token and has a fixed positional embedding, it serves as a tag for collecting information from other positions using the self-attention mechanism. Hence h L 0 is a representation of the entire sequence, with no biases for any specific tokens or positions. In many cases, we need a single representation of a sequence and take it as input to downstream components of the system, for example, we can construct a sentence classification system based on a single vector generated from {h L 0 , ..., h L m}. In this case, we can simply use h L 0 as the representation of the sequence. A more general approach is to add a pooling layer to the encoder. This allows us to explore various pooling methods to generate the sequence embedding from {h L 0 , ..., h L m}. In text encoding, token sequences are represented by real-valued vectors, often referred to as sentence representations or sentence embeddings, which can be seen as points in a multi-dimensional space (Hill et al., 2016). Another way to make use of text encoding, therefore, is to obtain semantic or syntactic similarities of token sequences based on their relative positions or proximity in this space. A straightforward method for this is to compute the Euclidean distances between sequence embeddings. The shorter the distance between two sequences, the more similar they are considered to be. There are many distance metrics we can choose, and it is possible to combine them to obtain a better measure of sequence similarity. Such similarity computations are applied in areas such as text entailment, information retrieval, translation evaluation, among others (Cer et al., 2018; Reimers and Gurevych, 2019). Additionally, they are often used to assess the quality of text encoding models. Text encoding is also a crucial component of sequence-to-sequence models. Given this, we can develop a separate Transformer encoder for source-side sequence modeling in an encoder-decoder system (see Figure 16). For example, we can pre-train a Transformer encoder on large-scale source-side texts, and use it as the encoder in a downstream encoderdecoder model. It is worth noting that while the encoder is designed based on the Transformer architecture, the decoder is not confined to just Transformers. Such flexibility enables us to incorporate pre-trained Transformer encoders into hybrid sequence-to-sequence architectures, such as systems that combine a Transformer encoder with an LSTM decoder. 82 Introduction to Transformers Encoder ⟨CLS⟩Never give up . Pooling Classifier (e.g., Softmax) (a) Classification Encoder ⟨CLS⟩Never give up . Pooling Encoder ⟨CLS⟩Never say die ! Pooling Similarity Computation (e.g., FFN) Similarity = 0.7 (b) Similarity Computation Encoder ⟨CLS⟩Never give up . Decoder ⟨SOS⟩ 永不放弃永不放弃。 (c) Sequence-to-Sequence Modeling Figure 16: Integrating Transformer encoders as components of different systems. A common approach is to feed the output of the encoder (with pooling) into a classifier to obtain a sequence classification system. Another way to utilize Transformer encoders is to compute the similarity between two sequences. We use the same encoder to represent the two sequences, and then construct a neural network on top of the two representations for producing a similarity score between them. As usual, Transformer encoders can also be used in encoder-decoder systems to model sequence-to-sequence problems. 83 Xiao and Zhu In supervised learning scenarios, training a Transformer encoder is straightforward. We can treat it as a regular component of the target model and train this model on task-specific labeled data. However, such a method requires the encoder to be optimized on each task, and the resulting encoder might not always generalize well to other tasks, especially given that labeled data is scarce in most cases. A more prevalent approach is to frame the training of text encoders as an independent task in which supervision signals are derived solely from raw text. This led researchers to develop self-supervised Transformer encoders, such as BERT, which make use of large-scale unlabeled text, and these encoders were found to generalize well across many downstream tasks. 6.3 Speech Translation As illustrated in Section 2, the standard encoder-decoder Transformer model was proposed to model sequence-to-sequence problems. Here we consider the problem of translating speech in one language to text in another language — a problem that is conventionally addressed using both automatic speech recognition (ASR) and machine translation techniques. Instead of cascading an automatic speech recognition system and a machine translation system, we can use Transformer models to build an end-to-end speech-to-text (S2T) translation system to directly translate the input speech to the output text. To simplify the discussion, we assume that the input of an S2T translation system is a sequence of source-side acoustic feature vectors, denoted by a1...am, and the output of the system is a sequence of target-side tokens, denoted by y1...yn. 27 Mapping a1...am to y1...yn is a sequence-to-sequence problem. Thus it is straightforward to model the problem using an encoder-decoder Transformer model, and the training and inference of this model are standard, like in neural machine translation. In S2T translation, however, we have to deal with sequence mappings between modalities and between languages simultaneously. This poses new challenges compared with conventional machine translation problems and influences the design of S2T translation models. There have been several improvements to Transformer models for adapting them better to S2T translation tasks. Some of the improvements concern the design of Transformer blocks (Di Gangi et al., 2019). For example, in Gulati et al. (2020)’s system, a CNN sub-layer and relative positional embeddings are integrated into each Transformer block, enabling the model to efficiently capture both local and global features. Another line of research on S2T translation focuses on improving the encoder-decoder architecture. This involves modifications to either encoders or decoders, or both. To illustrate, Figure 17 shows the architectures of three S2T translation models. All of them are based on Transformers, but have different encoder architectures. As shown in the figure, the standard encoder-decoder architecture has one Transformer encoder for reading the source-side input a1...am and one Transformer decoder for producing the target-side output y1...yn. By contrast, the decoupled encoder model separates the encoder into two stacked encoders — one for acoustic modeling (call it the speech encoder), and one for textual 27. In order to obtain the input sequence to the system, we need to discretize continuous speech into signals represented by feature vectors. This process is typically nontrivial, requiring either a feature extractor based on a variety of signal processing operations or a neural network that learns feature mappings in an end-to-end manner. But we will not dive into the details of these methods and simply treat the input feature extractor as an upstream system. 84 Introduction to Transformers modeling (call it the text encoder) (Liu et al., 2020c; Xu et al., 2021a). This design reflects a modeling hierarchy in which representations in different levels of the network are concerned with different aspects of the problem, for example, the speech encoder models low-level features in mapping acoustic embeddings into larger language units, and the text encoder models the semantic or syntactic features in representing the entire input sequence. An advantage of separating out the text encoder is that the encoding process follows our prior knowledge that we need to first transcribe the speech input and then translate the transcript into the target language. Therefore, we can train the speech encoder in some way we train an ASR system. This enables us to pre-train the speech encoder and the text encoder on unlabeled data, and incorporate the pre-trained encoders into S2T translation systems. An alternative encoding architecture is the two-stream architecture, as shown in Figure 17 (c). Like the decoupled encoder architecture, this architecture has a speech encoder and a text encoder, but the two encoders work in parallel rather than in sequence (Ye et al., 2021). The speech encoder takes acoustic features as input and the text encoder takes tokens (or their embeddings) as input. A third encoder, called shared encoder, integrates the outputs from both the speech and text encoders, merging the representations from the two modalities. This two-stream architecture is flexible because it provides multiple ways to train S2T translation models. A common approach is to train each branch individually. For example, if we mask the speech encoder, then the model will transform into a machine translation model which can be trained using bilingual texts. Conversely, if we mask the text encoder, then we can train the model as a standard S2T translation model. For inference, the text encoder can be dropped, and the speech input is modeled using the speech encoder and the shared encoder. In deep learning, training is often related to architecture design. Here, we have data in two modalities and two languages, and so we can develop multiple supervision signals for multi-task learning of S2T translation models. A widely used method is to introduce ASRrelated loss into the training of speech encoders. For example, in the decoupled encoder model, a classifier can be constructed based on the output from the speech encoder. By minimizing the connectionist temporal classification (CTC) loss for this classifier, the speech encoder can be optimized in a manner similar to ASR. In general, training S2T translation models is challenging because speech-to-text aligned data is scarce. Among typical responses to this challenge are data augmentation, pre-training, knowledge distillation with machine translation, and so on. However, an in-depth discussion of these methods goes beyond the scope of this discussion on Transformers. The interested reader can refer to a recent survey on speech translation for more information (Xu et al., 2023a). 6.4 Vision Models While Transformers were first used in NLP, their application to other domains has been a prominent research topic. In computer vision, for instance, there is a notable trend of shifting from CNNs to Transformers as the backbone models. In this sub-section, we consider Vision Transformer (ViT) - an interesting application of Transformers to image classification (Dosovitskiy et al., 2021). Vision Transformer is a milestone model which opens the door to purely Transformer-based vision models. Here we consider the basic 85 Xiao and Zhu Encoder (Speech) Speech (Source) Decoder Text (Target) (a) Single Encoder + Single Decoder Encoder (Speech) Speech (Source) Encoder (Text) Transcript (Source) Decoder Text (Target) (b) Decoupled Encoder + Single Decoder Encoder (Speech) Speech (Source) Encoder (Text) Transcript (Source) Shared Encoder Decoder Text (Target) (c) Two-stream Encoder + Single Decoder Figure 17: Architectures of speech-to-text translation models based on Transformers. In addition to the standard encoder-decoder architecture, we can explicitly model the acoustic and textual (semantic) information using two separate encoders, called the speech encoder and the text encoder. In the decoupled encoder architecture, the two encoders are stacked, that is, text encoding is a subsequent process after speech encoding. In the two-stream encoder architecture, the two encoders work in parallel, and their outputs are merged using an additional encoder, called the shared encoder. The dotted line indicates the potential for interaction between the two encoders. For example, we could define a loss function to minimize the difference between their outputs, thereby guiding the model towards more aligned representations. 86 Introduction to Transformers Image Flattened Image Patches Patch Embedding + Positional Embedding C C = Extra Learnable [CLS] embedding Transformer Encoder Is it a building? Classifier Figure 18: Illustration of Vision Transformer for image classification(Dosovitskiy et al., 2021). There are three steps. In the first step, the input image is segmented into patches, which are then flattened and mapped into embeddings. In the second step, a Transformer encoder is employed to process the sequence of embeddings, representing the image as a real-valued vector (e.g., the output of the encoder at the first position). In the last step, a classifier is built on top of this image representation. structure of Vision transformer to make this section concentrated and coherent, although there has been an extensive literature on Vision transformer and its variants. More detailed discussions of vision transformer can be found in recent surveys (Han et al., 2022; Liu et al., 2023b). The core idea behind Vision Transformer is to transform an image into a sequence of visual tokens, and input this sequence into a Transformer encoder to generate a representation of the image. The Transformer encoder is standard, and so we will not discuss it here, given the introduction to Transformers we have presented so far in this chapter. Mapping a 2D image into a sequence of tokens needs some additional work. Suppose we have an image represented as an H × W × C feature map, where H is the height of the image, W is the width of the image, and C is the number of channels. The first step is to segment this image into a number of patches. Suppose all patches are squares of side length P. Then the resulting patches can be represented by feature maps of shape P × P × C. By ordering these patches in some way, we obtain a sequence of HW P2 patches, with each patch being treated as a “token”. Given this patch sequence, the subsequent steps are straightforward. For the patch at each position, we obtain a d-dimensional embedding by a linear transformation of the input feature map. The input of the Transformer encoder is a sequence of d-dimensional vectors, each of which is the sum of the corresponding patch and positional embeddings. Figure 18 illustrates the patching and embedding steps in Vision Transformer. 87 Xiao and Zhu Once we have a sequence of vectors for representing the image, we can employ the Transformer encoder to encode the sequence. The encoding process is exactly the same as that in text encoding as discussed in Section 6.2. For classification problems, we need only a single representation of the input. It is convenient to take the output of the encoder at position 0 (denoted by h L 0 ) and feed it into a classifier. Given that the first token [CLS] serves as a special token that would be attended to by all other tokens, h L 0 provides an unbiased representation of the entire sequence. Typically, a standard way to train Vision Transformer is to minimize some loss on labeled data, such as ImageNet. More recently, inspired by self-supervised learning in BERT-like models, there have been successful attempts to train Transformer-based image encoders on large-scale unlabeled data (Bao et al., 2021; Caron et al., 2021; He et al., 2022). Note that one of the most significant contributions of Vision Transformer is that it unifies the representation models for different modalities. This suggests that if an object, whether an image or text, is represented as a sequence of embeddings, it can be easily modeled using the Transformer architecture. 6.5 Multimodal Models The above discussion of Vision Transformer offers the possibility of unifying the representations from multiple modalities using the same Transformer architecture. In fact, many recent multimodal systems draw inspiration largely from Transformers (Xu et al., 2023c). Such systems convert objects from different modalities into vector sequences and feed these vectors into a single Transformer model. The output is a fused representation of all inputs, which can then be used in downstream systems. As a simple example, consider the task of encoding a pair consisting of text and its corresponding image. First, we represent both the text and the image as sequences of embeddings that have the same dimensionality. This is a common step in sequence modeling, which we have confronted many times so far. We can do this by using either a simple embedding model (e.g., a word or patch embedding model) or a well-trained sequence model (e.g., a vision model). Then, these two sequences are concatenated into a long sequence involving both textual and visual embeddings. The follow-on step is standard: a Transformer encoder takes the concatenated sequence of embeddings as input and produces representations of the text and image as output. Note that concatenating textual and visual sequences is one of the simplest methods for vision-text modeling. There are several alternative ways to merge information from different modalities, for example, we can feed visual representations into the attention layers of a text encoder or decoder (Alayrac et al., 2022; Li et al., 2022d). The above multimodal encoder can be used in both encoder-only and encoder-decoder systems. For encoder-only systems, consider an example where, given an image and a description of it, we predict the class of the image using a classifier built on top of the encoder (Kim et al., 2021). For encoder-decoder systems, we pair the encoder with a decoder, as in sequence-to-sequence modeling (Cho et al., 2021). For example, we might employ a Transformer decoder to generate text based on the output of the encoder. A common application of this architecture is visual question answering (VQA), where an image and a question about the image are provided, and the system is tasked with 88 Introduction to Transformers generating an answer (Antol et al., 2015). The architectures of these models are illustrated in Figure 19 (a-b). More recently, NLP has seen new advances by using large language models to deal with both textual and other forms of data, such as images, videos, and audio, leading to new breakthroughs in multimodal processing (Liu et al., 2023a; Yin et al., 2023). By representing all inputs as a sequence of token embeddings, the problem will be simple: we predict the next token given its context. This can be done by using decoder-only systems, as shown in Figure 19 (c). 7. Summary Transformer models have achieved widespread use over the past few years since the concept of Transformer was proposed by Vaswani et al. (2017). This has accelerated the development of these models, leading to a great variety of new algorithms, systems and concepts. A thorough discussion of Transformers requires a broad scope, and so it is impossible to cover every problem and to provide a complete list of the corresponding references. While this chapter has presented a detailed introduction to Transformers, there are still topics that we did not mention, such as the theoretical aspects of these models. Figure 20 shows an overview of Transformer models, where we attempt to give a big picture. Note that these models and related techniques can be classified in many different ways, and we just show one of them. To summarize, we would like to highlight the following points. • Foundations of Transformers. Although the impact of Transformers has been revolutionary, they are not completely ”new” models. From a deep learning perspective, Transformers are composed of common building blocks, including word and positional embeddings (Bengio et al., 2003; Gehring et al., 2017; Mikolov et al., 2013), attention mechanisms (Bahdanau et al., 2014; Luong et al., 2015), residual connections (He et al., 2016b), layer-normalization (Ba et al., 2016), and so on. Many of these components were presented in earlier systems, for example, similar ideas with QKV attention can be found in memory networks (Sukhbaatar et al., 2015) and hierarchical attention networks (Yang et al., 2016). Transformers offer a novel approach to integrating these components, resulting in a unique architecture. For example, in Transformers, the combination of multi-head attention and dot-product QKV attention, along with the incorporation of layer-normalization and residual connections, gives rise to a distinctive neural network block, specifically a self-attention sub-layer. This design has since become a de facto standard in many follow-on sequence modeling systems. • Attention Models. The success of Transformers on NLP tasks has largely been attributed to the use of multi-head self-attention for sequence modeling. This has led to a surge of interest in enhancing the attention mechanisms within Transformers. While it is impossible to detail every attention model, there are several notable research directions. One prominent direction involves modifying the forms of QKV attention and multi-head attention for improved performance. The scope of this direction is vast, as there are numerous aspects to consider when enhancing Transformers (Lin et al., 2022a). For example, one may add new components to self-attention sub-layers to adapt them to specific tasks, resulting in various Transformer variants. A second 89 Xiao and Zhu ⟨CLS⟩ A cube with green color. Word and Positional Embeddings C Patch and Positional Embeddings Transformer Encoder Classifier Is it an animal? (a) Multi-modal Encoder + Classifier ⟨CLS⟩ A cube with green color. Word and Positional Embeddings C Patch and Positional Embeddings Transformer Encoder Decoder ⟨SOS⟩ 一个绿色的立方体一个绿色的立方体。 (b) Multi-modal Encoder + Text Decoder (Translation) ⟨CLS⟩ What’s the color of the cube? Word and Positional Embeddings C Patch and Positional Embeddings Transformer Decoder ⟨SOS⟩ The color is green The color is green . (c) Multi-modal Decoder (Language Modeling) Figure 19: Vision-text models. Blue boxes represent word+position embeddings, and red boxes represent image patch+position embeddings. 90 Introduction to Transformers Attention Scalability Efficiency Syntaxaware Attention Deep Models Wide Models • Mixture of Exports Sparse Attention • Span-based / Local Attention • Chunked Attention • Strided Attention • Learning Attention Fields Recurrent and Memory Models • Cache-based Memory • Encoding Long-term Memory • Retrieval-based Methods Alternatives • Convolutional Attention • Linear Attention Data Efficiency Absolute Positional Encoding Regularization • Layer Skipping / Stochastic Layers Rotational Positional Encoding Theoretical Analysis • Linguistics • Machine Learning • Formal Systems Foundations of Transformers Transformer Sub-models • Word Encoding and Positional Encoding • Multi-head Self-attention • Feed-forward Networks • Layer Normalization and Residual Connections Architectures • Encoder Only • Decoder Only • Encoder-Decoder Sequence Compression • Token Pruning • Progressive Downsampling Model Compression • Knowledge Distillation • Structured Pruning Search Algorithms Quantization Early Stop Length Extrapolation Parameter and Activation Sharing • Layer Fusion • Multi-scale Models • Multi-branch Models • Numerical Method-inspired Models Architecture Improvement Training Inference Positional Encoding IO-aware Attention Caching Foundations of Transformers Efficiency Attention Inference Training Architecture Improvement Positional Embedding Scalability Applications Applications Self-supervised Transformers in NLP Supervised Transformers in NLP Natural Language Generation: GPT Series, T5, BART, MASS, PaLM, LaMDA, Megatron-Turing NLG, BLOOM, LLaMA, etc. Natural Language Understanding: BERT, RoBERTa, ALBERT, SpanBERT, ERNIE, XLM, XLNet, etc. Neural Machine Translation, Summarization, Sentiment Analysis, Question Answering, Named Entity Recognition, Syntactic Analysis, etc. Vision Speech Multi-modal Time Series Analysis Bioinformatics Recommendation Systems Robotics ViT, Swin, MAE, BEiT, DETR, iGPT, etc. Wav2vec 2.0, Whisper, CLIP, ViLBERT, VisualBERT, VLBERT, UNITER, LXMERT, ViLT, VLT5, Data2vec, etc. HuBERT, Conformer, etc. Figure 20: An overview of Transformers. 91 Xiao and Zhu direction is to incorporate prior knowledge into the design of attention models. This makes sense, because much of the emphasis in traditional NLP has been on using linguistic insights to guide system design, and we generally want NLP systems to be linguistically explainable. For example, many Transformer-based systems take syntactic parses as input in various forms and make use of syntax in sequence modeling. A third direction is to develop efficient attention models (Tay et al., 2020b). Selfattention has long been criticized for its quadratic time complexity and dependency on all previous tokens for each new token. In response, many researchers have focused on simplifying the structure of self-attention, or on approximating it using sparse or recurrent models. This concern for efficiency also motivates the development of alternatives to self-attention, such as attention models with linear time complexity. In addition to exploring stronger and more efficient attention models, it is natural to examine what knowledge is learned by such models. Interestingly, researchers have found that the underlying structure of languages can be learned by multi-head selfattention models, although these models are not trained to represent such knowledge (Manning et al., 2020). • Word and Positional Embeddings. Transformers represent each input word as a word embedding, along with its positional embedding. Learning these word embeddings is not a specific problem for Transformers. We can either resort to well-trained word embeddings, such as the Word2Vec or GloVe embeddings, or treat them as learnable parameters of Transformers. A related issue is tokenization of the input sequences. In general, tokenization impacts the number of resulting tokens and the difficulty of learning the corresponding embeddings. In many applications, therefore, one needs to carefully choose a tokenization method. Furthermore, positional embedding plays an important role in Transformers, as the attention mechanisms are order-insensitive by design (Dufter et al., 2022). Although positional embedding is a general problem, much of the research is focused on improving Transformers, leading to modifications to Transformer models (Huang et al., 2018; Shaw et al., 2018). Additionally, studies show that, when we deal with sequences that are much longer than those in training data, extrapolation can be achieved by replacing sinusoidal positional embeddings with rotary positional embeddings or simply scaling attention weights with a positional scalar (Press et al., 2021; Raffel et al., 2020; Su et al., 2021). • Training and Model Scaling. In the era of deep learning, powerful systems are typically obtained by using large neural networks. A simple approach to increasing the model capacity of Transformers is to stack more layers and/or enlarge the size of each representation. We can see many cases where deep and wide Transformer models consistently outperform small models. However, challenges arise when we attempt to train extremely large Transformer models, especially when gradient descent is applied over vast amounts of data, demanding substantial computational resources. An engineering solution is to distribute the training across a cluster of computers (Chowdhery et al., 2022; Lepikhin et al., 2021). While distributed training is a very general method and is not restricted to Transformers, it indeed influences the design of model architectures, for example, sparse expert models can ease the training with distributed parameters, serving as the foundation for many expansive Transformer92 Introduction to Transformers based systems. Scaling up the training of Transformers allows us to study the scaling law of large neural networks: how model performance relates to model size, training data size, and training cost (Hestness et al., 2017; Kaplan et al., 2020). This is sometimes accompanied by an interesting behavior, known as emergence (Wei et al., 2022). In recent NLP research, the acquisition of emergent abilities has been considered one of the prerequisites for developing strong language models. • Efficient Models. There are different goals for efficiency. For example, one may wish a system to be memory efficient when the problem is memory bound, or one may wish it to be speed efficient when latency is an important consideration. In general, we need to seek a balance between these goals, resulting in different efficiency optimizations. In the context of Transformers, many of these optimizations are achieved by modifying the attention models, as mentioned above. For example, several variants of the self-attention models are proposed to reduce the memory footprint when processing long sequences (Tay et al., 2020b). Similarly, other variants aim to reduce computation and thus give lower latency. Furthermore, being a type of neural network, Transformers can be optimized in ways independent of model architectures. Typical methods include but are not limited to conditional computation, knowledge distillation, structured pruning, and sequence compression. Efficiency optimizations can also be considered from the perspective of computer architecture (Kim et al., 2023). For example, when applying Transformers to sequence-to-sequence problems, the encoding and decoding processes are generally compute-intensive and IO-intensive, respectively. Therefore, we can employ different optimization methods for different components of Transformers. • Inference. The inference problem is commonly discussed in sequence generation. In NLP, we often need to find the “best” hypothesis in a space involving sequences of tens or even hundreds of tokens over a vocabulary. Considering this an instance of the search problem in artificial intelligence, many algorithms can be applied, such as breadth-first search, depth-first search and A* search. In many practical applications of NLP, the efficiency of the search systems is an important consideration. As a result, optimized search algorithms are required. Most of these algorithms have been explored in machine translation and ASR, and are directly applicable to neural text generation models like Transformer. There are also optimizations of conventional decoding methods tailored to Transformers (Leviathan et al., 2023). Moreover, the above-mentioned efficient approaches, such as the efficient attention models, are also in widespread use, with many successful examples in deploying neural machine translation systems and large language models (Dao et al., 2023; Heafield et al., 2021). • Applications. Applications of Transformers cover a wide variety of NLP problems. During the development of Transformers, they were at first used to build supervised models that perform particular tasks. Later, a greater success was achieved by using them as backbone networks for large scale self-supervised learning of foundation models (Bommasani et al., 2021). This markedly changed the paradigm in NLP. We need only pre-train a model to obtain general knowledge of languages on huge amounts of text. Then, we adapt this model to downstream tasks using methods with little effort, such as fine-tuning or prompting. Over the past few years, we have also seen an 93 Xiao and Zhu explosion of applications for Transformers in fields other than NLP, such as computer vision, speech processing, and bioinformatics. The idea behind these applications is that we can represent any input data as a sequence of tokens and directly employ Transformers to model this sequence. This approach extends Transformers to general representation models across different modalities, making it easier to use Transformers for handling multi-modal data. • Large Language Models as Foundation Models. Transformers form the basis of recent large language models, such as the GPT series, which show surprising breakthroughs in NLP, and even in artificial general intelligence (AGI) (Bubeck et al., 2023; Yang et al., 2023a). Much of the research in large language models is more or less related to Transformers. For example, as discussed in Section 6.1, the problem of training these language models is the same as that of training Transformer decoders. And the modifications to Transformer decoders can be directly applied to large language models. On the other hand, the rapid development of large language models has also driven further improvements in various techniques for Transformers, such as efficient and low-cost adaptation of large Transformers to different tasks. • Theoretical Analysis. Although Transformers have shown strong empirical results in various fields, their theoretical aspects have received relatively less attention compared to the extensive research on model improvement and engineering. This is not a specific problem for Transformers, but a common problem for the NLP and machine learning communities. In response, researchers have made attempts to analyze Transformers more deeply. One way is to view Transformers as deep neural networks and interpret them via mathematical tools. For example, the residual networks in Transformers are mathematically equivalent to the Euler solvers for ODEs. This equivalence suggests that we can leverage insights from numerical ODE methods to inform model design. Another promising avenue of research aims to develop a theoretical understanding of the self-attention mechanism, which distinguishes Transformers from other deep learning models. For example, there have been studies on interpreting self-attention and Transformers from machine learning perspectives, such as data compression (Yu et al., 2023), optimization (Li et al., 2022c), and function approximation (Yun et al., 2019). Moreover, Transformers can also be related to formal systems, including Turing machines (P´erez et al., 2018), counter machines (Bhattamishra et al., 2020), regular and context-free languages (Hahn, 2020), Boolean circuits (Hao et al., 2022; Merrill et al., 2022), programming languages (Weiss et al., 2021), first-order logic (Chiang et al., 2023), and so on. These provide tools to study the expressivity of Transformers. It is, however, worth noting that, while we can understand Transformers in several different ways, there are no general theories to explain the nature of these models. Perhaps this is a challenge for the field of machine learning, and many researchers are working on this issue. But it is indeed an important issue, as the development of the theories behind complex neural networks like Transformers can help develop systems with explainable and predictable behaviors. 94 Introduction to Transformers Acknowledgements We would like to thank Yongyu Mu, Chenglong Wang, Bei Li, Weiqiao Shan, Yuchun Fan, Kaiyan Chang, Tong Zheng, and Huiwen Bao for their suggestions on improving the early version of this work. 95 Xiao and Zhu A. Sinusoidal Positional Encoding In Transformers, positions are represented as vectors. Although vectorizing the representations of positions sounds complicated, a simple idea is to use a carrying system which describes how a natural number is expressed by a polynomial with respect to a base (Kernes, 2021). For example, i can be written as i = k Xmax k=0 a(i, k)b k (202) where a(i, k) is the k-th digit, kmax + 1 is the maximum number of digits, and b is the base of the system. The carrying occurs when a(i, k) reaches b: we increase a(i, k + 1) by 1 and roll back a(i, k) to 0. In this way we can change a(i, k) with a period of b k , that is, a(i, 0) changes with a period of b 0 , a(i, 1) changes with a period of b 1 , a(i, 2) changes with a period of b 2 , and so on. Using this system, i can be represented as a vector PE(i) = a(i, 0) a(i, 1) ... a(i, kmax) (203) For example, when b = 2, PE(11) = 1 1 0 1 . However, in Eq. (203), PE(i) is still a discrete function. We may want a continuous vector representation that can describe intermediate states between discrete events. Considering a(i, k) as a periodic function, a common choice is the sine function. Thus a(i, k) can be re-defined, as follows a(i, k) = sin(i · ωk) (204) This function has an amplitude of 1 and a period of 2π ωk . Using an analogous form of periods to that used in Eq. (202), we define ωk as ωk = 1 (bmodel) k/dmodel (205) where bmodel > 0 and dmodel > 0 are hyper-parameters of the model. Obviously, we have 2π ω0 < 2π ω1 < ... < 2π ωkmax . Similarly, we can define a(i, k) via the cosine function a(i, k) = cos(i · ωk) (206) Taking both Eqs. (204) and (206), we create a new representation of i, as follows PE(i) = sin(i · ω0) cos(i · ω0) ... sin(i · ωkmax ) cos(i · ωkmax ) (207) Vaswani et al. (2017) instantiated the above form by setting bmodel = 10, 000. Let PE(i, k) be the k-th dimension of PE(i). Vaswani et al. (2017)’s version of positional encoding is written as PE(i, 2k) = sin(i · 1 100002k/dmodel ) (208) PE(i, 2k + 1) = cos(i · 1 100002k/dmodel ) (209) 96 Introduction to Transformers Figure 21: A heat map of the positional embedding model of Eqs. (208) and (209) (bmodel = 10, 000 and dmodel = 512). Consider a position i (i.e., the i-th row), then move another position j from i upwards or downwards. Intuitively, when i and j are closer, the corresponding row vectors are more similar. By contrast, when j moves away from i, the similarity is not that obvious. This property helps explain the idea behind the positional embedding model: the “distance” between two positions is implicitly modeled by comparing their multi-dimensional representations. Choosing bmodel = 10, 000 is empirical. One can adjust it for specific tasks. Figure 21 plots the positional encoding for different positions. We see that, when k becomes larger, the change of the color follows a larger period. Note that Eqs. (208) and (209) have a useful property that PE(i + µ) can be easily expressed by a linear function of PE(i) for a given offset µ 28 PE(i + µ, 2k) = PE(i, 2k) · PE(µ, 2k + 1) + PE(i, 2k + 1) · PE(µ, 2k) (212) PE(i + µ, 2k + 1) = PE(i, 2k + 1) · PE(µ, 2k + 1) + PE(i, 2k) · PE(µ, 2k) (213) The resulting benefit is that the encoding can somewhat model relative positions. That is, the state at position i + µ can be described by starting with i and then appending it with the offset µ. 28. One can derive these by taking sin(α + β) = sin(α) · cos(β) + cos(α) · sin(β) (210) cos(α + β) = cos(α) · cos(β) − sin(α) · sin(β) (211) 97 Xiao and Zhu When applying the sinusoidal positional encoding, one way is to concatenate xi and PE(i). In Vaswani et al. (2017)’s work, they instead assume PE(i) to be a vector of the same size as xi (i.e., |PE(i)| = |xi| = de), and add PE(i) to xi, like this xpi = xi + PE(i) (214) This sinusoidal addictive model has been the basis of many positional encoding approaches (Dehghani et al., 2018; Likhomanenko et al., 2021; Su et al., 2021). 98 Introduction to Transformers References Yossi Adi, Einat Kermany, Yonatan Belinkov, Ofer Lavi, and Yoav Goldberg. Fine-grained analysis of sentence embeddings using auxiliary prediction tasks. In Proceedings of International Conference on Learning Representations, 2016. Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. Etc: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 268–284, 2020. Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning. Advances in Neural Information Processing Systems, 35:23716–23736, 2022. Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. Vqa: Visual question answering. In Proceedings of the IEEE international conference on computer vision, pages 2425–2433, 2015. Karl J ˚Astr¨om and Bj¨orn Wittenmark. Computer-controlled systems: theory and design. Courier Corporation, 2013. Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016. Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley. Rezero is all you need: Fast convergence at large depth. In Proceedings of Uncertainty in Artificial Intelligence, pages 1352–1361. PMLR, 2021. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473, 2014. Jiangang Bai, Yujing Wang, Yiren Chen, Yaming Yang, Jing Bai, Jing Yu, and Yunhai Tong. Syntax-bert: Improving pre-trained transformers with syntax trees. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 3011–3020, 2021. Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei. Beit: Bert pre-training of image transformers. In Proceedings of International Conference on Learning Representations, 2021. Paul Barham, Aakanksha Chowdhery, Jeff Dean, Sanjay Ghemawat, Steven Hand, Daniel Hurt, Michael Isard, Hyeontaek Lim, Ruoming Pang, Sudip Roy, et al. Pathways: Asynchronous distributed dataflow for ml. In Proceedings of Machine Learning and Systems, volume 4, pages 430–449, 2022. Yonatan Belinkov. Probing classifiers: Promises, shortcomings, and advances. Computational Linguistics, 48(1):207–219, 2022. 99 Xiao and Zhu Irwan Bello. Lambdanetworks: Modeling long-range interactions without attention. In Proceedings of International Conference on Learning Representations, 2020. Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv:2004.05150, 2020. Emmanuel Bengio, Pierre-Luc Bacon, Joelle Pineau, and Doina Precup. Conditional computation in neural networks for faster models. arXiv preprint arXiv:1511.06297, 2015. Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. A neural probabilistic language model. Journal of Machine Learning Research, 3:11371155, 2003. Yoshua Bengio, Nicholas L´eonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432, 2013. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096–7116, 2020. Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, S. Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen A. Creel, Jared Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren E. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas F. Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, O. Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir P. Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Benjamin Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, J. F. Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Robert Reich, Hongyu Ren, Frieda Rong, Yusuf H. Roohani, Camilo Ruiz, Jack Ryan, Christopher R’e, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishna Parasuram Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tram`er, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei A. Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang. On the opportunities and risks of foundation models. ArXiv, 2021. Yelysei Bondarenko, Markus Nagel, and Tijmen Blankevoort. Understanding and overcoming the challenges of efficient transformer quantization. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7947–7969, 2021. 100 Introduction to Transformers Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020. S´ebastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712, 2023. Maxime Burchi and Valentin Vielzeuf. Efficient conformer: Progressive downsampling and grouped attention for automatic speech recognition. In Proceedings of 2021 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), pages 8–15. IEEE, 2021. Mathilde Caron, Hugo Touvron, Ishan Misra, Herv´e J´egou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pages 9650–9660, 2021. Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, et al. Universal sentence encoder. arXiv preprint arXiv:1803.11175, 2018. Kehai Chen, Rui Wang, Masao Utiyama, Eiichiro Sumita, and Tiejun Zhao. Syntax-directed attention for neural machine translation. In Proceedings of the AAAI conference on artificial intelligence, 2018a. Mia Xu Chen, Orhan Firat, Ankur Bapna, Melvin Johnson, Wolfgang Macherey, George Foster, Llion Jones, Mike Schuster, Noam Shazeer, Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. The best of both worlds: Combining recent advances in neural machine translation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 76–86, 2018b. Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018c. Tianqi Chen, Ian Goodfellow, and Jonathon Shlens. Net2net: Accelerating learning via knowledge transfer. arXiv preprint arXiv:1511.05641, 2015. David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. arXiv preprint arXiv:2301.10743, 2023. Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019. 101 Xiao and Zhu Jaemin Cho, Jie Lei, Hao Tan, and Mohit Bansal. Unifying vision-and-language tasks via text generation. In International Conference on Machine Learning, pages 1931–1942. PMLR, 2021. Do Kook Choe and Eugene Charniak. Parsing as language modeling. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2331–2336, 2016. Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. In Proceedings of International Conference on Learning Representations, 2020. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022. Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does bert look at? an analysis of bert’s attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 276–286, 2019. Alexis Conneau, Germ´an Kruszewski, Guillaume Lample, Lo¨ıc Barrault, and Marco Baroni. What you can cram into a single vector: Probing sentence embeddings for linguistic properties. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2126–2136, 2018. Anna Currey and Kenneth Heafield. Multi-source syntactic neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2961–2966, 2018. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978–2988, 2019. Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher R´e. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344–16359, 2022. Tri Dao, Daniel Haziza, Francisco Massa, and Grigory Sizov. Flash-decoding for longcontext inference. https://pytorch.org/blog/flash-decoding/, 2023. Retrieved 2023-10-23. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. Luciano Del Corro, Allie Del Giorno, Sahaj Agarwal, Bin Yu, Ahmed Awadallah, and Subhabrata Mukherjee. Skipdecode: Autoregressive skip decoding with batching and caching for efficient llm inference. arXiv preprint arXiv:2307.02628, 2023. 102 Introduction to Transformers Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, 2019. Mattia Antonino Di Gangi, Matteo Negri, Roldano Cattoni, Roberto Dessi, and Marco Turchi. Enhancing transformer for end-to-end speech-to-text translation. In Proceedings of Machine Translation Summit XVII: Research Track, pages 21–31, 2019. Ming Ding, Zhuoyi Yang, Wenyi Hong, Wendi Zheng, Chang Zhou, Da Yin, Junyang Lin, Xu Zou, Zhou Shao, Hongxia Yang, et al. Cogview: Mastering text-to-image generation via transformers. Advances in Neural Information Processing Systems, 34:19822–19835, 2021. Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In Proceedings of ICLR 2021, 2021. Philipp Dufter, Martin Schmitt, and Hinrich Sch¨utze. Position information in transformers: An overview. Computational Linguistics, 48(3):733–763, 2022. Weinan Ee. A proposal on machine learning via dynamical systems. Communications in Mathematics and Statistics, 5:1–11, 02 2017. Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. Depth-adaptive transformer. In Proceedings of International Conference on Learning Representations, 2020. Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1):1997–2017, 2019. Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li, Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer. Multiscale vision transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6824–6835, 2021. Yang Fan, Shufang Xie, Yingce Xia, Lijun Wu, Tao Qin, Xiang-Yang Li, and Tie-Yan Liu. Multi-branch attentive transformer. arXiv preprint arXiv:2006.10270, 2020. William Fedus, Jeff Dean, and Barret Zoph. A review of sparse expert models in deep learning. arXiv preprint arXiv:2209.01667, 2022a. William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. The Journal of Machine Learning Research, 23(1):5232–5270, 2022b. Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry hungry hippos: Towards language modeling with state space models. In Proceedings of The Eleventh International Conference on Learning Representations, 2022. 103 Xiao and Zhu Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International conference on machine learning, pages 1243–1252. PMLR, 2017. Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. A survey of quantization methods for efficient neural network inference. In Low-Power Computer Vision, pages 291–326. Chapman and Hall/CRC, 2022. Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249–256. JMLR Workshop and Conference Proceedings, 2010. Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible residual network: Backpropagation without storing activations. Advances in neural information processing systems, 30, 2017. Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129:1789–1819, 2021. Robert M. Gray. Quantization. IEEE transactions on information theory, 44(6):2325–2383, 1998. Albert Gu, Karan Goel, and Christopher R´e. Efficiently modeling long sequences with structured state spaces. In Proceedings of International Conference on Learning Representations, 2021. Albert Gu, Karan Goel, Ankit Gupta, and Christopher R´e. On the parameterization and initialization of diagonal state space models. Advances in Neural Information Processing Systems, 35:35971–35983, 2022a. Albert Gu, Karan Goel, Khaled Saab, and Chris R´e. Structured state spaces: Combining continuous-time, recurrent, and convolutional models. https://hazyresearch. stanford.edu/blog/2022-01-14-s4-3, 2022b. Retrieved 2022-01-14. Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang. Conformer: Convolution-augmented transformer for speech recognition. Proceedings of Interspeech 2020, pages 5036–5040, 2020. Qipeng Guo, Xipeng Qiu, Pengfei Liu, Xiangyang Xue, and Zheng Zhang. Multi-scale self-attention for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7847–7854, 2020. Madan Gupta, Liang Jin, and Noriyasu Homma. Static and dynamic neural networks: from fundamentals to advanced theory. John Wiley & Sons, 2004. Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training. In Proceedings of International conference on machine learning, pages 3929–3938. PMLR, 2020. 104 Introduction to Transformers Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse problems, 34(1):014004, 2017. Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171, 2020. Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on vision transformer. IEEE transactions on pattern analysis and machine intelligence, 45(1):87–110, 2022. Wei Han, Zhengdong Zhang, Yu Zhang, Jiahui Yu, Chung-Cheng Chiu, James Qin, Anmol Gulati, Ruoming Pang, and Yonghui Wu. Contextnet: Improving convolutional neural networks for automatic speech recognition with global context. In Proceedings of Interspeech 2020, pages 3610–3614, 2020. Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, and Yulin Wang. Dynamic neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7436–7456, 2021. Jie Hao, Xing Wang, Shuming Shi, Jinfeng Zhang, and Zhaopeng Tu. Multi-granularity self-attention for neural machine translation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 887–897, 2019. Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800–810, 2022. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016a. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Proceedings of ECCV 2016, pages 630–645, 2016b. Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Doll´ar, and Ross Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16000–16009, 2022. Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decodingenhanced bert with disentangled attention. In Proceedings of International Conference on Learning Representations, 2021. Kenneth Heafield, Qianqian Zhu, and Roman Grundkiewicz. Findings of the WMT 2021 shared task on efficient translation. In Proceedings of the Sixth Conference on Machine Translation, pages 639–651, 2021. Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv:1712.00409, 2017. 105 Xiao and Zhu John Hewitt and Percy Liang. Designing and interpreting probes with control tasks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLPIJCNLP), pages 2733–2743, 2019. Felix Hill, Kyunghyun Cho, and Anna Korhonen. Learning distributed representations of sentences from unlabelled data. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1367–1377, 2016. Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2015. Lu Hou, Zhiqi Huang, Lifeng Shang, Xin Jiang, Xiao Chen, and Qun Liu. Dynabert: Dynamic bert with adaptive width and depth. Advances in Neural Information Processing Systems, 33:9782–9793, 2020. Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1314–1324, 2019. Chi Hu, Chenglong Wang, Xiangnan Ma, Xia Meng, Yinqiao Li, Tong Xiao, Jingbo Zhu, and Changliang Li. Ranknas: Efficient neural architecture search by pairwise ranking. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 2469–2480, 2021. Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Ian Simon, Curtis Hawthorne, Noam Shazeer, Andrew M Dai, Matthew D Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer: Generating music with long-term structure. In Proceedings of International Conference on Learning Representations, 2018. Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. In Proceedings of the 14th European Conference, pages 646–661. Springer, 2016. Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017. Zhiheng Huang, Davis Liang, Peng Xu, and Bing Xiang. Improve transformer models with better relative position embeddings. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3327–3335, 2020. Andrei Ivanov, Nikoli Dryden, Tal Ben-Nun, Shigang Li, and Torsten Hoefler. Data movement is all you need: A case study on optimizing transformers. In Proceedings of Machine Learning and Systems, volume 3, pages 711–732, 2021. 106 Introduction to Transformers Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2704–2713, 2018. Andrew Jaegle, Sebastian Borgeaud, Jean-Baptiste Alayrac, Carl Doersch, Catalin Ionescu, David Ding, Skanda Koppula, Daniel Zoran, Andrew Brock, Evan Shelhamer, et al. Perceiver io: A general architecture for structured inputs & outputs. In Proceedings of International Conference on Learning Representations, 2021. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and Fran¸cois Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5156–5165. PMLR, 2020. Jonathan Kernes. Master positional encoding: Part i, 05 2021. URL https:// towardsdatascience.com/master-positional-encoding-part-i-63c05d90a0c3. Patrick Kidger. On neural differential equations. arXiv preprint arXiv:2202.02435, 2022. Gyuwan Kim and Kyunghyun Cho. Length-adaptive transformer: Train once with length drop, use anytime with search. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 6501–6511, 2021. Najoung Kim, Roma Patel, Adam Poliak, Patrick Xia, Alex Wang, Tom McCoy, Ian Tenney, Alexis Ross, Tal Linzen, Benjamin Van Durme, et al. Probing what different nlp tasks teach machines about function word comprehension. In Proceedings of the Eighth Joint Conference on Lexical and Computational Semantics (* SEM 2019), pages 235–249, 2019. Sehoon Kim, Coleman Hooper, Thanakul Wattanawong, Minwoo Kang, Ruohan Yan, Hasan Genc, Grace Dinh, Qijing Huang, Kurt Keutzer, Michael W Mahoney, et al. Full stack optimization of transformer inference: a survey. arXiv preprint arXiv:2302.14017, 2023. Wonjae Kim, Bokyung Son, and Ildoo Kim. Vilt: Vision-and-language transformer without convolution or region supervision. In Proceedings of International Conference on Machine Learning, pages 5583–5594. PMLR, 2021. Yoon Kim and Alexander M Rush. Sequence-level knowledge distillation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1317–1327, 2016. Young Jin Kim and Hany Hassan Awadalla. Fastformers: Highly efficient transformer models for natural language understanding. In Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing, pages 149–158, 2020. 107 Xiao and Zhu Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In Proceedings of International Conference on Learning Representations, 2020. Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 66–75, 2018. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. arXiv preprint arXiv:2309.06180, 2023. Fran¸cois Lagunas, Ella Charlaix, Victor Sanh, and Alexander M Rush. Block pruning for faster transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10619–10629, 2021. Guillaume Lample, Alexandre Sablayrolles, Marc’Aurelio Ranzato, Ludovic Denoyer, and Herv´e J´egou. Large memory layers with product keys. Advances in Neural Information Processing Systems, 32, 2019. Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. Gshard: Scaling giant models with conditional computation and automatic sharding. In Proceedings of International Conference on Learning Representations, 2021. Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In Proceedings of International Conference on Machine Learning, pages 19274–19286. PMLR, 2023. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K¨uttler, Mike Lewis, Wen-tau Yih, Tim Rockt¨aschel, et al. Retrievalaugmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems, 33:9459–9474, 2020. Bei Li, Hui Liu, Ziyang Wang, Yufan Jiang, Tong Xiao, Jingbo Zhu, Tongran Liu, and Changliang Li. Does multi-encoder help? a case study on context-aware neural machine translation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3512–3518, 2020a. Bei Li, Ziyang Wang, Hui Liu, Yufan Jiang, Quan Du, Tong Xiao, Huizhen Wang, and Jingbo Zhu. Shallow-to-deep training for neural machine translation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 995–1005, 2020b. Bei Li, Ziyang Wang, Hui Liu, Quan Du, Tong Xiao, Chunliang Zhang, and Jingbo Zhu. Learning light-weight translation models from deep transformer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 13217–13225, 2021. 108 Introduction to Transformers Bei Li, Quan Du, Tao Zhou, Yi Jing, Shuhan Zhou, Xin Zeng, Tong Xiao, Jingbo Zhu, Xuebo Liu, and Min Zhang. Ode transformer: An ordinary differential equation-inspired model for sequence generation. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8335–8351, 2022a. Bei Li, Tong Zheng, Yi Jing, Chengbo Jiao, Tong Xiao, and Jingbo Zhu. Learning multiscale transformer models for sequence generation. In International Conference on Machine Learning, pages 13225–13241. PMLR, 2022b. Hongkang Li, Meng Wang, Sijia Liu, and Pin-Yu Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. In The Eleventh International Conference on Learning Representations, 2022c. Junhui Li, Deyi Xiong, Zhaopeng Tu, Muhua Zhu, Min Zhang, and Guodong Zhou. Modeling source syntax for neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 688–697, 2017. Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. Blip: Bootstrapping languageimage pre-training for unified vision-language understanding and generation. In International Conference on Machine Learning, pages 12888–12900. PMLR, 2022d. Yanghao Li, Chao-Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Mvitv2: Improved multiscale vision transformers for classification and detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4804–4814, 2022e. Kaiyuan Liao, Yi Zhang, Xuancheng Ren, Qi Su, Xu Sun, and Bin He. A global pastfuture early exit method for accelerating inference of pre-trained language models. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2013–2023, 2021. Tatiana Likhomanenko, Qiantong Xu, Gabriel Synnaeve, Ronan Collobert, and Alex Rogozhnikov. Cape: Encoding relative positions with continuous augmented positional embeddings. Advances in Neural Information Processing Systems, 34:16079–16092, 2021. Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. AI Open, 2022a. Ye Lin, Shuhan Zhou, Yanyang Li, Anxiang Ma, Tong Xiao, and Jingbo Zhu. Multi-path transformer is better: A case study on neural machine translation. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 5646–5656, 2022b. Fenglin Liu, Xuancheng Ren, Zhiyuan Zhang, Xu Sun, and Yuexian Zou. Rethinking skip connection with layer normalization. In Proceedings of the 28th international conference on computational linguistics, pages 3586–3598, 2020a. Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. arXiv preprint arXiv:2304.08485, 2023a. 109 Xiao and Zhu Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the difficulty of training transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5747–5763, 2020b. Peter J Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. In Proceedings of International Conference on Learning Representations, 2018. Yang Liu, Yao Zhang, Yixin Wang, Feng Hou, Jin Yuan, Jiang Tian, Yang Zhang, Zhongchao Shi, Jianping Fan, and Zhiqiang He. A survey of visual transformers. IEEE Transactions on Neural Networks and Learning Systems, 2023b. Yuchen Liu, Junnan Zhu, Jiajun Zhang, and Chengqing Zong. Bridging the modality gap for speech-to-text translation. arXiv preprint arXiv:2010.14920, 2020c. Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention-based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1412–1421, 2015. Christopher D Manning, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. Emergent linguistic structure in artificial neural networks trained by self-supervision. Proceedings of the National Academy of Sciences, 117(48):30046–30054, 2020. Pedro Henrique Martins, Zita Marinho, and Andr´e FT Martins. ∞-former: Infinite memory transformer-former: Infinite memory transformer. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5468–5485, 2022. Saeed Masoudnia and Reza Ebrahimpour. Mixture of experts: a literature survey. The Artificial Intelligence Review, 42(2):275, 2014. JS McCarley, Rishav Chakravarti, and Avirup Sil. Structured pruning of a bert-based question answering model. arXiv preprint arXiv:1910.06360, 2019. William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843–856, 2022. Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? Advances in neural information processing systems, 32, 2019. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, page 31113119, 2013. Markus Nagel, Marios Fournarakis, Rana Ali Amjad, Yelysei Bondarenko, Mart Van Baalen, and Tijmen Blankevoort. A white paper on neural network quantization. arXiv preprint arXiv:2106.08295, 2021. 110 Introduction to Transformers Alan V Oppenheim and Ronald W Schafer. Digital signal processing(book). Prentice-Hall, 1975. Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXiv:2303.06349, 2023. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744, 2022. Wonpyo Park, Dongju Kim, Yan Lu, and Minsu Cho. Relational knowledge distillation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3967–3976, 2019. Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In International conference on machine learning, pages 4055–4064. PMLR, 2018. Baoyun Peng, Xiao Jin, Jiaheng Liu, Dongsheng Li, Yichao Wu, Yu Liu, Shunfeng Zhou, and Zhaoning Zhang. Correlation congruence for knowledge distillation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5007–5016, 2019. Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, et al. Rwkv: Reinventing rnns for the transformer era. arXiv preprint arXiv:2305.13048, 2023. H Peng, N Pappas, D Yogatama, R Schwartz, N Smith, and L Kong. Random feature attention. In Proceedings of International Conference on Learning Representations (ICLR 2021), 2021. Jorge P´erez, Javier Marinkovi´c, and Pablo Barcel´o. On the turing completeness of modern neural network architectures. In Proceedings of International Conference on Learning Representations, 2018. Fabio Petroni, Tim Rockt¨aschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. Language models as knowledge bases? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2463–2473, 2019. Ngoc-Quan Pham, Thai-Son Nguyen, Jan Niehues, Markus M¨uller, Sebastian St¨uker, and Alexander Waibel. Very deep self-attention networks for end-to-end speech recognition. arXiv preprint arXiv:1904.13377, 2019. Telmo Pessoa Pires, Ant´onio V Lopes, Yannick Assogba, and Hendra Setiawan. One wide feedforward is all you need. arXiv preprint arXiv:2309.01826, 2023. 111 Xiao and Zhu Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. In Proceedings of Machine Learning and Systems, 2023. Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In Proceedings of International Conference on Learning Representations, 2021. Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. Bpe-dropout: Simple and effective subword regularization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1882–1892, 2020. Jiezhong Qiu, Hao Ma, Omer Levy, Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2555–2565, 2020. Lawrence R Rabiner and Bernard Gold. Theory and application of digital signal processing. Prentice-Hall, 1975. Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, Chloe Hillier, and Timothy P Lillicrap. Compressive transformers for long-range sequence modelling. In Proceedings of International Conference on Learning Representations, 2019. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140): 1–67, 2020. Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3982–3992, 2019. Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. Fitnets: Hints for thin deep nets. arXiv preprint arXiv:1412.6550, 2014. Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient contentbased sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53–68, 2021. Michael Santacroce, Zixin Wen, Yelong Shen, and Yuanzhi Li. What matters in the structured pruning of generative language models? arXiv preprint arXiv:2302.03773, 2023. Imanol Schlag, Kazuki Irie, and J¨urgen Schmidhuber. Linear transformers are secretly fast weight programmers. In Proceedings of International Conference on Machine Learning, pages 9355–9366. PMLR, 2021. 112 Introduction to Transformers Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Tran, Yi Tay, and Donald Metzler. Confident adaptive language modeling. Advances in Neural Information Processing Systems, 35:17456–17472, 2022. Roy Schwartz, Gabriel Stanovsky, Swabha Swayamdipta, Jesse Dodge, and Noah A Smith. The right tool for the job: Matching model and instance complexities. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6640– 6651, 2020. Abigail See. Deep learning, structure and innate priors: A discussion between yann lecun and christopher manning, 02 2018. URL http://www.abigailsee.com/2018/02/21/ deep-learning-structure-and-innate-priors.html. Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1715–1725, 2016. Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 464–468, 2018. Noam Shazeer. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:1911.02150, 2019. Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-ofexperts layer. In Proceedings of International Conference on Learning Representations, 2017. Dinghan Shen, Mingzhi Zheng, Yelong Shen, Yanru Qu, and Weizhu Chen. A simple but tough-to-beat data augmentation approach for natural language understanding and generation. arXiv preprint arXiv:2009.13818, 2020. Xing Shi, Inkit Padhi, and Kevin Knight. Does string-based neural mt learn source syntax? In Proceedings of the 2016 conference on empirical methods in natural language processing, pages 1526–1534, 2016. Maciej Skorski, Alessandro Temperoni, and Martin Theobald. Revisiting weight initialization of deep neural networks. In Asian Conference on Machine Learning, pages 1192–1207. PMLR, 2021. David So, Quoc Le, and Chen Liang. The evolved transformer. In Proceedings of International conference on machine learning, pages 5877–5886. PMLR, 2019. Matthias Sperber, Jan Niehues, Graham Neubig, Sebastian St¨uker, and Alex Waibel. Selfattentional acoustic models. In Proceedings of Interspeech 2018, pages 3723–3727, 2018. Rupesh Kumar Srivastava, Klaus Greff, and J¨urgen Schmidhuber. Highway networks. arXiv preprint arXiv:1505.00387, 2015. 113 Xiao and Zhu Pierre Stock, Angela Fan, Benjamin Graham, Edouard Grave, R´emi Gribonval, Herve Jegou, and Armand Joulin. Training with quantization noise for extreme model compression. In Proceedings of International Conference on Learning Representations, 2021. Emma Strubell, Patrick Verga, Daniel Andor, David Weiss, and Andrew McCallum. Linguistically-informed self-attention for semantic role labeling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 5027– 5038, 2018. Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. arXiv preprint arXiv:2104.09864, 2021. Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, et al. End-to-end memory networks. Advances in neural information processing systems, 28, 2015. Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive ´ attention span in transformers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 331–335, 2019. Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models. arXiv preprint arXiv:2307.08621, 2023. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Proceedings of 2nd International Conference on Learning Representations (ICLR 2014), 2014. Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pages 6105–6114. PMLR, 2019. Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. In Proceedings of International Conference on Machine Learning, pages 9438– 9447. PMLR, 2020a. Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. CoRR, abs/2009.06732, 2020b. Ian Tenney, Dipanjan Das, and Ellie Pavlick. Bert rediscovers the classical nlp pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4593–4601, 2019a. Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R Thomas McCoy, Najoung Kim, Benjamin Van Durme, Samuel R Bowman, Dipanjan Das, et al. What do you learn from context? probing for sentence structure in contextualized word representations. In Proceedings of International Conference on Learning Representations, 2019b. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timoth´ee Lacroix, Baptiste Rozi`ere, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 114 Introduction to Transformers Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023a. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023b. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of Advances in Neural Information Processing Systems, volume 30, 2017. Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. Grammar as a foreign language. Advances in neural information processing systems, 28, 2015. Elena Voita, Pavel Serdyukov, Rico Sennrich, and Ivan Titov. Context-aware neural machine translation learns anaphora resolution. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1264–1274, 2018. Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multihead self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5797–5808, 2019. Eric Wallace, Yizhong Wang, Sujian Li, Sameer Singh, and Matt Gardner. Do nlp models know numbers? probing numeracy in embeddings. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 5307–5315, 2019. Hanrui Wang, Zhanghao Wu, Zhijian Liu, Han Cai, Ligeng Zhu, Chuang Gan, and Song Han. Hat: Hardware-aware transformers for efficient natural language processing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7675–7688, 2020a. Hongyu Wang, Shuming Ma, Li Dong, Shaohan Huang, Dongdong Zhang, and Furu Wei. Deepnet: Scaling transformers to 1,000 layers. arXiv preprint arXiv:2203.00555, 2022a. Hongyu Wang, Shuming Ma, Shaohan Huang, Li Dong, Wenhui Wang, Zhiliang Peng, Yu Wu, Payal Bajaj, Saksham Singhal, Alon Benhaim, et al. Foundation transformers. arXiv preprint arXiv:2210.06423, 2022b. Jue Wang, Ke Chen, Gang Chen, Lidan Shou, and Julian McAuley. Skipbert: Efficient inference with shallow layer skipping. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7287–7301, 2022c. 115 Xiao and Zhu Lin Wang and Kuk-Jin Yoon. Knowledge distillation and student-teacher learning for visual intelligence: A review and new outlooks. IEEE transactions on pattern analysis and machine intelligence, 44(6):3048–3068, 2021. Peihao Wang, Rameswar Panda, Lucas Torroba Hennigen, Philip Greengard, Leonid Karlinsky, Rogerio Feris, David Daniel Cox, Zhangyang Wang, and Yoon Kim. Learning to grow pretrained models for efficient transformer training. In Proceedings of The Eleventh International Conference on Learning Representations, 2023. Qiang Wang, Fuxue Li, Tong Xiao, Yanyang Li, Yinqiao Li, and Jingbo Zhu. Multilayer representation fusion for neural machine translation. In Proceedings of the 27th International Conference on Computational Linguistics, pages 3015–3026, 2018a. Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F Wong, and Lidia S Chao. Learning deep transformer models for machine translation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1810–1822, 2019. Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Selfattention with linear complexity. arXiv preprint arXiv:2006.04768, 2020b. Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dynamic routing in convolutional networks. In Proceedings of the European Conference on Computer Vision (ECCV), pages 409–424, 2018b. Ziheng Wang, Jeremy Wohlwend, and Tao Lei. Structured pruning of large language models. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6151–6162, 2020c. Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682, 2022. Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Proceedings of International Conference on Machine Learning, pages 11080–11090. PMLR, 2021. Felix Wu, Angela Fan, Alexei Baevski, Yann Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. In Proceedings of International Conference on Learning Representations, 2018a. Felix Wu, Angela Fan, Alexei Baevski, Yann Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. In Proceedings of International Conference on Learning Representations, 2019. Yuhuai Wu, Markus Norman Rabe, DeLesley Hutchins, and Christian Szegedy. Memorizing transformers. In Proceedings of International Conference on Learning Representations, 2021. 116 Introduction to Transformers Zhanghao Wu, Zhijian Liu, Ji Lin, Yujun Lin, and Song Han. Lite transformer with longshort range attention. In Proceedings of International Conference on Learning Representations (ICLR), 2020. Zuxuan Wu, Tushar Nagarajan, Abhishek Kumar, Steven Rennie, Larry S Davis, Kristen Grauman, and Rogerio Feris. Blockdrop: Dynamic inference paths in residual networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8817–8826, 2018b. Tong Xiao, Yinqiao Li, Jingbo Zhu, Zhengtao Yu, and Tongran Liu. Sharing attention weights for fast transformer. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), pages 5292–5298, 2019. Saining Xie, Ross Girshick, Piotr Doll´ar, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492–1500, 2017. Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. Deebert: Dynamic early exiting for accelerating bert inference. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2246–2251, 2020. Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pages 10524– 10533, 2020. Canwen Xu and Julian Mcauley. A survey on dynamic neural networks for natural language processing. In Findings of the Association for Computational Linguistics: EACL 2023, pages 2325–2336, 2023. Chen Xu, Bojie Hu, Yanyang Li, Yuhao Zhang, Shen Huang, Qi Ju, Tong Xiao, and Jingbo Zhu. Stacked acoustic-and-textual encoding: Integrating the pre-trained models into speech translation encoders. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 2619–2630, 2021a. Chen Xu, Rong Ye, Qianqian Dong, Chengqi Zhao, Tom Ko, Mingxuan Wang, Tong Xiao, and Jingbo Zhu. Recent advances in direct speech-to-text translation. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23): Survey Track, pages 6796–6804, 2023a. Chen Xu, Yuhao Zhang, Chengbo Jiao, Xiaoqian Liu, Chi Hu, Xin Zeng, Tong Xiao, Anxiang Ma, Huizhen Wang, and Jingbo Zhu. Bridging the granularity gap for acoustic modeling. In Findings of the Association for Computational Linguistics: ACL 2023, pages 10816–10833, 2023b. Hongfei Xu, Qiuhui Liu, Josef van Genabith, Deyi Xiong, and Jingyi Zhang. Lipschitz constrained parameter initialization for deep transformers. In Proceedings of the 58th 117 Xiao and Zhu Annual Meeting of the Association for Computational Linguistics, pages 397–402, July 2020. Peng Xu, Xiatian Zhu, and David A Clifton. Multimodal learning with transformers: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023c. Zenan Xu, Daya Guo, Duyu Tang, Qinliang Su, Linjun Shou, Ming Gong, Wanjun Zhong, Xiaojun Quan, Daxin Jiang, and Nan Duan. Syntax-enhanced pre-trained model. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 5412–5422, 2021b. Baosong Yang, Zhaopeng Tu, Derek F Wong, Fandong Meng, Lidia S Chao, and Tong Zhang. Modeling localness for self-attention networks. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4449–4458, 2018. Zhengyuan Yang, Linjie Li, Kevin Lin, Jianfeng Wang, Chung-Ching Lin, Zicheng Liu, and Lijuan Wang. The dawn of lmms: Preliminary explorations with gpt-4v (ision). arXiv preprint arXiv:2309.17421, 2023a. Zi Yang, Samridhi Choudhary, Siegfried Kunzmann, and Zheng Zhang. Quantization-aware and tensor-compressed training of transformers for natural language understanding. arXiv preprint arXiv:2306.01076, 2023b. Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. Hierarchical attention networks for document classification. In Proceedings of the 2016 conference of the North American chapter of the association for computational linguistics: human language technologies, pages 1480–1489, 2016. Rong Ye, Mingxuan Wang, and Lei Li. End-to-end speech translation via cross-modal progressive training. arXiv preprint arXiv:2104.10380, 2021. Shukang Yin, Chaoyou Fu, Sirui Zhao, Ke Li, Xing Sun, Tong Xu, and Enhong Chen. A survey on multimodal large language models. arXiv preprint arXiv:2306.13549, 2023. Yaodong Yu, Sam Buchanan, Druv Pai, Tianzhe Chu, Ziyang Wu, Shengbang Tong, Benjamin D Haeffele, and Yi Ma. White-box transformers via sparse rate reduction. arXiv preprint arXiv:2306.01129, 2023. Seniha Esen Yuksel, Joseph N Wilson, and Paul D Gader. Twenty years of mixture of experts. IEEE transactions on neural networks and learning systems, 23(8):1177–1193, 2012. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In Proceedings of International Conference on Learning Representations, 2019. Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: 118 Introduction to Transformers Transformers for longer sequences. Advances in neural information processing systems, 33:17283–17297, 2020. Biao Zhang, Deyi Xiong, and Jinsong Su. Accelerating neural transformer via an average attention network. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1789–1798, 2018. Biao Zhang, Ivan Titov, and Rico Sennrich. Improving deep transformer with depth-scaled initialization and merged attention. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 898–909, 2019. Zhuosheng Zhang, Yuwei Wu, Junru Zhou, Sufeng Duan, Hai Zhao, and Rui Wang. Sg-net: Syntax-guided machine reading comprehension. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9636–9643, 2020. Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11106– 11115, 2021. Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Ke Xu, and Furu Wei. Bert loses patience: Fast and robust inference with early exit. Advances in Neural Information Processing Systems, 33:18330–18341, 2020. Zhi-Hua Zhou. Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC, 2012. Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In Proceedings of International Conference on Learning Representations, 2016. 119

Research Papers: transformer architectures, <4 authors, PhD

Criteria

Enrichments

Find more results