Tony-X opened a new pull request, #16915: URL: https://github.com/apache/lucene/pull/16915
### Description **Stacked on #16914**; the first commit here is that PR and only the second commit, `Add PiPNN search-free HNSW graph construction for merges`, is new. Will be rebased once #16914 lands. Draft until then. Implements PiPNN ([Rubel et al., KDD 2026](https://arxiv.org/abs/2602.21247)) as an opt-in HNSW builder for merges. Closes #16906. Level 0 is built without graph search: - `PipnnPartitioner`: randomized ball carving into small overlapping leaves (fanout per level, leaf size bounded). The top-level assignment of all vectors to leaders and the in-leaf all-pairs scoring both run on `VectorUtil.dotProducts` over gathered, padded buffers (`GatheredVectors`, `LeaderAssigner`, `LeafProcessor`). - Every pair inside a leaf is scored once; each vector's nearest in-leaf neighbors stream into `PipnnCandidateReservoir`, a bounded per-node reservoir with direction hashing (HashPrune) so candidates stay diverse. - Final edges: the diversity heuristic with a Vamana-style `alpha`, a reverse-edge round through a second reservoir, then `connectComponents`. Level 0 is deterministic for a given seed regardless of thread scheduling. 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. Euclidean and cosine are derived from dot products and norms; byte and float16 encodings fall back to the scorer. Wiring: `Lucene99HnswVectorsFormat(M, beamWidth, numMergeWorkers, mergeExec, PipnnParams)`; when set, `Lucene99HnswVectorsWriter` uses `PipnnHnswGraphMerger` for merges. Default behaviour is untouched. One existing-code fix: `connectComponents` no longer adds a duplicate reverse link when `n1` already points to `n0`. ### Scope - Merges only, and only the rebuild-from-scratch branch (the path `HnswConcurrentMergeBuilder` takes today). When `IncrementalHnswGraphMerger` can initialize from an existing segment graph it inserts only the remaining vectors and that is unchanged; it still wins for the common no-deletes merge (graph-reuse force merge of 1M x 1024d: 54 s, versus 103-107 s for a PiPNN rebuild of all vectors). - Not flush: flush builds the graph incrementally today. **Open Q: do we expose that graph for queries? If not we can also speed up flush** - PiPNN uses the executor and worker count the merge already has (`numMergeWorkers` / `mergeExec`, or the intra-merge executor) and creates no threads of its own. All numbers below compare both builders at the same worker count. ### Results See the main issue https://github.com/apache/lucene/issues/16906 for results. -- 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]
