Reuse IVF Coarse-Quantizer Routing Across Index Segments

[majin1102]

Proposal

Add a content-derived coarse-quantizer fingerprint to IVF index segment metadata. When every physical segment of a logical index has the same well-formed fingerprint, rank the IVF centroids once per query and reuse the selected partition IDs and query-to-centroid distances across all segments.

If any segment has a missing, malformed, or different fingerprint, Lance keeps the existing per-segment routing behavior.

This implements the compatibility-based shared routing described in Lance Vector Index: Multi-Segment Final State.

Draft PR: #8966

Motivation

Lance supports both shared and independently trained IVF models across physical index segments. This proposal does not suggest that segments should share a coarse quantizer, nor does it change the independently trained path.

The optimization applies only when multiple segments intentionally use the same ordered IVF centroids—for example, when distributed workers horizontally index a static or batch-built dataset using one globally trained model. In this topology, the segments are physical shards of one logical IVF index, but a query currently runs find_partitions independently for every segment:

query
  +-- segment 0: find_partitions -> search partitions
  +-- segment 1: find_partitions -> search partitions
  `-- segment N: find_partitions -> search partitions

For these segments, find_partitions receives identical inputs and returns identical partition IDs and centroid distances. Repeating it once per segment performs identical work. Segments with different coarse quantizers continue to rank and search their partitions independently.

The proposed path is:

                         +-- segment 0: search partitions
query -> find_partitions +-- segment 1: search partitions
                         `-- segment N: search partitions
                                      -> merge top-k

Only coarse routing is shared. Each segment still searches its own inverted lists before the existing global top-k merge.

Design

The fingerprint is a 32-byte SHA-256 digest over the lance.coarse_quantizer.v1 domain separator, distance metric, centroid count, vector dimension, centroid scalar type, and ordered centroid values in canonical little-endian form. Centroid order is included because partition IDs are positions in that array. The within-partition codec is excluded because it does not affect routing.

Lance derives the fingerprint from the final effective IvfModel, after training, conversion, and partition adjustment. This applies to ordinary, distributed, independently trained, appended, retrained, rebalanced, and merged segments. Operations that preserve the routing model preserve its identity. A writer that cannot reliably describe its final routing state omits the field, causing queries to use the existing path.

For a query over two or more segments, Lance compares their fingerprints. If all are equal and well-formed, it opens one representative segment, normalizes the query, calls find_partitions once, and fans out the result. Otherwise it uses the existing path. The first implementation is all-or-nothing and does not group matching subsets within a mixed set of segments.

Format change

Add one optional field to VectorIndexDetails:

optional bytes coarse_quantizer_fingerprint = 10;

The persisted fingerprint establishes a routing-compatibility contract between index writers and readers. Lance SDKs and other execution engines can determine from segment metadata, before fan-out, whether all segments use the same ordered coarse model. They can then load the centroid list from one representative segment, rank it once, and reuse the routing result. A reader could instead load and compare the centroids from every segment, but that adds noticeable overhead for cold object-store and short-lived workloads and requires each engine to implement the same discovery logic.

The field always describes the final effective routing model:

• If an operation creates or changes the routing model, it computes a new fingerprint from the final model.
• If the routing model is unchanged, it preserves the existing fingerprint.
• If the final routing identity cannot be computed reliably, it omits or clears the field.

As a result, segments with the same final routing model receive the same fingerprint regardless of how they were built.

The field is an optimization hint with fail-closed semantics:

• New readers query legacy indexes through the existing path.
• Old readers ignore the new optional field.
• Invalid lengths, invalid metadata, and mismatches disable reuse.
• Losing the field loses only the optimization, not query correctness.
• Reuse is enabled only when every queried segment has the same well-formed 32-byte value.

No dataset migration or reader/writer feature flag is required because the field does not affect index readability or query semantics.

Benchmark plan

The benchmark evaluates routing reuse within a shared-model topology. It does not compare shared-model indexing with independently trained segment models.

The benchmark isolates coarse-routing reuse from index construction and storage effects. Two Lance branches are created from the same LAION 100M dataset version and indexed with identical fragment groups, six physical segments, 24,414 IVF centroids, and a shared 5-bit RaBitQ model. The only A/B difference is whether the segments carry the coarse-quantizer fingerprint.

Before measuring performance, query-plan metrics verify that the baseline calls find_partitions once per segment while the optimized path calls it once and reuses the result for the other five segments. They also verify that no payload LanceRead is introduced.

Both indexes are pre-warmed into the index cache before timing. Timed queries return only _rowid and _distance and cover k={10,100}, nprobes={16,64,256,1024}, and request concurrency {1,8,16}. Recall is calculated separately, outside the timed interval, from the actual ANN results for a fixed query set. Each configuration is repeated three times with alternating A/B order.

The benchmark reports QPS, P50/P95/P99 latency, Recall@k, errors, and query-plan routing counters. Detailed results will be posted as a follow-up in this Discussion.

Implementation summary

The draft implementation adds the optional metadata field, fingerprint generation and lifecycle handling, fail-closed validation, rank-once/fan-out execution, and query-plan counters for routing calls and reused segments.

The execution pattern is similar to Faiss IndexShardsIVF, but Lance needs a persisted identity because its segments are independently stored and versioned.

[majin1102]

Benchmark

Configuration

Item	Value
Dataset	LAION 100M, 768D float32, L2
Index	5-bit IVF_RQ, 24,414 partitions, 6 segments
Machine	32 vCPUs, 247 GiB RAM
Lance	PyLance 12.0.0-beta.6, commit 44571ca81
Query matrix	k={10,100}, nprobes={16,64,256,1024}, concurrency {1,8,16}, query_parallelism=1
Measurement	5-second warm-up, 10-second timed window, 3 repeats per configuration, median reported
Projection	_rowid and _distance only; no payload LanceRead
Recall	Recall from 100 fixed queries; row-ID lookup and Recall calculation excluded from the timed window
Cache	128 GiB; both approximately 50.9-GB indexes fully pre-warmed

Query path

Metric	reuse-off	reuse-on
find_partitions_calls	6	1
partitions_ranked	approximately 146.5K	approximately 24.41K
coarse_quantizer_reused_segments	0	5
bytes_read / indices_loaded	0 / 0	0 / 0

Results

Across the 24 configurations, reuse-on increased QPS by 3.9%–259.5%, reduced P50 by 4.7%–72.5%, and reduced P95 by 5.3%–73.6%. All requests succeeded.

k=10

nprobes	Concurrency	Recall@10 off -> on	QPS off -> on	QPS gain	P50 ms off -> on	P95 ms off -> on
16	1	0.870 -> 0.868	99.53 -> 149.47	+50.2%	10.02 -> 6.61 (-34.0%)	10.66 -> 7.19 (-32.6%)
16	8	0.870 -> 0.868	343.87 -> 735.33	+113.8%	22.79 -> 10.69 (-53.1%)	27.69 -> 12.78 (-53.8%)
16	16	0.870 -> 0.868	367.19 -> 1,319.99	+259.5%	43.18 -> 11.88 (-72.5%)	53.49 -> 14.12 (-73.6%)
64	1	0.934 -> 0.928	85.57 -> 113.60	+32.8%	11.52 -> 8.70 (-24.5%)	13.34 -> 9.42 (-29.4%)
64	8	0.934 -> 0.928	312.57 -> 592.21	+89.5%	25.19 -> 13.31 (-47.2%)	30.08 -> 15.56 (-48.3%)
64	16	0.934 -> 0.928	335.63 -> 979.95	+192.0%	47.18 -> 15.92 (-66.3%)	58.06 -> 19.12 (-67.1%)
256	1	0.952 -> 0.949	59.68 -> 66.77	+11.9%	16.63 -> 14.85 (-10.7%)	18.14 -> 16.22 (-10.6%)
256	8	0.952 -> 0.949	237.42 -> 364.54	+53.5%	33.53 -> 21.74 (-35.2%)	37.31 -> 24.99 (-33.0%)
256	16	0.952 -> 0.949	256.12 -> 507.20	+98.0%	61.81 -> 31.26 (-49.4%)	75.18 -> 36.12 (-52.0%)
1024	1	0.960 -> 0.958	26.83 -> 27.89	+3.9%	37.16 -> 35.43 (-4.7%)	41.77 -> 39.55 (-5.3%)
1024	8	0.960 -> 0.958	125.06 -> 147.95	+18.3%	63.62 -> 53.86 (-15.3%)	69.91 -> 59.57 (-14.8%)
1024	16	0.960 -> 0.958	135.40 -> 189.58	+40.0%	117.13 -> 83.72 (-28.5%)	137.25 -> 97.76 (-28.8%)

k=100

nprobes	Concurrency	Recall@100 off -> on	QPS off -> on	QPS gain	P50 ms off -> on	P95 ms off -> on
16	1	0.8563 -> 0.8566	92.20 -> 141.99	+54.0%	10.81 -> 6.99 (-35.4%)	12.09 -> 7.49 (-38.1%)
16	8	0.8563 -> 0.8566	339.30 -> 702.83	+107.1%	23.18 -> 11.18 (-51.8%)	28.01 -> 13.32 (-52.5%)
16	16	0.8563 -> 0.8566	362.32 -> 1,263.80	+248.8%	43.75 -> 12.37 (-71.7%)	54.12 -> 14.91 (-72.5%)
64	1	0.9493 -> 0.9481	86.76 -> 111.59	+28.6%	11.43 -> 8.91 (-22.0%)	12.37 -> 9.56 (-22.8%)
64	8	0.9493 -> 0.9481	308.02 -> 577.05	+87.3%	25.47 -> 13.65 (-46.4%)	30.37 -> 16.00 (-47.3%)
64	16	0.9493 -> 0.9481	331.09 -> 941.80	+184.5%	47.83 -> 16.57 (-65.4%)	58.83 -> 20.06 (-65.9%)
256	1	0.9739 -> 0.9739	58.78 -> 65.88	+12.1%	16.85 -> 15.08 (-10.5%)	18.59 -> 16.53 (-11.1%)
256	8	0.9739 -> 0.9739	236.24 -> 362.08	+53.3%	33.66 -> 21.91 (-34.9%)	37.51 -> 25.03 (-33.3%)
256	16	0.9739 -> 0.9739	253.35 -> 495.84	+95.7%	62.48 -> 31.99 (-48.8%)	75.97 -> 36.76 (-51.6%)
1024	1	0.9804 -> 0.9801	26.32 -> 28.03	+6.5%	37.72 -> 35.17 (-6.8%)	42.15 -> 39.59 (-6.1%)
1024	8	0.9804 -> 0.9801	124.30 -> 147.64	+18.8%	64.04 -> 53.89 (-15.9%)	70.10 -> 59.67 (-14.9%)
1024	16	0.9804 -> 0.9801	134.58 -> 187.62	+39.4%	118.08 -> 84.88 (-28.1%)	139.82 -> 97.83 (-30.0%)

Conclusions

• The query plan confirms that reuse removes the duplicated coarse-routing work: find_partitions drops from six calls to one, and ranked centroids drop from approximately 146.5K to 24.41K per query.
• The largest gains appear when coarse ranking is a significant part of the workload and the system is under concurrency. At nprobes=16, concurrency 16, QPS improves by 248.8%–259.5%, while P50 and P95 fall by approximately 72%–74%.
• The relative benefit narrows as nprobes increases because RQ scanning within the selected partitions becomes dominant. At nprobes=1024, concurrency 1, the QPS gain is 3.9%–6.5%; higher concurrency still converts the saved CPU work into larger throughput gains.
• No material Recall regression was observed. The independently built A/B branches differ by at most 0.006 Recall, which cannot be attributed to routing reuse; a same-artifact spot check at k=10, nprobes=16, concurrency 16 produced identical Recall@10 (0.868) on both paths.

These results describe a single-host, six-segment, fully pre-warmed workload. Cold-cache behavior and workloads with a different number of segments require separate measurement.