You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "costin (via GitHub)" <gi...@apache.org> on 2026/09/10 20:06:41 UTC
[PR] Speed up concurrent HNSW merge through reduced beam insertion [lucene]
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speed up concurrent HNSW merge through reduced beam insertion [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova closed pull request #16664: Speed up concurrent HNSW merge through reduced beam insertion
URL: https://github.com/apache/lucene/pull/16664
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speed up concurrent HNSW merge through reduced beam insertion [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on PR #16664:
URL: https://github.com/apache/lucene/pull/16664#issuecomment-5636185836
@costin Thanks for tackling concurrent merges.
Before you invest more here: I'm not convinced by this approach. The sequential algorithm was designed around the join set, which gives two guarantees — coverage and ordering. `CompletedNeighborEps` correctly replaces ordering, but nothing replaces coverage: a node takes the reduced beam off whichever single neighbor happens to be finished, so anchor quality is arbitrary and varies run to run. We keep the half of the algorithm that spends less and drop the half that paid for it.
I'm also concerned about the extra heap: ~12 bytes per vector retained for the whole graph build
---
I like the goal, but I think the shape is wrong, and both problems trace back to partitioning work by *merged* ordinal ranges — a worker then no longer knows which graph its node came from, hence the reverse-lookup tables and the lost
guarantee.
We can explore an alternative approach to partition per source graph instead, with two concurrent phases and a barrier: join set at full beam, then the remainder with eps. That keeps both guarantees, makes the decision deterministic, and removes the per-vector tables.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speed up concurrent HNSW merge through reduced beam insertion [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on PR #16664:
URL: https://github.com/apache/lucene/pull/16664#issuecomment-5914051448
I see some performance numbers here, but it is also important to report recall, especially under different merge scenarios. In the past we've seen significant degradation due to a low deletion rate accumulating errors over many merges, but we had only tested merging segments with a higher deletion rate. I want to avoid that kind of trap with thorough testing of anything that has the potential to impact the graph quality, as I think this does (from the description - I haven't looked at the implementation).
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speed up concurrent HNSW merge through reduced beam insertion [lucene]
Posted by "costin (via GitHub)" <gi...@apache.org>.
costin commented on PR #16664:
URL: https://github.com/apache/lucene/pull/16664#issuecomment-5687267715
Thanks for the review.
This is going to be a long answer as my understanding of the algorithm might be incomplete hence trying to articulate my findings :)
To reduce memory, I dropped the reverse maps which connected a merged ordinal back to source graph / source ordinal). Now threads "steal" leftover work as (source graph, source ordinal) and look up the merged ordinal through the forward ordMaps, which the sequential path already had. The concurrent path still uses a completion bitset and a steal cursor. Note that both exist only while the graph is being built.
Regarding coverage, thanks for pointing that out; the first revision did not enforce it and the reduced beam ran off whichever neighbour happed to be finished; non zero but also non guaranteed.
I've fixed that in this PR and traded some speed in the process: before, reduced beam ran off whichever neighbor happened to be finished, this has now changed so that join-set nodes now always take full beam.
A remainder node takes reduced beam only if _at least one_ of its leftover neighbors was already inserted with full beam; otherwise it takes full beam as well.
Furthermore, entry points are all completed same-source leftover neighbors plus their current layer-0 neighbors in the output graph, not a single finished neighbor.
I also noticed leftover neighbors that were not inserted yet, were getting dropped from the candidate set. Leftover vertices are now pre-added on layer 0 before insert starts. On the cheap path those leftover neighbors are unioned into the candidate set after the reduced search. The pruning occurs as usual however there's more "diversity" to choose from.
I experimented with waiting for the join set before cheap inserts, and assigning one worker per leftover graph but neither proved successful. The barrier on the join set did not improve the GIST recall and the one worker per leftover graph ended up slowing the force-merge on GIST, since the merge ends up on a single leaf with hundreds of thousands of vectors (and thus becoming a bottleneck) instead of many tiny graphs, effectively no paralleism.
For better benchmarking, I used luceneutil instead of 5×100k random.
Cohere-1024 was already close in the first review so I've picked GIST-960 500k as is
the dataset that actually showed lost quality in my tests.
### Benchmark
GIST-960 500k
AMD EPYC 7R32 (c5a.2xlarge), JDK 25, M=16, beam=100, 8 workers. 3 runs (table shows the mean).
| path | runs | workers | R@10 | R@100 | multi-seg R@10 | force_merge_s | vs concurrent |
| --- | --- | --- | --- | --- | --- | --- | --- |
| this encoding | 3 | 8 | 0.834 | 0.818 | 0.920 | 52 | ×0.72 |
| concurrent full beam | 3 | 8 | 0.835 | 0.821 | 0.926 | 72 | ×1.00 |
| sequential leftover | 1 | 1 | 0.816 | 0.797 | — | 170 | — |
The results are quite promising and the speed improvement still shows up.
Let me know what you think.
P.S. I've added sequential leftover however since the bench occurred on a different machine and different number of segments so it's there for recall not speedup.
Thanks!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speed up concurrent HNSW merge through reduced beam insertion [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on PR #16664:
URL: https://github.com/apache/lucene/pull/16664#issuecomment-6171486141
Closing in favour of #16794, which solves the same problem by splitting work per source graph, with a barrier between the join set and the remaining nodes. That keeps the serial algorithm's guarantees (with 1 worker the graph is identical to the serial merge) and needs about 1 bit per vector instead of per-vector lookup tables. Thanks @costin for kicking this off!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org