RaBitQ: Quantizing High-Dimensional Vectors with Unbiased Error Bounds

8 min read

RaBitQ (Randomised Binary Quantization) is a state-of-the-art vector compression algorithm designed to solve the "storage amplification" bottleneck in vector search. Instead of relying on data-dependent heuristic clustering (like Product Quantization), RaBitQ employs randomised orthogonal projections to compress high-dimensional vectors into ultra-compact bit strings while guaranteeing a sharp, mathematically optimal theoretical error bound of $\mathcal{O}(1/\sqrt{D})$.

1. The Core Architecture: PQ vs. RaBitQ

To appreciate RaBitQ, we must contrast its architectural deltas with traditional Product Quantization (PQ):

2. Step-by-Step Indexing Phase (Compression & Storage)

Let us trace how RaBitQ compresses a raw database vector $\mathbf{o}_r$ in a $4$-dimensional space ($D = 4$).

Step 1: Unit Vector Normalization

Raw vectors in a database can have arbitrary lengths. RaBitQ normalises them onto a unit hypersphere so that their spatial angles and distributions are mathematically predictable.

Let our raw database vector ($\mathbf{o}_r$) and the precomputed dataset centroid ($\mathbf{c}$) be: $\mathbf{o}_r = \begin{bmatrix} 3.0 \\ 4.0 \\ 0.0 \\ 0.0 \end{bmatrix}, \quad \mathbf{c} = \begin{bmatrix} 0.0 \\ 0.0 \\ 0.0 \\ 0.0 \end{bmatrix}$

First, we find the Euclidean norm of our raw vector from the dataset centroid: $\|\mathbf{o}_r - \mathbf{c}\| = \sqrt{3.0^2 + 4.0^2 + 0.0^2 + 0.0^2} = \sqrt{25} = 5.0$

Next, we normalize the coordinates by dividing each coordinate by its norm to obtain the unit vector $\mathbf{o}$: $\mathbf{o} = \frac{\mathbf{o}_r - \mathbf{c}}{\|\mathbf{o}_r - \mathbf{c}\|} = \begin{bmatrix} 0.6 \\ 0.8 \\ 0.0 \\ 0.0 \end{bmatrix}$

The vector $\mathbf{o}$ sits perfectly on a unit hypersphere since $\|\mathbf{o}\| = \sqrt{0.6^2 + 0.8^2 + 0.0^2 + 0.0^2} = 1.0$.

Step 2: Randomized Rotation (JLT)

Instead of running an expensive K-Means clustering pass to find centroids, RaBitQ defines a simple conceptual codebook consisting of the vertices of a hypercube, where coordinates are $\pm 1/\sqrt{D}$. For $D=4$, these coordinates sit at $\pm 1/\sqrt{4} = \pm 0.5$.

To eliminate directional bias, we generate a random orthogonal rotation matrix $P$ (a Johnson-Lindenstrauss Transformation). We inversely rotate our normalized vector $\mathbf{o}$ by multiplying it by $P^{-1}$. Let us assume this inverse rotation yields: $\mathbf{o}' = P^{-1}\mathbf{o} = \begin{bmatrix} 0.45 \\ -0.12 \\ 0.88 \\ -0.32 \end{bmatrix}$

Step 3: Quantize to Signs (Bits)

To compress the vector, RaBitQ discards all decimal precision and retains only the signs of the rotated coordinates (positive $\to 1$, negative $\to 0$):

• Coordinate 1: $0.45 > 0 \implies \mathbf{1}$
• Coordinate 2: $-0.12 < 0 \implies \mathbf{0}$
• Coordinate 3: $0.88 > 0 \implies \mathbf{1}$
• Coordinate 4: $-0.32 < 0 \implies \mathbf{0}$

The final compressed representation of our vector is the 4-bit string: $\mathbf{x}_b = \mathbf{1010}_2$

This compact code corresponds to the unrotated hypercube vertex $\bar{\mathbf{x}} = [0.5, \ -0.5, \ 0.5, \ -0.5]^T$.

Step 4: Precompute the Scaling Corrector

To cancel out the noise introduced by discarding decimal precision, we precompute the similarity (dot product) between our true rotated vector $\mathbf{o}'$ and its unrotated quantized vertex $\bar{\mathbf{x}}$: $\langle \bar{\mathbf{o}}, \mathbf{o} \rangle = \langle \bar{\mathbf{x}}, \mathbf{o}' \rangle = (0.5 \times 0.45) + (-0.5 \times -0.12) + (0.5 \times 0.88) + (-0.5 \times -0.32) = \mathbf{0.885}$

This single scalar value ($\mathbf{0.885}$) acts as a scaling corrector during search queries to keep our distance estimations completely unbiased.

What is Stored in the Database?

For each vector in our dataset, the database stores only three lightweight values:

1. The $D$-bit string code ($\mathbf{x}_b$): 1010 (Takes exactly $4$ bits).
2. The scaling corrector ($\langle \bar{\mathbf{o}}, \mathbf{o} \rangle$): 0.885 ($32$-bit float).
3. The raw length ($\|\mathbf{o}_r - \mathbf{c}\|$): 5.0 ($32$-bit float).

3. The Compression Wins: Cutting the Index in Half

• Raw Vectors (F32): A raw $128$-dimensional vector ($D = 128$) using standard 32-bit floats takes 4,096 bits ($512$ bytes) of memory.
• Product Quantization (PQ): To achieve acceptable accuracy, standard PQ or Optimized PQ (OPQ) typically splits vectors into $M = D/2$ segments and encodes each segment using 4 bits, resulting in a quantization code size of $2D$ bits (256 bits, or $32$ bytes).
• RaBitQ: Quantizes a vector down to a flat $D$-bit string. For $D = 128$, the core quantization code takes exactly 128 bits ($16$ bytes).
• The Compression Ratio: Even when adding the lightweight overhead of the scaling corrector and raw norm float per vector ($8$ bytes total), RaBitQ cuts the index storage footprint of standard PQ in half, achieving a massive $32\times$ compression ratio compared to raw floats! This 50% savings directly translates to millions of dollars saved in caching and NVMe costs at scale.

4. Step-by-Step Query Phase (Search & Lookup)

Suppose a client queries the database with a raw vector $\mathbf{q}_r = [0.0, \ 13.0, \ 0.0, \ 0.0]^T$.

Step 1: Normalize & Rotate the Query

The search engine measures the query's length from the dataset centroid: $\|\mathbf{q}_r - \mathbf{c}\| = \sqrt{0.0^2 + 13.0^2 + 0.0^2 + 0.0^2} = 13.0$

We normalize the query to a unit vector: $\mathbf{q} = \frac{\mathbf{q}_r - \mathbf{c}}{\|\mathbf{q}_r - \mathbf{c}\|} = \begin{bmatrix} 0.0 \\ 1.0 \\ 0.0 \\ 0.0 \end{bmatrix}$

We then inversely rotate the query using the same random rotation matrix ($P^{-1}$) to obtain $\mathbf{q}'$. Let us assume this yields: $\mathbf{q}' = P^{-1}\mathbf{q} = \begin{bmatrix} 0.2 \\ 0.7 \\ -0.4 \\ 0.5 \end{bmatrix}$

Step 2: 4-Bit Query Quantization ($B_q = 4$)

To avoid slow floating-point math during search, RaBitQ quantizes the query's rotated coordinates into small $B_q$-bit (usually 4-bit) integers (values from 0 to 15). Let’s say our quantized query is: $\mathbf{q}_u = \begin{bmatrix} 10 \\ 15 \\ 0 \\ 13 \end{bmatrix}$

Step 3: Hardware-Accelerated Bitwise Matching

To find the similarity between our stored database bit string 1010 ($\mathbf{x}_b$) and the quantized query integers ($\mathbf{q}_u$):

1. Because the query is represented as 4-bit integers, we decompose them into 4 binary bitmasks (one bitmask $\mathbf{q}_u^{(j)}$ for each of the $4$ bit-planes).
2. The CPU performs exactly 4 parallel bitwise AND operations between our stored database bit string (1010) and these 4 query bitmasks.
3. The CPU runs a hardware-accelerated popcount (bit-counting) instruction on the results, summing them up to calculate the raw similarity $\langle \bar{\mathbf{o}}, \mathbf{q} \rangle$. Let's say this fast register math yields: 0.85.

Step 4: Unbiased Distance Reconstruction

We evaluate RaBitQ's unbiased estimator formula to find our estimated unit similarity: $\text{Estimated Unit Similarity } \langle \mathbf{o}, \mathbf{q} \rangle \approx \frac{\langle \bar{\mathbf{o}}, \mathbf{q} \rangle}{\langle \bar{\mathbf{o}}, \mathbf{o} \rangle} = \frac{0.85}{0.885} \approx \mathbf{0.9605}$

(Note: The true unit similarity is $\langle \mathbf{o}, \mathbf{q} \rangle = (0.6 \times 0.0) + (0.8 \times 1.0) \approx \mathbf{0.80}$. Due to the extreme low-dimensionality of $D=4$, the random projection has a high variance of $\mathcal{O}(1/\sqrt{D})$. At production scales like $D=1536$, the concentration of measure guarantees this estimate converges tightly to the truth).

Finally, we apply the Law of Cosines to reconstruct the estimated raw squared Euclidean distance using the cached raw norms ($5.0$ and $13.0$): $\|\mathbf{o}_r - \mathbf{q}_r\|^2_{\text{estimated}} = \|\mathbf{o}_r - \mathbf{c}\|^2 + \|\mathbf{q}_r - \mathbf{c}\|^2 - 2 \|\mathbf{o}_r - \mathbf{c}\| \|\mathbf{q}_r - \mathbf{c}\| \langle \mathbf{o}, \mathbf{q} \rangle_{\text{estimated}}$ $\text{Estimated Raw Distance}^2 = 5.0^2 + 13.0^2 - 2(5.0)(13.0)(0.9605) \approx \mathbf{69.135}$

(The true raw squared distance is $(3-0)^2 + (4-13)^2 = 9 + 81 = \mathbf{90}$. RaBitQ estimated this with high accuracy using just 4 bits of compressed indexing data!)

5. Selective Re-ranking via Error Filtering

Because RaBitQ has a rigorous mathematical error bound, we no longer have to manually guess or tune how many candidates to re-rank.

During a query:

1. The engine calculates a strict lower bound of the distance for each candidate based on the $\mathcal{O}(1/\sqrt{D})$ confidence interval.
2. If a vector's best-case distance is worse than the exact distance of the closest match we've already found, it is instantly dropped.
3. Only the ambiguous vectors that cross the mathematical threshold are sent to full-fidelity re-ranking (where raw float coordinates are pulled from disk or S3), ensuring high search recall ($>90\%$ accuracy) automatically.

Related reads

• Hypercube — why the hypercube is the perfect codebook geometry
• Product Quantization (PQ) — the data-dependent approach RaBitQ replaces
• Storage Amplification in Vector Search — the bottleneck RaBitQ targets