Optional initial top-k threshold (seeded search cutoff)

[krickert]

Context: why this issue set exists

These issues are all tied together as an effort to create a distributed search engine optimized for high K values. This particular one is the piece I know best from the Lucene side: I built shared-floor kNN collection for Lucene's HNSW (apache/lucene#16357) - concurrent searchers share a monotonically rising k-th-best bound so each can prune candidates that can never make the merged top-k. It works, but protecting graph recall takes real machinery: an ascent gate so a converged sibling doesn't kill a search mid-descent, a greediness clamp to preserve the low-scoring bridge nodes HNSW navigation depends on.

Turbovec's exhaustive scan deletes all of that machinery. A floor here only skips work, never reachability - every vector still gets the compare - so the bound is unconditionally safe with zero recall trade-off. The kernel already maintains exactly this bound internally (the block prefilter against the running k-th best); this issue just lets a caller seed it. With that, a coordinator can broadcast the running global k-th best and every shard prunes from its first block; the same primitive serves a client or agent that fans out across indexes and merges results itself.

The companion issues are "Expose TQ+ calibration for reproducible, comparable index builds" (#202, cross-shard score comparability - that issue also carries my contributor-access request) and "Large-k search: top-k selection cost dominates the scan" (#201). Re-querying after appends and cascaded retrieval want the same floor with no distribution anywhere in sight.

Summary

Allow a search to start with a caller-supplied score threshold instead of an empty top-k. When the caller already holds k scored candidates, seeding the cutoff lets the SIMD block prefilter skip non-competitive blocks from the very first block instead of only after the local top-k fills.

Current behavior

The top-k cutoff starts empty: until k results have been gathered, every candidate is accepted, and the block prefilter (compare a block of scores against the current k-th best, skip on no survivors) only starts paying off once the heap is full and the cutoff has risen.

That is optimal for a cold search, but wasteful whenever the caller already knows a valid lower bound on the final k-th-best score:

• Re-querying after appends - the previous result set's k-th score is a valid floor for the re-run.
• Searching several indexes and merging (time-partitioned, sharded, or otherwise split corpora) - after the first index, the running merged k-th best is a floor for every subsequent search, and each gets cheaper.
• Cascaded retrieval - a cheap first pass produces candidates whose k-th score bounds the refined pass.

In all three cases the scan currently re-proves scores it was told about.

Proposed change (as implemented)

pub fn search_with_options(&self, queries: &[f32], k: usize, opts: SearchOptions) -> SearchResults
// SearchOptions { mask: Option<&[bool]>, initial_threshold: Option<f32> }  (#[non_exhaustive], builder-style setters)

Semantics: initial_threshold pre-seeds the pruning cutoff exactly as if k results at that score had already been observed. Internally every kernel variant's tracked minimum is seeded with next_down(threshold) - one ULP below (hand-rolled; f32::next_down stabilized in 1.86, MSRV is 1.81) - so the existing strict > comparisons keep ties exactly at the floor, and a floor equal to the true k-th best is provably lossless. Fill-phase insert sites gain a single gate that is a no-op when unseeded (the cutoff then starts at NEG_INFINITY).

Rows whose floor excludes candidates are padded to k with an explicit (NEG_INFINITY, -1) sentinel rather than returned short - preserving SearchResults' rectangular layout; the previously-unreachable 0-index padding is replaced so a padding entry can never be mistaken for slot 0. Documented on SearchResults.

search / search_with_mask are unchanged in signature and behavior. SearchOptions is a new idiom in an API that otherwise uses flat variants (search_with_mask, search_with_allowlist) - it avoids combinatorial explosion as options grow, but if you prefer a flat search_with_threshold, the rename is trivial.

Status

Implemented with tests on my fork: search-floor-seed. Seven integration tests plus two unit tests: lossless at floor = exact k-th best (batch and per-query, bit widths 2/3/4); higher floors return exactly the floor-filtered unseeded results plus padding; ties at the floor survive (duplicated vectors); composes with masks; NEG_INFINITY/default options bitwise-identical to plain search; NaN floor panics; scalar-fallback kernel parity via the existing FORCE_SCALAR_FALLBACK hook. Verified by injection in both directions (floor ignored: the three filter/padding tests fail; over-pruned by one ULP: four tests fail including lossless). CHANGELOG entry included.

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

[RyanCodrai]

Please explain this in simple english.

[krickert]

Simple version: a search keeps a running bar - the worst score still good enough to make the top k - and cheaply skips everything below it. Today the bar always starts from nothing and has to be rediscovered every query. This lets the caller hand the bar in at the start. That pays off whenever you already know one: re-running a query after adding vectors, searching several indexes in sequence (each search makes the next cheaper), or many machines searching at once while a coordinator tells them "the cluster already has k results this good, skip anything worse". Results are identical to a normal search - it only skips work it can prove is pointless.