Skip to main content
Hello and welcome back. Now that HNSW is understood as a multi-layer graph, this guide shows how to build and use it in practice. We walk through how a new vector is inserted and how the structure is tuned for performance. Insertion into HNSW is a multi-step process:
  1. Assign a random maximum layer to the new vector
    Each new element is assigned a random maximum layer. Higher layers are exponentially rarer than lower ones, producing a pyramid-like topology: only a small subset of vectors appear in top layers while most vectors remain near the base. This sparsity at higher layers keeps long-range routing efficient. The distribution is controlled by a level-distribution parameter (often tied to M and implementation defaults).
  2. Navigate from the top layer down to the target layer
    Insertion starts from a global entry point (typically a node located in the top layer). At each layer, the algorithm performs a greedy search: move to the neighbor that is closer to the new vector repeatedly until reaching a local minimum (no neighbor is closer). That local minimum becomes the entry point for the next lower layer. Repeat this until you reach the layer where the new vector will be inserted.
  3. Connect the new vector to its neighbors
    For every layer where the new vector should appear, HNSW performs a best-first search (candidate list size determined by efConstruction) to find the best neighbor candidates. The algorithm then connects the new node to up to M nearest neighbors at that layer. Connections are bidirectional—if A connects to B, B also links back to A—ensuring bidirectional navigability.
  4. Prune and select neighbors (diversification)
    If connecting the new node would exceed a node’s M limit, a neighbor-selection heuristic prunes connections to keep the closest and most diversifying neighbors. This diversification preserves search quality while preventing layers from becoming overly dense.
Key parameters that control HNSW behavior
The image is a flowchart explaining the steps for HNSW (Hierarchical Navigable Small World) construction and adoption, detailing the process of inserting a new vector into the structure.
ParameterWhat it controlsTypical effect / guidance
MMaximum number of connections per node at each layerHigher M → better connectivity and recall but more memory and maintenance overhead. Common defaults: 16 or 32.
efConstructionCandidate list size during index constructionLarger efConstruction → better-connected index and higher recall, at the cost of slower indexing and more memory during build.
ef / efSearchCandidate list size during queriesLarger ef → higher recall at query time, but with increased query latency. Tune to the desired recall/latency balance.
Tuning notes:
  • Increase efConstruction and/or M to improve index quality (higher recall) — expect longer build times and greater memory use.
  • Increase query ef to improve accuracy at query time — expect longer queries.
  • Typical production strategy: tune efConstruction and M once (at index build time), then adjust ef dynamically per-query to meet latency/recall requirements.
Tune efConstruction to prioritize index-build quality and tune ef at query time to meet your recall versus latency goals. Higher values improve recall but consume more resources.
Why HNSW is popular
  • High recall: HNSW often achieves very high recall (commonly in the mid-90s to high-90s percentiles), approximating true nearest neighbors closely.
  • Very fast queries: On modern hardware, many queries run in sub-millisecond to single-digit-millisecond ranges, making HNSW suitable for real-time applications.
  • Tunable trade-offs: M, efConstruction, and ef let you balance accuracy, build time, memory, and query latency.
  • Broad ecosystem adoption: Many vector databases and libraries use HNSW as a default or recommended index (for example, Pinecone, Weaviate, Qdrant). If you use production semantic search or recommendation systems, they’re likely powered by HNSW or a variant.
The trade-off: HNSW stores explicit links between vectors, so it typically requires more memory than simpler approximations (for example, inverted-file or PQ-based methods). In many applications the extra memory cost is justified by the speed and accuracy gains.
The image explains the construction and adoption of HNSW, detailing steps for inserting a new vector and highlighting its advantages. It also lists HNSW as the default index in several platforms such as Pinecone and Weaviate.
Summary HNSW construction centers on four ideas:
  1. Assign elements to exponentially distributed layers.
  2. Navigate from a top-level entry point down using greedy search.
  3. Connect new elements to up to M neighbors per layer using a best-first search sized by efConstruction.
  4. Prune neighbors to preserve diversity and sparsity.
Properly tuning M, efConstruction, and ef lets you trade recall, indexing cost, memory, and query latency—making HNSW a practical default for production vector search. That concludes the HNSW construction and adoption overview.

Watch Video