A from-scratch HNSW vector-search engine in modern C++ with Python bindings.
Approximate-nearest-neighbor search — the thing that makes semantic search and RAG fast — implemented from first principles: the layered proximity graph, the best-first traversal, and the neighbor-selection heuristic that most naive versions get wrong. No faiss, no hnswlib in the core. Benchmarked honestly against hnswlib on the same data.
Fashion-MNIST (60k × 784, L2), recall@10 vs single-query throughput, Proxima vs hnswlib at the same
M=16 / efConstruction=200. Proxima reproduces hnswlib's recall at every ef while sustaining ~2×
the single-query throughput on this machine (Apple M-series, NEON). This is single-query latency,
where Proxima is strong; hnswlib pulls ahead with batched, multi-threaded queries — see
Benchmarks for the honest caveats.
pip install proxima # from a wheel; builds from source via CMake + pybind11 otherwiseimport numpy as np
import proxima
vectors = np.random.rand(100_000, 128).astype(np.float32)
index = proxima.HNSW(dim=128, metric="l2", M=16, ef_construction=200)
index.add(vectors) # build the graph
index.set_ef(64) # query-time recall/speed knob
q = np.random.rand(128).astype(np.float32)
ids, dists = index.query(q, k=10) # ids: (10,), dists: (10,)
index.save("index.prox")
index2 = proxima.HNSW.load("index.prox")Metrics: "l2" (squared Euclidean), "ip" (inner product), "cosine" (normalized inner product).
Inputs must be C-contiguous float32; bad shapes/dtypes raise a clear proxima.ProximaError.
HNSW (Hierarchical Navigable Small World) builds a multi-layer proximity graph. Layer 0 holds every vector; each higher layer holds an exponentially thinning random subset. The sparse upper layers act as express lanes — a query greedily hops through them to land near the right region, then does a fine-grained best-first search in the dense base layer.
layer 2 (o)---------------------(o) few long-range hubs
| |
layer 1 (o)------(o)------------(o)----(o) more nodes
| | | |
layer 0 (o)-(o)-(o)-(o)-(o)-(o)-(o)-(o)-(o)-(o) every vector, densely linked
Three pieces have to be right, and the third is the one that separates a real implementation from a toy:
- Layer assignment — a new node's top level is
floor(-ln(U) · mL),mL = 1/ln(M). Most nodes stay on layer 0; a few reach high layers and become long-range hubs. search_layer— best-first traversal with a candidate min-heap, a bounded result max-heap, and an epoch-based visited set; the core of both build and query.- The neighbor-selection heuristic (Malkov & Yashunin, Algorithm 4) — this is the differentiator.
When linking a new node, the tempting choice is to connect it to its M nearest neighbors. That
produces clustered, redundant edges all pointing the same direction, and recall plateaus well below
what HNSW can do.
Instead, iterate candidates nearest-first and keep a candidate e only if it is closer to the
query than to any neighbor already selected:
keep e ⇔ dist(e, q) ≤ dist(e, r) for every already-kept r
This prunes edges that bunch up in one direction and preserves long-range links, which is exactly
what gives the graph its navigability. Proxima implements this as a clearly named, separately-tested
function (hnsw_neighbors.hpp); the test
test_heuristic.cpp constructs a case where the heuristic provably
drops a redundant clustered edge that naive top-M would keep.
The second subtlety: after adding a bidirectional edge, a neighbor's degree can exceed the layer cap
(Mmax0 = 2M at layer 0, M above), so it is re-pruned with the same heuristic. Skipping that step
quietly wrecks recall and memory.
Method (ann-benchmarks convention): build both libraries on the same data with the same
M/efConstruction, sweep efSearch, and for each point measure single-threaded QPS (warm cache,
best of 3) and recall@10 against exact ground truth. Reproduce with:
pip install -e ".[bench]"
python bench/run_bench.py --dataset synthetic # fast, no download
python bench/run_bench.py --dataset fashion-mnist-784-euclidean # standard dataset
python bench/plot.py bench/results/<name>.csvWhat the plots show. Proxima's recall curve lands directly on hnswlib's — the from-scratch graph
is algorithmically faithful. On Fashion-MNIST (60k × 784) at matched ef, recall is neck-and-neck
(e.g. ef=40: Proxima 0.9975 vs hnswlib 0.9946) while Proxima sustains roughly 2× the single-query
throughput on this Apple Silicon machine (ef=40: ~6,200 vs ~2,800 QPS). The synthetic 50k × 128 run
(plot) shows the same shape.
The honest caveats (the point of an honest benchmark):
- This measures single-query latency, one vector at a time — a real serving pattern, and the one where Proxima looks best. hnswlib is heavily optimized for batched, multi-threaded queries; Proxima v1 is single-threaded per query by design, so hnswlib will pull ahead once you batch and thread. That is a deliberate v1 scope choice, not an algorithmic gap. Don't read these plots as "Proxima is faster than hnswlib" in general — read them as "the from-scratch graph is competitive."
- Numbers are machine-, dataset-, and build-flag-specific (here: Apple M-series, NEON, single
thread). Fashion-MNIST is a standard ann-benchmarks dataset with exact ground truth;
syntheticis committed for reproducibility without a download. The harness also pulls SIFT-1M and GloVe-100. - Recall is the apples-to-apples correctness axis (the curves overlap); QPS depends heavily on the threading model and hardware, so treat the throughput gap as machine-specific, not universal.
Every claim here is a measured before/after, not a vibe.
- SIMD distance kernels. The inner loop is the distance function. Hand-written NEON (AArch64) and
AVX2+FMA (x86) kernels are selected at runtime by CPU capability, with a scalar fallback. On
20k×128 L2 queries (
ef=64), switching scalar→NEON took single-query throughput from 7,140 to 19,400 QPS — 2.7×. (PROXIMA_FORCE_SCALAR=1reproduces the scalar path for A/B.) - Contiguous memory. All vectors live in one flat
float32buffer indexed by offset; cache locality dominates ANN performance. - Epoch-based visited list. A versioned tag array gives O(1) membership and O(1) amortized reset — no per-query hash-set allocation — pooled across queries for thread-safe, allocation-free search.
| Call | Description |
|---|---|
HNSW(dim, metric="l2", M=16, ef_construction=200, seed=…) |
Construct an index. |
.add(vectors) |
Add (n, dim) or (dim,) float32 vectors. |
.set_ef(ef) / .ef |
Query-time candidate-list size (recall/speed knob). |
.query(queries, k=10) |
Returns (ids int64, distances float32), shape (k,) or (m, k). |
.save(path) / HNSW.load(path) |
Persist / restore to a single binary file. |
len(index), .dim, .metric, .M, .ef_construction |
Introspection. |
proxima.FlatIndex(dim, metric) |
Exact brute-force baseline (same add/query API). |
proxima.backend() |
Active distance backend: "neon", "avx2", or "scalar". |
The GIL is released around add, query, and I/O; a fully-built index is safe to query from
multiple threads.
#include "proxima/hnsw_index.hpp"
proxima::HnswIndex index({.dim = 128, .metric = proxima::Metric::L2, .M = 16, .efConstruction = 200});
index.add(vec_ptr); // one vector
index.setEf(64);
std::vector<uint32_t> ids(10);
std::vector<float> dists(10);
index.query(query_ptr, 10, ids.data(), dists.data());
index.save("index.prox");
auto loaded = proxima::HnswIndex::load("index.prox");Deliberately out of scope for v1 — listed because knowing why is the point:
- Deletion / updates. Genuinely hard: removing a node orphans its in-edges and can disconnect the hierarchy, especially if it is a hub or the entry point. The planned approach is tombstone + lazy-skip in search with periodic rebuild. Proxima's id↔offset indirection and single-writer build discipline are already shaped to make this additive.
- Parallel build. v1 build is single-threaded. The pieces are in place (per-search visited lists from a pool, isolated graph mutations) to add a thread-pool build with fine-grained locks.
- Metadata filtering, quantization (PQ / scalar), disk-resident indexes. All v2+.
python -m venv .venv && . .venv/bin/activate
pip install scikit-build-core pybind11 numpy pytest
pip install -e . # editable install
./scripts/test.sh # C++ tests (Catch2)
./scripts/sanitize.sh # ASan + UBSan
python -m pytest tests/python # Python testsRequires CMake ≥ 3.24 and a C++17 compiler. The core builds warnings-as-error
(-Werror -Wconversion) and runs clean under AddressSanitizer + UndefinedBehaviorSanitizer.
Yu. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE TPAMI, 2018. arXiv:1603.09320.
MIT — see LICENSE.