本文提出了简化的迭代算法，用于解决数据分析和科学计算中的两个基础性问题：规范相关分析和对称矩阵对的广义特征向量问题，并通过一个通用框架来解决广义特征向量问题，该框架仅需要对近似线性系统求解器进行黑匣子访问，该算法是全局线性收敛的，并具有可行的时间复杂度，适用于大规模矩阵。

Apr, 2016

本文提出了一种新的观点，即将数据定义为矩阵变量正态分布，并开发了一种直接运用于高维高阶张量数据的Kronecker注意力机制，相较于传统注意力机制，本文提出的方法大大降低了计算资源的需求，并在性能上优于未采用注意力机制和采用传统注意力机制的模型。

Jul, 2020

本文研究了Transformer网络中的自注意力矩阵，重点分析了稀疏模式的逼近。我们证明了通过固定自注意力参数，采用不同的输入即可逼近各种稀疏矩阵，并提出了一种基于随机映射技术的构造性证明和算法。尤其是，在保持矩阵元素比率不变的精度下，仅需要$log L$（L为序列长度）的$ d $即可逼近任何稀疏矩阵。

Jun, 2021

使用快速傅里叶变换（FFT）可以有效加速具有相对位置编码（RPE）的Transformer模型中的注意力计算，并且适当使用相对位置编码可以缓解基准核化注意力的训练不稳定性问题。

Jun, 2021

该研究论文通过使用多项式函数和多项式取样法，替代基于softmax的注意力机制，以及提出基于区块的算法，实现了一个能够在线性时间内计算多项式注意力机制的实用线性变换器架构，从而显著提高了大规模上下文下的注意力机制的速度。

Oct, 2023

FlashAttention算法解决了自我注意力在Transformer架构中的I/O复杂性问题，并且建立了通信复杂性与I/O复杂性之间的联系。

Feb, 2024

通过引入可分解的关注机制，我们将注意力机制的计算和内存复杂度从O(N^2)降低到O(N)，并保持了注意力矩阵的完整表示，具有稀疏性和全连接关系。经过各种标准设置的测试，结果表明我们的注意力机制具有稳定的性能，并在自我注意力被使用的多种应用领域中具有重要潜力。

Feb, 2024

大型语言模型对世界产生了深远影响，其中自注意机制是transformer在大型语言模型中取得成功的关键。然而，长度为n的输入序列带来的二次计算复杂度O(n^2)一直是对提高和扩展更长上下文的一个难以克服的障碍。本文利用注意力矩阵的卷积结构开发了一种有效的注意力计算近似方法，提出了一个类似秩基系统的卷积基系统，表明任意下三角（注意力）矩阵总是可以在该基系统中分解为k个结构化卷积矩阵的和。我们然后设计了一个算法，快速将注意力矩阵分解为k个卷积矩阵。借助快速傅里叶变换（FFT），可以在O(knd log n)的时间内计算注意力推理，其中d是隐藏维度。实际上，我们有d ≪ n，即d = 3,072和n = 1,000,000用于Gemma。因此，当kd = n^{o(1)}时，我们的算法实现了几乎线性时间，即n^{1+o(1)}。此外，注意力的训练前向和反向梯度也可以在n^{1+o(1)}内计算。我们的方法可以避免明确计算n×n的注意力矩阵，这可能会大大减轻二次计算复杂度。此外，我们的算法适用于任何输入矩阵。本研究提供了一种加速transformer注意力计算的新范式，以实现其对更长上下文的应用。

May, 2024

我们证明了张量注意力训练的反向梯度可以以几乎线性的$n^{1+o(1)}$时间计算，同时提供了梯度的闭式解，并通过多项式逼近和张量代数技巧提出了一种快速计算方法。我们的理论结果证实了高阶Transformer训练的可行性，并可能促进张量注意力架构的实际应用。

May, 2024

通过对两个m维变量的光滑函数进行采样生成的矩阵的低秩逼近是本文关注的重点。我们否定了先前文献中对一个特定类别的解析函数所提出的论点，即这些矩阵可以独立于m具有准确的逐个元素的秩逼近。我们在理论上解释了支持该论点的数值结果，并描述了三个更窄的函数类别，其中n×n由函数生成的矩阵可以在与维度m无关的情况下以O(log(n)ε^(-2)polylog(ε^(-1)))的逐个元素误差逼近。我们还将我们的论点扩展到了由m维变量的多线性积生成的张量的低秩张量列逼近。我们在Transformer神经网络的注意力低秩逼近的背景下讨论了我们的结果。

Jul, 2024