Source-linked AI summary
RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search
Jianyang Gao, Cheng Long
TL;DR
Exact nearest-neighbor search in high-dimensional spaces is impractical at scale, and popular PQ methods lack theoretical error bounds despite empirical success. RaBitQ uses randomized quantization and an unbiased distance estimator with a sharp error bound; experiments report a better time-accuracy trade-off than PQ variants and alignment between empirical performance and theory.
Problem
Method
RaBitQ quantizes D-dimensional vectors into D-bit strings using randomly transformed bi-valued vectors and an unbiased distance estimator with a sharp probabilistic error bound.
Source: §1 · p. 2Results
RaBitQ has a better time-accuracy trade-off than PQ and its variants across tested datasets, and its empirical performance aligns with theoretical analysis.
Source: §1 · p. 2Takeaways & Limitations
Real-world experiments report that RaBitQ remains stable on tested datasets, including some where PQ variants fail.
Source: §1 · p. 2When two true query-to-vector distances are extremely close, RaBitQ estimates may rank them incorrectly, so re-ranking is necessary for high recall.
Source: §4 · p. 8
Abstract
from arXiv · showhide
Searching for approximate nearest neighbors (ANN) in the high-dimensional Euclidean space is a pivotal problem. Recently, with the help of fast SIMD-based implementations, Product Quantization (PQ) and its variants can often efficiently and accurately estimate the distances between the vectors and have achieved great success in the in-memory ANN search. Despite their empirical success, we note that these methods do not have a theoretical error bound and are observed to fail disastrously on some real-world datasets. Motivated by this, we propose a new randomized quantization method named RaBitQ, which quantizes $D$-dimensional vectors into $D$-bit strings. RaBitQ guarantees a sharp theoretical error bound and provides good empirical accuracy at the same time. In addition, we introduce efficient implementations of RaBitQ, supporting to estimate the distances with bitwise operations or SIMD-based operations. Extensive experiments on real-world datasets confirm that (1) our method outperforms PQ and its variants in terms of accuracy-efficiency trade-off by a clear margin and (2) its empirical performance is well-aligned with our theoretical analysis.
1 INTRODUCTION
High-dimensional ANN makes exact search impractical, while PQ and its variants lack theoretical error bounds and can fail on real-world datasets. RaBitQ combines randomized quantization with an unbiased distance estimator and efficient implementations; experiments report a better time-accuracy trade-off than PQ and alignment with the theoretical analysis.
1 INTRODUCTION
- PQ and its variants lack theoretical error bounds and have been observed to fail severely on real-world datasets.The paper cites MSong, where PQ's average relative distance-estimation error exceeds 50%.Source: §1 · pp. 1–2
- RaBitQ constructs a codebook from randomly transformed bi-valued vectors and encodes each quantized vector as a D-bit string.Its codebook is interpreted geometrically as randomly rotated vectors on the unit hypersphere.Source: §1 · p. 2
- RaBitQ's distance estimator is unbiased and has a sharp probabilistic error bound, unlike PQ's biased estimate without a theoretical bound.The estimator uses the geometric relationship among data, quantized, and query vectors.Source: §1 · p. 2
- For a single data vector, RaBitQ's bitwise implementation is 3x faster than original RAM-LUT PQ at the same accuracy.For batches, it adopts a SIMD strategy and is comparably fast to SIMD-based PQ with similar-length codes.Source: §1 · p. 2
- RaBitQ has a better time-accuracy trade-off than PQ and its variants across tested datasets, with empirical performance aligned with theoretical analysis.It also estimates distances more accurately with codes roughly half as long, and remains stable on datasets where PQ variants fail.Source: §1 · p. 2
2 ANN QUERY AND QUANTIZATION
The section defines in-memory ANN search and describes PQ's codebook and distance-estimation process, including its SIMD fast-scan implementation. It notes that PQ variants lack distance-estimation error bounds, while LSH guarantees a different, c-approximate query outcome.
2 ANN QUERY AND QUANTIZATION
- In-memory ANN retrieves the nearest database vector for a query, assuming raw vectors and indexes fit in main memory.The exposition assumes K=1, while the techniques can extend to general K.Source: §2 · p. 2
- PQ splits vectors into M subsegments, learns sub-codebooks with KMeans, and estimates distances by summing query-to-centroid lookup-table values.Each quantization code identifies one centroid per subsegment.Source: §2 · pp. 2–3
- PQ Fast Scan places quantized lookup tables in SIMD registers and reorganizes batches of 32 codes to estimate distances together.It changes the default setting from k=8 to k=4 and quantizes lookup-table values to 8-bit unsigned integers.Source: §2 · p. 3
- PQ variants lack theoretical error bounds on estimated distances; LSH instead guarantees a c-approximate query result, which does not guarantee high ANN recall.The LSH guarantee permits any vector within (1 + c) times a fixed radius r when one exists.Source: §2 · p. 3
3 THE RABITQ METHOD
The RaBitQ method estimates distances using normalized vectors, randomized binary codes, and transformed, quantized queries, with an unbiased inner-product estimator and a theoretical error bound. Its index and query phases support fast bitwise or SIMD-based computation.
3.1.1 Converting the Raw Vectors into Unit Vectors via Normaliza-
- Centering vectors at a centroid and normalizing them to unit length reduces raw squared-distance estimation to a unit-vector inner product; cluster-specific centroids can reduce data skewness.Source: §3.1.1 · p. 4
3.1.2 Constructing the Codebook.
- A uniformly random orthogonal rotation of the unit-vector codebook removes its preference for specific directions, and storing the rotation matrix suffices to represent the codebook.Source: §3.1.2 · p. 4
3.1.3 Computing the Quantized Codes of Data Vectors.
- On GIST’s 1 million 960-dimensional vectors using 32 CPU threads, indexing took 117s for RaBitQ, 105s for PQ, and 291s for OPQ; default codes use D bits versus PQ/OPQ’s 2D bits.RaBitQ stores each code as the signs of the inversely transformed data vector’s coordinates.Source: §3.1.3 · p. 4
3.2 Constructing an Unbiased Estimator
- RaBitQ has a sharp, asymptotically optimal additive absolute-error bound, with failure probability 2 exp(−c0 ε0²), decaying quadratically exponentially with ε0; the confidence-interval length grows linearly with ε0.The additive bound holds regardless of the data distribution; the multiplicative form applies when data vectors are well normalized.Source: §3.2.2 · p. 6
3.3 Computing the Estimator Efficiently
- For efficient distance estimation, RaBitQ computes the inner product between the binary data code and a transformed query, with both single-code bitwise and packed-batch SIMD implementations.Both RaBitQ and PQ have higher throughput on packed batches, which are feasible only in some scenarios.Source: §3.3 · p. 6, §3.3.2 · p. 7
3.3.1 Quantizing the Transformed Query Vector.
- Randomized uniform scalar quantization of the transformed query is unbiased, and Bq = Θ(log log D) suffices for high-probability error at the estimator’s order; Bq = 4 makes this error negligible empirically.Source: §3.3.1 · pp. 6–7
- Bitwise-and and popcount reduce inner-product computation to Bq operations on D-bit strings; RaBitQ averages 3x faster than PQ and OPQ at the same accuracy.Source: §3.3.2 · p. 7
- For SIMD distance estimation, RaBitQ splits each D-bit code into four-bit segments and uses LUTs to accumulate inner products, matching PQ’s implementation form.The approach preprocesses D/4 LUTs, each covering the possible four-bit strings, and accumulates lookups across the segments.Source: §3.3.2 · p. 7
- With default D-bit codes versus PQ and OPQ’s 2D-bit codes, RaBitQ achieves consistently better accuracy and greater efficiency for approximate-distance computation.Source: §3.3.2 · p. 7
3.4 Summary of RaBitQ
- The index phase normalizes data, samples a random orthogonal matrix P, and computes codes; the query phase transforms and quantizes the query, then estimates inner products and distances.The per-query transformation, normalization, and quantization costs can be shared across the data vectors; the inner-product estimate is unbiased.Source: §3.4 · pp. 7–8
1 Normalize the set of vectors (Section 3.1.1)
The query phase transforms the raw query into q′ using the sampled matrix P, then returns approximate distances between the raw query and raw data vectors.
1 Normalize the set of vectors (Section 3.1.1)
- A sampled random orthogonal matrix P is used to construct the codebook C_rand.Source: §1 · p. 8
- The query-phase inputs include the raw query, sampled matrix P, data-vector IDs, quantization codes, and precomputed values.Source: §1 · p. 8
- The algorithm outputs approximate distances between the raw query and raw data vectors.Source: §1 · p. 8
- The raw query vector is normalized and inversely transformed to obtain q′.Source: §1 · p. 8
2 Quantize q′ into ¯q (Section 3.3.1)
For each input data-vector ID, the query phase computes an estimated distance between the raw query and data vector using Equation (2).
4 RABITQ FOR IN-MEMORY ANN SEARCH
RaBitQ is paired with IVF for in-memory ANN search, using cluster-based distance estimation before exact-distance reranking. Its error bound guides reranking, though very close distances can still require exact evaluation for high recall.
4 RABITQ FOR IN-MEMORY ANN SEARCH
- RaBitQ is combined with IVF because graph-based search selects vectors sequentially, making SIMD batches difficult to form; applying the method to graph-based indexes is left for future work.The paper notes that combining quantization with IVF requires little effort, while competitive graph-based integration would require more work.Source: §4 · p. 8
- IVF clusters the data and assigns vectors to buckets; RaBitQ normalizes each vector using its cluster centroid, then estimates distances for the nearest-centroid clusters before exact-distance reranking.At query time, the algorithm selects the first N_probe clusters whose centroids are nearest to the query.Source: §4 · p. 8
- RaBitQ uses its distance error bound to guide reranking without a tuned count, dropping vectors whose lower bound exceeds the current nearest neighbor’s exact distance and exactly evaluating the rest.This strategy guarantees with high probability that the true nearest neighbor from the probed clusters is sent to reranking.Source: §4 · p. 8
- When true distances are extremely close, RaBitQ’s estimates may rank vectors incorrectly, so reranking is necessary to achieve high recall.The paper notes that distance estimation is inherently difficult for any method in this close-distance case.Source: §4 · p. 8
5 EXPERIMENTS
The experiments compare RaBitQ with quantization baselines on public datasets and evaluate both distance estimation and in-memory ANN search. Across the tested datasets, RaBitQ performs better than OPQ in ANN search, while its distance-estimation accuracy and efficiency compare favorably with PQ and OPQ.
5.1 Experimental Setup
- Experiments use six public datasets, compare RaBitQ with PQ, OPQ, LSQ, and HNSW, and assess distance-estimation and ANN accuracy and efficiency.For ANN, RaBitQ and OPQ are combined with IVF; the evaluation uses recall, average distance ratio, and queries per second.Source: §5.1 · p. 9
5.2.1 Time-Accuracy Trade-Off per Vector for Distance Estimation.
- At default code lengths, RaBitQ is more accurate than PQ and OPQ at comparable efficiency; at equal accuracy, it is significantly more efficient.Its code length is about D bits versus 2D for PQ and OPQ; its maximum relative error is at most 40% on tested datasets, while PQ and OPQ are around 100% except on SIFT and DEEP.Source: §5.2.1 · p. 10, Figure 3 · p. 11
5.2.2 Time in the Indexing Phase.
- On GIST, indexing takes a few minutes or less for RaBitQ, PQ, and OPQ, but more than 24 hours for LSQ.The authors attribute LSQ's cost to the NP-hard mapping of data vectors to quantization codes.Source: §5.2.2 · p. 10, Table 4 · p. 10
5.2.3 Time-Accuracy Trade-Off for ANN Search.
- RaBitQ consistently outperforms OPQ and HNSW on all tested datasets across ANN time-accuracy trade-offs, regardless of OPQ's re-ranking setting.OPQ's re-ranking candidate count has no single setting that works well across datasets; RaBitQ requires no tuning.Source: §5.2.3 · pp. 10, 12, Figure 4 · p. 11
- Across two datasets, recall nears perfect around ε0=1.9, error converges around Bq=4, and RaBitQ's estimates are unbiased while OPQ's are biased.The authors report that reducing Bq to 1 produces much larger error than using Bq=4.Source: §5.2.4 · p. 12, §5.2.6 · p. 12, Figure 7 · p. 12
6 RELATED WORK
The related-work discussion distinguishes RaBitQ from existing ANN and quantization approaches by its error guarantees and practical computation. It also identifies potential combinations with other ANN methods and applications beyond distance estimation.
Approximate Nearest Neighbor Search
- RaBitQ combines a sharp error bound with empirical performance, requires no parameter tuning, and supports efficient single-code distance estimation for integration with other ANN methods.The discussion notes that dedicated hardware-aware optimization for RaBitQ remains an open question.Source: §6 · p. 13
Quantization
- RaBitQ uses bi-valued vectors as binary representations and can be reduced to PQ computation to inherit existing hardware-aware optimization.The paper also notes that dedicated hardware-aware optimization for RaBitQ remains an open question.Source: §6 · p. 13
Theoretical Studies on High-Dimensional Vectors
- Prior short-code methods improve theoretical space complexity but require decompressing codes for distance computation, whereas RaBitQ supports efficient computation.The discussion describes prior methods as unsuitable for in-memory ANN because decompression and distance computation degrade to brute-force efficiency.Source: §6 · p. 13
Signed Random Projection
- Unlike signed random projection, RaBitQ targets unbiased inner-product and squared-distance estimates and bounds each data vector's distance with high probability.RaBitQ quantizes data vectors into bit strings but represents query vectors with 4-bit unsigned integers; the cited discussion says query quantization adds negligible error.Source: §6 · p. 13
7 CONCLUSION
The conclusion presents RaBitQ as combining empirical accuracy, a rigorous error bound, and efficient distance computation, while the included analysis studies the random projections underlying its guarantees.
7 CONCLUSION
- RaBitQ combines empirical accuracy and a rigorous error bound, with bitwise or SIMD implementations supporting its time-accuracy trade-off for in-memory ANN.The authors identify applying RaBitQ with graph-based indexes or other storage devices, and using it for cosine similarity or inner product, as research directions or potential applications.Source: §7 · p. 13
A THE PROOF OF LEMMA 3.1
- The proof of Lemma 3.1 decomposes the quantized vector into components along two orthogonal directions and an orthogonal residual.The directions are o and e1, where e1 is constructed from q and o.Source: A THE PROOF OF LEMMA 3.1 · p. 17
B THE ANALYSIS FOR THE CONCENTRATION PHENOMENON
- The appendix analyzes the expected value, concentration, and joint distribution of projections of the randomized quantized vector, summarizing results in Lemma B.3.It also reports empirical verification of the joint-distribution conclusions in Figure 8.Source: B THE ANALYSIS FOR THE CONCENTRATION… · p. 17
B.1 The Expected Value of ⟨ō,o⟩
- For dimensions from 10^2 to 10^6, the expected projection ⟨ō,o⟩ ranges from 0.798 to 0.800.The paper says this numerical stability matches observations in Section 3.2.1.Source: §B.1 · p. 17
B.2 The Concentration of ⟨ō,o⟩
- The projection ⟨ō,o⟩ is highly concentrated around its expectation and, with high probability, does not deviate by Ω(1/√D).The analysis derives this concentration from a Lipschitz-function bound on a random vector uniformly distributed on the unit sphere.Source: §B.2 · p. 18
B.3 The Joint Distribution of (⟨¯o, o⟩, ⟨¯o, e1⟩)
The analysis characterizes the joint distribution of the quantized vector's projections onto two orthogonal directions. It derives the result using the random-rotation construction and checks its predictions empirically.
B.3 The Joint Distribution of (⟨ō,o⟩, ⟨ō,e1⟩)
- The proof uses rotational invariance to reduce the analysis to two coordinate directions, then samples the random orthogonal transformation sequentially by rows.The first row determines the selected codeword; the next row informs its projection onto the second direction.Source: §B.3 · p. 18
- Lemma B.3 expresses the joint distribution of the two projections using an independent variable X1 distributed as p_{D−1}.The lemma also gives the expectation and concentration bound for ⟨ō,o⟩.Source: §B.3 · pp. 18–19
- Figure 8 reports a perfect match between empirical and theoretical results; its lower panel shows ⟨P̄x, o⟩ from 105 samples highly concentrated around its mean, with empirical mean matching theoretical expectation.Source: §B.3 · p. 19
C THE PROOF OF THEOREM 3.2
The proof establishes unbiasedness and an error bound for RaBitQ’s estimator, then uses probabilistic bounds to set the scalar-quantization precision. The resulting bit parameter is asymptotically smaller than that required by trivial bounds.
C THE PROOF OF THEOREM 3.2
- The estimator is unbiased: its error term has expectation zero, including for the non-collinear case analyzed in the proof.The proof treats the collinear case separately, where unbiasedness follows directly from the definition.Source: C THE PROOF OF THEOREM 3.2 · p. 19
- The proof analyzes the scalar-quantization contribution by bounding the inner-product approximation error and the range of the randomly rotated query coordinates.The passages identify the scalar error as |⟨x̄, q̄ − q′⟩| and note that concentration of q′ strengthens a trivial range bound.Source: D THE ANALYSIS FOR 𝐵𝑞 · p. 20
- Randomized uniform scalar quantization and concentration yield an overall error of O(1/√D) with high probability using B_q = Θ(log log D).The proof combines its probabilistic bounds with a union bound; trivial bounds require B_q = Θ(log D) for the same error bound.Source: D THE ANALYSIS FOR 𝐵𝑞 · p. 20
D.1 The Error of Randomized Uniform Scalar Quantization
Randomized uniform scalar quantization makes the coordinate-wise approximation errors independent, mean-zero, and bounded. Concentration bounds their sum, while concentration of the rotated query coordinates controls the quantization step size.
D.1 The Error of Randomized Uniform Scalar Quantization
- Independent, mean-zero coordinate errors bounded by Δ sum to an error of O(Δ) with high probability under Hoeffding’s inequality.The bound applies to the error in approximating ⟨x̄, q′⟩ by ⟨x̄, q̄⟩.Source: §D.1 · p. 20
D.2 The Analysis for Δ √︃
- For quantization step Δ, the coordinate range max_i q'[i] − min_i q'[i] is at most 2 max_i |q'[i]|, so Δ equals that range divided by 2B_q − 1.Source: §D.2 · p. 20
E DISCUSSION ON THE NORMALIZATION
The normalization discussion distinguishes an unconditional additive error bound from a multiplicative bound that assumes uniformity on the unit sphere. The ablations show that the codebook and estimator choices are integral to RaBitQ’s guarantees and empirical performance.
E DISCUSSION ON THE NORMALIZATION
- The multiplicative error corollary assumes normalized data vectors follow the uniform distribution on the unit hypersphere, while the additive bound does not assume a data distribution.The authors say normalization itself remains insufficiently explored and leave its rigorous study to future work.Source: E DISCUSSION ON THE NORMALIZATION · p. 21
- Across the datasets, code-bit entropy exceeds 99.9% of code length, which the authors interpret as evidence that centroid-based normalization is empirically effective.The entropy measure sums the entropy of each bit and normalizes by code length.Source: E DISCUSSION ON THE NORMALIZATION · p. 21
F DISCUSSION ON THE ABLATION STUDY
- RaBitQ’s codebook construction and distance estimator form an integral whole: ablating either removes theoretical predictability and disables error-bound-based ANN reranking.The discussion also notes that further heuristic optimization could improve empirical performance on datasets with promising properties.Source: F DISCUSSION ON THE ABLATION STUDY · p. 21, §F.1 · p. 21
F.1 The Ablation of the Codebook Construction
- Replacing RaBitQ’s randomized codebook with a learned heuristic codebook degrades both average and maximum relative distance-estimation error on GIST.The paper attributes the result to the learned heuristic process finding a suboptimal solution; Table 6 reports the ablation scope.Source: §F.1 · p. 22, Table 6 · p. 22
F.2 The Ablation of the Estimator
On GIST, RaBitQ’s estimator is unbiased, whereas the alternative estimator is biased and worsens distance-estimation quality. The reranking ablation also indicates that reranking is needed when close true distances make the guaranteed estimate insufficient for ranking.
F.2 The Ablation of the Estimator
- The proposed estimator is constructed to be unbiased; its ablation replaces it with an alternative that treats the quantized data vector as the data vector, as PQ does.The study collected 107 pairs from the first 10 query vectors and 106 GIST data vectors; Figure 11 shows estimated versus true inner products.Source: §F.2 · p. 22
- Using ⟨ō, q⟩ degrades average and maximum relative distance-estimation error and invalidates the original theoretical error bound.Without that bound, error-bound-based reranking is inapplicable; Table 7 gives the ablation scope.Source: §F.2 · p. 22, Table 7 · p. 22
F.3 The Ablation of the Re-Ranking
- When two data vectors have extremely close true distances to a query, reranking is necessary for high-recall ANN search.Figure 10 compares QPS–recall curves with and without reranking.Source: §F.3 · p. 22