# Optimal Quantization for Matrix Multiplication

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 78 references that are in the map.
- First posted on arXiv 17 Oct 2024.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs](https://mlsanity.com/paper/2404.00456/) (2024)
- [ZeroQuant: Efficient and Affordable Post-Training Quantization for Large-Scale Transformers](https://mlsanity.com/paper/2206.01861/) (2022)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [QuIP: 2-Bit Quantization of Large Language Models With Guarantees](https://mlsanity.com/paper/2307.13304/) (2023)
- [QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks](https://mlsanity.com/paper/2402.04396/) (2024)
- [The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits](https://mlsanity.com/paper/2402.17764/) (2024)
- [Dynamic Network Surgery for Efficient DNNs](https://mlsanity.com/paper/1608.04493/) (2016)
- [Compressing Deep Convolutional Networks using Vector Quantization](https://mlsanity.com/paper/1412.6115/) (2014)
- [QTIP: Quantization with Trellises and Incoherence Processing](https://mlsanity.com/paper/2406.11235/) (2024)
- [And the Bit Goes Down: Revisiting the Quantization of Neural Networks](https://mlsanity.com/paper/1907.05686/) (2019)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Multiplying Matrices Without Multiplying](https://mlsanity.com/paper/2106.10860/) (2021)
- [Quantization based Fast Inner Product Search](https://mlsanity.com/paper/1509.01469/) (2015)
- [Faster Matrix Multiplication via Asymmetric Hashing](https://mlsanity.com/paper/2210.10173/) (2022)
- [Gaussian Approximation of Quantization Error for Estimation from Compressed Data](https://mlsanity.com/paper/2001.03243/) (2020)

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

- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [High-Rate Quantized Matrix Multiplication I](https://mlsanity.com/paper/2601.17187/) (2026)
- [Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven](https://mlsanity.com/paper/2605.06014/) (2026)
- [High-Rate Quantized Matrix Multiplication II](https://mlsanity.com/paper/2605.13768/) (2026)
- [Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition](https://mlsanity.com/paper/2603.19559/) (2026)
- [Contraction-Gauge Preconditioning for Quantized Matrix Multiplication](https://mlsanity.com/paper/2607.18745/) (2026)
- [Price of metric universality in vector quantization is at most 0.11 bit](https://mlsanity.com/paper/2602.05790/) (2026)
- [A Nuclear-Norm Lower Bound for Dithered Scalar Quantization of Matrix Products](https://mlsanity.com/paper/2609.05641/) (2026)
- [Fast Matrix Multiplication in fp8: Certified Coefficient Optimization and Measured Error](https://mlsanity.com/paper/2609.26077/) (2026)
- [Understanding Behavior Cloning with Action Quantization](https://mlsanity.com/paper/2603.20538/) (2026)
- [Transforms for LLM Quantization: The Great Inversion and Format Co-Design](https://mlsanity.com/paper/2608.25188/) (2026)
- [Product-Aware Deterministic Rounding for Quantized Matrix Multiplication](https://mlsanity.com/paper/2609.31641/) (2026)
- [When Does Compensating Inherited Quantization Error Help? Mean-Square Guarantees for Layer-Wise Quantization and Their Limits](https://mlsanity.com/paper/2610.16020/) (2026)
- [Fast Quantized Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2610.16289/) (2026)

## Abstract (arXiv)

Recent work in machine learning community proposed multiple methods for performing lossy compression (quantization) of large matrices. This quantization is important for accelerating matrix multiplication (main component of large language models), which is often bottlenecked by the speed of loading these matrices from memory. Unlike classical vector quantization and rate-distortion theory, the goal of these new compression algorithms is to be able to approximate not the matrices themselves, but their matrix product. Specifically, given a pair of real matrices A,B an encoder (compressor) is applied to each of them independently producing descriptions with R bits per entry. These representations subsequently are used by the decoder to estimate matrix product A^top B. In this work, we provide a non-asymptotic lower bound on the mean squared error of this approximation (as a function of rate R) for the case of matrices A,B with iid Gaussian entries. Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matrices A, B in terms of only Frobenius norms |barA|F, |barB|F and |barA^top barB|F, where barA,barB are versions of A,B with zero-centered columns, respectively. For iid Gaussian matrices our quantizer achieves the lower bound and is, thus, asymptotically optimal. A practical low-complexity version of our quantizer achieves performance quite close to optimal. In addition, we derive rate-distortion function for matrix multiplication of iid Gaussian matrices, which exhibits an interesting phase-transition at R≈ 0.906 bit/entry, showing necessity of Johnson-Lindestrauss dimensionality reduction (sketching) in the low-rate regime.