Tensor-to-tensor models with fast iterated sum features

Designing expressive yet computationally efficient layers for high-dimensional tensor data (e.g., images) remains a significant challenge. While sequence modeling has seen a shift toward linear-time architectures, extending these benefits to higher-order tensors is non-trivial. In this work, we introduce the Fast Iterated Sums (FIS) layer, a novel tensor-to-tensor primitive with linear time and space complexity relative to the input size. Theoretically, our framework bridges deep learning and algorithmic combinatorics: it leverages “corner tree” structures from permutation pattern counting to efficiently compute 2D iterated sums. This formulation admits dual interpretations as both a higher-order state-space model (SSM) and a multiparameter extension of the Signature Transform. Practically, the FIS layer serves as a drop-in replacement for standard layers in vision backbones. We evaluate its performance on image classification and anomaly detection. When replacing layers in a smaller ResNet, the FIS-based model achieves accuracy of a larger ResNet baseline while reducing both trainable parameters and multiply-add operations. When replacing layers in ConvNeXt tiny, the FIS-based model saves around 2% of parameters, has around 8% shorter time per epoch and improves accuracy by around 0.6% on CIFAR-10 and around 2% on CIFAR-100. Furthermore, on the texture subset of MVTec AD, it attains an average AUROC of 97.3%. The code is available at https://github.com/diehlj/fast-iterated-sums .