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: [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]
