The Six Stages of Turbovec's Compression Pipeline

Turbovec compresses high-dimensional vectors through a deterministic six-stage pipeline—normalize, random rotation, per-coordinate calibration (TQ+), Lloyd-Max scalar quantization, bit-pack, and scale—that reduces storage by up to 16× while preserving unbiased inner-product search capabilities.

The turbovec compression pipeline enables efficient storage and retrieval of high-dimensional vectors by transforming dense f32 data into compact quantized representations. According to the RyanCodrai/turbovec source code, this process sequentially applies six mathematical operations implemented in Rust, converting 1536-dimensional vectors from approximately 6 KB down to 384 bytes when using 2-bit compression. Each stage targets specific distributional corrections to ensure the final bit-packed codes support provably unbiased approximate search via SIMD-accelerated kernels.

The Six-Stage Compression Process

1. Normalize

The pipeline begins by stripping the vector's length (‖v‖) and saving it as a single-precision float. The remaining data represents a unit-direction on the hypersphere, eliminating magnitude information from the subsequent quantization steps. As documented in the README, this normalization ensures that all subsequent operations work with directionality rather than raw magnitude.

2. Random Rotation

All normalized vectors are multiplied by the same deterministic orthogonal rotation, specifically a globally-permuted block-Hadamard transform implemented in turbovec/src/rotation.rs. This rotation enforces that each coordinate follows a known Beta distribution, which is essential for the calibration and quantization stages that follow. According to the README, this transformation is applied consistently across the entire dataset.

3. Per-Coordinate Calibration (TQ+)

For each coordinate, the pipeline fits a shift and scale parameter so that empirical quantiles align with the codebook's outermost centroids. This TQ+ (TurboQuant) calibration, described in the README, corrects drift that occurs in finite-dimensional data, ensuring the rotated coordinates match the theoretical distributions assumed by the quantizer.

4. Lloyd-Max Scalar Quantization

Using the calibrated coordinates, the system applies a Lloyd-Max codebook (pre-computed for the target bit-width) to quantize each coordinate into one of 2^bits buckets. This scalar quantization step, detailed in the README and implemented via turbovec/src/codebook.rs, maps continuous values to discrete indices while minimizing distortion for the given bit budget.

5. Bit-Pack

The quantized integer codes are tightly packed into bytes (e.g., 4-bit codes store two values per byte), dramatically reducing storage overhead. As noted in the [source comments of encode.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs#L1-L2), this stage converts the abstract quantized indices into a compact binary representation optimized for memory efficiency.

6. Scale

The final stage stores a per-vector scale factor calculated as ‖v‖ / ⟨u, x̂⟩, where u is the rotated unit vector and x̂ is the reconstructed centroid. During search operations, the SIMD kernel multiplies this scale back in to obtain an unbiased inner-product estimate. This critical correction, also documented in [encode.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs#L1-L2), ensures that compressed vectors retain the magnitude information stripped during normalization.

Core Implementation Files

The turbovec compression pipeline is implemented across several key Rust source files:

• turbovec/src/encode.rs — Contains the module-level comment listing all six stages and implements the full encode pipeline from normalization through scaling.
• turbovec/src/rotation.rs — Provides the deterministic orthogonal rotation (Stage 2) using the block-Hadamard transform.
• turbovec/src/codebook.rs — Generates the Lloyd-Max codebooks used during Stage 4 quantization.
• turbovec/src/lib.rs — Exposes the public API via TurboQuantIndex, which orchestrates the pipeline through methods like add(), calibrate(), and search().

Practical Rust API Usage

The following example demonstrates how the six-stage pipeline is triggered automatically when adding vectors to a TurboQuantIndex:

use turbovec::TurboQuantIndex;

// 1️⃣ Create an index for 1536‑dimensional vectors, 4‑bit compression.
let mut idx = TurboQuantIndex::new(1536, 4).unwrap();

// 2️⃣ Calibrate (stage 3) on a representative sample.  
let sample = generate_sample_vectors(1024, 1536);
idx.calibrate(&sample).unwrap();   // runs per‑coordinate TQ+ fit

// 3️⃣ Add vectors – the pipeline (1‑6) runs automatically.
//    Normalization → rotation → calibration → quantization → bit‑pack → scale.
let vectors = generate_vectors(10_000, 1536);
idx.add(&vectors).unwrap();

// 4️⃣ Search – the stored scale is applied inside the SIMD kernel.
let queries = generate_vectors(100, 1536);
let results = idx.search(&queries, 10);
println!("{:?}", results);

Summary

• Normalize: Strips magnitude to create unit vectors on the hypersphere.
• Random Rotation: Applies deterministic block-Hadamard transform to enforce Beta distribution.
• TQ+ Calibration: Per-coordinate shift and scale to align quantiles with codebook centroids.
• Lloyd-Max Quantization: Maps calibrated floats to discrete buckets using pre-computed codebooks.
• Bit-Pack: Compresses quantized indices into dense byte arrays.
• Scale: Stores correction factor for unbiased inner-product estimation during SIMD search.

Frequently Asked Questions

What compression ratios does turbovec achieve?

The pipeline typically achieves 16× compression for 2-bit quantization (e.g., reducing 1536-dimensional float32 vectors from 6 KB to 384 bytes) and 8× compression for 4-bit quantization. These ratios depend on the bit-width parameter passed to TurboQuantIndex::new().

How does turbovec maintain search accuracy after compression?

The Scale stage stores the per-vector factor ‖v‖ / ⟨u, x̂⟩, which the SIMD search kernel applies to reconstruct unbiased inner-product estimates. This correction compensates for information loss during quantization, preserving search quality relative to exact brute-force methods.

Why is random rotation necessary before quantization?

The Random Rotation stage (Stage 2) ensures all coordinates follow a known statistical distribution by applying a deterministic orthogonal transform. Without this step, per-coordinate calibration would be ineffective because the TQ+ fitting assumes specific distributional properties that raw high-dimensional data rarely exhibits.

Where is the main compression logic implemented?

The six-stage pipeline logic resides primarily in turbovec/src/encode.rs, which contains the module-level documentation listing each stage. The rotation transform lives in rotation.rs, while the Lloyd-Max codebook generation is handled in codebook.rs.

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