What does a minimal, correct HNSW implementation look like?

A minimal, correct HNSW implementation looks much smaller and plainer than the phrase “vector search engine” might suggest: a handful of operations, a simple per-node neighbor list, a couple of standard queue data structures, and a random-number-driven level assignment step, all of it verifiable by comparing its output against a brute-force search over the same small dataset before worrying about any performance optimization at all.

What’s the minimum set of operations a working implementation needs to expose?

At its core, an implementation needs to support inserting a new vector, searching for the nearest neighbors to a query vector, and computing the distance between two vectors according to whichever metric has been chosen — everything else in a full-featured system is built on top of these three operations. Saving the built graph to disk and loading it back are also worth including early rather than as an afterthought, since even a small test implementation benefits from not having to rebuild the graph from scratch every time it’s used, and getting persistence right from the start avoids having to retrofit it into a data structure that wasn’t designed with it in mind.

Why does node identity need two different ID systems?

Real applications identify their data with whatever labels are meaningful to them — database row IDs, document names, or arbitrary external keys — but the graph itself is easier to implement efficiently using small, dense, sequential internal indices that can be used directly as array positions rather than dictionary keys. Keeping these two identity systems separate from the start, with a simple lookup table translating between a caller’s external label and the graph’s internal index, avoids a messy retrofit later and mirrors how essentially every production implementation of this kind of structure is actually built.

What’s the simplest correct way to represent the graph itself?

Each node needs a neighbor list per layer it participates in, and the simplest correct representation is exactly that: for every layer a node belongs to, a plain list of the internal indices of its connected neighbors in that layer. This is deliberately unoptimized — a production implementation cares a great deal about how compactly and contiguously these lists are packed in memory, which is a performance question covered separately, but a first implementation should prioritize being obviously correct over being fast. The same advice applies to distance calculation: implement the straightforward version of whichever distance function is being used first, get correct results with it, and only then consider faster approximations or hardware-specific optimizations once correctness is established as a baseline to measure against.

How do you know a minimal implementation is actually correct?

The most reliable check is the one available from day one: build a tiny index, run a handful of searches against it, and compare the results directly against a brute-force search over the same small dataset using the same distance function. Because a small dataset makes exact search cheap and fast, this comparison can be run automatically as a unit test after every change, catching correctness regressions immediately rather than discovering them later through mysteriously degraded recall on a much larger dataset where the root cause is far harder to isolate. It’s also worth instrumenting a first implementation to count how many distance calculations, node visits, and queue operations a given search actually performs — not because these numbers matter yet for performance, but because watching them change as parameters change builds real intuition for what the algorithm is actually doing that reading a description of it cannot fully provide.

Once a version like this is working and verified, the next page moves from correctness to performance, looking at the memory layout decisions that separate a minimal implementation from one capable of handling large, real-world datasets efficiently. Anyone building this for the first time should genuinely write the small, unoptimized version described here before reading further — the performance-oriented material that follows will make substantially more sense once its baseline has been felt firsthand rather than only read about.