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

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

Abstract

Standard Transformers suffer from a quadratic computational bottleneck, $O(N^2)$, which limits their application to long sequences. While Linear Transformers offer an $O(N)$ alternative, they historically suffer from a significant performance gap compared to their softmax-based counterparts. This paper introduces the Momentum Transformer, which bridges this gap by re-interpreting attention and residual connections through the lens of mathematical optimization. By integrating "heavy ball" momentum into the architecture, the model achieves superior accuracy and faster convergence while maintaining the efficiency of linear models.

1. Introduction

The Transformer architecture has revolutionized sequence modeling, yet its reliance on softmax attention creates a computational and memory bottleneck that scales quadratically with sequence length. This makes processing high-resolution images or long documents prohibitively expensive. Linear Transformers were developed to mitigate this by using kernel tricks to achieve linear complexity. However, these efficient models often fail to match the accuracy of standard Transformers.

In this work, the authors identify a fundamental reason for this performance gap: the mathematical structure of linear attention behaves like a simple gradient descent step, which is often too imprecise to capture complex, long-range dependencies. To solve this, they propose the Momentum Transformer, which incorporates classical optimization techniques—specifically the "Heavy Ball" momentum method—to accelerate and refine the model's internal representations.

2. Methodology

The Momentum Transformer introduces three primary innovations designed to enhance the expressive power of linear attention without sacrificing its $O(N)$ efficiency.

2.1 Causal Momentum Attention

By re-interpreting the Recurrent Neural Network (RNN) formulation of linear attention as a gradient descent update, the authors identify that the hidden state update can be significantly improved. By adding a momentum term to this update, the model can "remember" and accumulate information from previous tokens more effectively. This allows the hidden state to act as a more robust memory buffer for long-range dependencies.

2.2 Momentum Connections

Standard Transformers rely on residual connections (adding the input of a layer to its output) to facilitate gradient flow. The authors replace this with a Momentum Connection, which incorporates the difference between the current and previous layers. This architectural change helps signals propagate more deeply and stably through the network, mimicking the behavior of accelerated optimization paths.

2.3 Adaptive Momentum Strategy

A common hurdle in using momentum is the difficulty of tuning hyperparameters. To address this, the authors derived an adaptive strategy based on the theory of quadratic optimization. This allows the model to calculate the optimal momentum value dynamically during training, eliminating the need for expensive grid searches and ensuring stable performance across different tasks.

3. Experimental Results

The Momentum Transformer was evaluated across a diverse suite of benchmarks, demonstrating its versatility and efficiency.

3.1 Long-Range Arena (LRA)

On the LRA benchmark—a rigorous test for efficient transformers including tasks like ListOps, Text (IMDb), and Pathfinder—the Momentum Transformer consistently outperformed other popular efficient models, including the Performer, Reformer, and Linformer. This confirms that the momentum-based approach effectively captures the long-range dependencies that other $O(N)$ models miss.

3.2 Image Generation and Speed

In pixel-by-pixel image generation on MNIST, the Momentum Transformer achieved a test bits/dim of 0.80, actually outperforming the standard softmax transformer (0.84). Crucially, it achieved this while being 300x faster during the generation phase. On CIFAR-10, the model was over 4,000x faster than the standard transformer, highlighting its massive potential for real-time applications.

3.3 Convergence and Efficiency

Training curves indicate that the Momentum Transformer reaches high accuracy levels in significantly fewer iterations than standard linear transformers. This faster convergence, combined with its $O(N)$ complexity, makes it a highly efficient choice for large-scale sequence modeling.

4. Key Insights

  • Attention as Optimization: The core contribution is the analogy between transformer layers and optimization algorithms. If a standard layer is a gradient step, then a momentum transformer is an accelerated gradient step.
  • Opposite Reweighting: The authors observed that momentum effectively reweights how much attention is paid to past tokens. Interestingly, this reweighting is mathematically opposite to "local attention" schemes, suggesting that momentum is uniquely suited for global, long-range context.
  • Hyperparameter Relief: The adaptive momentum formula provides a "plug-and-play" solution for practitioners, yielding performance comparable to perfectly fine-tuned constant momentum without the manual overhead.

5. Conclusion and Future Work

The Momentum Transformer successfully closes the performance gap between $O(N^2)$ and $O(N)$ models by treating the architecture as an optimization process. While the momentum parameter within the attention mechanism still requires some manual tuning, the overall framework provides a significant leap in efficiency and accuracy. Future research may explore integrating other optimization algorithms, such as Adam or Nesterov Accelerated Gradient, directly into the transformer's structural design.

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 Minh 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