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." At larger scales, the search itself becomes a problem: how do you find the nearest neighbors among a hundred million vectors within a fifty-millisecond budget?

Exact search is a good baseline and can be practical for small corpora, selective filters or GPU batches. This post asks when it becomes expensive, and how approximate indexes trade some nearest-neighbor recall for less work.

What exact search costs

For a query $q\in\mathbb{R}^d$ and $N$ stored vectors, a flat exact scan evaluates all $N$ distances or similarities and selects the best $k$. It does not require fully sorting the database. The vector comparisons cost $O(Nd)$ work.

At $N=10^8$ and $d=768$, dot-product scoring uses 76.8 billion multiply-adds, conventionally 153.6 billion FLOPs. Float32 vectors occupy 307.2 GB before index overhead. Whether compute or data movement dominates depends on hardware, batching, layout and caching; these counts are not a latency estimate.

Approximate indexes try to avoid a full scan, compress the comparisons, or both. They add their own build cost, memory overhead and tuning requirements.

The usual check is recall@k: the fraction of exact top-$k$ neighbors returned by the approximate search, averaged over evaluation queries. This measures agreement with the chosen vector metric, not whether the passages answer the user’s question.

Prereqs

The embeddings post introduces the vectors we will search. Here, cosine or Euclidean distance defines which neighbors count as closest.

HNSW: navigate a graph the way you navigate a city

HNSW stands for Hierarchical Navigable Small World. It combines nested proximity graphs with a search that uses sparse upper layers to find a promising entry into denser lower layers.

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.

The lowest layer contains all indexed points. Randomly sampled subsets also appear in higher layers, so a point reached above still exists below. The upper graphs provide longer-range routes; the precise composition depends on index construction.

Search starts at an entry point in an upper layer, moves toward the query, then descends from the same point. At the bottom, a bounded candidate search explores alternatives and returns the best candidates found.

This hierarchy can substantially reduce exploration. It is not a worst-case $O(\log N)$ guarantee for arbitrary data, nor a guarantee of the exact nearest neighbor.

The operational knob: ef_search

ef_search controls the search breadth at query time. Implementations maintain candidate and result queues; increasing ef generally explores more possibilities. In hnswlib, ef should be at least the requested result count $k$. The parameter is not a direct count of distance evaluations.

Sweep ef against an exact reference on representative queries. Report recall with latency and memory.

IVF: skip the regions you don't care about

HNSW stores neighbor links and spends work building them. IVF, or Inverted File Index, groups vectors into lists instead. Its build, storage, and query costs provide another comparison for large or frequently rebuilt indexes.

IVF first assigns vectors to coarse centroids, often learned with $k$-means. Each centroid owns an inverted list of assigned vectors. At query time, choose the closest nprobe centroids and scan those lists. A square-root-of-$N$ cluster count is only a rough starting heuristic.

With one probed list, a true neighbor in another list can be missed. Probing more lists expands the candidate set. For this exact-scoring toy, recall cannot fall as that set grows; a compressed or capped implementation adds other sources of approximation.

IVF composes with compression and can store inverted lists outside RAM. Its performance relative to a graph index depends on the workload.

Product quantization: replace subvectors with codes

A 768-dimensional float32 embedding uses 3,072 bytes; a billion use 3.072 TB before overhead. Compression can make the difference between a feasible index and an expensive one.

Product quantization compresses a vector by encoding its subvectors separately. We can work through it with a small codebook.

Start with 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. This replaces full-dimensional comparisons with lookup-table work. The latency benefit depends on code size, hardware and implementation.

PQ can be combined with IVF or other candidate-search structures. A second pass may score shortlisted candidates using original vectors. It can repair ordering within that shortlist, but cannot recover a neighbor excluded earlier.

M and the bits per code

More subvectors or more codebook entries usually improve reconstruction at a storage and search cost, but retrieval quality still needs measurement. With 192 subquantizers and 8-bit codes, a 768-dimensional float32 vector shrinks from 3,072 to 192 code bytes: a 16× payload reduction, excluding shared codebooks and index overhead.

Measure the recall–work tradeoff

A real latency curve needs the dataset, metric, hardware, concurrency, implementation and query distribution recorded alongside it.

Choose an operating point by measuring both neighbor recall and the downstream task under the workload’s latency and memory limits.

A worked example

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. That is four point comparisons plus two centroid comparisons, yielding the same top-3. Recall@3 = 1.0. This tiny example saves no total distance computations; with larger lists, the centroid overhead can be a smaller share of the work.

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 nprobe = nlist, provided every candidate is scored exactly.

This code builds and queries the example index:

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}")

The library example compares two search settings for one query. Both may find all ten neighbors on such a small dataset. Use many held-out queries and repeat timing measurements before inferring a useful recall–latency curve.

Libraries and storage systems

Separate the index algorithm from the operational system around it:

Faiss implements exact search and multiple approximate indexes, including IVF, PQ and HNSW. Its index documentation lists storage assumptions and supported combinations.

Vector databases add persistence, filtering, updates and distributed operation around search indexes. Those features can matter as much as the index algorithm.

pgvector provides exact vector search and HNSW/IVFFlat indexes inside PostgreSQL. Filters and query plans affect which rows the index can return.

ScaNN explores efficient vector search including anisotropic quantization. DiskANN uses graph-based search designed to work with SSD storage.

Compare how each system shards data, applies filters, uses RAM and SSDs, and handles updates. Implementations can differ on these operations even when they expose the same index family.

Misconceptions

"HNSW is always the right answer." Graph links consume memory, builds and updates have costs, and filtering can change search behavior. Compare it with exact search and alternatives appropriate to the workload.

"Higher recall is always better." Evaluate neighbor recall alongside the downstream task: retrieval-augmented answers, semantic search, or 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." Approximate search can miss a true neighbor. Those misses may recur for particular regions or query types. Compare returned neighbors with an exact-search reference on held-out queries, then check downstream relevance separately. This helps distinguish index errors from encoder ranking errors.

"Product quantization destroys your embeddings." PQ is lossy compression. The error may be acceptable, or it may change important neighbors. Measure compressed-index recall and downstream quality before choosing the code size.

What's next

The next post combines vector ranking with lexical ranking, so a passage has more than one route into the candidate set.

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. A benchmark suite for comparing recall and query throughput under recorded configurations.

• Beyer, K. et al. (1999). When Is "Nearest Neighbor" Meaningful?. ICDT 1999. Analyzes conditions under which nearest and farthest distances become difficult to distinguish as dimensionality increases.

• 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 for vector retrieval inside Postgres.

• 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.