An HNSW vector search index, written from scratch in Java with no runtime dependencies — graph, distance kernels, filtering, HTTP API and visualiser.
Almost every backend engineer has used a vector database. This is the inside of one: the layered navigable graph, the neighbour-selection heuristic that makes it work, SIMD distance kernels, and a benchmark that reports what the approximation actually costs.
The hierarchy, drawn as it actually is. L3 has 2 nodes, L2 has 13, L1 has 95, L0 has all 600 — the geometric thinning that makes search logarithmic. Blue dashed lines are the query dropping a layer: the node one walk ends on is the node the next walk starts from. Orange is a distance actually computed, green is a result.
Press Play to watch it fall through the stack, or click any layer to search from that point. The trace comes from the engine — nothing here re-implements HNSW in JavaScript.
100,000 vectors × 128 dimensions, clustered. Apple M4, single-threaded, Java 25.
Reproduce with make bench.
| efSearch | recall@10 | QPS | p50 | p95 | p99 |
|---|---|---|---|---|---|
| 10 | 0.8494 | 47,268 | 21 µs | 28 µs | 40 µs |
| 32 | 0.9794 | 25,771 | 39 µs | 49 µs | 83 µs |
| 64 | 0.9940 | 18,050 | 55 µs | 73 µs | 120 µs |
| 128 | 0.9968 | 12,967 | 76 µs | 103 µs | 177 µs |
| 512 | 0.9998 | 5,677 | 172 µs | 225 µs | 341 µs |
| brute force | 1.0000 | 895 | 1,067 µs | 1,343 µs | 1,457 µs |
20× faster than exact search while finding 99.4% of the true neighbours — and efSearch
moves along that curve without rebuilding anything.
Choosing a node's neighbours by keeping the m nearest candidates is the intuitive rule, and
it is catastrophically wrong on clustered data:
| selection | recall@10 | QPS | build |
|---|---|---|---|
nearest m |
0.1813 | 81,358 | 2.2 s |
| heuristic (paper, Alg. 4) | 0.8576 | 33,455 | 7.2 s |
A 4.7× difference in recall from one rule. The naive graph is faster precisely because it is broken — every link points inside the node's own cluster, nothing joins the clusters, and a greedy walk terminates early having never left the clump it started in.
The heuristic keeps a candidate only if it is closer to the node than to any neighbour already chosen, which forces a spread of directions and preserves the long links that make the graph navigable. It costs 3× the build time, paid once.
| kernel | ns per distance | speedup |
|---|---|---|
| scalar (4-way unrolled) | 24.7 | 1.00× |
| SIMD (Vector API, 128-bit lanes) | 10.0 | 2.46× |
| m | graph bytes/vector | total bytes/vector | build | recall@10 |
|---|---|---|---|---|
| 8 | 77 | 664 | 10.7 s | 0.9959 |
| 16 | 140 | 727 | 18.4 s | 0.9968 |
| 32 | 268 | 855 | 44.7 s | 0.9999 |
Raw vectors are 512 bytes each at 128 dimensions, so the graph is a 15–52% overhead on top.
git clone https://github.com/Ankitnehra6/vector-engine.git
cd vector-engine
make serve # visualiser on http://localhost:8080
make bench # the numbers above, on synthetic data
make test # 51 testsFor the standard benchmark dataset:
make sift # downloads SIFT1M — a million real SIFT descriptors, ~168 MB
make bench-siftThe layers are drawn stacked, because the hierarchy is the whole idea and it cannot be seen one layer at a time. Press Play to watch a query fall through them, or Step to advance a layer at a time; click anywhere on any layer to search from that point.
The node counts down the left-hand side are the point: a typical build gives 2 → 13 → 95 →
600, a ratio of about m per layer. That is not a coincidence. Levels are drawn from an
exponential with scale 1/ln(m) precisely so that a descent visits a roughly constant number of
nodes per layer, which is what makes the whole search O(log n).
Watch the dropline between layers — it is the step that makes this a hierarchy rather than four separate graphs: the node one layer's walk ends on is the node the next layer's walk starts from.
●─────────────────────● layer 3 2 nodes, very long links
│ │
●───●────●───────●────────●───● layer 2 13 nodes
│ │ │ │ │ │
●─●─●─●──●─●─●───●─●──●───●─●─●─●─● layer 1 95 nodes
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● layer 0 600 nodes, every vector
A query enters at the top and walks greedily downhill — hop to whichever neighbour is closer, repeat. At the top that means enormous strides; each layer down is denser and refines the answer. It is a skip list with a graph at every level instead of a linked list.
Three details separate a working implementation from one that merely runs, and all three are easy to leave out:
- The selection heuristic — see above. Worth 4.7× recall.
- Pruning reverse links. Links are bidirectional, so a popular node accumulates connections from everyone who found it. Left alone its degree grows without bound and every search is dragged through it. When a node goes over budget its whole neighbour list is re-selected, not truncated — truncating strips out exactly the long links the heuristic chose.
- Layer 0 gets
2mconnections. Every node lives there and it is where the final refinement happens.
"Find similar vectors, but only ones this tenant may see" breaks the obvious approaches.
Search-then-filter returns fewer than k results as soon as the predicate is selective, and
none at all when it is very selective — the walk never went near the matching vectors, and
nothing reports an error.
So the predicate is applied inside the traversal: non-matching nodes are still walked through, because one is often the only route to a matching one, but only matching nodes are eligible to be results. That has its own failure mode — when almost nothing matches, the result set never fills, the stopping condition never fires, and the search crawls the whole graph. Hence a visit budget, past which it abandons the graph and scans the matching subset exactly.
Result: a filter matching 1 vector in 100 still returns a full page of exactly correct results. See ADR 4.
curl -X POST localhost:8080/api/collections \
-d '{"name":"docs","dimensions":384,"metric":"cosine","m":16}'
curl -X POST localhost:8080/api/collections/docs/vectors \
-d '{"vectors":[{"id":"doc-1","vector":[...],"metadata":{"tenant":"acme"}}]}'
curl -X POST localhost:8080/api/collections/docs/search \
-d '{"vector":[...],"k":10,"filter":{"tenant":"acme"},"efSearch":64}'POST /api/collections |
create — dimensions, metric, m, efConstruction |
POST /api/collections/{n}/vectors |
upsert one or a batch |
DELETE /api/collections/{n}/vectors/{id} |
tombstone |
POST /api/collections/{n}/search |
k, filter, per-query efSearch, optional trace |
GET /api/collections/{n}/graph?layer= |
the graph, for 2-D collections |
efSearch is per-query, not per-index — the same data legitimately serves a
latency-sensitive autocomplete and an accuracy-sensitive batch job. pgvector and Qdrant both
expose it the same way.
The graph is primitive arrays, the HTTP layer is com.sun.net.httpserver, and the JSON parser
is one file. That is not
minimalism for its own sake: bytes per vector is a headline number here, and a framework
with its own thread pools, buffers and caches in the same heap would make it impossible to
attribute honestly.
51 tests. An approximate index cannot be tested by asserting on specific results — being
occasionally wrong is the entire point — so the assertions are about how often it is right,
measured against BruteForceIndex, which is exact by construction.
| Test | What it proves |
|---|---|
HnswIndexTest |
Recall > 0.95 on clustered, uniform and cosine data; efSearch monotonically improves recall; the heuristic beats naive; degrees stay within budget; levels thin geometrically; every node is reachable; builds are byte-identical from a seed |
FilteredSearchTest |
A 1-in-100 filter still returns k exactly-correct results; broad filters keep graph recall; ordering survives the fallback |
DistancesTest |
SIMD and scalar agree across 14 dimension counts, including several that leave a remainder |
DistanceHeapTest |
Keys and values stay paired through 500 random operations — a heap bug here does not crash, it silently returns slightly wrong neighbours |
Kept because the interesting part of a project is what it got wrong first.
- A test-data bug that looked exactly like an index bug. Clustered recall sat at 0.776 and
refused to improve with
efSearch. The queries were generated with a different seed than the data, so their cluster centres were somewhere else entirely — and in 64 dimensions that makes every stored vector almost exactly equidistant from every query. The "true" ten nearest were an arbitrary pick among thousands of ties, and the index was being punished for returning a different but equally valid ten. Holding out the queries from the same generation took recall to 0.997. Nothing was wrong with the algorithm; the measurement was meaningless. exec:javameasured scalar against scalar. It runs inside Maven's JVM, which was not started with--add-modules=jdk.incubator.vector, soDistances.best()fell back and the SIMD row of the benchmark compared the scalar kernel to itself — reporting a 1.00× speedup for a change that is actually worth 2.46×. Fixed by forking a JVM withexec:exec.- A two-argument helper called with one argument.
postJson(payload)against(path, payload)meantJSON.stringify(undefined), an empty request body, and a visualiser that drew the graph perfectly and could not search it.
Honest limits, not a roadmap.
- No quantization. Vectors are stored as raw
float32. Product quantization is the single biggest memory win available (4–32×) and is the main reason to choose IVF over HNSW at scale. - No persistence. The index is in memory and rebuilt on startup. Serialising the arena and the adjacency arrays is straightforward; a memory-mapped format that loads without deserialising is the interesting version, and is not here.
- Inserts are serialised. Many concurrent searches, one writer. Concurrent insertion is genuinely hard to get right — two inserts touching the same region can interleave into a graph that is not corrupt but is quietly worse, with nothing in a stack trace. A lock that is obviously correct was the better trade for a bulk-load-then-query workload; it would not be for a streaming one.
- Deletion is tombstones only. The graph is never repaired, so recall degrades as deletions accumulate and the fix is a rebuild. Every production engine does the same; this one says so.
- No sharding, no replication. Single process.
- The filter budget is a constant. Estimating selectivity by sampling the predicate would choose it better, and is not implemented.
Recorded with the reasoning and the costs:
- HNSW, rather than IVF or LSH
- The neighbour-selection heuristic is not optional
- Flat arenas and primitive heaps, not objects
- Filtering happens inside the traversal
- SIMD via the Vector API, with a scalar fallback
Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (2016), arXiv:1603.09320.
MIT — see LICENSE.