Asymmetric Distance Computation for High Dimensional Vector Search

93 concepts55 papers1 proposal

When scaling vector search to millions or billions of high-dimensional embeddings, we inevitably run into a storage bottleneck. Keeping raw, high-precision floating-point vectors in memory becomes prohibitively expensive. To bypass this, modern retrieval systems compress database vectors into compact representations using techniques like product quantization, binarization, or sketching.

The traditional way to perform a search over this compressed data is Symmetric Distance Computation (SDC). In an SDC framework, when a user submits a query, the system compresses the query vector using the exact same method applied to the database, and then computes the distance between the two compressed representations. While SDC is fast, it suffers from a major flaw: it introduces quantization noise on both sides of the equation, compounding information loss and degrading search accuracy.

Asymmetric Distance Computation (ADC) solves this by exploiting a fundamental operational asymmetry: database storage costs are cumulative and persistent, whereas query processing costs are transient and isolated. As Kordopatis-Zilos et al. note, because a query is short-lived and processed one at a time, we do not need to compress it to save space. By keeping the query vector in its original, high-precision format and comparing it directly against the compressed database entries, ADC significantly reduces approximation error without adding a single byte to the database's permanent storage footprint.

The Mechanics of the Lookup Table

How can a system compute the distance between a raw, uncompressed query vector and a compressed database entry without decompressing the database entry first? Doing so naively would defeat the speed benefits of compression.

The trick lies in decoupling the distance calculation using Product Quantization (PQ) and precomputed Lookup Tables (LUT).

To understand how this works, let us look at a standard vector decomposition pipeline described by Wan et al.:

  1. Database Compression: A high-dimensional vector (e.g., 128 dimensions) is split into $M$ distinct sub-spaces (e.g., 8 sub-vectors of 16 dimensions each). For each sub-space, a codebook of centroids (typically 256) is learned via $K$-means. Every database vector is then compressed by mapping its sub-vectors to their nearest centroids. Instead of storing floating-point values, the database stores a sequence of $M$ integer indices (bytes).
  2. Query-Time Table Generation: When a high-precision query vector $q$ arrives, the system does not compress it. Instead, it breaks $q$ into the same $M$ sub-spaces. For each sub-space, it calculates the exact floating-point distance from the query's sub-vector to all 256 possible centroids in that sub-space's codebook. These values are stored in a small, temporary Lookup Table.
  3. Asymmetric Scanning: To evaluate a database item, the system reads its $M$ stored indices. It uses these indices to look up the precomputed distances in the LUT and sums them up.
Query (High-Precision) ──► Split into M Sub-vectors ──► Compute distances to all centroids ──► Populate LUT
                                                                                                  │
Database Item (Compressed) ──► Read M Integer Indices ────────────────────────────────────────────► Look up & Sum

As Jianfeng Wang et al. and Deguchi et al. demonstrate, this mechanism completely bypasses expensive floating-point vector arithmetic during the database scan. The exhaustive vector-to-vector operations are performed only once per query to populate the LUT. The actual search across millions of database entries is reduced to a series of fast table lookups and basic additions. Guo et al. show that this same asymmetric principle applies seamlessly to inner product spaces, enabling rapid Maximum Inner Product Search (MIPS) by aggregating pre-calculated inner products between the query and subspace centroids.

Quantization vs. Hashing: The Resolution Advantage

Before the widespread adoption of quantization-based ADC, similarity search relied heavily on symmetric binary hashing (e.g., Locality-Sensitive Hashing). In binary hashing, vectors are projected onto random hyperplanes and converted into bitstrings using a sign function. Distance is then approximated using the Hamming distance, which can be computed incredibly fast via bitwise XOR operations.

However, Jingdong Wang demonstrates that binary hashing suffers from severe information loss because the sign function discards the magnitude of the vectors. In contrast, dictionary-based quantization methods preserve structural information much more effectively.

For a fixed bit budget, quantization combined with ADC provides exponentially more distinct distance levels than binary hashing. As Klein and Klein point out, this increased granularity provides a much higher resolution for distance approximation. Instead of a coarse Hamming distance that lumps many distinct vectors into the same distance bucket, ADC allows for fine-grained ranking, which directly translates to higher recall in top-$K$ retrieval tasks.

There is, however, a computational trade-off. As Cao et al. observe, accessing memory via lookup tables introduces a hardware bottleneck that bitwise XOR operations do not face. While ADC requires more CPU cache coordination than symmetric binary matching, the dramatic leap in search precision usually justifies the minor latency overhead in modern systems.

Training for Asymmetric Inference

If a retrieval system is destined to use asymmetric distance computation during inference, the underlying embedding model should be trained to expect it. Standard metric learning frameworks often optimize embeddings using symmetric distances (e.g., computing the Euclidean distance between two uncompressed vectors in a batch). This creates a discrepancy between training and deployment.

To bridge this gap, Yuan et al. introduced an Asymmetric Triplet Loss. During training, the query representation is kept unquantized, while the database samples (anchors, positives, and negatives) are passed through a differentiable quantization layer. By minimizing a loss function that mirrors the exact asymmetric lookup process used during inference, the neural network learns to generate features that are explicitly robust to the distortions introduced by database compression.

The Broader Spectrum of Asymmetry

While product quantization is the most prominent application of this design pattern, the core philosophy—preserving query fidelity while compressing the database—extends across several domains:

  • Heterogeneous Precision Matching: In distributed environments where queries and data originate from devices with varying power constraints, systems often have to mix and match bit depths. Li and Li proved that forcing a high-precision query to down-sample to a low-precision database format causes unnecessary information loss; maintaining the query's original fidelity and using asymmetric estimators yields far more accurate similarity rankings.
  • Resolution Asymmetry in Vision: In mobile visual search, edge devices often suffer from bandwidth constraints when uploading query images. Tolias and Šuma demonstrate that systems can execute high-speed queries using low-resolution images on mobile devices while matching them against a high-resolution database, preserving discriminative power without requiring a corresponding reduction in the quality of the stored reference embeddings.
  • Asymmetric Feature Maps: Moving computational complexity entirely to the query side can also enable dynamic search parameters. Tolias showed that by evaluating multiple similarity kernels (such as different spatial scales) exclusively on the query side, systems can approximate complex multi-scale searches without needing to re-index or increase the storage requirements of the database.

Ultimately, asymmetric distance computation works because it aligns perfectly with the economics of search infrastructure. By concentrating computational precision where it is cheapest (the single, transient query) and compression where it is most critical (the massive, permanent database), ADC provides a highly optimized trade-off between memory efficiency and retrieval accuracy.

Key Foundational Work

Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces (2008) — contributed 3 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 59 papers
  2. Version 1 · 2026-10-04 · 75 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_asymmetric_distance_computation_d7d09704,
  title = {asymmetric distance computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-distance-computation/rdr_d7d0970466914a2aa5b748533feff9c5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_asymmetric_distance_computation_d7d09704_v2,
  title = {asymmetric distance computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-distance-computation/rdr_d7d0970466914a2aa5b748533feff9c5/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake