🔢 mathematics

High-Rate Quantized Matrix Multiplication I

This paper investigates the fundamental information-theoretic tradeoff between quantization rate and distortion for generic matrix multiplication without prior statistical calibration, while also analyzing and deriving heuristic approximations for popular quantization schemes like absmax INT and floating-point.

Original authors: Or Ordentlich, Yury Polyanskiy

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Or Ordentlich, Yury Polyanskiy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a massive, high-definition movie across a tiny, narrow tunnel. The movie represents the complex math inside a Large Language Model (like the ones powering chatbots), and the tunnel represents the computer's memory and processing speed. If you try to push the full, uncompressed movie through, the tunnel clogs up, and the computer slows to a crawl.

To fix this, engineers use quantization. Think of this as taking that high-definition movie and compressing it into a low-resolution, pixelated version. It's not perfect, but it fits through the tunnel much faster, and the picture is still recognizable enough to watch.

This paper, written by Or Ordentlich and Yury Polyanskiy, is like a theoretical physics report on compression. Instead of just testing different compression tools to see which one works best in practice, the authors ask: "What is the absolute, mathematical limit of how well we can compress this data before it becomes garbage?"

Here is a breakdown of their findings using simple analogies:

1. The Two Types of "Compression"

The authors point out a confusion between how mathematicians and engineers talk about "rate" (how much data we keep).

The Mathematician's View: Imagine taking a whole block of pixels and compressing them all together into a single, clever code. This is the most efficient way, but it's incredibly hard to do in real-time.
The Engineer's View: Imagine looking at each pixel individually and saying, "You're a bit too bright, so I'll just round you down to the nearest standard color." This is how current AI chips work (using formats like INT8 or FP8). It's fast and easy, but the authors argue it's not as efficient as the theoretical limit.

2. The "High-Rate" Assumption

The paper focuses on a scenario where the compression isn't too extreme (like turning a movie into a stick figure). They assume we are keeping enough detail that the "noise" (the errors introduced by rounding) is small.

The Analogy: Imagine trying to measure a table with a ruler. If your ruler has tiny, precise markings (high rate), the error is just a tiny fraction of a millimeter. If you use a ruler with huge gaps (low rate), the error is massive. The authors assume we are using the precise ruler, which lets them use simple math to predict the errors.

3. The "Perfect" vs. The "Real"

The authors calculated the Fundamental Limit: the best possible accuracy you could ever hope to achieve if you had a magic compression tool that could look at the whole picture at once.

The Result: They found that for a perfect system, the error drops very quickly as you add more bits (more detail).
The Reality Check: They then looked at popular tools used in AI today, like INT (integer) and FP (floating-point) formats.
- The Problem: These tools often use a "one-size-fits-all" scaling method (like using the same ruler for a giant elephant and a tiny mouse). If the data has a few huge numbers and many small ones, the ruler gets stretched to fit the big ones, making the small ones look like blurry dots.
- The Fix: They found that if you rotate the data (like spinning a picture so the jagged edges align with the grid) before compressing it, the "blur" becomes much more uniform and predictable. This is a technique called random rotation.

4. The "Shrinkage" Surprise

One interesting finding is about "shrinking."

The Analogy: If you compress a photo and then try to un-compress it, the best guess for the original isn't just the un-compressed photo; it's actually a slightly "shrunk" version of it.
The Paper's Take: While this "shrinking" effect exists, the authors found that in the high-quality (high-rate) world they are studying, the benefit is so tiny that we can safely ignore it to keep the math simple.

5. Testing the Tools

The authors tested their theories against real-world data from a popular AI model (Llama 3).

INT vs. FP: They found that for standard integer formats (INT), rotating the data first is crucial. Without rotation, the error can be huge. With rotation, the error drops to near the theoretical limit.
Floating Point (FP): Surprisingly, for floating-point formats, rotating the data is actually harmful. The authors explain that the way these formats handle numbers naturally handles the "jagged edges" better, so spinning the data just messes things up.
NestQuant: They looked at a new, fancy method called NestQuant (which uses complex geometric shapes called "lattices" instead of simple cubes). They found it performs significantly better than the standard tools, getting closer to that "magic" theoretical limit.

The Bottom Line

This paper provides a blueprint for the future of AI compression. It tells us:

There is a hard mathematical limit to how well we can compress AI math.
Current tools (like INT8 and FP8) are good, but they often leave "bits of accuracy" on the table because they don't account for the shape of the data.
Rotation is a powerful trick, but it's a double-edged sword: it helps integer math but hurts floating-point math.
Newer, more complex methods (like NestQuant) are starting to bridge the gap between what we do and what is mathematically possible.

In short, the paper says: "We know the speed limit of the highway. Current cars are driving fast, but if we tweak the engine (using rotation or better lattices), we can get much closer to that speed limit without crashing."

Technical Summary: High-Rate Quantized Matrix Multiplication I

Problem Statement
This paper addresses the problem of quantized matrix multiplication (MatMul), a critical operation for the efficient deployment of Large Language Models (LLMs). The authors focus on a "Generic MatMul" setting where both matrices (weights and activations) must be quantized without specific a priori statistical knowledge (calibration) of the factors. The core challenge is to characterize the fundamental information-theoretic tradeoff between the quantization rate (bits per entry, $R$ ) and the resulting distortion (error) in the matrix product. The paper distinguishes between the information-theoretic definition of "rate" (where a vector of $N$ entries is encoded into $NR$ bits globally) and the practical definition used in AI (where each entry is quantized individually or in small groups).

Methodology and Theoretical Framework
The analysis relies on high-rate quantization theory, assuming the quantization noise is significantly weaker than the signal ( $R$ is sufficiently large). Under this assumption, quantization error is modeled as additive, independent, and uniformly distributed noise. The authors also neglect "linear shrinkage" effects, which are of order $O(2^{-4R})$ , to simplify the distortion analysis.

The paper formalizes the problem using a rate- $R$ quantization scheme involving encoders and a decoder, potentially utilizing shared randomness (public coins). It evaluates performance in two settings:

Worst-case: Matrices $A$ and $B$ have bounded $\ell_2$ norms, but no distributional assumptions.
Average-case (Gaussian): Entries of $A$ and $B$ are independent and identically distributed (i.i.d.) Gaussian.

Key Contributions and Results

Fundamental Limits for Generic MatMul:
The paper establishes that for generic matrices, the smallest expected distortion for the $(i,j)$ -th entry of the product $A^\top B$ is characterized by:
$D^*_{ij} = \frac{\|a_i\|^2 \cdot \|b_j\|^2}{n} \cdot 2 \cdot 2^{-2R}$
where $a_i$ and $b_j$ are the columns of $A$ and $B$ , and $n$ is the dimension. This bound is shown to be tight for Gaussian inputs. The authors demonstrate that non-randomized schemes or simple sketching approaches generally suffer from distortion scaling linearly with dimension $n$ ( $\Omega(n)$ ), whereas schemes combining randomization (random rotation/dither) with lattice quantization can achieve the fundamental limit.
Analysis of Popular Quantization Schemes:
The authors derive accurate heuristic approximations for the distortion of widely used schemes, expressing them in the form $K(i,j) \cdot 2 \cdot 2^{-2R_{\text{eff}}}$ , where $R_{\text{eff}}$ is the "effective rate" in bits.
- INT Multipliers (absmax): For standard INT $M$ with absmax scaling, the effective rate is $R_{\text{eff}} \approx M - \frac{1}{2}\log_2(\frac{2 \ln n}{3})$ . This indicates a significant rate penalty due to the $\ell_\infty$ scaling factor. The paper shows that applying a random rotation (e.g., Hadamard transform) prior to quantization reduces the distortion factor $\Delta_{\text{INT}}$ to concentrate around $2 \ln n$ , making rotation crucial for INT quantization.
- Floating-Point (FP) Multipliers: Using an "Infinite-Exponent Independent Noise" (IEIN) model, the authors derive that for FP with $M$ mantissa bits, $R_{\text{eff}} \approx M + 2.23$ bits. Unlike INT, the analysis suggests that for FP quantization, random rotation is often unnecessary and can even be harmful, as the distortion factor $\Delta_{\text{FP}}$ tends to be smaller than 1 without rotation for certain distributions.
- Multi-scaled Formats (NVFP4/NVINT4): The paper analyzes 4-bit formats (NVFP4, NVINT4) which use multi-scaling (group scaling). It argues that NVFP4 effectively behaves like a 1-mantissa-bit scheme with an effective rate of roughly 3.24 bits, while NVINT4 suffers from the same scaling penalties as standard INT unless carefully managed.
- NestQuant: The authors review the NestQuant framework, which utilizes nested lattice codes (specifically the $E_8$ lattice) and a bank of scales. They note that NestQuant significantly outperforms INT and FP schemes at similar bit-rates, achieving approximately 0.6 additional bits of accuracy.
Empirical Validation:
Using activation matrices from the 15th layer of Llama3-8B, the paper validates the theoretical approximations.
- The derived formulas for INT and FP distortion match empirical Root Mean Squared Error (RMSE) measurements remarkably well.
- Histograms confirm that random rotation drastically reduces the variance of the distortion factor for INT quantization but has a different, often negative, impact on FP quantization.
- Comparisons at $R=4.5$ bits show NestQuant significantly outperforming both NVINT4 and NVFP4.

Significance and Claims
The paper claims to provide the first information-theoretic benchmarks for generic quantized MatMul where no calibration statistics are available. Its primary significance lies in quantifying the gap between fundamental limits and restrictive practical approaches (like standard INT/FP formats).

The authors emphasize that while high-rate assumptions may not hold for very low bit-rates ( $R < 2$ ), they provide sufficiently accurate expressions for the rates typically used in LLMs (e.g., 4 to 8 bits). The work serves as a theoretical foundation to evaluate current quantization strategies, highlighting that:

Random rotation is a critical component for INT quantization to approach fundamental limits.
FP quantization behaves differently, where rotation may not be beneficial.
There is a substantial performance gap between standard schemes and the theoretical optimum, which can be narrowed by advanced techniques like NestQuant.

The paper concludes by noting that Part II of this work will address the weight-only quantization setup where second-order statistics of activations are available.