Asymmetric Distance Computation (ADC)

The fundamental distinction lies in which vectors undergo quantization:

• Symmetric Distance Computation (SDC): Both the query vector and the database vectors are compressed via product quantization. Distance is approximated between two quantized representations, introducing error on both sides.
• Asymmetric Distance Computation (ADC): Only the database vectors are compressed. The query vector remains in full floating-point precision.

The result: ADC eliminates the quantization error on the query side entirely. The distance between a precise query and an approximate database vector is inherently more accurate than the distance between two approximations.

ADC leverages pre-computed lookup tables to accelerate the distance calculation between a full-precision query and product-quantized database vectors.

The process:

1. The database vector is decomposed into M subvectors, each quantized to a centroid index from its sub-codebook.
2. For the incoming query, the distance from the query subvector to every centroid in each sub-codebook is computed once and stored in an M × K lookup table (where K is the number of centroids per sub-codebook).
3. The approximate distance to any database vector is then computed by summing M table lookups, avoiding expensive high-dimensional distance calculations.

This makes ADC both memory-efficient for storage and computationally fast during search.

ADC is the standard distance computation method paired with Product Quantization for nearest neighbor search.

• Encoding Phase: Database vectors are compressed using PQ. Each vector is represented by a short code (a sequence of centroid indices), not its original floating-point values.
• Search Phase: For a query vector, the ADC lookup table is built. The distance to every compressed database code is approximated by summing the pre-computed partial distances.

This pairing is the engine behind indices like IVFPQ, where an Inverted File Index first prunes the search space, and ADC computes the fine-grained residual distances to the remaining candidates.

The primary benefit of ADC is a superior accuracy-speed tradeoff compared to symmetric computation at the same memory footprint.

• Higher Recall@K: By preserving the query's full precision, ADC more reliably ranks true nearest neighbors at the top of the result list. The quantization error is isolated to the database side.
• Negligible Speed Overhead: The cost of building the lookup table for a full-precision query is a small, one-time overhead per search, making it the default operational mode in libraries like FAISS for virtually all PQ-based indices.

In practice, ADC provides a 'free' accuracy boost over SDC with no meaningful increase in query-time latency.

ADC enables massive compression of the database while retaining high search fidelity:

• Database Storage: Only the short PQ codes (typically 8-64 bytes per vector) need to be stored in memory, not the original high-dimensional vectors. For a billion-scale dataset, this can reduce storage from terabytes to gigabytes.
• Codebook Storage: The full-precision sub-codebooks must be retained to reconstruct the lookup table distances for each query. These codebooks are small relative to the database size.
• Query Handling: The query vector itself is ephemeral and processed in full precision, requiring no persistent storage beyond the duration of the search.

This asymmetry is ideal for read-heavy workloads where the database is static or infrequently updated but queries arrive in real-time.

The Facebook AI Similarity Search (FAISS) library provides a canonical implementation of ADC within its product quantization indices.

• The IndexPQ class stores database vectors as compressed PQ codes.
• During a search, the search() method automatically performs asymmetric distance computation by default, computing exact query-to-centroid distances and using them to approximate query-to-database distances.
• For composite indices like IndexIVFPQ, ADC operates on the residual vectors—the difference between the query and the coarse cluster centroid—further improving accuracy by quantizing only the local distribution.

This built-in behavior makes ADC the standard, high-accuracy mode for any engineer using FAISS for large-scale vector search.

The foundational compression mechanism enabling ADC. High-dimensional vectors are decomposed into subvectors, each quantized independently using a distinct codebook.

• Mechanism: The original vector is split, and each subvector is mapped to its nearest centroid.
• ADC Role: During search, the query vector remains full-precision, and distances are computed using pre-calculated lookup tables.
• Trade-off: Compression ratio vs. quantization error.

The contrasting approach where both the query and database vectors are compressed via quantization before distance calculation.

• Accuracy Loss: Introduces quantization error on the query side, degrading recall compared to ADC.
• Use Case: Preferred only when query-side compute or transmission bandwidth is severely constrained.
• Key Distinction: ADC retains full query precision, yielding strictly higher accuracy for the same compression ratio.

A composite indexing strategy that directly leverages ADC. An Inverted File Index provides coarse partitioning, while Product Quantization compresses residual vectors.

• Pipeline: Coarse quantizer assigns query to nearest partitions, then ADC computes precise distances to compressed database vectors within those cells.
• Benefit: Balances high recall from IVF with low memory footprint from PQ, using ADC to maximize final accuracy.

The specific vector representation compressed in ADC-based indices. The coarse centroid is subtracted from the original vector, leaving a residual that encodes fine-grained local information.

• Process: residual = original_vector - coarse_centroid
• ADC Application: The residual is compressed via PQ, and the query computes distances to these compressed residuals, adding back the coarse distance.
• Advantage: Reduces the variance of the data being quantized, minimizing quantization error.

The primary accuracy bottleneck that ADC mitigates. This distortion is introduced when mapping a continuous vector to its nearest discrete codebook centroid.

• ADC Mitigation: By keeping the query uncompressed, ADC eliminates query-side quantization error entirely.
• Measurement: Mean squared error between original and reconstructed vectors.
• Impact: Directly determines the recall ceiling of the compressed index.