Multiplying Matrices Without Multiplying

Davis W. Blalock, John V. Guttag

Abstract

Multiplying matrices is among the most fundamental and compute-intensive operations in machine learning. Consequently, there has been significant work on efficiently approximating matrix multiplies. We introduce a learning-based algorithm for this task that greatly outperforms existing methods. Experiments using hundreds of matrices from diverse domains show that it often runs $100\times$ faster than exact matrix products and $10\times$ faster than current approximate methods. In the common case that one matrix is known ahead of time, our method also has the interesting property that it requires zero multiply-adds. These results suggest that a mixture of hashing, averaging, and byte shuffling—the core operations of our method—could be a more promising building block for machine learning than the sparsified, factorized, and/or scalar quantized matrix products that have recently been the focus of substantial research and hardware investment.

Introduction

Matrix multiplication is the primary computational bottleneck in modern machine learning, consuming the vast majority of compute cycles in neural networks and large-scale data mining. To mitigate this, researchers often turn to Approximate Matrix Multiplication (AMM). However, traditional AMM methods like sketching or PCA rely on linear projections, which are themselves matrix multiplications. For many real-world "tall" matrices, the cost of this preprocessing often outweighs the savings. We propose MADDNESS (Multiply-ADDitioN-lESS), a learning-based algorithm that circumvents this "preprocessing paradox" by replacing linear operations with lightning-fast non-linear hashing and table lookups.

Methods

MADDNESS moves away from linear projections toward a quantization-based approach designed to exploit modern CPU instructions.

  1. MADDNESS-Hash: Instead of slow K-means clustering, the algorithm uses balanced binary regression trees to find representative "prototypes." Encoding a vector involves simple bitwise comparisons, traversing a tree of depth 4 to find a bucket index. This allows encoding speeds exceeding 100GB/s on a single CPU thread.
  2. Optimized Prototypes: Rather than using simple means, MADDNESS employs ridge regression to find optimal prototype values that minimize the reconstruction error of the original matrix.
  3. Fast 8-bit Aggregation: The algorithm leverages SIMD averaging instructions (like vpavgb) to keep computations in 8-bit, doubling throughput compared to standard 16-bit upcasting while maintaining accuracy through closed-form bias correction.
The MADDNESS pipeline: Data vectors are encoded via hash trees into indices, which are then used to look up precomputed dot products with prototypes to form an approximate result.

Key Results

We evaluated MADDNESS across diverse domains, including deep learning classifiers (CIFAR-10/100), time series classification (UCR Archive), and image processing (Caltech101).

  • Speed-Accuracy Tradeoff: MADDNESS consistently outperforms rivals like Bolt and PCA sketching by roughly 10x in terms of the speed-accuracy tradeoff. On CIFAR-10, it achieves nearly the same accuracy as exact multiplication while providing massive speedups, whereas other AMM methods see accuracy collapse at similar speeds.
  • Hardware Efficiency: The algorithm is often 100x faster than exact BLAS multiplication. In scenarios where one matrix (e.g., model weights) is known ahead of time, MADDNESS requires zero floating-point multiply-adds at runtime, relying entirely on hashing and table lookups.
Classification accuracy vs. speedup over exact matrix multiply for CIFAR-10 and CIFAR-100. MADDNESS (Ours) maintains significantly higher accuracy at high speedup factors compared to baselines.

Limitations and Future Work

MADDNESS requires a representative training set for its hash trees, making it sensitive to significant data distribution shifts. Additionally, the current hash function is non-differentiable, which prevents direct integration into standard backpropagation-based training. Future work will focus on porting these hardware-optimized principles to GPUs and specialized AI accelerators, as well as exploiting spatial reuse patterns in convolutional layers.

Summary updated

Abstract

Multiplying matrices is among the most fundamental and compute-intensive operations in machine learning. Consequently, there has been significant work on efficiently approximating matrix multiplies. We introduce a learning-based algorithm for this task that greatly outperforms existing methods. Experiments using hundreds of matrices from diverse domains show that it often runs $100\times$ faster than exact matrix products and $10\times$ faster than current approximate methods. In the common case that one matrix is known ahead of time, our method also has the interesting property that it requires zero multiply-adds. These results suggest that a mixture of hashing, averaging, and byte shuffling$-$the core operations of our method$-$could be a more promising building block for machine learning than the sparsified, factorized, and/or scalar quantized matrix products that have recently been the focus of substantial research and hardware investment.
BibTeX
@inproceedings{blalock2021multiplying,
  author = {Davis W. Blalock and John V. Guttag},
  title = {{Multiplying Matrices Without Multiplying}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=mT1CG8sEIN},
}

Loading related content...

Figure