Motivated by the factorization inherent in the original fast multipole method
and the improved fast Gauss transform we introduce a factorable form of
attention that operates efficiently in high dimensions. This approach reduces
the computational and memory complexity of the attention mechanism in
transformers from $O(N^2)$ to $O(N)$. In comparison to previous attempts, our
work presents a linearly scaled attention mechanism that maintains the full
representation of the attention matrix without compromising on sparsification
and incorporates the all-to-all relationship between tokens. We explore the
properties of our new attention metric and conduct tests in various standard
settings. Results indicate that our attention mechanism has a robust
performance and holds significant promise for diverse applications where
self-attention is used.

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