You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "ethbak (via GitHub)" <gi...@apache.org> on 2026/08/24 20:42:19 UTC
[I] HNSW graph-reuse-during-merge progressively degrades recall over successive low-delete merges (disconnected-node repair threshold is per-merge-relative, preventing re-diversification) [lucene]
ethbak opened a new issue, #16552:
URL: https://github.com/apache/lucene/issues/16552
### Description
## Summary
When `IncrementalHnswGraphMerger` reuses an existing segment's HNSW graph as the base for a merged segment (introduced in #15003), a surviving node's neighbor list is copied **verbatim minus its deleted neighbors**. The node is repaired (searched for replacement neighbors) **only if it lost more than 15% of its neighbors _in that single merge_** (`DISCONNECTED_NODE_FACTOR = 0.85`).
The threshold is relative to the node's **current** (potentially already thinned) degree at the start of each merge, not its target or original degree. Therefore, nodes that lose only a small fraction of their neighbors (<15%) stay above the threshold every time, and are never flagged and repaired, so their degree decays silently across merge generations with no re-diversification / repair.
This results in **progressive degradation of search recall as merges accumulate**. It's most pronounced at **low per-merge delete rates (<1–2%)**, after many generations of merges, which I'd think is a pretty realistic / common case in real implementations.
## Mechanism
`InitializedHnswGraphBuilder.copyGraphStructure` copies each surviving node's neighbors, dropping deleted ones, and flags the node for repair only against *this merge's* input degree:
```java
// oldNeighbourCount is counted from THIS merge's input graph (already thinned by prior merges)
int oldNeighbourCount = 0;
for (int oldNeighbor = initializerGraph.nextNeighbor(); oldNeighbor != NO_MORE_DOCS; oldNeighbor = initializerGraph.nextNeighbor()) {
oldNeighbourCount++;
int newNeighbor = newOrdMap[oldNeighbor];
if (newNeighbor != -1) { // keep only non-deleted neighbors — verbatim, no re-diversification
newNeighbors.addOutOfOrder(newNeighbor, Float.NaN);
}
}
// repaired only if it lost > 15% of its *current* neighbors this merge
if (newNeighbors.size() < oldNeighbourCount * DISCONNECTED_NODE_FACTOR) { // DISCONNECTED_NODE_FACTOR = 0.85
disconnectedNodes.add(newOrd);
}
```
([link to DISCONNECTED_NODE_FACTOR](https://github.com/apache/lucene/blob/d85fc27bb36be862130a602984f5c7e244503457/lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java#L79)) ([link to mechanism](https://github.com/apache/lucene/blob/d85fc27bb36be862130a602984f5c7e244503457/lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java#L259-L262))
Because `oldNeighbourCount` resets to the shrinking current degree every merge, the check **can't observe cumulative degradation**. A node losing ≤15% per merge stays ≥ 0.85× each time, so after `n` merges it could be as disconnected as `0.85ⁿ` of its original degree (worst case), **never once repaired**.
## Reproduction (luceneutil)
Utilized two upstream builds that only differ in reuse.
- **RE-USE ON**: stock `main` (reuse on, `DELETE_PCT_THRESHOLD = 40`).
- **RE-USE OFF**: the same with `DELETE_PCT_THRESHOLD = 0`, so re-use is never applied to ANY segment with ANY deletes.
Used a harness around `KnnGraphTester` to run a multi-generation delete-only loop:
1. index `ndoc` docs
2. `forceMerge(1)`
3. Then per generation, delete X% of live docs and `forceMerge(1)` again. This second merge is a reuse merge on a delete-carrying base.
4. Each generation, measure set-overlap recall vs brute-force exact NN over the live docs, plus level-0 mean out-degree. Both arms share a deterministic base (single index thread), so they start identical.
Params:
- `ndoc=100000`
- `M=32`
- `beamWidth=250`
- unquantized float32
- `X=2%` deletes/generation
- `N=50` generations
## Evidence: glove-100, M=32, 2% deletes/generation
RE-USE ON vs RE-USE OFF baseline over the identical per-generation live set (so Δ isolates the graph-construction difference):
### Delete only (delete docs per generation, don't add any docs)
| gen | recall@100 RE-USE OFF | recall@100 RE-USE ON | Δ recall@100 | L0 out-deg OFF | L0 out-deg ON |
|----|----|----|----|----|----|
| 0 | 0.847 | 0.847 | 0.0pp | 28.33 | 28.33 |
| 10 | 0.862 | 0.850 | −1.2pp | 29.25 | 23.67 |
| 20 | 0.886 | 0.855 | −3.1pp | 30.10 | 20.24 |
| 30 | 0.901 | 0.842 | −5.9pp | 30.94 | 17.85 |
| 40 | 0.923 | 0.854 | −6.9pp | 31.72 | 16.34 |
| 50 | 0.930 | 0.860 | −7.0pp | 32.37 | 15.50 |
### Delete-only with `DISCONNECTED_NODE_FACTOR=1.00` (proves mechanism)
| gen | recall@100 RE-USE OFF | recall@100 RE-USE ON | Δ recall@100 | L0 out-deg OFF | L0 out-deg ON |
|----|----|----|----|----|----|
| 0 | 0.847 | 0.847 | +0.0pp | 28.33 | 28.33 |
| 10 | 0.862 | 0.891 | +2.9pp | 29.25 | 32.30 |
| 20 | 0.886 | 0.908 | +2.2pp | 30.10 | 32.31 |
| 30 | 0.901 | 0.912 | +1.1pp | 30.94 | 32.51 |
| 40 | 0.923 | 0.930 | +0.7pp | 31.72 | 32.88 |
| 50 | 0.930 | 0.934 | +0.4pp | 32.37 | 33.27 |
### Churn (delete and add new docs each generation to keep corpus a consistent size)
| gen | recall@100 RE-USE OFF | recall@100 RE-USE ON | Δ recall@100 | L0 out-deg OFF | L0 out-deg ON |
|----|----|----|----|----|----|
| 0 | 0.847 | 0.847 | +0.0pp | 28.33 | 28.33 |
| 10 | 0.866 | 0.854 | −1.2pp | 29.75 | 23.56 |
| 20 | 0.887 | 0.857 | −3.0pp | 30.74 | 20.67 |
| 30 | 0.910 | 0.876 | −3.4pp | 31.21 | 18.94 |
| 40 | 0.927 | 0.896 | −3.1pp | 31.55 | 18.02 |
| 50 | 0.937 | 0.910 | −2.7pp | 31.44 | 17.33 |
### Visual: Baseline (RE-USE OFF) vs. RE-USE ON (bug) vs. RE-USE ON with potential fix (0.85 → 1.00)
<img width="2125" height="1000" alt="Image" src="https://github.com/user-attachments/assets/e008a579-9914-497b-a9db-d7bf5a96fe51" />
### Conclusions
- **RE-USE ON** level-0 out-degree decays geometrically: 28.33 → 15.50 (0.547x, ≈0.98/generation), while the full-rebuild baseline holds ~flat (32.37). This shows the corpus effect of the compounding thinning.
- **recall@100 diverges from 0 to −7.0pp** (deletes only), or from 0 to ~-3% (churn deletes+adds) by generation 50
- Absolute recall improves over generations, yet the difference in recall between RE-USE ON and RE-USE OFF widens.
- Recall with **DISCONNECTED_NODE_FACTOR=1.00** is BETTER than just rebuilding each graph from scratch, proving the re-diversification mechanism works, the issue is only that connections are not being repaired on smaller iterative disconnections.
This contrasts with #15003's validation because its iterative 10%/gen test used too high of a deletion percentage, meaning at 10% deletion per segment, many nodes cross the 15% disconnected threshold and trigger the repair.
## Why it went unnoticed
- Correct graph, no functional symptom, only recall degrades slowly
- Standard KNN benchmarks build a fresh index and measure once, so a multi-generation delete/merge-churn recall regression would not surface in them.
- #15003's validation used high delete% (repair fires) and few generations.
- The per-merge-relative threshold hides slow erosion by construction.
## Some ideas to fix (feedback appreciated!)
- Make the disconnected-node test relative to the **target degree** (`M`, or `2M` at level 0) or the node's original degree, instead of its current degree.
- Track cumulative degradation across merges (e.g. persist a target/original degree per node).
- Increase DISCONNECTED_NODE_FACTOR to near 100% (if performance permits), or tune it as a function of segment delete percent and layer-0 out degree.
## Related
- #15003
- #15427
- #15429
- #16400
### Version and environment details
- Lucene `main` @ `d85fc27`
- JDK Corretto 25
- aarch64 Graviton
- 64-core
- Can provide raw artifacts/logs from benchmarking and setup if needed
--
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.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: [I] HNSW graph-reuse-during-merge progressively degrades recall over successive low-delete merges (disconnected-node repair threshold is per-merge-relative, preventing re-diversification) [lucene]
Posted by "ethbak (via GitHub)" <gi...@apache.org>.
ethbak commented on issue #16552:
URL: https://github.com/apache/lucene/issues/16552#issuecomment-5414678913
It seems @msokolov predicted this issue while the initial PR was still in review, but the fix never made it into the merged code. https://github.com/apache/lucene/pull/15003#issuecomment-3250002372
> there is the possibility of creeping graph rot where we continually erode the graph through repeated merges, and each time the deletion % gets reset to 0 so we think everything looks fine? … examine some metric that persists across merges, like graph connectivity. We could (for example) check for nodes whose outdegree drops below 50% of maxconn, and in those cases, use searches to "patch up" the graph?
The `outdegree < 50% of maxConn` idea was benchmarked in https://github.com/apache/lucene/pull/15003#issuecomment-3499486112, but was discarded in favor of the relative, 15% single merge loss, implementation due to performance (naive implementation which simply repaired all nodes with outdegree < 50% M erased nearly all performance gains, taking **73.1%** of merge time with NO RE-USE). Since the case with small delete percentage over many iterations was not benchmarked, the cost of using the relative approach over the absolute was not fully understood.
Performance was so poor in the previous absolute maxConn benchmark run because some nodes are sparse by design, and even in a healthy graph built from scratch, they have fewer than .5 * maxConn connections. @benwtrent pointed this out https://github.com/apache/lucene/pull/15003#issuecomment-3497692104:
> I bet the issue with higher maxconn is that the layer is sparsely connected already, meaning very few deletes throw you under the 50% threshold … make that 50% relative to the connections the graph had BEFORE the deletes?
BUT, we can avoid this issue somewhat by only applying the cap-relative clause **when the node actually lost at least one neighbor in the current merge**. A sparse-but-stable node that lost nothing is never touched. This would improve merge performance (won't repeatedly fire re-diversification on nodes that are sparse by design, unless they actually lost a connection) and has some nice properties:
- It doesn't change behavior on very sparse nodes at all. With the current 0.85 factor, a single lost neighbor already exceeds 15% once a node is down to ~6 or fewer connections (`1 > 0.15 * 6`), so those nodes were already being repaired on any loss, and the loss-gate preserves that.
- Instead, it extends protection to the higher-degree nodes that currently slip through when they lose a little each merge, stay above the 15%-relative bar every time, and erode unchecked.
I'm currently working on an implementation for this locally and am mid-benchmarking but the results so far look very promising, it looks like we may be able to restore the recall while maintaining a bigger improvement in merge time performance (~25% of rebuild time, vs. 73.1% that was initially benchmarked, ~3x speedup).
--
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: [I] HNSW graph-reuse-during-merge progressively degrades recall over successive low-delete merges (disconnected-node repair threshold is per-merge-relative, preventing re-diversification) [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on issue #16552:
URL: https://github.com/apache/lucene/issues/16552#issuecomment-5424137570
> BUT, we can avoid this issue somewhat by only applying the cap-relative clause when the node actually lost at least one neighbor in the current merge.
This is a nice idea!
--
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: [I] HNSW graph-reuse-during-merge progressively degrades recall over successive low-delete merges (disconnected-node repair threshold is per-merge-relative, preventing re-diversification) [lucene]
Posted by "ethbak (via GitHub)" <gi...@apache.org>.
ethbak commented on issue #16552:
URL: https://github.com/apache/lucene/issues/16552#issuecomment-5416468983
Adding this benchmarking data here to show the tradeoff between recall and merge time:
All benchmarks run on JDK Corretto 25, aarch64 Graviton, 64-core. Tested via `luceneutil` with GloVe-100, M=32, beamWidth=250, 2% deletes per generation, 100 generations, deterministic base for all arms.
### Benchmarks
**Delete-only** (each generation deletes 2% of the live docs, 100k starting docs, ~13k ending docs):
| `CUMULATIVE_DEGREE_FLOOR_FACTOR` | Δ recall@100 (gen 50 / gen 100) | L0 out-degree (gen 100) | force-merge time / gen |
|---|---|---|---|
| current (`main`) | −7.0 / −5.6 pp | 15.5 | 2.0 s |
| 0.35 | −1.6 / −0.3 | 26.2 | 8.1 s |
| 0.40 | −1.1 / +0.2 | 28.0 | 9.3 s |
| 0.45 | −0.8 / +0.5 | 29.5 | 11.2 s |
| **0.50** | **−0.4 / +0.7** | **30.7** | **12.4 s** |
| 0.55 | +0.1 / +0.9 | 32.0 | 14.7 s |
| 0.60 | +0.4 / +0.9 | 32.8 | 16.0 s |
| 0.85 | +0.7 / +1.3 | 34.7 | 21.2 s |
| rebuild (control) | 0 | 34.7 | 41.8 s |
**Churn** (each generation deletes 2% and re-adds the same count randomly, holding the corpus at 100k, so each gen is full-scale):
| `CUMULATIVE_DEGREE_FLOOR_FACTOR` | Δ recall@100 (gen 50 / gen 100) | L0 out-degree (gen 100) |
|---|---|---|
| current (`main`) | −2.7 / −2.9 pp | 14.3 |
| 0.40 | −0.1 / −0.2 | 21.8 |
| **0.50** | **+0.3 / +0.2** | **23.2** |
| rebuild (control) | 0 | 26.5 |
### Visual
<img width="2009" height="1430" alt="16552-benchmarks" src="https://github.com/user-attachments/assets/c9d53086-258e-46f9-9c8d-751e40b86dd3" />
### Tuning
The results show that `0.5` is the point which best balances the tradeoff between recall and merge cost, the below table shows the 'Kneedle score', which finds the perpendicular distance of each point above the endpoint chord of the (merge cost, recall) curve on min-max-normalized axes. The point with the highest score is the knee, which balances the tradeoff with the least diminishing returns.
| FLOOR | 0.35 | 0.4 | 0.45 | **0.5** | 0.55 | 0.6 | 0.65 | 0.85 |
|---|---|---|---|---|---|---|---|---|
| Δ recall vs rebuild (pp) | −1.38 | −0.64 | −0.57 | **−0.04** | +0.15 | +0.19 | +0.60 | +0.70 |
| merge cost (s, full corpus) | 8.1 | 9.3 | 11.2 | **12.4** | 14.7 | 16.0 | 18.1 | 21.2 |
| Kneedle score | 0.000 | 0.188 | 0.109 | **0.225** | 0.166 | 0.109 | 0.136 | 0.000 |
### Results / Conclusions
Using a CUMULATIVE_DEGREE_FLOOR_FACTOR to track deletion drift over many merges and re-diversify when nodes' connections are slowly eroded at less than 15% neighbors per merge allows us to maintain most of the performance improvement originally introduced in #15003 while restoring correctness/recall in cases with slow low-delete percentage drift.
We maintain a **70.3%** speedup when comparing to full graph re-build every time with no re-use, which is unfortunately not as strong as the **95.2%** speedup in the buggy implementation. However, this additional merge time is simply due to re-diversifying nodes that genuinely need repairing (they all lost at least one neighbor and are sparse under 0.5 * maxConn), while the original implementation wrongfully skipped them (so it's speedup % should not be taken at face value).
`CUMULATIVE_DEGREE_FLOOR_FACTOR = 0.5` seems to be the natural choice as it is the 'knee' which best balances the improved recall with the increased merge time (kneedle) and has strong intuition to aim for half of the maximum connection value.
--
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: [I] HNSW graph-reuse-during-merge progressively degrades recall over successive low-delete merges (disconnected-node repair threshold is per-merge-relative, preventing re-diversification) [lucene]
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov closed issue #16552: HNSW graph-reuse-during-merge progressively degrades recall over successive low-delete merges (disconnected-node repair threshold is per-merge-relative, preventing re-diversification)
URL: https://github.com/apache/lucene/issues/16552
--
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