HNSW index

HNSW builds a layered graph in which each vector links to its near neighbors. The top layers are sparse, for long jumps across the space; the bottom layer is dense, for fine-grained search. A query starts at the top and greedily walks toward closer vectors, layer by layer, which avoids comparing the query against every stored vector.

It is the most common vector index in practice, supported by pgvector and most vector databases, because it gives fast queries with high recall and handles inserts without a full rebuild. The alternative family, IVF-style indexes, clusters vectors and searches only nearby clusters; they build faster and use less memory but need tuning and periodic rebuilding as data shifts.

The costs are memory and build time. HNSW indexes can be large, and building one over millions of vectors takes a while. Search parameters trade recall against latency, and filtered queries can return fewer results than expected if the index scan doesn't look far enough.

Because HNSW is approximate, a quiet drop in search quality after data grows is often an index setting rather than an embedding problem. Compare against exact search on a sample to know which.