Generalizable Multi-linear Attention Network

Tao Jin, Zhou Zhao

Overview

The Generalizable Multi-linear Attention Network (MAN) addresses a major scaling bottleneck in multimodal learning: the exponential growth of computational complexity when integrating more than two modalities (e.g., video, audio, and text). By combining hierarchical tensor decomposition with a novel "Addition Random Features" mechanism, MAN reduces the complexity of high-order attention from exponential to linear. This breakthrough allows for the efficient and effective fusion of multiple data streams without sacrificing performance.

The Bottleneck in Multimodal Learning

In multimodal sequential learning, models must fuse information from diverse sources—such as a speaker's words, vocal tone, and facial expressions—to accurately understand sentiment or personality traits.

While existing methods like the Bilinear Attention Network (BAN) excel at fusing two modalities, they suffer from the "curse of dimensionality" when scaled up. For $m$ modalities, the attention map required to capture all interactions grows at a rate of $O(T^m)$, where $T$ is the sequence length. For three or more modalities, this becomes computationally prohibitive for standard hardware. Consequently, researchers are often forced to either limit their models to two modalities or rely on simplified fusion methods that fail to capture rich, fine-grained interactions across all sources simultaneously.

The MAN Architecture

To overcome these limitations, the authors introduce MAN, which employs several mathematical innovations to maintain the integrity of multimodal interactions while keeping computational costs manageable.

Architecture of the Generalizable Multi-linear Attention Network

The core innovations of MAN include:

  • Multi-Linear Pooling: An extension of bilinear pooling that uses low-rank decomposition to approximate high-order tensor operations for multiple input vectors.
  • Hierarchical Approximation Decomposition (HAD): Instead of calculating a massive $m$-dimensional attention tensor, MAN decomposes the operation into a series of smaller, linear projections. This shifts the complexity from $O(T^m)$ to $O(\sum T_j)$, making it linear relative to the number of modalities.
  • Addition Random Features (ARF): A primary challenge in linearizing attention is the non-linear softmax function. Inspired by the Performer architecture, the authors use ARF to approximate the non-linear softmax kernel using orthogonal random projections, enabling effective decomposition.
  • Local Sequential Constraints (LSC): To ensure the model respects the temporal nature of the data (e.g., aligning a spoken word at second 5 with the video frame at second 5), positional information is baked directly into the random feature space.
  • Transformer Compatibility: MAN is designed as a "plug-and-play" module, fully supporting the multi-head attention and residual connections standard in modern Transformer architectures.

Key Insights

A crucial realization in this work is the difference between additive and multiplicative interactions. As more modalities are added, multiplying attention weights (via the Hadamard product) often causes values to vanish toward zero. To counter this, the authors propose a Combinational Additive Operation (CAO), which maintains signal strength even as the number of modalities increases.

Furthermore, by successfully approximating the softmax kernel linearly, the model can reorder matrix multiplications (leveraging the associative property) to compute the final attention output without ever constructing the computationally massive $m$-order tensor.

Experimental Results

The model was rigorously evaluated across four diverse benchmarks: CMU-MOSI (sentiment analysis), POM (trait recognition), MSR-VTT (video-text retrieval), and LSMDC (movie clip retrieval).

Performance comparison on the CMU-MOSI dataset
  • State-of-the-Art Performance: On the CMU-MOSI sentiment task, the Transformer-based version of MAN achieved an impressive 83.0% F1 score, outperforming the popular Multimodal Transformer (MulT).
  • Superior Trait Recognition: On the POM dataset, MAN significantly outperformed baselines across almost all traits. For instance, it achieved 44.8% accuracy on the "Dominant" trait, compared to MulT's 38.9%.
  • Massive Efficiency Gains: Ablation studies demonstrated that the HAD approach reduced the floating-point operations (FLOPs) of a single-layer integration module from $10.23 \times 10^6$ down to just $3.87 \times 10^5$—a nearly 30x reduction in computational cost for that component.
  • Retrieval Success: On MSR-VTT, MAN achieved highly competitive results (e.g., 24.1 R@1 for Text-to-Video), proving its scalability to large retrieval tasks.

Limitations and Future Directions

While highly effective, MAN's performance is sensitive to the number of random features ($H$) used in the ARF approximation. If $H$ is set too low, the approximation of the softmax function degrades, leading to a drop in performance. Additionally, the authors note that when paired with an exceptionally powerful backbone (like a massive Transformer), the specific benefits of the MAN module can sometimes diminish, as the base model may already capture some high-order interactions internally.

Future work will explore integrating these high-order interaction methods with joint representation learning—creating a single, shared latent space for all modalities—rather than relying solely on late-stage attention fusion.

Summary updated

Abstract

The majority of existing multimodal sequential learning methods focus on how to obtain effective representations and ignore the importance of multimodal fusion. Bilinear attention network (BAN) is a commonly used fusion method, which leverages tensor operations to associate the features of different modalities. However, BAN has a poor compatibility for more modalities, since the computational complexity of the attention map increases exponentially with the number of modalities. Based on this concern, we propose a new method called generalizable multi-linear attention network (MAN), which can associate as many modalities as possible in linear complexity with hierarchical approximation decomposition (HAD). Besides, considering the fact that softmax attention kernels cannot be decomposed as linear operation directly, we adopt the addition random features (ARF) mechanism to approximate the non-linear softmax functions with enough theoretical analysis. We conduct extensive experiments on four datasets of three tasks (multimodal sentiment analysis, multimodal speaker traits recognition, and video retrieval), the experimental results show that MAN could achieve competitive results compared with the state-of-the-art methods, showcasing the effectiveness of the approximation decomposition and addition random features mechanism.
BibTeX
@inproceedings{jin2021generalizable,
  author = {Tao Jin and Zhou Zhao},
  title = {{Generalizable Multi-linear Attention Network}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
}
Figure