# Multiplying Matrices Without Multiplying

arXiv: https://arxiv.org/abs/2106.10860 · HTML: https://mlsanity.com/paper/2106.10860/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 78 references that are in the map.
- First posted on arXiv 21 Jun 2021.

## Builds on (most cited first, 26 of 26)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [Compressing Neural Networks with the Hashing Trick](https://mlsanity.com/paper/1504.04788/) (2015)
- [SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks](https://mlsanity.com/paper/1708.04485/) (2017)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Learning to Hash for Indexing Big Data - A Survey](https://mlsanity.com/paper/1509.05472/) (2015)
- [Hashing for Similarity Search: A Survey](https://mlsanity.com/paper/1408.2927/) (2014)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [Stacked Quantizers for Compositional Vector Compression](https://mlsanity.com/paper/1411.2173/) (2014)
- [Scalable and Sustainable Deep Learning via Randomized Hashing](https://mlsanity.com/paper/1602.08194/) (2016)
- [Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD](https://mlsanity.com/paper/1812.09162/) (2018)
- [Accelerated Nearest Neighbor Search with Quick ADC](https://mlsanity.com/paper/1704.07355/) (2017)
- [Bolt: Accelerated Data Mining with Fast Vector Compression](https://mlsanity.com/paper/1706.10283/) (2017)
- [Approximate Matrix Multiplication with Application to Linear Embeddings](https://mlsanity.com/paper/1403.7683/) (2014)
- [Generalized residual vector quantization for large scale data](https://mlsanity.com/paper/1609.05345/) (2016)
- [All Sparse PCA Models Are Wrong, But Some Are Useful. Part I: Computation of Scores, Residuals and Explained Variance](https://mlsanity.com/paper/1907.03989/) (2019)
- [Fast Approximate Matrix Multiplication by Solving Linear Systems](https://mlsanity.com/paper/1408.4230/) (2014)
- [Improved Practical Matrix Sketching with Guarantees](https://mlsanity.com/paper/1501.06561/) (2015)
- [Speeding Up Neural Networks for Large Scale Classification using WTA Hashing](https://mlsanity.com/paper/1504.07488/) (2015)
- [Pairwise Quantization](https://mlsanity.com/paper/1606.01550/) (2016)
- [Co-Occuring Directions Sketching for Approximate Matrix Multiply](https://mlsanity.com/paper/1610.07686/) (2016)

## Built on by (most cited first, 30 of 30)

- [Extreme Compression of Large Language Models via Additive Quantization](https://mlsanity.com/paper/2401.06118/) (2024)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [T-MAC: CPU Renaissance via Table Lookup for Low-Bit LLM Deployment on Edge](https://mlsanity.com/paper/2407.00088/) (2024)
- [Compute-Efficient Deep Learning: Algorithmic Trends and Opportunities](https://mlsanity.com/paper/2210.06640/) (2022)
- [Bitnet.cpp: Efficient Edge Inference for Ternary LLMs](https://mlsanity.com/paper/2502.11880/) (2025)
- [LUT-NN: Empower Efficient Neural Network Inference with Centroid Learning and Table Lookup](https://mlsanity.com/paper/2302.03213/) (2023)
- [Channelformer: Attention based Neural Solution for Wireless Channel Estimation and Effective Online Training](https://mlsanity.com/paper/2302.04368/) (2023)
- [Optimal Quantization for Matrix Multiplication](https://mlsanity.com/paper/2410.13780/) (2024)
- [NoMAD-Attention: Efficient LLM Inference on CPUs Through Multiply-add-free Attention](https://mlsanity.com/paper/2403.01273/) (2024)
- [LUT-DLA: Lookup Table as Efficient Extreme Low-Bit Deep Learning Accelerator](https://mlsanity.com/paper/2501.10658/) (2025)
- [PECAN: A Product-Quantized Content Addressable Memory Network](https://mlsanity.com/paper/2208.13571/) (2022)
- [PQA: Exploring the Potential of Product Quantization in DNN Hardware Acceleration](https://mlsanity.com/paper/2305.18334/) (2023)
- [Memory-Efficient Backpropagation through Large Linear Layers](https://mlsanity.com/paper/2201.13195/) (2022)
- [Look-ups are not (yet) all you need for deep learning inference](https://mlsanity.com/paper/2207.05808/) (2022)
- [Accurate Compression of Text-to-Image Diffusion Models via Vector Quantization](https://mlsanity.com/paper/2409.00492/) (2024)
- [A Unified View of Long-Sequence Models towards Modeling Million-Scale Dependencies](https://mlsanity.com/paper/2302.06218/) (2023)
- [Pegasus: A Universal Framework for Scalable Deep Learning Inference on the Dataplane](https://mlsanity.com/paper/2506.05779/) (2025)
- [EVA: Accelerating LLM Decoding via an Efficient Vector Quantization Architecture](https://mlsanity.com/paper/2605.24144/) (2026)
- [ARM 4-BIT PQ: SIMD-based Acceleration for Approximate Nearest Neighbor Search on ARM](https://mlsanity.com/paper/2203.02505/) (2022)
- [Stella Nera: A Differentiable Maddness-Based Hardware Accelerator for Efficient Approximate Matrix Multiplication](https://mlsanity.com/paper/2311.10207/) (2023)
- [Attention, Distillation, and Tabularization: Towards Practical Neural Network-Based Prefetching](https://mlsanity.com/paper/2401.06362/) (2023)
- [TabConv: Low-Computation CNN Inference via Table Lookups](https://mlsanity.com/paper/2404.05872/) (2024)
- [Pushing the Envelope of LLM Inference with Ultra-Low-Bit Quantized Models](https://mlsanity.com/paper/2508.06753/) (2025)
- [AXELRAM: Quantize Once, Never Dequantize](https://mlsanity.com/paper/2604.02638/) (2026)
- [FASQ: Flexible Accelerated Subspace Quantization for Calibration-Free LLM Compression](https://mlsanity.com/paper/2605.04084/) (2026)
- [Breaking the 1.58-bit Barrier for Ternary LLMs](https://mlsanity.com/paper/2609.16338/) (2026)
- [Mitigating scalability challenges in LUT-based neural networks via pruning optimisations](https://mlsanity.com/paper/2407.02362/) (2024)
- [QoS-Nets: Adaptive Approximate Neural Network Inference](https://mlsanity.com/paper/2410.07762/) (2024)
- [Optimal Approximate Matrix Multiplication over Sliding Windows](https://mlsanity.com/paper/2502.18830/) (2025)
- [LeanStream: A Speculate-and-Refine Streaming Framework for Efficient on-Device LLM Inference](https://mlsanity.com/paper/2609.03079/) (2026)

## Abstract (arXiv)

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× faster than exact matrix products and 10× 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.