[DOC] Asymmetric Distance Calculation and Random Rotation in k-NN

[finnroblin]

What do you want to do?

• Request a change to existing documentation
• Add new documentation
• Report a technical problem with the documentation
• Other

Tell us about your request. In 3.2 k-NN enhanced Disk Based Vector search to increase recall in binary indices. Asymmetric Distance Calculation (ADC) and Random Rotation (RR) are two separate user-configurable parameters that increase search quality (recall) at a slight performance penalty. The best performance/recall tradeoff is when they are used together which is why I'm clubbing both in a single documentation PR.

ADC and RR are each used within faiss binary indices. Random rotation is supported for 1 bit, 2 bit, and 4 bit quantization, while ADC is supported only for 1 bit quantization. For lower levels of quantization (2, 4 bits) the benefit of ADC is lesser so we do not support it.

The parameters can be specified like:

PUT vector-index
{
  "settings" : {
    "index": {
      "knn": true
    }
  },
  "mappings": {
    "properties": {
      "vector_field": {
        "type": "knn_vector",
        "dimension": 8,
        "method": {
            "name": "hnsw",
            "engine": "faiss",
            "space_type": "l2",
            "parameters": {
              "encoder": {
                "name": "binary",
                "parameters": {
                  "bits": 1,
// new parameters
		  "random_rotation": true,
		  "enable_adc": true
                }
              }
            }
        }
      }
    }
  }
}

ADC PR: opensearch-project/k-NN#2733

RR PR: opensearch-project/k-NN#2718

Version: 3.2

What other resources are available? Related issue containing algorithm background: opensearch-project/k-NN#2714

Full explanation of both methods:
Random Rotation

One consequence of binary quantization is that each vector entry is given equal weight during the quantization process. This leads to undesirable effects if the scale of variance is different in different dimensions.

For illustration imagine we have a 2-dimensional data distribution where the first dimension (x axis) has small variance and the second dimension (y axis) has high variance. The position of a vector in the second dimension may have more information than its position in the first dimension, but binary quantization treats each dimension as equally important. However, we can rotate the distribution and ”smooth“ variance (information) from the second dimension into the first dimension. See below for an illustration.

Beyond the above toy example, we have observed that image datasets like sift and gist respond well to random rotation. Intuitively this is expected since images typically have some high-information pixels and other pixels with less information. Without random rotation the embedding model may treat these pixels equally and lose more information upon 32x compression.

Asymmetric Distance Computation (ADC)

The idea behind ADC is to maintain a full-precision query vector, while rescaling it to have meaningful distance computations against binary-quantized document vectors. It’s asymmetric in the sense that our query vector is float32 type, but the document vectors are 1-bit binary types.

When we traverse through the hnsw graph, all of our distance computations are asymmetric: they compare the float query vector to binary index vectors with a custom distance calculation derived by the science team.

Essentially, ADC allows us to maintain more information about the query vector and get a higher quality search without a significant memory penalty. Naive binary quantization introduces error in two different stages: 1), when the document vectors are quantized during ingestion, and 2), when the query vectors are quantized during search.

While stage 1) is necessary to achieve memory savings due to the number of documents, stage 2) is less necessary for reducing memory requirements.
Essentially, ADC allows us to maintain the full precision of our query vectors and boost the quality of search without paying a significant memory penalty.

[onestardao]

Thanks for sharing this detailed write-up — especially on the impact of random rotation and asymmetric distance computation (ADC). We’ve been exploring a few adjacent areas recently, particularly how rotation-aware quantization can reduce semantic skew without sacrificing retrieval performance.

Curious: have you encountered any instability with binary quantization when vector density varies significantly between fields? We ran into this under mixed-mode ingestion, and ended up using a hybrid path-dependent quantization with WFGY-style semantic filtering. I’d be interested to hear if OpenSearch’s current setup has guardrails around this.

Let me know if there’s interest in digging deeper — happy to compare edge cases.

[kumarghp]

Hi, I noticed that OpenSearch supports multiple types of indexes with binary quantization, such as in this pull request: opensearch-project/k-NN#2805. Can you share any guidance on when to use each type? I am a bit confused about which one is suitable for which use case. Thanks!

[finnroblin]

Hi @kumarghp thanks for the question!

These two features (asymmetric distance calculation and random rotation) are intended to help boost recall when binary quantizing particularly difficult datasets. That is, datasets that lose a lot of information to compression/quantization. For example sift-128-euclidean is an image dataset and achieves only ~0.35 recall with 32x compression without these features, but 0.7 with ADC+RR. These changes are only supported for the faiss engine.

The proposal you linked will bring similar enhancements (though BBQ algorithm) to the lucene engine.

In both cases the use case will be very dataset-dependent, since these enhancements will increase recall at the cost of higher search latencies. Datasets with high out-of-box quantization recall won't need these enhancements.

[kumarghp]

@finnroblin Thanks for the quick reply! So is it fair to say that for most common use cases, the out-of-box quantization is enough and neither of the binary quantization types is really needed? Also, if both proposals bring similar improvements on difficult datasets, why does OpenSearch have two engines for binary quantization? Any trade-offs I might be missing?