HNSW Vector Index

A from-scratch C++17 implementation of HNSW (Hierarchical Navigable Small World) — an approximate nearest-neighbor search structure over document embeddings, ranked by cosine similarity.

The project is deliberately implemented from first principles (no external ANN libraries) so the graph construction and search logic can be inspected, tested, and incrementally optimized.

How it works, briefly

Each inserted vector is randomly assigned a maximum "layer" (higher layers are exponentially sparser). A vector exists in every layer from 0 up to its assigned max layer. Search starts at the sparsest (highest) layer, greedily walks toward the query vector, and narrows the candidate set as it descends toward layer 0, which holds every vector and gives the final ranked results. This gives roughly logarithmic search time instead of a full linear scan, at the cost of being approximate rather than exact.

Project structure

File	Purpose
Document.hpp / Document.cpp	Plain struct-like wrapper for a document's id + title.
Embedding.hpp / Embedding.cpp	Wraps a fixed-size float vector with an id; validates dimensionality on construction.
Hnsw.hpp / Hnsw.cpp	The index itself: graph construction (insert), approximate search (_search, _make_connections), and top-k lookup (query).
test.cpp	Correctness checks against the public API. Run before pushing any change.
benchmark.cpp	Perf harness: insert throughput, query latency, recall@k vs. brute force. Run after any optimization to see its effect.
Makefile	Builds the test target (mainout) and the bench target (benchout).

Build & run

# Correctness checks
make
./mainout

# Performance benchmark
make bench
./benchout

# Clean build artifacts
make clean

test.cpp and benchmark.cpp are independent binaries (each has its own main()), so they're built as separate targets rather than both being linked together.

Usage

#include "Hnsw.hpp"

// max_connections per node per layer, and the fixed embedding dimensionality
Hnsw index(/*max_connections=*/16, /*vec_size=*/128);

// insert(vector, document_id, document_title) -> internal vector id
int id = index.insert(my_embedding, /*document_id=*/1, "some-doc.txt");

// query(Embedding, k) -> top-k results sorted by similarity, descending
Embedding q(/*id=*/-1, /*vec_size=*/128, query_vector);
std::vector<Hnsw::query_result> results = index.query(q, /*k=*/10);

for (auto& r : results) {
    // r.doc.document_id, r.doc.document_title, r.similarity, r.candidate_id
}

Notes:

• insert() and the Embedding constructor both throw if the vector's length doesn't match the index's configured vec_size.
• query() returns fewer than k results if the index has fewer than k vectors, and an empty vector if the index is empty.
• Similarity scores are cosine similarity in [-1, 1] (higher is closer).

Testing

test.cpp is a small self-contained harness (no external framework) that exercises only the public API: Document, Embedding, Hnsw::insert, and Hnsw::query. It checks things like:

• basic construction and field storage for Document / Embedding
• dimensionality-mismatch errors are thrown where expected
• inserting a vector and querying for itself returns similarity ≈ 1.0
• results come back sorted by similarity, closest first
• querying an empty index, or with k larger than the index size, doesn't crash and returns a sensible result
• nearest neighbor is still found correctly once multiple graph layers exist

Run it with make && ./mainout. Add a new test_*() function and a CHECK() call for any behavior you add or fix.

Benchmarking

benchmark.cpp inserts a batch of random vectors, then runs a batch of random queries against the index, reporting:

• insert throughput (vectors/sec)
• query latency (avg / p50 / p95 / p99, in ms)
• recall@k against a brute-force cosine-similarity ground truth, so you can see quality/speed tradeoffs, not just raw speed

It runs this at a few dataset sizes (1k / 5k / 20k vectors by default — adjust the calls in main() to taste). Because the graph construction has a random component (_assign_layer), the benchmark uses a fixed RNG seed so numbers are comparable across runs — always re-run the full benchmark after a change rather than comparing against an old log.

make bench && ./benchout

Known limitations / possible next steps

• _assign_layer() constructs a fresh std::random_device + std::mt19937 on every call, which is wasteful at scale — a good first optimization target for insert throughput.

• No deletion / update support — the index is insert-and-query only.

• No persistence — everything lives in memory for the process lifetime.

• _make_connections's "replace worst neighbor" step is O(degree) per candidate per insert, which is the standard HNSW tradeoff but could be cached/optimized further (see the comment in the source).

• Layer assignment uses a simple p = 0.5 coin-flip rather than the usual -ln(uniform()) * mL normalization constant — works, but doesn't give the same layer-size distribution as canonical HNSW; worth experimenting with if recall/latency at scale doesn't look right.

  Notes

  Efficiency of greedy routing on NSW breaks on verteces greater than 10,000.