Higher-Order Transformers With Kronecker-Structured Attention
This work addresses a computational bottleneck for researchers and practitioners handling multiway data in domains like time series and image analysis, offering an incremental improvement over existing Transformer methods.
The paper tackles the computational inefficiency of applying Transformers to high-dimensional, multiway tensor data by proposing the Higher-Order Transformer (HOT), which uses Kronecker-structured attention to reduce costs while preserving tensor structure, achieving competitive performance in tasks like multivariate time series forecasting and image classification with significantly lower computational and memory requirements.
Modern datasets are increasingly high-dimensional and multiway, often represented as tensor-valued data with multi-indexed variables. While Transformers excel in sequence modeling and high-dimensional tasks, their direct application to multiway data is computationally prohibitive due to the quadratic cost of dot-product attention and the need to flatten inputs, which disrupts tensor structure and cross-dimensional dependencies. We propose the Higher-Order Transformer (HOT), a novel factorized attention framework that represents multiway attention as sums of Kronecker products or sums of mode-wise attention matrices. HOT efficiently captures dense and sparse relationships across dimensions while preserving tensor structure. Theoretically, HOT retains the expressiveness of full high-order attention and allows complexity control via factorization rank. Experiments on 2D and 3D datasets show that HOT achieves competitive performance in multivariate time series forecasting and image classification, with significantly reduced computational and memory costs. Visualizations of mode-wise attention matrices further reveal interpretable high-order dependencies learned by HOT, demonstrating its versatility for complex multiway data across diverse domains. The implementation of our proposed method is publicly available at https://github.com/s-omranpour/HOT.