A vector search engine I wrote from scratch in C++17. It's an HNSW index, the same approximate-nearest-neighbor structure that sits inside most vector databases, built around one idea: at any real scale, the search spends its time waiting on memory, not doing math.
Here's the reasoning. Every step of an HNSW search reads a full vector to compute one distance. At 128 dimensions that's 512 bytes, pulled from a random spot in RAM, and a query does thousands of these. The multiply-add is cheap; the memory read is what costs. So proxima tries to move fewer bytes per step, in two ways:
- It walks the graph using int8 copies of the vectors (a quarter the size) with AVX2 integer instructions, then recomputes the final shortlist in exact float32. A rough distance is good enough to decide which neighbor to step toward; you only need an exact distance to rank the handful of results you actually return. So the returned distances are exact and recall stays at the float level.
reorder()renumbers the nodes so the ones visited together end up next to each other in memory. It doesn't change any results, it just lets queries hit cache more often.
The rest is the standard HNSW from the Malkov & Yashunin paper (TPAMI 2018), written out rather than wrapped, and measured against hnswlib and FAISS on the same data and settings.
New to this? docs/HOW_IT_WORKS.md walks through the whole thing from scratch, with diagrams: what embeddings are, how HNSW works, and what proxima adds on top.
import numpy as np, proxima
index = proxima.Index(dim=128, space="l2", M=16, ef_construction=200)
index.add(np.random.rand(100_000, 128).astype(np.float32))
index.reorder() # optional: faster queries, same results
labels, distances = index.search(queries, k=10, ef=80, mode="sq8")
index.save("vectors.idx")
index = proxima.load("vectors.idx")100,000 vectors of 128 dimensions, 1,000 queries, k=10, M=16, efConstruction=200. Build and search are both single-threaded for every library, and ground truth is exact brute force. Run on an Intel Core Ultra 9 185H, built with MSVC 19.42 /O2 /arch:AVX2 on Windows 11. python bench/bench.py reproduces it.
| index | build (s) | ef=20 | ef=80 | ef=160 | ef=640 | recall ceiling |
|---|---|---|---|---|---|---|
| proxima-sq8 (reorder + int8 traversal + exact re-rank) | 11.5 | 0.834 / 40,402 | 0.993 / 18,090 | 0.999 / 12,049 | 1.000 / 5,621 | 0.9996 |
| proxima (float32) | 11.5 | 0.850 / 24,966 | 0.993 / 10,343 | 0.999 / 7,221 | 1.000 / 3,475 | 0.9996 |
| hnswlib | 13.9 | 0.849 / 20,265 | 0.991 / 8,741 | 0.998 / 6,684 | 1.000 / 3,663 | 0.9996 |
| FAISS HNSWFlat | 16.7 | 0.856 / 19,185 | 0.992 / 7,444 | 0.999 / 4,823 | 1.000 / 1,633 | 0.9996 |
| FAISS HNSWSQ (int8, no re-rank) | 36.1 | 0.796 / 9,383 | 0.899 / 4,381 | 0.902 / 3,156 | 0.902 / 1,335 | 0.9017 |
Each cell is recall@10 / queries-per-second. Full sweep in bench/results/results.md.
A few things to read out of this:
- Above about 0.95 recall, the int8 path is the fastest index here: roughly 1.8× hnswlib and 2.5× FAISS HNSWFlat at 0.999 recall. The reason is the cache. At this size the float vectors are 51 MB and don't fit the 24 MB L3; the int8 codes are 12.8 MB and mostly do.
- The re-rank is the part that matters. FAISS HNSWSQ uses the same 8-bit codes but ranks results straight from them, and its recall stops at 0.902 no matter how long you let it search. proxima walks on the same codes but ranks the final shortlist in float32, so it reaches 0.9996, the same as the float indexes.
- Below ~0.9 recall (ef around 10) the shortlist is too short for the re-rank to fix much, so the plain float path is better there. And this is one synthetic dataset on one laptop. SIFT1M and a 1M-vector run are the obvious next checks, and at that size the cache gap should get wider, not smaller.
- The full HNSW algorithm: random layer assignment (
level = floor(-ln(U) / ln(M))), greedy descent through the upper layers, beam search, and the neighbor-selection heuristic from the paper that keeps long-range links instead of only the nearest ones. Neighbor lists get trimmed with the same rule when a node fills up. - One beam search, templated on the distance function, so the float and int8 paths run the exact same code.
- int8 kernels that widen to int16 and accumulate with
vpmaddwd, using two accumulators to keep the pipeline busy. The codes share one global scale, so integer distances sort the same as real distances and the inner loop stays plain integer math. - AVX2 + FMA float kernels (L2, inner product, cosine) with a scalar fallback when AVX2 isn't compiled in.
- Layer-0 links live in one flat
uint32array with a fixed stride rather than per-node allocations, so a node's neighbors are one offset away. Upper layers are sparse and kept in per-node blocks.reorder()rewrites the whole thing in BFS order. - Visited tracking uses an epoch counter, so resetting it between queries is O(1) instead of clearing an array. Buffers come from a small pool so threaded queries don't collide.
- Binary save/load with a version header. A loaded index gives identical results, with or without a prior
reorder(). - pybind11 bindings: NumPy in and out, the GIL released during build and search, and threaded batch queries.
Needs a C++17 compiler (MSVC, GCC, or Clang) and Python 3.9+.
pip install . # builds the extension via scikit-build-core + CMake
python -m pytest tests/ # Python tests
python bench/bench.py # recall/QPS sweep vs hnswlib + FAISS (pip install .[bench])Native tests without Python:
cmake -B build -DPROXIMA_BUILD_TESTS=ON -DPROXIMA_BUILD_PYTHON=OFF
cmake --build build --config Release && ctest --test-dir build -C ReleaseWhy re-rank instead of just trusting the codes. A small distance error is fine while you're navigating, because the graph routes around it. It's not fine for the final ranking: once two real neighbors are closer to each other than the rounding step, the codes can't tell them apart, and searching longer won't recover it. That's exactly the wall FAISS HNSWSQ hits. Using int8 to navigate and float to rank costs about ef extra float distances per query and removes the wall.
Why one global scale and not per-dimension. With a shared scale, the integer distance between two codes lines up with the real distance, so traversal just compares int32 sums. Per-dimension scales are more accurate but need a float rescale per dimension in the hot loop, which is the conversion cost the int8 path exists to avoid. The re-rank makes up the accuracy difference instead.
Why the neighbor heuristic is worth it. Connecting each new node to its M nearest neighbors sounds right, but it clusters all the edges in one direction and breaks the graph into islands. The paper's heuristic keeps a candidate only if it's closer to the new node than to the neighbors already chosen, which leaves some long-range edges in place. It moved recall more than any amount of ef tuning did.
Writes are single-threaded. Inserts happen one at a time (no per-node locks yet). Queries are read-only and fine to run from several threads once you've stopped adding.
- The int8 path is weaker at low ef, since a short shortlist gives the re-rank little to work with. Use the float path if you're targeting under ~0.9 recall.
- No deletes or in-place updates (same as FAISS
IndexHNSWFlat). - No concurrent inserts yet (hnswlib has them).
- The global int8 scale is sensitive to outliers. Per-dimension codes with a fused re-rank would be the next thing to try.
- AVX2 is picked at compile time; there's no runtime CPU dispatch.
MIT