Lloyd-Max Algorithm for Optimal Scalar Quantization Buckets in Turbovec

Turbovec implements the Lloyd-Max algorithm in turbovec/src/codebook.rs to pre-compute optimal quantization boundaries and centroids for Beta-distributed rotated embeddings, minimizing mean-squared error through iterative centroid updates and adaptive Simpson integration.

The turbovec library compresses high-dimensional vector embeddings by quantizing each coordinate after an orthogonal rotation. Because these rotated coordinates follow a Beta distribution, the crate applies the Lloyd-Max algorithm for optimal scalar quantization buckets to determine the cut points and representative values that minimize reconstruction error.

Why Scalar Quantization Uses the Beta Distribution

When turbovec rotates a unit-vector embedding, each resulting coordinate follows a symmetric Beta distribution with shape parameter a = (dim - 1) / 2 on the interval [-1, 1]. Unlike uniform quantization, optimal compression requires buckets that account for this specific probability density. The Lloyd-Max algorithm generates these buckets by treating the quantization as a mean-squared error (MSE) minimization problem where the source distribution is known analytically.

Lloyd-Max Implementation in turbovec/src/codebook.rs

The core logic resides in turbovec/src/codebook.rs, specifically within the lloyd_max function. This implementation follows the classic iterative expectation-maximization approach adapted for the Beta distribution’s support on [-1, 1].

Parameter Setup and Initialization

The algorithm begins by calculating the Beta distribution’s standard deviation analytically. It then initializes n_levels = 2^bits centroids uniformly across the range ±3 × σ, where bits is the target bit-width (typically 2–4 bits). This initialization ensures the starting points cover the high-probability mass of the distribution while remaining symmetric around zero.

Iterative Refinement Using Adaptive Simpson Integration

Each iteration of the Lloyd-Max loop performs three critical operations:

1. Boundary Calculation – New boundaries are set to the midpoints between consecutive centroids, with the outermost boundaries fixed at -1 and +1.

2. Centroid Recomputation – For each quantization level i, the new centroid becomes the conditional mean of the distribution within its cell:

   $$c_i = \frac{\int_{l_i}^{u_i} x , p(x),dx}{\Pr[l_i \le X \le u_i]}$$

   The integration maps the interval from [-1, 1] to the Beta’s native support [0, 1] and evaluates using adaptive_simpson with a tolerance of 1e-14.

3. Convergence Check – The algorithm computes the maximum absolute change across all centroids. If the change falls below tol = 1e-12 or reaches 200 iterations, the loop terminates.

Result Construction and Caching

Upon convergence, the function returns the final boundaries (as midpoints between centroids) and the centroids themselves as Vec<f32>. Turbovec caches these results per (bits, dim) pair, ensuring the expensive numerical integration runs only once during the prepare() phase.

Generating Quantization Codebooks in Practice

The public codebook function wraps this implementation, allowing direct computation of optimal buckets for any supported dimension and bit-width:

use turbovec::codebook::codebook;

// Generate 2-bit quantizer for 1536-dimensional embeddings
let (boundaries, centroids) = codebook(2, 1536);

// boundaries: Vec<f32> with 3 cut points dividing [-1, 1] into 4 intervals
// centroids: Vec<f32> with 4 optimal representative values
println!("Boundaries: {:?}", boundaries);
println!("Centroids: {:?}", centroids);

The returned vectors feed directly into the encoding pipeline in turbovec/src/encode.rs, where raw coordinates map to bucket indices using these pre-computed boundaries.

Summary

• The Lloyd-Max algorithm in turbovec minimizes MSE for scalar quantization by iteratively updating centroids and boundaries.
• Implementation in turbovec/src/codebook.rs uses adaptive Simpson integration (adaptive_simpson) to compute conditional means of the Beta distribution.
• Initialization spreads centroids across ±3σ of the analytical Beta standard deviation.
• The algorithm converges when centroid changes drop below 1e-12 or hit 200 iterations.
• Results are cached per (bits, dim) pair to avoid redundant computation.

Frequently Asked Questions

What distribution assumption enables the Lloyd-Max optimization in turbovec?

Turbovec assumes coordinates follow a Beta distribution with shape parameter (dim-1)/2 after orthogonal rotation. This assumption allows the Lloyd-Max algorithm to compute optimal centroids as conditional means of the known distribution rather than estimating from data.

How does turbovec handle the numerical integration required by the Lloyd-Max algorithm?

The adaptive_simpson function in turbovec/src/codebook.rs performs high-precision numerical integration with a tolerance of 1e-14. This adaptive quadrature method accurately evaluates the Beta PDF integrals needed to compute each centroid’s conditional mean during iteration.

Why does the initialization use ±3 standard deviations?

Centroids initialize uniformly across ±3 × σ because this range captures approximately 99.7% of the probability mass for the Beta distribution on [-1, 1]. This provides a data-informed starting point that accelerates convergence toward the globally optimal quantization buckets.

Where does turbovec store the computed Lloyd-Max codebooks?

The library caches computed boundaries and centroids internally during the prepare() API call, keyed by the bit-width and dimension tuple. This caching mechanism ensures the numerical iteration runs once per configuration, with subsequent encoding operations in turbovec/src/encode.rs reusing the pre-computed values.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}