While merging quantized vector fields, how can we minimize information loss?

[kaivalnp]

Description

Disclosure + Credit: I work at Amazon, and this idea was suggested by a colleague familiar with vector search (thanks Karthik!)

For quantized vector fields, HNSW graphs are initially built (during indexing) with original (unquantized) vectors, but later (during merging) with quantized vectors (see ref).

Would a graph built using original (unquantized) vectors every time (both indexing + merge) be higher quality, and better to search?

This is a tradeoff b/w increased indexing time (quantized computations are cheaper) v/s better recall + latency at search time.

[kaivalnp]

I made sample changes in #15774 (still draft, we can probably clean up some more things) and ran knnPerfTest on Cohere v3 vectors, 1024 dimensions, 500K docs, 10K queries, force merged to single segment, maxConn = 64, beamWidth = 250, topK = 100, fanout = 100

Baseline:

recall  latency(ms)  netCPU  avgCpuCount  quantized  visited  index(s)  index_docs/s  force_merge(s)  index_size(MB)  vec_disk(MB)  vec_RAM(MB)
 0.976        3.902   3.821        0.979     8 bits     8127    100.03       4998.75           38.85         2520.66      2449.036      495.911
 0.918        2.799   2.742        0.980     4 bits     8216    100.04       4997.90          138.61         2276.77      2204.895      251.770
 0.815        2.637   2.593        0.983     2 bits     8617     98.43       5079.75          142.12         2156.33      2081.871      128.746
 0.695        2.423   2.371        0.979     1 bits     9593     98.99       5051.02          112.67         2102.03      2020.836       67.711

Candidate (linked PR):

recall  latency(ms)  netCPU  avgCpuCount  quantized  visited  index(s)  index_docs/s  force_merge(s)  index_size(MB)  vec_disk(MB)  vec_RAM(MB)
 0.976        3.947   3.864        0.979     8 bits     8129    114.95       4349.87          153.95         2520.60      2449.036      495.911
 0.918        2.829   2.771        0.979     4 bits     8161    112.50       4444.40          153.31         2276.47      2204.895      251.770
 0.816        2.535   2.480        0.978     2 bits     8255    114.26       4376.18          171.60         2154.43      2081.871      128.746
 0.697        2.137   2.093        0.979     1 bits     8456    112.15       4458.43          162.72         2093.41      2020.836       67.711

With increasing levels of quantization, the search has to visit fewer HNSW nodes to get the same quality of results.

We see up to 12% better latency for 1-bit quantization. Consequently, indexing time increased by ~13% (not sure why?) and force merge time increased by ~44% in this case.

[mccullocht]

A graph built with the original vectors (or higher bit rate vectors in general) will be higher quality. In particular with 1 bit quantized vectors the algorithm can struggle to differentiate between different edges because the quantized scores are very similar. There's some acknowledgement of this in the quantized vectors format for 1 and 2 bits because we also store a 4 bit representation for the "query" during indexing to better approximate the actual score.

An alternative would be to use the quantized vectors in most cases but allow the use of full fidelity vectors in certain spots, mostly whenever you might want to prune the edges for a vertex. This is only likely to be useful when quantizing to <= 4 bits, at 8 bits the loss from quantization is small enough that using full fidelity vectors won't change the outcome very often.

We see up to 12% better latency for 1-bit quantization. Consequently, indexing time increased by ~13% (not sure why?) and force merge time increased by ~44% in this case.

In this case your float data set is about 2GB and everything fits in RAM on your host. If you scale the data set (or, I suppose, "shrink" your host by running in a memory container) so that the data set is larger than RAM, indexing/merge time is likely to be much worse.

[benwtrent]

I don't think we should do this. This will greatly increase the indexing time on an already stupidly expensive indexing & merging operation. It will also increase the memory requirements by a magnitude (in the case of single and 2 bit).

There are way better ways to do this at query time & index time.

Query refinements (e.g. refining at higher bits when things are on the verge of competitive), or maybe during graph building a nicer way to refine (e.g. higher bits to rescore maybe gathering initial candidates).

I would rather we spend time figuring out how to make indexing and merging way cheaper.

EDIT:

I recognize the graph is higher quality, but we should try to achieve that higher quality without increasing memory requirements by 32x & merge time (even when everything fits in memory)

[kaivalnp]

Thanks @mccullocht @benwtrent -- makes sense!

I meant to quantify how much we're losing with the use of quantized vectors to merge HNSW graphs, and it's likely that outright using the original (unquantized) vectors is an overkill -- so I'll generalize this issue..

[mikemccand]

Since merging/indexing is essentially running KNNFloat/ByteVectorQuery and then inserting the returned top K as the connections for that node ... could we use re-ranking (needs fewer full precision vectors) during that query? But, in aggregate, it seems likely to need all ish of those full precision vectors (I have the same concern about reranking at search time -- does it really reduce transient hot RAM needed?).

Or, maybe when quantizing to 1 or 2 bits, we also quantize to 8 bits, and use those 8 bit vectors for re-ranking or so.

There's some acknowledgement of this in the quantized vectors format for 1 and 2 bits because we also store a 4 bit representation for the "query" during indexing to better approximate the actual score.

Oh, hmm, what does this mean exactly? Is it asymmetric quantization used for the query vector (the vector being inserted) during its HNSW search against the 1 or 2 bit indexed vectors?

It's curious that we do use full precision scores on segment birth (newly indexed vectors), but quantized scores for merging. It means depending on your RAM buffer settings, numbers of threads, etc., you can "see" the effect on different HNSW graphs -- normally such settings do not (should not?) alter the semantics of the index, but HNSW is probabilistic anyways so this is probably just in the noise, ish.

[mikemccand]

Also, I think this was @msokolov idea maybe: simple set-overlap recall is a dangerous metric because it doesn't reflect vectors whose scores are really close. So if I get totally different vectors, but their scores were very close to the previous set of vectors, that shouldn't really count as 0% recall. Are there known improvements to recall, "score weighted recall" or so, to take this into account somehow...? One workaround is to report recall@N with many N values -- once N gets beyond those "nearly the same distance" set of result vectors, recall rises, vs the smaller Ns...

[mikemccand]

With increasing levels of quantization, the search has to visit fewer HNSW nodes to get the same quality of results.

Did knnPerfTest.py also give an ROC graph with these results? Maybe attach that too? It's quick (quicker for me anyways) to understand the results visually, since I then get to use the massive concurrency in my vision -> brain system heh.

[mikemccand]

I opened mikemccand/luceneutil#554 to see if we can improve luceneutil's knnPerfTest.py to somehow take scores into account for recall...

[benwtrent]

Oh, hmm, what does this mean exactly? Is it asymmetric quantization used for the query vector (the vector being inserted) during its HNSW search against the 1 or 2 bit indexed vectors?

Yes, the reason is backlink scoring. Since we are required to add backlinks, we need to "requantize" the query side for all the already inserted nodes. However, this can add a significant overhead (requantizing each node many many times). So, quantizing the "query side" once up front provides a nice optimization at the cost of some disk.

I think for rescoring, when asymmetric quantization is used, we could just rescore with the "query side" vectors. They are int4, which is as good as the "old int8".

That said, I would really hope we can improve HNSW merging by not having the "query side" written to disk at all. Instead, we should just query all the old graphs and insert into the new one. This removes the need to do backlinking at all (see: #15504 ). Even if we did that, we could rescore with the floating point vectors.

All around, I would really prefer us get HNSW merging to be more performant (many ideas here: #12440 ), before we start making it more expensive.

It's curious that we do use full precision scores on segment birth (newly indexed vectors), but quantized scores for merging. It means depending on your RAM buffer settings, numbers of threads, etc., you can "see" the effect on different HNSW graphs

Yeah, its weird. I wonder if we need to stop building the graph incrementally during indexing and instead wait until flush and use the quantized values there as well :).