perf: accelerate online IVF centroid routing with HNSW

[majin1102]

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