Higher Order Transformers With Kronecker-Structured Attention

Modern datasets are increasingly high-dimensional and multiway, naturally represented as tensors with multiple indexed variables. Such data arise in numerous applications, including multivariate time series forecasting, 3D medical imaging, and climate modeling. While Transformers have demonstrated exceptional performance in sequence modeling and high-dimensional learning tasks, their direct application to multiway data remains computationally prohibitive due to the quadratic complexity of dot-product attention. Moreover, standard self-attention mechanisms do not inherently preserve the tensor structure, leading to inefficiencies in capturing cross-dimensional dependencies.In this work, we introduce the Higher-Order Transformer (HOT), a novel attention mechanism designed to process multiway data efficiently. HOT leverages Kronecker factorization to express multiway attention as either a sum of Kronecker products or mode-wise attention matrices, effectively capturing structured dependencies while significantly reducing computational and memory overhead. Unlike conventional self-attention, HOT maintains the original tensor structure, ensuring efficient representation of both dense and sparse interactions across dimensions. Through theoretical analysis, we show that HOT retains the expressiveness of full high-order attention while providing a mechanism to control complexity via the factorization rank.We evaluate HOT on challenging real-world datasets, including multivariate time series forecasting, 3D medical image classification, and stock market prediction. Experimental results demonstrate that HOT achieves competitive or superior performance compared to state-of-the-art Transformer-based baselines while requiring significantly fewer computational resources. Additionally, ablation studies highlight the impact of factorization rank, positional encoding strategies, and attention patterns, providing further insights into HOT’s efficiency and adaptability. Our findings underscore HOT's potential as a scalable and effective solution for high-dimensional multiway learning, paving the way for future extensions in autoregressive modeling, large-scale vision tasks, and cross-modal learning