Vector Search Algorithms: Exact Search, IVF, Product Quantization and HNSW

On this page

Every vector database and every retrieval-augmented generation (RAG) system rests on one operation: given a query vector, find the stored vectors closest to it. With a few thousand vectors that is a loop. With tens of millions, comparing the query with every vector takes too long for an interactive request, so systems use approximate nearest neighbour (ANN) indexes that look at a small fraction of the data and accept that they will occasionally miss a true neighbour.

This article explains the algorithms behind those indexes as of August 2024: exact search, the inverted file index (IVF), product quantization (PQ) and the HNSW graph. It covers what each one does, which parameters control the trade-off between recall, speed and memory, and how to measure that trade-off on your own data. The sample code implements exact search, IVF and HNSW in plain NumPy so the parameters can be read and experimented with.

Exact search and the recall measure

Exact search computes the distance from the query to every stored vector and keeps the k smallest. It is always correct and needs no index, which makes it the right choice for small collections and the reference for everything else. Approximate indexes are judged by recall@k: the share of the true k nearest neighbours, as found by exact search, that the index returns. Most production systems target recall between 0.9 and 0.99, chosen by how much a missed neighbour costs the application.

Distance choice matters less than it looks. For embeddings normalised to unit length, ranking by cosine similarity, by inner product and by Euclidean distance gives the same order, so normalise once and use whichever metric the index handles fastest.

Exact search, IVF, IVF with product quantization and HNSW, each with how it narrows the search and the parameters that control it
Every approximate index has a knob that trades work for recall. Tune it against measured recall.

IVF: search only the nearby partitions

An inverted file index runs k-means on the vectors to find nlist centroids and assigns every vector to its nearest centroid, producing nlist lists. At query time it finds the nprobe centroids nearest the query and scans only their lists. More lists make each list shorter; more probes raise recall and the amount scanned. A true neighbour is missed when it sits in a list just across a partition boundary that was not probed, which is why recall rises quickly with the first few extra probes.

IVF needs training data: build the index after loading a representative sample, not on an empty table, or the centroids will not reflect the data. pgvector’s documentation makes the same point about building IVFFlat indexes once the table has data.

Product quantization: compress the vectors

Product quantization, introduced by Jégou, Douze and Schmid, splits each vector into sub-vectors, runs k-means separately in each sub-space, and stores each vector as the list of nearest centroid IDs in each sub-space. A 768-dimensional float32 vector (3,072 bytes) can become a code of a few dozen bytes. Distances between a query and a code are estimated from small per-query lookup tables, which is fast. Combined with IVF (IVF-PQ), it lets a single machine search very large collections; the cost is lower precision, usually recovered by re-ranking the top candidates with their full vectors.

HNSW: navigate a graph

Hierarchical navigable small world graphs, described by Malkov and Yashunin, connect each vector to nearby vectors in a multi-layer graph. Each vector is placed in the bottom layer and, with exponentially decreasing probability, in higher layers, so the upper layers are sparse and act like express lanes. A query starts at the top, walks greedily towards the query until it cannot get closer, drops a layer and repeats, then searches the bottom layer keeping a candidate list of size ef.

%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#FFF3E0', 'primaryTextColor': '#232F3E', 'primaryBorderColor': '#FF9900', 'lineColor': '#232F3E', 'clusterBkg': '#F8FAFC', 'clusterBorder': '#CBD5E1', 'edgeLabelBackground': '#FFFFFF', 'nodeTextColor': '#232F3E'}}}%%
flowchart TD
    A["Start at the entry point<br/>on the top layer"] --> B["Move to the neighbour<br/>closest to the query"]
    B --> C{"Any neighbour closer?"}
    C -- "Yes" --> B
    C -- "No" --> D{"Bottom layer?"}
    D -- "No" --> E["Drop one layer,<br/>start from the same node"]
    E --> B
    D -- "Yes" --> F["Search with a candidate<br/>list of size ef"]
    F --> G["Return the k closest"]
    classDef aws fill:#FFF3E0,stroke:#FF9900,stroke-width:2px,color:#232F3E
    classDef ok fill:#F0FFF4,stroke:#1D8102,stroke-width:2px,color:#145202
    class A,B,C,D,E,F aws
    class G ok

Three parameters matter. M is the number of links per node: higher values improve recall and use more memory. ef_construction is the candidate list size while building: higher values build a better graph more slowly. ef_search (often just ef) is the candidate list size at query time, the knob for recall against latency. In pgvector 0.7.0, for example, the defaults are m = 16, ef_construction = 64 and hnsw.ef_search = 40, and its documentation notes that HNSW has a better speed-recall trade-off than IVFFlat but builds more slowly and uses more memory.

The sample implements exact search, IVF and HNSW, with a recall function to compare them:

Python151 lines
"""Three nearest-neighbour search algorithms in plain NumPy, for reading.

- `brute_force`: exact search; the reference every approximate index is
  measured against.
- `IVFFlat`: inverted file index. k-means splits the vectors into `nlist`
  clusters; a query scans only the `nprobe` closest clusters.
- `HNSW`: hierarchical navigable small world graph (Malkov and Yashunin).
  A query descends sparse upper layers greedily, then searches the dense
  bottom layer with a candidate list of size `ef`.
- `recall_at_k`: the share of the true k nearest neighbours an index returns.

Distances are squared Euclidean. For cosine similarity, normalise vectors to
unit length first; the ranking is then the same. Production libraries (FAISS,
hnswlib, the engines inside vector databases) are far faster; these versions
exist to make the parameters understandable.
"""
from __future__ import annotations

import heapq
import math

import numpy as np


def _sqdist(a: np.ndarray, b: np.ndarray) -> np.ndarray:
    return ((a - b) ** 2).sum(axis=-1)


def brute_force(data: np.ndarray, query: np.ndarray, k: int) -> np.ndarray:
    d = _sqdist(data, query)
    idx = np.argpartition(d, min(k, len(d) - 1))[:k]
    return idx[np.argsort(d[idx])]


def recall_at_k(found: np.ndarray, truth: np.ndarray) -> float:
    return len(set(found.tolist()) & set(truth.tolist())) / len(truth)


class IVFFlat:
    def __init__(self, nlist: int, iterations: int = 20, seed: int = 0):
        self.nlist, self.iterations = nlist, iterations
        self.rng = np.random.default_rng(seed)

    def fit(self, data: np.ndarray) -> "IVFFlat":
        if self.nlist > len(data):
            raise ValueError("nlist cannot exceed the number of vectors")
        self.data = data
        centroids = data[self.rng.choice(len(data), self.nlist, replace=False)].copy()
        for _ in range(self.iterations):                       # Lloyd's k-means
            assign = np.argmin(((data[:, None, :] - centroids[None, :, :]) ** 2).sum(-1), axis=1)
            for c in range(self.nlist):
                members = data[assign == c]
                if len(members):
                    centroids[c] = members.mean(axis=0)
        self.centroids = centroids
        self.lists = [np.flatnonzero(assign == c) for c in range(self.nlist)]
        return self

    def search(self, query: np.ndarray, k: int, nprobe: int = 1) -> np.ndarray:
        probe = np.argsort(_sqdist(self.centroids, query))[:nprobe]
        cand = np.concatenate([self.lists[c] for c in probe])
        if len(cand) == 0:
            return cand
        order = np.argsort(_sqdist(self.data[cand], query))[:k]
        return cand[order]

    def scanned(self, query: np.ndarray, nprobe: int) -> int:
        probe = np.argsort(_sqdist(self.centroids, query))[:nprobe]
        return int(sum(len(self.lists[c]) for c in probe))


class HNSW:
    def __init__(self, M: int = 16, ef_construction: int = 100, seed: int = 0):
        if M < 2:
            raise ValueError("M must be at least 2")
        self.M, self.M0, self.efc = M, 2 * M, ef_construction
        self.mL = 1 / math.log(M)
        self.rng = np.random.default_rng(seed)
        self.vectors: list[np.ndarray] = []
        self.graph: list[dict[int, list[int]]] = []    # graph[layer][node] -> neighbours
        self.entry: int | None = None
        self.top = -1

    def _d(self, i: int, q: np.ndarray) -> float:
        return float(((self.vectors[i] - q) ** 2).sum())

    def _search_layer(self, q: np.ndarray, entries: list[int], ef: int, layer: int) -> list[tuple[float, int]]:
        visited = set(entries)
        cand = [(self._d(e, q), e) for e in entries]
        heapq.heapify(cand)                                    # closest first
        best = [(-d, e) for d, e in cand]                      # farthest first (max-heap)
        heapq.heapify(best)
        while cand:
            d, c = heapq.heappop(cand)
            if d > -best[0][0] and len(best) >= ef:
                break
            for n in self.graph[layer].get(c, []):
                if n in visited:
                    continue
                visited.add(n)
                dn = self._d(n, q)
                if len(best) < ef or dn < -best[0][0]:
                    heapq.heappush(cand, (dn, n))
                    heapq.heappush(best, (-dn, n))
                    if len(best) > ef:
                        heapq.heappop(best)
        return sorted((-d, e) for d, e in best)

    def add(self, v: np.ndarray) -> int:
        node = len(self.vectors)
        self.vectors.append(np.asarray(v, dtype=float))
        level = int(-math.log(1.0 - self.rng.random()) * self.mL)
        while len(self.graph) <= level:
            self.graph.append({})
        for layer in range(level + 1):
            self.graph[layer][node] = []
        if self.entry is None:
            self.entry, self.top = node, level
            return node
        ep = [self.entry]
        for layer in range(self.top, level, -1):              # greedy descent
            ep = [self._search_layer(v, ep, 1, layer)[0][1]]
        for layer in range(min(level, self.top), -1, -1):
            found = self._search_layer(v, ep, self.efc, layer)
            cap = self.M0 if layer == 0 else self.M
            neighbours = [e for _, e in found[: self.M]]
            self.graph[layer][node] = neighbours
            for n in neighbours:                               # connect both ways, then prune
                links = self.graph[layer][n]
                links.append(node)
                if len(links) > cap:
                    links.sort(key=lambda x: self._d(x, self.vectors[n]))
                    del links[cap:]
            ep = [e for _, e in found]
        if level > self.top:
            self.entry, self.top = node, level
        return node

    def fit(self, data: np.ndarray) -> "HNSW":
        for v in data:
            self.add(v)
        return self

    def search(self, q: np.ndarray, k: int, ef: int = 50) -> np.ndarray:
        if self.entry is None:
            return np.array([], dtype=int)
        ep = [self.entry]
        for layer in range(self.top, 0, -1):
            ep = [self._search_layer(q, ep, 1, layer)[0][1]]
        found = self._search_layer(q, ep, max(ef, k), 0)
        return np.array([e for _, e in found[:k]])

Measuring the trade-off

The sample’s example.py runs both indexes on 2,000 synthetic 32-dimensional vectors in 16 clusters and compares their results with exact search. The figures describe this toy data and these simple implementations, not any product, but they show the shape of the trade-off:

Index and settingRecall@10Work per query
IVF, nlist 32, nprobe 10.875114 vectors scanned
IVF, nlist 32, nprobe 20.953203 vectors scanned
IVF, nlist 32, nprobe 40.993302 vectors scanned
IVF, nlist 32, nprobe 81.000577 vectors scanned
HNSW, M 12, ef 100.978graph walk
HNSW, M 12, ef 1000.980graph walk

Do the same with your embeddings and a few hundred real queries: compute exact neighbours once, then sweep nprobe or ef_search and plot recall against latency. Pick the cheapest setting that meets your recall target, and measure again when the data grows or the embedding model changes.

Exact, IVFFlat, IVF-PQ and HNSW compared on recall, memory, build and updates, and typical use
Start with exact search; move to HNSW for latency, IVF for memory, PQ for very large collections.
⚠️
FILTERS CHANGE RECALL

A query with a metadata filter (tenant, date, language) applied after the approximate search can return fewer than k results, or miss neighbours that the filter would have kept. Check how your database combines filters with the index, raise ef_search or nprobe for filtered queries, or use exact search when a filter selects a small subset.

💡
RE-RANK THE TOP CANDIDATES

Retrieve more candidates than you need from the approximate index (say 50 for a final 10), then re-rank them with full-precision distances or a cross-encoder. It recovers most of the recall lost to compression and costs little because the candidate set is small.

⚖️
INDEXES HOLD THE DATA TOO

Vectors, product-quantization codes and graph links are derived from the source documents and can leak information about them. Apply the same access control, encryption and deletion rules to vector indexes as to the documents, and make sure a deletion request removes the vector from every index and replica.

📝
HOW THIS WAS CHECKED

ann.py was tested with Python 3.12, numpy==1.26.4 and pytest==8.3.2: six tests cover exact search, IVF returning exact results when every list is probed, IVF recall rising with nprobe while scanning under half the data, HNSW recall of at least 0.95 rising with ef, HNSW degree limits and layers, and parameter validation. The table is the output of the sample’s example.py. pgvector defaults are from its 0.7.0 documentation.

Key takeaways

  • Exact search is correct and simple; it is the baseline and often enough for small collections.
  • IVF partitions with k-means and scans the nprobe nearest lists; it needs training data and is memory-light.
  • Product quantization compresses vectors into short codes for very large collections; re-rank to recover precision.
  • HNSW gives high recall at low latency, at the cost of memory and build time; tune ef_search for recall.
  • Measure recall@k against exact search on your own vectors and queries, including filtered queries.

Which index and settings did you settle on, and what recall do you measure in production? Share it in the comments.

Glossary

ANN
Approximate nearest neighbour search: finding close vectors without comparing against all of them.
Recall@k
The share of the true k nearest neighbours that a search returns.
IVF
Inverted file index: vectors grouped into lists by nearest k-means centroid.
nprobe
The number of IVF lists searched per query.
Product quantization
Compressing vectors into codes of per-sub-space centroid IDs.
HNSW
Hierarchical navigable small world: a layered proximity graph searched greedily.
ef_search
HNSW query-time candidate list size; higher means better recall and slower queries.

References & Further Reading


Discover more from C4: Container, Code, Cloud & Context

Subscribe to get the latest posts sent to your email.

Written by

Nithin Mohan TK

Hello Namaste! 👋🏻 I'm an accomplished Enterprise Solution Architect & Engineering Leader with 20+ years of progressive experience architecting, building, and scaling transformative enterprise solutions. ⚜️ Solution Architect / AI & Cloud 📌 Galway, Ireland

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.