Lloyd-Max Scalar Quantization in Turbovec: Optimal Vector Compression Explained

Turbovec uses Lloyd-Max scalar quantization to compress high-dimensional vectors into 2–4 bit nibbles per dimension by computing a shared codebook of optimal reconstruction levels that minimizes mean-squared error.

Turbovec is an open-source vector search library that reduces storage costs through aggressive quantization. At its core lies Lloyd-Max scalar quantization, an iterative algorithm that derives optimal scalar levels for compressing floating-point dimensions into compact codes. This technique enables the storage of massive vector datasets using only a few bits per dimension while preserving retrieval accuracy.

How Lloyd-Max Scalar Quantization Works in Turbovec

Turbovec stores vectors in a quantized index where each dimension is mapped independently to a small set of quantization levels. The process treats each dimension as a scalar value and applies the Lloyd-Max algorithm to find the optimal set of levels for the data distribution.

The Iterative Optimization Process

The algorithm follows the classic Lloyd-Max procedure, which is essentially k-means clustering for one-dimensional data. According to the implementation in benchmarks/hillclimb/permute_dot_recall.py, the process involves four key steps:

1. Sample collection: Turbovec draws a representative subset of raw vectors using stratified sampling (e.g., raw[::max(1, N // 4000)]) to capture the data distribution without processing the entire dataset.

2. Initialization: Creates an initial uniform grid between the 0.1% and 99.9% quantiles of the samples to avoid outlier sensitivity.

3. Iterative refinement: For each of 60 iterations (by default), the algorithm:

   • Computes decision boundaries b = (c[1:] + c[:-1]) / 2 between current levels
   • Assigns each sample to the nearest level using np.searchsorted(b, samples)
   • Recomputes each level as the mean of assigned samples (samples[mask].mean())

4. Codebook generation: Returns the final sorted array c containing the optimal quantization levels.

This procedure minimizes the mean-squared reconstruction error between original floating-point values and their quantized representations.

Implementation Details and Source Code

The core Lloyd-Max implementation resides in the benchmark suite rather than the production Rust/C++ engine, exposing the logic for analysis and testing. The production engine uses an identical algorithm during index construction.

Key Functions and Files

In benchmarks/hillclimb/permute_dot_recall.py, the lloyd_max_levels function (lines 41-51) implements the algorithm:

def lloyd_max_levels(samples: np.ndarray, levels: int, iters: int = 60) -> np.ndarray:
    lo, hi = np.quantile(samples, [0.001, 0.999])
    c = np.linspace(lo, hi, levels)                     # initial uniform grid

    for _ in range(iters):
        b = (c[1:] + c[:-1]) / 2.0                      # decision boundaries

        idx = np.searchsorted(b, samples)               # assign each sample

        for j in range(levels):
            mask = idx == j
            if mask.any():
                c[j] = samples[mask].mean()             # recompute centroid

    return np.sort(c)

A duplicate reference implementation exists in benchmarks/hillclimb/bitlinear_recall.py, which also discusses constrained Lloyd iterations for specialized use cases.

Practical Example: Building and Using the Codebook

The following example demonstrates the complete workflow used by Turbovec to generate a shared codebook and quantize vectors:

import numpy as np

def lloyd_max_levels(samples: np.ndarray, levels: int, iters: int = 60) -> np.ndarray:
    """Compute optimal scalar quantization levels using Lloyd-Max algorithm."""
    lo, hi = np.quantile(samples, [0.001, 0.999])
    c = np.linspace(lo, hi, levels)                     # initial uniform grid

    for _ in range(iters):
        b = (c[1:] + c[:-1]) / 2.0                      # decision boundaries

        idx = np.searchsorted(b, samples)               # assign each sample

        for j in range(levels):
            mask = idx == j
            if mask.any():
                c[j] = samples[mask].mean()             # recompute centroid

    return np.sort(c)

def quantize_vectors(vecs: np.ndarray, codebook: np.ndarray) -> np.ndarray:
    """Returns nibble indices (0-(levels-1)) for each dimension."""
    boundaries = (codebook[1:] + codebook[:-1]) / 2.0
    return np.searchsorted(boundaries, vecs).astype(np.int32)

# Example usage matching Turbovec's pipeline

N, DIM = 20_000, 768                      # number of vectors & dimensionality

rng = np.random.default_rng(0)

# Generate raw L2-normalized vectors

raw = rng.normal(size=(N, DIM))
raw /= np.linalg.norm(raw, axis=1, keepdims=True)

# Build shared codebook from subset (4,000 samples max)

sampled = raw[::max(1, N // 4000)].ravel()
codebook = lloyd_max_levels(sampled, levels=16)  # 4 bits per dimension

# Quantize entire matrix (each entry becomes 4-bit nibble)

codes = quantize_vectors(raw, codebook)   # shape (N, DIM)

The resulting codes array contains indices into the shared codebook, allowing compact storage (e.g., packed 4-bit per entry) while enabling fast dot-product computations through lookup tables.

Accuracy Ceiling and Retrieval Performance

The Lloyd-Max codebook establishes an accuracy ceiling for Turbovec's quantized index. When a query vector is reconstructed using the exact floating-point values from the codebook (the "float-Lloyd-Max reconstruction"), it yields the highest possible recall achievable for that specific bit budget.

As demonstrated in permute_dot_recall.py (lines 75-78), reconstruction uses the expression s_float = q @ c[codes].T, where c is the codebook and codes are the stored indices. The benchmark proves that switching between different scoring kernels (such as the shipped LUT kernel versus a dot-product kernel) does not alter the codebook itself—only the location where quantization occurs changes. This validates that the Lloyd-Max levels represent the optimal compression strategy for the given data distribution.

Summary

• Lloyd-Max scalar quantization in Turbovec creates a single, shared codebook of optimal scalar levels that minimizes mean-squared reconstruction error.
• The algorithm iteratively refines quantization boundaries by computing decision thresholds and updating centroids based on sample means, typically running for 60 iterations.
• Each vector dimension is compressed independently into 2-4 bit nibbles that index into the shared codebook, enabling massive storage reduction.
• The reference implementation is available in benchmarks/hillclimb/permute_dot_recall.py as the lloyd_max_levels function, with the production engine using identical logic.
• The codebook provides an accuracy ceiling against which all other fast-scoring kernels are evaluated, ensuring optimal retrieval performance within the bit constraint.

Frequently Asked Questions

What is the difference between Lloyd-Max quantization and product quantization?

Lloyd-Max scalar quantization operates on individual dimensions, treating each scalar value independently to find optimal quantization levels. Product quantization (PQ) splits vectors into subspaces and quantizes each subspace separately using different codebooks. Turbovec uses Lloyd-Max quantization to create a single shared codebook across all dimensions, whereas PQ would require multiple codebooks. According to the source code in permute_dot_recall.py, the Lloyd-Max approach provides a tighter accuracy ceiling for scalar compression compared to subspace methods when using 2-4 bits per dimension.

How many bits per dimension does Turbovec typically use?

Turbovec typically uses 2 to 4 bits per dimension, storing each quantized value as a nibble (4-bit index) or smaller. The lloyd_max_levels function accepts a levels parameter (e.g., 16 for 4 bits) that determines the codebook size. The benchmark files demonstrate configurations using 16 levels (4 bits), though the architecture supports any power-of-two bit width that fits within a byte boundary for efficient packing.

Is the Lloyd-Max codebook shared across all vector dimensions?

Yes, Turbovec uses a shared codebook across all dimensions. The algorithm samples from all dimensions of the input vectors (flattening the sample matrix with .ravel()) and computes a single set of optimal levels. This shared codebook C is then used to quantize every dimension of every vector in the index. This approach reduces memory overhead and simplifies the dequantization process during query time, as the same lookup table applies universally.

Where is the Lloyd-Max implementation located in the Turbovec repository?

The primary reference implementation resides in benchmarks/hillclimb/permute_dot_recall.py at lines 41-51, specifically within the lloyd_max_levels function. An alternative implementation with additional constraints appears in benchmarks/hillclimb/bitlinear_recall.py. While these Python files serve as benchmarks and analysis tools, the actual index construction in Turbovec's compiled Rust/C++ engine implements the identical algorithm to generate the codebook used in production indexes.

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