How turbovec Uses the Lloyd-Max Algorithm for Scalar Quantization

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 under the How it works section.

Lloyd-Max Codebook Generation in turbovec/src/codebook.rs

The core implementation lives in 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 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 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 lazily triggers Lloyd-Max codebook generation on the first call to add(). Subsequent adds reuse the same boundaries and centroids.

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.

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.

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 iteratively refines boundaries and centroids using adaptive Simpson integration until convergence.
• 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 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, 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.

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