Inside HNSW: The Graph Algorithm That Makes Your AI Agent's Memory Fast (and Sometimes Wrong)

Every time an AI agent calls something like memory.search(query, limit=5), a graph traversal runs underneath it that most developers never look at. It's not a database index in the traditional sense — it's closer to a probabilistic subway map, and understanding how it's built explains both why vector search is fast and why it occasionally hands your agent the wrong memory with full confidence.

The algorithm is called HNSW — Hierarchical Navigable Small World graphs. It's the default index type in Faiss, hnswlib, pgvector, Qdrant, Weaviate, and most managed vector stores, which means if you've built a RAG pipeline or given an agent long-term memory, HNSW is already running your retrieval whether you chose it explicitly or not.

The problem it solves

Exact nearest-neighbor search means comparing your query vector against every stored vector and sorting by distance. For 10,000 memories at 768 dimensions, that's fine — a few milliseconds. At 10 million memories, brute force means scanning 10 million floating-point comparisons per query, every query. That doesn't scale, and it definitely doesn't scale to an agent calling memory search dozens of times per conversation.

HNSW trades exactness for speed. It doesn't guarantee it finds your true nearest neighbor — it guarantees it finds a very good neighbor, almost all of the time, in roughly logarithmic time instead of linear time. That "almost all of the time" is the detail that matters once you're building on top of it.

The structure: layers of shortcuts

HNSW builds a multi-layer graph. Picture a skip list, but in vector space instead of a sorted array.

• Layer 0 (the bottom) contains every vector you've inserted, each one connected to its nearest neighbors — typically 16 to 64 edges, controlled by a parameter called M.
• Higher layers contain progressively smaller random subsets of those same vectors, with sparser connections. A vector's odds of appearing in layer 3 are exponentially smaller than appearing in layer 0 (the assignment uses a randomized exponential decay, same trick skip lists use).

The top layers act as highways — a handful of nodes with long-range connections that let a search jump across the vector space quickly. The bottom layer is the local street grid — dense, short connections for fine-grained precision once you're close to the answer.

How a search actually runs

When you call .search(query_vector, k=5), here's what happens under the hood:

1. Start at a fixed entry point in the topmost layer.
2. Greedily walk toward the neighbor closest to your query vector, one hop at a time, until no neighbor at this layer is closer than your current node.
3. Drop down one layer, using your current position as the new starting point.
4. Repeat the greedy walk at this layer, which is denser and more accurate.
5. Once you reach layer 0, instead of taking just the single closest node, HNSW keeps a candidate list of size ef (the search-time beam width) and explores that many promising paths before returning the top k.

This is why HNSW search is roughly O(log n) instead of O(n): each layer eliminates most of the graph before you ever reach the dense bottom layer where the real comparisons happen.

The three knobs that actually matter

Most HNSW tuning guides list parameters without explaining what breaks when you get them wrong. In practice, three matter:

M (edges per node, insertion time). Higher M means a denser graph — better recall, but more memory and slower inserts. Going from M=16 to M=48 roughly triples index memory for maybe a 3-5% recall gain past a certain dataset size. For memory stores under a few million vectors, M=16-32 is almost always the right range; don't reach for 64 unless benchmarks tell you to.

efConstruction (candidate list size during insertion). This controls how thoroughly the graph is built when a vector is added. Low efConstruction (say, 40) builds fast but leaves the graph with worse long-term recall — and you can't fix it later without rebuilding. This is the parameter people forget until they're debugging why search quality degraded after a bulk import: it was set too low at write time, not read time.

efSearch / ef (candidate list size during query). This is the one lever you can tune live, per query, without rebuilding anything. Raise it and you trade latency for recall. On the classic glove-100 ann-benchmark dataset, going from ef=10 to ef=100 typically moves recall@10 from around 85% to 98%+, at maybe 3-4x the query latency — still single-digit milliseconds either way at that scale.

Why this matters specifically for agent memory

A vector database used for product search can tolerate 85% recall — a slightly-off search result is a minor UX blemish. An agent's long-term memory is different: if the memory holding the user's actual preference or a past correction doesn't make it into the top-k, the agent doesn't know it's missing anything. There's no error, no exception, no log line. The agent just answers as if that memory never existed.

This is the practical reason to treat ef as a first-class config value in a memory system, not an implementation detail buried in a client library default. Two changes are worth making explicitly:

• Set efSearch higher than the library default for anything retrieval-critical. Most client libraries default ef somewhere in the 10-50 range, tuned for throughput benchmarks, not recall. For agent memory where a miss is invisible and costly, bias toward recall — ef=100-200 is still fast enough for interactive use, and the latency difference is milliseconds a user will never notice.
• Re-embed and rebuild, don't just re-tune, after large deletions. HNSW graphs degrade gracefully on insert but not on delete — most implementations soft-delete (mark and skip) rather than actually removing edges, which means a memory store with heavy churn slowly accumulates dead-end paths that waste traversal steps and quietly lower effective recall. If your agent forgets and relearns things constantly, periodic index rebuilds aren't housekeeping, they're a correctness fix.

The single takeaway worth carrying into any vector-backed memory system: HNSW's speed comes from being probabilistically honest, not exact. Every default configuration is a bet about how much wrongness is acceptable, made by someone who was optimizing for a benchmark, not for whether your agent remembers what your user told it last week. Read the ef values before you trust the recall.