How Length-Renormalization Corrects Scoring Bias in TurboVec: Implementation Deep Dive

TurboVec eliminates systematic downward bias in similarity scores by computing a per-vector length-renormalization factor of ||v|| / <u, x̂> during encoding, which SIMD search kernels apply at query time to restore unbiased inner-product estimates.

TurboVec compresses high-dimensional vectors using scalar quantization against a Lloyd-Max codebook. While this reduces storage costs, the quantized reconstruction x̂ is slightly shorter than the original rotated unit vector u, causing raw inner-product scores to systematically underestimate true similarity. The library corrects this through length-renormalization, a zero-cost correction applied in the SIMD kernels that restores the original vector magnitude without additional runtime overhead.

The Quantization Shrinkage Problem

When TurboVec encodes a vector, it first normalizes the vector to unit length, applies a random rotation, and then quantizes each coordinate against Lloyd-Max centroids.

The quantized reconstruction x̂ is a centroid-based approximation of the rotated unit vector u. Because scalar quantization maps continuous values to discrete centroids, the reconstructed vector x̂ is inevitably shorter than the original unit vector u.

This length reduction creates a systematic downward bias: the raw inner product <u, x̂> used as a similarity score is smaller than the true inner product <v, q> between the original vectors. Without correction, this bias degrades recall, particularly at low bit-widths (2-bit or 4-bit) where quantization shrinkage is most severe.

Computing the Correction Factor in encode.rs

During encoding, TurboVec calculates a per-vector correction scale that captures the ratio between the original vector's magnitude and the magnitude of its quantized reconstruction.

In turbovec/src/encode.rs, the fused_quantize_scale_pack routine computes:

let inner = inner.max(1e-10) as f32;
norm / inner

Here, norm represents the original vector norm ||v||, and inner is the dot product <u, x̂> between the rotated unit vector u and the reconstructed centroid vector x̂. The function returns norm / inner as the length-renormalization factor, which is stored alongside each compressed vector.

This scale factor is computed exactly once per vector during the encoding phase. The library stores it as a single f32 (approximately 4 bytes per vector), which is negligible compared to the compressed code size.

Applying Renormalization During Search

At query time, the SIMD search kernels apply the stored scale factors to remove the quantization bias. The kernels first compute the inner-product accumulator between the query and the quantized codes without scaling, then multiply each per-vector partial score by its corresponding renormalization factor.

In turbovec/src/search.rs, the NEON kernel for aarch64 implements this as:

for i in 0..8 {
    let n = vld1q_f32(vec_scales_ptr.add(i * 4));
    // fa[i] holds the accumulated inner-product (biased)
    // n = per-vector scale = ||v|| / <u, x̂>
    vst1q_f32(out_ptr.add(i * 4), vmulq_f32(fa[i], n));
}

The same pattern appears in the AVX2 and AVX-512 implementations (avx2_batch_flush_to_fa → avx2_post_flush_heap_update), where each SIMD lane is multiplied by the vector-specific scale before the heap update. Because the scale is exactly the reciprocal of the shrinkage introduced by quantization, the final score equals the true inner product ⟨v, q⟩ (up to floating-point rounding error).

Performance and Storage Characteristics

The length-renormalization correction incurs minimal overhead:

• Storage cost: One extra f32 per vector (4 bytes), stored in the vec_scales array.
• Query cost: A single SIMD multiply per lane, fused into the existing score accumulation pipeline.
• Encode cost: Computed once during the initial quantization phase with no additional passes required.

The correction is most noticeable at very low bit-widths (2-bit, 4-bit) where quantization shrinkage is largest, directly improving recall metrics as documented in the repository README.

Implementation Examples

Rust: Encoding and Searching with Renormalization

The following example demonstrates how the scale factor flows from encoding to search:

use turbovec::encode::encode;
use turbovec::search::search;

// Encode a batch of vectors (dim = 1536, 4-bit quantization)
let (packed_codes, scales, _shift, _scale_tq) = encode(
    &vectors,                 // &[f32] flat input
    n_vectors,
    dim,
    &rotation,               // random orthogonal matrix
    &boundaries,             // Lloyd-Max boundaries
    &centroids,              // Lloyd-Max centroids
    4,                       // bit-width
    None,                    // first batch → fit TQ+ calibration
);

// scales[i] = ||v_i|| / <u_i, x̂_i> (length-renorm factor)

// Search with bias correction applied
let results = search(
    &packed_codes,
    &scales,                  // passed as vec_scales
    &rotation,
    &centroids,
    /* other parameters */
);

The search routine invokes SIMD kernels (e.g., score_4bit_block_neon) that multiply each lane’s accumulator by scales[i], yielding unbiased inner-product scores.

Python: High-Level API

When using the Python bindings in turbovec-python/python/turbovec/haystack.py, the correction is applied automatically:

import turbovec

# Build an index (4-bit, dim=1536)

idx = turbovec.Index(
    dim=1536,
    bit_width=4,
    metric="dot_product",
)

# Add vectors – per-vector scales computed automatically

idx.add(vectors)  # vectors is np.ndarray of shape (N, 1536)

# Query with length-renormalization enabled

scores, ids = idx.search(query, k=10, scale_score=True)

Setting scale_score=True passes the stored per-vector scales to the underlying Rust search kernel, which applies the same multiplication described above. The returned scores are unbiased inner-product values.

Summary

• Scalar quantization shortens reconstructed vectors, causing a systematic downward bias in similarity scores.
• The correction factor ||v|| / <u, x̂> is computed once per vector during encoding in turbovec/src/encode.rs.
• SIMD kernels in turbovec/src/search.rs multiply accumulators by this scale to restore unbiased estimates.
• Overhead is minimal: one extra f32 per vector and one SIMD multiply per lane at query time.
• Recall improves measurably at low bit-widths (2-bit, 4-bit) where quantization shrinkage is most pronounced.

Frequently Asked Questions

What causes the scoring bias in quantized vector similarity?

TurboVec uses Lloyd-Max scalar quantization to compress vectors into compact codes. The quantized reconstruction x̂ is a centroid-based approximation that is always slightly shorter than the original rotated unit vector u. Because the inner product <u, x̂> is proportional to vector length, this shrinkage causes the raw score to systematically underestimate the true similarity <v, q>.

How much additional storage does length-renormalization require?

The correction requires storing one f32 (4 bytes) per vector in the vec_scales array. For a typical 4-bit quantization of a 1536-dimensional vector (768 bytes compressed), this represents less than 0.5% storage overhead.

Does length-renormalization affect query latency?

No. The correction is applied as a single SIMD multiply instruction per vector during the final score accumulation phase. This is fused into the existing kernel pipeline in turbovec/src/search.rs, resulting in zero measurable latency increase compared to uncorrected scoring.

Which SIMD architectures support the renormalization step?

The renormalization multiplier is implemented across all TurboVec SIMD backends: NEON (aarch64), AVX2 (x86_64), and AVX-512 (x86_64). Each kernel loads the per-vector scale from the vec_scales array and applies it using architecture-specific multiply instructions (vmulq_f32 on NEON, _mm256_mul_ps on AVX2, etc.) before updating the result heap.

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