Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs

Nir Ailon, Akhiad Bercovich, Omri WeinsteinarXiv 2025 · DOI · arXiv

Researchers from NVIDIA and Hebrew University have introduced Strassen-Tile (STL), a new mathematical operator designed as a faster, more expressive alternative to standard Matrix Multiplication (MatMul). Unlike traditional compression methods that sacrifice model capacity for speed, STL reduces computational work (FLOPs) while simultaneously increasing the number of trainable parameters, leading to improved accuracy and faster inference on modern GPUs.

The "Hardware Lottery" Problem

Modern deep learning is built on massive matrix multiplications, which account for 80-90% of energy consumption and latency. While "fast" matrix multiplication algorithms like Strassen’s have existed for decades, they are rarely used in practice because they are not optimized for GPU hardware.

This is known as the "Hardware Lottery": we use MatMuls not because they are mathematically superior, but because our hardware (GPUs and Tensor Cores) is specifically optimized for them. Most attempts to speed up models involve pruning or low-rank decomposition, which reduces parameter count and often hurts accuracy. The authors of this paper ask: Can we create an operator that is faster than MatMul on a GPU without decreasing—and perhaps even increasing—the number of trainable parameters?

The Strassen-Tile (STL) Operator

The proposed STL operator breaks large matrices into small "tiles" (e.g., 4x4 blocks) and applies a three-step process:

  1. Encode: Transform the input tiles into a new "basis" using a learnable linear transformation.
  2. Element-wise Product: Multiply these encoded tiles. Crucially, this step is implemented as a series of standard MatMuls, allowing the operator to leverage existing GPU Tensor Core optimizations.
  3. Decode: Transform the result back into the original space.

By applying these transformations locally on tiles, the overhead of changing the base is amortized across the entire operation. Furthermore, the researchers introduce "Fake Encoding": instead of storing standard weights, they store weights directly in the higher-dimensional encoded space. This increases the model's expressivity (parameter count) by a factor of $r/t^2$ (where $r$ is the rank and $t$ is the tile size).

Key Results and Performance

The researchers evaluated STL using synthetic data and the ImageNet-1K dataset, training a T2T-ViT-7 vision transformer from scratch.

  • FLOP Reduction: STL can approximate 4x4 MatMuls while reducing the required FLOPs by a factor of 2.66x.
  • Accuracy Boost: On ImageNet-1K, replacing standard MatMuls with STL improved accuracy. The baseline model achieved 71.5% accuracy, while the STL version (with a tensor rank of 49) reached 75.8%.
  • Wall-Clock Speedup: Even using non-optimized PyTorch code, the authors observed real-world speedups on NVIDIA H100 GPUs in compute-bound scenarios.
Figure 1: Speedup vs. Tensor Rank r across different matrix sizes (n).

As shown in the figure above, the speedup increases as the tensor rank $r$ decreases. For larger matrix sizes (e.g., $n=16384$), the operator maintains a significant performance advantage over standard MatMul even at higher ranks.

Limitations and Future Work

While promising, STL introduces a trade-off: it saves computation time but increases memory overhead due to the higher parameter count. Additionally, training these layers from scratch is more complex than standard layers because the optimization problem is highly non-convex.

Future work will focus on writing custom CUDA kernels to unlock greater performance gains and scaling STL to much larger models, such as Large Language Models (LLMs), where the MatMul bottleneck is most severe.

Summary updated

Abstract

Modern AI relies on huge matrix multiplications (MatMuls), whose computation poses a scalability problem for inference and training. We propose an alternative, GPU native bilinear operator to MatMuls in neural networks, which offers a three-way tradeoff between: speed, accuracy and parameter count. In particular, this operator requires substantially fewer FLOPs to evaluate ($\ll n^3$), yet increases the parameter count compared to MatMul ($\gg n^2$). We call this operator Strassen-Tile (STL). The key idea behind STL is a local learnable change-of-basis, applied on tiles of the weight and activation matrices, followed by an element-wise product between the tiles, implemented simultaneously via MatMul. The key technical question we study is how to optimize the change-of-basis of a given layer, which is a highly non-convex problem. We show that theory-backed initializations (inspired by fast matrix and polynomial multiplication) lead to substantially better accuracy than random SGD initialization. This phenomenon motivates further algorithmic study of STL optimization in DNNs. Our experiments demonstrate that STL can approximate 4x4 MatMul of tiles while reducing FLOPs by a factor of 2.66, and can improve Imagenet-1K accuracy of SoTA T2T-ViT-7 (4.3M parameters) while lowering FLOPs. Even with non-CUDA optimized PyTorch code, STL achieves wall-clock speedups in the compute-bound regime. These results, together with its theoretical grounds, suggest STL as a promising building block for scalable and cost-efficient AI.
BibTeX
@misc{ailon2025changing,
  author = {Nir Ailon and Akhiad Bercovich and Omri Weinstein},
  title = {{Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs}},
  year = {2025},
  eprint = {2503.12211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.12211},
}
Figure