Vector Databases
Advanced 13 min read Vector Databases

HNSW Indexes

A city map of shortcuts

HNSW builds a hierarchical graph of vectors where short links connect near neighbors and long links skip across the space. It's the default choice for low-latency semantic search — if you can stomach the RAM.

HNSWhierarchical navigable small worldgraph indexMefConstructionRAM
Prerequisites: Vector Indexing
Before we start

What you will learn

  • Explain HNSW's layered graph
  • Tune M and ef for your triangle
  • Budget HNSW memory
Introduction

What is this?

HNSW (Hierarchical Navigable Small World) organizes vectors in a multi-layer proximity graph: layer 0 has dense neighbor links, higher layers have sparser 'express lanes'. A query starts at the top, descends layers, and walks small neighborhoods to the answer — millisecond latency with excellent recall at the cost of RAM-hungry graph structure.

Motivation

Why do you need it?

  • Best-in-class latency/recall balance in practice.
  • Understandable behavior: M controls links, ef controls search breadth.
  • Your RAG stack likely uses HNSW by default — tune it deliberately.
  • Memory math (M × 8 bytes × nodes) decides RAM budget before you buy.
Think about it

Mental model

Imagine

A city with express highways and local streets

Think of

HNSW layers

Highways (upper layers) carry you quickly across town via a few big hops; local streets (layer 0) refine to your exact destination. You enter a freeway, exit near the target, then walk street-by-street to the door — fast, reliable, but the map itself is huge.

Mechanics

How it works

  • Insert: each new vector joins layer 0, and with probability p also higher layers (fewer).
  • Layer 0 links each node to ~M nearest neighbors; upper layers fewer/different links.
  • Search: from the top layer's entry, greedily descend to layer 0, expanding ef candidates.
  • efConstruction (build time) vs efSearch (query time) control accuracy.
  • Memory ≈ nodes × avg-links × 8 bytes (roughly (M+4)×8 × nodes).

Navigating down the layers.

Entry
Greedy hops
Descend
Layer 0
Result
Real world

In production

  • Default for RAG semantic search: HNSW M=16-64, ef=query-latency tuned.
  • Hybrid stacks filter inside the graph walk when the DB supports it.
  • Multi-million-row services split the graph (shards) — HNSW memory per node stays sane.
Guidelines

Best practices

  • Tune efSearch dial from 10 upwards until recall@k plateaus.
  • Set M considering RAM: doubling M roughly doubles link memory.
  • Batch rebuilds during off-peak to fight insert-driven graph rot.
  • Monitor recall@k on a fixed sample weekly.
Watch out

Common mistakes

  • Cranking ef to 800 'for accuracy' and paying 20x latency.
  • Ignoring that small corpus = simple linear search may beat HNSW entirely.
  • Inserting millions one-off into a graph without periodic rebuild.
Root cause analysis

Common issues

Error
Recall@k drops after mass inserts
Root cause

HNSW graph degeneration

Fix

Increase ef temporarily; schedule graph rebuilds.

Error
HNSW eats the server RAM
Root cause

M/ef too high or node dims underestimated

Fix

Model memory; drop to smaller M or move to IVF/PQ.

When things break

Debugging tips

  • Recall varies wildly per query → locality of query embeddings; sample more.
  • RAM spike at ingest → efConstruction high and parallel inserts forking graphs.
  • Searches slower after deletions → graph rot; rebuild.
Interviews

Interview checkpoint

Test yourself

Quick quiz

0/2
1

In HNSW, higher layers contain…

2

Doubling the M parameter roughly doubles HNSW link memory.

Go deeper

Official documentation

HNSW paper
spec
Qdrant HNSW docs
docs