Large-k search: top-k selection cost dominates the scan

[krickert]

Context: why this issue set exists

These issues are all tied together as an effort to create a distributed search engine where it's optimized for high K values. I have spent a long time working on this effort with Lucene - and with some success too (apache/lucene#16357). However, Turbovec's architecture presents a far better opportunity than Lucene due to the long time maturity of Lucene and its tie to an index setup that presents challenges to hybrid ranking.

Turbovec changes the shape of the problem. The exhaustive scan means recall doesn't fall apart at depth the way graph traversal does, so deep candidate generation - k in the thousands, feeding a hybrid rerank stage - is a natural fit rather than a fight. And because scoring is deterministic and corpus-independent, pinning one calibration across shards makes the same vector score identically everywhere, so a scatter-gather merge is exact instead of approximate. No distributed-stats phase, no rank correction - the kind of thing Lucene makes you retrofit.

The other two issues in this set cover the distributed pieces: "Expose TQ+ calibration for reproducible, comparable index builds" (#202, cross-shard score comparability - that one also carries my contributor-access request) and "Optional initial top-k threshold" (#203, the coordinator's pruning bound). This issue is different: it's a straight single-node performance item. Large-k selection cost is currently the one thing between turbovec and the high-K role, and it's worth fixing whether or not anyone ever runs it distributed.

Summary

Search latency degrades sharply at large k (thousands), not because of the scan itself but because of the top-k selection structure. Proposal: add a large-k selection path that materializes per-query scores and uses select_nth_unstable, keeping the current structure for the small-k range it is excellent at.

Current behavior

The top-k structure in search.rs is a flat array with a tracked minimum, not a binary heap: when a candidate beats the current cutoff, it overwrites the min slot and then does a linear O(k) rescan to find the new minimum:

for h in 1..k {
    if hs[h] < hs[*hmi] { *hmi = h; }
}

This idiom is shared by every kernel variant (avx2_post_flush_heap_update and the corresponding AVX-512 / NEON / scalar paths - 10+ sites), so it is a selection-strategy property, not a per-kernel detail.

For small k this is the right design - the array is cache-resident and the SIMD block prefilter (compare 32 scores against the cutoff, skip the block on no survivors) makes accepted insertions rare. But the expected number of insertions over a random-order scan is roughly k·(1 + ln(n/k)), each costing O(k). At k = 10_000, n = 10M that is on the order of ~7×10⁸ comparisons per query - the selection dominates the quantized scan by a wide margin, and per-query latency grows from tens of milliseconds to hundreds.

Proposed change

Above a k threshold (to be found by benchmark; likely somewhere in the 256-1024 range):

1. Score into a flat Vec<f32> per query (4 bytes/vector - 40 MB per query at n = 10M, transient).
2. select_nth_unstable_by for the k-th element - O(n), branch-predictable.
3. Sort the selected prefix - O(k log k).

Below the threshold, keep the existing structure unchanged. The mask/allowlist path composes naturally (masked-out slots score as -inf or are skipped before selection). If the seeded-threshold issue lands, the floor also cheapens this path (pre-filter scores before selection).

Benchmark plan

Criterion matrix: k ∈ {10, 100, 1_000, 10_000} × n ∈ {1M, 10M} × bit widths, reporting the crossover point to justify the threshold constant.

Status

Not yet implemented: the threshold constant and the score-materialization layout deserve a benchmark-first conversation. The other two issues in this set have working implementations on my fork. Happy to take this one next if the approach looks right to you.

Developed in collaboration with Claude (Fable 5); commits will carry Co-authored-by trailers per CONTRIBUTING.

Related: the gRPC surface and client examples — https://github.com/ai-pipestream/turbovec/tree/turbovec-grpc-java-example

[RyanCodrai]

Please explain this in simple english.

[krickert]

Simple version: asking for the top 10,000 results is far slower than it should be. The scan is fine - the slow part is the bookkeeping on the running top-k list, which does work proportional to k every time a candidate makes the cut. Fine at k=10, dominant at k=10,000. The fix is standard: above some k, collect the scores and run a selection algorithm instead of maintaining the list. Deep k matters when vector search is stage one of something bigger - pull 10,000 candidates cheap, rerank the best with something smarter.