Building a Vector Search Engine from Scratch with HNSW in Python

A developer detailed the construction of a vector search engine from scratch using the HNSW algorithm in Python, explaining the layered graph structure and query-time complexity reduction from O(n) to O(log n). The implementation, while not production-grade, aims to provide a concrete mental model for how approximate nearest neighbor search works under the hood.

Every vector database tutorial opens with pip install pinecone and skips the part where you understand why vector search works. That's fine for shipping fast, but it costs you later — when recall drops and you don't know where to look, or when a tuning parameter turns your latency from 10ms to 800ms. HNSW Hierarchical Navigable Small World is the algorithm behind almost every ANN Approximate Nearest Neighbor library in production today: FAISS, Qdrant, Weaviate, and hnswlib all use it internally. This post builds a working HNSW index in pure Python — not production-grade, but real enough to give you a concrete mental model. The naive approach to nearest neighbor search is brute force: compare your query vector to every stored vector, return the k closest. That's O n·d per query — for 1M vectors at 1536 dimensions, expect around 6 seconds per lookup. HNSW solves this with a layered graph. Vectors live across multiple layers: At query time: Expected complexity drops from O n to O log n . The trade-off: more memory, and approximate results — you may occasionally miss the single true nearest neighbor, but you'll be well within a small margin. Here's a minimal HNSW implementation that captures the core structure: python import numpy as np import heapq import math import random from dataclasses import dataclass, field from typing import Optional @dataclass class HNSWNode: vector: np.ndarray neighbors: dict = field default factory=dict layer - list of node ids class HNSWIndex: def init self, dim: int, M: int = 16, ef construction: int = 200, max layers: int = 6 : self.dim = dim self.M = M max neighbors per layer self.M0 = M 2 max neighbors at layer 0 self.ef = ef construction self.max layers = max layers self.nodes: list HNSWNode = self.entry point: Optional int = None self.top layer = 0 def distance self, a: np.ndarray, b: np.ndarray - float: diff = a - b return float np.dot diff, diff squared L2 def random level self - int: level = 0 while random.random < 1.0 / self.M and level < self.max layers - 1: level += 1 return level def search layer self, query: np.ndarray, entry id: int, ef: int, layer: int - list int : visited = {entry id} entry dist = self. distance query, self.nodes entry id .vector candidates = entry dist, entry id dynamic list = entry dist, entry id while candidates: c dist, c id = heapq.heappop candidates worst dist = max d for d, in dynamic list if c dist worst dist: break for nb id in self.nodes c id .neighbors.get layer, : if nb id not in visited: visited.add nb id nb dist = self. distance query, self.nodes nb id .vector if nb dist < worst dist or len dynamic list < ef: heapq.heappush candidates, nb dist, nb id dynamic list.append nb dist, nb id if len dynamic list ef: dynamic list.remove max dynamic list return nid for , nid in sorted dynamic list :ef def add self, vector: np.ndarray - int: node id = len self.nodes node = HNSWNode vector=vector self.nodes.append node level = self. random level if self.entry point is None: self.entry point = node id self.top layer = level for l in range level + 1 : node.neighbors l = return node id ep = self.entry point for l in range self.top layer, level, -1 : candidates = self. search layer vector, ep, ef=1, layer=l ep = candidates 0 for l in range min level, self.top layer + 1 : neighbors = self. search layer vector, ep, ef=self.ef, layer=l M = self.M0 if l == 0 else self.M neighbors = sorted neighbors, key=lambda nid: self. distance vector, self.nodes nid .vector :M node.neighbors l = neighbors for nb id in neighbors: nb node = self.nodes nb id if l not in nb node.neighbors: nb node.neighbors l = nb node.neighbors l .append node id if len nb node.neighbors l M: nb node.neighbors l = sorted nb node.neighbors l , key=lambda nid: self. distance nb node.vector, self.nodes nid .vector :M ep = neighbors 0 if neighbors else ep if level self.top layer: self.top layer = level self.entry point = node id return node id def search self, query: np.ndarray, k: int = 10, ef: int = 50 - list tuple float, int : if self.entry point is None: return ep = self.entry point for l in range self.top layer, 0, -1 : candidates = self. search layer query, ep, ef=1, layer=l ep = candidates 0 candidates = self. search layer query, ep, ef=max ef, k , layer=0 results = sorted candidates, key=lambda nid: self. distance query, self.nodes nid .vector return self. distance query, self.nodes nid .vector , nid for nid in results :k python import numpy as np from hnsw import HNSWIndex Build an index with 128-dimensional vectors index = HNSWIndex dim=128, M=16, ef construction=200 Insert 10k random vectors documents, embeddings, etc. np.random.seed 42 n = 10 000 vectors = np.random.randn n, 128 .astype np.float32 print "Building index..." for i, vec in enumerate vectors : index.add vec if i + 1 % 1000 == 0: print f" {i + 1}/{n} vectors inserted" Query with a random vector query = np.random.randn 128 .astype np.float32 results = index.search query, k=5, ef=50 print "\nTop 5 nearest neighbors HNSW :" for dist, node id in results: print f" node id={node id}, sq distance={dist:.4f}" Verify against brute force all dists = np.sum vectors - query 2, axis=1 brute top5 = sorted enumerate all dists , key=lambda x: x 1 :5 print "\nBrute-force top 5:" for nid, dist in brute top5: print f" node id={nid}, sq distance={dist:.4f}" On a 10k-vector dataset, you'll typically see 4 or 5 out of 5 results overlap between HNSW and brute force. That's the "approximate" in ANN: for most real workloads, occasionally missing one true neighbor is an acceptable trade-off for a 50x–100x query speedup. M — max connections per node per layer. Higher M means better recall and a denser graph, at the cost of more memory and slower inserts. Start with 16. Go up to 32 if your recall consistently falls below 90%. ef construction — candidate pool size during index build. Larger values produce a better-connected graph but slow down insertion. 200 is a solid default; lower it to 100 if insertion throughput matters more than recall. ef search-time — candidate pool size at query time. This is the most important lever for production tuning because you can adjust it without rebuilding the index. Setting ef = k gives the fastest queries; ef = 500 approaches brute-force recall. Plotting ef vs. recall typically reveals a knee around ef = 50–100 for most datasets — that's your sweet spot. Understanding these parameters matters the moment your AI-powered search starts returning wrong results. Before blaming your embedding model, check ef and whether your index was built with sufficient ef construction . It's the same diagnostic discipline that applies across security tooling — knowing the internals saves time when something breaks. The security hardening checklists https://ayinedjimi-consultants.fr/checklists we publish follow the same philosophy: understand the mechanism, then apply the control. This implementation deliberately omits several things you'd need in production: np.save for vectors, JSON or msgpack for the neighbor maps . For any production workload, use hnswlib https://github.com/nmslib/hnswlib directly pip install hnswlib or a vector database that wraps it. The API is almost identical to what's shown above, and you get persistence, filtering, and proper concurrency for free. HNSW is not magic — it's a graph with controlled connectivity. The layered structure lets queries skip large sections of the search space, and the ef parameter gives you a runtime dial between speed and accuracy. Building a stripped-down version reveals what every production vector database is doing under the hood. That understanding pays off when you're debugging recall issues at 3am — and it's faster than re-reading library documentation when you already know what the parameters mean. I run AYI NEDJIMI Consultants https://ayinedjimi-consultants.fr , a cybersecurity consulting firm. We publish free security hardening checklists https://ayinedjimi-consultants.fr/checklists — PDF and Excel.