ethbak opened a new pull request, #16559: URL: https://github.com/apache/lucene/pull/16559
### Description When `IncrementalHnswGraphMerger` reuses an existing segment's HNSW graph as the base for a merged segment (#15003), a surviving node's neighbor list is copied minus its deleted neighbors. The node is then repaired only if it lost more than 15% of its neighbors *in that single merge* (`DISCONNECTED_NODE_FACTOR = 0.85`). That threshold resets every merge, so a node that sheds only a small fraction each time never trips it. Its out-degree decays across successive merges and approximate-search recall drops with it. The effect is worst under continuous low-rate deletes, where an index accumulates a few percent of deletions between merges. This adds a second, cumulative check in `InitializedHnswGraphBuilder.copyGraphStructure`: a node that lost at least one neighbor this merge and whose out-degree has fallen below `CUMULATIVE_DEGREE_FLOOR_FACTOR` (0.5) of the level's connection budget (`2*M` at level 0, `M` above) is flagged for repair. Anchoring on the fixed per-level budget lets the check see decay that accumulates across merges, which the existing prior-degree-relative check cannot. Gating on an actual neighbor loss means a node that is simply sparse and lost nothing is never touched, so healthy graphs are unaffected and unnecessary work is not done. The repair path itself is unchanged. ### Benchmarks **Setup:** luceneutil, GloVe-100, `M=32`, `beamWidth=250`, 2% deletes per generation, 100 generations, deterministic base. "current" is `main`; "rebuild" is the same build with reuse disabled (`DELETE_PCT_THRESHOLD=-1`), i.e. a full rebuild every merge, which is the ground truth the reused graph is measured against. Recall is reported as Δ vs rebuild on the identical per-generation live set; out-degree is the level-0 mean. **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 | Reuse-on out-degree decays geometrically (28 → 15 delete-only), and recall diverges from the full-rebuild graph as merges accumulate. Recall recovers as the floor rises and saturates around 0.5; higher floors add merge cost for no further recall. At 0.5 the merged graph matches full-rebuild recall on both workloads while merging at roughly a third of a full rebuild's cost. The small positive Δ values are within run-to-run noise, since the rebuild graph is itself approximate. ### Visual <img width="2009" height="1430" alt="16552-benchmarks" src="https://github.com/user-attachments/assets/c9d53086-258e-46f9-9c8d-751e40b86dd3"; /> ### Tuning `CUMULATIVE_DEGREE_FLOOR_FACTOR = 0.5` was chosen in part due to benchmarking results, but also due to intuition about the distribution of the nodes by neighbor connections. 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 | These results make sense intuitively when we consider the insertion heuristic, which targets up to M connections per node on the upper levels and 2M at level 0: measured against that level-0 budget of 2M, a factor of 0.5 places the repair trigger at exactly M, the graph's per-node connection target. A node whose degree has decayed below M across successive merges has fallen beneath the connectivity the builder aims for, so repairing there restores it to a natural degree. Going lower waits until nodes are badly starved before acting (recall keeps sliding), while going higher spends merge cost re-connecting nodes that are still within the range the build naturally produces. ### Testing `./gradlew check` passes. Adds `TestHnswFloatVectorGraph#testReconnectsNodeDecayedBelowFloorDuringMerge`, a deterministic (fixed-seed) test that drives a single reuse-merge on a node engineered to sit just below the cumulative floor. It fails on the pre-fix builder (the node stays thinned) and passes with the fix (the node is reconnected). Closes #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: [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]
