Data-blind scalar quantization

[mccullocht]

Description

Add options for data-blind scalar quantization. Data blind quantization will allow users to drop the raw float vectors which will be a significant reduction in storage in all cases (~4x or more improvement) but limits flexibility (no re-quantization of input).

There are 3 parts to this change:

• Allow users to disable centering and drop the raw float vectors. This is usable at high bit rates (4-8 bits/dim) where users may not be interested in re-ranking the results.
• Implement random rotation of vectors and queries. This generates a more favorable value distribution for quantization and should help reclaim some of the accuracy losses in the first step.
• Implement residual vector quantization. After quantizing each vector v, quantize the residual v - dequantize(quantize(v)) and write it to separate storage. This vector can be used to boost accuracy during reranking/rescoring or vector decoding while still allowing fast/cheap representations for graph traversal. This makes data blind quantization more palatable at low bit rates (1-2 bits/dim).

[shubhamvishu]

Implement random rotation of vectors and queries. This generates a more favorable value distribution for quantization and should help reclaim some of the accuracy losses in the first step.

@mccullocht I have a working implementation solely for this with Claude's help (same Hadamard transform inspired by @xande 's PR #15903 but in isolation) and ran some luceneutil tests on cohere v3 with rotation enabled. Here are results :

BASELINE :

Results:
NOTE: nDoc = 500000 for all runs; skipping column
NOTE: searchType = KNN for all runs; skipping column
NOTE: topK = 100 for all runs; skipping column
NOTE: fanout = 100 for all runs; skipping column
NOTE: resultSimilarity = N/A for all runs; skipping column
NOTE: decay = N/A for all runs; skipping column
NOTE: resultCount = 100.000 for all runs; skipping column
NOTE: maxConn = 64 for all runs; skipping column
NOTE: beamWidth = 250 for all runs; skipping column
NOTE: num_segments = 1 for all runs; skipping column
NOTE: filterStrategy = null for all runs; skipping column
NOTE: filterSelectivity = N/A for all runs; skipping column
NOTE: overSample = 1.000 for all runs; skipping column
NOTE: bp-reorder = false for all runs; skipping column
NOTE: indexType = HNSW for all runs; skipping column
NOTE: rerank = no for all runs; skipping column
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.695        2.413   2.409        0.998     1 bits     9589     96.07       5204.65          110.07         2102.03      2020.836       67.711
 0.816        2.512   2.510        0.999     2 bits     8614     98.17       5093.00          137.36         2156.30      2081.871      128.746
 0.918        2.711   2.709        0.999     4 bits     8221     96.06       5205.08          135.73         2276.80      2204.895      251.770
 0.970        3.789   3.788        1.000     7 bits     8129    101.13       4944.28          228.06         2520.64      2449.036      495.911
 0.976        3.804   3.803        1.000     8 bits     8129    101.92       4905.71          230.64         2520.66      2449.036      495.911

 

CANDIDATE :

Results:
NOTE: nDoc = 500000 for all runs; skipping column
NOTE: searchType = KNN for all runs; skipping column
NOTE: topK = 100 for all runs; skipping column
NOTE: fanout = 100 for all runs; skipping column
NOTE: resultSimilarity = N/A for all runs; skipping column
NOTE: decay = N/A for all runs; skipping column
NOTE: resultCount = 100.000 for all runs; skipping column
NOTE: maxConn = 64 for all runs; skipping column
NOTE: beamWidth = 250 for all runs; skipping column
NOTE: num_segments = 1 for all runs; skipping column
NOTE: filterStrategy = null for all runs; skipping column
NOTE: filterSelectivity = N/A for all runs; skipping column
NOTE: overSample = 1.000 for all runs; skipping column
NOTE: bp-reorder = false for all runs; skipping column
NOTE: indexType = HNSW for all runs; skipping column
NOTE: rerank = no for all runs; skipping column
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.729        2.243   2.241        0.999     1 bits     9174     96.59       5176.47          100.21         2099.73      2020.836       67.711
 0.841        2.478   2.474        0.998     2 bits     8468     97.67       5119.12          128.30         2155.75      2081.871      128.746
 0.937        2.613   2.612        1.000     4 bits     8162    100.38       4980.97          124.06         2276.62      2204.895      251.770
 0.982        3.704   3.702        0.999     7 bits     8124    102.14       4895.48          227.00         2520.65      2449.036      495.911
 0.985        3.685   3.684        1.000     8 bits     8120     99.64       5017.91          227.74         2520.64      2449.036      495.911

 

Recall

Bits	Baseline	Rotation	Delta	% Gain
1	0.695	0.729	+0.034	+4.9%
2	0.816	0.841	+0.025	+3.1%
4	0.918	0.937	+0.019	+2.1%
7	0.970	0.982	+0.012	+1.2%
8	0.976	0.985	+0.009	+0.9%

[shubhamvishu]

I also ran the same luceneutil with 4K dimensional vectors and I see even higher impact to recall(~6-7% improvement) overall net-net with slight slowness in indexing-rate due to rotation overhead. Here is a summary of that :
 
Setup:

• 500K docs, 4096 dimensions, DOT_PRODUCT similarity, HNSW (maxConn=64, beamWidth=250), 10K queries.

Results

Bits	Avg Baseline Recall	Avg Candidate Recall(Rotation)	Avg Delta	% Diff
1	0.828	0.889	+0.061	+7.4%
2	0.858	0.916	+0.058	+6.7%
4	0.893	0.958	+0.066	+7.3%
7	0.920	0.972	+0.052	+5.6%
8	0.927	0.974	+0.047	+5.1%
All bits	0.885	0.942	+0.057	+6.4%

---

Metric	Baseline	Rotation	% Diff	Impact
Recall (avg all)	0.885	0.942	+6.4%	Improvement
Search latency	~2.0 ms	~2.0 ms	~0%	No change
Index rate	~3830 docs/s	~3620 docs/s	-5.5%	Slightly slower
Index size	8091-9799 MB	8091-9799 MB	0%	Identical
Force merge time	~213 s	~194 s	-8.9%	No regression

[mikemccand]

Implement random rotation of vectors and queries. This generates a more favorable value distribution for quantization and should help reclaim some of the accuracy losses in the first step.

@mccullocht I have a working implementation solely for this with Claude's help (same Hadamard transform inspired by @xande 's PR #15903 but in isolation) and ran some luceneutil tests on cohere v3 with rotation enabled. Here are results :

Very cool! Is this (standalone random rotation) something we could merge in luceneutil?

It's wild what this could unlock, what @mccullocht describes in OP.

• Implement residual vector quantization. After quantizing each vector v, quantize the residual v - dequantize(quantize(v)) and write it to separate storage. This vector can be used to boost accuracy during reranking/rescoring or vector decoding while still allowing fast/cheap representations for graph traversal. This makes data blind quantization more palatable at low bit rates (1-2 bits/dim).

At search time, how would we expose this? Somehow you need to use the original vector plus the quantized residuals to produce a more accurate vector for re-ranking. Maybe it'd have to be a dedicated reranking query that know about this Codec format... or maybe we could enhance KnnVectorsFormat API for first-class support, sort of a two-phased ranking API for vectors.

[mccullocht]

Residual vectors don't make sense as something to access on their own terms, but they can be accessed through FloatVectorValues via the rescorer(float[] query) API including them as part of the distance computation or via vectorValue() when the original float vectors aren't present.