Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search

1 INTRODUCTION

• Dimension-wise quantization keeps code length tied to original dimensionality, limiting compression choices and the ability to reduce bits for faster search.Fixed lengths may also misalign with SIMD bit-widths.Source: §1 · pp. 1–2
• After information-aware projection, variance has a long-tailed distribution, concentrating most information in a low-dimensional subspace.This motivates treating projected dimensions differently during quantization.Source: §1 · p. 2
• MRQ quantizes the projected vector using arbitrary bit lengths and models residual distance contributions with lightweight statistics and error bounds.Its multi-stage computation progressively refines distances, using the full vector when exact computation is needed.Source: §1 · p. 2, Figure 1 · p. 2
• Up to 3× higher search efficiency than existing approaches while preserving comparable accuracy, according to the paper’s evaluation.The evaluation benchmarks MRQ against strong baselines including HNSW and RabitQ.Source: §1 · p. 2

2.1 AKNN Search and Methods

• AKNN search seeks high recall with minimal computational cost; IVF methods search selected clusters, while graph methods traverse neighbor links from an entry node.The paper focuses on IVF- and graph-based methods.Source: §2.1 · pp. 2–3

2.2 Quantization Techniques

• Codebook-based quantization offers flexible compression ratios, but distance computation relies on table lookups and floating-point additions that are difficult to accelerate with SIMD.Hardware-aware optimizations may constrain codebook sizes or degrade accuracy.Source: §2.2 · p. 3
• Dimension-wise methods support efficient bitwise or low-precision computation, but their code length is tied to the original dimensionality, restricting compression and hardware alignment.For example, a 960-dimensional vector produces a 960-bit binary code.Source: §2.2 · p. 3

3.1 Problem Analysis

• Naively truncating dimensions to improve compression can introduce severe bias in distance estimation and degrade AKNN accuracy.The analysis frames the challenge as minimizing information loss while extracting useful information from discarded residual dimensions.Source: §3.1 · p. 3

3.2 Observation

• After PCA, the first 512 OpenAI-1536 dimensions capture nearly 90% of total variance, while 128 DEEP dimensions retain 90%.These examples illustrate the long-tailed variance distribution observed after PCA.Source: §3.2 · p. 3
• PCA concentrates information in leading dimensions, while residual norm can refine distance estimates and residual variance can provide error bounds.The paper contrasts this differentiated treatment with randomly dropping or truncating dimensions.Source: §3.2 · pp. 3–4

4.1 Vector Decomposition

• PCA concentrates information in a small number of dimensions, so MRQ quantizes a user-controlled projected subspace to support flexible compression ratios.The remaining dimensions form a residual component.Source: §4.1 · p. 4, §4 · p. 4
• The overall distance combines projected-subspace norms and a quantized inner product with residual norms and a residual inner product.The projected inner product can be represented with a d-bit binary code.Source: §4.1 · p. 4

4.2 Multi-Stage Distance Computation

• Precomputing base-vector norms leaves query-time norm calculations to be done once per query, after which the remaining work is evaluating projected and residual inner products.The norm component is C1; the quantized and residual inner-product terms are C2 and C3.Source: §4.2 · p. 5
• The residual inner product contributes minimally to total distance and can be omitted, while PCA-based decorrelation lets quantization and residual errors be analyzed separately.For centered data, Chebyshev’s inequality bounds residual error; the two error bounds are combined additively.Source: §4.2 · p. 5
• Choosing projection dimension d to match SIMD widths, such as 128, 256, or 512 bits, makes the quantized inner product amenable to hardware acceleration.The binary codes can be processed with SIMD instructions such as POPCNT on AVX2/AVX-512 registers.Source: §4.2 · p. 5
• MRQ re-ranks candidates using a lower-bound distance: candidates above the current top-K threshold are pruned, while others receive more accurate distance computation.The later stages use the original projected inner product and, if needed, the residual inner product for exact distance.Source: §4.2 · p. 5

5 INTEGRATE WITH EXISTING METHOD

• MRQ can be integrated with IVF-based methods, which partition data into clusters represented by centroids.The paper uses IVF for its relatively simple implementation and compact index size.Source: §5 · p. 5, §5.1 · p. 5

5.1 Preprocessing Process

• Preprocessing applies PCA, computes residual norms, builds an IVF index from projected vectors, and quantizes the projected vectors using an approach similar to RabitQ.PCA-rotated vectors serve as base vectors because Euclidean distances are preserved under the same transformation.Source: §5.1 · p. 6

5.2 Query Process

• At query time, MRQ rotates and quantizes the query, scans the top N_probe clusters, estimates candidate distances, and computes exact distances for candidates passing the threshold check.N_probe sets the number of clusters scanned, balancing efficiency and accuracy.Source: §5.2 · p. 6
• A residual-error bound supports pruning candidates before exact distance computation, and the memory layout is optimized for cache efficiency.The pruning condition is dis′_o − m·σ < τ.Source: §5.2 · p. 6

5.3 Discussion

• For efficiency-oriented deployment, MRQ selects d as the smallest power of two at least 128 that captures at least 80% of total variance; this rule delivers near-optimal performance.The rule is presented as a way to avoid repeatedly rebuilding the index to search for a good trade-off.Source: §5.3 · p. 6
• MRQ can be implemented in parallel or distributed IVF systems, but PCA requires global statistics obtained through distributed PCA or single-machine sampling.The authors plan to further explore distributed AKNN search under this framework.Source: §5.3 · p. 6

6.1 Experiment Settings

• Evaluation covers eight public datasets, measures recall@20 and QPS, and compares IVF-RabitQ and IVF-MRQ variants with HNSW.The datasets include established benchmarks and embeddings from recent models.Source: §6.1 · p. 7

6.2 Experiment Results

• MRQ is 2× faster than RabitQ on GIST with 1/7 the bits, 2.6× faster on OpenAI-1536 with 1/3, and 3.4× faster on OpenAI-3072 with 1/6.Figure 5 presents the time–accuracy trade-off; MRQ also outperforms HNSW in most cases, including 5.85× faster on GIST at high recall levels.Source: §6.2 · p. 7, Figure 5 · p. 8
• MRQ preprocessing takes half the time of RabitQ and one-quarter of HNSW, while its index uses over 5× less memory than HNSW and 2× less than IVF-RabitQ.The reported space excludes base vectors.Source: §6.2 · p. 7, Figure 6 · p. 8
• MRQ uses 1/8–1/3 as many bits as RabitQ while pruning 96%–98% of exact distance computations, 1–2% below RabitQ’s more-than-99% prune rate.MRQ+’s second-stage PCA projection distances achieve a nearly 100% prune rate and provide additional efficiency gains.Source: §6.2 · pp. 7–8, Figure 7 · p. 8

(a) GIST

• In real AKNN search scenarios, a grid search over projection dimensions in steps of 64 found that the empirically chosen d=128 for GIST and d=512 for OpenAI-1536 achieved near-optimal search performance across the grid.Source: §6.2 · p. 8, (a) GIST · p. 8

7 CONCLUSION

• MRQ decomposes vectors into a quantized component over user-controllable dimensions and a residual component modeled with lightweight statistical summaries.The projected dimensions enable arbitrary compression ratios, while multi-stage distance computation combines the components for efficient and accurate search.Source: §7 · p. 8
• Experiments show that MRQ improves search efficiency with negligible index construction time and storage overhead.Source: §7 · p. 8
• Future work will investigate distributed processing techniques for large-scale vector datasets.Source: §7 · p. 8

A.1. Extra Related Work

• Re-ranking addresses recall loss from approximate distances by recomputing exact distances for a larger candidate set before selecting the final top-k neighbors [26] [27] [28] [63].It is widely used in disk-based AKNN indexes, where compressed vectors are in memory and full-precision vectors are on disk [63].Source: §7.1 · p. 11
• RabitQ [28] uses error bounds to discard candidates whose true distance is guaranteed to exceed the current k-th neighbor’s distance, avoiding exact distance computation for them.Source: §7.1 · p. 11
• Error-bound methods guarantee search accuracy, whereas re-ranking requires an empirically set range to meet an accuracy target.RabitQ’s error-bound optimization is tied to code length equaling vector dimensionality, a constraint MRQ aims to remove.Source: §7.1 · p. 11

A.2. Extra Discussion

• PCA-rotated image, text, and audio embeddings consistently show long-tailed variance distributions.Source: §A.2 · p. 11
• Cumulative variance differs by dataset: Word2Vec captures less than 80% using its top 50% of dimensions, while GIST exceeds 80% using only 10%.Source: §A.2 · p. 11
• The dimensions required to preserve 80% of variance range from 5 for MSONG to 470 for OpenAI-3072; the selected projected dimensions achieve near-optimal search efficiency across datasets.Source: §A.2 · p. 11

• OPQ and 8-bit SQ are evaluated with empirical projection dimensions and unchanged quantization parameters, using a fixed reranking range to protect accuracy.The fixed range addresses the lack of probabilistic error bounds for OPQ and SQ.Source: §A.2 · p. 11
• MR-PQ and MR-SQ shift performance curves upward, delivering higher QPS at comparable recall than their original counterparts.The passage attributes the improvement to quantizing the variance-concentrated leading dimensions, reducing per-candidate computation and scanning memory traffic while residual error has negligible impact on distance estimation.Source: §A.2 · p. 11
• The centroid experiment applies k-means to projected approximate vectors instead of original full-dimensional vectors, producing approximate IVF centroids.Source: §A.2 · p. 11
• Figure 11 presents variance distributions of vectors after PCA.Source: Figure 11 · p. 12

(h) TINY

• MRQ outperforms IVF-RabitQ and IVF-OPQfsr on most datasets and substantially outperforms IVF-Truncate, even using quantized distances alone for reranking without multistage computation or memory-layout optimizations.Source: Figure 12 · p. 12, (h) TINY · pp. 12–13
• Without reranking, standard PQ fails to reach 90% recall across datasets, and using fewer bits further degrades accuracy.Source: Figure 12 · p. 12, (h) TINY · p. 12
• Projected centroids incur almost no recall loss on GIST and slightly outperform original centroids on OpenAI-1536, while significantly reducing IVF-index training time.The projected centroids use 128 dimensions for GIST and 512 for OpenAI-1536, versus all dimensions for the original centroids.Source: (h) TINY · p. 12
• The baselines include memory-matched IVF-PQ at 32× compression, IVF-Truncate without reranking, and reranked RabitQ, OPQ-4bit-fastscan, and truncation comparisons.The truncation baseline matches MRQ’s bit budget but lacks PCA-based flexible separation of leading and residual dimensions.Source: (h) TINY · p. 12