Tony-X opened a new issue, #16906: URL: https://github.com/apache/lucene/issues/16906
### Description HNSW merges that cannot reuse an existing graph (deletes, or no segment with a usable graph) rebuild it by inserting every vector with a beam search. That cost grows with `log n` per insertion, is random-access bound, and is the dominant part of a large force merge. [PiPNN (Rubel et al., KDD 2026) ](https://arxiv.org/abs/2602.21247) builds level 0 without any graph search: randomized ball carving splits the vectors into small overlapping leaves, every pair inside a leaf is scored, and each vector's nearest in-leaf neighbors stream into a bounded, direction-diverse candidate reservoir per node. The final neighbors come from the usual diversity heuristic plus a reverse-edge round. Because the work is a dense all-pairs scoring inside each leaf, it runs on a batched dot-product kernel at close to peak FMA throughput, is embarrassingly parallel, and is deterministic for a given seed regardless of thread scheduling. I have a prototype that keeps upper levels on the regular HNSW insertion, so the graph shape, reader and searcher are unchanged and this is purely a writer-side option. From-scratch build of 1M vectors, M=32, beam 100, 16 threads, Graviton2: | data | HNSW | PiPNN | speedup | |---|---|---|---| | Cohere v3 1024d | 152.5 s | 95.2 s | 1.60x | | Cohere truncated 128d | 50.9 s | 26.8 s | 1.90x | | Cohere truncated 512d | 96.6 s | 58.6 s | 1.65x | | Cohere replicated 2048d | 235.2 s | 176.5 s | 1.33x | Recall@100 / latency / node visited (from `KnnGraphTester`) | | fanout 0 | 50 | 100 | 200 | | --- | --- | --- | --- | --- | | baseline HNSW | 0.921 / 1.89 / 3038 | 0.951 / 2.61 / 4162 | 0.966 / 3.26 / 5219 | 0.980 / 4.53 / 7183 | | PiPNN alpha 1.0 | 0.879 / 1.54 / 2374 | 0.924 / 2.14 / 3301 | 0.946 / 2.69 / 4184 | 0.969 / 3.77 / 5859 | | PiPNN alpha 1.13 | 0.923 / 1.97 / 3146 | 0.953 / 2.83 / 4349 | 0.968 / 3.48 / 5492 | 0.982 / 4.85 / 7632 | Recall/latency of the resulting graph is on or slightly above HNSW's curve at every search fanout (with alpha=1.13). I plan two PRs: (1) `VectorUtil.dotProducts`, a blocked batch dot-product kernel, and (2) `PipnnGraphBuilder` / `PipnnHnswGraphMerger` plus an opt-in `Lucene99HnswVectorsFormat` constructor. --- # PR 1 **Title:** Add VectorUtil.dotProducts, a blocked batch dot-product kernel ### Description Adds `VectorUtil.dotProducts(a, aCount, b, bCount, dim, stride, out)`, which scores all `aCount x bCount` pairs between two sets of float vectors in one call, for builders that score a whole cluster of vectors against itself (needed by PiPNN). --- # PR 2 **Title:** Add PiPNN search-free HNSW graph construction for merges ### Description Implements PiPNN as an opt-in HNSW builder for merges. Depends on #PR1. Level 0 is built without graph search: - `PipnnPartitioner`: randomized ball carving into overlapping leaves (fanout per level, leaf size bounded). - `PipnnGraphBuilder.LeafProcessor`: gathers a leaf's vectors and scores every pair once with `VectorUtil.dotProducts` (euclidean and cosine derived from dot products and norms; other encodings go through the scorer). Each vector's nearest in-leaf neighbors are fed into - `PipnnCandidateReservoir`: a bounded per-node reservoir with direction hashing (HashPrune) so candidates stay diverse. - Final edges: the existing diversity heuristic, a reverse-edge round, then `connectComponents`. Upper levels use the regular HNSW insertion over the promoted nodes (`HnswGraphBuilder.connectNode` with a minimum level; concurrently under `HnswLock` when an executor is given). Graph shape, reader and searcher are unchanged. **Level 0 is deterministic for a given seed regardless of scheduling.** -- 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]
