usearch: HNSW with the fat trimmed

qdrant’s HNSW is production plumbing; usearch is the algorithm with the fat trimmed — same paper, ~10× less code, essentially all of it in one header. Read it as the reference implementation for YOUR hnsw.rs. The interesting part is the memory layout: one contiguous “tape” per node.

1. The node tape

:2242 class index_gt — the whole index: a vector of node pointers + per-node tapes
:2404 neighbors_ref_t — a view over raw bytes (tape_, :2416): each node’s storage is [level | links-L0 | links-L1 | ... ], counts inline, slots preallocated to connectivity limits

 node tape:  ┌───────┬────────────────┬──────────┬─────┐
             │ level │ L0: cnt + M0×id │ L1: cnt+M×id │ ... │
             └───────┴────────────────┴──────────┴─────┘
             one allocation, all levels adjacent

Compare qdrant (per-level Vec<Vec<_>> in the builder, serialized compressed later) and neo4j’s scattered records (topic 13): usearch picks “everything about a node in one place” — one pointer chase per node visit, then streaming.

#![allow(unused)]
fn main() {
// the tape: level header, then per-level slots preallocated to the
// connectivity limit — neighbors(l) is offset arithmetic, not Vec hops
struct NodeTape<'a> { bytes: &'a [u8] }   // one allocation per node

impl NodeTape<'_> {
    fn neighbors(&self, l: usize, m: usize, m0: usize) -> &[u32] {
        let slot = |links: usize| (1 + links) * 4;       // count + ids
        let start = 2 + if l == 0 { 0 }                  // 2 = level header
                    else { slot(m0) + (l - 1) * slot(m) };
        let cnt = read_u32(self.bytes, start) as usize;
        cast_u32(&self.bytes[start + 4..start + 4 + cnt * 4])
    }   // one miss to reach the tape; the rest prefetches
}
}

2. Defaults = the paper’s advice, frozen

:1563 default_connectivity() = 16 (M)
:1591 connectivity_base = 2 × M (M0) — computed at :1604
:1568 default_expansion_add() = 128 (ef_construction)
:1573 default_expansion_search() = 64 (ef)

3. The three core walks

:3234 search_to_insert_ — Alg 1’s per-level beam during insert; :3239 form_links_to_closest_ (defined :4262) applies the Alg 4 heuristic and back-links (shrinking overfull neighbors)
:3446 search_to_find_in_base_ — Alg 2 on layer 0 with an optional predicate — filtering exists here too, but ONLY as filter-during-traversal (no cardinality planner, no ACORN: compare qdrant’s search.rs:55-84 — that gap IS qdrant’s moat)
:3232, :3354 — the greedy descent loops (level >= 0; --level), including the update path (usearch supports in-place vector updates — rare among HNSW libs)

4. Concurrency

:664-717 striped_locks_gt — insertions take striped per-node locks (~threads × connectivity stripes), not one big lock; searches are lock-free over published tapes. Simpler than qdrant’s RwLock-per-node builder; the cost is update-vs-read races handled by slot versioning in index_dense.hpp.

Questions (answer in notes.md)

Bytes per node for M=16, M0=32, avg 1.06 levels, u32 slots — tape vs qdrant-builder Vec-of-Vecs (count headers, capacity slack, allocator overhead).
Why preallocate link slots to the max instead of growing? What does it cost in memory, and what does it buy under concurrent insert?
Filter-during-traversal with a 1% predicate on usearch: what happens, and which qdrant mechanism was built to fix exactly this?
usearch templates the metric; qdrant enum-dispatches scorers. Map this to topic 11’s compiled-vs-vectorized argument — who wins where?
For YOUR hnsw.rs: steal the tape or use Vec<Vec<u32>> per level? Decide, justify with expected access pattern, and note what M17’s SIMD needs.

References

Papers

Malkov, Yashunin — the HNSW paper (arXiv:1603.09320) — gets its own chapter: reading-hnsw-paper.md

Code

usearch — all of it in include/usearch/index.hpp (+ index_dense.hpp for the type-erased/quantized wrapper); C++ templates, but small enough to hold in your head

Keyboard shortcuts