Higher Order Linear Transformer

Jean MercatarXiv 2020 · OpenReview

Abstract

Following up on the linear transformer part of the article from Katharopoulos et al., that takes this idea from Shen et al., the trick that produces a linear complexity for the attention mechanism is re-used and extended to a second-order approximation of the softmax normalization.

Introduction

Standard Transformers are limited by the quadratic $O(n^2)$ complexity of their attention mechanism, where $n$ is the sequence length. While "Linear Transformers" offer a solution by approximating the Softmax operator with kernels, they often suffer from reduced accuracy compared to full attention. This work explores using higher-order Taylor expansions of the exponential function to better approximate Softmax while maintaining linear complexity relative to sequence length.

Methodology

The core proposal is to replace the $\exp(x)$ term in Softmax with its Taylor series expansion: $$\exp(x) \approx 1 + x + \frac{x^2}{2}$$

To implement this efficiently, several techniques are employed:

  1. Normalization: Since Taylor expansions are local approximations, Layer Normalization (without learnable affine transforms) and a scaling parameter $\alpha$ are used to keep dot products small.
  2. Linear Complexity Trick: By using multinomial expansion for the second-order term, the computation can be re-ordered from $(QK^T)V$ to $Q(K^TV)$, achieving $O(n)$ complexity.
  3. Complexity Trade-offs: The complexity scales as $O(n \cdot d_v \cdot d_k^{o_t})$, where $o_t$ is the expansion order.
Taylor series approximations of the exponential function compared to the original curve.

Key Insights

The choice of expansion order is critical. As shown in the figure above, even-order expansions (like the 2nd order) are preferred because they remain positive for negative inputs, avoiding the instability of odd-order expansions which can produce negative values. Furthermore, the author notes a "zero correlation" problem where a dot product of zero results in a baseline value of 1 in standard attention; subtracting 1 from the expansion might allow the model to represent zero correlation more naturally.

Results and Limitations

Currently, the model has been tested primarily on synthetic data. While theoretically sound, the second-order expansion introduces a $d_k^2$ overhead that may offset sequence-length gains for shorter contexts. Higher-order expansions (3rd or 4th) likely hit a wall of diminishing returns where they become slower than standard $O(n^2)$ attention due to the exponential growth in the head dimension $d_k$.

Conclusion

Higher-order linear transformers provide a promising mathematical framework for improving linear attention. Future work will focus on empirical benchmarking against standard transformers on real-world long-sequence tasks to determine if the increased precision of the second-order approximation translates to better performance in practice.

Summary updated

Abstract

Following up on the linear transformer part of the article from Katharopoulos et al., that takes this idea from Shen et al., the trick that produces a linear complexity for the attention mechanism is re-used and extended to a second-order approximation of the softmax normalization.
BibTeX
@misc{mercat2020higher,
  author = {Jean Mercat},
  title = {{Higher Order Linear Transformer}},
  year = {2020},
  eprint = {2010.14816},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.14816},
}
Figure