HNSW internals: M, ef, memory and the delete problem

What it is

Hierarchical Navigable Small World is a graph-based approximate nearest neighbour index. Vectors are nodes; each node has edges to a bounded number of near neighbours; and the graph is layered, with sparse long-range links at the top and dense local links at the bottom. Search enters at the top layer, greedily walks toward the query, drops a layer, and repeats.

Layer 2   A -------------------- F              sparse, long hops
          │                      │
Layer 1   A ------ C ----------- F ------ H     medium
          │        │             │        │
Layer 0   A - B - C - D - E - F - G - H - I     dense, all vectors

The layer assignment is probabilistic: a vector is inserted into layer $l$ with probability decaying exponentially, so layer 0 holds every vector, layer 1 roughly $1/m_L$ of them, and so on. That gives the same asymptotic shape as a skip list, which is exactly the analogy to use: HNSW is a skip list in metric space.

Commonly confused with an exact index. It is approximate: recall is a tuned parameter, not a guarantee, and a query can miss true neighbours. Also commonly confused with "a vector database", which is a product; HNSW is one index structure inside it, and IVF-PQ, ScaNN and DiskANN are others with different trade-offs.

The problem it solves

Exact nearest neighbour search over $n$ vectors in $d$ dimensions is $O(nd)$ per query. At 50 million vectors of 768 dimensions that is roughly 38 billion multiply-adds per query, which is hundreds of milliseconds even with good SIMD.

Tree-based indexes (kd-trees, ball trees) degrade to linear scan above roughly 20 dimensions, because the volume of a high-dimensional space concentrates and pruning stops working. That failure is the reason graph methods exist, and naming it is a useful signal that you understand why the obvious structures were abandoned.

HNSW gives approximately logarithmic search complexity with recall typically above 0.95, at the cost of memory for the graph and an expensive build.

Mechanics

The two build parameters

M                 Number of bidirectional edges per node at
                  layers above 0. Layer 0 gets 2*M ("M0").
                  Typical: 16 to 64.

efConstruction    Size of the dynamic candidate list during
                  insertion. Controls how hard the algorithm
                  looks for good neighbours when linking a new
                  node. Typical: 100 to 500.

$M$ is the memory/recall knob and it is permanent. More edges means better connectivity and higher achievable recall, and it costs memory linearly and slows every traversal step. You cannot change it without rebuilding.

efConstruction is a build-time-only cost. Higher values produce a better graph (higher recall at the same search-time cost) and take longer to build. It does not affect query memory or query speed at all, which makes it the parameter to spend on: you pay once at build time and benefit on every query forever.

Effect of efConstruction on a 1M-vector, 768-dim index (shape,
not exact figures, which are corpus-dependent):

efConstruction   build time   recall@10 at efSearch=64
     40             1.0x           ~0.92
    100             1.8x           ~0.96
    200             3.1x           ~0.975
    500             7.0x           ~0.98    <- diminishing returns

The recommendation that follows: set efConstruction as high as your build budget allows, then tune recall at query time with efSearch. Teams routinely leave efConstruction at the default and then fight for recall with efSearch, which costs latency on every single query instead of once at build.

The search parameter

efSearch (or just "ef")   Size of the dynamic candidate list during
                          search. Must be >= k. Higher = better
                          recall, more distance computations,
                          more latency. Tunable per query.

Typical shape on a 10M-vector index, k=10:

ef      recall@10    latency (relative)
 10       0.82           1.0x
 32       0.94           1.8x
 64       0.97           3.0x
128       0.985          5.2x
256       0.992          9.4x
512       0.996         17.0x

Recall follows a diminishing-returns curve and latency does not, which is the tuning insight: the region around ef of 64 to 128 is usually where the curve bends, and pushing past it buys fractions of a percent of recall for multiples of latency.

efSearch is per query, which is the operationally useful property. You can serve a high-value query at ef 256 and a background one at ef 32, and you can drop ef under load as a degradation lever, which is what the multilingual search design does.

The memory formula

This is the calculation to be able to produce, because it decides the deployment.

Per vector:
  raw vector:  d x bytes_per_component
  graph edges: (M0 + M x (num_layers_above_0 - 1)) x 4 bytes
               In practice, edges are dominated by layer 0
               because layer 0 holds every vector:
               ~ M0 x 4 bytes = 2M x 4 = 8M bytes per vector
               plus a small tail for upper layers (~1/(m_L - 1)
               of the vectors, so typically <10% extra)

Rule of thumb:
  bytes/vector ≈ d x bytes_per_component + 8 x M x 1.1

Worked: 50M vectors, d = 768, M = 32

fp32 vectors:  768 x 4  = 3,072 bytes
int8 vectors:  768 x 1  =   768 bytes
graph:         8 x 32 x 1.1 ≈ 282 bytes

fp32 total: 50e6 x (3072 + 282) = 167.7 GB
int8 total: 50e6 x ( 768 + 282) =  52.5 GB

*** Quantising the vectors takes the index from "needs a
    special machine" to "fits a standard one". ***
    The graph is 282 bytes either way and becomes a much
    larger relative share (27% of the int8 index).

Two conclusions from that arithmetic:

Quantisation is the dominant memory lever, not $M$. Going from fp32 to int8 saves 2,304 bytes per vector; halving $M$ from 32 to 16 saves 141. Teams reduce $M$ to save memory and lose recall for a tenth of the benefit.

But at low precision the graph becomes significant. In the int8 case the graph is 27 percent of the index, so once you have quantised, $M$ starts to matter.

Choosing M

M = 8-12    Low-dimensional data (d < 100), or memory-critical.
            Lower achievable recall ceiling.
M = 16      A reasonable default; most libraries default here.
M = 32-48   High-dimensional (d >= 768) or high-recall
            requirements. This is where most text-embedding
            workloads land.
M = 64+     Diminishing returns; the graph starts to dominate
            memory and each traversal step examines more edges.

Higher intrinsic dimensionality needs higher $M$, because the local neighbourhood structure is harder to capture with few edges. That is the practical reason 768- and 1024-dimensional text embeddings want $M$ of 32 or more while a 64-dimensional recommendation embedding is fine at 16.

The delete problem

HNSW has no true delete, and this is the operational fact that surprises people.

Why not: removing a node would break the graph. Its neighbours
lose an edge each, connectivity degrades, and repairing properly
means recomputing neighbour lists for every node that pointed at
it, which cascades.

What implementations actually do:
  SOFT DELETE  Mark the node deleted. It stays in the graph and
               is still traversed (it is a useful routing node),
               but it is excluded from results.

The consequences:

1. Memory is not reclaimed. A deleted vector still occupies its
   d x bytes plus its edges.

2. Search does more work. Traversal still visits deleted nodes
   and must fetch more candidates to fill k results.

3. Recall degrades as the deleted fraction grows, because the
   effective ef is reduced: with 30% deleted, an ef of 64 yields
   roughly 45 usable candidates.

4. An UPDATE is a delete plus an insert, so a high-churn
   workload accumulates tombstones fast. A vector re-embedded
   monthly across a year leaves 11 tombstones behind it.

The fix is periodic rebuild, and it should be designed in from the start rather than discovered:

Monitor:  deleted_count / total_count
Rebuild:  when it exceeds ~20-30%

Mechanism: build the new index offline into a new index/alias,
swap atomically, drop the old. Same alias-swap pattern as a
zero-downtime reindex.

Some systems mitigate rather than rebuild: Vespa and Weaviate perform incremental repair by relinking a deleted node's neighbours to each other, which keeps connectivity and still leaves memory unreclaimed. Lucene's HNSW implementation ties deletes to segment merges, so the merge that rewrites a segment also rebuilds its HNSW graph, which means the delete problem is handled by the existing segment lifecycle rather than needing a separate rebuild. That is a real architectural advantage of the Lucene approach and it is worth naming.

Build cost

Insertion is O(log n) distance computations x efConstruction,
so building is O(n log n x efConstruction) and it is
CPU-bound and highly parallel across insertions.

Practical: 10M vectors at d=768, M=32, efConstruction=200
  ~1-3 hours on 32 cores, depending on the implementation.

Consequence: rebuilds are scheduled jobs, not online operations,
which reinforces the build-offline-and-swap pattern.

Production evidence

Malkov and Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" (2016, IEEE TPAMI 2018) is the original, including the layer-probability construction and the heuristic neighbour selection that makes the graph navigable rather than merely connected.

hnswlib is the reference implementation and its README documents the $M$, efConstruction and ef semantics plus the memory formula, and it is explicit that deletes are soft.

Lucene's HNSW implementation (used by Elasticsearch and OpenSearch) integrates the graph with the segment lifecycle, so a merge rebuilds the graph for the merged segment. That is why Lucene-based vector search does not need a separate rebuild schedule for deletes, and it is a genuinely different operational profile from a standalone hnswlib index.

FAISS implements HNSW alongside IVF and PQ and supports composite indexes (HNSW32,PQ64), which is the practical route to combining graph navigation with quantisation.

ANN-Benchmarks (Aumüller, Bernhardsson and Faithfull) is the standard recall-versus-QPS comparison across implementations and datasets, and it is the right citation for claims about relative performance rather than vendor benchmarks.

DiskANN (Subramanya et al., NeurIPS 2019) is the main alternative for larger-than-memory indexes: a graph designed so that traversal is SSD-friendly, trading latency for the ability to index billions of vectors on one machine.

The debate

The case for HNSW: the best recall-versus-latency curve of the practical methods at in-memory scale, no training step (unlike IVF-PQ, which needs a representative sample to learn centroids), and it handles incremental insertion naturally.

The case for IVF-PQ: dramatically lower memory. Product quantisation compresses a 768-dimensional fp32 vector from 3,072 bytes to under 100, which puts a billion vectors on a machine that could hold 20 million with HNSW. The cost is lower recall at equal configuration and a training step.

The case for DiskANN: billions of vectors on one machine by keeping the graph on SSD with a memory-resident compressed representation for routing. The right answer when the index genuinely does not fit in RAM and you are unwilling to shard heavily.

The case for brute force: below roughly 100,000 vectors, exact search with SIMD is fast enough (single-digit milliseconds), always correct, has no build step and no parameters, and handles deletes trivially. A surprising number of production "vector search" problems are this size, and building an HNSW index for them is pure overhead.

My position: HNSW with int8-quantised vectors and $M$ of 32 for text embeddings, with efConstruction set as high as the build budget allows and recall tuned at query time via efSearch.

The specific reasoning on quantisation: it is the dominant memory lever by an order of magnitude over $M$, and the recall cost of int8 on normalised text embeddings is typically under a point, which is far cheaper than the recall lost by halving $M$ to save a tenth as much memory. Teams reduce $M$ because it is the parameter they know about.

On efConstruction, the argument is that it is a one-time cost with a permanent benefit, so under-spending on it is strictly worse than under-spending on efSearch. A better graph gives higher recall at every future query's latency budget.

The thing I would design for from the start is the delete problem, because it is not obvious and it degrades silently. Soft deletes mean memory is never reclaimed, traversal still visits tombstones, and effective recall falls as the deleted fraction grows. So: monitor deleted fraction, rebuild offline and alias-swap above roughly 20 to 30 percent, and size capacity assuming the index carries tombstones. A high-churn workload where every vector is re-embedded monthly leaves eleven tombstones per vector after a year, and nobody plans for that.

Where I would push back on the premise: check the corpus size before building an index at all. Under about 100,000 vectors, brute force with SIMD is single-digit milliseconds, exactly correct, and has no build, no parameters and no delete problem. That threshold is higher than people expect and a meaningful share of vector-search projects are below it.

Follow-up Q&A

"Explain HNSW in one paragraph." It is a skip list in metric space. Vectors are graph nodes with edges to near neighbours, and the graph is layered, with a vector appearing in layer $l$ with exponentially decaying probability, so the top layer is sparse with long hops and layer zero holds everything with dense local links. Search enters at the top, greedily moves toward the query, drops a layer and repeats, which gives approximately logarithmic complexity. It is approximate: recall is a tuned parameter, not a guarantee.

"What do $M$ and ef control?" $M$ is edges per node, set at build time and permanent: more edges means better connectivity and a higher recall ceiling, costing memory linearly and slowing each traversal step. efConstruction is how hard insertion looks for good neighbours, a build-time-only cost that affects graph quality forever without costing query memory or speed. efSearch is the candidate list size at query time, tunable per query, trading recall against latency. The practical advice is to spend on efConstruction, because you pay once and benefit on every query.

"How much memory does a 50 million vector index need?" Roughly $d$ times bytes per component, plus about eight times $M$ for the graph. At 768 dimensions with $M$ of 32, that is 3,072 plus about 282 bytes in fp32, so about 168 gigabytes. Quantised to int8 it is 768 plus 282, so about 53 gigabytes. Which is the important observation: quantisation saves 2,300 bytes per vector and halving $M$ saves 141, so quantisation is the lever by an order of magnitude, and teams cut $M$ because it is the parameter they know.

"How do deletes work?" They do not, really. HNSW has no true delete because removing a node breaks the graph, and repairing it properly cascades. So implementations soft-delete: the node stays and is still traversed as a routing node but is excluded from results. Memory is never reclaimed, traversal still visits tombstones, and effective recall falls as the deleted fraction grows, since an ef of 64 with 30 percent deleted yields around 45 usable candidates. An update is a delete plus an insert, so a high-churn workload accumulates tombstones fast.

"So what do you do about it?" Monitor the deleted fraction and rebuild offline into a new index, then alias-swap, above roughly 20 to 30 percent. Design that in from the start rather than discovering it, and size capacity assuming tombstones. Worth knowing that Lucene's implementation avoids the separate rebuild because HNSW graphs are rebuilt when segments merge, so the existing segment lifecycle handles it, which is a real operational advantage over a standalone index.

"When would you not use HNSW?" Three cases. Below about 100,000 vectors, brute force with SIMD is single-digit milliseconds, exact, and has no build, parameters or delete problem, and more projects are in this range than people expect. When memory is the binding constraint, IVF-PQ compresses a 768-dimensional vector to under a hundred bytes, which puts a billion vectors where HNSW fits twenty million. And when the index genuinely will not fit in RAM and you do not want to shard heavily, DiskANN keeps the graph on SSD with a memory-resident compressed representation for routing.

"What breaks when you add filters?" Recall, and it breaks off a cliff rather than degrading. The traversal assumes a connected graph, and filtering out most nodes can disconnect the regions holding qualifying results, so the search cannot reach neighbours that exist. At around one percent selectivity you can lose most of your recall, silently. The mitigations are exact search over the accessible set when it is small, partitioned indexes when the filter is a partition key, and a widened ef otherwise.

"How long does a build take?" Insertion is logarithmic in distance computations times efConstruction, so the build is $O(n \log n \cdot \text{efConstruction})$, CPU-bound and highly parallel. Practically, ten million 768-dimensional vectors at $M$ of 32 and efConstruction of 200 is one to three hours on 32 cores. Which is why rebuilds are scheduled jobs and why the build-offline-and-alias-swap pattern is the operational shape rather than in-place modification.

Common misconceptions

"HNSW is exact if you set ef high enough." It is approximate at any ef. Very high ef approaches exhaustive search and at that point you have paid for a graph you are not using.

"Reduce $M$ to save memory." Quantisation saves an order of magnitude more and costs less recall. $M$ only becomes significant once the vectors are already quantised.

"efConstruction affects query performance." It affects graph quality, which affects recall at a given efSearch. It costs nothing at query time, which is why it is the parameter to spend on.

"Deleted vectors free memory." They are tombstones. Memory is reclaimed only by a rebuild, or by a segment merge in Lucene-based implementations.

"HNSW is always the right vector index." Under 100k vectors, brute force wins on every axis. Above memory capacity, IVF-PQ or DiskANN wins.

Interview delivery note

Give the skip-list analogy first, because it makes the structure immediately clear: "HNSW is a skip list in metric space. Layered graph, top layer sparse with long hops, layer zero holds every vector with dense local links, and a vector appears in layer $l$ with exponentially decaying probability. Search enters at the top, greedily walks toward the query, drops a layer, repeats. Approximately logarithmic."

Separate the three parameters by when you pay for them, which is the practical framing: "$M$ is edges per node, build time, permanent, costs memory. efConstruction is graph quality, a one-time build cost with a permanent benefit and zero query cost. efSearch is per query and trades recall against latency. So spend on efConstruction, because you pay once and benefit forever, and teams get this backwards: they leave it at the default and then fight for recall with efSearch, which costs latency on every query."

Produce the memory formula, because very few candidates can: "Roughly $d$ times bytes per component, plus eight times $M$ for the graph. Fifty million 768-dimensional vectors at $M$ of 32 is about 168 gigabytes in fp32 and 53 in int8. Which tells you quantisation is the lever: it saves 2,300 bytes per vector where halving $M$ saves 141."

Volunteer the delete problem, because it is the operational fact people miss: "And the thing I'd design for from the start is that HNSW has no real delete. Removing a node would break the graph, so implementations soft-delete: the node stays, is still traversed, and is excluded from results. Memory is never reclaimed and effective recall falls as the deleted fraction grows. A workload that re-embeds every vector monthly leaves eleven tombstones per vector after a year, so monitor the deleted fraction and rebuild-and-swap above twenty or thirty percent."

And the judgement close: "though I'd check the corpus size first. Under about a hundred thousand vectors, brute force with SIMD is single-digit milliseconds, exact, with no build, no parameters and no delete problem. That threshold is higher than people expect."

The Staff & Team Lead Interview Reference