文章主要針對一類X-former模型，例如Reformer, Linformer, Performer, Longformer為例，這些對原版Transformer做了改進，提高了其計算和內(nèi)存的效率。

self-attention是Transformer模型的關鍵定義特征。該機制可以看作是類似graph的歸納偏差（inductive bias），它可將序列中的所有token與基于相關的pooling操作相聯(lián)系。self-attention 的一個眾所周知的問題是quadratic級別的時間和內(nèi)存復雜度，阻礙許多設置的模型規(guī)模化（scalability）。所以，最近提出了解決該問題的大量變型，這里將這類模型稱為efficient Transformers。

efficient self-attention模型在長序列建模的應用中至關重要，例如文檔、圖像和視頻通常都由相對大量的像素或token組成。因此，處理長序列的效率對于Transformers的廣泛采用至關重要。

如圖是一個標準的Transformer架構(gòu)：

Transformer是通過將Transformer blocks彼此堆疊而形成的多層體系結(jié)構(gòu)。Transformer blocks的特點包括multi-head self-attention機制、positionwise前饋網(wǎng)絡（feed-forward network）、層歸一化（LN）模塊和殘差連接器（residual connectors）。

Transformer模型的輸入通常是形狀為BxN的張量，其中B是批處理（batch）大小，N是序列長度。該輸入先穿過一個嵌入層，該層將每個one-hot token表示轉(zhuǎn)換為d-維的嵌入向量，即BxNxd。然后，新張量與位置編碼相加，并通過一個multi-head self-attention模塊。

位置編碼可以是正弦輸入形式或者可訓練的嵌入方式。multi-head self-attention模塊的輸入和輸出通過殘差連接器和層歸一化層（LN）模塊連接。然后，將multi-head self-attention模塊的輸出傳遞到兩層前饋網(wǎng)絡（FFN），類似于以殘差方式連接層歸一化（LN）模塊。

帶層歸一化模塊的殘差連接器定義為：

而在Multi-Head Self-Attention的單個head操作定義為：

Attention矩陣A = QK^T主要負責學習序列中token之間的校準分。這會推動self-attention的自我校準過程，從而token學習彼此之間的聚類。不過，這個矩陣計算是一個效率的瓶頸。

FFN的層操作定義為：

這樣整個Transformer block的操作定義是：

下面要注意的是Transformer模塊使用方式的不同。Transformer主要使用方式包括：（1）編碼器（例如用于分類），（2）解碼器（例如用于語言建模）和（3）編碼器-解碼器（例如用于機器翻譯）。

在編碼器-解碼器模式下，通常有多個multi-head self-attention模塊，包括編碼器和解碼器中的標準self-attention，以及允許解碼器利用來自解碼器的信息的編碼器-解碼器cross-attention。這影響了self-attention機制的設計。

在編碼器模式中，沒有限制或self-attention機制的約束必須是因果方式，即僅取決于現(xiàn)在和過去的token。

在編碼器-解碼器設置中，編碼器和編碼器-解碼器cross-attention可能是無因果方式，但解碼器的self attention必須是因果方式。設計有效的self attention機制，需要支持AR（auto-regressive）解碼的因果關系，這可能是一個普遍的限制因素。

Efficient Transformers的分類如圖，其對應的方法在近兩年（2018-2020）發(fā)表的時間、復雜度和類別見表：

注：FP = Fixed Patterns/Combinations of Fixed Patterns, M = Memory, LP = Learnable Pattern, LR = Low Rank, KR = Kernel, RC = Recurrence.

除segment-based recurrence外，大多數(shù)模型的主要目標是對attention matrix做quadratic級別開銷近似。每種方法都將稀疏的概念應用于原密集的attention機制。

Fixed patterns（FP）：self attention的最早改進是將視場限制為固定的、預定義模式（例如局部窗和固定步幅的塊模式）來簡化attention matrix。

• Blockwise Patterns這種技術(shù)在實踐中最簡單的示例是blockwise（或chunking）范式，將輸入序列分為固定塊，考慮局部接受野（local receptive fields）塊。這樣的示例包括逐塊和/或局部attention。將輸入序列分解為塊可將復雜度從N^2降低到B^2（塊大?。?，且B << N，從而顯著降低了開銷。這些blockwise或chunking的方法可作為許多更復雜模型的基礎。
• Strided patterns是另一種方法，即僅按固定間隔參與。諸如Sparse Transformer和/或Longformer之類的模型，采用“跨越式”或“膨脹式“視窗。
• Compressed Patterns是另一條進攻線，使用一些合并運算對序列長度進行下采樣，使其成為固定模式的一種形式。例如，Compressed Attention使用跨步卷積有效減少序列長度。

Combination of Patterns (CP)：其關鍵點是通過組合兩個或多個不同的訪問模式來提高覆蓋范圍。例如，Sparse Transformer 將其一半的頭部分配給模式，結(jié)合strided 和 local attention。類似地，Axial Transformer 在給定高維張量作為輸入的情況下，沿著輸入張量的單軸應用一系列的self attention計算。本質(zhì)上，模式組合以固定模式相同的方式降低了內(nèi)存的復雜度。但是，不同之處在于，多模式的聚集和組合改善了self attention機制的總覆蓋范圍。

Learnable Patterns (LP)：對預定FP模式的擴展即可學習。毫不奇怪，使用可學習模式的模型旨在數(shù)據(jù)驅(qū)動的方式學習訪問模式。LP的關鍵是確定token相關性，將token分配給buckets 或者clusters。值得注意的是，Reformer引入了基于哈希的相似性度量，有效地將token聚類為chunks。類似地，Routing Transformer在token上采用在線的k-means聚類。同時，Sinkhorn排序網(wǎng)絡（Sorting Network）通過學習對輸入序列的blocks排序來顯露attention weight的sparsity。所有這些模型中，相似性函數(shù)與網(wǎng)絡的其它部分一起進行端到端訓練。LP的關鍵點仍然是利用固定模式（chunked patterns）。但是，此類方法學會對輸入token進行排序/聚類，即保持FP方法效率優(yōu)勢的同時，得到更優(yōu)的序列全局視圖。

Memory：另一種表現(xiàn)突出的方法，用一個side memory模塊，可以一次訪問多個token。通用形式是全局存儲器，能夠訪問整個序列。全局token充當記憶的一種形式，從輸入序列的token中學習聚集。這是最早在Set Transformers中引入的inducing points方法。這些參數(shù)通常被解釋為“memory”，并用作將來處理的臨時上下文信息。這可以看作是parameter attention的一種形式。全局內(nèi)存也用于ETC和Longformer。借著數(shù)量有限的內(nèi)存（或者inducing points），對輸入序列采用類似pooling操作進行壓縮，這是設計有效的self attention模塊時可以使用的技巧。

Low-Rank 方法：另一種新興技術(shù)，利用self attention矩陣的低秩近似來提高效率。關鍵點是假設NxN矩陣的低秩結(jié)構(gòu)。Linformer是此技術(shù)的經(jīng)典示例，將keys和values的長度維投影到較低維的表示形式（N-》 k）。不難發(fā)現(xiàn)，由于NxN矩陣現(xiàn)在已分解為Nxk，因此該方法改善了self attention的存儲復雜性問題。

Kernels：另一個最近流行的提高Transformers效率的方法，通過核化（kernelization）查看attention機制。核的使用使self attention機制能夠進行巧妙的數(shù)學重寫，避免顯式地計算NxN矩陣。由于核是attention矩陣的一種近似形式，因此也可以視為Low Rank方法的一種。

Recurrence：blockwise方法的直接擴展是通過遞歸連接這些塊。Transformer-XL提出了一種segment-level 遞歸機制，該機制將多個segment和block連接起來。從某種意義上說，這些模型可以看作是FP模型。

該綜述對以下17個方法進行了內(nèi)存和計算復雜度分析，即

1、Memory Compressed Transformer：“Generating wikipedia by summarizing long sequences” 如圖

2、 Image Transformer：“Image Transformer” 如圖

3、 Set Transformer：“Set transformer: A framework for attention-based permutation-invariant neural networks“ 如圖

4、 Sparse Transformer：“Generating long sequences with sparse transformers”如圖

5、 Axial Transformer：“Axial attention in multidimensional transformers.“如圖

6、 Longformer：“Longformer: The long-document transformer“如圖

7、 Extended Transformer Construction (ETC)：“Etc: Encoding long and structured data in transformers“如圖

8、 BigBird：“Big Bird: Transformers for Longer Sequences“如圖

9、 Routing Transformer：“Efficient content-based sparse attention with routing transformers“如圖

10、 Reformer：“Reformer: The efficient transformer“如圖

11、 Sparse Sinkhorn Transformer：“Sparse sinkhorn attention“如圖

12、 Linformer：“Hat: Hardware-aware transformers for efficient natural language processing“如圖

13、 Linear Transformer：“Transformers are rnns: Fast autoregressive transformers with linear attention“ 如圖是其算法偽代碼

14、 Performer：“Masked language modeling for proteins via linearly scalable long-context transformers“ 如圖是Fast Attention via Orthogonal Random Features (FAVOR)的算法偽代碼

15、 Synthesizer：“Synthesizer: Rethinking self-attention in transformer models.“如圖

16、 Transformer-XL：“Transformer-xl: Attentive language models beyond a fixed-length context“如圖

17、 Compressive Transformers：“Compressive transformers for long-range sequence modelling“如圖

盡管該領域忙于使用新的Transformer模型，但幾乎沒有一種簡單的方法可以將這些模型比較。許多研究論文選擇自己的基準來展示所提出模型的功能。再加上不同的超參數(shù)設置（例如模型大小和配置），可能難以正確地找到性能提升的原因。此外，一些論文將其與預訓練相提并論，使區(qū)分這些不同模型相對性能的難度更大。考慮使用哪個基本高效的Transformer block，仍然是一個謎。

一方面，有多種模型集中在generative modeling，展示了提出的Transformer單元在序列AR（auto-regressive）建模上的能力。為此，Sparse Transformers, Adaptive Transformers, Routing Transformers 和 Reformers主要集中在generative modeling任務。這些基準通常涉及在諸如Wikitext、enwik8和/或ImageNet / CIFAR之類的數(shù)據(jù)集上進行語言建模和/或逐像素生成圖像。而segment based recurrence模型（例如Transformer-XL和Compressive Transformers）也專注于大范圍語言建模任務，例如PG-19。

一方面，一些模型主要集中于編碼（encoding only）的任務，例如問題解答、閱讀理解和/或從Glue基準中選擇。例如ETC模型僅在回答問題基準上進行實驗，如NaturalQuestions或TriviaQA。另一方面，Linformer專注于GLUE基準測試子集。這種分解是非常自然和直觀的，因為ETC和Linformer之類的模型無法以AR（auto-regressive）方式使用，即不能用于解碼。這加劇了這些編碼器模型與其他模型進行比較的難度。

有些模型著眼于上述兩者的平衡。Longformer試圖通過在生成建模和編碼器任務上運行基準來平衡這一點。Sinkhorn Transformer對生成建模任務和僅編碼任務進行比較。

此外，還值得注意的是，盡管Seq2Seq任務的機器翻譯（MT）是普及Transformer模型的問題之一，但這些有效的Transformer模型沒有能對MT進行多些的評估。這可能是因為MT的序列長度不足以保證這些模型的使用。

盡管generative modeling、GLUE（General Language Understanding Evaluation）和/或question answering，似乎是這些應用的通用評估基準，但仍有一些基準可供小部分論文單獨進行評估。首先，Performer模型會對masked language modeling進行評估，和其他有效的Transformer模型進行了正面對比。而且Linear Transformer還對語音識別進行評估，這是比較罕見的了。

另外，論文最后還對這些效率提高的方法做了分析比較，主要是幾個方面：

• Weight Sharing
• Quantization / Mixed Precision
• Knowledge Distillation (KD)
• Neural Architecture Search (NAS)
• Task Adapters