Understand HNSW: Why Your Vector Search Returns Garbage (Build your own minimalist HNSW from…

A developer explains that poor vector search results in RAG systems often stem from the HNSW approximate nearest neighbor algorithm rather than embedding models, and demonstrates how to build, break, and tune an HNSW index from scratch to improve recall.

I still remember that query. Typed in “how to cancel my subscription”, and the result that came out was an article that explained how to reset a forgotten password. Well, that seems wrong, and that too, in a way that it made no sense given how obviously related those two concepts should have been in embedding space. Blamed the embedding model first. Swapped it for a bigger one. SAME RESULT Spend two days convincing myself that I had a data quality problem before I finally looked one layer lower, past the embeddings, into the thing which actually decided which vectors get compared at query time. That specific layer is called HNSW, and let me tell you, almost nobody building RAG systems today actually understand what it is doing on their behalf. The article you are going to read will fix that. We will build a working HNSW index from scratch, and then break it deliberately, watch the recall collapse with real numbers, and then tune our way back out of the mess. So this is going to be real code, real measurements, running and printing from my own machine. Here is the raw scenario, and I could bet real money that you have lived some version of it. You have a document that is obvious, semantically. The user’s query and the correct answer share almost identical language. You would bet your job that the vector database returns it in the top three results. However, it returns something really different, or nothing useful at all. And your actual answer sits somewhere buried at rank forty, invisible to your top-k cutoff. Now, 90% of the time, the blame goes to the embedding model. That instinct is usually wrong. Embedding models are remarkably consistent. If two pieces of text are semantically close, the vectors representing them land close in that high-dimensional space almost every time. The relationship that you are looking for is genuinely there, sitting in the math, just waiting to be found. Interesting enough, the part that fails silently is the search itself. Your vector database is not comparing your query against every single vector in the whole collection. It is taking a shortcut, and that shortcut has a name, “ Approximate Nearest Neighbor ”, or ANN. HNSW is basically the graph structure that most modern vector databases use to implement it, and that is the actual usual suspect behind the “obviously related result never showed up” problem. Nobody looks there. And everybody should. Majority of the people picture vector search as a straightforward operation. Query vector - Compare against every stored vector using cosine similarity or Euclidean Distance - Return closest match This right above, is called Brute Force Search , and it is correct. It always finds the true nearest neighbors, no exceptions. Also, it is completely impractical past a few hundred thousand vectors. Brute force search scales linearly with the number of the stored vectors. So, if you double your collection, you double the time every single query takes. At about ten thousand vectors, this would be barely noticeable. However, at 10 Million vectors, a query that used to take two milliseconds is now gonna be taking two seconds, and trust me, nobody is gonna be waiting two seconds fro a search result inside a chat interface. So, every production vector database quietly makes a trade on your behalf. It sacrifices a small amount of exactness for a massive amount of speed. So, instead of comparing your query against every vector, it uses a graph structure to intelligently skip toward the right neighborhood and only examines a small fraction of the total collection. That trade is not necessarily a flaw. It is the entire reason vector search works at scale at all. But it is more of a dial, not a fixed setting, and if you never touch that dial, you are living with whatever default the library shipped with, better or worse HNSW stands for Heirarchical Navigable Small World Graphs. Forget that phrase for a sec. Let me explain it in a more simpler way. Picture a skip list, the classic data structure for the fast ordered search. A skip list has multiple layers. The top layer has very few entries, and they are spaced far apart, letting you jump across large distances quickly. Each layer below has progressively more entries, and letting you narrow in with increasing precision, until the bottom layer contains everything. HNSW is that same idea, just translated into vector space, with graphs instead of sorted lists . The top layer of the HNSW graph contains a small number of vectors, connected, designed for making large jumps across the space quickly. As you descend through the layers, the graph gets denser and the connections get more local. By the time you reach the layer zero, every single vector in your collection is present, tightly connected to its true neighbors. Okay, so how does a search actually move through this thing? It starts way up at the top layer, at some fixed entry point that the database picked when it built the index. From there, it just greedily hops to whichever neighbor looks closest to your query vector. Nothing fancy. It keeps hopping like that until it can’t find a neighbor that’s any closer, and once it hits that wall, it drops down a level and starts the same greedy hopping again, using wherever it landed as the new starting point. Rinse and repeat, layer after layer, and by the time it lands on layer zero, it’s already sitting more or less in the right neighborhood. From there, a tighter local search around that spot pulls out the final candidates you actually see. Here’s the thing though, that word “ approximate ” earns its palce here honestly. It’s doing real work. Because the whole traversal is greedy, it can wander into a spot that looks good locally but is actually the wrong neighborhood entirely, and once it’s there, it has no built-in way of realizing it. The true nearest neighbor to your query could be sitting one single hop off to the side of the path the graph actually walked, and if the search never widens out enough to check that hop, it just never finds it. Nothing crashes, no error. It just returns the wrong “ closest ” answer and moves on like everything’s fine. And this detail rght here, is basically the root cause behind almost every “ why did my obviously relevant document not show up ” bug you’re ever going to chase down. There are three settings that basically decide how your HNSW index behaves, and here’s the funny part, most people who are building on top of a vector database have never so much as looked at them. M: How Connected Each Node Gets M controls how many connections every node keeps at each layer above the bottom one. Crank M up and you get a denser, more richly wired graph. And a denser graph is just harder to get lost in, so recall goes up. But nothing’s free here. Every extra connection is extra memory sitting around, and it’s extra work at build time too, because now every single insert has to weigh and prune through a bigger pile of candidate edges before it settles on which ones to keep. ef construction: The One-Time Payment Worth Making ef construction controls how wide the algorithm searches while it’s actually building the graph, specifically when it’s deciding which neighbors a brand new node should connect to. A higher value means the algorithm looks at a bigger pool of candidates before locking in the final connections, and that just produces a better graph, plain and simple. And here’s the nice part, you only pay this cost once , at build time. Frankly, this is one of the easiest wins in this whole article: just pay it. There’s really no good reason to be stingy withef constructionwhen you’re building the index. ef search: The Knob Everyone Forgets Exists ef search controls how wide the search goes at query time, down at layer zero, right before the results actually get handed back to you. This is the parameter almost nobody touches, it just sits at whatever default the library shipped with, and that’s a shame because it’s directly, measurably behind a huge chunk of the “vector search is returning garbage” complaints out there. Raise it and the recall climbs. Raise it up too far, though, and you’re paying real latency for what amounts to a sliver of extra recall. Below is a table pulled from measurements later in this piece, once we actually build an index and put it through its paces, showing how these three parameters play off each other in practice: Two things jump out immediately, and they’re the whole point of this article. First, a weak graph, one built with a small M and a small ef construction , hits a hard ceiling on recall, and no amount of raising ef search at query time is going to break through that ceiling. It just is what it is. Second, a strong graph gets you most of the recall you’re ever going to get almost right away, at a pretty modest ef search , and pushing that value way higher after that point buys you next to nothing. We’re about to go prove both of these to ourselves, with our own index, running on our own machine. Ok, so lets dive into something exciting. You only need Python and numpy. That’s the entire dependency list. No FAISS, or hnswlib, nothing pre-built. The goal is to see every part with your own eyes. The graph itself is a dictionary of vectors, a dictionary of neighbor sets keyed by layer, and a record of which layer that each node reaches up to. python import heapqimport mathimport randomimport numpy as npdef l2 sq a, b : diff = a - b return float np.dot diff, diff class SimpleHNSW: def init self, dim, M=8, ef construction=100, seed=42 : self.dim = dim self.M = M self.M0 = M 2 layer zero keeps more connections, standard HNSW practice self.ef construction = ef construction self.mL = 1.0 / math.log M self.rng = random.Random seed self.vectors = {} self.neighbors = {} self.levels = {} self.entry point = None self.entry level = -1 def random level self : return int -math.log self.rng.random self.mL The random level function is what gives the graph its layered shape. Most inserted nodes get level zero and only exist at the bottom layer. A small, exponentially shrinking fraction get assigned to higher levels, which is exactly what creates that sparse, long jump top layer and dense, local bottom layer. Insertion has two phases. First, a cheap greedy descent from the top layer down to the new node’s own level, just to find a good entry point. Second, from that level down to zero, a proper search at ef construction width to find real candidate neighbors, followed by connecting the new node to the best of them. python def search layer self, query, entry points, layer, ef : visited = set entry points candidates = l2 sq query, self.vectors ep , ep for ep in entry points heapq.heapify candidates result = -d, i for d, i in candidates heapq.heapify result while candidates: dist, current = heapq.heappop candidates furthest dist = -result 0 0 if dist furthest dist and len result = ef: break for neighbor in self.neighbors current .get layer, : if neighbor in visited: continue visited.add neighbor d = l2 sq query, self.vectors neighbor furthest dist = -result 0 0 if d < furthest dist or len result < ef: heapq.heappush candidates, d, neighbor heapq.heappush result, -d, neighbor if len result ef: heapq.heappop result return sorted -d, i for d, i in result def select neighbors self, candidates, m : return i for , i in sorted candidates :m def insert self, node id, vector : vector = np.asarray vector, dtype=np.float64 self.vectors node id = vector self.neighbors node id = {} level = self. random level self.levels node id = level if self.entry point is None: self.entry point = node id self.entry level = level for lc in range level + 1 : self.neighbors node id lc = set return ep = self.entry point for lc in range self.entry level, level, -1 : ep = self. search layer vector, ep , lc, ef=1 0 1 for lc in range min level, self.entry level , -1, -1 : candidates = self. search layer vector, ep , lc, ef=self.ef construction m = self.M0 if lc == 0 else self.M chosen = self. select neighbors candidates, m self.neighbors node id lc = set chosen for c in chosen: self.neighbors c .setdefault lc, set .add node id cap = self.M0 if lc == 0 else self.M if len self.neighbors c lc cap: ranked = sorted l2 sq self.vectors c , self.vectors n , n for n in self.neighbors c lc self.neighbors c lc = set n for , n in ranked :cap if candidates: ep = candidates 0 1 if level self.entry level: self.entry point = node id self.entry level = level That pruning step, the one after connecting a new node to its chosen neighbors, matters more than it looks. Every neighbor gets a back link to the new node, and if that pushes any neighbor’s connection count past its cap, the weakest connection gets dropped. Without that pruning step, popular regions of the graph would just accumulate unlimited connections over time and the whole structure would slowly degrade into something close to brute force again, just with extra bookkeeping. And we dont want that. Search is the same layered descent, minus the insertion bookkeeping. python def search self, query, k, ef search : query = np.asarray query, dtype=np.float64 if self.entry point is None: return ep = self.entry point for lc in range self.entry level, 0, -1 : ep = self. search layer query, ep , lc, ef=1 0 1 candidates = self. search layer query, ep , 0, ef=max ef search, k return sorted candidates :k I ran this exact class on a small, clean toy dataset first, five hundred random vectors in sixteen dimensions, no clustering tricks, generous parameters M=16, ef construction=200, ef search=200 . Every single query returned recall of 1.0 against a brute force ground truth, meaning that the index found the true top ten nearest neighbors, every time, for every query tested. The mechanism works exactly as designed when you give it room to work. Now let’s take that room away on purpose. Real production data almost never looks like a clean & uniform cloud of points floating in space. It clusters. Most of your documents are going to circle around a handful of recurring topics, and then you’ve got a small number of genuine outliers scattered around the edges. So I built a synthetic dataset that mirrors exactly that: five tight clusters of four hundred vectors each, in sixty-four dimensions, and fifty outlier vectors scattered far off from any cluster, for a total of two thousand and fifty vectors. From there, I built two indexes on that exact same dataset. One with deliberately weak parameters, M=4 and ef construction=10 , values low enough that, honestly, plenty of real deployments are running settings this stingy without even realizing it. And one with strong parameters, M=32 and ef construction=200 . Then I ran one hundred queries against each index, using vectors that were already sitting in the dataset as the queries themselves, and compared what came back against the true brute force nearest neighbors. WEAK INDEX: M=4, ef construction=10 ef search= 5 | cluster recall@10=0.315 | outlier recall@10=0.085 ef search= 10 | cluster recall@10=0.315 | outlier recall@10=0.085 ef search= 20 | cluster recall@10=0.352 | outlier recall@10=0.125 ef search= 50 | cluster recall@10=0.405 | outlier recall@10=0.175 ef search= 100 | cluster recall@10=0.420 | outlier recall@10=0.200 ef search= 200 | cluster recall@10=0.435 | outlier recall@10=0.205 ef search= 400 | cluster recall@10=0.440 | outlier recall@10=0.210 Read that outlier row again. With a weak graph, queries against outlier points, the scenario where the user searched for something genuinely uncommon in your dataset, recovered barely 1/5th of their true nearest neighbors, even at an absurdly high The query was semantically legitimate. The correct answer existed in the collection. The graph just never built a path good enough to reach it, and no amount of searching harder at query time could invent a path that was never built. We would go directly back to construction, when we trace the reason. With M=4, each node in the graph keeps only four connections at the upper layers. During insertion, Here is the same experiment, same dataset, same one hundred queries, run against the strong index instead, M=32 and STRONG INDEX: M=32, ef construction=200 ef search= 5 | cluster recall@10=0.778 | outlier recall@10=0.590 ef search= 10 | cluster recall@10=0.778 | outlier recall@10=0.590 ef search= 20 | cluster recall@10=0.780 | outlier recall@10=0.640 ef search= 50 | cluster recall@10=0.780 | outlier recall@10=0.650 ef search= 100 | cluster recall@10=0.780 | outlier recall@10=0.655 ef search= 200 | cluster recall@10=0.780 | outlier recall@10=0.655 Cluster recall jumps from a ceiling of 0.44 to a ceiling of That's the entire lesson of this article, right there, in one side-by-side comparison. Build quality sets your ceiling. Query-time search width just decides how close you actually get to that ceiling. One more thing worth noticing here is exactly where the diminishing returns show up. On the strong index, almost all of the recall gain happens by the time you hit ef search=20 . Pushing it all the way up to That's an 85% jump in latency for what amounts to a rounding error in accuracy. That's real money, real user-facing delay, spent for almost nothing, and it's exactly the kind of waste you get when a team tunes ef search by trial and error instead of just plotting recall against latency and looking at it. And since I promised no vague hand waving anywhere in this piece: this is a simplified, from-scratch implementation, built for clarity rather than raw performance. Production libraries like hnswlib and That is exactly why mature implementations routinely report recall in the high 90s on real workloads, well above anything my simplified version reaches even at its best settings. But the mechanism you just watched play out, weak graphs capping recall no matter how hard you search, strong graphs closing in on their ceiling fast, holds true in every real implementation out there. The exact numbers justt get a lot better once that extra construction heuristic is in the mix. Every parameter you just watched in action has a direct counterpart sitting in your production vector database’s configuration, usually untouched. In Pinecone , pod-based indexes historically exposed these directly as index build settings, and serverless indexes manage graph construction internally but still expose query-time behavior worth checking against your recall requirements in their documentation. In Qdrant , the HNSW config block exposes M and In FAISS , the IndexHNSWFlat constructor takes Here is the checklist worth running against your own system this week, symptom first, likely culprit second: Here’s the gut check I use now, and it only takes about ten minutes. It would’ve saved me those two wasted days I spent chasing the embedding model. Pull twenty or thirty real queries out of your logs, ones where you already know, or at least strongly suspect, what the correct top result should be. Run them against your current index and just write down what comes back. Then, on a small sample of your actual collection, maybe five or ten thousand vectors, run a true brute force nearest neighbor search for those same queries. Line the two result sets up side by side. Compare them directly. If brute force finds the right answer and your production index doesn’t, that’s an ANN tuning problem, full stop, not an embedding problem. Go check M, ef construction, and That one test alone will tell you, with certainty, which half of your stack actually broke. I have watched engineers spend entire sprints rewriting prompts, swapping embedding models, and restructuring retrieval logic, chasing a problem that a single configuration change would have fixed in an afternoon. Nobody checks their index config. Everybody checks their prompt first, obsessively, over and over, because the prompt is the part you can see and touch and iterate on in a chat window. The index config is invisible. It sits underneath everything, quietly deciding what your system is even capable of finding, and most people never once open that file. That is exactly backwards. Your prompt cannot retrieve a document your index never let it see in the first place. Understand HNSW: Why Your Vector Search Returns Garbage Build your own minimalist HNSW from… https://pub.towardsai.net/understand-hnsw-why-your-vector-search-returns-garbage-build-your-own-minimalist-hnsw-from-114415ddf28c was originally published in Towards AI https://pub.towardsai.net on Medium, where people are continuing the conversation by highlighting and responding to this story.