(lucene) branch branch_10x updated: Fix join set degeneration on low-degree nodes (#16435) (#16438)

[ma...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

mayya-sharipova pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/branch_10x by this push:
     new 6a62b3c7a12 Fix join set degeneration on low-degree nodes (#16435) (#16438)
6a62b3c7a12 is described below

commit 6a62b3c7a1273b4bc94f96dbd04e609bedebd44d
Author: Mayya Sharipova <ma...@elastic.co>
AuthorDate: Thu Jul 30 14:52:08 2026 -0400

    Fix join set degeneration on low-degree nodes (#16435) (#16438)
    
    UpdateGraphsUtils#computeJoinSet asked for a coverage of 2 for every
    node with a degree below 9, including nodes with a degree of 1. Such a
    node can be covered at most once (only its neighbours can cover it), so
    the coverage was unsatisfiable and the node always ended up in the join
    set itself.
    
    On hub-and-spoke shaped graphs, which HNSW produces for 1-dimensional
    or heavily duplicated vectors, almost all nodes have a degree of 1, so
    the join set degenerated to the whole graph and merging lost all its
    savings. Clamp the requested coverage by the node's degree; graphs
    where all nodes have a degree of 2 or more are unaffected.
    
    Fixes #16251
---
 lucene/CHANGES.txt                                   |  5 +++++
 .../apache/lucene/util/hnsw/UpdateGraphsUtils.java   | 20 ++++++++++++++++++--
 2 files changed, 23 insertions(+), 2 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index f03aa38c498..245162d24d5 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -85,6 +85,11 @@ Optimizations
 
 Bug Fixes
 ---------------------
+* GITHUB#16251: Fix UpdateGraphsUtils#computeJoinSet to not request more coverage for a node than
+  the node's degree. Previously nodes with a degree of 1 were always forced into the join set,
+  which made the join set degenerate to the whole graph on hub-and-spoke shaped HNSW graphs.
+  (Mayya Sharipova)
+
 * GITHUB#16350: Disable bulk-scoring in monitor queries. (Alan Woodward)
 
 * GITHUB#16378: Accumulate join Total/Avg scores in double precision in
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java
index ce103952d50..4a551a38f3f 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/UpdateGraphsUtils.java
@@ -49,7 +49,7 @@ public class UpdateGraphsUtils {
     for (int v = 0; v < size; v++) {
       graph.seek(0, v);
       int degree = graph.neighborCount();
-      k = degree < 9 ? 2 : Math.ceilDiv(degree, 4);
+      k = coverage(degree);
       gExit += k;
       int gain = k + degree;
       heap.push(encode(gain, v));
@@ -67,7 +67,7 @@ public class UpdateGraphsUtils {
       for (int u = graph.nextNeighbor(); u != NO_MORE_DOCS; u = graph.nextNeighbor()) {
         ns[i++] = u;
       }
-      k = degree < 9 ? 2 : Math.ceilDiv(degree, 4);
+      k = coverage(degree);
       if (stale[v]) { // if stale, recalculate gain
         int newGain = Math.max(0, k - counts[v]);
         for (int u : ns) {
@@ -101,6 +101,22 @@ public class UpdateGraphsUtils {
     return j;
   }
 
+  /**
+   * How many times a node needs to be covered by the nodes of the join set before we consider it
+   * covered.
+   *
+   * <p>A node's neighbours are the only nodes that can cover it, so a node can never be covered
+   * more than {@code degree} times. Requesting a bigger coverage than that would make the coverage
+   * unsatisfiable, and the node would be forced to join the join set itself. This happens on
+   * degenerate graphs (e.g. hub-and-spoke shapes produced by highly duplicated or low dimensional
+   * vectors) where most of the nodes have a degree of 1: without clamping, every leaf ends up in
+   * the join set, and the join set degenerates to the whole graph.
+   */
+  private static int coverage(int degree) {
+    int k = degree < 9 ? 2 : Math.ceilDiv(degree, 4);
+    return Math.min(k, degree);
+  }
+
   private static long encode(int value1, int value2) {
     return (((long) -value1) << 32) | (value2 & 0xFFFFFFFFL);
   }