The Lloyd–Max quantizer: J-means in one dimension

After the random rotation, TurboQuant replaces each coordinate t by one of J = 2^b values c₁ < … < c_J and stores only its index (b bits). The best values, the ones minimizing E[(t − c_nearest)²], are found by Lloyd's algorithm, which is J-means (k-means) run on a 1-D distribution instead of a dataset:

Assign: each t goes to its nearest centroid. In 1-D every cell is an interval, and the boundaries are the midpoints (c_k + c_k+1)/2. Update: each centroid moves to the mean of its cell, c_k = ∫_cell t f(t) dt / ∫_cell f(t) dt; with a sample instead of a density this is the ordinary average of the points in the cell.

Because the rotation makes the density f_d known in advance (it depends only on d), TurboQuant runs this once, offline, and uses the same codebook for every coordinate of every vector: no training data, and nothing to update as new vectors arrive.

distribution d bits b

fit to start from

Density, cells and centroids

density f cells cell boundaries centroids before update

Mean squared error per coordinate

Codebook

Check against the paper

For large d, the converged codebooks for f_d, scaled by √d, are the optimal quantizers of a standard Gaussian, and d × (MSE per coordinate) is the expected ‖x − x̃‖² for a unit vector. The TurboQuant paper reports ≈ 0.36, 0.117, 0.03, 0.009 for b = 1, 2, 3, 4, within a factor of about 2.7 of the information-theoretic lower bound 4^−b.