85 agentic tools audited for security incidents · Talk to the lab →
MotionticBook a call
Glossary

What is HNSW?

HNSW (Hierarchical Navigable Small World) is an approximate nearest neighbour index that links vectors into a stack of proximity graphs and searches from the sparse top layer down, finding close vectors without comparing every one.

Checked

Comparing a query against every stored vector is exact but slow at scale. HNSW trades a little accuracy for a large gain in speed. It was described by Yu. A. Malkov and D. A. Yashunin in a paper first posted in March 2016, which reports logarithmic complexity scaling for search.

It is now the default vector index in many systems, including pgvector, Redis Search and Lucene-based engines such as Elasticsearch.

How the search works

Every vector is a node in the bottom layer, linked to its near neighbours. Each higher layer holds a random subset of nodes with longer links, like an express route. A search enters at the top, moves greedily toward the query, drops a layer, and repeats until it reaches the bottom, where it refines a list of candidates.

The parameters that matter

  • m

    The maximum number of links per node in each layer. pgvector's default is 16. More links raise recall and memory use.

  • ef_construction

    The candidate list size while building the graph. pgvector's default is 64. Higher values build a better graph more slowly.

  • ef_search

    The candidate list size at query time. pgvector's default is 40. Raising it improves recall at the cost of latency, and it can be set per query.

Trade-offs and alternatives

pgvector's documentation states the trade-off plainly: HNSW has a better speed and recall balance than IVFFlat, but builds more slowly and uses more memory. That memory cost is why alternatives exist: DiskANN-style indexes such as pgvectorscale's StreamingDiskANN keep most of the graph on disk, IVF indexes partition vectors into clusters, and quantization shrinks every vector.

Filters are a second trap. When a query filters on metadata, an HNSW search can return too few results that pass the filter. pgvector 0.8.0 (November 2024) added iterative index scans to address this over-filtering.

How Motiontic's engineers apply it

Motiontic's engineers tune ef_search against recall measured on the client's own queries and filters, then size memory for the index at the expected corpus growth. When memory becomes the constraint, quantization or a disk-based index is tested against the same recall target before anything changes in production.

HNSW compared with other vector index types

HNSW compared with other vector index types
HNSWIVFFlatDiskANN-style
StructureLayered proximity graphVectors grouped into clustersGraph kept mostly on disk
Query speed and recallStrongLower at the same speedStrong, with disk reads
Build timeSlowerFasterVaries by implementation
MemoryHighLowerLow
Examplepgvector, Redis, Elasticsearchpgvectorpgvectorscale StreamingDiskANN

Common questions

What does HNSW stand for?

Hierarchical Navigable Small World. It refers to a layered graph in which each node links to near neighbours, so a search can reach any point in a few hops.

Is HNSW exact or approximate?

Approximate. It usually finds the true nearest neighbours but can miss some. Raising the search candidate list, ef_search in pgvector, improves recall at the cost of speed.

HNSW or IVFFlat in pgvector?

pgvector's documentation says HNSW has the better speed and recall trade-off, while IVFFlat builds faster and uses less memory. Many teams start with HNSW and revisit when memory becomes the limit.

Why does HNSW use so much memory?

The graph stores links for every vector across layers, and search is fastest when both the graph and the vectors sit in memory. Quantization and disk-based indexes are the usual ways to cut that cost.

Running agents that have to hold up?

Describe the agent, the systems it touches and what it must never get wrong. The first call is with a lab engineer, who will say plainly whether it is ready for production, and whether Motiontic is the right team.