You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ka...@apache.org on 2026/04/03 01:56:24 UTC
(lucene) branch main updated: Adaptive HNSW graph traversal in similarity-based vector searches (#15784)
This is an automated email from the ASF dual-hosted git repository.
kaivalnp pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new be2af1e7b43 Adaptive HNSW graph traversal in similarity-based vector searches (#15784)
be2af1e7b43 is described below
commit be2af1e7b4393f41570c5611bccf565db1a3e0c2
Author: Kaival Parikh <ka...@gmail.com>
AuthorDate: Thu Apr 2 21:56:17 2026 -0400
Adaptive HNSW graph traversal in similarity-based vector searches (#15784)
Adaptive HNSW graph traversal in [Byte|Float]VectorSimilarityQuery.
The buffer for graph traversal (i.e. `resultSimilarity` - `minCompetitiveSimilarity`) is now adaptive: starts with a high value, and decays towards scores of nodes traversed but not collected (i.e. with score < `resultSimilarity`), with a provided factor.
The decay factor should lie in [0, 1]; with higher values producing better recall using more graph exploration. Earlier, this buffer was controlled by an explicit parameter (set as `resultSimilarity` - `traversalSimilarity`), which is now deprecated.
---
lucene/CHANGES.txt | 7 +
lucene/MIGRATE.md | 21 +++
.../search/AbstractVectorSimilarityQuery.java | 53 +++++---
.../lucene/search/ByteVectorSimilarityQuery.java | 34 ++---
.../lucene/search/FloatVectorSimilarityQuery.java | 34 ++---
.../lucene/search/VectorSimilarityCollector.java | 68 +++++++---
.../search/BaseVectorSimilarityQueryTestCase.java | 151 ++++++++++++---------
.../search/TestByteVectorSimilarityQuery.java | 18 +--
.../search/TestFloatVectorSimilarityQuery.java | 18 +--
.../search/TestVectorSimilarityCollector.java | 15 +-
10 files changed, 227 insertions(+), 192 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 6fa4c282674..8bd0f81720e 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -268,6 +268,13 @@ Improvements
* GITHUB#15753: Add Case Insensitive makeChar and makeString to Automata. (John Wagster)
+* GITHUB#15784: Adaptive HNSW graph traversal in [Byte|Float]VectorSimilarityQuery. The buffer for graph traversal
+ (i.e. `resultSimilarity` - `minCompetitiveSimilarity`) is now adaptive: starts with a high value, and decays towards
+ scores of nodes traversed but not collected (i.e. with score < `resultSimilarity`), with a provided factor. The decay
+ factor should lie in [0, 1]; with higher values producing better recall using more graph exploration. Earlier, this
+ buffer was controlled by an explicit parameter (set as `resultSimilarity` - `traversalSimilarity`), which is now
+ deprecated. (Kaival Parikh)
+
Optimizations
---------------------
* GITHUB#15637: Lazily allocate ByteArrayDataInputs in SegmentTermsEnumFrame#15637 (Misha Dmitriev)
diff --git a/lucene/MIGRATE.md b/lucene/MIGRATE.md
index 95b652fde9f..58dff66f68c 100644
--- a/lucene/MIGRATE.md
+++ b/lucene/MIGRATE.md
@@ -159,6 +159,27 @@ iwc.getConfig().getCodec().compoundFormat().getShouldUseCompoundFile();
iwc.getConfig().getCodec().compoundFormat().getMaxCFSSegmentSizeMB();
```
+## Migration from Lucene 10.4 to Lucene 10.5
+
+### `[Byte|Float]VectorSimilarityQuery` now performs adaptive HNSW graph traversal
+
+GITHUB#12679 added `[Byte|Float]VectorSimilarityQuery` to perform similarity-based vector searches, which match all
+(approximate) vectors above a similarity score to the query vector (specified by `resultSimilarity`). For Euclidean
+distance, this can be visualized as matching all vectors within a radius of the query vector.
+
+This query traversed and collected results from existing HNSW graphs. In Lucene 10.4, graph traversal was controlled by
+an explicit parameter (specified by `traversalSimilarity`), where all nodes scoring above this value were traversed, and
+all traversed nodes scoring above `resultSimilarity` were collected as results. To protect against adversarial cases of
+the entry node being far away from the query vector, traversal continued as long as better scoring nodes were available.
+Picking the right value for traversal could be a challenge, and search was susceptible to being stuck in a local maxima,
+terminating before reaching the vicinity of the query vector.
+
+GITHUB#15784: With Lucene 10.5, graph traversal is now adaptive: starts with a high buffer, which decays towards scores
+of nodes traversed but not collected, with a provided factor. The decay factor should lie in `[0, 1]`; with higher
+values producing better recall using more graph exploration. This gives a better recall v/s latency tradeoff than before
+in most cases, while still providing a knob for advanced users to tune quality and performance if needed (using the
+`decay` factor).
+
## Migration from Lucene 9.x to Lucene 10.0
### DataInput#readVLong() may now read negative vlongs
diff --git a/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java b/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java
index 73b43bc0e59..e1fb961b448 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java
@@ -29,15 +29,22 @@ import org.apache.lucene.search.knn.KnnSearchStrategy;
import org.apache.lucene.util.Bits;
/**
- * Search for all (approximate) vectors above a similarity threshold.
+ * Search for all (approximate) vectors above a similarity threshold using {@link
+ * VectorSimilarityCollector}.
*
* @lucene.experimental
*/
abstract class AbstractVectorSimilarityQuery extends Query {
- // TODO, switch to optionally use the new strategy
+ // TODO enable supplying KnnSearchStrategy
static final KnnSearchStrategy.Hnsw DEFAULT_STRATEGY = new KnnSearchStrategy.Hnsw(0);
+
+ static final float DECAY_MAX_APPROXIMATION = 0f;
+ static final float DEFAULT_DECAY = 0.5f;
+ static final float DECAY_MAX_QUALITY = 1f;
+
protected final String field;
- protected final float traversalSimilarity, resultSimilarity;
+ protected final float resultSimilarity;
+ protected final float decay;
protected final Query filter;
/**
@@ -46,24 +53,32 @@ abstract class AbstractVectorSimilarityQuery extends Query {
* the filter, and then falls back to exact search if results are incomplete.
*
* @param field a field that has been indexed as a vector field.
- * @param traversalSimilarity (lower) similarity score for graph traversal.
- * @param resultSimilarity (higher) similarity score for result collection.
+ * @param resultSimilarity similarity score for result collection.
+ * @param decay decay factor for graph traversal buffer.
* @param filter a filter applied before the vector search.
*/
- AbstractVectorSimilarityQuery(
- String field, float traversalSimilarity, float resultSimilarity, Query filter) {
- if (traversalSimilarity > resultSimilarity) {
- throw new IllegalArgumentException("traversalSimilarity should be <= resultSimilarity");
+ AbstractVectorSimilarityQuery(String field, float resultSimilarity, float decay, Query filter) {
+ if (Float.isNaN(resultSimilarity)) {
+ throw new IllegalArgumentException(
+ "resultSimilarity must have a valid value; got " + resultSimilarity);
+ }
+
+ if (Float.isNaN(decay)) {
+ throw new IllegalArgumentException("decay must have a valid value; got " + decay);
+ } else if (decay < DECAY_MAX_APPROXIMATION || decay > DECAY_MAX_QUALITY) {
+ throw new IllegalArgumentException(
+ "decay must lie in range [DECAY_MAX_APPROXIMATION = 0, DECAY_MAX_QUALITY = 1]; got "
+ + decay);
}
+
this.field = Objects.requireNonNull(field, "field");
- this.traversalSimilarity = traversalSimilarity;
this.resultSimilarity = resultSimilarity;
+ this.decay = decay;
this.filter = filter;
}
protected KnnCollectorManager getKnnCollectorManager() {
- return (visitLimit, _, _) ->
- new VectorSimilarityCollector(traversalSimilarity, resultSimilarity, visitLimit);
+ return (visitLimit, _, _) -> new VectorSimilarityCollector(resultSimilarity, decay, visitLimit);
}
abstract VectorScorer createVectorScorer(LeafReaderContext context) throws IOException;
@@ -122,8 +137,8 @@ abstract class AbstractVectorSimilarityQuery extends Query {
// If there is no filter
if (filterWeight == null) {
- if (traversalSimilarity == Float.NEGATIVE_INFINITY) {
- // When traversalSimilarity is -∞, the intent is to find all vectors above
+ if (decay == DECAY_MAX_QUALITY) {
+ // With DECAY_MAX_QUALITY, the intent is to find all vectors above
// resultSimilarity. The approximate graph search may miss nodes,
// so use exact search to guarantee completeness.
AcceptDocs acceptDocs = AcceptDocs.fromLiveDocs(liveDocs, leafReader.maxDoc());
@@ -158,8 +173,8 @@ abstract class AbstractVectorSimilarityQuery extends Query {
return null;
}
- if (traversalSimilarity == Float.NEGATIVE_INFINITY) {
- // When traversalSimilarity is -∞, skip approximate search and go straight
+ if (decay == DECAY_MAX_QUALITY) {
+ // With DECAY_MAX_QUALITY, skip approximate search and go straight
// to exact search over the filtered docs.
return VectorSimilarityScorerSupplier.fromAcceptDocs(
boost, createVectorScorer(context), acceptDocs.iterator(), resultSimilarity);
@@ -200,17 +215,15 @@ abstract class AbstractVectorSimilarityQuery extends Query {
public boolean equals(Object o) {
return sameClassAs(o)
&& Objects.equals(field, ((AbstractVectorSimilarityQuery) o).field)
- && Float.compare(
- ((AbstractVectorSimilarityQuery) o).traversalSimilarity, traversalSimilarity)
- == 0
&& Float.compare(((AbstractVectorSimilarityQuery) o).resultSimilarity, resultSimilarity)
== 0
+ && Float.compare(((AbstractVectorSimilarityQuery) o).decay, decay) == 0
&& Objects.equals(filter, ((AbstractVectorSimilarityQuery) o).filter);
}
@Override
public int hashCode() {
- return Objects.hash(field, traversalSimilarity, resultSimilarity, filter);
+ return Objects.hash(field, resultSimilarity, decay, filter);
}
private static class VectorSimilarityScorerSupplier extends ScorerSupplier {
diff --git a/lucene/core/src/java/org/apache/lucene/search/ByteVectorSimilarityQuery.java b/lucene/core/src/java/org/apache/lucene/search/ByteVectorSimilarityQuery.java
index 0c66d334558..eccb626c37a 100644
--- a/lucene/core/src/java/org/apache/lucene/search/ByteVectorSimilarityQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/ByteVectorSimilarityQuery.java
@@ -40,34 +40,16 @@ public class ByteVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
*
* @param field a field that has been indexed as a {@link KnnByteVectorField}.
* @param target the target of the search.
- * @param traversalSimilarity (lower) similarity score for graph traversal.
- * @param resultSimilarity (higher) similarity score for result collection.
+ * @param decay decay factor for graph traversal buffer.
+ * @param resultSimilarity similarity score for result collection.
* @param filter a filter applied before the vector search.
*/
public ByteVectorSimilarityQuery(
- String field,
- byte[] target,
- float traversalSimilarity,
- float resultSimilarity,
- Query filter) {
- super(field, traversalSimilarity, resultSimilarity, filter);
+ String field, byte[] target, float resultSimilarity, float decay, Query filter) {
+ super(field, resultSimilarity, decay, filter);
this.target = Objects.requireNonNull(target, "target");
}
- /**
- * Search for all (approximate) byte vectors above a similarity threshold using {@link
- * VectorSimilarityCollector}.
- *
- * @param field a field that has been indexed as a {@link KnnByteVectorField}.
- * @param target the target of the search.
- * @param traversalSimilarity (lower) similarity score for graph traversal.
- * @param resultSimilarity (higher) similarity score for result collection.
- */
- public ByteVectorSimilarityQuery(
- String field, byte[] target, float traversalSimilarity, float resultSimilarity) {
- this(field, target, traversalSimilarity, resultSimilarity, null);
- }
-
/**
* Search for all (approximate) byte vectors above a similarity threshold using {@link
* VectorSimilarityCollector}. If a filter is applied, it traverses as many nodes as the cost of
@@ -80,7 +62,7 @@ public class ByteVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
*/
public ByteVectorSimilarityQuery(
String field, byte[] target, float resultSimilarity, Query filter) {
- this(field, target, resultSimilarity, resultSimilarity, filter);
+ this(field, target, resultSimilarity, DEFAULT_DECAY, filter);
}
/**
@@ -92,7 +74,7 @@ public class ByteVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
* @param resultSimilarity similarity score for result collection.
*/
public ByteVectorSimilarityQuery(String field, byte[] target, float resultSimilarity) {
- this(field, target, resultSimilarity, resultSimilarity, null);
+ this(field, target, resultSimilarity, null);
}
@Override
@@ -121,12 +103,12 @@ public class ByteVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
public String toString(String field) {
return String.format(
Locale.ROOT,
- "%s[field=%s target=[%d...] traversalSimilarity=%f resultSimilarity=%f filter=%s]",
+ "%s[field=%s target=[%d...] resultSimilarity=%f decay=%f filter=%s]",
getClass().getSimpleName(),
field,
target[0],
- traversalSimilarity,
resultSimilarity,
+ decay,
filter);
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/FloatVectorSimilarityQuery.java b/lucene/core/src/java/org/apache/lucene/search/FloatVectorSimilarityQuery.java
index 6f04b76cb4e..9d6ef471fd5 100644
--- a/lucene/core/src/java/org/apache/lucene/search/FloatVectorSimilarityQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/FloatVectorSimilarityQuery.java
@@ -41,34 +41,16 @@ public class FloatVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
*
* @param field a field that has been indexed as a {@link KnnFloatVectorField}.
* @param target the target of the search.
- * @param traversalSimilarity (lower) similarity score for graph traversal.
- * @param resultSimilarity (higher) similarity score for result collection.
+ * @param resultSimilarity similarity score for result collection.
+ * @param decay decay factor for graph traversal buffer.
* @param filter a filter applied before the vector search.
*/
public FloatVectorSimilarityQuery(
- String field,
- float[] target,
- float traversalSimilarity,
- float resultSimilarity,
- Query filter) {
- super(field, traversalSimilarity, resultSimilarity, filter);
+ String field, float[] target, float resultSimilarity, float decay, Query filter) {
+ super(field, resultSimilarity, decay, filter);
this.target = VectorUtil.checkFinite(Objects.requireNonNull(target, "target"));
}
- /**
- * Search for all (approximate) float vectors above a similarity threshold using {@link
- * VectorSimilarityCollector}.
- *
- * @param field a field that has been indexed as a {@link KnnFloatVectorField}.
- * @param target the target of the search.
- * @param traversalSimilarity (lower) similarity score for graph traversal.
- * @param resultSimilarity (higher) similarity score for result collection.
- */
- public FloatVectorSimilarityQuery(
- String field, float[] target, float traversalSimilarity, float resultSimilarity) {
- this(field, target, traversalSimilarity, resultSimilarity, null);
- }
-
/**
* Search for all (approximate) float vectors above a similarity threshold using {@link
* VectorSimilarityCollector}. If a filter is applied, it traverses as many nodes as the cost of
@@ -81,7 +63,7 @@ public class FloatVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
*/
public FloatVectorSimilarityQuery(
String field, float[] target, float resultSimilarity, Query filter) {
- this(field, target, resultSimilarity, resultSimilarity, filter);
+ this(field, target, resultSimilarity, DEFAULT_DECAY, filter);
}
/**
@@ -93,7 +75,7 @@ public class FloatVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
* @param resultSimilarity similarity score for result collection.
*/
public FloatVectorSimilarityQuery(String field, float[] target, float resultSimilarity) {
- this(field, target, resultSimilarity, resultSimilarity, null);
+ this(field, target, resultSimilarity, null);
}
@Override
@@ -123,12 +105,12 @@ public class FloatVectorSimilarityQuery extends AbstractVectorSimilarityQuery {
public String toString(String field) {
return String.format(
Locale.ROOT,
- "%s[field=%s target=[%f...] traversalSimilarity=%f resultSimilarity=%f filter=%s]",
+ "%s[field=%s target=[%f...] resultSimilarity=%f decay=%f filter=%s]",
getClass().getSimpleName(),
field,
target[0],
- traversalSimilarity,
resultSimilarity,
+ decay,
filter);
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/VectorSimilarityCollector.java b/lucene/core/src/java/org/apache/lucene/search/VectorSimilarityCollector.java
index 0c0036c20e4..a511839ac1b 100644
--- a/lucene/core/src/java/org/apache/lucene/search/VectorSimilarityCollector.java
+++ b/lucene/core/src/java/org/apache/lucene/search/VectorSimilarityCollector.java
@@ -16,53 +16,83 @@
*/
package org.apache.lucene.search;
+import static org.apache.lucene.search.AbstractVectorSimilarityQuery.DECAY_MAX_APPROXIMATION;
+import static org.apache.lucene.search.AbstractVectorSimilarityQuery.DECAY_MAX_QUALITY;
+
import java.util.ArrayList;
import java.util.List;
/**
- * Perform a similarity-based graph search.
+ * Perform a similarity-based graph search to find all (approximate) vectors above a similarity
+ * threshold.
+ *
+ * <p>The buffer for graph traversal is adaptive: starts with a high value, and decays towards
+ * scores of nodes traversed but not collected, with a provided factor. The decay factor should lie
+ * in {@code [0, 1]}; with higher values producing better recall using more graph exploration.
+ *
+ * <p>Note: Some functions of this class deviate from {@link KnnCollector}, and should be used with
+ * queries that are aware of the differences (like {@link ByteVectorSimilarityQuery} and {@link
+ * FloatVectorSimilarityQuery}).
+ *
+ * <ul>
+ * <li>{@link #k()} does NOT provide a good estimate of the number of collected results.
+ * <li>{@link #topDocs()} does NOT return docs sorted in descending order of scores.
+ * <li>{@link #collect(int, float)} does NOT return true / false based on whether the document was
+ * collected.
+ * </ul>
*
* @lucene.experimental
*/
class VectorSimilarityCollector extends AbstractKnnCollector {
- private final float traversalSimilarity, resultSimilarity;
- private float maxSimilarity;
+ private final float resultSimilarity, decay;
private final List<ScoreDoc> scoreDocList;
+ private float minCompetitiveSimilarity;
/**
- * Perform a similarity-based graph search. The graph is traversed till better scoring nodes are
- * available, or the best candidate is below {@link #traversalSimilarity}. All traversed nodes
- * above {@link #resultSimilarity} are collected.
+ * Perform a similarity-based graph search.
*
- * @param traversalSimilarity (lower) similarity score for graph traversal.
- * @param resultSimilarity (higher) similarity score for result collection.
+ * @param resultSimilarity similarity score for result collection.
+ * @param decay decay factor for graph traversal buffer.
* @param visitLimit limit on number of nodes to visit.
*/
- public VectorSimilarityCollector(
- float traversalSimilarity, float resultSimilarity, long visitLimit) {
- // TODO: add search strategy support
+ public VectorSimilarityCollector(float resultSimilarity, float decay, long visitLimit) {
+ // TODO: enable supplying KnnSearchStrategy
super(1, visitLimit, AbstractVectorSimilarityQuery.DEFAULT_STRATEGY);
- if (traversalSimilarity > resultSimilarity) {
- throw new IllegalArgumentException("traversalSimilarity should be <= resultSimilarity");
- }
- this.traversalSimilarity = traversalSimilarity;
+
+ assert Float.isNaN(resultSimilarity) == false
+ : "resultSimilarity must have a valid value; got " + resultSimilarity;
+
+ assert Float.isNaN(decay) == false : "decay must have a valid value; got " + decay;
+
+ assert decay >= DECAY_MAX_APPROXIMATION && decay <= DECAY_MAX_QUALITY
+ : "decay must lie in range [DECAY_MAX_APPROXIMATION = 0, DECAY_MAX_QUALITY = 1]; got "
+ + decay;
+
this.resultSimilarity = resultSimilarity;
- this.maxSimilarity = Float.NEGATIVE_INFINITY;
+ this.decay = decay;
this.scoreDocList = new ArrayList<>();
+ this.minCompetitiveSimilarity = Math.nextUp(Float.NEGATIVE_INFINITY);
}
@Override
public boolean collect(int docId, float similarity) {
- maxSimilarity = Math.max(maxSimilarity, similarity);
+ // Returns true / false based on whether minCompetitiveSimilarity has been updated
if (similarity >= resultSimilarity) {
scoreDocList.add(new ScoreDoc(docId, similarity));
+
+ } else if (decay < DECAY_MAX_QUALITY) {
+ // decay buffer towards score of current node
+ minCompetitiveSimilarity =
+ (float) (similarity + ((double) minCompetitiveSimilarity - similarity) * decay);
+ return true;
}
- return true;
+
+ return false;
}
@Override
public float minCompetitiveSimilarity() {
- return Math.min(traversalSimilarity, maxSimilarity);
+ return minCompetitiveSimilarity;
}
@Override
diff --git a/lucene/core/src/test/org/apache/lucene/search/BaseVectorSimilarityQueryTestCase.java b/lucene/core/src/test/org/apache/lucene/search/BaseVectorSimilarityQueryTestCase.java
index 21391ee4c9b..69e0e5267e0 100644
--- a/lucene/core/src/test/org/apache/lucene/search/BaseVectorSimilarityQueryTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/search/BaseVectorSimilarityQueryTestCase.java
@@ -18,6 +18,9 @@ package org.apache.lucene.search;
import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.DEFAULT_BEAM_WIDTH;
import static org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsFormat.DEFAULT_MAX_CONN;
+import static org.apache.lucene.search.AbstractVectorSimilarityQuery.DECAY_MAX_APPROXIMATION;
+import static org.apache.lucene.search.AbstractVectorSimilarityQuery.DECAY_MAX_QUALITY;
+import static org.apache.lucene.search.AbstractVectorSimilarityQuery.DEFAULT_DECAY;
import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import static org.hamcrest.Matchers.either;
import static org.hamcrest.Matchers.greaterThan;
@@ -68,10 +71,10 @@ abstract class BaseVectorSimilarityQueryTestCase<
abstract F getVectorField(String name, V vector, VectorSimilarityFunction function);
abstract Q getVectorQuery(
- String field, V vector, float traversalSimilarity, float resultSimilarity, Query filter);
+ String field, V vector, float resultSimilarity, float decay, Query filter);
abstract Q getThrowingVectorQuery(
- String field, V vector, float traversalSimilarity, float resultSimilarity, Query filter);
+ String field, V vector, float resultSimilarity, float decay, Query filter);
public void testEquals() {
String field1 = "f1", field2 = "f2";
@@ -82,40 +85,76 @@ abstract class BaseVectorSimilarityQueryTestCase<
vector2 = getRandomVector(dim);
} while (checkEquals(vector1, vector2));
- float traversalSimilarity1 = 0.3f, traversalSimilarity2 = 0.4f;
float resultSimilarity1 = 0.4f, resultSimilarity2 = 0.5f;
+ float decay1 = 0.5f, decay2 = 0.6f;
Query filter1 = new TermQuery(new Term("t1", "v1"));
Query filter2 = new TermQuery(new Term("t2", "v2"));
- Query query = getVectorQuery(field1, vector1, traversalSimilarity1, resultSimilarity1, filter1);
+ Query query = getVectorQuery(field1, vector1, resultSimilarity1, decay1, filter1);
// Everything is equal
- assertEquals(
- query, getVectorQuery(field1, vector1, traversalSimilarity1, resultSimilarity1, filter1));
+ assertEquals(query, getVectorQuery(field1, vector1, resultSimilarity1, decay1, filter1));
// Null check
- assertNotEquals(query, null);
+ assertNotEquals(null, query);
// Different field
- assertNotEquals(
- query, getVectorQuery(field2, vector1, traversalSimilarity1, resultSimilarity1, filter1));
+ assertNotEquals(query, getVectorQuery(field2, vector1, resultSimilarity1, decay1, filter1));
// Different vector
- assertNotEquals(
- query, getVectorQuery(field1, vector2, traversalSimilarity1, resultSimilarity1, filter1));
+ assertNotEquals(query, getVectorQuery(field1, vector2, resultSimilarity1, decay1, filter1));
- // Different traversalSimilarity
- assertNotEquals(
- query, getVectorQuery(field1, vector1, traversalSimilarity2, resultSimilarity1, filter1));
+ // Different decay
+ assertNotEquals(query, getVectorQuery(field1, vector1, resultSimilarity1, decay2, filter1));
// Different resultSimilarity
- assertNotEquals(
- query, getVectorQuery(field1, vector1, traversalSimilarity1, resultSimilarity2, filter1));
+ assertNotEquals(query, getVectorQuery(field1, vector1, resultSimilarity2, decay1, filter1));
// Different filter
- assertNotEquals(
- query, getVectorQuery(field1, vector1, traversalSimilarity1, resultSimilarity1, filter2));
+ assertNotEquals(query, getVectorQuery(field1, vector1, resultSimilarity1, decay1, filter2));
+ }
+
+ public void testIllegalParams() {
+ expectThrows(
+ IllegalArgumentException.class,
+ () ->
+ getVectorQuery(
+ vectorField,
+ getRandomVector(dim),
+ Float.NaN, // illegal resultSimilarity
+ DEFAULT_DECAY,
+ null));
+
+ expectThrows(
+ IllegalArgumentException.class,
+ () ->
+ getVectorQuery(
+ vectorField,
+ getRandomVector(dim),
+ 0f,
+ Float.NaN, // illegal decay
+ null));
+
+ expectThrows(
+ IllegalArgumentException.class,
+ () ->
+ getVectorQuery(
+ vectorField,
+ getRandomVector(dim),
+ 0f,
+ Math.nextDown(DECAY_MAX_APPROXIMATION), // illegal decay
+ null));
+
+ expectThrows(
+ IllegalArgumentException.class,
+ () ->
+ getVectorQuery(
+ vectorField,
+ getRandomVector(dim),
+ 0f,
+ Math.nextUp(DECAY_MAX_QUALITY), // illegal decay
+ null));
}
public void testEmptyIndex() throws IOException {
@@ -128,11 +167,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
Query query =
getVectorQuery(
- vectorField,
- getRandomVector(dim),
- Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
- null);
+ vectorField, getRandomVector(dim), Float.NEGATIVE_INFINITY, DECAY_MAX_QUALITY, null);
// Check that no vectors are found
assertEquals(0, searcher.count(query));
@@ -148,11 +183,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
// All vectors are above -Infinity
Query query1 =
getVectorQuery(
- vectorField,
- getRandomVector(dim),
- Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
- null);
+ vectorField, getRandomVector(dim), Float.NEGATIVE_INFINITY, DECAY_MAX_QUALITY, null);
// Check that all vectors are found
assertEquals(numDocs, searcher.count(query1));
@@ -160,11 +191,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
// No vectors are above +Infinity
Query query2 =
getVectorQuery(
- vectorField,
- getRandomVector(dim),
- Float.POSITIVE_INFINITY,
- Float.POSITIVE_INFINITY,
- null);
+ vectorField, getRandomVector(dim), Float.POSITIVE_INFINITY, DECAY_MAX_QUALITY, null);
// Check that no vectors are found
assertEquals(0, searcher.count(query2));
@@ -187,7 +214,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
vectorField,
getRandomVector(dim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
filter);
ScoreDoc[] scoreDocs = searcher.search(query, numDocs).scoreDocs;
@@ -214,7 +241,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
vectorField,
getRandomVector(dim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
filter1);
// Check that no vectors are found
@@ -227,7 +254,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
vectorField,
getRandomVector(dim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
filter2);
// Check that no vectors are found
@@ -248,7 +275,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
vectorField,
getRandomVector(newDim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
null);
// Check that an exception for differing dimensions is thrown
@@ -275,18 +302,14 @@ abstract class BaseVectorSimilarityQueryTestCase<
"random_field",
getRandomVector(dim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
null);
assertEquals(0, searcher.count(query1));
// Indexed as int field
Query query2 =
getVectorQuery(
- idField,
- getRandomVector(dim),
- Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
- null);
+ idField, getRandomVector(dim), Float.NEGATIVE_INFINITY, DECAY_MAX_QUALITY, null);
assertEquals(0, searcher.count(query2));
}
}
@@ -312,7 +335,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
vectorField,
getRandomVector(dim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
null);
ScoreDoc[] scoreDocs = searcher.search(query, numDocs).scoreDocs;
@@ -343,7 +366,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
vectorField,
getRandomVector(dim),
Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
+ DECAY_MAX_QUALITY,
null);
// Check that no vectors are found
@@ -363,11 +386,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
Query query1 =
getVectorQuery(
- vectorField,
- getRandomVector(dim),
- Float.NEGATIVE_INFINITY,
- Float.NEGATIVE_INFINITY,
- null);
+ vectorField, getRandomVector(dim), Float.NEGATIVE_INFINITY, DECAY_MAX_QUALITY, null);
ScoreDoc[] scoreDocs1 = searcher.search(query1, numDocs).scoreDocs;
Query query2 = new BoostQuery(query1, boost);
@@ -417,7 +436,7 @@ abstract class BaseVectorSimilarityQueryTestCase<
IndexSearcher searcher = newSearcher(reader);
Query query =
- getVectorQuery(vectorField, queryVector, Float.NEGATIVE_INFINITY, resultSimilarity, null);
+ getVectorQuery(vectorField, queryVector, resultSimilarity, DECAY_MAX_QUALITY, null);
ScoreDoc[] scoreDocs = searcher.search(query, numDocs).scoreDocs;
for (ScoreDoc scoreDoc : scoreDocs) {
@@ -452,22 +471,24 @@ abstract class BaseVectorSimilarityQueryTestCase<
Query query =
getThrowingVectorQuery(
- vectorField, queryVector, resultSimilarity, resultSimilarity, filter);
+ vectorField, queryVector, resultSimilarity, DECAY_MAX_APPROXIMATION, filter);
- // Falls back to exact search
+ // Falls back to exact search, even with DECAY_MAX_APPROXIMATION
expectThrows(UnsupportedOperationException.class, () -> searcher.count(query));
- // When traversalSimilarity is -∞ without a filter, exact search should be used directly
Query exactQuery =
getThrowingVectorQuery(
- vectorField, queryVector, Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY, null);
+ vectorField, queryVector, Float.NEGATIVE_INFINITY, DECAY_MAX_QUALITY, null);
- // Falls back to exact search because traversalSimilarity is -∞
+ // Exact search should be used directly with DECAY_MAX_QUALITY
expectThrows(UnsupportedOperationException.class, () -> searcher.count(exactQuery));
}
}
+ @Monster("indexes and searches a large number of vectors")
public void testApproximate() throws IOException {
+ numDocs = 1000;
+
// Non-restrictive filter, along with similarity to visit a small number of nodes
int numFiltered = numDocs - 1;
int targetVisited = random().nextInt(1, numFiltered / 10);
@@ -495,9 +516,10 @@ abstract class BaseVectorSimilarityQueryTestCase<
try (IndexReader reader = DirectoryReader.open(indexStore)) {
IndexSearcher searcher = newSearcher(reader);
+ // Use DECAY_MAX_APPROXIMATION to avoid fallback to exact search
Query query =
getThrowingVectorQuery(
- vectorField, queryVector, resultSimilarity, resultSimilarity, filter);
+ vectorField, queryVector, resultSimilarity, DECAY_MAX_APPROXIMATION, filter);
// Does not fall back to exact search
assertTrue(searcher.count(query) <= numFiltered);
@@ -518,13 +540,15 @@ abstract class BaseVectorSimilarityQueryTestCase<
// This query is cacheable, explicitly prevent it
searcher.setQueryCache(null);
- // Use Math.nextUp(Float.NEGATIVE_INFINITY) to ensure approximate graph search is used,
- // since Float.NEGATIVE_INFINITY now triggers exact search which bypasses graph traversal
- float nearNegInf = Math.nextUp(Float.NEGATIVE_INFINITY);
+ // Use Math.nextDown(DECAY_MAX_QUALITY) to ensure approximate graph search is used,
+ // since DECAY_MAX_QUALITY now triggers exact search which bypasses graph traversal
+ float highQualityNoExact = Math.nextDown(DECAY_MAX_QUALITY);
Query query =
- new CountingQuery(getVectorQuery(vectorField, queryVector, nearNegInf, nearNegInf, null));
- assertEquals(numDocs, searcher.count(query)); // Expect all results without timeout
+ new CountingQuery(
+ getVectorQuery(
+ vectorField, queryVector, Float.NEGATIVE_INFINITY, highQualityNoExact, null));
+ assertEquals(numDocs, searcher.count(query)); // Expect some results without timeout
searcher.setTimeout(() -> true); // Immediately timeout
assertEquals(0, searcher.count(query)); // Expect no results with the timeout
@@ -540,7 +564,8 @@ abstract class BaseVectorSimilarityQueryTestCase<
Query filter = IntField.newSetQuery(idField, getFiltered(numFiltered));
Query filteredQuery =
new CountingQuery(
- getVectorQuery(vectorField, queryVector, nearNegInf, nearNegInf, filter));
+ getVectorQuery(
+ vectorField, queryVector, Float.NEGATIVE_INFINITY, highQualityNoExact, filter));
searcher.setTimeout(() -> false); // Set a timeout which is never met
assertEquals(numFiltered, searcher.count(filteredQuery));
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestByteVectorSimilarityQuery.java b/lucene/core/src/test/org/apache/lucene/search/TestByteVectorSimilarityQuery.java
index 07f9e8a86e9..1612c495ea7 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestByteVectorSimilarityQuery.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestByteVectorSimilarityQuery.java
@@ -58,24 +58,14 @@ public class TestByteVectorSimilarityQuery
@Override
ByteVectorSimilarityQuery getVectorQuery(
- String field,
- byte[] vector,
- float traversalSimilarity,
- float resultSimilarity,
- Query filter) {
- return new ByteVectorSimilarityQuery(
- field, vector, traversalSimilarity, resultSimilarity, filter);
+ String field, byte[] vector, float resultSimilarity, float decay, Query filter) {
+ return new ByteVectorSimilarityQuery(field, vector, resultSimilarity, decay, filter);
}
@Override
ByteVectorSimilarityQuery getThrowingVectorQuery(
- String field,
- byte[] vector,
- float traversalSimilarity,
- float resultSimilarity,
- Query filter) {
- return new ByteVectorSimilarityQuery(
- field, vector, traversalSimilarity, resultSimilarity, filter) {
+ String field, byte[] vector, float resultSimilarity, float decay, Query filter) {
+ return new ByteVectorSimilarityQuery(field, vector, resultSimilarity, decay, filter) {
@Override
VectorScorer createVectorScorer(LeafReaderContext context) {
throw new UnsupportedOperationException();
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestFloatVectorSimilarityQuery.java b/lucene/core/src/test/org/apache/lucene/search/TestFloatVectorSimilarityQuery.java
index 479d4ef0df1..d99fcad1aca 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestFloatVectorSimilarityQuery.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestFloatVectorSimilarityQuery.java
@@ -59,24 +59,14 @@ public class TestFloatVectorSimilarityQuery
@Override
FloatVectorSimilarityQuery getVectorQuery(
- String field,
- float[] vector,
- float traversalSimilarity,
- float resultSimilarity,
- Query filter) {
- return new FloatVectorSimilarityQuery(
- field, vector, traversalSimilarity, resultSimilarity, filter);
+ String field, float[] vector, float resultSimilarity, float decay, Query filter) {
+ return new FloatVectorSimilarityQuery(field, vector, resultSimilarity, decay, filter);
}
@Override
FloatVectorSimilarityQuery getThrowingVectorQuery(
- String field,
- float[] vector,
- float traversalSimilarity,
- float resultSimilarity,
- Query filter) {
- return new FloatVectorSimilarityQuery(
- field, vector, traversalSimilarity, resultSimilarity, filter) {
+ String field, float[] vector, float resultSimilarity, float decay, Query filter) {
+ return new FloatVectorSimilarityQuery(field, vector, resultSimilarity, decay, filter) {
@Override
VectorScorer createVectorScorer(LeafReaderContext context) {
throw new UnsupportedOperationException();
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestVectorSimilarityCollector.java b/lucene/core/src/test/org/apache/lucene/search/TestVectorSimilarityCollector.java
index b0a80803d68..fa689ff332d 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestVectorSimilarityCollector.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestVectorSimilarityCollector.java
@@ -16,21 +16,22 @@
*/
package org.apache.lucene.search;
+import static org.apache.lucene.search.AbstractVectorSimilarityQuery.DEFAULT_DECAY;
+
import org.apache.lucene.tests.util.LuceneTestCase;
public class TestVectorSimilarityCollector extends LuceneTestCase {
public void testResultCollection() {
- float traversalSimilarity = 0.3f, resultSimilarity = 0.5f;
+ float resultSimilarity = 0.5f;
VectorSimilarityCollector collector =
- new VectorSimilarityCollector(traversalSimilarity, resultSimilarity, Integer.MAX_VALUE);
+ new VectorSimilarityCollector(resultSimilarity, DEFAULT_DECAY, Integer.MAX_VALUE);
+
int[] nodes = {1, 5, 10, 4, 8, 3, 2, 6, 7, 9};
float[] scores = {0.1f, 0.2f, 0.3f, 0.5f, 0.2f, 0.6f, 0.9f, 0.3f, 0.7f, 0.8f};
- float[] minCompetitiveSimilarities = new float[nodes.length];
for (int i = 0; i < nodes.length; i++) {
collector.collect(nodes[i], scores[i]);
- minCompetitiveSimilarities[i] = collector.minCompetitiveSimilarity();
}
ScoreDoc[] scoreDocs = collector.topDocs().scoreDocs;
@@ -44,11 +45,5 @@ public class TestVectorSimilarityCollector extends LuceneTestCase {
// All nodes above resultSimilarity appear in order of collection
assertArrayEquals(new int[] {4, 3, 2, 7, 9}, resultNodes);
assertArrayEquals(new float[] {0.5f, 0.6f, 0.9f, 0.7f, 0.8f}, resultScores, 1e-3f);
-
- // Min competitive similarity is minimum of traversalSimilarity or best result encountered
- assertArrayEquals(
- new float[] {0.1f, 0.2f, 0.3f, 0.3f, 0.3f, 0.3f, 0.3f, 0.3f, 0.3f, 0.3f},
- minCompetitiveSimilarities,
- 1e-3f);
}
}