(lucene) branch branch_10x updated: Bugfix/fix hnsw search termination check (#14215)

[be...@apache.org]

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

benwtrent 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 430411a833b Bugfix/fix hnsw search termination check (#14215)
430411a833b is described below

commit 430411a833bb65620ce08f342af9b4d9835531c4
Author: Benjamin Trent <be...@gmail.com>
AuthorDate: Tue Feb 11 14:05:26 2025 -0500

    Bugfix/fix hnsw search termination check (#14215)
    
    previously related PR: https://github.com/apache/lucene/pull/12770
    
    While my original change to help move us towards a saner HNSW search behavior, it is will still actually explore a candidate if its score is `==` min accepted. This will devolve in the degenerate case where all vectors are the same.
    
    This change adjusts minimum required candidate score to match `Math.nextUp`, similar to TopScoreDocCollector
    related to (but doesn't fully solve): https://github.com/apache/lucene/issues/14214
---
 lucene/CHANGES.txt                                 |  2 ++
 .../apache/lucene/util/hnsw/HnswGraphSearcher.java |  4 ++--
 .../apache/lucene/document/TestManyKnnDocs.java    | 24 +++++++++++++++++++++-
 3 files changed, 27 insertions(+), 3 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index dd3dbac10fb..8ddf8b6e6a9 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -82,6 +82,8 @@ Bug Fixes
 * GITHUB#14126: Avoid overflow in index input slices invariant checks
   (Chris Hegarty)
 
+* GITHUB#14215: Fix degenerate case in HNSW where all vectors have the same score. (Ben Trent)
+
 Other
 ---------------------
 
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java
index a414bb9dfe0..9278c252541 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java
@@ -212,7 +212,7 @@ public class HnswGraphSearcher extends AbstractHnswGraphSearcher {
 
     // A bound that holds the minimum similarity to the query vector that a candidate vector must
     // have to be considered.
-    float minAcceptedSimilarity = results.minCompetitiveSimilarity();
+    float minAcceptedSimilarity = Math.nextUp(results.minCompetitiveSimilarity());
     while (candidates.size() > 0 && results.earlyTerminated() == false) {
       // get the best candidate (closest or best scoring)
       float topCandidateSimilarity = candidates.topScore();
@@ -238,7 +238,7 @@ public class HnswGraphSearcher extends AbstractHnswGraphSearcher {
           candidates.add(friendOrd, friendSimilarity);
           if (acceptOrds == null || acceptOrds.get(friendOrd)) {
             if (results.collect(friendOrd, friendSimilarity)) {
-              minAcceptedSimilarity = results.minCompetitiveSimilarity();
+              minAcceptedSimilarity = Math.nextUp(results.minCompetitiveSimilarity());
             }
           }
         }
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestManyKnnDocs.java b/lucene/core/src/test/org/apache/lucene/document/TestManyKnnDocs.java
index 2023ee73391..9130a2bf311 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestManyKnnDocs.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestManyKnnDocs.java
@@ -16,7 +16,11 @@
  */
 package org.apache.lucene.document;
 
+import static org.apache.lucene.index.VectorSimilarityFunction.DOT_PRODUCT;
+
 import com.carrotsearch.randomizedtesting.annotations.TimeoutSuite;
+import java.io.IOException;
+import java.util.Arrays;
 import org.apache.lucene.index.DirectoryReader;
 import org.apache.lucene.index.IndexWriter;
 import org.apache.lucene.index.IndexWriterConfig;
@@ -36,6 +40,24 @@ import org.apache.lucene.tests.util.LuceneTestCase.Monster;
 public class TestManyKnnDocs extends LuceneTestCase {
   // gradlew -p lucene/core test --tests TestManyKnnDocs -Ptests.heapsize=16g -Dtests.monster=true
 
+  public void testSameVectorIndexedMultipleTimes() throws IOException {
+    try (Directory d = newDirectory()) {
+      float[] vector = new float[16];
+      Arrays.fill(vector, 0.5f);
+      try (IndexWriter w = new IndexWriter(d, new IndexWriterConfig())) {
+        for (int j = 1; j <= 100_000; j++) {
+          Document doc = new Document();
+          doc.add(new KnnFloatVectorField("field", vector, DOT_PRODUCT));
+          w.addDocument(doc);
+          if (j % 1000 == 0) {
+            w.flush();
+          }
+        }
+        w.commit();
+      }
+    }
+  }
+
   public void testLargeSegment() throws Exception {
     IndexWriterConfig iwc = new IndexWriterConfig();
     iwc.setCodec(
@@ -47,7 +69,7 @@ public class TestManyKnnDocs extends LuceneTestCase {
     mp.setSegmentsPerTier(256); // only merge once at the end when we ask
     iwc.setMergePolicy(mp);
     String fieldName = "field";
-    VectorSimilarityFunction similarityFunction = VectorSimilarityFunction.DOT_PRODUCT;
+    VectorSimilarityFunction similarityFunction = DOT_PRODUCT;
 
     try (Directory dir = FSDirectory.open(createTempDir("ManyKnnVectorDocs"));
         IndexWriter iw = new IndexWriter(dir, iwc)) {