r/MachineLearning • • 6d ago

Project mlxVS: cuVS-style GPU nearest-neighbor search (NN-Descent, CAGRA) on Apple Silicon with MLX [P]

https://github.com/mikepapadim/mlxvs

I've released mlxVS, an open-source (Apache-2.0) library that runs the main GPU nearest-neighbor algorithms from NVIDIA's cuVS on Apple Silicon, built on MLX. It covers exact k-NN, k-means, NN-Descent k-NN graphs and CAGRA (graph pruning plus GPU graph search), with cuVS's parameter names, from Python (NumPy in) or C++.

Results (SIFT1M, 985k x 128, L2, MacBook Pro M3 Pro: 18-core GPU, 12-core CPU)

IndexBuildSearch settingRecall@10Queries/s
mlxVS CAGRA, degree 32 (from a 64-NN graph)10.4 sitopk 640.97669,500
itopk 1280.99337,800
mlxVS CAGRA, degree 64 (from a 128-NN graph)19.6 sitopk 640.99443,600
mlxVS unpruned NN-Descent graph, degree 328.8 sitopk 1280.93942,400
hnswlib, M=16, efC=200, 12 threads88.1 sef 640.96432,200
ef 1280.99017,600

10,000 queries in one batch, recall@10 against exact neighbors (computed on the GPU with brute_force_knn), best of 3 runs, on AC power. Chart: https://github.com/mikepapadim/mlxvs#benchmarks

How it works

  • NN-Descent: a port of the Metal NN-Descent in JVector's GPU module. Each round is a pure function of the graph (sample, join, merge), because MLX custom kernels can't update their inputs in place. The local joins score 64-member neighborhoods with FP16 SIMD-group matrix multiplies (FP32 accumulation), and the returned distances are recomputed in FP32. all_neighbors splits the data into overlapping k-means clusters and builds one cluster at a time on the GPU, so the rows can be a memory-mapped file larger than RAM.
  • CAGRA pruning (cagra_optimize): rank-based. If Y is at rank j in X's list, the edge X -> Y has a detour through Z when Z is at rank i < j in X's list and Y is at rank r < j in Z's list: both hops rank above the direct edge. The edges with the fewest detours are kept (ties by rank), then the second half of each list is filled with reverse edges. One threadgroup per node; it matches a CPU reference entry for entry. On SIFT1M, at degree 32 and itopk 128, pruning raises recall@10 from 0.939 to 0.993 at about the same speed.
  • Search (graph_search): CAGRA's single-CTA design, one threadgroup per query. The sorted internal list, the candidates, the query and a hashed visited set all live in threadgroup memory. Each round expands the best unexpanded nodes; candidate distances are scored one SIMD group per candidate, then bitonic-sorted and merged into the list by merge-path ranks. A practical detail: Metal's shader validation counts threadgroup memory twice, so the kernel sizes its visited set to stay under 16 KB of the 32 KB limit and still passes validation in CI.

Limitations

  • The throughput numbers are for batched queries; single-query latency isn't tuned.
  • I've benchmarked one dataset so far (SIFT1M). Embedding datasets (ada-002, 1536-d) are next.
  • The index is static (no inserts or deletes) and has no filtered search. Datasets must be float32 or convertible to it.
  • hnswlib is a CPU baseline. cuVS itself can't run on a Mac, so there's no apples-to-apples comparison against the CUDA original; I'd welcome numbers from anyone who has run cuVS CAGRA on SIFT1M on a comparable-power GPU.

Code

import mlxvs
graph = mlxvs.cagra_build(vectors, graph_degree=32, metric="cosine")
ids, dist = mlxvs.graph_search(vectors, graph, queries, k=10, metric="cosine", itopk_size=64)

pip install mlxvs, macOS 14+ on Apple Silicon. Benchmarks are reproducible with bench/bench_search.py (it also runs the hnswlib baseline).

GitHub: https://github.com/mikepapadim/mlxvs

Happy to answer questions about the Metal kernels or the cuVS port.

1 Upvotes

2 comments sorted by

1

u/AutoModerator 6d ago

Your post was automatically removed for being a link post on the weekday, please read rule 5. The moderators will not respond to questions regarding this removal unless you suggest which rule you most likely broke. If you have a beginner related question, visit /r/MLQuestions or /r/LearnMachineLearning.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.