costin opened a new pull request, #16664: URL: https://github.com/apache/lucene/pull/16664
When merging HNSW graphs concurrently, every non-base vector is inserted via full beam search from the graph entry point. The sequential merge path avoids this, by collecting neighborhood information as entry points to jump directly to level-0 search (reduced beam), however this optimization was never available in the concurrent path. This PR addressed that. To avoid the low recall due to multiple concurrent insertion, each worker shares information about its completed/seen nodes with the others workers using a lightweight (concurrent) bitset. Thus when inserting a node, each worker can check the node neighbors that have been already connected in the graph and use that for a reduced beam search instead of the full traversal. Early nodes use the full beam as before however, as the information propagates most of the other nodes start finding their neighbors and take the cheaper path. When no 0-delete source graphs are available, the mechanism is a no-op. ### Benchmark AMD EPYC 7R32 (c5a.2xlarge), JDK 25, M=16, beam=100, 8 workers. **5 x 100K random float32, dim=128** | | HNSW_ms | recall@10 | cheap% | speedup | |-----------|---------|-----------|--------|---------| | baseline | 72625 | 0.144 | — | — | | candidate | 40752 | 0.136 | 98.15 | 1.78x | **5 x 100K Cohere wiki-2023-11 embed-multilingual-v3, dim=1024** | | HNSW_ms | recall@10 | cheap% | speedup | |-----------|---------|-----------|--------|---------| | baseline | 152530 | 0.962 | — | — | | candidate | 76360 | 0.948 | 99.77 | 2.00x | Relates #12440 -- 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]
