Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search

1 INTRODUCTION

• ANN systems face pressure to reduce memory because vector storage usually dominates total space, especially for high-dimensional embeddings.The introduction notes that memory use affects costs and user experience in commodity PCs, clouds, and mobile devices.Source: §1 · p. 1
• Existing RaBitQ supports only 32x compression, while moderate compression rates are sought to improve accuracy without retaining raw vectors for re-ranking.The paper identifies moderate rates such as 8x or 4x as the target.Source: §1 · p. 2
• Re-ranking from raw vectors stored on disks is orthogonal to vector compression and outside this study’s scope.That approach saves memory by compromising efficiency.Source: §1 · p. 2
• During querying, the method estimates distance from the most significant bits first, then accesses remaining bits for greater accuracy when needed.The most significant bits reproduce the original RaBitQ code and permit FastScan-based pruning.Source: §1 · p. 2
• The extended method uses shifted, normalized, randomly rotated vectors of B-bit unsigned integers, inheriting RaBitQ’s unbiased estimator and achieving asymptotic optimality in the space–error trade-off.The optimality concerns estimating the inner product of unit vectors.Source: §1 · p. 2
• At about 6.4x and 4.5x compression, the method stably achieves over 95% and 99% recall, respectively, without raw-vector re-ranking.It also produces more accurate distance estimates and higher recall than all baselines on all tested datasets at the same number of bits.Source: §1 · pp. 2–3

2.1 ANN Query

• The paper studies in-memory ANN with compressed vectors stored in main memory and raw vectors unavailable during querying to save space.Although the algorithm description assumes K=1, the method is stated to extend trivially to arbitrary K.Source: §2.1 · p. 3

2.2 The Quantization Method RaBitQ

• RaBitQ normalizes data and query vectors around a centroid, reducing raw-vector distance estimation to inner-product estimation on normalized vectors.The data-vector norm can be precomputed during indexing, while the query-vector norm can be computed at query time and shared across data vectors.Source: §2.2 · p. 3
• RaBitQ randomly rotates a predefined set of bi-valued unit vectors to form its codebook, then stores each data vector’s quantization code as a D-bit string.The codebook is determined by the random orthogonal matrix, which can be stored instead of the full codebook.Source: §2.2 · p. 3
• During querying, RaBitQ uses an unbiased estimator of the inner product of unit vectors and provides a probabilistic error bound.Its estimator supports estimating squared distances as well as inner products.Source: §2.2 · pp. 3–4

3.1 Motivations and Overview

• Padding vectors to (B·D) dimensions gives an error bound of O(1/D) with high probability, which decays slowly as more bits are used.The paper motivates a new extension because moderate compression rates require more accuracy than this padding approach offers.Source: §3.1 · p. 4

3.2.1 Constructing a Codebook.

• The codebook normalizes shifted B-bit integer-grid vectors and randomly rotates them, retaining unit-vector estimator conditions while enabling direct code-based inner products.For B=1, the codebook is the same as the original RaBitQ codebook.Source: §3.2.1 · pp. 4–5, Figure 1 · p. 4

3.2.2 Computing the Quantization Codes of Data Vectors.

• Quantization searches rounding-change thresholds along rescalings of P^-1o instead of enumerating the full grid, updating one coordinate at a time.The algorithm has time complexity O(2^B·D log D).Source: §3.2.2 · p. 5

3.3 Computing the Estimator

• The estimator ⟨ō, q⟩/⟨ō, o⟩ inherits RaBitQ’s unbiasedness and error bound when ō is the nearest codebook vector; its denominator can be precomputed.The query workflow applies the shared random transform and estimates squared distances from the quantization codes.Source: §3.3 · p. 5, §3.4 · p. 6

3.4 Summary and Theoretical Analysis

• The method achieves asymptotic optimality while remaining practically applicable, unlike the algorithmic proof in [2], whose variable-length integer storage is difficult to align.The paper presents its contribution as combining practicality with asymptotic optimality, rather than improving the theory itself.Source: §3.4 · p. 6

4.1 Using the Extended RaBitQ with IVF

• With IVF, extended RaBitQ can replace scalar quantization without storing raw vectors in RAM, improving accuracy at the same bit count while using the same computation implementations.The paper focuses on IVF; combining the method with graph-based indices is left for future work.Source: §4.1 · pp. 6–7

4.2 Conducting Distance Comparison with the Extended RaBitQ

• Distance checks first use the most-significant-bit RaBitQ code and its error bound, then read remaining bits only for candidates not discarded.For B=5 and B=9, the remaining bits correspond to 4-bit and 8-bit unsigned integers; implementations are also provided for B=3, 4, 7, and 8.Source: §4.2 · p. 7, Figure 2 · p. 7

5.1 Experimental Setup

• The evaluation uses six public real-world datasets, compares quantizers from 1 to 10 bits per dimension, and tests ANN with IVF against LVQ.The datasets include established ANN benchmarks and embeddings generated by advanced models; ANN performance is measured with single-thread search.Source: §5.1 · pp. 7–8

5.2.1 Space-Accuracy Trade-Off for Distance Estimation.

• Across tested datasets, RaBitQ (ext) has lower distance-estimation error than equal-bit baselines; for B>6, LVQ’s average relative error is 1.3x–3.1x larger.The comparison concerns average relative error; the paper also reports that the gap is larger for SQ and for B<6.Source: §5.2.1 · p. 8, Figure 3 · p. 9
• PQ and OPQ errors decay more slowly and usually fail to beat SQ or LVQ at ≥4 bits; RaBitQ (pad) has O(1/(B·D)) error decay, unlike the exponential-in-B decay of RaBitQ (ext), SQ, and LVQ.The paper reports the error trends for moderate compression rates.Source: §5.2.1 · p. 9

5.2.2 Time-Accuracy Trade-Off for ANN Query.

• With IVF, RaBitQ (ext) beats LVQ on time–accuracy trade-off at equal 4- and 8-bit settings; 4-, 5-, and 7-bit codes yield >90%, >95%, and >99% recall without reranking.At 5 bits, average distance ratio is nearly perfect across datasets, although recall is usually 97%.Source: Figure 4 · p. 10, §5.2.2 · p. 10

5.2.3 Time of Quantizing in the Indexing Phase.

• On OpenAI-3072, quantization at B=5 and B=7 takes a few minutes while sufficing for >95% and >99% recall, respectively.The indexing-time measurement includes multiplying vectors by P−1 and computing their quantization codes.Source: §5.2.3 · p. 10

5.2.4 Verifying the Scalability.

• On about 100 million 1,024-dimensional MSMARCO vectors, B=9 quantization takes around 2 hours, versus over 1 day to build IVF; B=4 reaches >95% recall without reranking using 56.94 GB instead of 433.47 GB raw.The ANN time–accuracy trade-off remains consistently better than LVQ on this dataset.Source: §5.2.4 · pp. 10–11

5.2.5 Verifying the Unbiasedness.

• For B=2 and B=3, regression of estimated against true squared distances has slope 1 and intercept 0, indicating unbiased distance estimation.The study uses around 10^7 normalized pairs from OpenAI-3072.Source: Figure 6 · p. 11, §5.2.5 · p. 11

5.2.6 Measuring the Empirical Formula among ε, D and B.

• With D=1000 or B=4 fixed in turn, the empirical formula ε < cε·2^-B/√D matches the 99.9% error quantile when cε=5.75.The study samples 5 × 10^6 pairs of unit vectors for each B,D pair.Source: §5.2.5 · p. 11

6 RELATED WORK

• PQ and SQ share a codebook-based indexing and distance-estimation framework, but are mostly used at large and moderate compression rates, respectively.The section reports that PQ does not outperform classical SQ on many datasets at moderate rates, while SQ can hardly produce reasonable accuracy at 1 or 2 bits per dimension.Source: §6 · pp. 11–12
• The study reports that its method outperforms methods empirically from 3x to 32x compression and achieves asymptotic optimality in theory.At moderate rates, PQ does not outperform classical SQ on many datasets; at larger rates, SQ can hardly produce reasonable accuracy.Source: §6 · pp. 11–12
• The study describes its vector compression and unbiased distance and inner-product estimation as applicable to attribute-filtering ANN and multi-vector search.Multi-vector search maps documents and queries to multiple vectors and uses MaxSim, aggregated from inner products.Source: §6 · p. 12
• Prior work establishes bit-based error bounds for inner-product and distance estimation, including an O(ε^-2 log(1/δ))-bit guarantee for error ε.The section also notes that the algorithmic proof of a further improvement for high accuracy is hardly practically applicable.Source: §6 · p. 12

7 CONCLUSION

• The method extends RaBitQ to moderate compression rates, aiming for promising recall without re-ranking, and has empirical and theoretical advantages over SQ and its variants.It estimates distances from the first code bits to help prune candidates before full-code distance computation.Source: §7 · p. 12
• First-bit distance estimates help prune candidates before distance computation based on full codes.The conclusion describes this as supporting efficient distance comparisons.Source: §7 · p. 12
• The authors say extensive experiments verify practical effectiveness and alignment between empirical performance and theoretical analysis.The paper notes possible adaptations for inner-product and cosine-similarity estimation, compression above 32x, and other ANN settings, while identifying neural-network training and inference as potential applications.Source: §7 · p. 12

A THE PROOF OF LEMMA 3.1

• It suffices to prove that some t > 0 makes the stated distance inequality hold for every y in G.The passage presents this as the condition needed to establish the preceding proof goal.Source: A THE PROOF OF LEMMA 3.1 · p. 15
• The passage says that establishing the positive quantity in (23) finishes the proof.Source: A THE PROOF OF LEMMA 3.1 · p. 15

B THE PROOF OF THEOREM 3.2

• The proof begins by restating a tail bound for coordinates of a uniformly distributed vector on the unit sphere.It invokes the bound for a random vector in S^(D−1).Source: B THE PROOF OF THEOREM 3.2 · p. 15
• Theorem 3.2 is proved by first establishing Lemmas B.2 and B.3.The proof frames its goal as bounding the estimator error.Source: B THE PROOF OF THEOREM 3.2 · pp. 15–16
• Lemma B.2 lower-bounds the squared distance from the rotated unit vector to every positively scaled grid vector by 1 − ⟨o, ō⟩².The proof uses the unit norm of o′ and the symmetry of G when choosing the maximizing normalized grid vector.Source: B THE PROOF OF THEOREM 3.2 · p. 15
• The proof of (32) uses t0 = L√D/2^(B−1); choosing each grid coordinate t0y[i] closest to f(o′[i]) gives coordinate error at most L√D/2^B.Source: B THE PROOF OF THEOREM 3.2 · p. 16
• The proof analyzes expected squared quantization error by summing coordinate errors, using identical coordinate distributions, and applying Markov’s inequality for a tail bound.It separately analyzes the expected value of the squared norm error and the second term in its bound.Source: B THE PROOF OF THEOREM 3.2 · p. 16
• A union bound combines two events, each with failure probability at most δ, yielding the stated result with probability at least 1 − 2δ.The proof then chooses a parameter to bound the right-hand side by ε.Source: B THE PROOF OF THEOREM 3.2 · p. 16

• A random orthogonal matrix projects a D-dimensional vector into d-dimensional space for estimating the distance between projected vectors.Source: C USING RABITQ WITH >32X COMPRESSION… · p. 16
• Equations (63) and (65) are based on the Johnson-Lindenstrauss Lemma [39].Source: C USING RABITQ WITH >32X COMPRESSION… · p. 16
• The inner product between two unit vectors in d-dimensional space can be estimated with RaBitQ.Source: C USING RABITQ WITH >32X COMPRESSION… · p. 16