What Is HNSW? The Vector Index Behind Fast Search Explained

Vector search performance is usually treated as a property of the database rather than as a set of decisions, which works until a corpus grows or a recall problem surfaces with no obvious cause. HNSW is the index behind most of those systems, and understanding its trade-offs explains a great deal of otherwise puzzling behaviour. This explainer covers it. It complements what is approximate nearest neighbor search and what is a retrieval index, and reflects FISTA Solutions' approach in AI agents delivery.

What problem does it solve?

Finding the nearest vectors to a query without comparing against every vector in the collection. Exhaustive comparison is exact and scales linearly, which becomes untenable somewhere in the millions depending on dimensionality and latency budget.

HNSW builds a structure that lets search reach the neighbourhood of the answer in a small number of steps, at the cost of occasionally missing a true nearest neighbour.

Property	Exhaustive search	HNSW
Accuracy	Exact	Approximate, tunable
Query time	Linear in corpus size	Roughly logarithmic
Memory overhead	None	Substantial
Update handling	Trivial	Deletions degrade quality
Tuning required	None	Several parameters
Suits	Small corpora	Large corpora

How does the structure work?

As a set of layered graphs. The top layer contains few nodes with long-range connections; each layer below is denser. Search begins at the top, moves greedily toward the query, descends a layer, and repeats until reaching the bottom layer where a local search finds the final candidates.

The upper layers act like express routes, carrying the search across the space quickly before the lower layers refine. That layered design is what gives the logarithmic scaling.

Which parameters matter?

Three. The number of connections per node controls graph density: more connections improve recall and increase memory. The construction search width governs how thoroughly the graph is built, affecting quality and build time. The query-time search width trades recall against latency on each request.

The last is the useful one operationally, because it can be adjusted per query without rebuilding the index — a system can search harder for queries that matter and faster for those that do not.

Why is memory the usual constraint?

Because the graph structure is stored alongside the vectors, and the overhead is significant. For large collections the index may not fit comfortably in memory, and spilling to disk degrades the latency the index existed to provide.

This is why quantization frequently accompanies HNSW in large deployments: reducing vector precision shrinks the footprint enough to keep everything resident, at a small and measurable recall cost.

When should you not use an index?

When the corpus is small. Tens of thousands of vectors can be searched exhaustively in milliseconds, exactly, with no index memory, no tuning, and trivial update handling. Many systems adopt a vector index because it is what vector databases offer, not because their scale required it.

Starting exhaustive and adding an index when measurement shows it is needed is the better order.

How are updates and deletions handled?

Insertions are supported directly. Deletions are the weakness: removing a node would damage the graph's connectivity, so implementations typically mark nodes as deleted and skip them at query time. Memory is not reclaimed and recall drifts as deleted nodes accumulate.

Corpora with high churn — frequently updated documents, rolling content — therefore need periodic full rebuilds, scheduled deliberately rather than discovered when quality has already degraded.

How should recall be measured?

Against exhaustive search on a sample of real queries from your own corpus. Take a few hundred queries, compute exact nearest neighbours by brute force, and compare against what the index returns.

Published recall figures come from standard benchmark datasets with particular dimensionalities and distributions, and they do not transfer. A configuration reporting high recall on a benchmark may perform differently on domain-specific embeddings.

What are the alternatives?

Inverted file indexes with quantization scale to very large collections with lower memory, at some recall cost and with a training step. Disk-based approaches trade latency for footprint. Each has a regime where it wins; HNSW's popularity reflects strong all-round behaviour rather than dominance everywhere.

What should teams actually do?

Measure recall on their own data, set query-time search width from that measurement rather than from a default, plan rebuild cadence against expected churn, and check whether an index was needed at all before tuning one.

What should you do first?

Check whether you need an index at all by timing an exhaustive search over your actual corpus. If it returns in a few milliseconds, the index is complexity without benefit. If it does not, measure recall at the default settings before tuning anything, because that number is the baseline every later decision is judged against.

How FISTA Solutions helps

FISTA Solutions sizes vector infrastructure against measured recall on client corpora, tunes query-time parameters rather than accepting defaults, plans rebuild cadence for corpora with churn, and recommends exhaustive search where scale does not justify an index, through AI agents, AI enablement, and forward deployed engineers. The record behind the approach is 150+ projects for 50+ companies with 99.9% uptime.

To make vector search fast without losing the results that matter, message FISTA on WhatsApp, or read what is retrieval augmentation.