Is your feature request related to a problem?
Disk-based vector search was added in OpenSearch 2.17. This feature uses binary quantization to decrease the memory footprint of vector search while keeping recall high. While disk-based vector search is successful at keeping recall high for some datasets, other data sets have recall less than 0.9 out of the box. We can use the two techniques discussed in this RFC, Asymmetric Distance Computation (ADC) and Random Rotation (RR), to increase the recall on some of these datasets.

In order to maintain high recall, disk-based search uses two phases. The first phase searches a binary quantized index for an oversampled number of neighbors. The second phase rescores and reduces these oversampled neighbors using exact search.

Currently, the first phase quantizes each 4-byte floating point entry in a vector into a single bit, then computes its distance to neighbors using hamming distance.

While this approach achieves high recall on some datasets, it does not perform well on others.

We can see that for some datasets, the recall for on-disk (32x compression) is above 0.9 out of the box:

However, the success of this approach is dataset dependent. There are data sets that are well below 0.9 out of the box:

In general, recall can be improved by increasing number of documents we rescore (via increasing oversample_factor). However, because rescoring has a random access pattern to disk, more rescoring leads to slower latencies. So recall is improved, but the recall/search latency tradeoff is not.

What solution would you like?

Reduce the impact of quantization errors through combining two separate optimizations:

1. Asymmetric Distance Computations (ADC)
2. Random Rotation (RR)

I am opening as a single RFC instead of several because the recall benefits of ADC+RR are much higher than the recall benefits of ADC or RR separately. There is also a search latency tradeoff for these techniques.

Asymmetric Distance Computation (ADC)

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. For instance, a full-precision 768-dimension float32 vector will use around 3 kB memory, but the same binary-quantized vector will use 100 B memory. While this is a 32x difference, the scale is small compared to the ~3 gB required to index 1M binary quantized documents (the added overhead from 3 kB vs 100B is not significant).

We can use ADC to preserve the full-precision vectors during search. This cuts down the error introduced in stage 2).

At a very high level, ADC scales our query vector close to 0 and 1. Each entry q_d in the query vector is modified via: q_d = (q_d - x_d) / (y_d - x_d). x_d is the mean of all document entries quantized to 0 (the below threshold mean) and y_d is the mean of all document entries quantized to 1 (the above threshold mean). Intuitively, the query is transformed through a linear interpolation of the above and below threshold means. This implies that an entry in our query vector that is very close to the below threshold mean will be transformed to a value near 0 and an entry close to the above threshold mean will be close to 1. However, this scheme allows for values besides just 0 and 1 which is where the better accuracy comes from.

Random Rotation (RR)

One fact about binary quantization (a type of scalar quantization) is that each 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 some of the variance is ”smoothed“ from the second dimension into the first dimension. See below for an illustration.

Random rotation can help smooth uneven variance across dimensions, which improves the effectiveness of k-NN search under binary quantization, since binary quantization treats all dimensions equally.

What alternatives have you considered?

• Increase oversampling factor to achieve 0.9 recall out of box for the above datasets.
  The issue with this alternative is that it is naive and does not address the fundamental sources of error introduced in binary quantization (it does not account for uneven information across dimensions and still introduces quantization error in two stages). It will also increase the amount of random disk IO for fetching the full-precision vectors. I believe, based on the fact that we are achieving >0.9 recall on some datasets and <0.9 on others out of the box, that solely increasing oversampling factor is not the correct next step to improve the recall for disk-based vector search.

Benchmark Results

Benchmark Setup

1. Random rotation (RR).
2. Asymmetric distance calculation (ADC).
3. Asymmetric distance calculation and random rotation (ADC+RR).

• m=16
• ef_construction=256
• ef_search=256
• oversample_factor = 5.0 if dimensions < 1000 else 3.0

Note that these experiments were conducted on a single shard/single segment one-machine cluster. We expect recall to be higher for multiple segments and multiple shard setups since there will be more hnsw graphs constructed in those cases (as opposed to a single hnsw graph).

Recall Changes

ADC+RR leads to good recall gains for some datasets, especially for datasets with a low recall (a high number of false positives). However, ADC+RR does not show improvements across the board and there are some datasets with small regressions.

Here is an enlarged recall plot for (ADC+RR):

Latency impact

Indexing Impact

The main performance hit comes when we force merge segments into a single segment. The reason for this is that all vectors must be rotated before being sent to the faiss index. We do not store an extra copy of the rotated vectors due to the memory overhead and engineering complexity. One optimization we could look into implementing is to store rotated vectors in the source, then undo the rotation before returning the vectors. Alternatively we could simply store only the rotated vectors (if the user only cares about the document ids of the vectors and not the vectors themselves). Already k-NN does this something similar to support cosine similarity in faiss (store normalized vectors so IP and cosine similarity are equivalent).

ADC Design

High Level Design

Indexing Changes

Search Changes

Whenever this ADC-enabled index is searched, the new distance computer’s set_query and distance_to_code methods are used for asymmetric computation within the hnsw search code.

After the search concludes, the path is the same as before, with rescoring handled by preexisting code. Any rescoring is performed with the original non-transformed vector against the non-quantized document vectors. The filtering code path is not affected.

See the LLD section for a sequence diagram covering searching and caching as well as more details about the alteration strategy.

Out of Scope

• Using ADC during indexing to build a better hnsw graph. We would need to explore this direction further to see if the recall gains are large enough to offset what will be a large increase in indexing time.
• Automatically deducing when ADC should be enabled/disabled. We elaborate on this option in the alternatives considered section, but this document does not include the auto design.

LLD

Faiss Index Alteration Strategy

Search sequence diagram

Transformation Formulae

Additional Memory Requirements

• Need to store (d/ 8) * 256 additional floats for the batched distance.
• Total cost: (d / 8) * 256 * 4 = 128*d bytes.

• Need to store (d / 8) * 256 * 2 additional floats for the batched distance.
• Need to store a copy of the above and below threshold means used to transform the query vector ( 2 * d floats)
• Finally need partitions (3 * d floats)
• Not strictly necessary but makes implementation easier.
• Total cost: 4 * ((d * 64) + (d * 2) + (d * 3)) = 276*d bytes.

Batching Optimization

Random Rotation Design

High Level Design

1. Sample each entry in the matrix from a standard normal random variable.
2. Use Gram-Schmidt to orthonormalize the matrix.

Low Level Design

Train Flow

Indexing Flow

Search Flow

Open Questions

• Due to merge time regressions, should we store the rotated vectors in memory?
• We do something similar in the cosine space for faiss, where we store the normalized vectors in source.
• Rotation, like normalization, is an invertible operation. We can preserve the option of undoing this rotation by logging the entire random rotation matrix and its transpose. (the transpose of the rotation matrix is its inverse since the rotation matrix, due to its generation process, is orthogonal.) However, this approach may break if data is downloaded from opensearch and then re-indexed, since it will be rotated multiple times. This is in contrast to normalization, where normalization only affects the vectors during the first indexing step.

User Experience - Recommended Changes to k-NN Interface

We recommend giving users control over ADC+RR via an index mapping parameter. The P0 goal for 3.1 is to introduce low-level configuration changes under the encoder configuration. enable_adc and random_rotation can be set to true/false to enable/disable each behavior. They are off by default to avoid unexpected latency increases.

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,
		  "random_rotation": true,
		  "enable_adc": true
                }
              }
            }
        }
      }
    }
  }
}

In the future we can add a higher-level index mapping parameter named enhance_search or boost_recall or boost_search_recall with boolean true/false options. enhance_search/boost_recall should be false by default to prevent unexpected latency increases.

PUT /adc-index
{
  "settings" : {
    "index": {
      "knn": true
    }
  },
  "mappings": {
    "properties": {
      "vector_field": {
        "type": "knn_vector",
        "dimension": 768,
        "space_type": "l2",
        "data_type": "float",
        "mode": "on_disk",
        "compression_level": "32x",
        // new enable adc+rr mapping parameter
        "enhance_search": true
      }
    }
  }
}

Alternatives Considered

Enable by Default

Enable by default but decrease oversampling

Enable based on characteristics of index (auto mode)

Coauthors