HNSW is the dominant data structure for approximate nearest neighbor (ANN) search in high-dimensional vector spaces. It builds a multi-layer proximity graph where upper layers contain long-range links for fast navigation and lower layers contain short-range links for precision. A search begins at the top layer and greedily descends, reaching the neighborhood of the target in logarithmic time.
Vector databases like Pinecone, Milvus, Weaviate, and Qdrant all use HNSW as their primary index. In a typical vector search system, HNSW is implemented for embedding-based search over document stores, making it a core competency for anyone building AI-powered retrieval systems.
Understanding HNSW is essential because the quality of your vector search directly determines RAG accuracy, recommendation relevance, and anomaly detection sensitivity. Tuning HNSW parameters (M, efConstruction, efSearch) is one of the highest-leverage performance knobs in any vector-heavy application.
HNSW achieves logarithmic search complexity O(log n) by using the hierarchical structure as a coarse-to-fine navigation system. Upper layers act like an express highway, skipping over large regions of the graph to quickly reach the right neighborhood.
The layer assignment follows an exponential distribution: a node is inserted at layer floor(-ln(uniform(0,1)) * mL) where mL = 1/ln(M). This ensures the number of nodes halves with each layer, creating the logarithmic depth.
Elements are inserted one at a time. For each new element, a random maximum layer is chosen. The algorithm first navigates from the entry point through upper layers using greedy search (keeping only the single closest node at each step) until it reaches the element’s assigned layer. From there, it searches with a beam width of efConstruction, collecting candidate neighbors. The best M neighbors are selected using a heuristic that balances proximity with graph connectivity.
A query enters at the top layer’s entry point and greedily navigates down to layer 0. At layer 0, it performs a beam search with width efSearch, maintaining a priority queue of candidates and a result set. The search terminates when no unvisited candidate is closer than the furthest result. The final result set contains the approximate k nearest neighbors.
Rather than simply picking the M closest neighbors, HNSW uses a heuristic that considers whether a candidate is closer to the new element than to any already-selected neighbor. This pruning ensures the graph stays well-connected and avoids clusters of redundant edges, which is critical for maintaining recall in high-dimensional spaces.
The neighbor selection heuristic is what separates HNSW from naive proximity graphs. By preferring diverse directions over pure proximity, it creates “shortcuts” that prevent the search from getting trapped in local clusters.
In a production vector search system, HNSW powers the vector index, allowing the system to perform sub-millisecond similarity searches across millions of document embeddings while maintaining >95% recall.
High-performance implementations store the graph in flat arrays rather than pointer-based structures. Each node’s neighbors are stored contiguously, with the vector data adjacent to the link lists. This cache-friendly layout reduces memory indirection and improves search throughput by 2-3x compared to pointer-chasing designs.
Distance functions (cosine similarity, L2, inner product) dominate runtime. SIMD-accelerated implementations use AVX-512 or NEON intrinsics to compute distances over 8-16 float dimensions per instruction. Quantized variants (PQ, SQ) trade precision for even faster comparisons.
Read queries are lock-free since the graph structure is append-only during search. Writes require fine-grained locking at the node level: lock only the nodes whose neighbor lists are being modified. This allows concurrent inserts with minimal contention.
package hnsw
import (
"math"
"math/rand"
"sort"
)
type Node struct {
ID uint64
Vector []float32
Layers [][]uint64 // neighbors per layer
MaxLayer int
}
type HNSW struct {
Nodes map[uint64]*Node
EntryPoint uint64
MaxLayer int
M int // max connections per layer
Ml float64 // level generation factor
EfConstruct int
}
func NewHNSW(m, efConstruction int) *HNSW {
return &HNSW{
Nodes: make(map[uint64]*Node),
M: m,
Ml: 1.0 / math.Log(float64(m)),
EfConstruct: efConstruction,
}
}
func (h *HNSW) randomLevel() int {
return int(math.Floor(-math.Log(rand.Float64()) * h.Ml))
}
func (h *HNSW) Insert(id uint64, vec []float32) {
level := h.randomLevel()
node := &Node{
ID: id,
Vector: vec,
MaxLayer: level,
Layers: make([][]uint64, level+1),
}
if len(h.Nodes) == 0 {
h.Nodes[id] = node
h.EntryPoint = id
h.MaxLayer = level
return
}
// Navigate from top layer down to node's level
current := h.EntryPoint
for l := h.MaxLayer; l > level; l-- {
current = h.greedyClosest(current, vec, l)
}
// Insert at each layer from level down to 0
for l := min(level, h.MaxLayer); l >= 0; l-- {
neighbors := h.searchLayer(current, vec, h.EfConstruct, l)
selected := h.selectNeighbors(vec, neighbors, h.M)
node.Layers[l] = selected
// Add bidirectional connections
for _, nid := range selected {
h.Nodes[nid].Layers[l] = append(h.Nodes[nid].Layers[l], id)
h.pruneConnections(nid, l)
}
}
h.Nodes[id] = node
if level > h.MaxLayer {
h.MaxLayer = level
h.EntryPoint = id
}
}const std = @import("std");
const Vector = std.meta.Vector;
/// L2 squared distance using SIMD, processing 8 floats at a time
pub fn l2DistanceSimd(a: []const f32, b: []const f32) f32 {
std.debug.assert(a.len == b.len);
const simd_width = 8;
var sum_vec: Vector(simd_width, f32) = @splat(0.0);
var i: usize = 0;
// SIMD loop: process 8 dimensions per iteration
while (i + simd_width <= a.len) : (i += simd_width) {
const va: Vector(simd_width, f32) = a[i..][0..simd_width].*;
const vb: Vector(simd_width, f32) = b[i..][0..simd_width].*;
const diff = va - vb;
sum_vec += diff * diff;
}
// Horizontal sum of SIMD accumulator
var sum = @reduce(.Add, sum_vec);
// Scalar tail for remaining dimensions
while (i < a.len) : (i += 1) {
const diff = a[i] - b[i];
sum += diff * diff;
}
return sum;
}
/// Cosine similarity via SIMD dot product
pub fn cosineSimilaritySimd(a: []const f32, b: []const f32) f32 {
const simd_width = 8;
var dot_vec: Vector(simd_width, f32) = @splat(0.0);
var norm_a_vec: Vector(simd_width, f32) = @splat(0.0);
var norm_b_vec: Vector(simd_width, f32) = @splat(0.0);
var i: usize = 0;
while (i + simd_width <= a.len) : (i += simd_width) {
const va: Vector(simd_width, f32) = a[i..][0..simd_width].*;
const vb: Vector(simd_width, f32) = b[i..][0..simd_width].*;
dot_vec += va * vb;
norm_a_vec += va * va;
norm_b_vec += vb * vb;
}
var dot = @reduce(.Add, dot_vec);
var norm_a = @reduce(.Add, norm_a_vec);
var norm_b = @reduce(.Add, norm_b_vec);
while (i < a.len) : (i += 1) {
dot += a[i] * b[i];
norm_a += a[i] * a[i];
norm_b += b[i] * b[i];
}
return dot / (@sqrt(norm_a) * @sqrt(norm_b));
}efConstruction = 2 * M.M neighbor IDs per layer. With M=32 and 10M vectors, the graph metadata alone can exceed the vector storage. Always budget for graph overhead.HNSW trades memory for speed: the multi-layer graph is larger than flat indexes like IVF, but delivers consistently low latency (<1ms) even at millions of vectors, making it the default choice when latency matters more than memory.
The three critical tuning knobs are M (graph degree), efConstruction (build quality), and efSearch (query accuracy). Recall and latency are always in tension — profile your workload to find the right tradeoff.