HNSW from scratch, benchmarked against FAISS: brute force still wins at 5,183 documents. [P]

I built a retrieval engine with no retrieval libraries in the core — BM25 over a hand-rolled inverted index, HNSW from the Malkov & Yashunin paper, RRF to fuse them — mainly to understand HNSW rather than treat it as a black box inside a vector DB. FAISS, bm25s and rank_bm25 appear only on the other side of the benchmark.

The result I didn't expect. Median latency per query:

My HNSW loses to my own brute force by 10.9× and 18.3×. Some of that is pure-Python graph traversal, which is genuinely slow. The part that isn't about Python: on SciFact FAISS's flat index beats its own HNSW by 1.36×, and on NFCorpus HNSW's run-to-run spread (0.023 ms) exceeds the gap between the two systems' means (0.019 ms), with p95 at 0.207 against 0.209. The graph also costs 500× more to build than the flat index it's meant to accelerate — 0.93 s against 0.0017 s.

All four systems retrieve at the same quality: nDCG@10 between 0.3159 and 0.3162 on NFCorpus, and 0.6451 for every one of them on SciFact.

Why brute force wins here. Exact search over 3,633 docs at 384 dims is a single dense matmul — 1.4M multiply-adds, which BLAS does without noticing. HNSW replaces that with pointer chasing, per-node distance computations and a priority queue, none of it vectorized, paying interpreter overhead per hop in Python and cache misses in C++. The graph wins when the linear scan is long enough that skipping most of it beats navigating. At a few thousand documents it isn't.

Validation, because a perf finding from unchecked code is worth nothing. Dense retrieval with MiniLM-L6-v2 reproduces published BEIR baselines (0.3159 vs ~0.314 on NFCorpus, 0.6451 vs ~0.645 on SciFact). Paired bootstrap against FAISS over 323 queries, BH-corrected across 36 pairs: mini-brute vs faiss-flat d = +0.0000, p = 1.00; mini-hnsw vs faiss-flat d = +0.0002, p = 0.68. Indistinguishable, which is the correct outcome for a reimplementation — nobody should be pleased when their from-scratch version wins.

My BM25 lands 0.019 below published on NFCorpus. I attribute that to tokenization (no stemming, no stopword list), on the evidence that all three BM25 implementations I tested agree within 0.0036 while all three sit below the published figure. That localizes the gap without sizing it; I haven't built the stemmed variant.

ANN recall against exact, sweeping efSearch on NFCorpus: mine goes 0.9034 / 0.9548 / 0.9811 / 0.9954 / 0.9975 at ef = 16/32/64/128/256, FAISS 0.8755 / 0.9430 / 0.9740 / 0.9904 / 0.9985. Both converge cleanly.

The number that dwarfs all of this. Query embedding on NFCorpus is 25.8 ms against 0.295 ms for the exact search it feeds. The encoder is 87× the retrieval step. Every argument here about index structure is happening two orders of magnitude below the noise floor of the thing that runs immediately before it.

The only significant quality gain in the whole project was RRF fusion of BM25 and dense: 0.3423 vs 0.3162 best-single on NFCorpus, 0.6969 vs 0.6644 on SciFact (d = +0.0264, p = 0.0045 and d = +0.0518, p = 0.0009 against faiss-flat). Two mediocre rankers disagreeing productively beat either alone, and the fusion costs 7.36 μs. Everything expensive turned out indistinguishable from its reference implementation; the cheap thing was the win.

Limitations, stated plainly. Two datasets, one machine, one embedding model — the corpus-size claim rests on two points and the shape of an argument. No significance test on latency: quality comparisons are bootstrapped, timing ones are medians with spread reported. The expensive HNSW builds are single samples (270.0 s, 95.4 s and 216.0 s for the same config across three runs, and I can't explain the spread), so build-cost ratios are good to within ~2×. Everything is single-threaded, which should widen the gap in brute force's favour since BLAS scales with cores and graph traversal doesn't — I haven't measured it, so I'm not claiming it.

I don't know where the crossover is. The gap moved further in brute force's favour on the larger corpus, which is obviously not the asymptotic behaviour since ANN indexes exist and work, and the two corpora differ in more than size. So that widening is an observation about these two datasets, not a trend. The claim I'll defend is narrow: the flip hasn't happened by 5,183 documents, and a lot of production vector stores are smaller than that.

Code and reproduction steps: https://github.com/sankalp021/mini-search

Full writeup: https://snklp.dev/blog/hnsw-vs-brute-force

Two things I'd like input on. Whether anyone has measured the crossover properly across a size sweep on fixed data. And my layer-0 link budget deviates from Algorithm 1, tuned against clustered distributions — my A/B between the two budgets only exists on synthetic uniform vectors, so I can't connect the deviation to the low-ef recall margin I see on BEIR.