HNSW-Sharp

What is HNSW?

Hierarchical Navigable Small World (HNSW) graphs are a data structure for approximate nearest-neighbor search published by Malkov & Yashunin (2016). They are the backbone of most modern vector databases — including FAISS, Milvus, Weaviate, and pgvector — because they offer the best practical recall/latency trade-off across a wide range of workloads.

The intuition

Exact k-NN search is hard in high dimensions: when each item has hundreds or thousands of coordinates, every distance comparison touches every coordinate, and there are no useful axis-aligned shortcuts. Bruteforce becomes the only honest baseline.

HNSW dodges that by building a proximity graph. Each item is a node; an edge connects items that are close under your distance metric. To search, you start somewhere in the graph and greedily hop to neighbours that are closer to the query than your current position. With enough edges, the greedy walk converges on the true nearest neighbours after only a handful of hops — far fewer than the size of the dataset.

The "hierarchical" part adds layers of progressively-sparser graphs on top of the full graph. The top layer is tiny — a few long-range edges between far-apart points. As you descend, layers grow denser. Search starts at the top, takes a long-range hop to land roughly in the right neighbourhood, and only then drops down to the dense bottom layer to refine.

Layer 3:   o------------o                 ← few nodes, long-range edges
Layer 2:   o----o-------o-----o
Layer 1:   o--o-o-o--o--o-o---o-o
Layer 0:   ooooooooooooooooooooooooo      ← every item lives here

In HNSW-Sharp this entire structure is hidden behind SmallWorld<TItem, TDistance>. You add items, you ask for neighbours — the layering is handled internally.

How it scales

Empirically, HNSW search is roughly logarithmic in the number of items, with a small constant. Indexes with millions of vectors return top-k results in microseconds; indexes with hundreds of millions still answer in well under a millisecond.

The trade-offs are:

  • Memory. Each item needs roughly M × 4 bytes for layer-zero edges plus the vector itself. A 1M × 768-dimensional float index is around 3 GB.
  • Build time. Inserting an item costs roughly O(log N × EfConstruction). Building 1M items takes seconds to a minute or two depending on M.
  • Recall. Search is approximate. Increasing EfSearch recovers recall at the cost of latency.

See Parameters for the levers you have to tune all of this.

What this library adds

HNSW.Net (this package's underlying name) is a managed C# implementation of the algorithm with a few practical extras:

  • Generic over item and distance type — SmallWorld<TItem, TDistance> accepts any item and any numeric distance.
  • SIMD-accelerated cosine — CosineDistance.SIMD* paths for float[] vectors. See Distance functions.
  • Stream-based serialization — write a built graph to any Stream, reload it on startup, skip the build entirely.
  • ACORN-γ filtering — optional graph construction mode that keeps recall high under filter predicates. See Filtering.
  • Thread-safety toggle — a built-in reader-writer lock around the graph that you can disable when you have your own synchronisation.

When to use HNSW (and when not)

HNSW is the right answer when:

  • You have lots of items (more than a few thousand) and search latency matters.
  • Items have many dimensions and there's no obvious cheaper structure (no useful axis-aligned tree).
  • You are happy with approximate results — recall in the high 90s is achievable, but exact matches are not guaranteed.

It is not the right answer when:

  • You have only a few hundred items — bruteforce is faster and simpler.
  • You need an exact top-k under strict guarantees — use bruteforce, or a tree if your dimensionality is low.
  • Your data changes rapidly and you can't afford the rebuild cost — HNSW supports incremental inserts but no deletes.

Further reading

© 2026 HNSW-Sharp. All rights reserved.