Can we add configuration on dropping raw vectors from quantized formats after some period of time?

[benwtrent]

Description

Tangentially related to: #13158

But, I have observed, that as the corpus reaches a fairly large size, the actual quantiles aren't changing much at all during segment merges. This is tricky to fully measure and make a promise about lossiness (users can always just start throwing garbage that shakes up the whole world). But if the data isn't a "bad actor", quantiles and quantization buckets become fairly stable over time.

Maybe we should add a configuration option, or a new codec, or some way to drop the raw floating point vectors. The 4x reduction in disk usage would be really nice for many use-cases.

I am not 100% sure how this would look (a threshold provided by the user, or we just do it based on internal statistics).

[mikemccand]

This is a neat idea -- it would allow the user to accept some "lossy compression" when they know/expect that loss will be minor for their use case. Sort of like JPEG vs RAW image encoding.

One question (I don't know enough about how the HNSW merging works): if we did this, and segments with these "only the quantized vectors remain" are merged, we would have to use those quantized vectors to build the next HNSW graph right? (Whereas today we always go back to the full precision vectors to build the graph for the newly merged segment?). Or are we always using the quantized vectors to build the graph?

I suppose, if using the quantized vectors at search time is not hurting much, because the "quantization noise" in the resulting distance computation between two vectors is negligible, then building the graph off of the quantized forms should also not hurt much since that graph building is really just doing a bunch of searching to get the top K vectors that should be linked up in the graph?

[jmazanec15]

I think it would make sense to be config option as opposed to default behavior. One reason during search I see for keeping vectors would be for doing a second phase full precision disk based re-score over initial search results of quantized structure to improve recall. This might make more sense at more aggressive quantization levels.

[msokolov]

If we were to a dd a config option what would it look like? I guess the key elements are: quantization is one-and-done; no re-evaluation on merging, and therefore any data required only for indexing can be dropped. This could be true whether or not some higher-precision vectors are preserved for re-ranking. I mean it's conceivable we'd want to quantize at 1 bit for recall and 8 bits for re-ranking? To me the key choice is whether to re-evaluate quantization bounds on merge. I actually wonder if with OSQ this is ever necessary since it is computing bounds per-vector?

[mccullocht]

There was some discussion of this on #15903 since the proposed format is data blind.

• OSQ quantizes the residual against a mean vector computed from the input segment. You would want to break this dependency to discard the raw vectors at ingestion time and rotation might help cover some of the losses. I could also see discarding the raw vectors at some later point if we believe the mean isn't moving but that might be trickier than dropping them at ingestion.
• A technique that OSQ doesn't implement but appears in one of the source papers (Intel LVQ) is quantizing the residual, e.g. for some vector v quantize v - dequantize(quantize(v)) and use this for re-ranking.

[mikemccand]

Thanks @mccullocht -- it looks like that discussion starts around this comment (#15903 is getting big -- final inch is hard!).

With BBQ supporting pre-conditioning (and also the proposed TurboQuant I think), which normalizes model-output dimensional irregularities in the incoming vectors (luceneutil's knnPerfTest.py smells query/document vectors to try to spot such mis-behaving dimensions/vectors/corpora) can't we always use a data-blind quantization if pre-conditioning is enabled? All dimensions should look nicely uniform, carry the same (ish) information content the same (ish) normal value distributions?

And then if the quantization is data-blind, can't we expose the option to always drop the full precision vectors? Users may still want to keep them around if they are re-ranking or so... but merging would no longer lose information if the quantization is data blind?

(Hmm, maybe not -- in the adversarial cases where vectors are very tightly clustered, not utilizing the full vector space, random rotation won't fix that, and centering is then probably still helpful).

A technique that OSQ doesn't implement but appears in one of the source papers (Intel LVQ) is quantizing the residual, e.g. for some vector v quantize v - dequantize(quantize(v)) and use this for re-ranking.

That sounds like a great idea! Rather than wastefully / independently storing your higher precision vectors for reranking, take advantage of the quantized form (used for first pass vector retrieval) and build on it. Maybe I quantize to 2 bits for first pass, and use 4 bits for second pass, which would equate (ish) to reranking with 6 bit precision vectors (if we quantized the residuals), vs today where it would just be reranking with 4 bits.

But how would we model this in Lucene? Would it somehow be a 2nd vector field which magically pulls the residual vector from the 1st field (sheesh, another example of spooky/magical field to field interaction within one Document...).

[mikemccand]

• A technique that OSQ doesn't implement but appears in one of the source papers (Intel LVQ) is quantizing the residual, e.g. for some vector v quantize v - dequantize(quantize(v)) and use this for re-ranking.

I think it's this paper from Intel? And also implemented in their GitHub project ScalableVectorSearch -- ASL 2 licensed (like Lucene) so we can peruse / poach / borrow ideas/implementations!

[mccullocht]

(Hmm, maybe not -- in the adversarial cases where vectors are very tightly clustered, not utilizing the full vector space, random rotation won't fix that, and centering is then probably still helpful).

The comment you linked showed that centering is still valuable -- even after rotation -- so I don't want to be too opinionated in terms of what we provide. In particular centering appears to be much more valuable than rotation at lower bit rates, really maximizing the value of what little information you have available.

We can have an option to drop full precision vectors if the codec is configured to be data blind (OSQ can already do this by making the center the 0 vector). I poked at this for an hour or so and the tricky part is merging mixed input where some segments are already quantized and some are float-only. Whatever you might think of it the current codec is a lot simpler for the assumption of float input.

But how would we model this in Lucene? Would it somehow be a 2nd vector field which magically pulls the residual vector from the 1st field (sheesh, another example of spooky/magical field to field interaction within one Document...).

I think you can hide it all in one field. You may want a second file for the residual vectors so it's easy to avoid them when warming an index. After that you can use a rescorer to compare a float input to primary+residual vector. Comparison can happen by either (a) decoding the primary and residual vectors into a float vector and performing direct comparison or (b) quantizing the target vector and summing the results of the primary and residual vector comparison.

I think it's this paper from Intel? And also implemented in their GitHub project ScalableVectorSearch -- ASL 2 licensed (like Lucene) so we can peruse / poach / borrow ideas/implementations!

This is indeed the paper I was thinking of. There is a second paper that describes a packing scheme to make comparisons between vectors of different bit rates (e.g. 2-bit vector against 4-bit vector) cheaper. Last I looked they had hidden the implementation and were distributing pre-compiled objects, good to see they changed their minds.