Vector Search and Approximate Nearest Neighbors

In the previous post we talked about how embeddings turn chunks of text (or images, or code) into points in a high-dimensional space, and how "retrieval" reduces to "find the nearest points to this query." That framing is clean and it's true. It also ducks the question that matters the most once you try to build anything: how do you find the nearest neighbors, when there are a hundred million of them and you have fifty milliseconds?

Brute force is fine for a toy. The second you're indexing a real corpus, every part of the retrieval pipeline starts to strain, and the thing that strains first is the nearest-neighbor search. This post is about the data structures that keep it fast.

Exact kNN doesn't scale

Let me put numbers on it, because the handwave-y version ("brute force is slow") obscures why.

You have a query vector $q \in \mathbb{R}^d$ and a database of $N$ vectors $\{x_1, \ldots, x_N\}$. Exact $k$-nearest-neighbors means: compute the distance from $q$ to every $x_i$, sort, take the top $k$. That's $O(Nd)$ work per query, with no free lunches.

Plug in realistic numbers. A modern retrieval system might have $N = 10^8$ documents and $d = 768$. One exact query is $10^8 \times 768 = 7.68 \times 10^{10}$ floating-point multiply-adds. Even at hundreds of gigaFLOPS on a GPU, that's hundreds of milliseconds per query, for a single user making a single query. That doesn't work.

You could throw hardware at it (FAISS has a very good GPU brute-force implementation), and for some workloads that is the right answer. But for most applications you'd rather burn a bit of recall, search ten or a hundred times faster, and serve a thousand queries per second off a single machine.

That tradeoff is what "approximate" nearest neighbors is about. You give up the guarantee of perfect top-$k$. You get almost always correct top-$k$, orders of magnitude faster. The literature measures the loss with recall@k, the fraction of the true top-$k$ that your ANN search returns, averaged over queries. Good ANN systems in 2026 run at recall@10 of 0.95 to 0.99 while being 100 to 1000× faster than brute force.

So. How do they do it.

Prereqs

I'm going to assume you've read the embeddings post and are comfortable with the picture of a vector as a point in a dense, high-dimensional space, and cosine or Euclidean distance as "how similar two things are." Everything else gets built up from there.

In high dimensions, distance stops behaving the way 2D intuition suggests. Most of the volume of a $d$-dimensional ball sits near its surface. Random pairs of vectors in $\mathbb{R}^{768}$ tend to have nearly the same distance to each other, which is known as the "curse of dimensionality." The reason ANN works at all is that learned embeddings from neural networks don't fill the space uniformly. They sit on a low-dimensional manifold, and that local structure is what the data structures below exploit.

HNSW: navigate a graph the way you navigate a city

HNSW stands for Hierarchical Navigable Small World. It's the dominant ANN method in production today, and once the mental model clicks it feels almost obvious in retrospect.

Start with a simpler idea: a proximity graph. Every indexed vector is a node. You connect each node to its nearest few neighbors. To search for a query, pick any starting node, look at its neighbors, jump to the one that's closest to the query, and repeat. You're doing greedy search on the graph. Each hop strictly decreases the distance to the query until you land on a local minimum.

That almost works. The problem is that greedy search on a single dense graph gets stuck in local minima and can take a lot of hops across flat regions. So you layer it.

An HNSW index is several stacked proximity graphs. The top layer contains a tiny sample of the points, maybe 0.1%, connected by long edges that span huge distances in the embedding space. The bottom layer contains every point, connected by short edges to its immediate neighbors. Layers in between interpolate.

Search runs like this: start at a fixed entry point on the top layer. Greedy-search until you can't get closer. Drop down a layer. Greedy-search from wherever you ended up. Drop down again. Repeat until you've searched the bottom layer. Return the closest node you've seen.

The top-layer hops cover most of the distance to the query in $\log N$ moves, like plotting a cross-country drive on the interstate. The bottom-layer hops snap to the exact neighborhood, like driving the last mile on residential streets. Total work is roughly $O(\log N)$ distance computations, and the "navigable small world" structure means you almost always end up in the right neighborhood.

The operational knob: ef_search

Pure greedy search is too aggressive. It commits to one path and doesn't look back. Real HNSW search maintains a priority queue of candidate nodes of size ef_search, explores the most promising one, adds its neighbors to the queue, and continues until the queue stops improving. Larger ef_search means a wider beam, more candidates explored, higher recall, and more latency. Smaller ef_search is the opposite.

This is the single most important tuning knob you'll touch when operating an HNSW index. A good default is something like ef_search=64 for a small corpus and ef_search=128-400 for a large one. Pick your recall target, sweep ef_search, read off the latency. We'll see this plotted later.

IVF: skip the regions you don't care about

HNSW is great but it has two real costs. The graph itself takes memory (each node stores pointers to its neighbors), and building the index is slow. For very large corpora or for systems that need to re-index often, the other classic approach is IVF, for Inverted File Index, adapted from text search.

The idea: cluster all the vectors into $k$ groups with $k$-means (typically $k \approx \sqrt{N}$). Each cluster has a centroid. When you index a new vector, assign it to the closest centroid and push it into that centroid's list. When you query, compute the distance from $q$ to every centroid (cheap: only $k$ of them), then only search inside the $p$ closest centroid lists. That $p$ is called nprobe.

If nprobe = 1, you only search one cell and the search is fastest, but you miss any true neighbors that happened to sit just across a cell boundary. As nprobe grows, you cover more of the space and recall rises. At nprobe = k, you've searched everything and you're doing brute force again.

IVF's recall-latency curve is usually a bit worse than HNSW's at the same memory budget, but IVF has two advantages that keep it relevant. First, it composes cleanly with vector compression (which we're about to talk about). Second, when you have too many vectors to fit in RAM, you can keep the inverted lists on disk and stream them in on demand, which is exactly what DiskANN and FAISS's on-disk variants do.

Product Quantization: 32 bytes of vector, four bytes on disk

Even with a smart index, the vectors themselves cost money. A single $d=768$ float-32 embedding is $768 \times 4 = 3{,}072$ bytes. A billion of those is three terabytes. You cannot keep three terabytes of floats in RAM on a single machine.

Product quantization is the standard compression trick. The idea is clever enough that I think it's worth working through by hand before handwaving about the scale.

Here's the pitch. You have a database of $d$-dimensional vectors. Split each vector into $M$ equal subvectors of dimension $d / M$. For each subvector position (1 through $M$), train a separate $k$-means with $K$ centroids on just that slice of every database vector. Now you have $M$ little codebooks, each with $K$ entries.

To store a database vector, replace each of its subvectors with the index of the nearest codebook entry in its own codebook. If $K = 256$, each index is 8 bits. Your $d = 768$ float-32 vector (3072 bytes) becomes $M = 96$ one-byte codes (96 bytes). A 32× compression.

To search, there's a second trick called asymmetric distance computation: the query stays un-quantized, and for each query you precompute the distance from the query's subvectors to every centroid in every codebook (so $M \times K$ small distance calculations). Then scoring any database vector is just $M$ table lookups and an add. You get dramatic speed-ups on top of the compression win.

Product quantization is almost never used on its own in production. It gets stacked with IVF (cluster first, then PQ-compress inside each cluster) to make IVF-PQ, the workhorse of FAISS's billion-scale indexes. HNSW can also be combined with PQ (as in HNSW-PQ or the "PQ-refine" variants), though it's a more recent trend.

M and the bits per code

The tuning knobs for PQ are $M$ (more subvectors = finer-grained codes = better accuracy, more memory) and the bits per code (almost always 8; more is rarely worth it, less makes it hard to reconstruct). Rule of thumb: PQ at 8 bits per code with $M = d/4$ subvectors loses a couple of points of recall@10 and compresses 16×. That's usually the right starting point.

The recall-latency curve, in one picture

Every knob we've just talked about (ef_search in HNSW, nprobe in IVF, $M$ and bits in PQ) moves an index along a Pareto curve in recall-vs-speed space. When engineers talk about "tuning an ANN index," they usually mean: sweep a knob, plot the curve, pick an operating point.

A few things in that curve are true of almost every ANN system:

• At low recall (say 0.80), the throughput advantage over brute force is enormous: 50–100×.
• The curve bends hard somewhere in the 0.95–0.99 range. Each extra point of recall costs you a chunk of QPS.
• The top of the curve asymptotes below 1.0. To hit recall 1.0, you go back to brute force (or a rerank step, which we'll get to in the next post).

Picking an operating point is a product decision. A semantic-search backend for a legal-research tool probably wants recall@10 of 0.99 even if it means half the QPS. A consumer recommender system running on hot-path embeddings might happily take 0.90 for 10× the throughput.

A worked example

Let me make this concrete with a small walk-by-hand example, to calibrate the intuition before the code block.

Say we have 6 indexed vectors in 2D and a query $q = (2.0, 1.0)$. The vectors are $x_1 = (2.1, 0.9)$, $x_2 = (3.5, 1.2)$, $x_3 = (0.0, 0.5)$, $x_4 = (2.3, 1.4)$, $x_5 = (-1.0, -0.5)$, $x_6 = (1.7, 1.1)$.

Brute-force top-3. Compute $\|q - x_i\|$ for each $i$:

• $\|q - x_1\| = \sqrt{0.1^2 + 0.1^2} = 0.141$
• $\|q - x_2\| = \sqrt{1.5^2 + 0.2^2} = 1.513$
• $\|q - x_3\| = \sqrt{2.0^2 + 0.5^2} = 2.062$
• $\|q - x_4\| = \sqrt{0.3^2 + 0.4^2} = 0.500$
• $\|q - x_5\| = \sqrt{3.0^2 + 1.5^2} = 3.354$
• $\|q - x_6\| = \sqrt{0.3^2 + 0.1^2} = 0.316$

Six distance computations. Sort. Top-3: $\{x_1, x_6, x_4\}$.

Now suppose we built an IVF index with two centroids, one near $(2.0, 1.0)$ and one near $(-0.5, 0.0)$. Assignments: $x_1, x_2, x_4, x_6 \to c_1$; $x_3, x_5 \to c_2$. With nprobe=1, we only compute distances to $c_1$'s four vectors. Four distance computations instead of six, same top-3. Recall@3 = 1.0.

If the query had been $q' = (-0.5, 0.0)$, the closest centroid would flip to $c_2$, and nprobe=1 would only look at $\{x_3, x_5\}$. We'd miss neighbors that actually live on $c_1$'s side of the boundary. nprobe=2 covers both cells and we're back to brute force, which is what IVF degenerates to when $p = k$.

More points, more clusters, higher dimensions, but the reasoning is the same.

Here's the matching code, small enough to run end-to-end:

import numpy as np
 
# --- the tiny example from the post ---
X = np.array([
    [2.1, 0.9], [3.5, 1.2], [0.0, 0.5],
    [2.3, 1.4], [-1.0, -0.5], [1.7, 1.1],
])
q = np.array([2.0, 1.0])
 
# --- brute force top-3 ---
dists = np.linalg.norm(X - q, axis=1)
top3 = np.argsort(dists)[:3]
print("brute-force top-3:", top3, dists[top3].round(3))
# brute-force top-3: [0 5 3] [0.141 0.316 0.5]
 
# --- IVF with k=2 centroids, nprobe=1 ---
from sklearn.cluster import KMeans
km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
centroids = km.cluster_centers_
labels = km.labels_
 
# find the closest centroid to q
probe = np.argmin(np.linalg.norm(centroids - q, axis=1))
candidates = np.where(labels == probe)[0]
cand_dists = np.linalg.norm(X[candidates] - q, axis=1)
order = np.argsort(cand_dists)[:3]
ivf_top3 = candidates[order]
print("IVF nprobe=1 top-3:", ivf_top3, cand_dists[order].round(3))
# With this split, we only scan the 4 vectors in probe's cell.
 
# --- HNSW on a slightly bigger toy set, via hnswlib ---
# pip install hnswlib
import hnswlib
rng = np.random.default_rng(0)
big = rng.standard_normal((2000, 16)).astype(np.float32)
q_big = rng.standard_normal(16).astype(np.float32)
 
index = hnswlib.Index(space="l2", dim=16)
index.init_index(max_elements=2000, ef_construction=200, M=16)
index.add_items(big, np.arange(2000))
 
index.set_ef(32)   # ef_search — the knob
labels32, _ = index.knn_query(q_big, k=10)
 
index.set_ef(200)
labels200, _ = index.knn_query(q_big, k=10)
 
# compare against brute force
brute = np.argsort(np.linalg.norm(big - q_big, axis=1))[:10]
recall32  = len(set(labels32[0])  & set(brute)) / 10
recall200 = len(set(labels200[0]) & set(brute)) / 10
print(f"recall@10 at ef=32:  {recall32:.2f}")
print(f"recall@10 at ef=200: {recall200:.2f}")

Small dataset, real library, the same pattern you'd run at scale. The numbers in the HNSW block will wobble a bit with the random seed, but you'll consistently see recall rise as ef_search grows.

The landscape in 2026

The "which vector database should I use" question has split into a few stable answers:

FAISS (from Meta) is the reference C++ library. It implements HNSW, IVF, PQ, OPQ, and the disk-backed variants, and it's where new indexing algorithms land first. If you're building your own retrieval system with tight latency budgets, you're probably linking against FAISS.

Pinecone, Weaviate, Qdrant, Milvus are the managed or self-hostable vector databases built on top of ANN indexes like FAISS or custom HNSW implementations, with extras: metadata filtering, horizontal scaling, replication, namespace management, hybrid search. Pinecone is the most hands-off SaaS; Qdrant and Milvus have become the popular open-source choices.

pgvector is the PostgreSQL extension that adds a vector type, a handful of distance operators, and HNSW + IVF indexes inside ordinary Postgres. For workloads where the vectors live alongside other relational data and the scale is "millions, not billions," pgvector has taken over a lot of what used to be managed-vector-DB territory. It's boring and that's the point.

ScaNN (from Google) and DiskANN (from Microsoft) are the other two ANN systems worth knowing by name. ScaNN popularized anisotropic quantization. DiskANN is the state-of-the-art for billion-scale on-disk search; it's what's running underneath Azure AI Search at this point.

The through-line is that the algorithms don't change much from one product to another. What changes is the operational surface around them: how you shard, how you filter by metadata pre- or post-ANN, how you tier hot data to RAM and cold data to SSD, how you handle updates without rebuilding the index. The actual distance computations are the same.

Misconceptions

"HNSW is always the right answer." In most benchmark leaderboards HNSW wins on recall-vs-latency, and that's why it's the default in almost every production system. But HNSW has real downsides: high memory cost (the graph itself can be 30–50% of the index size), slow build times, and an awkward story for deletes and heavy update loads because removing nodes breaks the graph invariants. If your corpus is mostly-read, fits in RAM, and is rebuilt periodically, HNSW is great. If it's constantly mutating or billion-scale-on-disk, IVF-PQ or DiskANN is a better fit.

"Higher recall is always better." Recall is a means, not an end. What actually matters is the quality of the downstream task (retrieval-augmented answers, semantic search results, recommendations). A bump from recall@10 = 0.95 to 0.99 might be invisible to users if the top-1 neighbor is the same. Worse, pushing recall too high can cost you latency that would've been better spent on reranking, or on pulling from more sources. Pick a recall target that the product actually needs and stop tuning once you hit it.

"ANN is just a faster way to do exact kNN." ANN is a different operation with its own failure modes. The indexes have recall holes where specific queries consistently miss their true neighbors, often the queries near cell boundaries in IVF, or the ones that land in sparsely-connected pockets of the HNSW graph. The failures correlate, which means they don't average out. If you're evaluating a retrieval system and 3% of queries get completely wrong answers, you need to know whether that's the model or the index, and the only way to know is to compare against brute force on a held-out slice.

"Product quantization destroys your embeddings." It compresses them lossily, which sounds destructive, but the loss is usually in the noise floor of what the embedding model can even resolve. An 8-bit PQ code retains enough signal to distinguish near-neighbors from far-neighbors, which is the only thing ANN needs. The cases where PQ genuinely hurts are when the embedding space is already very low-signal (e.g. bad embeddings, or very short text), in which case you've got bigger problems than quantization.

What's next

This post covered the "search in sub-linear time" half of the retrieval stack: HNSW's layered graph walk, IVF's cluster-and-probe, PQ's subvector compression, the recall-latency Pareto, and the knobs (ef_search, nprobe, $M$) you actually turn. The algorithms are stable; the operating point is what changes from one system to the next.

The next post covers dense-sparse hybrid retrieval, why pure semantic search still misses queries that a traditional BM25 index catches trivially, and how modern systems fuse the two signals.

Additional reading (and watching)

• Johnson, J., Douze, M., & Jégou, H. (2017). Billion-Scale Similarity Search with GPUs. arXiv:1702.08734. The FAISS paper, still the reference for GPU-accelerated brute-force and IVF-PQ at scale.

• Aumüller, M., Bernhardsson, E., & Faithfull, A. (2020). ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems. The standard recall-vs-QPS benchmark suite and the source of the Pareto-curve methodology that every ANN paper now uses.

• Beyer, K. et al. (1999). When Is "Nearest Neighbor" Meaningful?. ICDT 1999. The classic paper on why high-dimensional nearest-neighbor search is hard in the worst case, and why it's only tractable because real data is manifold-y.

• Malkov, Y. A., & Yashunin, D. A. (2016). Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World Graphs. arXiv:1603.09320. The HNSW paper. Short, readable, includes the full algorithm.

• Malkov, Y. A. (2018+). hnswlib. The reference C++/Python implementation. The README has sensible defaults and advice on ef_search, ef_construction, and M that are still current.

• Jayaram Subramanya, S. et al. (2019). DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node. NeurIPS 2019. The Vamana graph algorithm and its disk-resident variant. Underpins Azure AI Search's vector index.

• pgvector project. (2024–2026). pgvector GitHub repository. The Postgres extension. Supports HNSW and IVFFlat indexes and has become the default for small-to-medium vector workloads in 2025–2026.

• Guo, R. et al. (2020). Accelerating Large-Scale Inference with Anisotropic Vector Quantization. ICML 2020. The ScaNN paper. Shows that quantizing along directions that align with the query distribution beats isotropic PQ.