# How turbovec Uses the Lloyd-Max Algorithm for Scalar Quantization

> Discover how turbovec leverages the Lloyd-Max algorithm for scalar quantization. Achieve deterministic vector compression without training by optimizing boundaries and centroids.

- Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec)
- Tags: deep-dive
- Published: 2026-07-18

---

**The Lloyd-Max algorithm powers scalar quantization in turbovec by iteratively computing optimal boundaries and centroids for a Beta-distributed coordinate space, enabling deterministic vector compression without a training phase.**

The `turbovec` library by RyanCodrai compresses high-dimensional vectors for fast nearest-neighbor search using a deterministic pipeline centered on the **Lloyd-Max algorithm for scalar quantization**. By first applying a random orthogonal rotation, the library transforms each coordinate into a known Beta distribution, then pre-computes an optimal scalar quantizer once and reuses it for every vector. This eliminates the need for dataset-specific training while delivering near-optimal distortion within 2.7× of the Shannon limit.

## How Coordinate Distributions Enable Training-Free Quantization

### Random Rotation and Beta Distribution Modeling

After a random orthogonal rotation, each coordinate of a unit-length vector on the hypersphere follows a Beta\(((d-1)/2, (d-1)/2)\) distribution on \([-1, 1]\), as detailed in the project's README. Because this distribution is deterministic and analytically known, turbovec can pre-compute quantization regions without sampling from the target dataset. The relevant math and pipeline overview are documented in [`README.md`](https://github.com/RyanCodrai/turbovec/blob/main/README.md) under the *How it works* section.

## Lloyd-Max Codebook Generation in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs)

The core implementation lives in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs), where the `codebook()` function runs a full Lloyd-Max iteration. The algorithm proceeds in four steps:

1. Initializes uniformly spaced centroids across the Beta distribution's support.
2. Builds decision boundaries as the mid-points between adjacent centroids.
3. Computes the conditional mean within each region using an adaptive Simpson integrator.
4. Updates centroids until the maximum change falls below a tolerance threshold.

The result is a pair of vectors—**boundaries** and **centroids**—that minimize the mean-squared quantization error for the target distribution. You can inspect the implementation directly in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs) from lines 1 through 86.

## Scalar Quantization and Vector Encoding

### Mapping Rotated Coordinates to Integer Codes

When a vector is added to an index, each rotated coordinate is snapped to the nearest centroid using the pre-computed boundaries from the Lloyd-Max codebook. The [`turbovec/src/encode.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs) module handles the rotation, per-coordinate scaling calibration (TQ+), and integer packing. The index stores the resulting integer codes—2-bit codes for 4 buckets or 4-bit codes for 16 buckets—drastically reducing storage overhead.

### Length Renormalization for Unbiased Search

Because scalar quantization systematically shrinks vector norms, turbovec stores a per-vector correction factor of \(||v|| / \langle u, \hat{x} \rangle\). This factor removes the bias during search with no extra runtime cost, ensuring that nearest-neighbor distances remain faithful to the original vectors.

## Fast Search Without Decompression

Queries are rotated once and scored directly against the integer codes via SIMD-optimized lookup tables. As implemented in RyanCodrai/turbovec, this means **no full decompression is required** at query time. The Lloyd-Max codebook is used only during encoding; at search time, the pre-computed centroids drive the distance computation through efficient table lookups.

## Practical Code Examples

### Python: Lazy Codebook Generation on First `add`

The Python `TurboQuantIndex` class in [`turbovec/python/turbovec/__init__.py`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/python/turbovec/__init__.py) lazily triggers Lloyd-Max codebook generation on the first call to `add()`. Subsequent adds reuse the same boundaries and centroids.

```python
from turbovec import TurboQuantIndex
import numpy as np

# 1536-dimensional vectors, 4-bit quantisation (16 buckets per coordinate)

index = TurboQuantIndex(dim=1536, bit_width=4)

# First add triggers Lloyd-Max codebook generation for this (dim, bits)

vectors = np.random.randn(1000, 1536).astype(np.float32)   # example embeddings

index.add(vectors)

# Subsequent adds reuse the same codebook – no retraining needed

more = np.random.randn(500, 1536).astype(np.float32)
index.add(more)

# Search – the query is rotated and scored against the integer codes

scores, ids = index.search(np.random.randn(1, 1536).astype(np.float32), k=10)
print(scores, ids)

```

### Rust: Direct Access to the Lloyd-Max Codebook

For custom pipelines, you can call the `codebook()` function directly from `turbovec::codebook`.

```rust
use turbovec::codebook::codebook;

fn main() {
    // 1536 dimensions, 4-bit → 16 levels
    let (boundaries, centroids) = codebook(4, 1536);
    println!("Boundaries (first 5): {:?}", &boundaries[..5]);
    println!("Centroids (first 5): {:?}", &centroids[..5]);
}

```

### CLI: Inspecting Generated Codebooks

You can dump the rotation matrix and Lloyd-Max boundaries for a given configuration using the provided example.

```bash
cargo run --example dump_state -- 1536 4

# Prints the rotation matrix and the Lloyd-Max boundaries/centroids for the chosen config

```

## Summary

- The **Lloyd-Max algorithm** in turbovec generates optimal scalar quantization codebooks against a deterministic Beta distribution, eliminating the need for dataset-specific training.
- The implementation in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs) iteratively refines boundaries and centroids using adaptive Simpson integration until convergence.
- [`turbovec/src/encode.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs) applies the codebook to rotated vectors, packing coordinates into 2-bit or 4-bit integer codes with per-vector length renormalization.
- Python users interact with this through `TurboQuantIndex`, which lazily builds the codebook on the first `add()` call; Rust users can call `codebook()` directly.
- Search operates directly on compressed integer codes via SIMD-optimized lookup tables, avoiding decompression overhead.

## Frequently Asked Questions

### What makes turbovec’s Lloyd-Max scalar quantization training-free?

Because turbovec assumes every rotated coordinate follows a known Beta\(((d-1)/2, (d-1)/2)\) distribution, the `codebook()` function in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs) can derive optimal boundaries and centroids analytically. There is no need to sample your dataset or run k-means; the same codebook works for any vectors of that dimension and bit width.

### How does turbovec correct for the norm shrinkage caused by scalar quantization?

The library stores a per-vector correction factor equal to \(||v|| / \langle u, \hat{x} \rangle\) alongside the quantized codes. During search, this factor removes the systematic bias introduced by snapping coordinates to centroids, preserving accurate nearest-neighbor rankings without extra runtime cost.

### Why does turbovec use the Lloyd-Max algorithm instead of uniform quantization?

Uniform quantization assumes a flat or uniform distribution, which wastes codebook entries on low-probability regions. The **Lloyd-Max algorithm** optimally places centroids according to the Beta distribution's density, minimizing mean-squared error. According to the turbovec benchmarks, this achieves distortion within 2.7× of the Shannon limit.

### Where is the Lloyd-Max iteration implemented in the turbovec codebase?

The full iterative solver is implemented in [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs), specifically in the `codebook()` function (lines 14–86). It initializes centroids, computes boundaries as mid-points, integrates conditional means via adaptive Simpson's method, and repeats until centroid movement falls below a tolerance threshold.