# Lloyd-Max Algorithm for Optimal Scalar Quantization Buckets in Turbovec > Learn how the Lloyd-Max algorithm in turbovec optimizes scalar quantization buckets for Beta-distributed embeddings, minimizing errors with iterative centroid updates. - Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec) - Tags: deep-dive - Published: 2026-06-16 --- **Turbovec implements the Lloyd-Max algorithm in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`. 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: ```rust use turbovec::codebook::codebook; // Generate 2-bit quantizer for 1536-dimensional embeddings let (boundaries, centroids) = codebook(2, 1536); // boundaries: Vec with 3 cut points dividing [-1, 1] into 4 intervals // centroids: Vec 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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs) reusing the pre-computed values.