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:
- Encode: Transform the input tiles into a new "basis" using a learnable linear transformation.
- 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.
- 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.
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