.png){kind=icon}
.png){kind=icon}
Return
Optimal Quantization for Matrix Multiplication
.png){kind=icon}
PRE
AI
DOI：10.1109/TIT.2025.3649596.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 inverted perpendicular 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 parallel to A & strns;parallel to F,parallel to B & strns;parallel to F and parallel to A & strns;inverted perpendicular B & strns;parallel to F , where A & strns;,B & strns; 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 approximate to 0.906 bit/entry, showing necessity of Johnson-Lindestrauss dimensionality reduction (sketching) in the low-rate regime.
Keywords:
Lattices
Decoding
Vectors
Lower bound
Zinc
Vector quantization
Rate-distortion
Large language models
Hardware
Distortion
quantization
rate-distortion
Journal
I
IF:
2.9
Papers:
317
Citations:
0