SeededKnnVectorQuery: a caller-built seed Weight whose hits lack a vector makes search throw

SeededKnnVectorQuery starts the HNSW search from the documents a seed query matches. Since 10.3.0 its constructors SeededKnnVectorQuery(KnnFloatVectorQuery|KnnByteVectorQuery, Query, Weight) are public and take the seed Weight from the caller. The factories pass null, and rewrite then builds the Weight with seed MUST + FieldExistsQuery(field) FILTER; a caller's Weight is kept as given, so its hits can include documents without a vector. The code that maps seed documents to graph ordinals (MappedDISI) assumes they all have one: it calls advance on the vector iterator with a target at or before its current document, which DocIdSetIterator leaves undefined, and the entry-point count includes seeds that map to no vector. In the repro (2,000 documents, a vector on the even ones, seed hits on docs 1997 and 1998) IndexSearcher.search throws IllegalArgumentException, with assertions on and off, where fromFloatQuery with the same seed returns 2 hits. On a DENSE block the failure is an EOFException: read past EOF.

1. The filter is skipped. rewrite returns super.rewrite when the seed Weight is non-null (search/SeededKnnVectorQuery.java:119-123). Only for a null Weight does it call the package-private createSeedWeight (:136-146), which builds seed MUST + FieldExistsQuery(field) FILTER (+ the kNN filter as a FILTER).
2. Seed hits are collected and counted. Per leaf, SeededCollectorManager.newCollector scores the seed Weight into a top-k collector (:315-335; k = 2, hits 1997 and 1998), wraps the field's vector iterator (an IndexedDISI for a sparse field) and the sorted seed docs in MappedDISI, and passes seedTopDocs.scoreDocs.length (2) as the number of entry points (:341-353).
3. The mapping advances in place. MappedDISI.nextDoc (:254-260) and advance (:231-237) call indexedDISI.advance(newTarget) for every seed doc, with no check that newTarget > indexedDISI.docID(). Seed 1997 moves the vector iterator to doc 1998 (ordinal 999); seed 1998 then calls advance(1998) on an iterator already at 1998, which is undefined for target <= current (search/DocIdSetIterator.java:141-142). The SPARSE block reads forward from its cursor (codecs/lucene90/IndexedDISI.java:580-594), finds nothing later, and the iterator is exhausted.
4. Too few entry points. SeededHnswGraphSearcher.fromEntryPoints (util/hnsw/SeededHnswGraphSearcher.java:37-55), called from HnswGraphSearcher.search (util/hnsw/HnswGraphSearcher.java:148-152), wants 2 ordinals, gets 1, and throws (:47-49).

• A seed after the last vector document (docs 0..999 have a vector, the only seed is doc 1000): the same IllegalArgumentException, because the count includes a seed that maps to nothing.
• A DENSE block (docs 0..9899 have a vector except 9700..9799; seeds 9700, 9701, 9850; k = 3; run with assertions off only): EOFException: read past EOF ... [slice=_0_Lucene99HnswVectorsFormat_0.vec] [slice=docs] on MMapDirectory, IndexOutOfBoundsException on ByteBuffersDirectory. The factory with the same seeds returns 3 hits.
• Other layouts finish, but the mapping yields wrong ordinals, and those become the graph search's entry points: the hunt's probe of the package-private MappedDISI (vectors on even docs) mapped seeds {1, 2, 10} to ordinals [1, 2, 5], so seed doc 2 (ordinal 1) came out as ordinal 2 (doc 4); by reading its code, the recommended fix gives [1, 5] (doc 1 has no vector and is dropped). The effect on results was not measured; not claimed.

fromFloatQuery/fromByteQuery and a null Weight go through createSeedWeight; PatienceKnnVectorQuery.rewrite always rebuilds the seed Weight with it (search/PatienceKnnVectorQuery.java:297-312). A segment too small for an HNSW graph is not affected either (the default format skips the graph for small segments, codecs/lucene99/Lucene99HnswVectorsFormat.java:122-137), which is why the repro uses 1,000 vectors.

• Opt-in, experimental API. The Weight-taking constructors are public since 10.3.0; the class is @lucene.experimental (search/SeededKnnVectorQuery.java:40). Default codec and IndexWriterConfig suffice.
• Loud, sometimes misleading. One such leaf fails the whole IndexSearcher.search. On a DENSE block the EOFException: read past EOF or IndexOutOfBoundsException can send an operator looking for index corruption in an index IndexWriter wrote normally.
• No downstream caller found. Solr uses the factories; GitHub code search found no caller of the Weight-taking constructor outside Lucene.
• Likelihood: rare. It needs the experimental constructor, an unfiltered seed Weight, a sparse vector field and a seed layout that pushes the mapping past a vector document. No public report was found since 10.3.0.

TestSeededKnnSeedWithoutVector (one method, extends LuceneTestCase, package org.apache.lucene.search of the lucene/core tests, Apache license header). It is the hunt's minimal test, unchanged. It draws no random values itself (fixed default codec, ByteBuffersDirectory, default IndexWriterConfig, whose 16 MB buffer writes the 2,000 small documents as one segment at close; the test does not assert one segment); it failed with seeds DEADBEEF (gradle) and 5EED0B01 (standalone runner), with assertions on and off, and passes checkGoogleJavaFormat. The segment needs an HNSW graph, which the default format builds only from about 650 vectors (when numVectors > (int) (ln(numVectors) * 100), codecs/lucene99/Lucene99HnswVectorsWriter.java:712-722); the repro uses 1,000.

cp $REPRO/TestSeededKnnSeedWithoutVector.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestSeededKnnSeedWithoutVector -Ptests.seed=DEADBEEF

# gradle, scratch worktree at 5adff78bb168, -Ptests.seed=DEADBEEF (assertions on; -Ptests.asserts=false gives the same exception and frames)
TestSeededKnnSeedWithoutVector > testSeedHitWithoutVector FAILED
    java.lang.IllegalArgumentException: The number of entry points provided is less than the number of entry points requested
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:4B0DFB083D2B873B]:0)
        at org.apache.lucene.util.hnsw.SeededHnswGraphSearcher.fromEntryPoints(SeededHnswGraphSearcher.java:48)
        at org.apache.lucene.util.hnsw.HnswGraphSearcher.search(HnswGraphSearcher.java:151)
        at org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsReader.search(Lucene99HnswVectorsReader.java:380)
        at org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsReader.search(Lucene99HnswVectorsReader.java:324)
        at org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat$FieldsReader.search(PerFieldKnnVectorsFormat.java:329)
        at org.apache.lucene.index.CodecReader.searchNearestVectors(CodecReader.java:294)
        at org.apache.lucene.search.KnnFloatVectorQuery.approximateSearch(KnnFloatVectorQuery.java:118)
        at org.apache.lucene.search.SeededKnnVectorQuery.approximateSearch(SeededKnnVectorQuery.java:155)
        at org.apache.lucene.search.AbstractKnnVectorQuery.getLeafResults(AbstractKnnVectorQuery.java:254)
        ...
        at org.apache.lucene.search.SeededKnnVectorQuery.rewrite(SeededKnnVectorQuery.java:122)
        at org.apache.lucene.search.IndexSearcher.rewrite(IndexSearcher.java:873)
        ...
        at org.apache.lucene.search.IndexSearcher.search(IndexSearcher.java:624)
        at org.apache.lucene.search.TestSeededKnnSeedWithoutVector.testSeedHitWithoutVector(TestSeededKnnSeedWithoutVector.java:55)

# with the recommended fix: 1 test, 0 failures (assertions off); the repro, 2 probes and 4 suites: 160 tests, 0 failures

• No stated precondition. SeededKnnVectorQuery(KnnFloatVectorQuery|KnnByteVectorQuery, Query, Weight) (search/SeededKnnVectorQuery.java:85-105) has no javadoc. The class javadoc says "The underlying format is free to ignore the provided seed" (:33).
• The caller cannot reuse the safe path. createSeedWeight is package-private (:136). With a null Weight, rewrite returns a new plain SeededKnnVectorQuery (:124-133), so a subclass loses its overrides; #14838 ("Make it possible to extend Patience/Seeded knn queries") made the constructors public for subclassing. A caller can rebuild the filter with public API (FieldExistsQuery), but nothing says they must.
• Lucene's own contracts. KnnSearchStrategy.Seeded documents its iterator and count as "valid entry points" (search/knn/KnnSearchStrategy.java:125-141), and MappedDISI makes the advance call DocIdSetIterator leaves undefined (search/DocIdSetIterator.java:141-142).
• The invariant was named in review (as Benjamin Trent pointed out on #13635, 2024-08-06): the seed docs must have the vector field, or "the down stream translation from docId -> vector ordinal completely fails". createSeedWeight's FieldExistsQuery filter (#14084) answers it; the public constructor (#14838) bypasses it, and its PR and review do not discuss what the Weight may match.
• Tests. Upstream tests build the query only with a null Weight; none passes a caller-built one. #13634, the feature request, asks that an unusable seed fall back to normal graph traversal.

The strongest counter-argument: the Weight argument was the query's internal, already-rewritten state; #14838 exposed it only for subclassing, and every in-tree caller passes null or createSeedWeight's output.

Why it fails. Nothing documents the precondition, the only helper that meets it is package-private, null loses the subclass, and the failure is Lucene's own undefined advance call, surfacing as an internal IllegalArgumentException or a corruption-like EOFException. Even if maintainers call it a precondition, javadoc plus a check is warranted. The cross-model refute review rated the intended-behaviour case moderate and could not refute the bug; the independent reproducer, the devil's-advocate verifier and the adjudication rejected it.

The recommended change was applied in a scratch worktree at 5adff78bb168 and checked through gradle: the repro without it (fails, assertions on and off) and with it (passes, assertions off), then the repro, the two layout probes (seed after the last vector document; DENSE block) and TestSeededKnnFloatVectorQuery, TestSeededKnnByteVectorQuery, TestPatienceFloatVectorQuery, TestPatienceByteVectorQuery (160 tests, 0 failures, assertions on), and checkGoogleJavaFormat. An earlier run of the same change also passed 78 upstream seeded-query tests. Options B and C were not run. A guard on advance alone (newTarget > indexedDISI.docID()) fixes the repro's layout but not a seed after the last vector document, because the count still includes it. Maintainers may prefer B or C. The regression test is the one repro test, unchanged.

In SeededCollectorManager.newCollector (search/SeededKnnVectorQuery.java:347-354), walk the sorted seed docs once, advance the vector iterator only when it is behind the seed, keep the ordinal only when the vector doc equals the seed doc, pass that number to KnnSearchStrategy.Seeded, and return the plain collector when no seed has a vector (+23/-4).

for (int doc = seedDocIds.nextDoc(); doc != NO_MORE_DOCS; doc = seedDocIds.nextDoc()) {
  int vectorDoc =
      indexIterator.docID() < doc ? indexIterator.advance(doc) : indexIterator.docID();
  if (vectorDoc == NO_MORE_DOCS) break;
  if (vectorDoc == doc) {
    seedOrds[numSeedOrds++] = new ScoreDoc(indexIterator.index() + ctx.docBase, 0f);
  }
}
if (numSeedOrds == 0) return delegateCollector;
// seedDocs = TopDocsDISI over the numSeedOrds ordinals; Seeded(seedDocs, numSeedOrds, ...)

Trade-offs

Local to the seeded query; covers the repro, the seed-after-last-vector and the DENSE layouts; like the factory path it drops seeds without a vector, but only after the top-k seed collection, so a caller's Weight can give fewer than k entry points where the FieldExistsQuery filter would have collected the next-best seeds that have one. The mapping becomes eager, one pass over at most k seed docs per leaf. MappedDISI stays for the optimistic re-entry collector (search/AbstractKnnVectorQuery.java:463-469), whose seeds are kNN hits and always have a vector.

What the checks validated

Without it the repro fails with assertions on and off and the two probes fail 3 of 5 (their factory controls pass); with it the repro passes with assertions off, and the repro, the probes and the 4 suites run 160 tests, 0 failures; :lucene:core:checkGoogleJavaFormat passes.

When a Weight is given, still require FieldExistsQuery(field) (and the kNN filter), for example by building the Weight from seed with createSeedWeight, as PatienceKnnVectorQuery.rewrite already does.

Trade-offs

Simple, but it discards the caller's Weight, which is what the constructor is for, and leaves MappedDISI's undefined advance in place. Not run.

Javadoc on both constructors (the Weight must match only documents with a vector in the field, and the kNN filter), make createSeedWeight protected so subclasses can build such a Weight, and fail with a clear message.

Trade-offs

Cheapest, but it keeps the trap, and the corruption-like EOFException on a DENSE block stays unless the check covers it. Not run.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The finder listed what the seed-to-ordinal mapping needs from its inputs: sorted seed docs that each have a vector, so that every advance moves forward and the count equals the number of ordinals produced. The internal path discharges this with FieldExistsQuery; the public Weight-taking constructor does not.
• The finder then wrote a public-API JUnit test that fails on main with assertions on and off and on the 10.6.0 and 10.3.0 jars; a final repro check kept the minimal version as the one repro.
• An independent reproducer, an executed cross-model review, a devil's-advocate verifier and an adjudication reproduced it ("Prior reports, history and checks").