RaBitQ Library

RaBitQ is designed as a drop-in replacement for binary quantization and (uniform) scalar quantization, offering several benefits:

• High Accuracy with Tiny Space: Provides state-of-the-art similarity estimates across various space budgets. The smallest representation uses a one-bit code per padded dimension plus per-vector factors.
• Fast Distance Estimation: Utilizes bitwise operations for speed. For batched scans in IVF and SymphonyQG, it leverages FastScan for optimized performance.
• Theoretical Error Bound: Provides an asymptotically optimal error bound for distance and inner product estimation, which can be used for reliable ordering and reranking.

RaBitQ provides two primary public metric choices for distance estimation:

1. METRIC_L2: Used for squared Euclidean distance estimation.
2. METRIC_IP: Used for Inner Product estimation.

Note on Cosine Similarity: There is no dedicated METRIC_COSINE. To perform a cosine search, you must normalize both your data vectors and your query vectors before performing an Inner Product (METRIC_IP) search.

Each element in the HNSW + RaBitQ index is stored using a specific layout to balance graph connectivity and quantized vector storage. The layout is as follows:

[number of edges]
[edges]
[cluster ID]
[external label]
[BinData (1-bit * dim + factors)]
[ExData (ex-bits * dim + factors)]

SymphonyQG combines graph search (from QG/NGT) with batched RaBitQ distance estimation. It uses FastScan to estimate neighbor distances. Visited vertices are scored using either stored raw vectors or quantized codes.

Quantization Settings:

• quantization_bits=0 (default): Uses raw vectors.
• quantization_bits=4 or 8: Uses QG-quantization where quantized vectors share a rotated global centroid.

Refinement Process: During refinement, the system temporarily reconstructs source vectors to estimate distances to stored target codes. Because these estimates are directional, reverse edges are also rescored. When using raw vectors, refinement uses the owned raw vectors; no full reconstructed-vector cache is maintained.

RaBitQ uses inner-product kernels to compute the similarity between quantization codes ($\mathbf{x}$) and rotated query vectors ($\mathbf{q}_r'$). The library selects the optimal implementation at runtime based on available hardware instructions, specifically supporting AVX2/FMA and AVX-512. When available, AVX-512 VPOPCNTDQ is utilized for optimized popcount-specific execution paths.

The kernels are categorized into two main types:

1. Binary Code Kernels: Used for computing inner products between binary vectors and floating-point query vectors.
2. Multi-bit Code Kernels: Used for computing inner products with multi-bit quantization codes.

The IVF implementation uses a specific data layout to optimize searching:

1. [batch data]: 1-bit code and factors.
2. [ex_data]: Either the code for remaining bits (quantized mode) or the original float32 vectors (raw mode).
3. [ids]: PIDs of vectors, organized by clusters.
4. [cluster_lst]: Metadata for the clusters.

Quantized vs. Raw Mode:

• Quantized Mode: Uses total_bits (1–9) to store compressed codes. nbits() returns the bit width.
• Raw Mode: Set by using total_bits=32. In this mode, ex_data stores the original float32 vectors. The index owns a copy of the input, so the original data can be released after construction. nbits() returns 32 in this mode. Raw mode files include a magic/version header and rotation state, allowing them to be loaded without an external dataset.

RaBitQLib offers two rotation methods depending on your requirements for speed and memory:

1. FFHT + Kac’s Walk (RotatorType::FhtKacRotator)

This is the default method. It combines Fast Hadamard Transform (FFHT) with Kac’s Walk principles. It is highly efficient for high-dimensional vectors.

• Time Complexity: $O(D \log D)$
• Space Consumption: $4D$ bits

2. Random Orthogonal Transformation (RotatorType::MatrixRotator)

This is the classical Johnson-Lindenstrauss Transformation using a random Gaussian matrix orthogonalized via QR decomposition.

• Time Complexity: $O(D^2)$
• Space Consumption: $D^2$ floating-point numbers

For multi-bit codes, the kernel unpacks packed unsigned values and accumulates them using selected AVX2/FMA or AVX-512 kernels.

The dispatch table supports between zero and eight extended bits. Consequently, full RaBitQ codes can contain anywhere from one to nine bits per dimension.

RaBitQ improves vector search recall through an optimized reranking strategy that minimizes expensive disk I/O (retrieving raw vectors). Unlike standard ANN algorithms that typically rerank a fixed number of candidates, RaBitQ uses its theoretical error bounds to skip candidates that cannot possibly be part of the $K$ nearest neighbors.

By comparing a candidate's lower bound of estimated distance against the upper bound of the distances of current nearest neighbors, RaBitQ can achieve nearly perfect recall while reranking significantly fewer than $K$ vectors. It specifically targets only those vectors located on the boundaries of the $K$-nearest neighbor sets.

RaBitQ provides different index structures to balance memory, latency, and recall. Choose the one that fits your workload:

Implementation Details:

• IVF: Stores quantized vectors by default. To retain original float32 vectors for reranking, set nbits=32.
• HNSW: Searches quantized vectors instead of accessing raw vectors during search.
• SymphonyQG: Uses additional memory and multiple codes per vector to optimize access patterns.