HNSW

Deep dive

How it works

Parts:

• vector store — the n vectors, one row each
• layer graphs — per node up to M links (2M on layer 0), one graph per level
• level assigner — random level per node, P(level ≥ l) = M^−l
• entry point — top-level node where every search starts
• beam search — best-first search of width ef inside one layer
• neighbour heuristic — keeps links that point in different directions

Operations: insert (below) and search (greedy descent, then beam search of width ef on layer 0).

Insert vector v:

1. Level l = ⌊−ln(U) · mL⌋ with U uniform in (0, 1] and mL = 1/ln M, so P(level ≥ l) = M^−l.
2. From the entry point (top-level node), greedy search (ef = 1) on layers above l to get close to v.
3. On each layer from min(l, top) down to 0: beam search with ef_construction, pick up to M neighbours with the heuristic, link both ways. If a neighbour now exceeds its limit (M, or 2M on layer 0), re-select its links with the same heuristic.
4. If l > top, v becomes the entry point.

Beam search on one layer (ef): candidates = min-heap, results = max-heap of size ef. Pop the nearest candidate; stop if it is farther than the worst result; else add its unvisited neighbours that beat the worst result.

Neighbour heuristic: sort candidates by distance to v; keep c only if c is closer to v than to every already kept neighbour. This keeps links that point in different directions, which keeps clustered data navigable.

layer 2:  A ───────────────────── F             few nodes, long links
layer 1:  A ──── C ────── E ───── F
layer 0:  A─B─C─D─E─F─G─H─...  (2M links each)  all nodes, short links
query: greedy A→F (l2), F→E (l1), beam(ef) from E on l0

Code

use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub struct Hnsw {
    dim: usize, m: usize, ef_construction: usize,
    data: Vec<f32>,             // n × dim, row-major
    links: Vec<Vec<Vec<u32>>>,  // links[node][layer] = neighbour ids
    entry: Option<u32>,
    rng: u64,
}

// Squared L2 is non-negative, so its f32 bit pattern sorts like the value: use u32 keys in heaps.
fn dist(a: &[f32], b: &[f32]) -> u32 {
    a.iter().zip(b).map(|(x, y)| (x - y) * (x - y)).sum::<f32>().to_bits()
}

impl Hnsw {
    pub fn new(dim: usize, m: usize, ef_construction: usize) -> Self {
        Hnsw { dim, m, ef_construction, data: Vec::new(), links: Vec::new(), entry: None, rng: 0x9E3779B97F4A7C15 }
    }
    fn vec(&self, i: u32) -> &[f32] { &self.data[i as usize * self.dim..][..self.dim] }
    fn max_links(&self, layer: usize) -> usize { if layer == 0 { 2 * self.m } else { self.m } }

    /// Best-first search in one layer; returns up to ef (dist, id) pairs sorted ascending.
    fn search_layer(&self, q: &[f32], entry: &[(u32, u32)], ef: usize, layer: usize) -> Vec<(u32, u32)> {
        let mut visited = std::collections::HashSet::new(); // production: epoch-stamped Vec<u32>
        let mut cand: BinaryHeap<Reverse<(u32, u32)>> = BinaryHeap::new(); // nearest first
        let mut best: BinaryHeap<(u32, u32)> = BinaryHeap::new(); // farthest of the best ef on top
        for &e in entry { visited.insert(e.1); cand.push(Reverse(e)); best.push(e); }
        while let Some(Reverse((d, c))) = cand.pop() {
            if d > best.peek().unwrap().0 && best.len() >= ef { break; } // nothing closer is reachable
            for &nb in &self.links[c as usize][layer] {
                if !visited.insert(nb) { continue; }
                let dn = dist(q, self.vec(nb));
                if best.len() < ef || dn < best.peek().unwrap().0 {
                    cand.push(Reverse((dn, nb)));
                    best.push((dn, nb));
                    if best.len() > ef { best.pop(); }
                }
            }
        }
        best.into_sorted_vec()
    }

    /// Heuristic selection: keep a candidate only if it is closer to q than to every kept neighbour.
    fn select(&self, cands: &[(u32, u32)], m: usize) -> Vec<u32> {
        let mut out: Vec<u32> = Vec::with_capacity(m);
        for &(d, c) in cands { // ascending by distance to q
            if out.len() == m { break; }
            if out.iter().all(|&r| dist(self.vec(c), self.vec(r)) > d) { out.push(c); }
        }
        out
    }

    pub fn insert(&mut self, v: &[f32]) -> u32 {
        let id = self.links.len() as u32;
        self.data.extend_from_slice(v);
        self.rng ^= self.rng << 13; self.rng ^= self.rng >> 7; self.rng ^= self.rng << 17;
        let u = ((self.rng >> 11) as f64 + 1.0) / (1u64 << 53) as f64; // (0, 1]
        let level = (-u.ln() / (self.m as f64).ln()) as usize; // P(level >= l) = M^-l
        self.links.push(vec![Vec::new(); level + 1]);
        let Some(ep) = self.entry else { self.entry = Some(id); return id; };
        let top = self.links[ep as usize].len() - 1;
        let mut eps = vec![(dist(v, self.vec(ep)), ep)];
        for layer in (level + 1..=top).rev() { eps = self.search_layer(v, &eps, 1, layer); } // greedy descent
        for layer in (0..=level.min(top)).rev() {
            eps = self.search_layer(v, &eps, self.ef_construction, layer);
            let nbrs = self.select(&eps, self.m);
            for &nb in &nbrs {
                self.links[nb as usize][layer].push(id); // bidirectional link
                if self.links[nb as usize][layer].len() > self.max_links(layer) { // shrink with the same heuristic
                    let mut c: Vec<(u32, u32)> = self.links[nb as usize][layer].iter()
                        .map(|&x| (dist(self.vec(nb), self.vec(x)), x)).collect();
                    c.sort_unstable();
                    self.links[nb as usize][layer] = self.select(&c, self.max_links(layer));
                }
            }
            self.links[id as usize][layer] = nbrs;
        }
        if level > top { self.entry = Some(id); }
        id
    }

    /// Approximate k nearest neighbours: (squared distance, id), nearest first. ef >= k.
    pub fn search(&self, q: &[f32], k: usize, ef: usize) -> Vec<(f32, u32)> {
        let Some(ep) = self.entry else { return Vec::new() };
        let mut eps = vec![(dist(q, self.vec(ep)), ep)];
        for layer in (1..self.links[ep as usize].len()).rev() { eps = self.search_layer(q, &eps, 1, layer); }
        let res = self.search_layer(q, &eps, ef.max(k), 0);
        res.into_iter().take(k).map(|(d, i)| (f32::from_bits(d), i)).collect()
    }
}

Complexity and constants

Measured with the code above (M = 16, ef_construction = 200, one Apple M-series core, queries are dataset points plus small noise):

• Distance computations per query: order of ef × M × (a few) on layer 0. For 768-dim float vectors each is about 3 KB of memory traffic, so queries are memory-latency bound: one random cache miss per neighbour.
• Memory: 4·dim bytes per vector (3 KB at 768-dim) dominates the about 128-256 B of links. With 10^8 vectors at 768-dim that is about 300 GB, which is why big deployments quantize (int8, PQ) or move to disk.
• Average layer-0 degree after build: 18-23 here (limit 2M = 32).

Efficiency

• Cost: measured with the code above (M = 16, ef_construction = 200, one Apple M-series core, 32-dim): 78-136 µs per insert; a query takes 12 µs at recall@10 0.94 (ef 10) and 79 µs at 0.999 (ef 100) on 20k uniform vectors. Memory: 4·dim bytes per vector (3 KB at 768-dim) plus about 128-256 B of links. Bound: memory latency, one random cache miss per visited neighbour, then bandwidth for long vectors.
• Levers:
  • ef at query time — trades recall for latency, 12 µs → 79 µs for 0.94 → 0.999 (measured above) — every deployment, tune per recall target
  • epoch-stamped visited array instead of a hash set — the HashSet is a large share of query time here (measured) — all implementations
  • flat layer-0 link array and neighbour prefetch — avoids pointer chasing (hnswlib layout) — vectors beyond cache
  • int8 or PQ distances plus full-precision re-rank of the top candidates — cuts memory traffic and RAM (order of 4×+) — 10^7+ vectors, high dimension
  • SIMD FMA distances (AVX2/AVX-512/NEON) — more distances per cycle — compute-bound low-dimension cases
• Naive → standard → state of the art:
  • brute-force scan · O(n·dim) per query, exact, fine to 10^4-10^5 vectors
  • HNSW with float vectors · tens of µs per query at 0.94-0.99 recall (measured above)
  • HNSW over quantized vectors with re-ranking, or IVF-PQ / DiskANN beyond RAM · 10-50× less memory (IVF-PQ, order of)

Implementation notes

• Visited set: use a reusable Vec<u32> of epoch stamps (bump the epoch per query) instead of a hash set; the HashSet above is a large share of query time.
• Flat layer 0: store layer-0 links in one array with fixed 2M + 1 slots per node (count + ids), next to or indexed like the vectors (as hnswlib does) to avoid pointer chasing.
• Prefetch the vectors of all neighbours of the popped candidate before computing distances.
• SIMD distances: dot product or L2 with AVX2/AVX-512/NEON FMA. Normalize vectors and use the inner product for cosine similarity.
• Parameters: M = 16 (hnswlib, Lucene, pgvector defaults) and 32-64 for high-dimensional or high-recall needs; ef_construction 100-400; ef_search ≥ k, tuned per recall target.
• Concurrent inserts: per-node locks on link lists, plus a global lock only when the entry point changes.
• Quantized vectors: traverse with int8 or PQ distances, then re-rank the top candidates with full precision.
• Deletes: mark deleted, keep traversing through them, exclude them from results; rebuild or repair neighbours when the tombstone share grows (order of 10-20 %).

Pitfalls

• Recall measured on queries drawn from the dataset overstates real recall; use held-out queries with ground truth from brute force.
• ef < k silently returns fewer or worse results; enforce ef ≥ k.
• Inserting data sorted by cluster (all of cluster 1, then cluster 2) builds worse graphs than shuffled input.
• Restrictive filters applied after search return fewer than k hits; you need filter-aware traversal or a brute-force fallback.
• The memory estimate forgets upper layers and allocator overhead: plan about 1.1-1.5× of vectors plus layer-0 links.
• Distance type mismatch: an index built with L2 but queried as cosine on unnormalized vectors.

Variants and alternatives

In production

Libraries: hnswlib (defaults M = 16, ef_construction = 200), FAISS IndexHNSWFlat, Lucene/Elasticsearch/OpenSearch dense vector fields (default maxConn 16, beamWidth 100), pgvector HNSW index (m = 16, ef_construction = 64, hnsw.ef_search = 40), Qdrant, Weaviate, Milvus, Redis vector search. Fields: relational databases (pgvector), search engines (Lucene family), ML retrieval and RAG stacks (the vector stores above).

Implementations

Sources

• Y. A. Malkov, D. A. Yashunin, Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs, IEEE TPAMI, 2020 (arXiv:1603.09320, 2016). paper · arXiv · code
• S. J. Subramanya, F. Devvrit, R. Kadekodi, R. Krishnaswamy, H. V. Simhadri, DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NeurIPS, 2019. paper
• C. Fu, C. Xiang, C. Wang, D. Cai, Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph, VLDB, 2019. paper · arXiv
• M. Aumüller, E. Bernhardsson, A. Faithfull, ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms, Information Systems, 2020. paper · code