Pruning strategies in HNSW graphs
Pruning in HNSW is the process of limiting which neighbors a node keeps, so that each node has at most M bi-directional links (see defining M). Pruning controls memory use, keeps the graph navigable, and influences recall and latency.
Summary
- After finding candidates (via efConstruction), prune to M closest or use a “diverse” heuristic so retained neighbors aren’t too similar. Reduces memory and can speed search; too much pruning can lower recall.
- Pruning happens at insert/build time only; query only traverses existing edges. Standard approach: select from candidates using distance and optionally diversity.
- Pipeline: search for candidates → rank by distance (and diversity) → keep top M → create bi-directional edges; reciprocal updates may trigger pruning on existing nodes.
- Trade-off: aggressive pruning saves memory and can reduce query branching but may drop useful “bridge” links; tune M and the pruning rule with recall and memory in mind.
- Practical tip: use default pruning (M nearest) first; if recall is low for your M, try diversity-based selection or increase M and efConstruction so candidates are better.
How pruning works
When a new node is inserted, the algorithm finds candidate neighbors (using an internal search with efConstruction-sized candidate list) and then prunes that set to the M closest (by the chosen distance metric). Different implementations use different rules: keep the M nearest, or use a “diverse” heuristic so that retained neighbors are not too similar to each other, improving coverage. Pruning can be applied when extending the neighbor list (e.g. only add a candidate if it is closer than the worst current neighbor or improves diversity).
When a new node N is linked to an existing node E, E’s neighbor list may grow beyond M; then E must also be pruned (drop the worst or least diverse link) to maintain at most M neighbors. So pruning is applied both when selecting the new node’s links and when updating existing nodes that gain a new neighbor.
Simple nearest vs. diverse pruning
Simple “M nearest” pruning keeps the M candidates with smallest distance to the new node. It is fast and works well for many datasets. “Diverse” pruning tries to keep neighbors that span different directions—e.g. by iteratively adding the candidate that is farthest from (or least similar to) the already selected set, or by enforcing a minimum angle or distance between chosen neighbors. Diversity helps when data has tight clusters or when M is small, so that the M links do not all point to the same region.
Pipeline: from candidates to M links
The pipeline: (1) run approximate search to get a candidate set of size up to efConstruction; (2) optionally compute diversity scores or order by distance; (3) select up to M neighbors according to the pruning rule; (4) create bi-directional edges; (5) for each existing node that gained a new link, prune its list back to M if necessary. All of this happens at build/insert time; at query time the graph is fixed and search only follows existing edges.
Trade-offs and practical tips
Aggressive pruning reduces memory consumption and can speed up search by reducing the number of edges to follow, but too much pruning may drop links that would have led to true nearest neighbors, lowering recall. Tuning M and the pruning rule is part of balancing build cost, memory, and query quality. Practical tip: start with M nearest; if recall is low or the graph has many “bottleneck” nodes, try a diversity heuristic or increase M.
Frequently Asked Questions
What is “diverse” pruning?
Keeping neighbors that are not too similar to each other (e.g. by angle or distance), so the set covers more directions and can improve recall.
When is simple “M nearest” enough?
For many datasets, keeping the M closest candidates works well. Diversity heuristics help when data has tight clusters or when M is small.
Does pruning happen at query time?
No. Pruning is done at insert/build time when choosing which M links to keep. Query only traverses existing edges.
Can I prune existing nodes later?
Not in standard HNSW. Graph is built incrementally; to “re-prune” you’d typically rebuild or run a repair pass that rewrites neighbor lists.