Momentum Transformer: Closing the Performance Gap Between Self-attention and Its Linearization

Tan M. Nguyen, Richard G. Baraniuk, Robert M. Kirby, Stanley J. Osher, Bao Wang

TL;DR

This paper introduces the "Momentum Transformer," a novel architecture that enhances the accuracy of efficient linear transformers by incorporating momentum, inspired by gradient descent optimization. It achieves this while maintaining linear computational complexity and introduces an adaptive momentum strategy to further improve performance and reduce hyperparameter tuning.

What Problem Does This Paper Address?

Standard Transformer models, while highly successful in sequence modeling, suffer from a quadratic increase in computational and memory requirements as the input sequence length grows. This makes them impractical for tasks involving very long sequences. While various "efficient transformers" have been proposed to address this, they often sacrifice accuracy for speed. This paper aims to bridge this performance gap by improving the accuracy of linear transformers without compromising their efficiency.

Methods

The core innovation is the "Momentum Transformer," which builds upon linear transformers. The authors draw an analogy between the linear attention mechanism and gradient descent. They then introduce "heavy ball" style momentum into this analogy, first into the causal linear attention formulation (resulting in "causal momentum attention") and then generalizing it to "momentum attention" for both autoregressive and non-autoregressive tasks.

Additionally, they introduce a "momentum connection" to replace the standard residual connection between the attention output and the input, further boosting performance. A key contribution is an "adaptive momentum" strategy. This strategy dynamically computes the momentum value based on the optimal momentum for quadratic optimization, eliminating the need for manual hyperparameter tuning and improving robustness.

Datasets

The paper evaluates the proposed models on a variety of tasks and datasets, including:

  • Synthetic Copy Task: A custom task for analyzing convergence speed.
  • MNIST and CIFAR-10 Image Generation: Standard datasets for image generation tasks.
  • Long-Range Arena (LRA) Benchmark: A suite of tasks designed to test performance on long sequences, including ListOps, text classification, document retrieval, and image classification on sequences.
  • IWSLT'16 En-De Dataset: Used for non-autoregressive machine translation.

Key Insights and Ideas

  • Momentum as a Bridge: The paper elegantly connects the optimization concept of momentum to improving the performance of linear transformers, showing that it can recover accuracy lost in linearizations.
  • Linear Attention as Gradient Descent: The interpretation of linear attention as a gradient descent step provides a novel theoretical lens for understanding and modifying these efficient architectures.
  • Adaptive Momentum Simplifies Tuning: The adaptive momentum strategy is a significant practical improvement, removing the burden of hyperparameter search and making the model more robust and easier to deploy.
  • Momentum Connection Enhances Performance: Integrating momentum into the residual connection offers an additional avenue for performance gains, complementing the momentum in the attention mechanism itself.

Key Results

  • Improved Accuracy: Momentum Transformers consistently outperform standard linear transformers and other efficient models (like Reformer) in terms of accuracy across various tasks, including image generation and machine translation.
  • Faster Convergence: Momentum-based transformers converge significantly faster during training compared to linear transformers.
  • Maintained Efficiency: The Momentum Transformer retains the O(N) memory and computational complexity of linear transformers, making it suitable for long sequences.
  • Competitive with Softmax: While not matching the absolute fastest convergence of the standard softmax transformer, the Momentum Transformer achieves comparable or better accuracy with vastly superior efficiency.
  • Adaptive Momentum Performance: The adaptive momentum transformer performs comparably to the best manually tuned momentum transformer, demonstrating the effectiveness of the adaptive strategy. For example, on MNIST generation, adaptive momentum transformer achieved the best test bits/dim.

Limitations and Future Work

  • Hyperparameter Sensitivity (for non-adaptive): While the adaptive strategy addresses this, the paper notes that tuning momentum hyperparameters (like $\beta$) can be computationally costly.
  • Future Work: The authors suggest exploring momentum based on other optimization algorithms (e.g., Adam) and designing improved weighting schemes for attention. They also highlight the potential for further improvements with more thorough hyperparameter searches on complex tasks.

Summary updated

Abstract

Transformers have achieved remarkable success in sequence modeling and beyond but suffer from quadratic computational and memory complexities with respect to the length of the input sequence. Leveraging techniques include sparse and linear attention and hashing tricks; efficient transformers have been proposed to reduce the quadratic complexity of transformers but significantly degrade the accuracy. In response, we first interpret the linear attention and residual connections in computing the attention map as gradient descent steps. We then introduce momentum into these components and propose the \emph{momentum transformer}, which utilizes momentum to improve the accuracy of linear transformers while maintaining linear memory and computational complexities. Furthermore, we develop an adaptive strategy to compute the momentum value for our model based on the optimal momentum for quadratic optimization. This adaptive momentum eliminates the need to search for the optimal momentum value and further enhances the performance of the momentum transformer. A range of experiments on both autoregressive and non-autoregressive tasks, including image generation and machine translation, demonstrate that the momentum transformer outperforms popular linear transformers in training efficiency and accuracy.
BibTeX
@inproceedings{nguyen2022momentum,
  author = {Tan M. Nguyen and Richard G. Baraniuk and Robert M. Kirby and Stanley J. Osher and Bao Wang},
  title = {{Momentum Transformer: Closing the Performance Gap Between Self-attention and Its Linearization}},
  booktitle = {MSML},
  year = {2022},
}
Figure