Similarity-threshold vector queries with traversalSimilarity == resultSimilarity skip documents that score exactly the threshold

A similarity-threshold vector query (FloatVectorSimilarityQuery, ByteVectorSimilarityQuery) returns every document whose similarity to the target is at least resultSimilarity; traversalSimilarity controls how far the search explores. The constructors without a traversal argument, (field, target, resultSimilarity[, filter]), set the two equal: the plain constructors in 9.10.0-10.4.0, the deprecated Explicit classes in 10.5.2 and main (the full forms behave the same when given equal values). Then, once the collector has seen a hit at exactly the threshold t, its minCompetitiveSimilarity() = min(traversalSimilarity, maxSimilarity) equals t, and every consumer treats a score equal to that bound as not competitive: the exhaustive scan of a segment without a graph collects a 64-vector batch only if its best score is > the bound, and the HNSW graph search accepts only scores >= nextUp(bound). So later documents at exactly t can be silently dropped (without a graph, those in a later batch that holds no better score; on a graph, those met after the first hit), although the query's own collect(), explain() and exact fallback all count them. On 65 vectors with exact copies of the target at docs 0 and 64 (EUCLIDEAN, t = 1.0) the query returns [0]; on a 3,000-vector HNSW segment with 6 copies, 1 of 6; with traversal one ulp lower, all of them. It needs an exact score tie, which is routine for exact-duplicate lookups, byte vectors and thresholds copied from a document's score. The fix is one line: Math.min(Math.nextDown(traversalSimilarity), maxSimilarity).

• Similarity-threshold query: FloatVectorSimilarityQuery / ByteVectorSimilarityQuery (@lucene.experimental, "Search for all (approximate) float vectors above a similarity threshold"). resultSimilarity is the score a document must reach to be returned; traversalSimilarity (<= resultSimilarity) controls how far the HNSW graph is explored. The constructors without a traversal argument, (field, target, resultSimilarity[, filter]), pass resultSimilarity for both; the full forms (field, target, traversalSimilarity, resultSimilarity[, filter]) take both values. On 10.5.2 and main these are the deprecated Explicit classes ("Equivalent to the FloatVectorSimilarityQuery constructors in Lucene 10.4 and earlier"), next to the Adaptive classes, which are not affected. In 10.5.0 and 10.5.1 the plain constructors are adaptive (#15784); the nested Adaptive and Explicit classes first appear in 10.5.2 (#16654/#16671).
• EUCLIDEAN similarity: 1 / (1 + squared distance), so 1.0 means "identical to the target" and nothing scores higher.
• minCompetitiveSimilarity(): the KnnCollector method that the vector readers and the HNSW searcher ask for the score below which candidates are not worth visiting. Its javadoc says only "When full, the minimum score should be returned"; every consumer treats a score equal to it as not competitive, which is right for top-k collectors.

1. The short constructors set traversalSimilarity = resultSimilarity = t (FloatVectorSimilarityQuery.java:182-183, :194-195; ByteVectorSimilarityQuery.java:181-182, :193-194). Only traversal > result is rejected.
2. ExplicitVectorSimilarityCollector.collect() keeps similarity >= resultSimilarity (:59) and tracks the best score seen (:58); minCompetitiveSimilarity() returns Math.min(traversalSimilarity, maxSimilarity) (:66-67). After the first hit at exactly t, that is t.
3. Segments without a graph (with the default format, fewer than 648 vectors; from 10.4.0): Lucene99HnswVectorsReader scores vectors in batches of 64 and collects a batch only if bulkScore(...) > minCompetitiveSimilarity() (:396, :408). A later batch whose best score is exactly t is skipped. Ties inside a collected batch are kept, so on this path it takes at least 65 vectors (a segment with a graph can lose a tie with a few vectors: 3 in a run with a forced graph). The scalar-quantized reader has the same gate (Lucene104ScalarQuantizedVectorsReader.java:390, :402).
4. Segments with a graph (every affected release): HnswGraphSearcher accepts a neighbour only if score >= Math.nextUp(minCompetitiveSimilarity()) (:304, :347, :352) and skips a scored batch unless its best is > the bound (:341-343). Every node at exactly t met after the first hit is neither collected nor explored. A filter does not change this: the query pins KnnSearchStrategy.Hnsw(0) (AbstractVectorSimilarityQuery.java:48), so FilteredHnswGraphSearcher is never chosen (HnswGraphSearcher.java:139-145, KnnSearchStrategy.java:80-82) and the same searcher runs with acceptOrds.
5. The query's other paths count the dropped document: explain() says "Score above threshold" for score >= resultSimilarity (AbstractVectorSimilarityQuery.java:175-176), and the exact fallback keeps score >= threshold (:363).

Main ea57360912ed, default codec, one segment, traversal == result == t.

• Who is exposed. Code that builds a similarity-threshold query with traversalSimilarity equal to resultSimilarity: the plain constructors without a traversal argument in 9.10.0-10.4.0 (the short, non-deprecated forms (field, target, resultSimilarity[, filter])), [Float|Byte]VectorSimilarityQuery.Explicit with those arguments in 10.5.2 and main (deprecated), or a full form (field, target, traversalSimilarity, resultSimilarity[, filter]) with equal values. Not 10.5.0 or 10.5.1 (adaptive collector, no Explicit), not the Adaptive queries, not Float16VectorSimilarityQuery, and not any call with traversal strictly below result.
• What it takes. A document scoring exactly the threshold after another vector at or above it was collected in the same segment (without a graph, only in a later 64-vector batch that holds no better score). Exact-duplicate lookup at EUCLIDEAN 1.0 always qualifies (nothing scores above 1.0, so every further copy is a tie); byte vectors give many equal scores; so does a threshold copied from a known document's score. For float embeddings with an arbitrary threshold an exact tie is very unlikely.
• How much is lost. On a segment with a graph, every tie met after the first hit: 1 of 6 and 1 of 12 copies in the runs. On a segment without a graph (fewer than 648 vectors with the default format, from 10.4.0), a tie in a later 64-vector batch that holds no better vector. Rarely an above-threshold document reachable only through tied graph nodes goes too: in a 120-query check, 11 of 6,699 missing documents were above the threshold, and the fix recovered all 11 (attributed to tied nodes, inferred).
• Silent and inconsistent. No error; count() matches the short hit list, while explain() says the missing documents match. The answer changes with document order, with an all-matching filter (no-graph segments in which every document has a vector, 10.4.0 on) and with a one-ulp change of traversalSimilarity. As a MUST_NOT clause, a tied document is not excluded (64 hits instead of 63).
• Settings and size. Default codec, directory and IndexSearcher. From 10.4.0 a segment needs at least 65 vectors: below 648 it has no graph and is scanned in 64-vector batches, and ties in the first collected batch are kept. Smaller segments are hit only when they have a graph: with a format whose tiny-segment threshold is 0 (executed with 3 vectors), or on 9.10.0-10.3.2, which had no tiny-segment threshold (read; not run below 65 vectors). The scalar-quantized formats have the same gate; a random hunt hit them, but no dedicated test targets them.
• Downstream. Solr's vector-similarity parser defaults minTraverse to -Infinity (not affected), but a request may set minTraverse equal to minReturn, and an open Solr issue (SOLR-17713) shows a user doing that. The OpenSearch k-NN plugin uses the Adaptive query or 0.95 x threshold (not affected); no Elasticsearch use was found.
• How likely. Rare: it needs both the equal-thresholds setting and an exact tie, and no public report was found in the two and a half years since 9.10.0 (released 2024-02-20).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[0, 64]> but was:<[0]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.TestExplicitSimilarityThresholdTie.testFloatExactDuplicates(TestExplicitSimilarityThresholdTie.java:54)

• Contract text. Collector javadoc (ExplicitVectorSimilarityCollector.java:35-37): "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." A tie is not "below". collect() (:59) uses >=; explain() (AbstractVectorSimilarityQuery.java:175-176) returns "Score above threshold" for score >= resultSimilarity; the exact fallback (:363) uses score >= threshold.
• Release notes. The 9.10.0 CHANGES entry for #12679: "find all vectors scoring above a resultSimilarity while traversing the HNSW graph till better-scoring nodes are available, or the best candidate is below a score of traversalSimilarity in the lowest level."
• Upstream tests. TestVectorSimilarityCollector.testExplicitResultCollection (:53-85) expects node 4 (score 0.5) at resultSimilarity 0.5 under "All nodes above resultSimilarity appear in order of collection" (:76-78). BaseExplicitVectorSimilarityQueryTestCase.testVectorsAboveSimilarity builds the expected set with score >= resultSimilarity (:404) and asserts all are returned (:427-428), but with traversal = -Infinity (:414), which hides the tie. Three upstream tests do run traversal == result (testFallbackToExact and testApproximate at the exact score of an indexed document, testExtremes at -Infinity and +Infinity), but none checks that tied documents are returned: testFallbackToExact asserts only the fallback to exact search (:452), testApproximate only an upper bound (:489).
• The PR's own definition. In #12679 the author describes the baseline as "any vector with a score >= resultSimilarity".
• History. #12770 (merged 2023-11-07, 9.9.0) made the graph searcher's neighbour test strict because the search over-explored the graph on equal scores (its commit message names lower dimensionality and quantization); for top-k an equal score does not raise the cutoff. #12679 was in review then; the traversal = result default was proposed on 2023-11-30, and the PR merged on 2023-12-11 without adapting the collector. #14215 (10.2.0) kept the strict form; in its review jimczi noted that this contract "does place the responsibility on the various implementers". #15021 (10.4.0) added the exhaustive batch gate, and #16654 (10.5.2) restored the 10.4 collector's body, renamed and deprecated, behind Explicit.
• Counterfactuals. On 9.10.0, the pre-#12770 >= in the graph searcher makes the repro pass; on 10.4.0, an inclusive batch gate makes it pass; on main, the one-line collector fix makes it pass.

The strongest "works as designed" case (built on purpose by a devil's-advocate verifier and by a cross-model refute review, which rated it strong): (1) the queries are documented as "(approximate)" and @lucene.experimental, and no upstream traversal == result test checks that tied documents are returned (testApproximate asserts an upper bound); (2) the strict tie rule in the searchers is deliberate (#12770, #14215), and TestFilteredHnswGraphSearcher.testAllTiedScoresBoundedVisitation bounds equal-score exploration on purpose; (3) completeness is promised only for traversal = -Infinity: #15836 (10.5.0) made that case exact "to guarantee completeness"; (4) "above" can be read as strictly above, and testExplicitResultCollection pins the bound to min(traversal, best); (5) Explicit is a deprecated shim that #16654 proposed to remove.

Why it fails: (1, 3) approximation and #15836 cover documents the search never reaches (#15836 fixed a disconnected graph, where the missed document scored 0.1033 against 0.0979, not a tie); here the tie is reached: on a segment without a graph it is scored and then thrown away at a batch boundary, and on a graph a traversal one ulp lower finds every copy on the same graph; (2) the strict rule and the bounded tie test serve top-k collectors, which still pass with the fix, while this collector defines its results with >=; (4) collect(), explain(), the exact fallback and the upstream unit test all mean >=, the pinned bound uses delta 1e-3 with traversal 0.3 below result 0.5, and under either reading one document at exactly 1.0 is returned and another is not, depending only on document order; (5) deprecation is a won't-fix risk, not intent: 9.10.0-10.4.0 hit it through the primary constructors, and Explicit still ships on main and branch_10_6. Verdict: a defect. The devil's advocate rated the intended argument weak, cross-model reviews moderate, the refute review strong (it could not run code); the reproducer and the adjudication say real. The cross-model fact check of the brief rated the case moderate for the no-graph path and strong for the graph path, where the query is approximate and equal-score exploration was bounded on purpose, so expect maintainers to weigh the graph case that way.

The cause is one inclusive threshold handed to exclusive gates, and the gates are right for top-k collectors, so the fix belongs in the collector. Option A was built and validated in a scratch worktree at ea57360912ed (removed afterwards); the others were not built. Option A is this doc's recommendation: it also covers the full constructors, but whether equality should include ties is the maintainers' call, and its cost on tie-heavy data was not benchmarked. Users can work around it today with a full constructor (field, target, traversalSimilarity, resultSimilarity[, filter]) and traversalSimilarity = Math.nextDown(resultSimilarity), or with the Adaptive query on 10.5.2 and later (in 10.5.0 and 10.5.1 the plain constructors are already adaptive).

In ExplicitVectorSimilarityCollector (and VectorSimilarityCollector in 9.10.0-10.4.0: 10.4.0 :65, 9.10.0 :64), return Math.min(Math.nextDown(traversalSimilarity), maxSimilarity). The bound is then below resultSimilarity, so any batch holding a score >= resultSimilarity passes the exhaustive gate, and the graph searcher's acceptance bound nextUp(bound) is at most traversalSimilarity (for finite thresholds; with traversalSimilarity -Infinity nothing changes, and the fix does not change how a NaN traversalSimilarity, which the constructor check lets through, is handled).

@Override
public float minCompetitiveSimilarity() {
  // Searchers treat a score equal to minCompetitiveSimilarity() as not competitive, but a score
  // equal to traversalSimilarity must still be traversed (and, when traversalSimilarity ==
  // resultSimilarity, collected).
  return Math.min(Math.nextDown(traversalSimilarity), maxSimilarity);
}

Trade-offs

• Extra work. With many exact ties at the threshold the graph search now explores all of them; they are all results, so the work is proportional to the output. With traversal < result, nodes scoring exactly traversalSimilarity are now explored, as the javadoc ("below traversalSimilarity") describes. The worst case is a large plateau of equal scores at a traversalSimilarity below resultSimilarity: the graph search now explores it in full and returns none of it. No benchmark was run, and the upstream bounded-tie test uses a top-k collector, so it does not cover this collector.
• Scope. The strict gates in the readers and searchers, and every top-k collector, are unchanged. The upstream testExplicitResultCollection pins minCompetitiveSimilarity with delta 1e-3 and still passes.
• Backports. Not run on releases before main; the same line exists in 9.10.0-10.4.0 under the old class name.

What the checks validated

• Stock: the 3 tests fail 3 of 3 through gradle, assertions on and off, seeds DEADBEEF and 5EED1234.
• Patched, assertions on and off: the 7 closest classes (the repro, TestExplicitFloatVectorSimilarityQuery, TestExplicitByteVectorSimilarityQuery, TestVectorSimilarityCollector, TestFloatVectorSimilarityQuery, TestByteVectorSimilarityQuery, TestFloat16VectorSimilarityQuery): 90 tests, 0 failures, 3 skipped.
• Patched: org.apache.lucene.search.*Vector*, *Knn*, org.apache.lucene.util.hnsw.*, codecs.lucene99.*, codecs.lucene104.*: 891 tests, 0 failures, 23 skipped.
• ecjLint, forbiddenApis (main and test) and checkGoogleJavaFormat on core pass.
• Earlier runs: the finder's, the independent reproducer's and the root-cause verifier's tests pass with the fix; 140 and 201 upstream similarity-query and collector tests pass; the random hunt's 473 failures drop to 0.

Same effect for the constructors without a traversal argument; this is exactly the one-ulp control that was run.

Trade-offs

Leaves the full 4- and 5-argument constructors (field, target, traversalSimilarity, resultSimilarity[, filter]) broken when they are given equal values, and changes toString() and equals() of the short forms. Not built.

Run only as a counterfactual: on 9.10.0 (graph searcher) and 10.4.0 (exhaustive gate) it makes the repro pass.

Trade-offs

Not recommended: it undoes the deliberate top-k optimisation of #12770 and #14215 for every collector, and would be needed in each reader and searcher, including the scalar-quantized reader.

State that a score equal to the returned value is treated as not competitive, as raised in the #14215 review.

Trade-offs

Documentation only; it prevents the next collector from repeating the mistake but fixes nothing by itself.

As #16654 proposes.

Trade-offs

Fixes main eventually, not 10.5.2, branch_10_6 or the 9.10.0-10.4.0 releases. Open PR #16811 rewrites the exhaustive path with a per-vector scores[j] > minScore check that, by code reading only, would widen the drop; A should land first or with it.

Method: code reading, then random differential (metamorphic) testing (the registry's non-formal tier; the finder tagged it semi-formal). A hunt unit built a harness of random small indexes (0-300 documents, 1-4 segments, deletions, small-integer vectors so every similarity is computed exactly, several vector formats) and checked every kNN and similarity query against an exact brute-force reference.

• Reading the exhaustive-scan gate bulkScore(...) > minCompetitiveSimilarity() next to the collector's >=, the finder wrote a public-API probe: Explicit(field, target, 1.0f) returned [0], the same query with a MatchAllDocsQuery filter [0, 64].
• The random hunt's relation "similarity query == documents with exact score >= t" then failed 473 times in 55,970 traversal == result checks over 1,496 indexes (default codec and both scalar-quantized formats), with 0 failures for traversal -Infinity, traversal t - 0.25 and the Adaptive query, 0 when no segment exceeded 60 vectors, and 0 with the fix.
• The finder minimised it to the 65-vector JUnit; an independent reproducer, a root-cause verifier, a devil's advocate and an adjudication followed (see the checks).