II · THE IDEA · ARTIFICIAL INTELLIGENCE

Vector Search

Systems and judgement · HNSW (Hierarchical Navigable Small World) · Recall versus speed

▶ Listen · narrated

Embedding search promises semantic retrieval: documents ranked by meaning rather than keyword overlap. But a million 768-dimensional vectors means a trillion pairwise distances if you check them all. Production systems take shortcuts.

At a glance

What it is: Approximate nearest neighbour search: finding vectors close to a query without exhaustive comparison
Common algorithm: HNSW, which builds a navigable graph with multiple layers
The trade-off: Higher recall (finding the true nearest neighbours) costs more time; speed comes by accepting that you might miss some
When to skip it: Small collections, or queries where keyword precision matters more than semantic similarity

Imagine you are looking for a book in a library with a million volumes, but there is no catalogue. You could check every shelf, but that would take days. Instead, someone has left notes: from the entrance, a sign points you toward the general area — fiction, say. When you reach fiction, another sign narrows it to crime novels. A third points to the correct shelf. You never checked most of the library, but you found your book in minutes.

Vector search works the same way. Each document or image is represented as a point in a high-dimensional space, and finding similar items means finding nearby points. Checking every point is slow, so the system builds a navigable structure — a graph with shortcuts. You start at a high level, follow edges toward your query, and descend through layers until you reach the neighbourhood that matters. You do not visit every point, so you might miss the single closest one, but you get close very quickly. That is the trade-off: speed for near-perfection rather than perfection.

Approximate nearest neighbour search finds vectors within a dataset that are close to a query vector, without computing all pairwise distances. HNSW achieves this by constructing a multi-layer graph at index time. Each vector is a node. The algorithm assigns each node to one or more layers probabilistically, with higher layers being sparser. Nodes in the same layer are connected to their nearest neighbours by edges, up to a maximum degree M.

At search time, you enter at the top layer with a random entry point, greedily traverse edges toward the query vector using distance as the objective, and descend to the next layer when no further progress is possible. At the bottom layer, you explore a candidate set of size ef, tracking the nearest neighbours found so far. The parameters M (maximum edges per node) and ef (exploration factor) control the recall-speed trade-off: higher values increase recall and query time.

The algorithm's complexity is sublinear in dataset size, typically logarithmic for search and log-linear for insertion, though this depends on the intrinsic dimensionality of the data and the chosen parameters. Malkov's paper reports that HNSW outperforms tree-based and hashing-based methods on high-dimensional benchmarks, particularly when recall targets exceed 0.9.

GPU acceleration parallelises distance calculations across the candidate set. Johnson's Faiss library includes GPU kernels for both brute-force search (useful as a baseline or for small datasets) and approximate methods including HNSW and inverted file indexes with product quantisation. The latter compresses vectors into short codes, trading some accuracy for memory efficiency, which matters when the index must fit in GPU memory.

Recall is measured by comparing approximate results to the ground truth from brute-force search. If the true k nearest neighbours are known, recall@k is the fraction of those neighbours that the approximate search returned. In production, recall is typically validated on a held-out query set, and parameters are tuned to meet a target — often 0.95 — within a latency budget.

Hybrid retrieval combines vector search with keyword search using an inverted index. Results from both are merged, often with keyword matches receiving a boost or appearing first. This addresses cases where the user's query contains a precise identifier that must match exactly, which vector search may not prioritise if the embedding space does not encode exact string overlap.

Look closer

HNSW builds a graph you can navigate like a highway network
Each vector becomes a node. The algorithm connects nearby nodes with edges, but it does so in layers: a sparse top layer with long-distance links, then progressively denser layers beneath. At search time you enter at the top, greedily follow edges toward the query vector, and drop down through layers as you get closer. The structure is inspired by small-world networks, where a few long-range shortcuts let you reach distant nodes in logarithmic hops. Malkov and colleagues showed that this design gives sublinear search time even as the dataset grows into the millions.
Recall is the fraction of true neighbours you actually retrieve
If the ten nearest vectors to your query are A through J, and your approximate search returns A, B, C, D, E, F, G, H, and two impostors, your recall at ten is 0.8. Perfect recall means you found exactly the right neighbours; approximate search deliberately sacrifices some recall to avoid measuring every distance. The dial you turn is usually a parameter controlling how many candidate paths the algorithm explores. More exploration raises recall and slows the search. In production the target is often 0.95 recall, accepting that one in twenty results might be slightly suboptimal in exchange for answering in milliseconds rather than seconds.
A keyword index can outperform vector search when precision matters
If someone searches for a product code, a case number, or a person's exact name, a traditional inverted index returns only documents containing that string. Vector search returns documents whose embeddings are close, which may include paraphrases, synonyms, or conceptually related text that does not contain the term at all. That behaviour is the point when you want semantic breadth, but it is a liability when the user needs a specific document and knows its identifying string. Hybrid systems often run both searches in parallel and merge the results, letting keyword matches surface at the top when they exist.

The story

A dense vector has hundreds of dimensions. Finding the vectors in a collection that sit closest to a query vector is geometrically simple — measure the distance to each candidate and sort — but computationally expensive. A collection of a million 768-dimensional vectors means 768 million floating-point operations per query if you check them all, and that grows linearly with collection size. The approach is called exact or brute-force search, and it works, but it does not scale to the datasets that embedding-based retrieval was meant to handle.

Approximate nearest neighbour search accepts a bargain: you will not always get the true nearest neighbours, but you will get close ones quickly. The algorithms that implement this trade-off build auxiliary structures at index time — graphs, trees, hash tables, quantised representations — that let you rule out large portions of the collection without measuring them. The cost is paid once, when you index the vectors. The benefit accrues on every query.

Hierarchical Navigable Small World graphs, introduced by Malkov and colleagues in 2016, have become a dominant choice. The algorithm constructs a multi-layer graph. The top layer is sparse, connecting only a small fraction of vectors with long-range edges. Each layer below is denser. At search time you start at the top, greedily follow edges toward the query, and descend through layers as you close in on the target region. The structure mirrors the small-world property observed in social networks: a few long-distance links let you traverse a large graph in logarithmic hops.

The parameters you set control the trade-off. Increasing the number of edges per node, or the number of entry points explored during search, raises recall but slows queries. Decreasing them does the reverse. There is no free lunch: you cannot have both perfect recall and logarithmic search time at scale. Production systems typically target 0.95 recall, accepting that five per cent of results might not be the absolute nearest in exchange for sub-millisecond response.

GPU-based implementations, such as those described by Johnson and colleagues at Facebook AI Research, push throughput higher still by parallelising distance calculations across thousands of cores. A single GPU can handle tens of thousands of queries per second against billion-vector indexes, provided the vectors and graph structures fit in video memory or can be streamed efficiently. The hardware matters as much as the algorithm.

But approximate search is not always the right tool. If your collection has ten thousand vectors, brute-force search completes in single-digit milliseconds on a CPU, and the complexity of building and tuning an HNSW index buys you nothing. If your query is a precise identifier — a document ID, a product SKU — keyword search in an inverted index returns the exact match instantly, while vector search may return conceptually similar items that are not what the user asked for. Hybrid retrieval systems run both in parallel, merging results so that exact keyword matches can override semantic proximity when appropriate. The choice depends on the query, the collection size, and whether you value breadth or precision.

Why it mattered then

The algorithms that underpin modern vector search emerged from different research traditions. Locality-sensitive hashing appeared in the late 1990s, offering probabilistic guarantees that similar items would collide in the same hash bucket. Tree-based methods like KD-trees and ball trees worked well in low dimensions but degraded as dimensionality climbed. Graph-based approaches, building on small-world network theory, gained traction in the 2010s because they scaled better and offered a more intuitive tuning surface: edges, layers, and exploration budgets map directly onto the recall-speed trade-off. Malkov's HNSW paper in 2016 synthesised ideas from navigable small-world graphs and skip lists, producing an algorithm that was both fast and simple to implement. It arrived at a moment when embedding models were becoming ubiquitous — word2vec, GloVe, and early sentence encoders had already created demand for similarity search at scale, but existing solutions either did not scale or required expert tuning. HNSW offered a practical answer. The same year, Johnson and colleagues at Facebook demonstrated that GPUs could accelerate not just training but also inference-time search, making billion-scale retrieval feasible for consumer applications. The combination of algorithmic efficiency and hardware parallelism turned vector search from a research problem into an infrastructure layer.

Why it matters now

Vector search is now a standard component in retrieval-augmented generation pipelines, recommendation engines, and semantic search products. Every major cloud provider offers a managed vector database, and open-source implementations like Faiss, Annoy, and hnswlib are embedded in thousands of production systems. The reason is that language models and vision models produce embeddings as a matter of course, and those embeddings are only useful if you can search them. But the trade-offs have not disappeared. Approximate search still means accepting that some true neighbours will be missed, and the parameters that govern recall versus speed must be tuned for each workload. A system that works well for 100-dimensional embeddings may perform poorly at 1,536 dimensions, and a recall target that is acceptable for recommendation may be too low for medical retrieval. The engineering judgement required is not trivial. There is also a growing recognition that vector search is not a replacement for keyword search, but a complement. Hybrid systems that combine both are more robust: they surface exact matches when the query is precise, and cast a wider net when the query is vague or exploratory. The challenge is deciding when to trust which signal, and that often requires logging, evaluation, and iteration rather than a single architectural choice. The infrastructure exists; the judgement is still human.

The surprising detail

HNSW's layered graph structure was inspired by skip lists, a probabilistic data structure invented in 1990 for fast search in sorted lists. Skip lists use the same principle: a hierarchy of sparse upper layers with express links, and dense lower layers with local connections. The insight that this design would work for navigating high-dimensional vector spaces was not obvious, because vectors do not have a natural ordering. But the greedy graph traversal, moving always toward the query, creates an effective ordering on the fly. The algorithm is also remarkably simple to implement — the core search loop fits in a few dozen lines — which partly explains its rapid adoption.

Remember this

Approximate search trades recall for speed. The true nearest neighbours are not guaranteed, but the ones you get are close enough, and you get them fast.

Test yourself

You have built a retrieval system using HNSW and 768-dimensional embeddings. A user reports that searching for exact product codes sometimes returns similar products instead of the one requested. You check the logs and confirm that the product code appears verbatim in the target document. What is the most likely explanation, and what is the standard fix?

Go deeper

Image: Original diagram, The Daily Triptych. Licence: Original work. Source.

← Back to day 87