perf: accelerate online IVF centroid routing with HNSW

Problem

IVF query routing currently computes the distance from the query to every centroid before selecting maximum_nprobes partitions. Both the legacy and V2 query paths call IvfModel::find_partitions, which delegates to kmeans_find_partitions_arrow_array.

This is exact and inexpensive for a small number of partitions, but its cost grows with num_partitions * dimension. For high-dimensional embeddings and thousands or tens of thousands of partitions, centroid routing can become a noticeable part of query latency.

Lance already has SimpleIndex, an HNSW graph over centroids, for K-means membership and build-time partition assignment. It was introduced in #4089 and later extended in #6119 and #6336. However, it cannot be directly reused for online IVF routing because it currently:

• returns only the nearest centroid, while queries need Top-nprobes;
• is temporary and is not persisted or cached with the IVF model;
• uses a fixed query ef = 15;
• has no query-facing recall or configuration contract;
• would add a new partition-routing recall loss before the partition-local search begins.

Proposal

Add an optional HNSW-based centroid router for the online IVF find_partitions path.

The design should consider:

• returning Top-maximum_nprobes centroid IDs and distances;
• a separate centroid-routing ef parameter, distinct from the ef used by partition-local HNSW;
• persisting the centroid graph with the IVF index, or lazily building and session-caching it if that is faster overall;
• preserving the current cosine preprocessing and distance semantics;
• falling back to exact centroid scan for small centroid sets, unsupported types/metrics, or when approximate routing is disabled;
• keeping exact routing as the compatibility-safe default until an automatic threshold is justified by benchmarks;
• recording centroid-routing latency and distance-evaluation metrics separately from partition-local search.

An optimized exact baseline should keep only Top-nprobes centroids with a heap or equivalent selection algorithm. HNSW should not claim speedup that only comes from avoiding the current full-sort overhead.

API and format questions

• Should routing be selected by an index-build option, a query option, or an automatic mode?
• Should the graph be persisted or rebuilt once and cached per session?
• What should the parameter be called so it is not confused with partition-local HNSW ef?
• How should adaptive minimum_nprobes / maximum_nprobes interact with approximate centroid routing?
• If persisted, where should the centroid router live in the current index format without extending legacy writers?

Suggested benchmark

Compare:

1. exact centroid scan + optimized Top-nprobes selection;
2. HNSW centroid routing using the same centroid array.

Recommended sweep:

• dimensions: 128, 768, 1024;
• partitions: 256, 1K, 4K, 16K;
• nprobes: 4, 16, 64;
• centroid HNSW ef: nprobes, 2x, 4x, 8x.

Record:

• centroid-routing p50/p95/p99 latency;
• number of query-to-centroid distance evaluations;
• partition recall against exact Top-nprobes;
• end-to-end Recall@K and p50/p95/p99 query latency;
• graph memory, build time, and load time.

Also run a 2x2 experiment to separate the two approximation layers:

Centroid routing	Partition-local search
Exact	IVF_PQ scan
Exact	HNSW-PQ
HNSW	IVF_PQ scan
HNSW	HNSW-PQ

Acceptance criteria

• Identify the num_partitions * dimension break-even point where centroid HNSW consistently beats an optimized exact baseline at the same end-to-end Recall@K.
• Avoid query latency regression below the break-even point through exact fallback.
• Validate centroid_ef >= maximum_nprobes with a descriptive error.
• Add recall and correctness coverage for supported metrics and multiple nprobes values.
• Preserve current behavior when the feature is not enabled.

Relevant code

• rust/lance-index/src/vector/utils.rs: build-time SimpleIndex
• rust/lance-index/src/vector/ivf.rs: IvfModel::find_partitions
• rust/lance-index/src/vector/kmeans.rs: exact centroid distance computation and selection
• rust/lance/src/index/vector/ivf.rs: legacy IVF query routing
• rust/lance/src/index/vector/ivf/v2.rs: V2 IVF query routing

Start by reading rust/lance-index/src/vector/ivf.rs and rust/lance-index/src/vector/kmeans.rs, then compare the legacy and V2 routing paths in rust/lance/src/index/vector/ivf.rs and rust/lance/src/index/vector/ivf/v2.rs. Benchmark optimized exact Top-nprobes selection against HNSW routing across the proposed sweep, and define the configuration, fallback, persistence or caching, and recall behavior. Done means meeting the acceptance criteria without changing behavior when the feature is disabled.