Brute-force, IVF, and HNSW nearest-neighbor indexes implemented in C++ - not wrapped around FAISS or any existing library - and benchmarked against a brute-force oracle at dataset sizes up to 1,000,000 vectors.
That's the part worth reading. Widening the query-time search should have helped. It didn't - which meant the bug wasn't where I was looking. The real story, below, is how I found where it actually was.
So - what did I actually build?
Imagine a library with a million books and no catalog. Finding the book most similar to the one in your hand means walking every aisle and comparing each one by hand - that's brute-force search, and it's exactly correct, just slow.
Now imagine two smarter librarians. One (IVF) groups books into labeled sections first, so you only search the one or two sections most likely to have your match. The other (HNSW) builds a map with a few long highways between distant shelves and many short local paths near each shelf - so you jump close fast, then walk the last few steps. Both trade a small chance of missing the true best match for being far faster. I built all three, from scratch, and measured exactly how much accuracy each one trades away.
First - the problem this actually solves.
Every vector database exists because of one uncomfortable fact: finding the truly closest match means checking everything, unless you're willing to accept "probably the closest."
Say you have 1,000,000 stored vectors, each with 128 numbers. A single query means computing a similarity score against all 1,000,000 of them - that's 128 million multiplications, just to answer one question. Do that 1,000 times a second and you're at over a hundred billion operations per second, on a single core. This is exactly why brute force tops out around a few thousand queries per second even on fast hardware, and why every real vector database uses an approximate index instead.
So I built three different answers to it.
Every index type - exact and approximate - implements the same insert / search / remove contract, so the benchmark harness can swap between them without any special-casing.
Linear scan against every stored vector, keeping the top-k in a bounded max-heap. Not fast - it exists to be unquestionably correct, so every approximate index in this project can be measured against it, not just trusted.
Query a 3-vector dataset for the nearest match: compute the distance to vector A, to B, to C - done, the answer is exact by construction. At 1,000,000 vectors, the logic is identical; only the wait gets longer.
K-means clustering partitions the vector space into nlist groups ahead of time. At query time, only the nprobe closest groups get searched - the rest are skipped entirely.
With 1,000 clusters and nprobe = 8, a query only searches 0.8% of the dataset. Measured in this project: recall climbed cleanly from 17% at nprobe=1 to a perfect 100% once nprobe = nlist - at which point searching "a few clusters" becomes searching all of them, which is mathematically identical to brute force. That clean convergence is the proof the clustering logic is actually correct, not just fast.
A multi-layer graph (Fig. 1, above). Sparse top layers take long hops across the vector space; the dense bottom layer refines to true neighbors. Search is greedy and sub-linear - O(log N) rather than O(N) - which is the entire reason production vector databases use it.
Every new vector is randomly assigned a "top layer" using an exponentially decaying probability - most vectors only ever exist at the bottom layer, a rare few reach the top. That randomness is what keeps the graph balanced without any explicit rebalancing step, similar to how a skip list avoids needing rotation like a balanced tree does.
But building three indexes means nothing if I can't prove which one's actually right.
A number without a definition is just a vibe. Here's the exact meaning behind every recall figure on this page.
Suppose the true 10 nearest neighbors to a query - found by exhaustively checking every vector - are labeled A through J. If the approximate index (IVF or HNSW) returns 6 of those 10 in its own top-10, that query scores recall@10 = 60%. Average that across many queries, and you get the recall numbers reported throughout this page - always measured against a full brute-force oracle over the entire dataset, never a subsample standing in for it.
Which brings us back to the 28%. Here's exactly what happened, in order.
A dedicated stress test against the brute-force oracle (5,000 vectors) confirmed the HNSW and IVF logic itself was sound before touching scale or tuning.
~99% recall@10 at 5K-20K vectorsThe same parameters that worked at 20K vectors (M=16, efConstruction=100) produced far worse results once the dataset reached full scale.
full_oracle_recall_at_10 = 0.283Swept ef_search from 64 → 512 - an 8x wider query-time search. Recall barely moved, while throughput dropped 3x. If widening the search doesn't help, the graph itself is missing the right edges.
At 1M vectors, the same construction budget (M, efConstruction) that worked at 20K spreads far too thin - the graph is built with too few, too shallow connections to reach true neighbors at all.
Rebuilt with M=32, efConstruction=200. Recall improved substantially, confirming the diagnosis - at a real, measured cost in build time.
0.283 → 0.552 recall@10, 15 min → 74 min buildRecall still plateaus under further ef_search increases at the new setting too - pointing at the neighbor-selection heuristic during graph construction as the next thing to inspect, not just more parameter scaling.
Here's that same finding, on a graph instead of in words.
Every point below is a real benchmark run at 1,000,000 vectors, 128 dimensions - not interpolated. Widening ef_search moves you along a curve; changing M/efConstruction moves the whole curve.
Read this chart as two separate curves, not one line: within each curve, ef_search trades throughput for recall. Between the curves, better graph construction shifts the entire tradeoff upward - the actual fix that mattered.
| Configuration | Recall@10 | QPS | Build time |
|---|---|---|---|
| M=16, efConstruction=100 | 28.3% | 3,525 | ~15 min |
| M=32, efConstruction=200 | 55.2% | 895-2,416 | ~74 min |
Recall measured against a full brute-force oracle over the entire 1M-vector corpus - not a subsample. QPS and recall are reported together deliberately: either number alone is meaningless without the other.
No cherry-picking - this is the unedited console output from the actual run, so anyone can check the numbers above against the source.
Now, the honest part.
Infrastructure projects earn trust by being precise about their own edges - here's the honest boundary of this one, today.