Multiplying Matrices Without Multiplying

Davis W. Blalock, John V. Guttag

TL;DR

MADDNESS (Multiply-ADDitioN-lESS) is a learning-based algorithm that performs approximate matrix multiplication by replacing expensive multiply-add operations with lightning-fast hashing and table lookups. It achieves up to a 10x better speed-accuracy tradeoff than existing approximation methods and can run 100x faster than exact matrix multiplication on standard CPUs.

What Problem Does This Paper Address?

Matrix multiplication is the computational backbone of modern machine learning, but it is incredibly resource-intensive. As models grow, the "compute tax" of multiplying large matrices becomes a bottleneck, especially for real-time inference on CPUs.

Existing approaches to Approximate Matrix Multiplication (AMM) typically rely on linear approximations (like sketching or PCA), which project matrices into lower dimensions. However, these methods still require performing an exact matrix multiply in that lower-dimensional space. Another approach, Product Quantization (PQ), uses table lookups to estimate products, but the "encoding" step (mapping data to the right table entry) is often so slow that it negates the speed gains unless the matrices are massive.

The authors seek a way to perform AMM that is fast even for "tall" matrices (common in neural network activations) and requires zero multiply-adds when one of the matrices is known in advance.

Methods: The MADDNESS Algorithm

The authors introduce MADDNESS, which departs from linear algebra-based approximations in three key ways:

The MADDNESS pipeline: Hashing data into indices, precomputing dot products into tables, and aggregating results via lookups.
  1. Hashing-based Encoding: Instead of using expensive K-means clustering to encode data (as in standard PQ), MADDNESS uses a family of balanced binary regression trees. These trees act as hash functions that map subvectors to indices using only simple comparisons. This process is extremely SIMD-friendly, allowing a single CPU thread to encode over 100GB of data per second.
  2. Global Prototype Optimization: Traditional methods learn "prototypes" (cluster centers) for each subspace independently. MADDNESS uses ridge regression to optimize all prototypes simultaneously, ensuring the encoded representation reconstructs the original matrix with minimal global error.
  3. Fast 8-bit Aggregation: To sum the values retrieved from lookup tables, MADDNESS avoids "upcasting" 8-bit integers to 16-bit (which usually halves throughput). Instead, it uses SIMD averaging instructions (like vpavgb on x86). While this introduces a small amount of "rounding" bias, the authors provide a closed-form solution to correct this bias, keeping the entire inner loop in high-speed 8-bit registers.

Datasets Evaluated

The authors evaluated MADDNESS across a diverse range of tasks:

  • Softmax Classification: Using activations and weights from VGG-like networks trained on CIFAR-10 and CIFAR-100.
  • Kernel-Based Classification: Testing on hundreds of diverse datasets from the UCR Time Series Archive.
  • Image Filtering: Applying Sobel and Gaussian filters to images from the Caltech101 dataset to test the algorithm's limits on very small matrices.

Key Insights and Ideas

  • Multiplication is Overkill: For many ML tasks, we don't need the exact floating-point result of a dot product. Hashing data into "buckets" of similar vectors is often sufficient to preserve classification accuracy.
  • The Hardware Mismatch: Modern CPUs and GPUs are packed with multipliers. However, MADDNESS shows that an algorithm relying on multiplexers (lookups) and shufflers can be significantly more efficient. This suggests that future AI hardware could be made simpler and lower-power by prioritizing lookups over MAC (Multiply-Accumulate) units.
  • Learning the Approximation: By treating AMM as a learning problem—optimizing the hash functions and prototypes on a training set—the algorithm can adapt to the specific distribution of the data, far outperforming "one-size-fits-all" sketching methods.

Key Results

MADDNESS consistently dominates the Pareto frontier of speed versus accuracy.

Comparison of speedup vs. accuracy on CIFAR datasets. MADDNESS (red) stays at high accuracy much longer than rivals as speed increases.
  • Speed: It is often 10x faster than the best existing AMM methods (like HashJL or SparsePCA) at the same level of accuracy. Compared to exact BLAS multiplication, it can reach 100x speedups.
  • Accuracy: On CIFAR-10 and CIFAR-100, MADDNESS achieves virtually the same accuracy as exact multiplication while being more than an order of magnitude faster.
  • Efficiency: The specialized aggregation function in MADDNESS is roughly twice as fast as its nearest vector quantization rivals because it avoids the overhead of bit-width upcasting.

Limitations and Future Work

  • Non-Differentiability: The use of discrete trees for hashing means the encoding function is not differentiable. This makes it difficult to "end-to-end" train a neural network with MADDNESS layers using standard backpropagation.
  • Matrix Shape Constraints: The method is specifically optimized for "tall" matrices (where one dimension is much larger than the others). Its benefits are less pronounced for square matrix multiplication.
  • Hardware Support: While MADDNESS is fast on current CPUs, it is actually "fighting" the hardware, which is designed for multiplication. The authors suggest that custom hardware (ASICs) designed for these operations could see even greater gains.
  • Convolutional Layers: The current work focuses on dense layers. Adapting MADDNESS to handle the weight reuse in convolutional layers is a noted direction for future research.

Summary updated

Abstract

Multiplying matrices is among the most fundamental and most computationally demanding operations in machine learning and scientific computing. Consequently, the task of efficiently approximating matrix products has received significant attention. 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 10x faster than alternatives at a given level of error, as well as 100x faster than exact matrix multiplication. 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},
}
Figure