Why is mathematics important in HNSW search? Because finding the nearest item in a large collection of high-dimensional vectors can require millions of distance calculations. Hierarchical Navigable Small World graphs trade an exact exhaustive scan for a structured approximate search whose recall, latency and memory can be measured.
HNSW appears in vector search, semantic retrieval, image similarity and recommendation pipelines. It does not understand meaning by itself. An embedding model creates vectors, a distance function defines “near,” and the index navigates a graph. A fast answer is useful only when the metric and evaluation match the reader's real task.
From Items to Vectors
A vector is an ordered list of numbers. Text, images or products can be mapped to vectors by a model so that selected relationships correspond to geometric proximity.
Dimension
A vector with d coordinates lives in d-dimensional space. Two-dimensional drawings are easy to see; production embeddings may have hundreds or thousands of coordinates.
Distance or similarity
Euclidean distance measures straight-line separation. Cosine similarity compares angle through the dot product divided by vector lengths. Inner product has another geometry. The index and model must agree on the metric.
Nearest neighbours
Given query q and collection points, exact k-nearest-neighbour search returns the k smallest distances under the defined metric.
Quick Reading Routes
- Understand exact and approximate neighbour search.
- Follow greedy movement through an HNSW graph.
- See why random hierarchy reduces search work.
- Calculate recall, latency and memory trade-offs.
- Explore construction, deletion, filtering and failure cases.
- Finish with experiments, guidance, misconceptions and FAQs.
Exhaustive Search Is the Baseline
The simplest algorithm computes the distance from q to every one of n stored vectors, then selects the nearest k.
Distance work
For dense d-dimensional Euclidean vectors, one distance needs roughly d subtractions, d multiplications and additions. Scanning n points costs on the order of nd coordinate operations.
A scale example
With n = 10 million and d = 768, one query touches about 7.68 billion coordinate positions before selection overhead. Hardware can batch and vectorise this work, but the scale remains large.
Exactness has value
Exhaustive results provide ground truth for evaluation and may be practical for small sets, offline jobs or accelerated batches. Approximation is not automatically better.
Approximate Search Changes the Contract
An approximate index tries to return neighbours close to the true ones with much less work.
Recall at k
If the exact top 10 contains ten items and an approximate search returns eight of them, recall@10 is 8/10 = 0.8 for that query.
Average hides hard queries
Mean recall can look strong while certain languages, categories or sparse regions perform poorly. Report distributions and meaningful segments.
Approximation is not random guessing
The index exploits geometry and graph links. Its errors are structured by data distribution, metric and search settings.
Product impact is separate
High neighbour recall does not prove useful search, fairness or factual relevance. Those require end-to-end evaluation.
A Proximity Graph Encodes Local Routes
HNSW represents each stored vector as a node. Edges connect selected nearby nodes.
Greedy navigation
Start at an entry node. Inspect its neighbours and move to one closer to the query. Repeat until no inspected neighbour improves the current candidate under the search rule.
Local minima
A graph can trap greedy search at a node that is better than its neighbours but not globally nearest. Long-range links and a well-connected neighbourhood reduce this risk.
Degree controls options
More neighbours give more routes and consume more memory. Too few can disconnect useful regions; too many increase construction and query work.
Hierarchy Adds Express Lanes
HNSW gives some nodes membership in upper, sparser layers. Search begins high, makes long moves, then descends into denser layers for refinement.
Random level assignment
The original method assigns maximum layer using an exponentially decaying distribution. Many nodes appear only at the base; progressively fewer reach high layers.
Expected population
If the probability of reaching each next layer is p, expected population at level l is approximately np^l. With n = 1,000,000 and p = 0.1, rough counts are 100,000, 10,000, 1,000 and 100.
Skip-list analogy
Sparse layers resemble express lanes in a skip list. They help reach the right region before detailed base-layer exploration.
Evidence
The original HNSW paper by Malkov and Yashunin describes a multilayer proximity graph, exponential layer assignment and greedy search from sparse to dense layers.
A Small Search Example
Imagine base-layer points along a winding shape. Query q lies near node J, while the entry node is A.
Upper layer
Only A, D, H and L appear. Distances to q decrease A → D → H. L is farther, so H becomes the entry for the next layer.
Middle layer
Neighbours of H include F, I and K. K is closest, so search moves there.
Base layer
The search explores a candidate set around K, perhaps discovering J and nearby nodes. It returns the best k encountered.
Approximation point
If a missing graph edge prevents the search from entering J's region, a true neighbour may be absent. Expanding the candidate set can improve recall at extra cost.
Search Uses a Candidate Frontier
Practical HNSW search keeps candidates ordered by distance and a result set of the best points found.
`efSearch`
A common control, often called `efSearch`, limits or influences how many candidates are explored. Larger values usually improve recall and increase distance computations and latency.
It is not a universal unit
`efSearch = 100` does not imply the same time or recall across libraries, datasets, metrics and hardware. Treat it as a configuration inside one measured system.
k and candidate breadth
The candidate breadth should generally be at least k, but the best margin depends on difficulty. Asking for more final neighbours also changes work.
Tail latency
Some queries explore more graph regions than others. Evaluate p95 and p99 latency, not only the mean.
Construction Is Also a Search Problem
When inserting a new vector, HNSW navigates the existing graph to find candidate neighbours, then selects links.
`efConstruction`
A broader construction search can discover better neighbours and improve graph quality, while taking more time.
M controls degree
Implementations often expose a neighbour parameter M. Larger M usually raises memory and construction cost and can improve recall or robustness.
Quality depends on order
Insertion order and random levels affect the graph. A clustered batch arriving first may create different routes from a shuffled build.
Rebuilds may improve structure
Incremental convenience is valuable, but a controlled rebuild can remove accumulated deletion markers, update models and retune parameters.
Neighbour Selection Needs Diversity
Choosing only the closest neighbours can create redundant links pointing in the same direction.
Geometric coverage
A diversity heuristic prefers connections that open different routes through space. A slightly farther link can improve navigation.
Dense clusters
In a dense cluster, many nearly identical candidates compete for limited degree. Keeping all links local can isolate the cluster from the rest of the graph.
Bridges matter
Bridge edges may have low local similarity but high navigation value. Their benefit appears in search paths rather than one node's nearest list.
Heuristics require evaluation
The paper reports a neighbour-selection heuristic, but implementation details and datasets affect results. Avoid claiming a fixed parameter is optimal everywhere.
Metric Choice Changes the Neighbourhood
Euclidean distance, cosine distance and inner product can rank the same vectors differently.
Cosine similarity
cos(q,x) = (q·x)/(|q||x|). If vectors are normalised to unit length, cosine ranking relates to Euclidean distance through a simple transformation.
Normalisation is a model choice
Normalising removes magnitude information. That is appropriate only when direction represents similarity better than length.
Inner product
Large vector norms can dominate inner product. Some recommendation models intentionally encode popularity or confidence in magnitude.
Distance must match index assumptions
A graph built under one metric should not be queried as if edges represented another without analysis or rebuilding.
High Dimensions Change Intuition
Distances can concentrate as dimension grows, and familiar low-dimensional pictures become unreliable.
Distance concentration
For some distributions, nearest and farthest distances become relatively closer. Ranking can become sensitive to small changes.
Intrinsic dimension
Data may lie near a lower-dimensional structure even when stored in many coordinates. Search difficulty often depends more on intrinsic organisation than raw d.
Hubness
Some points appear in many neighbour lists. Hubs can help navigation or bias retrieval, depending on why they occur.
Visualisations are projections
A two-dimensional plot cannot prove the high-dimensional graph has the same clusters or distances.
Memory Is Part of the Trade-Off
HNSW stores vectors plus graph links, level data and implementation overhead.
Link estimate
If base nodes store roughly M neighbour identifiers and each identifier uses b bytes, the simple base-link estimate is nMb bytes before headers, alignment and upper layers.
For n = 10 million, M = 32 and b = 4, identifiers alone are about 1.28 GB. Real memory is higher.
Vector storage
Ten million 768-dimensional float32 vectors need about 10,000,000 × 768 × 4 bytes = 30.72 GB, before metadata.
Compression changes accuracy
Quantised vectors reduce storage and bandwidth but approximate distances. Graph approximation and vector quantisation errors can combine.
Capacity needs headroom
Building or updating can need temporary memory beyond steady state. Plan for replicas, filtering metadata and operating-system cache.
Recall, Latency and Memory Form a Frontier
Increasing M, `efConstruction` or `efSearch` can improve one dimension while costing another.
Measure a curve
Run a query set at several `efSearch` values. Plot recall@k against p95 latency and distance computations.
Reject dominated settings
A setting with lower recall and higher latency than another is dominated. Keep non-dominated options for product judgement.
Include build cost
An index built once and queried billions of times can justify expensive construction. A rapidly changing index may not.
Include memory pressure
More links can reduce CPU search while causing memory misses. Hardware-level behaviour matters.
Ground Truth Evaluation
Approximate recall needs an exact or trusted reference.
Representative query set
Sample production-like queries, rare categories, languages, short inputs and adversarial cases. Easy random vectors can inflate results.
Exact baseline
Compute brute-force top k on an evaluation subset or use an exact system. Ensure the same metric and vector preprocessing.
Ties
Equal distances complicate recall. Define how tied neighbours are treated rather than punishing an equally valid result.
Confidence intervals
With a finite query sample, mean recall is estimated. Report sample size and variation; repeat after data drift.
Filtering Complicates Search
A query may require category, language, date or permission filters.
Filter after search
Retrieve candidates, then filter. If acceptable items are rare, too few remain and recall falls.
Filter during traversal
Restricting traversal can disconnect routes, depending on implementation. A filtered-out node may still be a valuable bridge.
Separate indexes
Building one index per segment improves filter selectivity but duplicates overhead and struggles with many small segments.
Evaluate the actual predicate
Unfiltered benchmark results do not predict a permission-heavy workload.
Updates and Deletions
Mutable data changes graph quality and operational cost.
Tombstones
Some systems mark deleted nodes and skip them until maintenance. Too many tombstones waste traversal.
Reinsertions
Changing a vector can be treated as delete plus insert. Its neighbours and reverse navigation value change.
Model upgrades
Vectors from different embedding models may not share a meaningful space. Version them and rebuild or migrate deliberately.
Consistency
Readers may see different index snapshots during updates. Define whether newly inserted items must appear immediately.
A Search Capacity Example
A service receives 2,000 queries per second. One node sustains 300 queries per second at the chosen recall and tail-latency target.
Baseline count
Ignoring failure and variation, 2,000/300 = 6.67, so at least seven nodes are needed.
Add failure reserve
To survive one node loss without overload, eight nodes leave seven survivors with theoretical capacity 2,100 qps.
Include utilisation margin
Running at 95% can amplify queues. At a target 70% utilisation, usable capacity per node is 210 qps, so 2,000/210 = 9.52: use at least ten, plus the chosen failure policy.
Index replication cost
Every replica stores graph and vectors. Query capacity, memory and update bandwidth must be planned together.
Failure Modes and Limits
HNSW has strong empirical performance, not a promise that every dataset yields sublinear search at high recall.
Adversarial geometry
Separated clusters, unusual manifolds or near-duplicate clouds can produce difficult navigation.
Entry-point sensitivity
The upper route may enter an unhelpful region. Broader exploration helps at a cost.
Distribution drift
New data can change density and hubs. A parameter tuned on last month's index may no longer meet objectives.
Theoretical caution
Research on approximate-neighbour implementations has identified difficult instances and limited worst-case guarantees. Production claims should be based on measured distributions, not the word “small world.”
Navigable Small Worlds and Path Length
The phrase “small world” describes a graph that combines local clustering with short routes between distant regions. In a search index, local links help refine a result, while longer-range links help cross the space quickly.
Path length is the relevant intuition
If a graph connects only immediate neighbours on a line, travelling from one end to the other takes many hops. Add a few well-placed long links and the number of hops can fall sharply. HNSW's layers create a related effect: sparse upper layers support large moves, and dense lower layers support detailed moves.
This does not mean every query takes a fixed logarithmic number of steps. The realised search depends on geometry, entry point, graph quality and candidate budget. The small-world idea explains the design; measurements establish its performance.
Degree is constrained
A fully connected graph would offer direct routes but require quadratic numbers of links. HNSW limits neighbourhood size. The challenge is to retain enough geometric diversity that a small set of edges still provides useful routes.
Recall Is More Than One Number
Recall@k compares returned identifiers with an exact top-k set. That is an essential technical metric, but it has variants and limitations.
Set recall
If the exact top ten contains identifiers E and the approximate result contains A, set recall is |E ∩ A|/10. It ignores the order inside the top ten. This is appropriate when any of the ten is equally useful.
Recall by rank
Some applications care more about the first result. A weighted measure can give larger credit to matches at high ranks. Alternatively, report exact-top-1 accuracy alongside recall@10. The metric should follow user value.
Distance ratio
When near neighbours are almost tied, missing one identifier may look severe even though the returned point is nearly the same distance. A distance-ratio measure compares the approximate distance with the exact distance. It complements identifier recall but cannot replace it when identities matter.
Macro and micro averages
A micro average pools all correct neighbours. A macro average gives each query equal weight. If query groups differ in size or difficulty, the two can tell different stories. Report group-level results for languages, product categories or customer segments when those distinctions affect service quality.
A Worked Recall and Latency Sweep
Suppose an evaluation set has 10,000 queries and an exact top ten for each. Three candidate settings produce these illustrative results:
- setting A: 0.88 recall@10, 4 ms median, 12 ms p99;
- setting B: 0.95 recall@10, 7 ms median, 24 ms p99;
- setting C: 0.972 recall@10, 14 ms median, 55 ms p99.
The move from A to B gains seven percentage points of recall for a moderate latency increase. The move from B to C gains 2.2 points but more than doubles p99. There is no context-free winner.
Add a service objective
If the service requires p99 below 30 ms, C is infeasible. If a safety review requires recall of at least 0.96 for a particular query class, A and B are also infeasible for that class. The next step may be a different index, more hardware, a reranker or a redesigned requirement.
Calculate uncertainty
Recall estimated from a sample can vary. Bootstrap intervals or repeated samples help show whether a small difference is real. Latency also changes with concurrency and cache warmth, so a single quiet-machine benchmark is incomplete.
Test the joint distribution
Slow queries may also be low-recall queries. Reporting separate averages hides that relationship. Plot or tabulate recall against latency by query difficulty to see whether the system fails twice on the same cases.
Two-Stage Retrieval and Reranking
Approximate nearest-neighbour search often produces candidates rather than the final answer. A second stage can calculate a more expensive score over a small candidate set.
Candidate recall sets the ceiling
If the correct item is absent from the HNSW candidate set, a reranker cannot recover it. Candidate recall should therefore be measured at the depth sent downstream, such as recall@100 for a reranker that examines 100 candidates.
Exact distance reranking
An index may store compressed vectors for navigation and retain original vectors elsewhere. After retrieving candidates, the service recomputes exact distances using the original representation. This can improve ordering without scanning the whole collection.
Hybrid scores
A final rank may combine vector similarity with keyword match, freshness, availability or policy constraints. Each term needs a documented scale. A high vector score must not override a hard permission rule.
End-to-end evaluation
Improved vector recall does not guarantee improved user outcomes if the reranker, business rules or content quality dominate. Evaluate index metrics and end-to-end task metrics together.
Sharding an HNSW Index
One machine may not hold every vector and link. Sharding divides the collection across nodes, creating a second search problem above the local graphs.
Search every shard
The simplest design queries all shards and merges their candidates. This can preserve recall when each shard returns enough results, but latency and network work grow with shard count. The coordinator must compare scores produced under the same metric.
Route to selected shards
A routing model can predict which shards are promising. This reduces work but may miss a shard containing a true neighbour. Routing recall and local HNSW recall then multiply: a miss at either stage loses the item.
Partition by meaning or by balance
Semantic clusters can improve locality, yet a popular cluster may become a hotspot. Random or hash-based sharding balances load but scatters neighbours. Graph partitioning offers another view: reduce cross-shard links while respecting capacity, as explored in Graph Partitioning, Cut Edges, Balance Constraints and Distributed Work.
Replicas and failures
Replicas increase availability and read capacity. They also multiply memory and make index updates more complex. A failure test should confirm that the reduced replica set still meets both recall and latency targets under load.
Deletions, Privacy and Access Control
Retrieval quality is not the only requirement. An index must respect deletion and permission changes.
Tombstones are temporary state
Some implementations mark a deleted node and skip it in results until compaction or rebuild. If many tombstones accumulate, they may waste memory or damage navigation. Operators should track the deleted fraction and define a rebuild trigger.
Permission filtering
A user must never receive a document they cannot access. Filtering after retrieval can be safe for output only if unauthorised content is never exposed to later stages, but it may return too few authorised results. Traversal-time filtering can also damage connectivity. Systems may need permission-aware partitions, oversampling, or separate indexes.
Deletion verification
Removing a source record is not enough if vectors, replicas, caches and backups retain derived data. A deletion workflow should identify each copy, define completion semantics and audit failures. HNSW mathematics helps locate neighbours; governance determines what is allowed to remain.
Membership leakage
Similarity systems can reveal whether sensitive material is present through responses or timing. Rate limits, output controls and privacy analysis may be needed. Fast search is not a substitute for a threat model.
Hardware Effects and Capacity Planning
HNSW search follows pointers through a graph and reads vector data. Its performance depends strongly on memory hierarchy.
Cache locality
Neighbour nodes stored close together may reduce cache misses. Random pointer chasing can stall while the processor waits for memory. Two implementations with the same M and `efSearch` can therefore have different latency.
SIMD and distance kernels
Vectorised instructions compute several coordinate operations at once. Dimension, alignment and data type affect how efficiently a distance kernel uses the hardware. Quantised vectors reduce bytes moved but add approximation.
Concurrency
Single-query latency and high-throughput latency are different. Many concurrent searches compete for memory bandwidth and caches. Benchmark at the intended concurrency, not only one request at a time.
Capacity arithmetic
Estimate raw vector bytes, graph-link bytes, metadata, allocator overhead, replicas and rebuild headroom. Then validate with a real index because object layouts and implementation details can add substantial overhead. A capacity plan that fills memory to 99% leaves no safe room for updates or failover.
Reproducible HNSW Experiments
A useful benchmark records enough detail to be repeated.
1. Freeze or version the dataset and embedding model. 2. State the metric and all normalisation steps. 3. Define exact ground truth and how ties are handled. 4. Record M, construction breadth, search breadth and random seed where applicable. 5. Warm or deliberately cold-start caches and say which condition was used. 6. Measure recall, latency percentiles, throughput, memory and build time. 7. Repeat under updates, filters, concurrency and node failure. 8. Publish group-level results for known difficult queries.
This method separates evidence from marketing language. “Fast” becomes a latency distribution under stated hardware and load. “Accurate” becomes a recall definition against a versioned exact baseline.
Choosing an Entry Point
Search begins from an entry node, commonly one present at the highest populated layer. From there it descends toward the query. A useful entry point shortens the early route, while an unlucky one can require more exploration.
One entry point is simple
A single maintained entry point is cheap to store and makes search behaviour straightforward. The hierarchy is intended to provide routes from it to many regions.
Multiple starts can improve robustness
Some designs can try several starts or use a routed starting region. This adds distance calculations but may help disconnected-looking or drifting data. The benefit must be measured against the additional work.
Entry points change over time
When the highest-level node is deleted, unavailable or no longer representative, the implementation needs a safe replacement. Operational details such as atomic updates and snapshot consistency matter alongside geometry.
Detecting Distribution Drift
An HNSW index is built from a particular vector distribution. A new embedding model, new language mix or changed catalogue can alter that distribution.
Monitor recall on a recent labelled sample, search expansions, distance distributions, filter selectivity and latency. A rising number of visited nodes at the same `efSearch` may indicate that navigation has become harder. Falling recall can appear even when latency remains stable.
Rebuilding is not automatically necessary after every change. Compare an incremental index with a clean rebuild on the same evaluation set. If the rebuild materially improves the recall-latency frontier, its compute and deployment cost may be justified. This is another controlled decision, not a ritual.
Did You Know? Approximate Can Be More Useful Than Exact
Exact geometric neighbours are only as good as the embedding and metric. An approximate search can miss one exact neighbour yet still return equally useful results for a person.
The reverse is also true: 100% vector recall cannot rescue an embedding that places irrelevant items nearby. Index quality and representation quality are separate.
Common Misconceptions
“HNSW is a vector database”
It is an indexing algorithm. A database adds storage, updates, filtering, security, replication and operations.
“Approximate means inaccurate by a fixed percentage”
Recall varies by query, dataset and settings. Measure it.
“More neighbours always help”
More links cost memory and distance work and can have diminishing returns.
“Cosine and Euclidean are interchangeable”
They relate under normalisation, not for arbitrary vectors.
“High average recall proves good search”
Hard segments, permissions and downstream relevance may still fail.
“One benchmark parameter transfers everywhere”
Implementations, hardware, vectors and traffic differ.
How Students Can Investigate
Build a two-dimensional graph
Plot 50 points, connect each to nearby neighbours, choose an entry and trace greedy movement to several queries.
Add an express layer
Promote every tenth point. Compare distance calculations with and without the sparse layer.
Measure recall
For each query, compute exact top five and graph-search top five. Count overlap and average across queries.
Sweep a search budget
Explore 10, 20, 50 and 100 candidates. Plot recall against visited nodes.
Test a bad metric
Compare raw and normalised vectors. Explain which information the normalisation removed.
Guidance for Parents and Teachers
Begin with a map of rooms connected by doors. A learner starts at one room and follows doors that seem closer to a target. Add a sparse set of “express corridors” to illustrate hierarchy.
Ask for three separate statements: what similarity means, how search moves, and how quality is measured. This prevents “AI understands the data” from replacing the actual mechanism.
The topic joins coordinates, vectors, dot products, probability, graphs, ratios and experimental design. It can support computing and data interests, but it does not guarantee a career or justify collecting personal data without safeguards.
For current Singapore pathways, consult MOE secondary education information and SEAB for the learner's cohort.
A Responsible HNSW Checklist
- Version the embedding model and preprocessing.
- Define the distance metric and normalisation.
- Build a representative exact ground-truth set.
- Report recall distribution, not only mean.
- Measure p50, p95 and p99 latency.
- Track distance computations and memory.
- Sweep M, construction and search breadth.
- Test filters and permissions.
- Test updates, deletes and model migration.
- Segment results for important user groups.
- Retain capacity for failure and rebuilds.
- Evaluate end-to-end relevance separately.
Frequently Asked Questions
What does HNSW stand for?
Hierarchical Navigable Small World, a multilayer graph approach to approximate nearest-neighbour search.
Why use approximate search?
It can reduce query work dramatically when an acceptable recall–latency trade-off exists.
What is recall@k?
The fraction of exact top-k neighbours present in the approximate top-k result.
What does M control?
In common implementations it controls graph connectivity limits, affecting memory, build cost and recall.
What does `efSearch` control?
It controls search breadth in common APIs. Larger values usually visit more candidates.
Is HNSW exact?
Not normally. With a very broad search it may recover exact results on many queries, but exactness is not its basic guarantee.
Why are layers random?
Exponential random promotion creates many base nodes and progressively sparse express layers without hand-designing levels.
Can HNSW handle filters?
Implementations support different strategies, but restrictive filters can reduce connectivity or usable candidates.
Is cosine similarity always best for embeddings?
No. Use the metric intended by the model and validated for the task.
Does HNSW guarantee useful AI answers?
No. Retrieval is one component; model quality, data, ranking, permissions and evaluation remain essential.
Useful Next Reading
- Compare vector meaning in Recommender Systems, Similarity and Matrix Factorisation.
- Explore placement in Graph Partitioning, Cut Edges, Balance Constraints and Distributed Work.
- Compare probabilistic membership in Bloom Filters, Hash Functions, False Positives and Memory Efficiency.
- Read the original HNSW research paper.
Final Perspective
HNSW turns a vast geometric search into a navigable graph. Random hierarchy supplies express layers, neighbourhood links create routes, and a candidate frontier trades distance work for recall.
The responsible question is not “Is approximate search fast?” It is “Under which metric, data, filters and recall target is it fast, and who is missed when it fails?” Mathematics makes that trade-off visible, testable and open to improvement.