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