kNN queries without a filter size each segment's heap from k: on 3 documents in one segment, k = Integer.MAX_VALUE throws and k = 2^28 runs out of memory

KnnFloatVectorQuery accepts any k >= 1 ("the number of documents to find"), and a k larger than the index returns every vector: k = 1000 over a 3-document index gives 3 hits. Since 9.10.0 the unfiltered (approximate) path builds each segment's collector with a heap sized from k (k + 1 longs on a single segment) before it looks at how many vectors the segment has. So on a single-segment index k = Integer.MAX_VALUE throws IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 2147483647 from an internal heap (with several segments it runs out of memory instead), k = 2^28 over the same 3 documents throws OutOfMemoryError with a 2 GiB heap, and k = 2^24 allocates about 128 MiB to return 3 hits. On main the same k works on that index with a filter that is not match-all (the exact path caps its queue at Math.min(k, cost), since 9.11.0) and through LeafReader#searchNearestVectors(..., int k, ...), which still caps k at the vector count. Up to 9.9.2 the query went through that method, and the readers before it carried the comment "bound k by total number of vectors to prevent oversizing data structures"; #12962 (9.10.0) made the query build its own collector and the cap was lost. The join DiversifyingChildren{Float,Byte}KnnVectorQuery has the same shape and has been unbounded since it was added in 9.8.0, and SeededKnnVectorQuery also sizes its seed collector by k. No wrong hits were seen: every search either returned the expected hits or threw.

• Segment collector: for each segment, the kNN query creates a KnnCollector through a KnnCollectorManager. The default one, TopKnnCollector, keeps the best hits in a NeighborQueue, which is a TernaryLongHeap.
• Approximate vs exact path: without a filter, every segment takes the approximate path (approximateSearch). With a filter, a segment whose matching documents are no more than its share of k takes the exact path (exactSearch), which scores the matches directly.

1. The constructor rejects only k < 1 (AbstractKnnVectorQuery.java:67-68). Without a filter (or with one that rewrites to MatchAllDocsQuery, which is dropped, :87-103), getLeafResults calls approximateSearch (:252-254).
2. KnnFloatVectorQuery.approximateSearch calls knnCollectorManager.newCollector(...) first (KnnFloatVectorQuery.java:107-108), then reads the vector values (:110) and checks Math.min(knnCollector.k(), floatVectorValues.size()) == 0 (:115): the remnant of the old cap, after the allocation. KnnByteVectorQuery is the same (:106-107, :114).
3. OptimisticKnnCollectorManager turns k into perLeafTopK from the segment's share of the index (AbstractKnnVectorQuery.java:319-347); for one segment that is k itself (computed in float, so a k above 2^24 is rounded to the nearest float). TopKnnCollectorManager passes it on unchanged: new TopKnnCollector(k, visitedLimit, searchStrategy) (knn/TopKnnCollectorManager.java:46, :52).
4. TopKnnCollector builds new NeighborQueue(k, false) (TopKnnCollector.java:45), and TernaryLongHeap(k) throws IllegalArgumentException for k >= ArrayUtil.MAX_ARRAY_LENGTH ("Throw exception to prevent confusing OOME") or allocates new long[k + 1] at once (util/TernaryLongHeap.java:56-69).
5. With several segments, the optimistic re-entry pass builds two more full-k collectors per re-entered segment (ReentrantKnnCollectorManager, AbstractKnnVectorQuery.java:128-130, :433-476).
6. Join: DiversifyingNearestChildrenKnnCollectorManager builds new DiversifyingNearestChildrenKnnCollector(k, ...) (:65-66, :77-78), whose NodeIdCachingHeap(k) allocates three arrays of k + 1 entries and a k-sized hash map (DiversifyingNearestChildrenKnnCollector.java:61, :140-153).
7. Seeded: SeededKnnVectorQuery first builds a seed collector, new TopScoreDocCollectorManager(k, null, Integer.MAX_VALUE).newCollector() (SeededKnnVectorQuery.java:315-316), with the query's full k on every segment; its TopScoreDocCollector allocates new TernaryLongHeap(numHits, ...) at once (TopScoreDocCollector.java:44).

Where Lucene does cap the same request: the exact path, Math.min(k, Math.toIntExact(acceptIterator.cost())) (AbstractKnnVectorQuery.java:373, #13184, from 9.11.0); LeafReader#searchNearestVectors(..., int k, ...), k = Math.min(k, ...size()) (index/LeafReader.java:288, :332, :376); regular top-N search, IndexSearcher#searchAfter caps numHits at max(1, maxDoc) (IndexSearcher.java:587-597).

The k = 2^24 rows come from runs on main ea57360912ed, whose query path is the same as a9779ef3c193's. On 12 vectors, k = 2^22 allocates 33,561,432 bytes in 1 segment and 302,491,608 bytes in 4 segments (9.01x); one k = 2^26 search over 3 vectors runs out of a 512 MiB heap. On a9779ef3c193, k = Integer.MAX_VALUE over 4 segments of 3 documents runs out of a 2 GiB heap instead of throwing IllegalArgumentException, and the same k also fails for KnnByteVectorQuery, KnnFloat16VectorQuery, PatienceKnnVectorQuery, SeededKnnVectorQuery and the byte join query. The filtered vs unfiltered contrast exists only from 9.11.0.

• Who is hit. Unfiltered KnnFloatVectorQuery / KnnByteVectorQuery (or with a filter that rewrites to MatchAllDocsQuery) on 9.10.0 through 10.5.2 and main; DiversifyingChildrenFloatKnnVectorQuery / DiversifyingChildrenByteKnnVectorQuery on 9.8.0 and later. Default codec, default IndexSearcher, no setting. SeededKnnVectorQuery and PatienceKnnVectorQuery (since 10.2.0) and KnnFloat16VectorQuery (main only) fail the same way on main (executed on main only).
• Trigger. k = Integer.MAX_VALUE to mean "all" (an idiom IndexSearcher supports: TestIndexSearcher.testHugeN), a k derived from the index size, or a server that forwards a client's k unchecked.
• Effect. On a single-segment index, k at or above ArrayUtil.MAX_ARRAY_LENGTH always throws IllegalArgumentException on the first search; with several segments the first pass sizes each heap by the segment's share of k, so it runs out of memory instead (4 segments, 2 GiB heap). Below that, a single-segment search reserves about 8 bytes per unit of k before it collects anything: 128 MiB for k = 2^24, a 512 MiB heap exhausted at k = 2^26, a 2 GiB heap at k = 2^28. More segments (about 9x for 4: first-pass heaps by each segment's share, plus two full-k collectors per re-entered segment) and concurrent searches add up. After a caught OutOfMemoryError a follow-up search on the same searcher worked; with -XX:+CrashOnOutOfMemoryError the JVM aborted.
• Not affected. No wrong hits were seen; on the 3-document index a filter that is not match-all takes the bounded exact path; ordinary k values cost kilobytes.
• Scale. None: 3 documents in one segment.
• How likely. Rare: only a very large k fails, and the Integer.MAX_VALUE case is loud on the first search; nothing was reported since 9.10.0 (2024-02).

# Lucene main 645d4fe14a20, assertions on (-ea), seed 5EED0454: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected 3 hits for k = Integer.MAX_VALUE, but got java.lang.IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 2147483647
       org.apache.lucene.search.TestKnnQueryKMaxValue.testKMaxValue(TestKnnQueryKMaxValue.java:45)
     Caused by: java.lang.IllegalArgumentException: initialCapacity must be > 0 and < 2147483630; got: 2147483647
       org.apache.lucene.util.TernaryLongHeap.<init>(TernaryLongHeap.java:59)
       org.apache.lucene.util.hnsw.NeighborQueue.<init>(NeighborQueue.java:60)
       org.apache.lucene.search.TopKnnCollector.<init>(TopKnnCollector.java:45)
       org.apache.lucene.search.knn.TopKnnCollectorManager.newOptimisticCollector(TopKnnCollectorManager.java:52)
       org.apache.lucene.search.AbstractKnnVectorQuery$OptimisticKnnCollectorManager.newCollector(AbstractKnnVectorQuery.java:330)
       [...]

• Contract. KnnFloatVectorQuery: "@param k the number of documents to find", "@throws IllegalArgumentException if <code>k</code> is less than 1" (KnnFloatVectorQuery.java:60-61, :73-75; KnnByteVectorQuery.java:59-60, :72-74). These constructors are not @lucene.experimental. The heap's "initialCapacity must be > 0 and < 2147483630" for an accepted k is not the documented failure.
• Upstream test. BaseKnnVectorQueryTestCase.testFindAll: "Tests that a AbstractKnnVectorQuery whose topK &gt;= numDocs returns all the documents in score order" (k = 10 over 3 documents, :178-194).
• A deliberate cap, lost silently. 9.0-9.7 readers: "// bound k by total number of vectors to prevent oversizing data structures" / k = Math.min(k, fieldEntry.size()); (9.7.0 Lucene95HnswVectorsReader.java:288-289, from LUCENE-9614 / #413). 9.8-9.9: the cap lived in LeafReader#searchNearestVectors(..., int k, ...) (9.9.2 LeafReader.java:253), which the query called (9.9.2 KnnFloatVectorQuery.java:82); main still has it (LeafReader.java:288). #12962 (9.10.0) made the query build its own collector; reviewers asked to keep the int-k LeafReader method unchanged, and none of the 22 conversation or 40 review comments discusses the cap.
• Siblings are capped. #13184 (9.11.0) capped the exact path of the same class (AbstractKnnVectorQuery.java:373) because "the number of candidates is actually lower than k". Until then that path failed for a huge k too (9.9.2, 9.10.0), so the project has bounded this kind of k-sized preallocation before. LUCENE-4938 extended IndexSearcher's min(maxDoc, n) cap to the sorted searches and added TestIndexSearcher.testHugeN ("should not throw exception"), which runs search(query, Integer.MAX_VALUE).
• Inconsistent (from 9.11.0). On one index, k = Integer.MAX_VALUE and 2^28 return all hits with a filter matching every document and through LeafReader#searchNearestVectors(int k), but throw without the filter (this doc's test; a verifier's contrast probe).
• The manager API speaks of per-leaf sizing. KnnCollectorManager#newOptimisticCollector: "generally with a specific k value, scaled per leaf statistics".

The strongest case for "intended": top-k naturally needs O(k) storage; TopKnnCollector is @lucene.experimental; the heap's IllegalArgumentException is deliberate ("to prevent confusing OOME"); maintainers have said Lucene targets "some reasonable value of k" (#9588), that k = Integer.MAX_VALUE "will not only run in O(maxDoc) time but also use O(maxDoc) memory" (#12679), and, on dev@ (2022-11), of a very large k, "something that I would like to be documented as not recommended"; downstream engines bound k; SECURITY.md leaves bounding resource-consuming input to the application.

Why it fails: here the storage does not grow with the index at all, because it is reserved per segment before the segment's size is known; 3 documents need 2 GiB. Lucene capped exactly this on purpose until 9.9.2 and still caps it on the filtered path and in LeafReader, and the remarks above were made while the cap existed, so they assume O(maxDoc). The heap's guard only turns an OOME into an exception; it does not make k = Integer.MAX_VALUE a documented failure of the query. Every reviewer rejected the intended-behaviour argument; the latest cross-model fact check rated it moderate, mainly as an argument about which fix to choose (a documented high upper bound would not contradict testFindAll, which uses k = 10).

One fix was built and validated, first in two files and then completed with the seeded query; the alternatives are untested.

A segment cannot return more hits than it has documents. TopKnnCollectorManager.newCollector and newOptimisticCollector pass perLeafK(k, context) instead of k, DiversifyingNearestChildrenKnnCollectorManager does the same in both methods, and SeededKnnVectorQuery's collector manager sizes its seed collector the same way. The TopKnnCollectorManager change covers KnnFloatVectorQuery, KnnByteVectorQuery, KnnFloat16VectorQuery, the optimistic re-entry pass and PatienceKnnVectorQuery; SeededKnnVectorQuery builds its seed collector from the full k on every segment, so it needs the third change (executed).

// TopKnnCollectorManager: newCollector and newOptimisticCollector
return new TopKnnCollector(perLeafK(k, context), visitedLimit, searchStrategy);

/** A leaf cannot return more than {@code maxDoc} hits, so do not size its collector by a larger k. */
private static int perLeafK(int k, LeafReaderContext context) {
  return Math.max(1, Math.min(k, context.reader().maxDoc()));
}

// DiversifyingNearestChildrenKnnCollectorManager: the same helper, in both methods
return new DiversifyingNearestChildrenKnnCollector(
    perLeafK(k, context), visitedLimit, searchStrategy, parentBitSet);

// SeededKnnVectorQuery.SeededCollectorManager.newCollector: the seed collector
// a leaf cannot return more than maxDoc seeds, so do not size the collector by a larger k
int seedK = Math.max(1, Math.min(k, ctx.reader().maxDoc()));
TopScoreDocCollector seedCollector =
    new TopScoreDocCollectorManager(seedK, null, Integer.MAX_VALUE).newCollector();

Trade-offs

• Same hits. A segment has at most maxDoc vectors, so min(k, maxDoc) slots hold every hit. The reader's choice between graph search and an exhaustive scan (knnCollector.k() < numVectors, Lucene99HnswVectorsReader.java:373) does not change: if k >= numVectors, then min(k, maxDoc) >= numVectors too. A segment cannot hold more than maxDoc seed hits either. Math.max(1, ...) keeps k >= 1 for an empty segment.
• Bound is maxDoc, not the vector count as before 9.10.0 (the managers do not know the field), so a large segment can still reserve 8 bytes per document for a huge k: O(maxDoc), the cost maintainers described in #12679.
• Custom KnnCollectorManager implementations are not covered. No benchmark was run; the change adds one Math.min per segment. Add a CHANGES entry under Bug Fixes.
• Backports (read): branch_10x and branch_10_6 have the same manager code as main. Older lines also allocate a global BlockingFloatHeap(k) per multi-segment query (TopKnnCollectorManager from 9.10.0, the join manager in 9.12.3, both up to 10.2.2), which a backport must bound too; 9.8.x and 9.9.x build the join collector directly in the query; SeededKnnVectorQuery exists from 10.2.0.

What the checks validated

• Two-manager fix (fix.diff), clean scratch worktree at a9779ef3c193, gradle, seed DEADBEEF, -Ptests.heapsize=2g. Stock: TestKnnQueryLargeK 2 of 4 fail, TestDiversifyingKnnLargeK 2 of 3 fail. With the fix: both pass (4 of 4, 3 of 3), with assertions on and with -Ptests.asserts=false; the 13 closest suites pass; format and lint pass.
• The seeded gap (standalone runner, a9779ef3c193): the 8 variant tests fail 6 of 6 and 2 of 2 on stock; with fix.diff 4 of 6 pass and both seeded tests still throw IllegalArgumentException from TopScoreDocCollector; with fix-complete.diff all pass, assertions on and off.
• Complete fix (fix-complete.diff), gradle on a source extraction of a9779ef3c193 with only the patch and the four test files added: with assertions on 338 tests, 0 failures (the 15 repro and variant tests plus TestKnnFloatVectorQuery (43), TestKnnByteVectorQuery (40), TestKnnByteVectorQueryMMap (40), TestSeededKnnFloatVectorQuery (39), TestSeededKnnByteVectorQuery (39), TestPatienceFloatVectorQuery (38), TestPatienceByteVectorQuery (38), TestKnnGraph (6), TestTopKnnResults (1), join TestParentBlockJoinFloatKnnVectorQuery (12), TestParentBlockJoinFloat16KnnVectorQuery (12), TestParentBlockJoinByteKnnVectorQuery (11), TestToParentJoinKnnResults (4)); with -Ptests.asserts=false the 15 tests pass; checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest pass for core and join.
• Not validated with the fix: byte and float16 queries on several segments, seeded queries with a filter, executor-backed searchers.

In approximateSearch, read the vector values first and size the collector by min(k, values.size()), in the core and the join queries.

Trade-offs

The pre-9.10 behaviour of the core queries (the join queries were unbounded before 9.10 too) and the tightest bound, but KnnCollectorManager#newCollector has no k parameter, so it needs an API change (or routing a bounded k through newOptimisticCollector).

Start NeighborQueue / TernaryLongHeap small and grow it as hits arrive, up to k.

Trade-offs

Also helps large segments with a huge k, but the heap's capacity is its overflow bound today (TernaryLongHeap.java:93-103), so it needs a separate maximum, and it touches the hot path of every kNN search; needs benchmarks. The heap's growth has its own limit (TernaryLongHeap stops growing at 715,827,883 elements, registry LFV-069).

Validate k against an upper bound in the constructor, or document one.

Trade-offs

The query does not know the index when it is built, and a bound would not fit the filtered path, LeafReader's int-k method and IndexSearcher (testHugeN), which all accept any k (testFindAll uses only k = 10, so a high documented bound would not contradict it). Until a fix ships, applications can cap k themselves, for example at reader.maxDoc() (read, not executed); that caps by the whole index, so on several segments each segment's collectors can still be sized by the index's maxDoc.

Method: a static and dynamic boundary scan (the finder's label: semi-formal; no model checker, solver or prover found it).

• A static guard inventory of the real jars: a JDK ClassFile API pass over 27 core and non-sandbox module jars listed 1,231 public entry points whose bytecode reaches an IllegalArgumentException, with each guard's parameters and constants.
• The kNN query constructors reject only k < 1 (AbstractKnnVectorQuery.java:67-68), so every k up to Integer.MAX_VALUE is accepted.
• A scratch driver (its output was not saved) then ran KnnFloatVectorQuery, KnnByteVectorQuery and the two DiversifyingChildren* queries end to end on the stock jars with k in {5, 1000, 2^20, 2^27, 2^28, Integer.MAX_VALUE - 9, Integer.MAX_VALUE}, and a public-API JUnit test witnessed the failure (2026-10-26).
• The same scan found the pattern at LatLonPoint.nearest(..., n = Integer.MAX_VALUE) and RescoreTopNQuery(..., n = Integer.MAX_VALUE) (an IllegalArgumentException from PriorityQueue); those are separate sites and were not filed.