A database contains one hundred million vectors.
The exact nearest neighbour is somewhere inside.
One method compares the query with all one hundred million.
HNSW tries something more like navigation.
It builds a graph and searches through likely neighbourhoods.
Quick Read
Hierarchical Navigable Small World, or HNSW, is a graph-based approximate nearest-neighbour index. Data points become nodes connected to nearby nodes. Additional upper layers create long-range shortcuts that help a query move quickly toward promising regions before refining the search in denser lower layers.
One-sentence answer: HNSW is lossy because it replaces exhaustive comparison with bounded graph exploration, preserving likely neighbours while accepting that some true nearest neighbours may never be visited.
The Graph Is a Map of Locality
Each vector is connected to selected nearby vectors.
The graph does not store every possible pairwise relationship.
It stores enough edges to create a navigable approximation of the geometry.
The first lossy move therefore happens at index construction: most possible edges never exist.
Upper Layers Provide Long Jumps
HNSW builds several graph layers.
Upper layers contain fewer nodes and longer-range connections.
Lower layers contain denser local structure.
A query begins high, moves toward a promising region, then descends and refines.
The hierarchy reduces the number of expensive local comparisons needed to reach a useful neighbourhood.
Search Is Greedy but Not Blind
The search keeps a frontier of promising nodes.
It explores neighbours that appear to move closer to the query.
With a larger exploration budget, more alternatives remain alive.
With a smaller budget, search becomes faster and more myopic.
efSearch Is a Recall–Latency Dial
HNSW implementations expose a search-effort parameter often called efSearch.
Raise it and the algorithm explores more candidate nodes.
Recall usually improves.
Latency rises too.
The parameter does not change the stored vectors. It changes how much of the graph the query is allowed to inspect.
M Shapes the Graph
Another important parameter controls how many neighbours each node tends to retain.
More connections can improve navigability and recall but increase index memory and build cost.
Fewer connections create a smaller graph but make some regions harder to reach.
Graph density becomes another rate–distortion budget.
The True Neighbour Can Exist and Still Be Unreachable in Practice
The vector remains in the database.
But the graph traversal may never enter the right basin under the chosen search budget.
That failure is not deletion of data.
It is loss of search path.
Graph Quality Matters as Much as Search Strategy
A good traversal cannot fully compensate for a badly constructed graph.
Recent research continues to examine the interaction between graph quality, traversal policy and ANN retrieval performance because indexing and searching are coupled.
The graph determines which routes are available; the traversal decides which available routes are actually taken.
HNSW and Sparse Attention Share a Structural Lesson
Sparse attention removes possible token-to-token edges.
HNSW stores only a sparse subset of possible vector-to-vector edges.
In both cases, connectivity decides what can become reachable under finite computation.
The domains differ, but the geometry of loss is similar.
HNSW and Candidate Generation Must Stay Separate
Candidate Generation owns the pipeline question: how do we reduce a huge corpus to a shortlist?
HNSW owns one mechanism for producing that shortlist through graph navigation.
The umbrella and mechanism support one another without competing for the same search intent.
Small Corpora Can Make HNSW Unnecessary
Approximation has overhead.
For smaller vector collections, brute-force flat search can be simple, exact and fast enough.
Recent retrieval guidance continues to emphasise that HNSW is not automatically superior at every scale.
Approximate indexing becomes worthwhile when the corpus, latency target and hardware make exhaustive comparison expensive.
Dynamic Updates Create Another Trade-Off
Insert new nodes and the graph changes over time.
Deletion, compaction and changing distributions can alter neighbourhood quality.
A graph that was excellent for yesterday’s corpus can become less balanced under heavy drift.
Index maintenance is therefore part of retrieval quality.
Education: Knowledge Retrieval Also Uses Paths
A student may remember one fact because another nearby idea cues it.
Strong knowledge is often navigable through associations rather than stored as one flat list.
This is an analogy, not HNSW mechanics. The shared lesson is that a memory can contain the answer and still fail if the route into the right neighbourhood is weak.
A CivDJ View: Audit the Unvisited Neighbourhood
Forward: does HNSW meet the target latency and recall?
Backward: which exact neighbours were missed and why?
Rotate: do misses concentrate in dense clusters, sparse regions, rare categories or newly inserted data?
The invisible failure is not always a bad distance function. It can be a path the search never traversed.
When HNSW Is Exactly the Right Loss
Use it when vector collections are large, low-latency ANN retrieval matters, extra index memory is acceptable, and recall can be tuned and validated against an exact baseline.
When HNSW Becomes Dangerous
- Recall is assumed rather than measured against exact search.
- Search effort is reduced too aggressively.
- Graph construction quality is poor.
- Distribution drift degrades neighbourhood structure.
- Rare regions become hard to enter.
- The approximate index replaces the exact source needed for audit.
A Practical HNSW Audit
- Metric: what vector distance defines neighbourhood?
- Graph: how dense are stored connections?
- Search: what exploration budget is used?
- Recall: how often are exact neighbours recovered?
- Drift: how does quality change as data evolve?
- Latency: what does extra recall cost?
- Baseline: is flat exact search available for calibration?
Research Anchors
Current retrieval research and operational guidance continue to treat HNSW as a major graph-based ANN method, while emphasising calibration against exact retrieval and the interaction between graph quality, traversal policy, memory and recall.
Continue Through eduKateSG
Continue with How Lossy Works | Candidate Generation, How Lossy Works | Locality-Sensitive Hashing, and the companion article How Lossy Works | Inverted File Indexing.
Final Thought: A Fast Search Is a Journey Through a Map That Never Contained Every Road
HNSW works because the graph is sparse and the search is selective.
Its success depends on whether the roads it kept still lead to the neighbours the receiver cares about.