Repository navigation
Closes the gaps found while hardening Wax's MetalANNS engine. Breaking changes are listed first.
Breaking:
VectorNeighbor.scoreis gone (compile error with a migration message). Hits now carrydistance,metricand a computedsimilarity.distanceis the metric's native distance: cosine1 − cos, inner product−dot, L2 squared Euclidean, Hamming bit count.similarityis higher-is-better: cosine1 − distance, the others−distance.Metric.similarity(fromDistance:)does the same conversion forAdvancedresults.GraphIndex.repair()is nowasync, because it waits for in-flight searches.VectorIndex.build(vectors:ids:)now throws on a vector/ID count mismatch. Previously it truncated silently.
Fixes:
- Re-inserting a deleted id now works with
insertandbatchInsert, for String and UInt64 keys. The id reuses its slot, so the on-disk format is unchanged and indexes survive save/load. - Capacity grows on insert, with amortized doubling. Previously inserts failed with
indexCapacityExceededpast about 2× the build size. Build now allocates exactly the build count. - Builds of any size ≥ 1 work, including count ≤ degree. Compaction down to a few survivors works too.
- Builds honour Task cancellation and throw
CancellationError. Checkpoints sit at NN-Descent iterations, between build phases, and in pruner batches. - NaN or ±inf input is rejected with
ANNSError.nonFiniteVector(index:)at build, insert, batchInsert, search, batchSearch and rangeSearch. - Concurrency:
GraphIndexholds a reader/writer gate. Searches run concurrently. build, insert, batchInsert, compact and repair are exclusive across their suspension points. An insert or delete issued duringcompact()is no longer lost. - Exact search stays exact with a filter, with k + deleted rows above 256, and in
rangeSearch. These cases used to fall back to approximate graph search without saying so. At 100k they went from recall 0.16–0.42 to 1.0. Filtered search is slower (0.8 → 5.1 ms p50 at 100k) because every row is now checked; deep-k and many-delete searches got faster. StreamingIndexno longer resubmits rows already in flight when batch inserts overlap, and no longer clamps tiny deltas to degree 1.
New:
build(flatVectors:dimension:ids:)onVectorIndexandGraphIndextakes one row-major[Float], with no[[Float]]materialization.GraphIndex.delete(numericID:).
Performance (M3 Max, 384-dim cosine; see BENCHMARKS.md):
- Graph pruning is parallel with bit-identical output: 1.14 s → 0.20 s at 100k, 12.8 s → 2.25 s at 1M (5.7×).
- CPU graph search (
exactSearchMaxVectorCount: 0) reads vectors in place instead of copying the corpus on every query. p50 drops from 3.24 to 0.06 ms at 10k, 36.5 to 0.10 ms at 100k, and 489 to 326 ms at 1M. Default (exact) search latency and recall are unchanged.
Not changed: exact and graph search already agree on cosine distances for non-unit vectors (within 3e-7 against a float64 reference). The ~1e-3 difference Wax saw comes from Wax's own normalization shortcut.
Full Changelog: 0.3.0...0.4.0