HNSW
Hierarchical Navigable Small World: a layered proximity graph searched greedily. The default in-RAM ANN index in pgvector, Qdrant, Lucene, Vespa.
HNSW stores vectors as points in a graph where each point links to a handful of nearby points. A few points also appear on sparser 'express' layers above. A search starts at the top layer, hops toward the query, drops down a layer, and repeats until it reaches the bottom layer, where it explores the neighbourhood more carefully. It is fast and accurate but keeps everything in memory.
Travelling by plane to the right country, train to the right city, then walking the last few streets.
Leaving ef_search at the library default and concluding the embedding model is weak. pgvector's default of 40 is tuned for speed; at k=20 with filters it can return fewer than k rows. Sweep ef_search against exact recall on your data before any model comparison.
Each vector gets a random top layer (exponentially fewer nodes per layer). M = links per node on upper layers (layer 0 gets 2·M); ef_construction = candidate list size while inserting; ef_search = candidate list size while querying and must be ≥ k. Memory per vector ≈ vector bytes + ~2·M·4 bytes on layer 0 (+ small upper-layer overhead): M=16 adds ~128–200 B per vector. Defaults: pgvector m=16, ef_construction=64, hnsw.ef_search=40; Qdrant m=16, ef_construct=100; Vespa max-links-per-node 16, neighbors-to-explore-at-insert 200; FAISS HNSW32 means M=32. Recall rises steeply with ef_search up to ~100–200 then saturates while latency grows roughly linearly. Deletes are tombstones; heavy churn degrades connectivity until a rebuild or Compaction & soft delete. Build is CPU-heavy: pgvector builds ~10M × 768-d in tens of minutes with maintenance_work_mem large enough to hold the graph and parallel workers enabled — if the graph spills out of memory, build time jumps by an order of magnitude.
M=16, ef_construction=64–128, ef_search=100 (≥ 5× k), cosine via normalised vectors + inner product. pgvector: halfvec for > 2,000 dims, maintenance_work_mem ≥ graph size for builds, hnsw.iterative_scan = relaxed_order (0.8+) when filtering.
Developer-docs index in pgvector, 6M chunks × 1024-d halfvec. CREATE INDEX ... USING hnsw (embedding halfvec_ip_ops) WITH (m = 16, ef_construction = 128); with maintenance_work_mem = '24GB' and 8 parallel workers: ~40 min build, index ≈ 13 GB. At query time SET hnsw.ef_search = 100: p50 2.1 ms, recall@10 0.97 vs exact. Leaving the default 40 gave 0.92 recall and p50 1.1 ms; 400 gave 0.995 at 6.8 ms.
Name the three knobs and what each costs: "M buys recall with memory and build time, ef_construction buys graph quality at build time only, ef_search buys recall with query latency — and it's the only one I can change without a rebuild." Expect the filtered-search follow-up: restrictive filters break HNSW's greedy walk; mention pgvector 0.8 iterative scans, Qdrant's filter-aware graph, or ACORN.
Numbers worth knowing
- Link overhead
- ~128–200 B per vector at M=164-byte neighbour ids, 2·M links on layer 0
- Recall@10
- 0.92 → 0.97 → 0.995ef_search 40 → 100 → 400, M=16, 1024-d
- Query latency
- ~1 / 2 / 7 mssame sweep, single thread, index in RAM
How to decide
| When | Do this |
|---|---|
| Recall short but latency headroom exists | Raise ef_search first (no rebuild). |
| Recall short even at ef_search 400 | Rebuild with M=32 or ef_construction=200; check vectors are normalised. |
| Index no longer fits RAM | Quantize vectors (int8/binary + rescoring) or move to IVF-PQ / DiskANN-style on-disk indexes. |
Cost maths
Memory = N × (dims × bytes + ~2·M·4). 10M × 768-d float32, M=16 → 10M × (3,072 + 128) ≈ 32 GB. Same with halfvec: 10M × 1,664 ≈ 17 GB; with int8 scalar quantization (Qdrant): ~9 GB in RAM + originals on disk for rescoring. At ~$0.43/hr per 64 GB node (illustrative, Oct 2026), float32 → halfvec saves one node pair per 10M vectors with 2 replicas (~$620/month).
Operating it
- Leave pgvector when: index > ~50% of instance RAM, builds exceed your maintenance window, or vector QPS starts competing with OLTP queries
- Delete/update rate > 10% of the index per week — schedule rebuilds or use an engine with segment compaction
- Recall at target latency < 0.95 — raise M or quantize to buy back latency
- Rows returned < k for filtered queries — alert above 1%
- Recall@10 vs exact on sampled queries — alert below 0.95
- Index size / RAM and build duration — alert at 70% RAM or build > 2 h
When it goes wrong
A tenant-scoped search over a financial-filings index returned 3 results for k=10, and sometimes 0.
Logs showed result counts < k for 18% of filtered queries; recall audit vs exact search was 0.4 on small tenants.
pgvector HNSW applied the tenant filter after the graph walk; with ef_search=40 and tenants holding 0.5% of rows, almost every candidate was filtered out.
Upgraded to pgvector 0.8 iterative index scans, raised ef_search to 200 for filtered queries, and moved the three largest tenants to partitions with their own index (see Metadata filtering (pre, post, filtered ANN)).
Related terms
Where it shows up
Sources
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — Malkov & Yashunin, 2016paper
- pgvector: open-source vector similarity search for Postgres — pgvector project, 2026docs
- Qdrant documentation: Indexing — Qdrant, 2026docs
- Vespa documentation: Nearest neighbor search — Vespa.ai, 2026docs
Check yourself
Three questions. Every option is explained once you answer.