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:
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:
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
.githistory 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
- Use `b1` quantization for USearch As suggested by @adolfogc (in https://github.com/unum-cloud/usearch/issues/405) the USearch implementation should use `b1` instead of `i8` for binary representatio... — committed to ashvardanian/sentence-transformers by ashvardanian 3 years ago
- Use `b1` quantization for USearch (#2644) As suggested by @adolfogc (in https://github.com/unum-cloud/usearch/issues/405) the USearch implementation should use `b1` instead of `i8` for binary repre... — committed to UKPLab/sentence-transformers by ashvardanian 3 years ago
- Merge pull request #120 from ashvardanian/main-dev Add: Swift bindings & `int8` dot-products With these changes we can make USearch behavior more predictable for `int8` inputs. https://github.... — committed to ashvardanian/SimSIMD by ashvardanian 2 years ago
- Improve: `i8` quantization Now, instead of linearly scaling to [-100, 100] range, when quantizing `f32` to `i8`, we first normalize the vectors, and only then scale them to [-127, 127], using a broad... — committed to jaepil/usearch by ashvardanian 2 years ago
@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.
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
dotmetric the order of keys is random, but forl2sqis 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 anddotmetric of normalized vectors.Our results for 1M of embeddings of size 1024
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:
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.
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.
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:
you can imagine that the value flip can introduce some dramatic changes in the distance values.
It looks like there is indeed a bug in the “Inner Product” metric, as according to documentation and the code IP should compute
and different results for f16

1 - dot(a, b), but when testing it locally it returns different values, here is an exampleFrom 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 version2.12.0.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:We though we can use
groundtruth.10K.ibinto verify metrics together withquery.10K.fbinandbase.10M.fbin, but it seemsgroundtruth.10K.ibinare not compatible with these query and train vectors.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.
The vectors in
query.10K.fbinare different from the official onesquery.public.10K.fbinfrom 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 ?Also, there is a bug in the
recallcomputation in the benchmarking code. In the run.py filegroundtruthvector is of shape [10_000, 1] (https://github.com/unum-cloud/usearch-benchmarks/blob/main/run.py#L49)later you use these
groundtruthindices to compute recall https://github.com/unum-cloud/usearch-benchmarks/blob/main/run.py#L82but this should be replaced with
or recall function should be fixed, as it adds new axis to the tensor causing a weird behaviour. Small example which demonstrates the issue
base.10M.fbinvectors, 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:After running this code you will see
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 😔
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
dotdistance, 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.
Usearch Version = 2.12.0
OS =Ubuntu 22.04.4 LTS
CPU Model:- 13th Gen Intel® Core™ i5-13600HX × 20
index.hardware_accelerationOutput:-@adolfogc, sure, that makes a lot of sense! I’ve proposed the patch.
@ashvardanian thank you for pointing that out! In that case, I think the snippet could use the
ubinaryprecision provided bysentence_transformers:Defined like so: https://github.com/UKPLab/sentence-transformers/blob/de3b29890344139d7b0e582cc7e00f18b98dc3d3/sentence_transformers/quantization.py#L380
I thought that since the
int8dimension was “lower”, the saved index would be smaller in size, but it turned out that usingb1also compressed the serialized index.Also, perhaps this (using
b1andubinary) could be suggested as an improvement to thesemantic_search_usearchfunction ofsentence_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: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)
I get following observations by running above code:-
Hi @keshusharmamrt! Can you please try the Cosine distance and share the dtype and shape of
embeddings?