Asymmetric Distance Computation (ADC)

The defining feature of ADC is the asymmetric nature of its distance computation. Unlike symmetric methods, ADC calculates distances between an uncompressed query vector and compressed database vectors. This asymmetry is crucial because the original, high-fidelity query vector is compared against a quantized approximation of the database vector. This preserves more information from the query side, leading to a more accurate distance approximation than if both vectors were compressed (symmetric computation).

ADC is not a standalone compression method; it is the distance calculation protocol used with Product Quantization (PQ). In this system:

• Database vectors are compressed offline using PQ, splitting them into subvectors and replacing each with a codebook centroid index.
• At query time, the uncompressed query vector is split into the same subvectors.
• Distances are computed by looking up pre-computed distance tables between the query's subvectors and the PQ codebook centroids, then summing these partial distances. This lookup-table approach is the engine of ADC's speed.

ADC enables a favorable operational trade-off. By storing only compact PQ codes (e.g., 8 bytes per vector instead of 128 bytes for a full-precision vector), it achieves massive memory footprint reduction, often 10x or more. This allows billion-scale vector datasets to reside in RAM. The cost is a loss in distance calculation precision versus an exhaustive search. However, ADC's asymmetric design minimizes this accuracy loss compared to symmetric PQ, making it a preferred choice for high-recall, memory-constrained applications.

ADC is commonly deployed in hybrid, multi-stage indexes to balance speed and accuracy. The most prominent example is the IVFADC index in Facebook AI Similarity Search (Faiss). This architecture combines:

1. A coarse quantizer (Inverted File, IVF) that narrows the search to a subset of promising database vectors.
2. A fine quantizer using PQ with ADC to compute precise distances within that subset. This structure provides fast candidate retrieval via IVF and accurate re-ranking via ADC, making it a production-standard for large-scale similarity search.

While ADC saves memory, it introduces computational overhead during a query. The system must perform multiple table lookups and additions—one for each PQ subspace—to reconstruct the approximate distance. This is more expensive than computing a simple dot product or L2 distance between two full vectors. However, this cost is fixed and predictable (O(m) for m subspaces), and is dramatically offset by the reduced number of comparisons needed due to efficient indexing structures like IVF.

ADC's advantages are clearest when contrasted with Symmetric Distance Computation (SDC). In SDC, both the query and database vectors are compressed using the same PQ codebooks before distance calculation. This double compression amplifies quantization error, leading to less accurate distance estimates. ADC avoids this by keeping the query in its original, high-dimensional space. The trade-off is that SDC can have even faster query times if its distance tables can be precomputed, but this is typically at a significant cost to search recall and accuracy.

Product Quantization (PQ) is the foundational lossy compression technique that enables ADC. It works by:

• Splitting a high-dimensional vector into multiple subvectors.
• Quantizing each subspace independently using a separate, learned codebook.
• Representing the original vector by a tuple of codebook indices (codes). ADC specifically refers to the distance calculation between an uncompressed query and these PQ-compressed database vectors, which is more accurate than symmetric PQ-to-PQ distance computation.

Symmetric Distance Computation (SDC) is the alternative to ADC where both the query vector and the database vectors are compressed using the same Product Quantization codebooks. Distance is then approximated using pre-computed lookup tables of distances between codewords.

• Key Difference: SDC is faster but less accurate than ADC because it introduces quantization error on both sides of the distance calculation.
• Use Case: Often used for re-ranking a very small candidate set where speed is paramount and the query can be compressed offline.

IVFADC is a canonical composite index structure in Facebook AI Similarity Search (Faiss) that combines two techniques for hierarchical search:

1. Inverted File (IVF) for coarse quantization: Partitions the dataset into clusters (Voronoi cells) and performs a non-exhaustive search by probing only the nearest clusters.
2. Asymmetric Distance Computation (ADC) for fine quantization: Compresses the residual vectors (original vector minus cluster centroid) using Product Quantization. This architecture provides a practical balance, using IVF for fast candidate generation and ADC for accurate, memory-efficient distance calculation within those candidates.

Residual Quantization is a refinement technique often used with PQ and ADC to improve accuracy. The process is:

• Calculate the residual vector by subtracting a coarse approximation (e.g., a cluster centroid from IVF) from the original vector.
• Apply Product Quantization to this residual vector instead of the original.
• The ADC distance is then computed between the query's residual and the PQ-compressed database residuals. This multi-stage approach allows the quantization to focus on the error from the first stage, leading to a more precise overall approximation.

Distance Approximation Error is the numerical difference between the true distance (e.g., exact L2) and the approximated distance calculated by a method like ADC or SDC. This error directly impacts search quality metrics like Recall.

• ADC vs. SDC: ADC typically has lower approximation error than SDC because the query vector remains uncompressed.
• Trade-off: The error is influenced by PQ parameters (number of subvectors, codebook size). Reducing error improves recall but increases memory for codebooks and computation for distance lookup tables.

Lookup Table (LUT) Precomputation is the critical optimization that makes ADC fast at query time. For a given uncompressed query vector:

• For each Product Quantization subspace, the distance between the query's subvector and every codeword in that subspace's codebook is precomputed.
• This results in m small lookup tables (where m is the number of subvectors).
• To compute the ADC distance to a database vector, the system simply sums the values fetched from these m tables using the vector's code indices. This replaces expensive floating-point operations with efficient table lookups and addition.