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

> Explore the TurboQuant algorithm, turbovec's core engine for 2-4 bit vector compression. Achieve near-optimal similarity search quality with zero training data.

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

---

**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](https://github.com/RyanCodrai/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs) |
| **TQ⁺ calibration** | Fits a per-coordinate `(shift, scale)` pair from empirical quantiles of a sample | [`turbovec/src/encode.rs`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs), [`turbovec/src/pack.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/pack.rs) |
| **SIMD search** | Scores packed codes with AVX-512 VNNI, NEON SDOT/SMMLA, and AVX2 kernels | [`turbovec/src/search.rs`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec-python/src/lib.rs):

```python
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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs):

```rust
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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs) | Public API definition, `TurboQuantIndex` struct, high-level docs |
| [`turbovec/src/rotation.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/rotation.rs) | Block-Hadamard rotation implementation and Beta distribution rationale |
| [`turbovec/src/codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs) | Lloyd-Max codebook solver for the Beta distribution |
| [`turbovec/src/encode.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs) | TQ⁺ calibration (`calibrate`), per-coordinate quantization, packing |
| [`turbovec/src/pack.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/pack.rs) | Low-level bit-plane packing and unpacking |
| [`turbovec/src/search.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/search.rs) | SIMD kernels (AVX-512 VNNI, NEON, AVX2, scalar) and mask handling |
| [`turbovec-python/src/lib.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec-python/src/lib.rs) | Python bindings exposing the Rust API |
| [`README.md`](https://github.com/RyanCodrai/turbovec/blob/main/README.md) / [`docs/api.md`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs), then look at [`rotation.rs`](https://github.com/RyanCodrai/turbovec/blob/main/rotation.rs) for the Hadamard rotation, [`codebook.rs`](https://github.com/RyanCodrai/turbovec/blob/main/codebook.rs) for the Lloyd-Max quantizer, [`encode.rs`](https://github.com/RyanCodrai/turbovec/blob/main/encode.rs) for TQ⁺ calibration and quantization, and [`search.rs`](https://github.com/RyanCodrai/turbovec/blob/main/search.rs) for the SIMD kernels.