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.
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.
HNSW builds a multi-layer graph. Picture a skip list, but in vector space instead of a sorted array.
M
.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.
When you call .search(query_vector, k=5)
, here's what happens under the hood:
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.
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.
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:
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.