Asymmetric Distance Computation (ADC)

The defining mechanism of ADC is its asymmetric treatment of query and database vectors. Database vectors are compressed (quantized) for storage efficiency, while the query vector remains in its original, full-precision form during distance calculation. This contrasts with Symmetric Distance Computation (SDC), where both query and database vectors are quantized, leading to compounded quantization error. By keeping the query vector pristine, ADC provides a more accurate approximation of the true distance to each compressed database point.

ADC is explicitly designed to deliver higher search accuracy than its symmetric counterpart for the same level of compression. The error in distance estimation comes solely from quantizing the database vector, not the query. This is critical for maintaining high Recall@k in production systems. For example, in a Product Quantization (PQ) setup, using ADC instead of SDC can improve recall by a significant margin (e.g., 5-15 percentage points) without increasing memory usage, as the compressed database representation remains identical.

ADC is most famously employed within the IVFPQ (Inverted File with Product Quantization) index architecture. Here, it operates on the residual vectors within each Voronoi cell:

• The Inverted File (IVF) acts as a coarse quantizer, narrowing the search to a few candidate cells.
• Product Quantization (PQ) compresses the residual vectors within those cells.
• ADC is then used to compute the approximate distance between the full-precision query residual and each PQ-compressed database residual. This combination makes IVFPQ a powerhouse for billion-scale searches, balancing speed, memory efficiency, and accuracy.

ADC introduces a specific cost-benefit profile:

• Memory Efficiency: Database vectors are heavily compressed (e.g., to 8-32 bytes per vector using PQ), enabling massive datasets to reside in RAM.
• Computational Overhead: Distance calculations are more expensive than with SDC. ADC requires reconstructing an approximation of the database vector from codes and computing the distance to the full-precision query. This is often accelerated via precomputed lookup tables that store partial distances between query subvectors and quantization centroids.
• The Trade-off: You exchange some CPU cycles for significantly higher accuracy at a fixed memory budget, which is almost always the preferred trade-off in large-scale retrieval.

A key performance optimization for ADC, especially with Product Quantization, is the use of precomputed lookup tables (LUTs). Since the query is full-precision and known at search time:

• For each subsegment (subvector) of the query, the distance to every possible centroid in the PQ codebook for that segment is precomputed.
• To compute the distance to a compressed database vector, the system simply fetches and sums the precomputed distances for each of its subvector codes from the LUTs.
• This transforms a complex floating-point operation into efficient memory-bound table lookups and additions, making ADC searches remarkably fast despite the asymmetric calculation.

ADC is not limited to Euclidean (L2) distance. It is equally crucial for Maximum Inner Product Search (MIPS), a common operation in recommendation systems. The asymmetric principle remains: the full-precision query vector's inner product is approximated with quantized database vectors. Libraries like Google's SCANN use advanced variants of anisotropic vector quantization specifically designed for ADC in the MIPS context, demonstrating the technique's fundamental importance across different similarity metrics.

Commercial and open-source vector databases implement ADC under the hood when using IVF-PQ composite indexes. The database engine handles:

• Transparent quantization of ingested vectors into PQ codes.
• Asymmetric distance calculation at query time, where the incoming query vector is not quantized.
• Integration with filtering, ensuring ADC works seamlessly with metadata filters. This abstraction allows developers to benefit from ADC's memory savings and accuracy without managing the low-level complexity of distance computations.

ADC is fundamentally the distance computation layer within an IVFPQ (Inverted File with Product Quantization) index. The implementation follows a two-stage process:

1. Coarse Quantizer (IVF): The query is compared to cluster centroids using full-precision distances to select the nearest Voronoi cells.
2. Fine Quantizer (PQ) with ADC: For each candidate vector in the selected cells, the distance is computed asymmetrically between the full-precision query and the PQ-compressed database vector. This involves looking up pre-computed distance tables between the query's subvectors and the PQ codebooks, a process far faster than reconstructing the database vector.

ADC is critically adapted for Maximum Inner Product Search (MIPS), a common similarity metric in recommendation systems. The asymmetric computation for MIPS involves:

• Transforming the database vectors via asymmetric transformation (e.g., adding a sufficiently large constant to make all entries non-negative).
• Quantizing the transformed database vectors.
• Computing the inner product between the full-precision query and the quantized, transformed database vector. Libraries like ScaNN from Google Research implement specialized anisotropic quantization techniques that are inherently asymmetric to optimize for MIPS accuracy.

ADC is often deployed as the first, fast retrieval stage in a two-stage search pipeline.

• Stage 1 (ADC): A compressed index (like IVFPQ) uses asymmetric distances to rapidly produce a shortlist of candidate vectors (e.g., top 1000).
• Stage 2 (Exact Re-ranking): The shortlist is re-scored using exact, full-precision distances between the original query and the original, uncompressed database vectors fetched from a separate store. This hybrid approach combines ADC's scalability with the perfect accuracy of exact search for the final result set.

For ultimate performance, ADC logic is implemented in low-level, optimized kernels:

• GPU Kernels: Libraries like FAISS write CUDA kernels that parallelize the ADC distance table lookups and accumulations across thousands of threads.
• Neural Processing Units (NPUs): Custom compilers for AI accelerators can map ADC's operations to specialized matrix multiplication and lookup units.
• CPU SIMD Instructions: Optimized C++ implementations use AVX-512 or Neon instructions to accelerate the subvector distance computations that underpin ADC. This hardware-level implementation is key to achieving low-latency search at scale.

Product Quantization (PQ) is the foundational compression technique that enables ADC. It splits a high-dimensional vector into subvectors and quantizes each subvector using a separate, learned codebook. The original vector is represented by a short code composed of the indices of the nearest centroid for each subsegment.

• Core Mechanism: Enables massive memory reduction by storing codes instead of full-precision vectors.
• Relation to ADC: In ADC, database vectors are compressed using PQ, while the query remains uncompressed for the distance calculation.

Symmetric Distance Computation (SDC) is the alternative to ADC where both the query vector and the database vectors are quantized using the same method (e.g., Product Quantization). Distances are approximated using only the quantized representations.

• Key Difference: SDC is faster but less accurate than ADC because it introduces quantization error on both sides of the distance calculation.
• Trade-off: ADC sacrifices some speed for significantly higher accuracy by keeping the query in full precision, making it preferable for applications where recall is critical.

IVFPQ is a composite indexing algorithm that combines an Inverted File (IVF) for coarse partitioning with Product Quantization (PQ) for fine compression. It is the most common practical framework where ADC is deployed.

• Two-Stage Search: 1) The IVF coarse quantizer selects a few relevant partitions (Voronoi cells). 2) ADC is performed within those cells using PQ-compressed residuals.
• Industry Standard: This architecture, implemented in libraries like FAISS, provides an optimal balance of speed, accuracy, and memory efficiency for billion-scale datasets.

Quantization Error is the distortion or loss of information introduced when a continuous-valued vector is compressed into a discrete representation (e.g., via PQ or Scalar Quantization). This error directly impacts the accuracy of approximate distance calculations.

• Impact on Search: Higher quantization error lowers recall, as the compressed representation may not accurately preserve true distances.
• ADC's Advantage: By keeping the query vector in full precision, ADC mitigates the compounding effect of quantization error, leading to a more accurate approximation of the true distance compared to SDC.

In a multi-stage vector index like IVFPQ, the Fine Quantizer is the component responsible for the high-resolution compression of vectors within a coarse partition. Product Quantization is the quintessential fine quantizer.

• Role: Compresses the residual vectors (the difference between the original vector and its coarse centroid) to enable dense, memory-efficient storage.
• ADC Execution: The fine quantizer's codebooks are used during ADC to compute the asymmetric distance between a full-precision query and the PQ-compressed database vector.

Recall@k is the primary evaluation metric for the accuracy of an Approximate Nearest Neighbor (ANN) search. It measures the proportion of the true k-nearest neighbors (found via exact search) that are present in the top k results returned by the approximate index.

• Formula: Recall@k = (Number of true neighbors in retrieved top k) / k.
• ADC's Objective: The design goal of ADC is to maximize Recall@k for a given memory budget and query latency by providing more accurate distance approximations than symmetric alternatives.