How Random Orthogonal Rotation Enables Data-Oblivious Quantization in TurboQuantIndex

Random orthogonal rotation forces every coordinate of high-dimensional vectors into a predictable Beta distribution, allowing TurboQuantIndex to use a single pre-computed scalar codebook that never requires inspection of the raw data.

TurboQuantIndex, implemented in the RyanCodrai/turbovec repository, compresses high-dimensional vectors using a data-oblivious quantization scheme that eliminates the need for dataset-specific codebook training. By applying a deterministic random orthogonal transformation, the system converts any input distribution into a mathematically known spherical distribution, enabling a universal scalar quantizer to compress vectors from any domain without examining the raw data.

Generating the Deterministic Orthogonal Matrix

The foundation of this approach lies in make_rotation_matrix(dim) from [rotation.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/rotation.rs). This function constructs a dim × dim orthogonal matrix by performing QR decomposition on a seeded Gaussian random matrix.

The QR decomposition guarantees the orthogonality property RᵀR = I, meaning the rotation preserves Euclidean norms and inner products. Because the random seed is fixed, the matrix is deterministic—ensuring that the same rotation is applied consistently during both indexing and query time.

use turbovec::rotation::make_rotation_matrix;

let dim = 1536;
let rotation = make_rotation_matrix(dim);  // Deterministic orthogonal matrix

Predictable Coordinate Distributions

After rotation, any unit vector v̂ lies uniformly on the unit sphere S^{d-1}. Crucially, the marginal distribution of each coordinate becomes statistically predictable:

v̂ᵢ ~ Beta((d-1)/2, (d-1)/2) on the interval [-1, 1]

This result holds for any original data distribution because orthogonal transformations only mix coordinates without altering the overall spherical symmetry. As implemented in [codebook.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs), this predictable distribution allows the system to compute optimal quantization boundaries before seeing any data.

Building the Data-Oblivious Scalar Codebook

The codebook(bits, dim) function in [codebook.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/codebook.rs) computes the optimal Lloyd-Max quantizer for the Beta distribution described above. Since the distribution is known and data-independent, the same scalar codebook can be pre-computed and applied to every coordinate of every vector.

For 4-bit quantization, this produces 16 levels derived from the theoretical Beta quantiles rather than empirical data statistics:

use turbovec::codebook::codebook;

let bits = 4;
let (boundaries, centroids) = codebook(bits, dim);  // Pre-computed, data-oblivious

TQ+ Calibration for Residual Anisotropy

Real-world datasets often exhibit anisotropic characteristics that violate perfect spherical symmetry. The encode function in [encode.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/encode.rs) addresses this through per-coordinate calibration (shift and scale parameters) that maps empirical quantiles onto the canonical Beta quantiles.

This calibration step remains data-oblivious because it only uses statistics from the rotated batch and never requires learning a separate codebook per coordinate. The calibration parameters are stored alongside the quantized codes and applied inversely during query processing.

use turbovec::encode::encode;

let n = vectors.len() / dim;
let (packed_codes, scales, shift, scale_tq) =
    encode(&vectors, n, dim, &rotation, &boundaries, &centroids, bits, None);

Query-Time Processing

At search time, the query vector undergoes the identical rotation and inverse calibration pipeline. The query is multiplied by the transpose of the rotation matrix, adjusted using the stored shift and scale_tq parameters, and compared against the quantized codes using the per-vector scales to restore unbiased inner-product estimates.

// Apply rotation to query
let q_rot = {
    let q_mat = ndarray::ArrayView2::from_shape((dim, dim), &rotation).unwrap();
    let q_vec = ndarray::ArrayView1::from_shape(dim, query).unwrap();
    q_mat.t().dot(&q_vec)
};

// Inverse calibration
let q_calib: Vec<f32> = q_rot.iter()
    .zip(shift.iter())
    .zip(scale_tq.iter())
    .map(|((&x, &s), &sc)| (x + s) * sc)
    .collect();

Summary

• Deterministic rotation: make_rotation_matrix generates a seeded orthogonal matrix via QR decomposition, ensuring RᵀR = I and preserving vector similarities.
• Universal distribution: Rotation forces coordinates to follow a Beta((d-1)/2, (d-1)/2) distribution, independent of the original data distribution.
• Pre-computed quantization: The codebook function generates a single scalar quantizer for the Beta distribution, eliminating the need for data-dependent training.
• Anisotropy handling: TQ+ calibration in encode adjusts for residual anisotropy using per-coordinate shift and scale, maintaining the data-oblivious property.
• Consistent pipeline: The same rotation and calibration parameters apply at both indexing and query time, ensuring mathematical consistency.

Frequently Asked Questions

Why does orthogonal rotation preserve search accuracy?

Orthogonal matrices preserve Euclidean norms and inner products because they satisfy RᵀR = I. When both database vectors and queries undergo the same rotation, their relative similarities remain unchanged, guaranteeing that approximate nearest neighbor search results remain valid after quantization.

What causes the Beta distribution to appear after rotation?

When any unit vector is multiplied by a random orthogonal matrix, it becomes uniformly distributed on the surface of the unit sphere. The marginal distribution of any single coordinate of a uniform unit vector follows the Beta distribution with parameters (d-1)/2, a consequence of the geometry of high-dimensional spheres.

How does TQ+ calibration differ from learning a codebook?

Traditional vector quantization learns codebook centroids from data, requiring expensive training. TQ+ calibration merely adjusts the mean and variance of each rotated coordinate to match the theoretical Beta distribution using linear transformations (shift and scale). It does not learn new quantization levels, preserving the data-oblivious nature of the system.

Can the same rotation matrix be reused across different datasets?

Yes. Because the rotation is deterministic and the resulting Beta distribution is universal, the same make_rotation_matrix output and corresponding codebook can compress vectors from completely different domains without modification. The calibration step in encode handles any minor distribution shifts without requiring per-dataset retraining.

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