Malkov & Yashunin (2018) — HNSW, and the part that breaks in production

[akash-coded]

Reading Club. One paper per thread. The house position: replicate, do not cite.
A paper we can re-run against this corpus is worth far more argued about with numbers.

Paper: arXiv:1603.09320

The claim, in one paragraph

Hierarchical navigable small world graphs: a layered proximity graph where greedy search is
roughly logarithmic. It is the default ANN index in most vector stores.

The claim rests on navigability — long-range links at scale-separated distances, so the search
takes big steps while far away and small ones when close. Take those away and greedy search walks
into the nearest basin and cannot leave.

How we would test it here

Issue #2 is this paper's failure mode, measured: a pure 16-NN graph with no
long-range links, where recall@20 = 0.00 at ef=64 on 2,430 chunks.
L11-adjacent
has the derivation. notebooks/04 §4.6 plots the collapse.

Two or three things to argue about

1. Recall that degrades gracefully with ef means the visit budget is too small. Recall pinned at zero regardless of ef means the graph is disconnected. Is that diagnostic in the paper, or did we have to find it?
2. The paper does not benchmark under metadata filtering. Almost no ANN paper does, and every production system filters. Pre-filtering deletes nodes and can disconnect the answer's region. Is this a gap in the literature or in how we read it?
3. This repo's fix uses uniformly sampled long-range links, not Kleinberg's d^-r sampling. It works at n=2,430 and would not at n=10⁶. Where exactly does uniform stop being enough?

---

If you have run any part of this, post the numbers — a replication with an interval outranks
every opinion in the thread, including mine.