LSM_VECTOR: the adaptive resume in findNeighborsFromVector discards the first pass, turning a good partial answer into a forced brute-force scan

[lvca]

Found while reviewing #5786 / #5761. Independent of that fix - it is on the plain k-NN path, not the grouped one.

What happens

LSMVectorIndex.findNeighborsFromVector, adaptive-efSearch branch (LSMVectorIndex.java:3953 on c67740ba9):

final SearchResult firstPass = searcher.search(ssp, k, initialEfSearch, 0.0f, 0.0f, bitsFilter);
if (firstPass.getNodes().length < k && graphSize >= k) {
  // Graph has enough nodes but beam search found too few - widen the beam
  searchResult = searcher.resume(k, Math.max(k * 10, 100));
} else {
  searchResult = firstPass;
}

searchResult = searcher.resume(...) replaces firstPass instead of accumulating onto it. The rows the first pass found are dropped on the floor, and resume in this branch can only ever return zero of them back.

Why resume always returns nothing here

The branch is gated on firstPass.getNodes().length < k. In jvector 4.0.0-rc.9:

• firstPass.getNodes().length == approximateResults.size() after the pop, and the branch condition says that is < k <= rerankK.
• GraphSearcher.stopSearch can only break the loop when approximateResults.size() >= rerankK. Since the queue never reached rerankK, stopSearch never fired, so searchOneLayer exited on candidates.size() == 0 - the candidate queue is dry.
• resume calls searchLayer0, which pushes evictedResults back onto candidates and re-enters searchOneLayer. evictedResults is empty too (addTopCandidate only evicts once approximateResults is full at rerankK, and reranking's overflow loop needs size > topK, also false).
• So candidates is still empty, searchOneLayer returns immediately, and reranking hands back a SearchResult with zero nodes.

The resume call is therefore pure waste in the only branch that makes it: it cannot widen anything, because the beam was not what ran out.

Reproduction

1500 vectors, 8 dims, COSINE, rebuilds frozen (VECTOR_INDEX_MUTATIONS_BEFORE_REBUILD=1_000_000, VECTOR_INDEX_REBUILD_GRAPH_RATIO=0f, VECTOR_INDEX_INACTIVITY_REBUILD_TIMEOUT_MS=0) so the deleted vectors stay in the graph as tombstones. Delete all but 4, then findNeighborsFromVector(query, 10).

Instrumenting the branch:

PROBE branch fired: firstPass=4 resumeReturned=0 k=10 graphSize=1500

and the search's own metrics:

live=4 k=10 -> hits=4, bruteForceScans 0->1

Impact

The answer stays correct - the brute-force fallback at the end of the method sees an empty results and rebuilds it, so the caller gets the right 4 rows. The costs are:

• A guaranteed full scan of every ordinal, every time this branch fires, in a case where the graph had already produced the correct answer and the code threw it away. On a large index that scan is the most expensive thing this index does (measured at 26 ms vs 95 us on 50k in LSM_VECTOR: a query with an allow-list narrower than k costs a full index scan, every time #5748).
• bruteForceScans over-counts. The metric exists to say "the graph is degraded, consider rebuilding" (LSM_VECTOR: a search whose query vector sits in a deleted region returns an empty neighbor list #5558). Here it fires on a shortfall the code manufactured, so the signal points at the wrong thing.
• A WARNING log per occurrence saying the graph may need rebuilding, when it may not.

It is rare - measured at 0 firings per 2000 queries on a healthy 50k index under #5558 - which is why it has gone unnoticed. It needs a tombstone-heavy or otherwise sparsely-reachable graph to trigger.

Suggested fix

Accumulate rather than replace, the same way the grouped path now does after #5786: keep the first pass's nodes and append what resume adds. Given the analysis above, the honest version is probably to drop the resume call from this branch altogether - a dry candidate queue is exactly the condition the brute-force fallback exists for, and going straight there would skip a pass that provably returns nothing. Either way the first pass's rows should reach the caller, so the fallback is consulted only for the genuine shortfall rather than for the whole answer.

Worth a regression test pinning both halves: that the branch's answer contains the first pass's rows, and that bruteForceScans does not increment when the graph search already found everything that is reachable.