usearch: Bug: Issues index dtype=i8 with Inner Product Metrics

Describe the bug

Hi, I am using uSearch with Integer 8 index dtype. I am having 928K embedding which I try to add to both i8 and float16 index with Inner Product Metrics and then search 10 starting embedding to get top 10 matches. I see with float16 I get same vector getting recognised in top 10 but with I8 I didn’t get them. Also when I change metrics from MetricKind.Inner Product to MetricKind.L2sq those vectors starts coming but using this the distances are getting scaled differently(distances for IP are of order 0.61365813 and for l2sq 4517 maybe these are also because of i8) which I am not able to understand. Also adding embedding to MetricKind.InnerProduct with I8 dtype is too slow.

Steps to reproduce

I use following code to create and populate index with I8 dtype:-

searcher = Index(
 ndim=1024,
 metric=MetricKind.InnerProduct,
 dtype="i8",
 connectivity=32,
 expansion_add=128,
 expansion_search=64,
 multi=False,
)

searcher.add(range(len(embeddings)), embeddings, log=True)
matches = searcher.search(embeddings[:10], 10)
print(matches.keys)

I get following results: image

when I only change metric=MetricKind.L2sq I start getting the expected embeddings (same index as first key). Note:- With other dtype like f16,f32 MetricKind.InnerProduct works completely fine.

Expected behavior

Ideally I should get something like this with I8+ MetricKind.InnerProduct The following is result I get with MetricKind.L2sq: image

USearch version

2.11.7

Operating System

Ubuntu 22.04

Hardware architecture

x86

Which interface are you using?

Python bindings

Contact Details

keshusharmamrt@gmail.com

Are you open to being tagged as a contributor?

  • I am open to being mentioned in the project .git history as a contributor

Is there an existing issue for this?

  • I have searched the existing issues

Code of Conduct

  • I agree to follow this project’s Code of Conduct

About this issue

  • Original URL
  • State: closed
  • Created 3 years ago
  • Reactions: 3
  • Comments: 29 (24 by maintainers)

Commits related to this issue

Most upvoted comments

@keshusharmamrt @adolfogc @kmkolasinski, I believe this issue is resolved now. I’ve extended the docs to highlight the improved behavior. Let me know if the issue persists 🤗

On older versions I’ve made this mistake.

    // Unfortunately we can't use the `_mm512_dpbusd_epi32` intrinsics here either,
    // as it's assymetric with respect to the sign of the input arguments:
    //      Signed(ZeroExtend16(a.byte[4*j]) * SignExtend16(b.byte[4*j]))
    // So we have to use the `_mm512_dpwssd_epi32` intrinsics instead, upcasting
    // to 16-bit beforehand.
    ab_i32s_vec = _mm512_dpwssd_epi32(ab_i32s_vec, a_vec, b_vec);
    a2_i32s_vec = _mm512_dpwssd_epi32(a2_i32s_vec, a_vec, a_vec);
    b2_i32s_vec = _mm512_dpwssd_epi32(b2_i32s_vec, b_vec, b_vec);

Hey @ashvardanian , @keshusharmamrt has prepared very simple example which shows that for the same data when using different metrics and int8 quantization we are getting unexpected results. It looks that there is a bug in the int8 quantization (maybe only for python client). You can see it that for dot metric the order of keys is random, but for l2sq is fine, but values of distances are too large. Everything works as expected for f16 and f32 quantization. We also compared usearch with faiss and qdrant for the same HNSW parameters and dot metric of normalized vectors.

Connectivity Expansion Add Expansion Search
32 128 64

Our results for 1M of embeddings of size 1024

Method Recal@1
usearch f16 0.98672
usearch int8 0.91227
qdrant int8 0.96034
qdrant int8 (with rescore) 0.98555
faiss int8 0.98278

For faiss we use the index setup from usearch benchmark repository

As you can see the results for usearch int8 are far from faiss and qdrant equivalents.

@ashvardanian final remarks and conclusions after spending more time on this issue:

  1. Indeed scaling vectors values to range -1 and 1 improves recall for the test vectors of dim=96. Something which bothers me is that with this approach we are loosing some potential information as int8 range is (-128, 127) but usearch only uses (-100, 100), with this truncation we drop about 20% of potential information while bucketing. This 20% maybe important in some cases.

  2. I think it would be nice if this -1, 1 scaling should be explicitly mentioned in the docs or readme, maybe usearch could do some validation of the input vectors to warn the user, that the vectors are not scaled optimally.

  3. There is also one potential problem with int8 quantization, which can be suprising for unaware users i.e. if vectors values are larger than +/-1 quantization will create overflow issues. Here is an example: image you can imagine that the value flip can introduce some dramatic changes in the distance values.

  4. It looks like there is indeed a bug in the “Inner Product” metric, as according to documentation and the code IP should compute 1 - dot(a, b), but when testing it locally it returns different values, here is an example image and different results for f16 image

From this you can see that IP is actually computing dot(a, b) / ||a|| ||b|| . This also explains why IP metric is producing terrible recall as the code expects the distance not similarity measure. However, I don’t see where it is defined in the code, I found this in the code: https://github.com/unum-cloud/usearch/blob/5ea48c87c56a25ab57634a8f207f80ae675ed58e/include/usearch/index_plugins.hpp#L977 which seems to be correct. I use usearch version 2.12.0.

  1. Regarding my previous comment, please check the benchmarking scripts and the recall function. You can easily check that for incorrect groudtruth shape array it will overestimate recall@1 by large marging. This is especially visible for int8.

Hi @ashvardanian @kimihailv we tried last thing. We took the benchmarking script from https://github.com/unum-cloud/usearch-benchmarks/tree/main and we tried to compare the metrics on a smaller dataset which is base.10M.fbin. Here is what we got:

  1. We though we can use groundtruth.10K.ibin to verify metrics together with query.10K.fbin and base.10M.fbin, but it seems groundtruth.10K.ibin are not compatible with these query and train vectors.

  2. The repository only points to 1B dataset which is too large for us to process. Unfortunately, we couldn’t manage to find 100M data which are mentioned in the usearch benchmarking blog post.

  3. The vectors in query.10K.fbin are different from the official ones query.public.10K.fbin from the https://research.yandex.com/blog/benchmarks-for-billion-scale-similarity-search. Which means that query vectors has been selected, which raise various questions in our minds. For example, how we can reproduce this blog post (https://www.unum.cloud/blog/2023-11-07-scaling-vector-search-with-intel) metrics ?

  4. Also, there is a bug in the recall computation in the benchmarking code. In the run.py file groundtruth vector is of shape [10_000, 1] (https://github.com/unum-cloud/usearch-benchmarks/blob/main/run.py#L49)

groundtruth = load_matrix(groundtruth_path)[:, :1]

later you use these groundtruth indices to compute recall https://github.com/unum-cloud/usearch-benchmarks/blob/main/run.py#L82

recall_at_one = recall(nn_ids, groundtruth, ats=(1,))

but this should be replaced with

recall_at_one = recall(nn_ids, groundtruth[:, 0], ats=(1,))

or recall function should be fixed, as it adds new axis to the tensor causing a weird behaviour. Small example which demonstrates the issue image

  1. We tried to reproduce the results using base.10M.fbin vectors, but we are getting the same conclusions as when using our data. Integer 8 quantization is about 10% worse than f16. Here is the code you can use to verify it by yourself:
from tqdm import tqdm
import numpy as np
from usearch.index import Index
from usearch.io import load_matrix
from utils.metrics import recall


train_embeddings = load_matrix("data/base.10M.fbin")[:500_000]
query_embeddings = load_matrix("data/query.10K.fbin")


def best_match(query):
    return (train_embeddings @ query[:, None]).ravel().argmax()


groundtruths = []
for query in tqdm(query_embeddings, desc="Computing ground truths"):
    best_index = best_match(query)
    groundtruths.append(best_index)

groundtruths = np.array(groundtruths)


print("Benchmark f16 index")
i_half = Index(ndim=96, metric="cos", dtype="f16")
i_half.add(None, train_embeddings, log=True)
result = i_half.search(query_embeddings, 1, log=True)
recall_at_one = recall(result.keys, groundtruths, ats=(1,))
print(f" >> recall@1 = {recall_at_one[0]:.5f}")


print("Benchmark i8 index")
i_quarter = Index(ndim=96, metric="cos", dtype="i8")
i_quarter.add(None, train_embeddings, log=True)
result = i_quarter.search(query_embeddings, 1, log=True)
recall_at_one = recall(result.keys, groundtruths, ats=(1,))
print(f" >> recall@1 = {recall_at_one[0]:.5f}")

After running this code you will see

Benchmark f16 index
Add: 100%|██████████| 500000/500000 [00:17<00:00, 28269.71vector/s]
Search: 100%|██████████| 10000/10000 [00:00<00:00, 33128.90vector/s]
 >> recall@1 = 0.97220
Benchmark i8 index
Add: 100%|██████████| 500000/500000 [00:11<00:00, 42828.76vector/s]
Search: 100%|██████████| 10000/10000 [00:00<00:00, 51415.34vector/s]
 >> recall@1 = 0.86640

I think that this is a clear evidence that there is a bug in the int8 index, and we cannot simply solve it by adding some customer wrapper for index class. Hope this helps somehow.

Sure, the most obvious benchmark/example would be to generate random integers (instead of quantizing random floats), constructing the index, and measuring self-recall. Thats should work fine.

ok, last question: let’s say I would like to use int8 quantization and dot product metric. Are there some requirements for vectors to make it work properly ? do you have some example code which we could use and benchmark on our data for such scenario ?

A bit overwhelmed by other USearch-related projects, and haven’t had the chance to investigate deeper, @keshusharmamrt 😔

All libraries we have tried so far do the quantization under the hood, so things like bucketing, scaling etc is handled internally by the lib.

It’s true, most other libraries come with a lot of options for different quantization schemes. We don’t currently aim to enforce any of them or implement them in the C++ layer. But maybe we can add a couple of simple quantization schemes as utilities in the Python layer for now, Any chance you can contribute, @kmkolasinski?

Hey, we will check it later. I don’t know how it is later used in usearch, but we see the problem with dot distance, not cos. However I don’t see dot implementation there. The reason we use dot is that our vectors are already normalized, so cos and dot should provide same results.

hi, @ashvardanian ,Thanks for your support. Sharing the Details as you asked. index.hardware_acceleration Output:- image Usearch Version = 2.12.0 OS =Ubuntu 22.04.4 LTS CPU Model:- 13th Gen Intel® Core™ i5-13600HX × 20

I also believe, that you should may have wanted to use a different precision argument for binary indexes. It’s not mentioned on the main page, but is listed in the docs - b1. Here is the updated snippet:

@ashvardanian thank you for pointing that out! In that case, I think the snippet could use the ubinary precision provided by sentence_transformers:

quantize_embeddings(embeddings_f32, precision="ubinary")

Defined like so: https://github.com/UKPLab/sentence-transformers/blob/de3b29890344139d7b0e582cc7e00f18b98dc3d3/sentence_transformers/quantization.py#L380

I thought that since the int8 dimension was “lower”, the saved index would be smaller in size, but it turned out that using b1 also compressed the serialized index.

Also, perhaps this (using b1 and ubinary) could be suggested as an improvement to the semantic_search_usearch function of sentence_transformers, here:

https://github.com/UKPLab/sentence-transformers/blob/de3b29890344139d7b0e582cc7e00f18b98dc3d3/sentence_transformers/quantization.py#L238

What do you think?

BTW, superb library, thank you for making it available!

@keshusharmamrt, your points are extremely close to each other to differentiate them with a simple scale-up. You’d need a custom quantization scheme. I’d recommend to stick to f16. I’ve cross-validated the output keys with a slightly extended script:

import numpy as np
from usearch.index import Index, MetricKind

np.set_printoptions(formatter={"float": "{: 0.4f}".format})
np.random.seed(42)
num_centroids = 200
num_examples = 100
num_embeddings = num_examples * num_centroids
dim = 1024

centroids = np.random.uniform(low=-1, high=1, size=(num_centroids, dim))
offsets = np.random.uniform(low=-0.05, high=0.05, size=(num_embeddings, dim))
centroids = np.tile(centroids, (num_examples, 1))
embeddings = centroids + offsets
embeddings = embeddings / np.linalg.norm(embeddings, axis=1)[:, None]


for dtype in ["f32", "f16", "i8"]:
    print("Running test for dtype = ", dtype)
    for metric in [MetricKind.IP, MetricKind.Cosine, MetricKind.L2sq]:
        searcher = Index(
            ndim=dim,
            metric=metric,
            dtype=dtype,
            connectivity=32,
            expansion_add=128,
            expansion_search=64,
        )
        print("Running test ", dtype, metric, searcher.hardware_acceleration)

        searcher.add(range(len(embeddings)), embeddings, log=True)
        matches = searcher.search(embeddings[:5], 4)

        print("Keys = \n", matches.keys)
        print("Distances = \n", matches.distances)

        exact_distances = 1 - (embeddings[:5] @ embeddings.T)
        exact_keys = exact_distances.argsort(axis=1)
        exact_distances.sort(axis=1)
        if metric == MetricKind.L2sq:
            exact_distances = 2 * exact_distances

        print("Exact Keys = \n", exact_keys[:, :4])
        print("Exact Distances = \n", exact_distances[:, :4])

Hi, Thanks for your suggestion but It doesn’t seems to be working too.

Sharing the Example Code snippet which demonstrates the issue(using random uniform embeddings to demonstrate this)

import numpy as np
from usearch.index import Index, MetricKind

np.set_printoptions(formatter={"float": "{: 0.4f}".format})
np.random.seed(42)
num_centroids = 200
num_examples = 100
num_embeddings = num_examples * num_centroids
dim = 1024

centroids = np.random.uniform(low=-1, high=1, size=(num_centroids, dim))
offsets = np.random.uniform(low=-0.05, high=0.05, size=(num_embeddings, dim))
centroids = np.tile(centroids, (num_examples, 1))
embeddings = centroids + offsets
embeddings = embeddings / np.linalg.norm(embeddings, axis=1)[:, None]


for dtype in ["f32", "i8"]:
    print("Running test for dtype = ", dtype)
    for metric in [MetricKind.IP, MetricKind.Cosine, MetricKind.L2sq]:
        print("Running test ", dtype, metric)
        searcher = Index(
            ndim=dim,
            metric=metric,
            dtype=dtype,
            connectivity=32,
            expansion_add=128,
            expansion_search=64,
        )

        searcher.add(range(len(embeddings)), embeddings, log=True)
        matches = searcher.search(embeddings[:5], 4)

        print("Keys = \n", matches.keys)
        print("Distances = \n", matches.distances)

        exact_distances = 1 - (embeddings[:5] @ embeddings.T)
        exact_distances.sort(axis=1)
        if metric == MetricKind.L2sq:
            exact_distances = 2 * exact_distances

        print("Exact Distances = \n", exact_distances[:, :4])

I get following observations by running above code:-

  • for f32 we see that Distances are equal to Exact Distances
  • for i8 - we get completely different values for each metric and differ by large margin. Also for int8 L2sq and Cos seem to return similar order.
  • for i8 with Inner Product the keys are ordered incorrectly, distances are negative.
  • We use L2 normalized vectors so IP and Cos metrics should give the same results Maybe this code snippet can help understand issues we are facing with Integer 8 dtype.

Hi @keshusharmamrt! Can you please try the Cosine distance and share the dtype and shape of embeddings?