Why architecture matters here
Exact nearest-neighbor search in high dimensions offers no free lunch: with 768-dimensional embeddings, space-partitioning trees (KD, ball trees) degrade to near-linear scans because every partition boundary is close to every point. A brute-force scan of ten million float32 vectors touches 30 GB per query. The field's answer is approximate NN — accept 95-99% recall in exchange for orders-of-magnitude speedups — and the architecture you pick determines which trade-offs you can even express. HNSW's particular deal: excellent recall-latency curves, fully incremental inserts, no training phase — paid for in memory, because the graph lives in RAM alongside the raw vectors.
Why a graph at all? Because proximity graphs turn search into local decisions. If every node's edges point at well-chosen near neighbors, then 'move to whichever neighbor is closest to the query' makes monotone progress — no global coordination, no partition boundaries to straddle, and the data structure itself encodes the geometry that trees fail to capture in high dimensions. The catch is that a graph of only short edges makes routing crawl: from a random start, you need many hops to cross the space. Small-world theory supplies the fix — a few long-range links collapse the graph's diameter — and HNSW's hierarchy is a principled way to get them: upper layers are the long-range links, organized so that routing distance shrinks geometrically per layer, giving O(log N) hops overall.
The architecture also decides operational shape. Because HNSW is incremental, it fits streaming ingest (new documents searchable in milliseconds) where clustering-based indexes like IVF need periodic retraining as distributions drift. Because it is RAM-resident and pointer-chasing, it fits latency-critical serving and fights with memory budgets — which is exactly the trade the deep-dive's operational sections are about managing.
The architecture: every piece explained
Layers, top of diagram. Every vector is a node in layer 0; with probability roughly 1/2^L (controlled by a normalization constant mL ≈ 1/ln(M)) it also appears in layers up to L, drawn once at insert time from a geometric distribution. A ten-million-vector index might have four or five layers with only a handful of nodes at the top. The highest-layer node serves as the global entry point. Upper layers exist purely for routing — they are the skip-list express lanes; all real answers live in layer 0.
Edges. Each node keeps up to M links per upper layer and M0 = 2M at layer 0 — M between 12 and 48 covers most workloads. Crucially, neighbors are chosen by the diversity heuristic, not simply the M nearest: a candidate is kept only if it is closer to the node than to any already-selected neighbor. This spreads edges across directions rather than letting them clump in one dense cluster, which is what keeps greedy routing from getting walled in — skip this heuristic (as naive reimplementations do) and recall quietly collapses on clustered data.
Search machinery, right column. In upper layers the search is pure greedy descent with beam width 1: from the entry point, move to any neighbor closer to the query; when no neighbor improves, drop a layer. At layer 0 it widens into a beam search governed by efSearch: a min-heap of candidates to expand, a bounded max-heap of the best ef results found, and a visited set to avoid re-expansion. The loop pops the closest unexpanded candidate, scores its neighbors, and terminates when the nearest candidate is farther than the worst of the current best — a natural stopping rule that makes efSearch a direct recall/latency dial. Bottom row: inserts run the same search to find their neighborhoods, heuristic pruning keeps degree bounds by re-selecting diverse neighbors when a node overflows, and filters/deletes bolt predicate checks and tombstones onto the traversal — workably, with caveats the failure-modes section covers.
End-to-end flow
Query. A 768-d query vector arrives with k=10, efSearch=100. Enter at the top layer's entry point — one node, maybe three edges. Greedy hops: two moves at layer 3, four at layer 2, six at layer 1 — perhaps a dozen distance computations total to cross ten million vectors' worth of space and land inside the query's region. At layer 0 the beam opens: seed the candidate heap with the arrival node, expand the closest candidate, score its ~32 neighbors against the query (SIMD-accelerated inner products dominate the runtime here), push improvements into the result heap, repeat. After a few hundred expansions the termination condition fires; the result heap's top 10 go back to the caller. Total: a few thousand distance computations, sub-millisecond to a few milliseconds depending on dimension and hardware — versus ten million for exact scan, at ~97% recall.
Insert. A new vector draws level L=1 from the geometric distribution. Descend greedily from the entry point to layer 1, then run an efConstruction-wide beam search (typically 100-400) at each layer from L down to 0 to collect candidate neighborhoods. At each layer, the diversity heuristic selects up to M links; edges are bidirectional, so each new neighbor also gains a link back — and any neighbor now over its degree cap re-runs selection over its edge set, possibly dropping an old link. The insert is searchable immediately; no rebuild, no training. Had the draw produced a level above the current maximum, the new node would simply become the global entry point.
Filtered query. The same search with a predicate — lang=de, say — checks the filter before admitting a node into the result heap but (in the standard approach) still traverses non-matching nodes, because routing through them is what keeps the graph connected for the search. With a 1% selective filter this means most expansions yield nothing; engines mitigate with pre-filtered candidate generation below a selectivity threshold, or filter-aware edge selection (as in Vamana/Filtered-DiskANN lineages).