Pranshu-S commented on issue #16029: URL: https://github.com/apache/lucene/issues/16029#issuecomment-5323519668
I’ve been independently [experimenting](https://github.com/Pranshu-S/k-NN/blob/track2-adaptive-rescore/src/test/java/org/opensearch/knn/research/Track2RhtBbqTests.java) with the low-bit quantization pieces discussed here, and wanted to share a few results that seem complementary to #16092 and #16030. I initially tested structured Hadamard preconditioning against Lucene’s existing 1-bit BBQ scoring path. I later found #16092, which is implementing essentially the same direction more completely (sign flips + permutation + block FWHT), so I don’t think there is a separate rotation proposal here. What may still be useful is the decomposition of where the gain comes from, especially on Fashion-MNIST, which has historically exposed distribution sensitivity in binary quantization. ### Setup My baseline reproduces the Lucene 10.4 Euclidean BBQ scoring path: - `OptimizedScalarQuantizer` - 1-bit document quantization - 4-bit asymmetric query quantization - `packAsBinary` - `transposeHalfByte` - `VectorUtil.int4BitDotProduct` - existing Lucene corrective terms The experimental variant applies a deterministic random-sign + dimension-preserving block-Hadamard transform to documents and queries before running the **same BBQ pipeline**. My transform currently does **not** include the random permutation used by #16092, so I plan to rerun these using the implementation from that PR for an exact comparison. The primary metric here is candidate recall@10 before fp32 reranking. ### Fashion-MNIST-784 20K vectors, 200 held-out queries, Euclidean, HNSW `M=16`, `beamWidth=100`. | Representation | Flat top-10 overlap | Candidate k for ≥0.90 | ≥0.95 | ≥0.99 | |---|---:|---:|---:|---:| | fp32 | 1.000 | 10 | 10 | 20 | | BBQ | 0.515 | 75 | 100 | 200 | | Hadamard → BBQ | 0.768 | 20 | 30 | 50 | BBQ and Hadamard → BBQ use the same stored representation in this experiment: - 104 B packed code - 16 B corrective metadata - 120 B/vector total ### Holding graph topology fixed I also built a single HNSW graph using fp32 distances and searched the **same graph** using each scorer: | Scorer | Candidate k for ≥0.90 | ≥0.95 | ≥0.97 | |---|---:|---:|---:| | fp32 | 10 | 10 | 20 | | BBQ | 50 | 75 | 100 | | Hadamard → BBQ | 20 | 30 | 30 | So at least on this dataset, the improvement is not only coming from building a different graph — the preconditioned scorer also navigates the same graph substantially better. ### Isotropic control I repeated the experiment on 15K iid Gaussian 784-D vectors: | Representation | Candidate k for ≥0.95 | |---|---:| | fp32 | 500 | | BBQ | 750 | | Hadamard → BBQ | 750 | I therefore did **not** observe the same candidate-threshold improvement when the input was already isotropic. That seems consistent with the direction being discussed in #16092 / #16030: preconditioning is most valuable when the component distribution is unfavorable for scalar quantization, while data-blind quantization should become more attractive once vectors are sufficiently well-conditioned. So #16030 and #16092 look complementary rather than competing approaches. ### One question this raised for me I also experimented with a RaBitQ-inspired normalized 1-bit representation / estimator. The interesting part was that on some distributions, changing the **estimator** produced a much larger gain than rotation alone. For example, on an iid Gaussian 784-D experiment: | Representation | Candidate recall@10 at k=500 | |---|---:| | Uniform 1-bit | 0.698 | | Hadamard 1-bit | 0.730 | | RaBitQ-inspired 1-bit + per-vector correction | 0.968 | | 4-bit | 0.963 | | fp32 | 0.970 | The RaBitQ-inspired representation uses a 1-bit sign code plus 8 bytes/vector of correction metadata, which is approximately `1.08 bits/dim` at 784D. This is currently a quality prototype rather than a production codec, so I’m not making performance claims from it yet. That leaves me wondering whether, once #16092-style preconditioning is in place, there is still value in exploring the **distance-estimation side independently**: > Is the existing BBQ estimator good enough after preconditioning, or are there distributions where a normalized / per-vector corrected estimator still materially improves low-bit HNSW traversal? My next step was going to be: 1. rerun the Fashion-MNIST experiment using the exact `HadamardRotation` implementation from #16092; 2. compare centered vs data-blind quantization (#16030) with and without preconditioning; 3. compare the preconditioned BBQ scorer against the corrected 1-bit estimator, holding graph topology fixed where possible. Would that be useful data for this issue, or would the estimator part be better discussed separately from the data-blind / preconditioning work? -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
