liveBook · Manning

Lloyd-Max algorithm

As explained in Quantization and Fast Inference

The Lloyd-Max algorithm iteratively assigns values to their nearest representative and updates representatives to minimize expected squared quantization error for a probability distribution.

Lloyd-Max builds a nonuniform scalar codebook by assigning regions of a probability distribution to their nearest representatives and updating the representatives to minimize expected squared error. In TurboQuant, it quantizes rotated vector coordinates using a precomputed codebook reused across vectors. section 7.5

Three-bit codebook

For 3-bit quantization, use eight representative values spaced unevenly across [−1, 1], packed more densely near zero to match the Beta distribution. Store each coordinate as the index of its nearest representative. section 7.5

How Quantization and Fast Inference covers it

How deep it goes
Explains representative initialization, nearest-region assignment, and updates that minimize expected squared error.
Examples
Uses an eight-entry, 3-bit codebook with representatives concentrated near zero for a Beta distribution.
What you can do after
Build a distribution-matched codebook by initializing representatives, assigning regions, and updating representatives to reduce expected squared error.
How it connects
Connects one-dimensional k-means with scalar quantization and probability distributions.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Quantization and Fast Inference. The section links point to the parts of the book it draws on.