All posts

RaBitQ: 32x Vector Compression With an Error Bound You Can Actually Prove

7 min read vector-searchquantizationdatabasesalgorithmsann

The quiet embarrassment of Product Quantization

Every serious vector database, FAISS, Milvus, pgvector's friends, ships some form of Product Quantization (PQ). The recipe from Jegou et al. (2011) is familiar: split a D-dimensional vector into M subvectors, run k-means in each subspace to build 256-entry codebooks, and store each subvector as a 1-byte centroid index. A 1024-dimensional float32 vector shrinks from 4 KB to 128 bytes, and distances are estimated by summing precomputed lookup-table entries.

It works, mostly. But PQ has two problems that practitioners paper over and theoreticians wince at:

  1. No error bound. PQ's accuracy depends entirely on how well k-means centroids happen to fit your data distribution. There is no guarantee of the form "the estimated distance is within epsilon of the true distance with probability 1 - delta." On some real-world datasets, notably ones where variance concentrates in a few dimensions, PQ's estimates degrade so much that recall collapses no matter how much you re-rank.
  2. Biased estimates. The quantized distance systematically underestimates or overestimates depending on where the query lands relative to the codebook cells. You cannot correct a bias you cannot measure.

RaBitQ, from Gao and Long at NTU (SIGMOD 2024, arXiv:2405.12497), attacks both problems at once. It compresses each vector to one bit per dimension, a 32x reduction from float32, provides an unbiased distance estimator, and proves the estimation error is O(1/sqrt(D)) with high probability. On the standard ANN benchmarks it beats PQ and its optimized variants (OPQ) on the accuracy-versus-throughput curve, often by a wide margin.

The core idea: rotate first, then be naive

Naive binary quantization, keep the sign of each coordinate, is ancient and usually bad. If your data has structure (and real embeddings always do: a handful of dominant directions, correlated coordinates), sign bits throw away exactly the information that matters.

RaBitQ's insight is that you can destroy that structure on purpose. Sample a random orthogonal matrix P (a random rotation of the space), apply it to every vector once at index time, and the rotated coordinates of any fixed unit vector become statistically indistinguishable from a random point on the sphere. No direction is special anymore. Now the naive codebook works, and, crucially, its behavior can be analyzed.

Concretely, RaBitQ operates on unit vectors (raw vectors are normalized relative to their IVF cluster centroid; norms are stored separately as scalars). The codebook is the set of all 2^D bivalued vectors:

C = { (±1/√D, ±1/√D, ..., ±1/√D) }

Every codeword sits on the unit sphere. A data vector o is quantized to the codeword whose signs match the signs of its rotated coordinates, which is just:

import numpy as np

def index_vector(o_residual, P):
    """One-time indexing. P is a random orthogonal matrix (Haar measure),
    sampled once and shared by the whole index."""
    o = o_residual / np.linalg.norm(o_residual)
    o_rot = P @ o
    code = (o_rot > 0)                       # D bits -- the entire code
    x_bar = np.where(code, 1, -1) / np.sqrt(len(o))
    dot = float(o_rot @ x_bar)               # <o, x_bar>, one scalar, stored
    return np.packbits(code), dot

Two things get stored per vector: D bits of code and one float, the inner product between the rotated vector and its own codeword. That scalar is the correction factor that turns a crude sign-match count into an unbiased estimate.

The unbiased estimator

At query time we need the inner product between the query q and the original data vector o. RaBitQ shows that

⟨o, q⟩ ≈ ⟨x̄, q⟩ / ⟨x̄, o⟩

where x̄ is the stored codeword. The numerator is computable from the binary code; the denominator is the stored scalar. The paper proves this estimator is unbiased and, this is the part PQ cannot offer, that its error concentrates:

|error| = O( sqrt( (1 - ⟨x̄,o⟩²) / ⟨x̄,o⟩² · log(1/δ) / D ) )  with probability 1 - δ

Because a random rotation makes ⟨x̄, o⟩ concentrate around a known constant (roughly sqrt(2/π) ≈ 0.8), the whole bound collapses to O(1/sqrt(D)). Higher-dimensional embeddings get more accurate per bit, which is exactly the regime modern 768- to 3072-dimensional embedding models live in.

The practical consequence: RaBitQ can report a confidence interval per candidate. An implementation can skip exact re-ranking for candidates whose interval clearly excludes the current top-k threshold, something PQ pipelines approximate with fragile, dataset-tuned heuristics.

Distance estimation is a popcount

The estimator needs ⟨x̄, q_rot⟩. Quantize the rotated query coarsely (4 bits per dimension is enough, done once per query, its error is second-order), and the inner product between a 1-bit code and a 4-bit query decomposes into bitwise ANDs and popcounts over the code's bit-planes:

def estimate_inner_products(codes, q_4bit_planes):
    """codes: (N, D/8) packed uint8. q_4bit_planes: 4 bit-planes of the
    quantized rotated query. Returns unnormalized <x_bar, q> for N vectors."""
    acc = np.zeros(len(codes), dtype=np.uint32)
    for k, plane in enumerate(q_4bit_planes):          # 4 planes
        acc += (1 << k) * popcount_rows(codes & plane) # AND + popcount
    return acc  # rescaled to a dot product with two scalar ops per vector

On real hardware this is VPAND + VPOPCNTQ over contiguous memory: no lookup tables competing for L1 like PQ's ADC scan, no gather instructions, just streaming bitwise arithmetic. This is where the throughput win comes from. A 1024-dimensional comparison touches 128 bytes of code and does a handful of SIMD ops; the paper reports ~3x higher queries-per-second than optimized PQ at equal recall on GIST and other standard datasets, with the gap widening on the datasets where PQ's lack of guarantees actually bites.

How it slots into a real index

RaBitQ is an estimator, not an index, and the paper pairs it with plain IVF:

  1. Index: cluster vectors (k-means), store each vector's RaBitQ code and correction scalar, plus its distance to the centroid.
  2. Query: probe the nearest clusters; for each candidate compute the estimated distance from the popcount pipeline in a few nanoseconds.
  3. Re-rank: fetch full-precision vectors only for candidates whose estimate (or lower confidence bound) beats the running top-k threshold.

The follow-up work extends the idea to a spectrum: an extended RaBitQ supports 2 to 9 bits per dimension for higher-accuracy tiers, and the technique is the foundation of recent "scalar quantization is all you need" results shipping in production systems, Milvus and Elasticsearch have both adopted RaBitQ-style binary quantization with rotation for their newest index types.

Why this matters beyond vector databases

The pattern generalizes and is worth internalizing:

  • Randomize, then simplify. A random rotation converts adversarial structure into average-case behavior, letting a trivially simple codebook (sign bits!) achieve what learned codebooks struggle with. This is the same move as randomized pivots in quicksort or random projections in Johnson-Lindenstrauss, applied to quantization.
  • Unbiasedness buys composability. Because the estimator is unbiased with known variance, you can reason about downstream decisions (prune or re-rank?) probabilistically instead of empirically re-tuning thresholds per dataset.
  • Guarantees are not a tax. The folk belief is that theoretically-grounded methods trade away practical performance. RaBitQ is faster and provable, because the theory pointed directly at a hardware-friendly primitive: popcount over packed bits.

If you operate a vector search system today and your memory bill or tail-latency budget is dominated by PQ scans and re-ranking, RaBitQ is one of the rare drop-in ideas where the replacement is simpler than what it replaces.

References

  • Gao, J., Long, C. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. SIGMOD 2024. arXiv:2405.12497
  • Gao, J., et al. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors for ANN Search. (extended RaBitQ, 2024)
  • Jegou, H., Douze, M., Schmid, C. Product Quantization for Nearest Neighbor Search. TPAMI 2011.