The TurboQuant Algorithm Explained: How turbovec Achieves 4-Bit Vector Compression

TurboQuant is turbovec's core quantization engine that compresses high-dimensional floating-point vectors to 2–4 bits per coordinate while preserving near-optimal similarity search quality — and it does so with zero training data required.

The TurboQuant algorithm is the heart of the turbovec Rust library, a high-performance vector search engine that delivers 3–4× speed over FAISS-PQ. Unlike classic Product Quantization (PQ), which requires a costly per-dataset training phase, TurboQuant uses a deterministic rotation plus a pre-computed Lloyd-Max codebook to quantize any dataset out of the box. Let's break down exactly how it works under the hood.

The Five Stages of the TurboQuant Algorithm

According to the turbovec source code, TurboQuant consists of five tightly coupled stages that transform raw f32 vectors into packed bit codes. Each stage lives in a dedicated module under turbovec/src/:

Stage	What it does	Key implementation
Rotation	Applies a deterministic orthogonal block-Hadamard rotation to each vector so every coordinate follows a Beta((d-1)/2, (d-1)/2) distribution on [-1, 1]	turbovec/src/rotation.rs
Lloyd-Max quantizer	Solves an optimal scalar codebook for 2, 3, and 4-bit widths against the Beta distribution	turbovec/src/codebook.rs
TQ⁺ calibration	Fits a per-coordinate (shift, scale) pair from empirical quantiles of a sample	turbovec/src/encode.rs
Quantization & packing	Maps each coordinate to its nearest centroid and bit-plane packs codes into cache-friendly blocks	turbovec/src/encode.rs, turbovec/src/pack.rs
SIMD search	Scores packed codes with AVX-512 VNNI, NEON SDOT/SMMLA, and AVX2 kernels	turbovec/src/search.rs

Stage 1: Data-Oblivious Rotation

The first step in TurboQuant is a deterministic orthogonal rotation applied to every vector. As documented in turbovec/src/rotation.rs lines 3–4, the rotation matrix is a block-Hadamard transform that is lazily built and cached in a OnceLock. The goal is statistical: after rotation, every coordinate follows the same Beta((d-1)/2, (d-1)/2) distribution on the [-1, 1] interval.

This is the key that makes the rest of the algorithm data-oblivious. Because every coordinate now has the same known distribution, a single fixed codebook works for any dataset — no training pass is ever needed. That eliminates the classic PQ training bottleneck entirely.

Why the Beta distribution? The rotation renders the coordinates approximately i.i.d. with a known density. This means the scalar quantizer from Stage 2 can be solved analytically and once per bit-width, not re-solved per dataset.

Stage 2: Lloyd-Max Codebook Generation

In turbovec/src/codebook.rs, the codebook(bits, dim) function solves for the optimal scalar quantizer of the Beta distribution using the Lloyd-Max algorithm. The solver outputs two arrays:

• Boundaries — the decision thresholds between quantized regions
• Centroids — the representitive value used for each region

Because the source distribution is known, these codebooks minimize the mean-squared quantization error exactly. The turbovec crate ships pre-solved codebooks for 2, 3, and 4 bits per coordinate, giving you the option between aggressive compression and higher fidelity.

Stage 3: TQ⁺ Calibration (Optional Recall Boost)

The TQ⁺ (TurboQuant Plus) stage is an optional calibration pass that runs after an index has been populated. As implemented in turbovec/src/encode.rs via the calibrate and calibrate_2d functions, it:

1. Takes a representative sample of approximately 1,024 vectors
2. Computes empirical quantiles per coordinate
3. Fits a per-coordinate affine transform — a (shift, scale) pair stored as tqplus_shift and tqplus_scale on the TurboQuantIndex struct

This simple affine alignment maps the observed rotated coordinates onto the codebook's expected Beta-range distribution, recovering recall lost by coarse bit widths. In practice, TQ⁺ boosts recall by roughly 2.5 percentage points at R@10 on average.

Stage 4: Quantization and Bit-Plane Packing

Once rotated and optionally calibrated, each coordinate is mapped to the nearest centroid from the codebook and stored as an integer in the range {0 .. 2^b - 1}. The quantize_* kernels in turbovec/src/encode.rs handle this mapping in bulk.

The resulting integer codes are then bit-plane packed into a blocked layout via turbovec/src/pack.rs. The packing design is SIMD-oriented — it arranges codes so a single vector instruction can read of 32 vectors at once and accumulate inner products without unpacking scalars individually.

Stage 5: SIMD-Accelerated Search

The packed codes are consumed by hand-written SIMD kernels in turbovec/src/search.rs:

• AVX-512 VNNI on Intel Xeon/EP with VNNI support
• NEON SDOT/SMMLA on ARM (Apple Silicon, AWS Graviton)
• AVX2 as a broadly portable fallback
• Scalar fallback for any other CPU

These kernels compute inner products directly on packed integers, which is why turbovec achieves its observed speed advantage. Optionally, filter masks or allow-lists are applied inside the inner kernel loop, so filtering never forces a second pass.

Why TurboQuant Works So Well

The design is elegant because each stage contributes something specific:

• Data-obliviousness: The rotation makes the codebook dataset-independent — no training phase, no overhead.
• Lloyd-Max optimality: The codebook minimizes the distortion for the Beta distribution, giving the best possible 2–4 bit approximation.
• TQ⁺ alignment: A cheap affine transform recovers most recall lost by aggressive quantization.
• SIMD-friendly layout: The bit-plane packing allows single-instruction dot-products, translating directly to the 3–4× performance edge over FAISS-PQ.

Code Example: Using TurboQuant from Python

The turbovec Python package exposes the entire TurboQuant algorithm behind a clean NumPy-compatible API. Bindings live in turbovec-python/src/lib.rs:

from turbovec import TurboQuantIndex

# 1. Create a 4-bit index (dim inferred on first add)

idx = TurboQuantIndex(bit_width=4)

# 2. Add vectors (shape = (n, dim), dtype = float32)

idx.add(vectors)                     # vectors is a NumPy ndarray

# 3. Optional: calibrate with a representative sample (TQ⁺)

idx.calibrate(sample_vectors)        # roughly +2.5 pp recall

# 4. Search

scores, slots = idx.search(queries, k=10)

# 5. Persist / load

idx.write("my_index.tv")             # durable by default

loaded = TurboQuantIndex.load("my_index.tv")

Code Example: TurboQuant in Rust

For more granular control, the underlying Rust API is exposed directly through TurboQuantIndex in turbovec/src/lib.rs:

use turbovec::{TurboQuantIndex, CalibrationState};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // 1. Create a 2-bit index for 1536-dimensional vectors
    let mut idx = TurboQuantIndex::new(1536, 2)?;

    // 2. Add a flat slice of f32 values (n * dim)
    let vectors: Vec<f32> = vec![0.0; 1536 * 10];
    idx.add(&vectors)?;

    // 3. Calibrate with a sample (optional, improves recall)
    let sample = &vectors[0..1536 * 1024]; // first 1024 vectors
    idx.calibrate(sample)?;

    // 4. Search a batch of queries
    let queries: Vec<f32> = vec![0.0; 1536 * 5];
    let (scores, ids) = idx.search(&queries, 10)?;

    // 5. Save and reload
    idx.write("index.tv")?;
    let loaded = TurboQuantIndex::load("index.tv")?;

    Ok(())
}

The key methods — new, add, calibrate, search, write, and load — are all defined on TurboQuantIndex in turbovec/src/lib.rs and documented in the crate-level docs.

Key Source Files for the TurboQuant Algorithm

Full understanding of TurboQuant requires only a handful of source files:

File	Purpose
turbovec/src/lib.rs	Public API definition, TurboQuantIndex struct, high-level docs
turbovec/src/rotation.rs	Block-Hadamard rotation implementation and Beta distribution rationale
turbovec/src/codebook.rs	Lloyd-Max codebook solver for the Beta distribution
turbovec/src/encode.rs	TQ⁺ calibration (calibrate), per-coordinate quantization, packing
turbovec/src/pack.rs	Low-level bit-plane packing and unpacking
turbovec/src/search.rs	SIMD kernels (AVX-512 VNNI, NEON, AVX2, scalar) and mask handling
turbovec-python/src/lib.rs	Python bindings exposing the Rust API
README.md / docs/api.md	Usage examples, benchmarks, and API reference

Summary

• TurboQuant is turbovec's core algorithm that quantizes floating-point vectors to 2–4 bits per coordinate while keeping high recall.
• The pipeline: Hadamard rotation → Beta-distributed codes → optional TQ⁺ affine calibration → Lloyd-Max quantization → bit-plane packing.
• The algorithm is data-oblivious — no training phase — thanks to the deterministic rotation creating a known distribution.
• TQ⁺ calibration is the optional recall booster, rewarding learning per-coordinate shifts and scales from a ~1K or smaller sample.
• The packed layout makes the library’s SIMD kernels (AVX-512, NEON, AVX2) extremely efficient, giving it 3–4× speed-ups over FAISS-PQ.
• All five stages are fully open source under turbovec/src/, starting at lib.rs.

Frequently Asked Questions

What exactly does the TurboQuant algorithm quantize for vector vectors?

TurboQuant quantizes each coordinate of a high-dimensional vector to a small integer in {0..2^b-1} — typically 2–4 bits. It combines rotation to normalize the coordinate distribution, an optimal Lloyd-Max codebook, and optional TQ⁺ calibration to keep recall high while dropping memory footprint and search cost.

Is TurboQuant training data required for TurboQuant?

No. Because the rotation stage deterministically transforms vectors so that every coordinate follows the Beta distribution, the quantizer codebook is pre-computed and universal. The optional TQ⁺ calibration step accepts a small sample only to improve recall — it is not a training requirement.

How does TurboQuant compare to Product Quantization (PQ)?

TurboQuant uses a per-coordinate scalar quantizer with a fixed codebook and data-oblivious rotation, so it requires no training phase at all. FAISS-PQ needs per-dataset training to learn centroids. Turbovec's or quantized layout is SIMD-friendly, giving it measured 3–4× speed-up over FAISS-PQ on supported CPUs.

Where can I see the actual implementation of TurboQuant?

The algorithm is fully source-available: start with the crate-level documentation in turbovec/src/lib.rs, then look at rotation.rs for the Hadamard rotation, codebook.rs for the Lloyd-Max quantizer, encode.rs for TQ⁺ calibration and quantization, and search.rs for the SIMD kernels.

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