线性 Transformer变长思路汇总Dilated Sliding window、LongFormer、BigBird、LongNet、Reformer、GAU、RWKV

Transformer默认是512，在 线性Transformer应该不是你要等的那个模型 中强调对于base版来说，当序列长度不超过1536时，Transformer的复杂度都是近乎线性的；当序列长度超过1536时，Transformer的计算量逐渐以Attention为主，复杂度慢慢趋于二次方，直到长度超过4608，才真正以二次项为主。 今天来梳理下真有更长的Transformer如何做的一些方法：

Sparse Transformer

来自于Generating Long Sequences with Sparse Transformers，以下转载自https://kexue.fm/archives/6853#Sparse%20Self%20Attention：

Longformer: The Long-Document Transformer

来自于 https://arxiv.org/abs/2004.05150

也就是说，从下图实现来看Longformer和Sparse Transformer的思路是一样的，只是这篇的实验更加充分

Big Bird

• Random attention：对每个token随机选取其他的r个token计算attention，
  来源于图论中的Erdős–Rényi model：对于一个有N个节点的图，如果其每条边形成的概率为p，那么当p足够大时，就几乎会形成一个完全连通图；类比到Transformer中，不需要对每两个Token都计算attention，只要每个token以较大的概率对其他token做attention，那么整个序列就可以连通起来；
• Window attention：和第一篇的local self attention一样；
• Global attention：尽管Random attention已经保证整个序列大概率是联通的，选取一些global token在全局做attention还是会有更好的效果，同时不至于太过增加计算量。这里还分为internal和extended两种方法：a) internal：在序列中随机选取一些token作为global token；extended：在序列外额外补充一些token作为global token（例如[CLS]）；
  

LongNet（LongNet: Scaling Transformers to 1,000,000,000 Tokens）

这篇文章有两张亮炸眼的图：

然后看改进，其实和LongTransformer、Big Bird是一脉相承的，作者管这里叫Dilated Attention

Reformer: The Efficient Transformer

来自于https://arxiv.org/abs/2001.04451，以下转载自 https://kexue.fm/archives/7546

Reformer也是有代表性的改进工作，它将Attention的复杂度降到了