A kNN query's mergeLeafResults may return its hits in any order, but Lucene reads the first hit as the max score and the last as the lowest (k-th) score

AbstractKnnVectorQuery#mergeLeafResults is a protected, @lucene.experimental hook on the public KnnFloatVectorQuery and KnnByteVectorQuery. Its javadoc says it returns "index-level kNN results (no constraint on their ordering)" and is "useful for reading and / or modifying the final results as needed". rewrite() passes its output unchanged to three readers that assume descending score order: DocAndScoreQuery.createDocAndScoreQuery takes the max score from the first hit, the optimistic re-entry pass (10.3.0 and later) and the no-match explainer take the lowest (k-th) score from the last. An override that returns exactly the default hits in another order therefore gets a rewritten query whose getMaxScore is below scores it returns (0.5 against 1.0 with 2 documents), so top-score pruning in a disjunction can skip the best kNN hit, and on a multi-segment index the second search pass is skipped and farther neighbours come back. Stock queries are not affected. Affected: 9.12.3 and 10.0.0 through 10.6.0, and main; sorting a copy of the hook's output in runSearchTasks fixes it.

1. The hook promises freedom of order. mergeLeafResults says "@return index-level kNN results (no constraint on their ordering)" and "This method is useful for reading and / or modifying the final results as needed" (AbstractKnnVectorQuery.java:416-430). It is protected and @lucene.experimental, inherited by the public, non-final KnnFloatVectorQuery (KnnFloatVectorQuery.java:48), KnnByteVectorQuery (KnnByteVectorQuery.java:47) and, on main, KnnFloat16VectorQuery.
2. rewrite() uses its output as is. runSearchTasks returns mergeLeafResults(...) unchanged (:227), for the first pass (:118) and the re-entry pass (:150).
3. Max score from the first hit. DocAndScoreQuery.createDocAndScoreQuery does float maxScore = topK.scoreDocs[0].score; (DocAndScoreQuery.java:125) before sorting by doc id (:126), and the scorer's getMaxScore returns it (:238-241), while score() returns each hit's own score (:243-246). Scorer#getMaxScore must bound the scores of the documents in range (Scorer.java:75-79).
4. Lowest (k-th) score from the last hit. The re-entry pass takes minTopKScore = topK.scoreDocs[topK.scoreDocs.length - 1].score (AbstractKnnVectorQuery.java:126) and searches a segment again only if its lowest hit reaches it (:136-137). The no-match explainer repeats the read, with the comment "topK is score-descending" (:160-166). A probe on the 10-segment shape below executed both: the stock query re-enters 1 segment and the override 0, and explain for doc 0 cites a minimum top-K score of 1.0 with the override against 4.1631973E-4 for the stock query.
5. Pruning trusts the bound. Under TOP_SCORES a disjunction is scored by MaxScoreBulkScorer, which treats a clause as non-essential once the minimum competitive score exceeds its bound; the kNN-only best hit is then never scored.

• Minimal repro: 2 documents, doc 0 at (0, 0) and doc 1 at (1, 0), query (1, 0), k = 2, an override that returns the default hits sorted by doc id: getMaxScore 0.5, then score() 1.0 for doc 1.
• Pruned disjunction: 200,001 documents, top-1 of SHOULD(kNN, k = 5) + SHOULD(0.5-boosted constant-score term), where doc 200000 is the query vector and has no term. In doc-id order the kNN clause's bound is doc 0's score, 1/101 = 0.0099 (the term clause's is 0.5), and the result is doc 0 (0.51) instead of doc 200000 (1.0). With a BM25 term clause over 20,000 documents and the default IndexSearcher#search(Query, int): doc 0 (0.32496786) instead of doc 19999 (1.0).
• Re-entry (10.3.0 and later): 10 segments of 2,000 documents, k = 50, the nearest neighbours at the end of the last segment. The stock query returns exactly docs 19950-19999. In doc-id order the last hit is the exact match (score 1.0), so no segment is searched again (the stock query re-enters 1), and the result contains doc 16000 from segment 8 (distance 4000). An independent shape (10 x 150 documents, k = 50): 12 of the 50 hits come from other segments.

Every test ran the stock KnnFloatVectorQuery as a control, and it was correct.

• What goes wrong. Silent, lower-quality results, the same with assertions on and off. (1) The rewritten query breaks the Scorer#getMaxScore upper bound, so top-score pruning over it (a scored disjunction under TOP_SCORES, as the default IndexSearcher#search(Query, int) runs it) can skip the kNN clause's best hits. (2) From 10.3.0 a kNN query on its own, on a multi-segment index, can return farther neighbours because the second pass is skipped; whether it shows depends on where the neighbours sit. (3) On 10.6.0 and main, explanations of documents that were not collected cite a wrong minimum score (executed on main by a probe).
• What the safety probe never saw. 10 runs, 9 random indexes with deletions, vectorless documents, kNN filters, FILTER and MUST_NOT clauses, and five overrides (four pure reorderings and one that re-weights the hits without re-sorting): no deleted, filtered, excluded or vectorless document was returned; for the pure reorderings no score was paired with the wrong document and no rewrite re-entered more segments than the stock query, which also follows from the code (the last entry of a reordering is never below the true minimum). An override that also lowers scores can re-enter more segments; that comes from the score change, not from the order.
• Who is exposed. Subclasses of KnnFloatVectorQuery or KnnByteVectorQuery (also when wrapped in SeededKnnVectorQuery or PatienceKnnVectorQuery, which delegate the hook) whose mergeLeafResults returns hits not sorted by descending score: re-weighted or rescored without re-sorting (an override that multiplies each score by 1 + 3 x doc/N gave score 2.0 above getMaxScore 1.0), in doc-id order, or concatenated per segment (as an early revision of #12679 did).
• Configuration and scale. Default codec, IndexWriterConfig and IndexSearcher. The bound break shows with 2 documents; the executed top-1 losses used 20,000 and 200,001 documents, enough for pruning to engage.
• How likely. Rare. No in-tree query triggers it, and the five downstream overrides read (Elasticsearch, Solr, OpenSearch k-NN, mongot, nrtsearch) return sorted TopDocs.merge output.

The class sits in org.apache.lucene.search, next to TestKnnFloatVectorQuery, and uses nothing package-private: a subclass of the public KnnFloatVectorQuery overriding the protected hook, and the public Weight and Scorer API. It pins the default codec and uses ByteBuffersDirectory, a plain IndexWriter and IndexSearcher; its data and oracle are deterministic, while the test harness still randomizes ambient settings (locale, time zone, similarity) that do not enter this result. It compiles on 9.9.0 and later; on 9.8.0 the hook does not exist.

It shows the max-score half only, on purpose. The executed end-to-end repros (a lost top-1 under pruning, farther neighbours on 10 segments) used 20,000 and 200,001 documents, or a 10-segment index; no smaller size was tried. The same fix covers them.

Regression test: this same test, as written. With the recommended fix it passes, together with the core format, ECJ and forbidden-apis checks.

cp $REPRO/TestKnnMergeLeafResultsOrder.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestKnnMergeLeafResultsOrder -Ptests.seed=DEADBEEF
# assertions off fails the same way: add -Ptests.asserts=false (the recorded runs added --offline --no-daemon)

# gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, assertions on
TestKnnMergeLeafResultsOrder > testMaxScoreBoundsScoresWithDocIdOrderedMerge FAILED
    java.lang.AssertionError: getMaxScore 0.5 < score 1.0
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:6BAF8CA364470CFD]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.search.TestKnnMergeLeafResultsOrder.testMaxScoreBoundsScoresWithDocIdOrderedMerge(TestKnnMergeLeafResultsOrder.java:61)

# standalone runner, seed DEADBEEF: the same message, 1 of 1 failed each
main 645d4fe14a20 (-ea, -da), 10.6.0, 10.5.2, 10.3.0, 10.0.0, 9.12.3
# passed: 9.12.2, 9.9.0; 9.8.0: does not compile (no mergeLeafResults)
# a later fact check: the same five releases with -da fail the same way

• The contract for overriders says the opposite (AbstractKnnVectorQuery.java:416-427). No javadoc, MIGRATE.md or CHANGES.txt entry asks overrides to sort.
• The precondition that exists is for another caller. "The entries of topK are expected in descending score order" is on createDocAndScoreQuery (DocAndScoreQuery.java:109-111, #16686). Lucene makes that call with the override's output; the overrider never calls it, and the order-dependent reads inside rewrite() are undocumented implementation details.
• Bound breaks are treated as bugs. #14857 "AbstractKnnVectorQuery breaks shallowAdvance contract, causing chaos" (fixed by #14858) and #16697 "Fix block-max support of DoubleValuesSource" (merged 2026-10-09: getMaxScore covered too little of the range).
• History. The first-entry read (#12146, 2023-02) was correct when written, because the merge could not be overridden. #12590 (2023-10) made it overridable and documented the order as free without touching that read. The last-entry reads came later (#14226, #16271). No review comment on #12590, #12679, #14226, #16271, #16324 or #16686 discusses the hook's ordering.
• The planned use was unordered. In the first revision of #12679 the hook's author overrode it to concatenate per-segment results: "Results of HNSW searches need not be sorted".
• No test covers it. No upstream test overrides mergeLeafResults with unsorted output.

The strongest case for "intended" (a devil's-advocate verifier, cross-model reviews and the adjudication built it): the hook is @lucene.experimental and custom queries are "an expert level task, so tread carefully" (package-info.java:388-390); in #12590 a reviewer (benwtrent) warned that "It would be very easy to do the wrong thing by allowing sub-classes to override this method for yet another avenue of customization"; every later change (#14226, #16271, #16686) treats the merged result as score-descending, so the 2023 sentence may be a stale doc; the default delegates to TopDocs.merge, whose javadoc says it returns the top hits "sorting by score" and requires sorted input (TopDocs.java:197-198), so score order is the default's convention; and no known deployment is affected.

Why it fails: experimental status allows incompatible API changes, not code that contradicts the API's own javadoc; the default's score order is a convention, but the hook's contract does not ask overrides to keep it and says the opposite; the warning was general and ordering was never raised; the later code never revisited the hook. It does make a javadoc change that requires descending order an acceptable resolution (option C), not "not a bug": today the documented contract and the code disagree.

Two fixes were validated through gradle in a scratch worktree of 645d4fe14a20; the recommended one changes one place and covers every reader. A documentation-only change was not built.

Where rewrite() receives the hook's output, sort a copy by descending score, then ascending doc id. The override's hits and scores are kept; only their order changes, and createDocAndScoreQuery re-sorts by doc id anyway.

TopDocs merged = mergeLeafResults(perLeafResults.values().toArray(TopDocs[]::new));
// mergeLeafResults may return its hits in any order, but the re-entry pass in rewrite(), the
// no-match explainer and DocAndScoreQuery (max score) read them as score-descending
ScoreDoc[] hits = merged.scoreDocs.clone();
Arrays.sort(
    hits,
    (a, b) ->
        a.score != b.score ? Float.compare(b.score, a.score) : Integer.compare(a.doc, b.doc));
return new TopDocs(merged.totalHits, hits);

Trade-offs

• Coverage. Fixes the max-score, re-entry and explainer reads, and any later reader in rewrite(), at the one place where the order became free.
• Cost. One copy of the ScoreDoc[] and an O(k log k) sort of the merged hits per pass (not benchmarked); the default output is already sorted, so an O(k) check could skip the copy.
• Stock results unchanged. TopDocs.merge orders by descending score, then shard index (-1 for these hits), then doc id (TopDocs.java:44-45), the same order as the sort (read).
• Aliasing. Today createDocAndScoreQuery sorts the override's own array by doc id in place; with the fix it sorts the copy, so an override that keeps a reference to the array it returned no longer sees it reordered.
• Scope. It does not harden the public createDocAndScoreQuery for other callers that pass unsorted hits (see the scan option).
• Score-changing overrides. The min and max reads become consistent, but the re-entry pass then compares the override's lowest score with raw per-segment scores; the sort does not make such overrides fully consistent.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, OpenJDK 25.0.3, seed DEADBEEF (2026-10-31). Stock: the repro fails. With the fix: the repro and every kNN, seeded, patience, rescore and vector-similarity query suite in core (18 classes, 372 tests, 5 skipped) and the four parent-join kNN suites (4 classes, 39 tests): 0 failures.
• With assertions off: the repro, TestKnnFloatVectorQuery and TestKnnByteVectorQuery (84 tests) pass; checkGoogleJavaFormat, ecjLintMain, ecjLintTest (with the repro test in place), forbiddenApisMain and forbiddenApisTest pass.
• The finder's two end-to-end tests pass with the fix on the 645d4fe14a20 jars; earlier the same change passed the independent reproducer's four tests, the cross-model reviewers' tests and 137 and 237 upstream kNN tests.

A private minScore(TopDocs) scan for the re-entry pass (AbstractKnnVectorQuery.java:126) and the explainer (:163), and a max scan in createDocAndScoreQuery (DocAndScoreQuery.java:125), whose javadoc then says the entries "may be in any order" (+19/-7, two files).

float maxScore = Float.NEGATIVE_INFINITY; // DocAndScoreQuery.createDocAndScoreQuery
for (ScoreDoc scoreDoc : topK.scoreDocs) {
  maxScore = Math.max(maxScore, scoreDoc.score);
}

Trade-offs

No reordering, and it also relaxes the public createDocAndScoreQuery precondition, so any caller may pass hits in any order (that also covers RescoreTopNQuery, a separate case found earlier that reaches the same line with heap-ordered hits). It touches three sites, and a future reader in rewrite() must remember to scan. Same score-changing caveat as the sort.

What the checks validated

Gradle on 645d4fe14a20: the same core and join test selection, 372 + 39 tests, 0 failures; checkGoogleJavaFormat and ecjLintMain pass; the finder's two end-to-end tests pass with it on the main jars.

Change the @return line of mergeLeafResults to require hits sorted by descending score, in line with #16686 and the explainer comment; optionally assert the order in runSearchTasks.

Trade-offs

No runtime change and consistent with the later code, but it changes the contract under existing overrides that followed the current javadoc, an assertion fires only with assertions on, and an override that misses the note still gets silently wrong results. Reasonable as a companion to a code fix, weaker alone.

Method: non-formal (code reading, then public-API JUnit tests).

• A hunt unit on the kNN query layer was modelling AbstractKnnVectorQuery.rewrite in TLA+ (KnnRewrite.tla). Its merge step is a set (the top k of the union), so the model cannot see an ordering defect.
• While writing that step, the finder read the mergeLeafResults javadoc ("no constraint on their ordering") against the code that consumes the result, found the first- and last-entry reads, and confirmed them with a probe and a JUnit with a doc-id-ordered override on the stock main jars (2 of 2 fail with assertions on and off).
• A cross-model review, an independent reproducer, a second cross-model review, a devil's-advocate verifier and an adjudication checked it; a follow-up ran it from 9.8.0 to main and probed for safety effects; the repro was minimized to one test.