You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "benwtrent (via GitHub)" <gi...@apache.org> on 2024/12/17 22:22:53 UTC
[PR] Binary vector format for flat and hnsw vectors [lucene]
benwtrent opened a new pull request, #14078:
URL: https://github.com/apache/lucene/pull/14078
This provides a binary vector format for vectors. The key ideas are:
- Centroid centered vectors
- Asymmetric quantization
- Individually optimized scalar quantization
This allows Lucene to have a single scalar quantization format that allows for high quality vector retrieval, even down to a single bit.
For all similarity types, on disk it looks like.
| quantized vector | lower quantile | upper quantile| additional correction | sum quantized components|
| - | - |- | - | - |
| (vector_dimension/8) bytes | float | float | float | short |
During segment merge & HNSW building, another temporary file is written containing the query quantized vectors over the configured centroids. One downside is that this temporary file will actually be larger than the regular vector index. This is because we use asymmetric quantization to keep good information around. But once the merge is complete, this file is deleted. I think eventually, this can be removed.
Here are the results for _Recall@10|50_
| Dataset | old PR | this one | Improvement |
| --- | --- | --- | --- |
| Cohere 768 | 0.933 | 0.938 | 0.5% |
| Cohere 1024 | 0.932 | 0.945 | 1.3% |
| E5-Small-v2 | 0.972 | 0.975 | 0.3% |
| GIST-1M | 0.740 | 0.989 | 24.9% |
Even with the optimization step, indexing time with HNSW is only marginally increased.
| Dataset | OLD PR | This One | Difference |
| --- | --- | --- | --- |
| Cohere 768 | 368.62s | 372.95s | +1% |
| Cohere 1024 | 307.09s | 314.08s | +2% |
| E5-Small-v2 | 227.37s | 229.83s | < +1% |
The consistent improvement in recall and flexibility for various bits makes this format and quantization technique much preferred.
Eventually, we should consider moving scalar quantization to utilize this new optimized quantizer. Though, the on disk format and scoring will change, so, I didn't do that in this PR.
supersedes: https://github.com/apache/lucene/pull/13651
Co-Authors: @tveasey @john-wagster @mayya-sharipova
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2710473036
> > Could you please also share other parameters of your benchmark (ndoc, maxConn, beamWidthIndex, fanout, etc.)
>
> I have lost my test environment and I regrettably didn't write all this down. however, these are some best guesses.
Enabling others to be able to repro benchy results is important for any and all benchmarks!
Can we fix `knnPerfTest.py` (in luceneutil) to do a better job outputting the key parameters along with its recall/CPU results? I.e. is it missing some columns in the table it produces?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "gaoj0017 (via GitHub)" <gi...@apache.org>.
gaoj0017 commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2573030521
Hi @msokolov , the discussion here is not only about the blog posts but also related to the pull request here. In this pull request (and its related blogs), it claims a new method without properly acknowledging the contributions/inspirations from our extended RaBitQ method as we have explained in our last reply. Besides, we believe this discussion is relevant to the Lucene community because Lucene is a collaborative project, used and contributed to by many teams beyond Elastic.
Thanks @mikemccand for your kind words - we truly appreciate them! It is also an honor to us that RaBitQ and the extended RaBitQ are seen as impactful in improving industry productivity.
Our responses to @benwtrent are as follows.
Point 1 in our last reply: This has been ignored in Ben’s reply. We would like to emphasize once again that the so-called “BBQ” method from Elastic is largely based on our RaBitQ method, with only minor modifications - this can be reflected in the previous PRs. Yet Elastic has repeatedly referred to BBQ as their new algorithm without acknowledging RaBitQ. For example, in a [press release](https://www.elastic.co/blog/whats-new-elasticsearch-platform-8-16-0 ), Elastic states that "Elasticsearch’s new BBQ algorithm redefines vector quantization," omitting any reference to RaBitQ. This is unacceptable and particularly unfair to other teams who have openly acknowledged their use of RaBitQ. We request that our RaBitQ method should be properly credited in all existing and future blogs, press releases, pull requests, and other communications regarding the “BBQ” method.
Point 2 in our last reply: In the related blog that describes the method in this pull request, it states “Although the RaBitQ approach is conceptually rather different to scalar quantization, we were inspired to re-evaluate whether similar performance could be unlocked for scalar quantization” - this is not true since this target has already been achieved by our extended RaBitQ method. Your team should not have made this mis-claim by ignoring our extended RaBitQ method since we circulated our extended RaBitQ paper to your team more than three months ago. In addition, our extended RaBitQ method proposed the idea of searching for the optimal parameters of scalar quantization for each vector (for details, please refer to our [blog](https://dev.to/gaoj0017/extended-rabitq-an-optimized-scalar-quantization-method-83m)). The method in this pull request has adopted a highly similar idea. For this reason, we request that in any existing and potentially future channels of introducing t
he method in this PR, proper acknowledgement of our extended RaBitQ method should be made.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2678033882
Hi @benwtrent, that's an amazing amount of work.
I wonder where can I find the code for the benchmarks that you are mentioning in the description? Thanks!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2679022162
> I wonder where can I find the code for the benchmarks that you are mentioning in the description? Thanks!
@lpld I patched a version of Lucene util, sort of like this: https://github.com/mikemccand/luceneutil/compare/main...benwtrent:luceneutil:bbq
But obviously, it needs to be updated. Once this can get merged, I will update Lucene Util to make testing and benchmarking this simpler. Right now its admittedly a bit of a hack.
Benchmarking with Lucene Util is its own adventure if you haven't done tackled it before. Some of the vector sets mentioned in the description are custom ones that I built that aren't really available anywhere for direct download (e.g. I generated vectors with e5-small directly and downloaded and munged GIST-1M to work directly with Lucene Util).
However, Lucene Util has a script to download a bunch of Cohere 768 vectors from 🤗.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2713454213
Hey @lpld
> May I also ask about the selection of datasets being used for the benchmarks? How do you choose them?
I haven't tested with SIFT, though be sure to use euclidean distance when testing it. I would imagine that so few dimensions might not perform super well. There is just too much information loss.
But the datasets I have been utilizing are ones that are built with modern day transformer based models. Lucene Util has tooling for downloading and using Cohere multi-lingual (max-inner product, 768 dims).
Specifically, for this data format, we did testing with the following datasets and models:
- https://huggingface.co/Snowflake/snowflake-arctic-embed-l with dbpedia
- https://huggingface.co/intfloat/e5-small with dbpedia, hot-pot qa, quora, fiqa
- https://huggingface.co/thenlper/gte-base with hotpotqa, fiqa, dbpedia
- And of course, coherev3 multi-lingual https://huggingface.co/datasets/Cohere/wikipedia-2023-11-embed-multilingual-v3
- https://huggingface.co/datasets/Cohere/wikipedia-22-12-simple-embeddings
- GIST-1M (sibling dataset to sift), with euclidean and max-inner product.
If you are testing for a product, I would use the model that you are planning to use.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2569565637
To head this off, this implementation is not an evolution of RabitQ in any way. It's intellectually dishonest to say it's an evolution of RaBitQ. I know that's pedantic, but it's a fact.
This is the next step of the global vector quantization optimization done already in Lucene. Instead of global, it's local and utilizes anisotropic quantization. I am still curious as to what in particular is considered built on RaBitQ here. Just because things reach the same ends (various bit level quantization) doesn't mean they are the same.
We can say "so this idea is unique from RaBitQ in these ways" to keep attribution, but it seems weird to call out another algorithm to simply say this one is different.
I agree, Elastic stuff should be discussed and fixed in a different forum.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2698684914
@lpld here is my Lucene util changes: https://github.com/mikemccand/luceneutil/pull/348
> What exactly do the numbers in the description of this pull request mean? When you say that the recall for Cohere 768 is 0.938, is it the absolute recall value that you got from the benchmark, or is it some sort of ratio between the quantized and non-quantized recalls?
Its recall with oversampling. So, gathering the nearest 50 vectors for calculating the nearest 10 vectors. In a production environment, there would be a rescore phase between the initial gathering and providing the final 10 docs to the consumer.
> Do you have any ideas about what could be the reason for such a huge recall difference in the benchmark results on difference environments?
Additionally, I have found that I periodically get bitten by Lucene util trying to be helpful and storing the true nearest neighbor files. If you reindex your data, the `nn-*` files should be deleted as the doc ids changed. Though, those `nn-*` files containing the true nearest neighbors are very useful when adjusting query time parameters against he same index.
I think lucene util can be made better here when it comes to getting repeatable recall from previously stored nearest neighbors. The tricky part is making sure whatever methodology we use works with all the different test kinds lucene util does :/
> I was also trying to do some benchmarking with other public datasets (without luceneutil), and I got a little confused about how to correctly calculate the recall. I understand that recall is a ratio between the number of correct responses and the total number of responses. The total number of responses is straightforward, but the number of correct ones is a bit confusing to me.
Lucene util utilizes function score queries, which I think is the best way.
```
var queryVector = new ConstKnnFloatValueSource(query);
var docVectors = new FloatKnnVectorFieldSource(KNN_FIELD);
var query = new BooleanQuery.Builder()
.add(new FunctionQuery(new FloatVectorSimilarityFunction(similarityFunction, queryVector, docVectors)), BooleanClause.Occur.SHOULD)
.add(filterQuery, BooleanClause.Occur.FILTER)
.build();
```
This will do a raw floating point vector comparison against every vector that passes the filterQuery. That will give you the true nearest neighbors for a given `queryVector` and configured `similarityFunction`.
> However, in lucene unit tests a different query is used to get the correct neighbors from the index:
I think this might be a bug actually. It will actually due a full scan, but use the quantized vector scorers. What you actually want is the raw vector scores compared directly.
Then you simply compare set overlap given the doc ids (or some stored id field) when queried against the index.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2684703383
@benwtrent Thanks for your reply!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "gaoj0017 (via GitHub)" <gi...@apache.org>.
gaoj0017 commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2692580673
Thank you for acknowledging that our extended RaBitQ method proposes the idea of exploring different scalar quantization parameters on a per-vector basis for the first time and OSQ adopts this idea. OSQ differs from extended RaBitQ (which is a prior art before OSQ) in the detailed way of trying different parameters. Good to know that Elastic will provide a reference to our extended RaBitQ method in the code. We hope that proper acknowledgement of extended RaBitQ’s contribution of exploring different scalar quantization parameters on a per-vector basis will be provided when introducing OSQ in other channels (e.g., tweets, blogs and press releases) as well.
We welcome benchmarks of comparing our extended RaBitQ and OSQ by Elastic and other parties. These will help to see whether the changes made by OSQ on extended RaBitQ would bring true improvement on the space-accuracy trade-off. We hope that the comparison will be objective, comprehensive, and insightful.
For the community’s information, our codes of extended RaBitQ are fully open-source (https://github.com/VectorDB-NTU/Extended-RaBitQ). We will be happy to see that the community and industry teams will use the algorithms and even improve them further.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "tveasey (via GitHub)" <gi...@apache.org>.
tveasey commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2573444675
Just sticking purely to the issues raised regarding this PR and the blog Ben linked explaining the methodology...
> Although the RaBitQ approach is conceptually rather different to scalar quantization, we were inspired to re-evaluate whether similar performance could be unlocked for scalar quantization” - this is not true since this target has already been achieved by our extended RaBitQ method. Your team should not have made this mis-claim by ignoring our extended RaBitQ method since we circulated our extended RaBitQ paper to your team more than three months ago.
This comment relates to the fact that RaBitQ, as you yourself describe it in both your papers, is motivated by seeking a form of product quantization (PQ) for which one can compute the dot product directly rather than via look up. Your papers make minimal reference to scalar quantisation (SQ) other than to say the method is a drop in replacement. If you strongly take issue to the statement based on this clarification we can further clarify it in the blog. I still feel this is separate to this PR and it seems better to discuss that in a separate forum.
I would also reiterate that conceptually, our approach is much closer to our prior work on int4 SQ we [blogged](https://www.elastic.co/search-labs/blog/vector-db-optimized-scalar-quantization) about *last April*, which is what inspired it more directly.
> In addition, our extended RaBitQ method proposed the idea of searching for the optimal parameters of scalar quantization for each vector (for details, please refer to our [blog](https://dev.to/gaoj0017/extended-rabitq-an-optimized-scalar-quantization-method-83m)).
I would argue that finding the nearest point on the sphere is exactly equivalent to the standard process in SQ of finding the nearest grid point to a vector. Perhaps more accurate would be to say you've ported SQ to work with spherical geometry, although as before the more natural motivation, and the one you yourselves adopt, is in terms of PQ. This isn't related to optimising hyperparameters of SQ IMO.
You could argue perhaps that arranging for both codebook centres and corpus vectors to be uniformly distributed on the sphere constitutes this sort of optimization, although it would not be standard usage. At best you could say it indirectly arranges for raw vectors to wind up close in some average sense to the quantized vectors. However, I'd take issue with this statement because a single sample of a random rotation does not ensure that the corpus vectors are uniformly distributed on the sphere: using a single random rotation of, for example, a set of points which are concentrated somewhere on the sphere doesn't change this. You would have to use different samples for different vectors, but this eliminates the performance advantages.
Incidentally, this I think is the reason it performs significantly worse on GIST and indeed generally why we found small improvements across the board for binary. (Tangentially, it feels like a whitening pre-conditioner might actually be of more benefit to performance of RaBitQ. I also can't help but feel some combination of hyperparameter optimization and normalization will yield even further improvements, but I haven't been able to get this to workout yet.)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent merged PR #14078:
URL: https://github.com/apache/lucene/pull/14078
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2555050252
@gaoj0017 Thank you for your feedback!
Truly, y'all inspired us on improving scalar quantization. RaBitQ showed that it is possible to achieve 32x reduction while achieving high recall without product quantization. And, to my knowledge, we have attributed inspiration where the particulars of the algorithm were used.
As for this change, it is not mathematically the same or derived from y'all's new or old paper. Indeed, your new paper is interesting and provides the same flexibility to various bit sizes and shows that it's possible. However, we haven’t tested it, nor implemented it.
Here are some details about this implementation.
https://www.elastic.co/search-labs/blog/scalar-quantization-optimization
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2679008833
@gaoj0017
> The OSQ method (introduced in this PR) has its major idea similar to our extended RaBitQ method and our extended RaBitQ method is a prior art which achieves good accuracy at 1-bit/2-bit binary/scalar quantization for the first time.
Thank you for further clarifying what y’all are meaning by prior art, this helps us understand each of our “sticking” points.
Extended RaBitQ is, to our knowledge, the first thing to do something other than min/max quantization per vector. Indeed, extended RaBitQ has impressive numbers from y’all’s paper and work.
Our sticking point is that the quantization optimizations for OSQ are unique. While both are improving the quantization quality per vector, OSQ is going about it in a different way. Its direct scalar quantile optimization via anisotropic loss. Both of which find their roots in the linked research in the PR.
I will happily indicate in the code comments that extended RaBitQ is the first to do this more advanced quantization per vector. Because to our knowledge it is true.
We want to donate this to the Apache Lucene project and community so it can grow and evolve here.
Additionally, we are wanting to do a broader survey work (though likely not an academic article), that shows the strengths and improvements over all of the major quantization techniques, including extended RaBitQ, LVQ, PQ, and OSQ. I think a direct comparison between the techniques helps provide color for the strengths of each.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "gaoj0017 (via GitHub)" <gi...@apache.org>.
gaoj0017 commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2664639299
As we have consistently emphasized in both public and private communications, we are concerned that the <ins>**OSQ method employs an idea highly similar to the one presented in our [extended RaBitQ paper](https://arxiv.org/pdf/2409.09913), which was published months earlier than OSQ - however, Elastic does not acknowledge extended RaBitQ as a prior art but as a parallel work**</ins>. Specifically, the high-level idea of OSQ is to try different parameters for scalar quantization on a per-vector basis as described in Elastic’s reply. This idea is highly similar to one of the key ideas of our extended RaBitQ (as described in Section 3.2.2 of our extended RaBitQ paper): it involves testing various parameters for each individual vector, performing rounding (i.e., scalar quantization) based on these parameters, and then calculating the similarity between the rounded vector and the original vector. It finally selects the optimal parameter and corresponding rounded vector. With this, ou
r extended RaBitQ method achieves significant performance improvements over LVQ, the state-of-the-art variant of scalar quantization by then. For example, under 2-bit quantization, the distance estimation error of LVQ is larger than that of the extended RaBitQ by orders of magnitude.
In addition, Elastic insists on categorizing our RaBitQ and its extension methods as a variant of PQ to highlight the differences from OSQ, despite our repeated refutation of this point in our responses in private meetings. We believe we have made it clear that our RaBitQ and its extension are not variants of PQ, but provide optimized methods of binary and scalar quantization, respectively.
We respect OSQ’s differences from extended RaBitQ and would be pleased to see if they can make further improvements. However, these differences do not negate the similarity between the two methods. At the same time, we hope Elastic will respect (1) the significant performance improvements brought by our extended RaBitQ method in the realm of scalar quantization and (2) the fact that our extended RaBitQ method was published months earlier than OSQ.
Finally, we would like to reiterate our two points:
1. <ins>**The so-called BBQ majorly follows our RaBitQ method;**</ins>
2. <ins>**The OSQ method (introduced in this PR) has its major idea similar to our extended RaBitQ method (published months earlier) and our extended RaBitQ method is a prior art which achieves good accuracy at 1-bit/2-bit binary/scalar quantization for the first time.**</ins>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on code in PR #14078:
URL: https://github.com/apache/lucene/pull/14078#discussion_r1890779090
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene102/Lucene102BinaryQuantizedVectorsFormat.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene102;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.hnsw.FlatVectorScorerUtil;
+import org.apache.lucene.codecs.hnsw.FlatVectorsFormat;
+import org.apache.lucene.codecs.hnsw.FlatVectorsReader;
+import org.apache.lucene.codecs.hnsw.FlatVectorsWriter;
+import org.apache.lucene.codecs.lucene99.Lucene99FlatVectorsFormat;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.index.SegmentWriteState;
+
+/**
+ * Copied from Lucene, replace with Lucene's implementation sometime after Lucene 10 Codec for
Review Comment:
Also should we remove this line?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2569246977
+1 for proper attribution.
We should give credit where credit is due. The evolution of this PR clearly began with the RaBitQ paper, as seen in the [opening comment on the original PR](https://github.com/apache/lucene/pull/13651#issue-2464020838) as well as [the original issue](https://github.com/apache/lucene/issues/13650#issue-2463854436).
Specifically for the open source changes proposed here (this pull request suggesting changes to Lucene's ASL2 licensed source code):
* The CHANGES.txt entry should link to both RaBitQ papers?
* The javadoc for the new `Lucene102BinaryQuantizedVectorsFormat` should also link to both papers, and describe the provenance (e.g. the algorithm described by these papers) along with how this implementation differs from the original papers? We try to do this when a paper inspires changes in Lucene, e.g. [the algorithm for efficiently building our FSTs](https://github.com/apache/lucene/blob/204c39f8eb7fb5fd26a3b9ff41ef7d18fae1c844/lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java#L49-L50), [the paper that inspired our block-tree terms dictionary](https://github.com/apache/lucene/blob/204c39f8eb7fb5fd26a3b9ff41ef7d18fae1c844/lucene/core/src/java/org/apache/lucene/codecs/lucene90/blocktree/Lucene90BlockTreeTermsReader.java#L55-L57), the [HNSW approximate KNN search algorithm](https://github.com/apache/lucene/blob/204c39f8eb7fb5fd26a3b9ff41ef7d18fae1c844/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java#L32-L35).
Linking to the papers that inspired important changes in Lucene is not only for proper attribution but also so users have a deep resource they can fall back on to understand the algorithm, understand how tunable parameters are expected to behave, etc. It's an important part of the documentation too! Also, future developers can re-read the paper and study Lucene's implementation and maybe find bugs / improvement ideas.
For the Elastic specific artifacts (blog posts, press releases, tweets, etc.): I would agree that Elastic should also attribute properly, probably with an edit/update/sorry-about-the-oversight sort of addition? But I do not (no longer) work at Elastic, so this is merely my (external) opinion! Perhaps a future blog post, either Elastic or someone else, could correct the mistake (missed attribution).
Finally, thank you to @gaoj0017 and team for creating RaBitQ and publishing these papers -- this is an impactful vector quantization algorithm that can help the many Lucene/OpenSearch/Solr/Elasticsearch users building semantic / LLM engines these days.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2706558384
@benwtrent This makes sense, thank you!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2702238939
@benwtrent Thanks for your response, it was quite helpful. Could you please also share other parameters of your benchmark (ndoc, maxConn, beamWidthIndex, fanout, etc.) ?
I was able to come close to your results finally with ndoc=500_000, maxConn=64, beamWidthIndex=250, oversample=5f.
Also, a short question. What is the purpose of having both `oversample` and `fanout` parameters? At first glance it seems like they are doing almost the same thing.
Appreciate your help and time!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2565588002
@gaoj0017 it sounds to me as if your concern is about lack of attribution in the blog post you mentioned, and doesn't really relate to this pull request (code change) - is that accurate?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2573298347
In my capacity as the Lucene PMC Chair (and with explicit acknowledgment of my current employment with Elastic, as of the date of this writing), I want to emphasize that proper attribution and acknowledgment should be provided for all contributions, as applicable, in accordance with best practices.
While the inclusion of links to external blogs and prior works serves to provide helpful context regarding the broader landscape, it would be of greater value to explicitly delineate which specific elements within this pull request are directly related to the RaBitQ method or its extension.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2706428269
@lpld
I agree, both are doing similar things but there are some important distinctions.
`oversample` indicates that you are going to return that ratio more results from the index search. Flat or HNSW, it doesn't matter. So, for searching for `k=10` the searcher will actually return the top `k=50`. These results are then typically passed off to a rescorer type query that will calculate the distances at some higher fidelity (e.g. raw floats). This type of oversampling, gathering more than the desired docs, and then correcting their scores, is required at higher quantization levels.
`fanout` makes the search queue when searching the HNSW graph larger. However, the searcher will still only return `k` results. So, searching for top `k=10` with `fanout=20` indicates the HNSW search (ef_search, if you will) will gather the nearest 30, but then only the top 10 of those are returned from the searcher.
Think of it this way:
- `oversample` is for handling scoring approximations (e.g. quantized scoring)
- `fanout` is for handling approximations in HNSW (e.g. getting stuck in local minima and exploring the graph more).
Does that help?
> Could you please also share other parameters of your benchmark (ndoc, maxConn, beamWidthIndex, fanout, etc.)
I have lost my test environment and I regrettably didn't write all this down. however, these are some best guesses.
For Cohere 768:
- ndoc: 1_000_000
- topk: 10
- oversample: 5
- maxConn: 16
- beamWidth: 100
- fanout: 50 (might have been 100)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2710482360
> @lpld quantizing is done per segment, at flush and merge time. So it takes into account live vectors in the segment during flush and merge.
>
> I don't see why adding/updating/deleting would be any issue
And also, Lucene retains the full precision original (`float[]`) vectors, so that even during segment merging, the quantization is recomputed (accurately) from the original vectors.
There have been some issues/discussions about somehow not keeping the original vectors (they are costly in index storage, and lead to complications like [skipping them when replicating an index that will be used only for searching](https://github.com/apache/lucene/issues/13158)), but so far those have not been implemented (I think?).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "gaoj0017 (via GitHub)" <gi...@apache.org>.
gaoj0017 commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2644556568
After Elastic’s last round of replies, the Elastic team reached us for clarification on the issues via zoom meetings. In the meetings, they promised to fix the misattribution, so we suspended our reply and waited for their amendment. Recently, Elastic made some edits on the [BBQ blog](https://www.elastic.co/search-labs/blog/better-binary-quantization-lucene-elasticsearch) and this pull request. However, (1) the updated blog still positions BBQ as a new method (despite that BBQ majorly follows our RaBitQ method with some differences in the implementation only), and (2) the updated PR does not position our extended RaBitQ method as a prior art of their method (despite that the method is similar to our extended RaBitQ method at its core and our method is a prior art). As academic researchers, we feel tired of writing emails asking for proper attribution round after round, and hence we would like to speak out for ourselves through this channel here.
Point 1 in our reply: This pull request is a direct follow-up to [the preceding pull request](https://github.com/apache/lucene/pull/13651) of the so-called “BBQ” method. Thus, this point should not be ignored and excluded from the discussion. We emphasize again that all the key features of the so-called “BBQ” method follow our RaBitQ method, with only minor modifications.
Point 2 in our last reply: For the community’s information, we would like to provide the following timeline.
- On 16-Sep-2024, we published our [extended RaBitQ paper](https://arxiv.org/abs/2409.09913) along with codes.
- On 25-Oct-2024, we circulated the extended RaBitQ paper to Elastic as we knew they were implementing RaBitQ in Lucene. They replied positively that they will eagerly read our new paper. At that time, we didn’t expect that they would announce a variant of our RaBitQ method as their own innovation later. In addition, it is worth highlighting that our extended RaBitQ method is the first to achieve reasonable accuracy with 1-bit and 2-bit binary/scalar quantization in the literature by then.
- On 11-Nov-2024, Elastic announced the BBQ method as their new innovation (despite that BBQ is simply our RaBitQ method with some differences in implementation).
- On 22-Nov-2024, we expressed our concerns over the BBQ method to Elastic via email. Elastic replied that they would need internal discussions and would get in touch soon.
- On 14-Dec-2024, we had not received any replies from Elastic and Elastic kept marketing the so-called “BBQ” method as their own innovation in several blogs and press releases. We therefore expressed our concerns over the BBQ method to the Lucene community (https://github.com/apache/lucene/pull/13651).
- On 19/20-Dec-2024, Elastic announced the OSQ method in this PR and [this blog](https://www.elastic.co/search-labs/blog/scalar-quantization-optimization). They claimed to have unlocked the performance gain for various bits. However, they ignored the fact that our extended RaBitQ method can already handle various bits, despite that the method was shared with Elastic on 25 Oct 2024 and published on arXiv in Sep 2024.
- 14-Dec-2024 to 07-Jan-2025, Elastic and we had a few rounds of communications via this channel at GitHub, which are visible to the public. The last response was from Elastic on 07-Jan-2025, and we stopped replying here because Elastic reached out to us after their response and proposed to have communications via other channels (email and meetings) and we agreed with the hope that Elastic would fix the acknowledgement problem.
- 13-Jan-2025 and 22-Jan-2025, Elastic and we had two Zoom meetings and email communications and discussed how to provide sufficient acknowledgements to RaBitQ and its extension. Afterwards, Elastic made some edits on [the BBQ blog](https://www.elastic.co/search-labs/blog/better-binary-quantization-lucene-elasticsearch) and this PR. However, (1) in the updated blog, Elastic still positions BBQ as a new methodology and does not explicitly specify that the core ideas of BBQ follow those of RaBitQ and (2) in this PR, Elastic still positions OSQ as a parallel work of our extended RaBitQ method (despite its core ideas are similar to our extended RaBitQ method and our method is a prior part and published months ago). In addition, Elastic shared a doc with us explaining the differences between OSQ and extended RaBitQ, but our understanding is that the core ideas of two methods, i.e., trying different parameters for scalar quantization on a per-vector basis, are similar.
- 05-Feb-2025, this is when Elastic contacted us via <ins>Email</ins> lastly (as of today), saying that they think the acknowledgement of our RaBitQ and extended RaBitQ (based on the updated blog and PR) is sufficient.
- 08-Feb-2025 (today), this is when we replied to Elastic via <ins>Email</ins> lastly, updating them we shall speak out for us in other channels (after getting tired of writing emails round after round).
In summary, our requirements are two-fold: (1) Elastic should position BBQ as a variant of RaBitQ but not as a new innovation; and (2) Elastic should acknowledge our extended RaBitQ method as a prior art, which has covered similar ideas of the OSQ method and been published months earlier, but not a parallel work.
As for future communications, we may not be able to respond to every future response from Elastic because we feel they can keep arguing and changing their arguing points - in this thread, Elastic have changed their attribution of OSQ several times (from the inspiration of RaBitQ to LVQ and SCANN, and to their own earlier PR). We should have been focusing on research more as academic researchers. No matter how they would argue, they cannot deny the following two points:
1. <ins>**The so-called BBQ majorly follows our RaBitQ method;** </ins>
2. <ins>**The OSQ method (introduced in this PR) has its major idea similar to our extended RaBitQ method and our extended RaBitQ method is a prior art which achieves good accuracy at 1-bit/2-bit binary/scalar quantization for the first time.**</ins>
We would also consider reaching out to more channels to speak out for ourselves if necessary.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2681113395
@benwtrent Thanks for your reply!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2626006980
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "tveasey (via GitHub)" <gi...@apache.org>.
tveasey commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2652753715
This pull request relates only to OSQ, and thus the proper scope of discussion is regarding the concerns raised around its attribution.
We have pursued multiple conversations and discussions in order to resolve various concerns amicably, and we continue to desire collaboration and open discourse with respect to each party's innovations on this problem space. We would like to reiterate that we highly rate the research in both RaBitQ and its extension. However, we also maintain that OSQ is not a derivative of extended RaBitQ as we have done in private communications.
> In addition, Elastic shared a doc with us explaining the differences between OSQ and extended RaBitQ, but our understanding is that the core ideas of two methods, i.e., trying different parameters for scalar quantization on a per-vector basis, are similar.
This goes to crux of the disagreement around attribution. In the following we describe the two schemes: extended RaBitQ [1] and OSQ [2] and state again the points we have made privately regarding their differences.
Both methods centre the data, which was originally proposed in LVQ [3] to the best of our knowledge.
Extended RaBitQ proposes a method for constructing a codebook for which one can compute the dot product efficiently using integer arithmetic.
In a nutshell it proceeds as follows:
1. Apply a random orthogonal transformation of the input vectors.
2. Normalise resulting vectors and perform an efficient search for the nearest codebook centroid.
3. Snap the floating point vector to this codebook centroid and then undo the normalization procedure to obtain an estimate of the original dot product.
At its heart it is a variant of product quantization which allows for efficient similarity calculations and was positioned as such in the original paper.
The key ingredients of OSQ are as follows:
1. Construct per vector quantization intervals, inherited from LVQ.
2. Formulate quantization as a hyperparameter optimization problem for the interval [a, b] used to construct the grid of possible quantized vectors, building on our earlier work which we published in April [4].
3. Perform an analysis to show how to choose [a, b] to minimize the expected square error in the dot product when the data are normally distributed using sufficient statistics of the vector component distribution. (We perform an empirical study of the distribution of vector components in embedding models and show they are typically normally distributed.)
4. Perform an iterative procedure based on coordinate descent which optimizes an anisotropic loss based on the ideas in [5] w.r.t. the interval [a, b] initialising with the output of 3.
At an algorithmic level there is no similarity between the methods other than they both centre the data. At a conceptual level RaBitQ was developed as a variant of product quantization and OSQ was developed as an approach to hyperparameter optimization for per vector scalar quantization. For the record, we were inspired to revisit scalar quantization in light of the success of binary RaBitQ and we were exploring ideas prior to any communication between our teams regarding extended RaBitQ. The actual inspiration for the approach was our previous work on hyperparameter optimisation for quantization intervals and LVQ and we attribute this PR accordingly.
Retrospectively, and in parallel to our work the authors of RaBitQ explored the relationship between extended RaBitQ and scalar quantization directly ([6] published 12/12/2024). They show that the act of normalising the vectors, finding the nearest centroid then undoing the normalisation can be thought of as a process of rescaling the quantization grid so that the nearest quantized vector winds up closer to the original floating point vector. Whilst this bears some relation to optimising b - a they never formulate this process as an optimisation problem and at no point show exactly what quantity they in fact optimise. In our view, this misses the key point that the important idea is the formulation. As such it is very clear that they do not and could not introduce any different optimisation objective, such as anisotopic loss in the dot product. Even if they did, OSQ optimises both a and b directly which gives it an extra degree of freedom and develops an effective and non-trivial
and completely distinct solution for this problem.
As we have communicated privately, we dispute that OSQ is a variant of extended RaBitQ. We laid out in broadly similar terms exactly why we disagree at a technical level (along the lines of the discussion in this comment). We have received no further technical engagement with the points we have raised and have therefore reached an impasse.
Regarding this point:
> They claimed to have unlocked the performance gain for various bits. However, they ignored the fact that our extended RaBitQ method can already handle various bits, despite that the method was shared with Elastic on 25 Oct 2024 and published on arXiv in Sep 2024.
we at no point intended to imply that RaBitQ could not be extended to support more than 1 bit and that this is the only motivation for our work. The main original motivations are all the benefits we see in being able to achieve high quality representations using a variant of vanilla scalar quantization such as:
1. Simplicity, and
2. And the speed with which we can calculate of quantized vectors for any compression rate.
We performed and published a study evaluating binary variants and showed consistent improvements in comparison to binary RaBitQ [2]. The study we performed is perfectly in the spirit of evaluating competing methods and covers multiple datasets and embedding models. Our initial focus was on binary quantization, since this is the only work we were releasing in product at that point. We privately discussed plans with the authors of RaBitQ to perform benchmarking for higher bit counts compared to extended RaBitQ and also to perform larger scale benchmarks.
We were unaware of the [4] at the time the blog [2] was written and we communicated privately that we plan to publish a survey which includes a discussion of both works as well as other pertinent work in the field. We have furthermore stated privately, that this feels like a more appropriate forum in which to discuss the two methods.
[1] Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search, https://arxiv.org/pdf/2409.09913
[2] Understanding optimized scalar quantization, https://www.elastic.co/search-labs/blog/scalar-quantization-optimization
[3] Similarity search in the blink of an eye with compressed indices, https://arxiv.org/abs/2304.04759
[4] Scalar quantization optimized for vector databases,
https://www.elastic.co/search-labs/blog/vector-db-optimized-scalar-quantization
[5] Accelerating Large-Scale Inference with Anisotropic Vector Quantization, https://arxiv.org/pdf/1908.10396
[6] Extended RaBitQ: an Optimized Scalar Quantization Method,
https://dev.to/gaoj0017/extended-rabitq-an-optimized-scalar-quantization-method-83m
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "gaoj0017 (via GitHub)" <gi...@apache.org>.
gaoj0017 commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2550510539
Hi @benwtrent , I am the first author of the [RaBitQ paper](https://arxiv.org/abs/2405.12497) and [its extended version](https://arxiv.org/abs/2409.09913). As your team have known, our RaBitQ method brings breakthrough performance on binary quantization and scalar quantization.
We notice that in this pull request, you mention a method which individually optimizes the lower bound and upper bound of scalar quantization. This idea is highly similar to our idea of individually looking for the optimal rescaling factor of scalar quantization as described in our [extended RaBitQ](https://arxiv.org/abs/2409.09913) paper, which we shared with your team in Oct 2024. An intuitive explanation can be found in our recent [blog](https://dev.to/gaoj0017/extended-rabitq-an-optimized-scalar-quantization-method-83m). The mathematical equivalence between these two ideas is listed in Remark 2.
In addition, the contribution of our [RaBitQ](https://arxiv.org/abs/2405.12497) has not been properly acknowledged at several other places. For example, in a previous post from Elastic - [Better Binary Quantization (BBQ) in Lucene and Elasticsearch](https://www.elastic.co/search-labs/blog/better-binary-quantization-lucene-elasticsearch), the major features of BBQ are introduced, yet it is not made clear that all these features originate from our [RaBitQ paper](https://arxiv.org/abs/2405.12497). In a [press release](https://www.elastic.co/blog/whats-new-elasticsearch-platform-8-16-0), Elastic claims that "Elasticsearch’s new BBQ algorithm redefines vector quantization", however, BBQ is not a grandly new method, but a variant of RaBitQ with some minor adaption.
We note that when a breakthrough is made, it is always easy to derive its variants or to restate the method in different languages. One should not claim a variant to be a new method with a new name and ignore the contribution of the original method. We hope that you would understand our concern and acknowledge the contributions of our RaBitQ and its extension properly in your pull requests and/or blogs.
* **Remark 1**. The BBQ feature fails on the GIST dataset because it removes the randomization operation of the RaBitQ method. With the randomization operation, RaBitQ is theoretically guaranteed to perform stably on all datasets.
* **Remark 2**. Let $B$ be the number of bits for scalar quantization. The scalar quantization can be represented in two equivalent ways.
1. Scalar quantization can be determined by the lower bound $v_l$ and the upper bound $v_r$. The algorithm first computes $\Delta =(v_r-v_l) / (2^{B}-1)$ and then maps each real value $x$ to the nearest integer of $(x-v_l) / \Delta$.
2. Based on the process above, scalar quantization can be equivalently determined by a rescaling factor $\Delta$ and a shifting factor $v_l$.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on code in PR #14078:
URL: https://github.com/apache/lucene/pull/14078#discussion_r1890793535
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene102/Lucene102BinaryQuantizedVectorsFormat.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene102;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.hnsw.FlatVectorScorerUtil;
+import org.apache.lucene.codecs.hnsw.FlatVectorsFormat;
+import org.apache.lucene.codecs.hnsw.FlatVectorsReader;
+import org.apache.lucene.codecs.hnsw.FlatVectorsWriter;
+import org.apache.lucene.codecs.lucene99.Lucene99FlatVectorsFormat;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.index.SegmentWriteState;
+
+/**
+ * Copied from Lucene, replace with Lucene's implementation sometime after Lucene 10 Codec for
+ * encoding/decoding binary quantized vectors The binary quantization format used here is a
+ * per-vector optimized scalar quantization. Also see {@link
+ * org.apache.lucene.util.quantization.OptimizedScalarQuantizer}. Some of key features are:
+ *
+ * <ul>
+ * <li>Estimating the distance between two vectors using their centroid normalized distance. This
+ * requires some additional corrective factors, but allows for centroid normalization to
+ * occur.
+ * <li>Optimized scalar quantization to single bit level of centroid normalized vectors.
+ * <li>Asymmetric quantization of vectors, where query vectors are quantized to half-byte (4 bits)
+ * precision (normalized to the centroid) and then compared directly against the single bit
+ * quantized vectors in the index.
+ * <li>Transforming the half-byte quantized query vectors in such a way that the comparison with
+ * single bit vectors can be done with bit arithmetic.
+ * </ul>
+ *
+ * The format is stored in two files:
+ *
+ * <h2>.veb (vector data) file</h2>
+ *
+ * <p>Stores the binary quantized vectors in a flat format. Additionally, it stores each vector's
+ * corrective factors. At the end of the file, additional information is stored for vector ordinal
+ * to centroid ordinal mapping and sparse vector information.
+ *
+ * <ul>
+ * <li>For each vector:
+ * <ul>
+ * <li><b>[byte]</b> the binary quantized values, each byte holds 8 bits.
+ * <li><b>[float]</b> the optimized quantiles and an additional similarity dependent
+ * corrective factor.
+ * <li><b>short</b> the sum of the quantized components
+ * </ul>
+ * <li>After the vectors, sparse vector information keeping track of monotonic blocks.
+ * </ul>
+ *
+ * <h2>.vemb (vector metadata) file</h2>
+ *
+ * <p>Stores the metadata for the vectors. This includes the number of vectors, the number of
+ * dimensions, and file offset information.
+ *
+ * <ul>
+ * <li><b>int</b> the field number
+ * <li><b>int</b> the vector encoding ordinal
+ * <li><b>int</b> the vector similarity ordinal
+ * <li><b>vint</b> the vector dimensions
+ * <li><b>vlong</b> the offset to the vector data in the .veb file
+ * <li><b>vlong</b> the length of the vector data in the .veb file
+ * <li><b>vint</b> the number of vectors
+ * <li><b>[float]</b> the centroid
+ * <li><b>float</b> the centroid square magnitude
+ * <li>The sparse vector information, if required, mapping vector ordinal to doc ID
+ * </ul>
+ */
+public class Lucene102BinaryQuantizedVectorsFormat extends FlatVectorsFormat {
+
+ public static final byte QUERY_BITS = 4;
+ public static final byte INDEX_BITS = 1;
+
+ public static final String BINARIZED_VECTOR_COMPONENT = "BVEC";
+ public static final String NAME = "Lucene102BinaryQuantizedVectorsFormat";
+
+ static final int VERSION_START = 0;
+ static final int VERSION_CURRENT = VERSION_START;
+ static final String META_CODEC_NAME = "Lucene102BinaryQuantizedVectorsFormatMeta";
+ static final String VECTOR_DATA_CODEC_NAME = "Lucene102BinaryQuantizedVectorsFormatData";
+ static final String META_EXTENSION = "vemb";
+ static final String VECTOR_DATA_EXTENSION = "veb";
+ static final int DIRECT_MONOTONIC_BLOCK_SHIFT = 16;
+
+ private static final FlatVectorsFormat rawVectorFormat =
+ new Lucene99FlatVectorsFormat(FlatVectorScorerUtil.getLucene99FlatVectorsScorer());
+
+ private static final Lucene102BinaryFlatVectorsScorer scorer =
+ new Lucene102BinaryFlatVectorsScorer(FlatVectorScorerUtil.getLucene99FlatVectorsScorer());
+
+ /** Creates a new instance with the default number of vectors per cluster. */
+ public Lucene102BinaryQuantizedVectorsFormat() {
+ super(NAME);
+ }
+
+ @Override
+ public FlatVectorsWriter fieldsWriter(SegmentWriteState state) throws IOException {
+ return new Lucene102BinaryQuantizedVectorsWriter(
+ scorer, rawVectorFormat.fieldsWriter(state), state);
+ }
+
+ @Override
+ public FlatVectorsReader fieldsReader(SegmentReadState state) throws IOException {
+ return new Lucene102BinaryQuantizedVectorsReader(
+ state, rawVectorFormat.fieldsReader(state), scorer);
+ }
+
+ @Override
+ public int getMaxDimensions(String fieldName) {
+ return 1024;
+ }
+
+ @Override
+ public String toString() {
+ return "Lucene102BinaryQuantizedVectorsFormat(name="
+ + NAME
+ + ", flatVectorScorer="
+ + scorer
Review Comment:
nit: should we also add + ", rawVectorFormat=" + rawVectorFormat?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on code in PR #14078:
URL: https://github.com/apache/lucene/pull/14078#discussion_r1890778000
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene102/package-info.java:
##########
@@ -0,0 +1,436 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Lucene 10.2 file format.
+ *
+ * <h2>Apache Lucene - Index File Formats</h2>
+ *
+ * <div>
+ *
+ * <ul>
+ * <li><a href="#Introduction">Introduction</a>
+ * <li><a href="#Definitions">Definitions</a>
+ * <ul>
+ * <li><a href="#Inverted_Indexing">Inverted Indexing</a>
+ * <li><a href="#Types_of_Fields">Types of Fields</a>
+ * <li><a href="#Segments">Segments</a>
+ * <li><a href="#Document_Numbers">Document Numbers</a>
+ * </ul>
+ * <li><a href="#Overview">Index Structure Overview</a>
+ * <li><a href="#File_Naming">File Naming</a>
+ * <li><a href="#file-names">Summary of File Extensions</a>
+ * <ul>
+ * <li><a href="#Lock_File">Lock File</a>
+ * <li><a href="#History">History</a>
+ * <li><a href="#Limitations">Limitations</a>
+ * </ul>
+ * </ul>
+ *
+ * </div> <a id="Introduction"></a>
+ *
+ * <h3>Introduction</h3>
+ *
+ * <div>
+ *
+ * <p>This document defines the index file formats used in this version of Lucene. If you are using
+ * a different version of Lucene, please consult the copy of <code>docs/</code> that was distributed
+ * with the version you are using.
+ *
+ * <p>This document attempts to provide a high-level definition of the Apache Lucene file formats.
+ * </div> <a id="Definitions"></a>
+ *
+ * <h3>Definitions</h3>
+ *
+ * <div>
+ *
+ * <p>The fundamental concepts in Lucene are index, document, field and term.
+ *
+ * <p>An index contains a sequence of documents.
+ *
+ * <ul>
+ * <li>A document is a sequence of fields.
+ * <li>A field is a named sequence of terms.
+ * <li>A term is a sequence of bytes.
+ * </ul>
+ *
+ * <p>The same sequence of bytes in two different fields is considered a different term. Thus terms
+ * are represented as a pair: the string naming the field, and the bytes within the field. <a
+ * id="Inverted_Indexing"></a>
+ *
+ * <h4>Inverted Indexing</h4>
+ *
+ * <p>Lucene's index stores terms and statistics about those terms in order to make term-based
+ * search more efficient. Lucene's terms index falls into the family of indexes known as an
+ * <i>inverted index.</i> This is because it can list, for a term, the documents that contain it.
+ * This is the inverse of the natural relationship, in which documents list terms. <a
+ * id="Types_of_Fields"></a>
+ *
+ * <h4>Types of Fields</h4>
+ *
+ * <p>In Lucene, fields may be <i>stored</i>, in which case their text is stored in the index
+ * literally, in a non-inverted manner. Fields that are inverted are called <i>indexed</i>. A field
+ * may be both stored and indexed.
+ *
+ * <p>The text of a field may be <i>tokenized</i> into terms to be indexed, or the text of a field
+ * may be used literally as a term to be indexed. Most fields are tokenized, but sometimes it is
+ * useful for certain identifier fields to be indexed literally.
+ *
+ * <p>See the {@link org.apache.lucene.document.Field Field} java docs for more information on
+ * Fields. <a id="Segments"></a>
+ *
+ * <h4>Segments</h4>
+ *
+ * <p>Lucene indexes may be composed of multiple sub-indexes, or <i>segments</i>. Each segment is a
+ * fully independent index, which could be searched separately. Indexes evolve by:
+ *
+ * <ol>
+ * <li>Creating new segments for newly added documents.
+ * <li>Merging existing segments.
+ * </ol>
+ *
+ * <p>Searches may involve multiple segments and/or multiple indexes, each index potentially
+ * composed of a set of segments. <a id="Document_Numbers"></a>
+ *
+ * <h4>Document Numbers</h4>
+ *
+ * <p>Internally, Lucene refers to documents by an integer <i>document number</i>. The first
+ * document added to an index is numbered zero, and each subsequent document added gets a number one
+ * greater than the previous.
+ *
+ * <p>Note that a document's number may change, so caution should be taken when storing these
+ * numbers outside of Lucene. In particular, numbers may change in the following situations:
+ *
+ * <ul>
+ * <li>
+ * <p>The numbers stored in each segment are unique only within the segment, and must be
+ * converted before they can be used in a larger context. The standard technique is to
+ * allocate each segment a range of values, based on the range of numbers used in that
+ * segment. To convert a document number from a segment to an external value, the segment's
+ * <i>base</i> document number is added. To convert an external value back to a
+ * segment-specific value, the segment is identified by the range that the external value is
+ * in, and the segment's base value is subtracted. For example two five document segments
+ * might be combined, so that the first segment has a base value of zero, and the second of
+ * five. Document three from the second segment would have an external value of eight.
+ * <li>
+ * <p>When documents are deleted, gaps are created in the numbering. These are eventually
+ * removed as the index evolves through merging. Deleted documents are dropped when segments
+ * are merged. A freshly-merged segment thus has no gaps in its numbering.
+ * </ul>
+ *
+ * </div> <a id="Overview"></a>
+ *
+ * <h3>Index Structure Overview</h3>
+ *
+ * <div>
+ *
+ * <p>Each segment index maintains the following:
+ *
+ * <ul>
+ * <li>{@link org.apache.lucene.codecs.lucene99.Lucene99SegmentInfoFormat Segment info}. This
+ * contains metadata about a segment, such as the number of documents, what files it uses, and
+ * information about how the segment is sorted
+ * <li>{@link org.apache.lucene.codecs.lucene94.Lucene94FieldInfosFormat Field names}. This
+ * contains metadata about the set of named fields used in the index.
+ * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90StoredFieldsFormat Stored Field values}.
+ * This contains, for each document, a list of attribute-value pairs, where the attributes are
+ * field names. These are used to store auxiliary information about the document, such as its
+ * title, url, or an identifier to access a database. The set of stored fields are what is
+ * returned for each hit when searching. This is keyed by document number.
+ * <li>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Term dictionary}. A
+ * dictionary containing all of the terms used in all of the indexed fields of all of the
+ * documents. The dictionary also contains the number of documents which contain the term, and
+ * pointers to the term's frequency and proximity data.
+ * <li>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Term Frequency data}. For
+ * each term in the dictionary, the numbers of all the documents that contain that term, and
+ * the frequency of the term in that document, unless frequencies are omitted ({@link
+ * org.apache.lucene.index.IndexOptions#DOCS IndexOptions.DOCS})
+ * <li>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Term Proximity data}. For
+ * each term in the dictionary, the positions that the term occurs in each document. Note that
+ * this will not exist if all fields in all documents omit position data.
+ * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90NormsFormat Normalization factors}. For
+ * each field in each document, a value is stored that is multiplied into the score for hits
+ * on that field.
+ * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90TermVectorsFormat Term Vectors}. For each
+ * field in each document, the term vector (sometimes called document vector) may be stored. A
+ * term vector consists of term text and term frequency. To add Term Vectors to your index see
+ * the {@link org.apache.lucene.document.Field Field} constructors
+ * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90DocValuesFormat Per-document values}. Like
+ * stored values, these are also keyed by document number, but are generally intended to be
+ * loaded into main memory for fast access. Whereas stored values are generally intended for
+ * summary results from searches, per-document values are useful for things like scoring
+ * factors.
+ * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90LiveDocsFormat Live documents}. An
+ * optional file indicating which documents are live.
+ * <li>{@link org.apache.lucene.codecs.lucene90.Lucene90PointsFormat Point values}. Optional pair
+ * of files, recording dimensionally indexed fields, to enable fast numeric range filtering
+ * and large numeric values like BigInteger and BigDecimal (1D) and geographic shape
+ * intersection (2D, 3D).
+ * <li>{@link org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat Vector values}. The
+ * vector format stores numeric vectors in a format optimized for random access and
+ * computation, supporting high-dimensional nearest-neighbor search.
+ * </ul>
+ *
+ * <p>Details on each of these are provided in their linked pages. </div> <a id="File_Naming"></a>
+ *
+ * <h3>File Naming</h3>
+ *
+ * <div>
+ *
+ * <p>All files belonging to a segment have the same name with varying extensions. The extensions
+ * correspond to the different file formats described below. When using the Compound File format
+ * (default for small segments) these files (except for the Segment info file, the Lock file, and
+ * Deleted documents file) are collapsed into a single .cfs file (see below for details)
+ *
+ * <p>Typically, all segments in an index are stored in a single directory, although this is not
+ * required.
+ *
+ * <p>File names are never re-used. That is, when any file is saved to the Directory it is given a
+ * never before used filename. This is achieved using a simple generations approach. For example,
+ * the first segments file is segments_1, then segments_2, etc. The generation is a sequential long
+ * integer represented in alpha-numeric (base 36) form. </div> <a id="file-names"></a>
+ *
+ * <h3>Summary of File Extensions</h3>
+ *
+ * <div>
+ *
+ * <p>The following table summarizes the names and extensions of the files in Lucene:
+ *
+ * <table class="padding4" style="border-spacing: 1px; border-collapse: separate">
+ * <caption>lucene filenames by extension</caption>
+ * <tr>
+ * <th>Name</th>
+ * <th>Extension</th>
+ * <th>Brief Description</th>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.index.SegmentInfos Segments File}</td>
+ * <td>segments_N</td>
+ * <td>Stores information about a commit point</td>
+ * </tr>
+ * <tr>
+ * <td><a href="#Lock_File">Lock File</a></td>
+ * <td>write.lock</td>
+ * <td>The Write lock prevents multiple IndexWriters from writing to the same
+ * file.</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene99.Lucene99SegmentInfoFormat Segment Info}</td>
+ * <td>.si</td>
+ * <td>Stores metadata about a segment</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90CompoundFormat Compound File}</td>
+ * <td>.cfs, .cfe</td>
+ * <td>An optional "virtual" file consisting of all the other index files for
+ * systems that frequently run out of file handles.</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene94.Lucene94FieldInfosFormat Fields}</td>
+ * <td>.fnm</td>
+ * <td>Stores information about the fields</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90StoredFieldsFormat Field Index}</td>
+ * <td>.fdx</td>
+ * <td>Contains pointers to field data</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90StoredFieldsFormat Field Data}</td>
+ * <td>.fdt</td>
+ * <td>The stored fields for documents</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Term Dictionary}</td>
+ * <td>.tim</td>
+ * <td>The term dictionary, stores term info</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Term Index}</td>
+ * <td>.tip</td>
+ * <td>The index into the Term Dictionary</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Frequencies}</td>
+ * <td>.doc</td>
+ * <td>Contains the list of docs which contain each term along with frequency</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Positions}</td>
+ * <td>.pos</td>
+ * <td>Stores position information about where a term occurs in the index</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene101.Lucene101PostingsFormat Payloads}</td>
+ * <td>.pay</td>
+ * <td>Stores additional per-position metadata information such as character offsets and user payloads</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90NormsFormat Norms}</td>
+ * <td>.nvd, .nvm</td>
+ * <td>Encodes length and boost factors for docs and fields</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90DocValuesFormat Per-Document Values}</td>
+ * <td>.dvd, .dvm</td>
+ * <td>Encodes additional scoring factors or other per-document information.</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90TermVectorsFormat Term Vector Index}</td>
+ * <td>.tvx</td>
+ * <td>Stores offset into the document data file</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90TermVectorsFormat Term Vector Data}</td>
+ * <td>.tvd</td>
+ * <td>Contains term vector data.</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90LiveDocsFormat Live Documents}</td>
+ * <td>.liv</td>
+ * <td>Info about what documents are live</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene90.Lucene90PointsFormat Point values}</td>
+ * <td>.kdd, .kdi, .kdm</td>
+ * <td>Holds indexed points</td>
+ * </tr>
+ * <tr>
+ * <td>{@link org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat Vector values}</td>
+ * <td>.vec, .vem, .veq, vex</td>
Review Comment:
should we also add `veb` and `vemb` files to the list?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "gaoj0017 (via GitHub)" <gi...@apache.org>.
gaoj0017 commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2562753433
@benwtrent Thanks for your reply.
First, in the blog - [Better Binary Quantization at Elastic and Lucene](https://www.elastic.co/search-labs/blog/better-binary-quantization-lucene-elasticsearch) - the BBQ method is a variant of our RaBitQ with no major differences. The claimed major features of BBQ all originate from our RaBitQ paper (as we have explained in our last reply). There is only one attribution to our method, where it is mentioned (in one sentence) that BBQ is based on some inspirations from RaBitQ. We think this attribution is not sufficient - it should be made clear that the mentioned features of BBQ all originate from RaBitQ.
Second, for the new method described in this pull request, there is no attribution to our extended RaBitQ method at all - we note that we shared with your team the extended RaBitQ paper more than 2 months ago. To our understanding, the method is highly similar to our extended RaBitQ at its core (which also supports quantizing a vector to 1-bit, 2-bit, ... per dimension). They share the major idea of optimizing the scalar quantization method by trying different parameters. In your new blog, it is mentioned that “Although the RaBitQ approach is conceptually rather different to scalar quantization, we were inspired to re-evaluate whether similar performance could be unlocked for scalar quantization.” This is not true since our extended RaBitQ corresponds to an optimized scalar quantization method.
Given that our extended RaBitQ method is a prior art of the method introduced in the blog and our method was known to your team more than 2 months ago, you should not have ignored it. Discussions on the differences between two methods if any should be clearly explained and experiments of comparing the two methods should be provided as well.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2698569925
Hi @benwtrent
Thanks again for your previous comment. I was able to modify luceneutil and run some benchmarks. I am quite new to lucene, so I would appreciate some help in understanding the results that I’m getting.
First, I was trying to run a quantized and a non-quantized benchmark on the Cohere 768 dataset on my local machine.
Here are the results for the quantized benchmark (with Lucene102HnswBinaryQuantizedVectorsFormat):
```
recall latency (ms) nDoc topK fanout maxConn beamWidth quantized index s index docs/s force merge s num segments index size (MB) vec disk (MB) vec RAM (MB)
0.452 11.655 10000000 100 50 16 100 1 bits 1914.86 5222.32 10112.13 1 30934.82 30212.402 915.527
```
Unfortunately I didn’t save the non-quantized results, but the recall was something around 0.73.
Then I ran the same tests on a dedicated server with more CPU and RAM, and the results were weird. Yes, they were much much faster, but the recall was super low now:
Non-quantized:
```
recall latency (ms) nDoc topK fanout maxConn beamWidth quantized index s index docs/s force merge s num segments index size (MB) vec disk (MB) vec RAM (MB)
0.203 7.143 10000000 100 50 16 100 no 1403.40 7125.53 769.29 1 29470.29 29296.875 29296.875
```
Quantized:
```
recall latency (ms) nDoc topK fanout maxConn beamWidth quantized index s index docs/s force merge s num segments index size (MB) vec disk (MB) vec RAM (MB)
0.191 7.721 10000000 100 50 16 100 1 bits 511.40 19554.09 1116.80 1 30597.43 30212.402 915.527
```
So, my questions are
1. What exactly do the numbers in the description of this pull request mean? When you say that the recall for Cohere 768 is 0.938, is it the absolute recall value that you got from the benchmark, or is it some sort of ratio between the quantized and non-quantized recalls?
2. Do you have any ideas about what could be the reason for such a huge recall difference in the benchmark results on difference environments?
3. I was also trying to do some benchmarking with other public datasets (without luceneutil), and I got a little confused about how to correctly calculate the recall. I understand that recall is a ratio between the number of correct responses and the total number of responses. The total number of responses is straightforward, but the number of correct ones is a bit confusing to me. `luceneutil` is querying them as following (not exact code, but my variation):
```java
var queryVector = new ConstKnnByteVectorValueSource(queryEmb);
var docVectors = new ByteKnnVectorFieldSource("vector");
var exactQuery = new BooleanQuery.Builder()
.add(new FunctionQuery(new ByteVectorSimilarityFunction(similarity, queryVector, docVectors)), BooleanClause.Occur.SHOULD)
.add(new MatchAllDocsQuery(), BooleanClause.Occur.FILTER)
.build();
```
However, in `lucene` unit tests a different query is used to get the correct neighbors from the index:
```java
var exactQuery = new KnnByteVectorQuery("vector", queryEmb, size, new MatchAllDocsQuery());
```
I would appreciate if you could give some insights on what query is the correct one, because they return different results.
Thanks for your time!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2709087834
@benwtrent A short question again. Does this quantization approach in principle applicable when my data is constantly changing, i.e. new vectors are being added and old vectors removed from the dataset? Thanks
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2710314969
@lpld quantizing is done per segment, at flush and merge time. So it takes into account live vectors in the segment during flush and merge.
I don't see why adding/updating/deleting would be any issue
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2710460602
> `fanout` makes the search queue when searching the HNSW graph larger. However, the searcher will still only return `k` results. So, searching for top `k=10` with `fanout=20` indicates the HNSW search (ef_search, if you will) will gather the nearest 30, but then only the top 10 of those are returned from the searcher.
Maybe we should rename `fanout` to `ef_search` in luceneutil? I'll open an issue there.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Binary vector format for flat and hnsw vectors [lucene]
Posted by "lpld (via GitHub)" <gi...@apache.org>.
lpld commented on PR #14078:
URL: https://github.com/apache/lucene/pull/14078#issuecomment-2710872661
@benwtrent @mikemccand I really appreciate your help and quick responses.
May I also ask about the selection of datasets being used for the benchmarks? How do you choose them? Why I'm asking is because there are many more publicly available datasets, some of which don't produce such good results. For instance, with [SIFT1M](http://corpus-texmex.irisa.fr/) I was able to produce only ~0.23 recall.
Thank you.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org