TurboQuant-MSE is the MSE-optimized variant. It randomly rotates the input vector so each coordinate follows a known distribution, then applies an optimal scalar quantizer independently to each coordinate. It achieves $D_{\text{mse}} \leq \frac{\sqrt{3}\pi}{2} \cdot \frac{1}{4^b}$ — within a factor of $\approx 2.7$ of the information-theoretic limit.

Algorithm 1: TurboQuant-MSE

Setup (one-time, shared across all vectors)

Input: dimension $d$, bit-width $b$

1. Generate random rotation matrix $\boldsymbol{\Pi} \in \mathbb{R}^{d \times d}$ — a uniformly random orthogonal matrix. In practice, generate a $d \times d$ matrix with i.i.d. $\mathcal{N}(0,1)$ entries and compute its QR decomposition; $\boldsymbol{\Pi}$ is the $Q$ factor.

2. Construct codebook: find centroids $c_1, c_2, \ldots, c_{2^b} \in [-1,1]$ that minimize the MSE cost $\mathcal{C}(f_X, b)$ via the Lloyd-Max algorithm.

Quantization: QUANT($\boldsymbol{x}$)

Input: vector $\boldsymbol{x} \in \mathbb{S}^{d-1}$

3. Compute rotated vector: $\boldsymbol{y} \leftarrow \boldsymbol{\Pi} \cdot \boldsymbol{x}$

4. For every coordinate $j \in [d]$: find the nearest centroid index

5. Output: $\text{idx} \in [2^b]^d$ — a vector of $d$ indices, each a $b$-bit integer. Storage: $b \cdot d$ bits total.

Dequantization: DEQUANT($\text{idx}$)

6. For every $j \in [d]$: look up the centroid $\tilde{\boldsymbol{y}}_j \leftarrow c_{\text{idx}_j}$

7. Rotate back to original basis: $\tilde{\boldsymbol{x}} \leftarrow \boldsymbol{\Pi}^\top \cdot \tilde{\boldsymbol{y}}$

8. Output: $\tilde{\boldsymbol{x}} \in \mathbb{R}^d$ — the reconstructed vector

End-to-End Pipeline

Step through the full quantization pipeline: generate a random vector, rotate it, quantize each coordinate to the nearest Lloyd-Max centroid, then rotate back. Compare the reconstruction with the original.

Optimal Scalar Quantization (Lloyd-Max)

The core engine of TurboQuant: given the known coordinate distribution $f_X$, partition $[-1,1]$ into $2^b$ intervals and assign a representative centroid $c_i$ to each. Each coordinate is replaced by the centroid of the interval it falls in.

The MSE cost to minimize:

This is exactly a 1-dimensional k-means problem with a continuous distribution instead of discrete points. The intervals are defined by midpoints between consecutive centroids — the Voronoi tessellation in 1-D.

The Lloyd-Max algorithm finds the optimal centroids via alternating optimization:

1. Initialize centroids uniformly in $[-1,1]$
2. Repeat until convergence:
   • Boundary step: compute boundaries $b_i = (c_i + c_{i+1})/2$
   • Centroid step: update each centroid to the conditional expectation: $c_i \leftarrow \frac{\int_{b_{i-1}}^{b_i} x \cdot f_X(x)\, dx}{\int_{b_{i-1}}^{b_i} f_X(x)\, dx}$

Adjust the bit-width and dimension to see how the quantization bins adapt to the distribution shape.

Precomputed Optimal Values

The codebook is universal: the same centroids work for any input vector, because the random rotation ensures all coordinates follow the same distribution.

Theorem 1 (Performance Guarantee)

For any bit-width $b \geq 1$ and any vector $\boldsymbol{x} \in \mathbb{S}^{d-1}$:

Note: The $\frac{\sqrt{3}\pi}{2} \cdot \frac{1}{4^b}$ formula is an asymptotic upper bound from the Panter-Dite formula (tight for large $b$). For small $b$, the exact Lloyd-Max values above are tighter.

Why TurboQuant-MSE is Biased for Inner Products

At $b = 1$, the optimal centroids are $\left\{\pm\sqrt{2/(\pi d)}\right\}$. The quantization effectively computes $\text{sign}(\boldsymbol{y}_j)$, giving:

There’s a multiplicative bias of $2/\pi \approx 0.637$. This bias diminishes with increasing $b$ but is significant at low bit-widths. This motivates TurboQuant-Prod (Algorithm 2).

Computational Complexity

• QUANT: $O(d^2)$ for the rotation + $O(d \cdot 2^b)$ for nearest-centroid search
• DEQUANT: $O(d)$ centroid lookup + $O(d^2)$ matrix-vector multiply
• All operations are dense matrix multiplications — fully vectorizable on GPU