Vector DB Internals: HNSW & IVF

A support assistant has to find one rollback runbook in a corpus of 100 million runbook chunks and incident summaries. Checking every stored representation can blow tail latency; skipping most candidates can miss the runbook an operator needs. How much work can we skip while still recovering the right neighbors?

Use that query to make the trade-off visible. An embedding turns the query and each runbook into a vector; the model determines how useful that geometry is for relevance. Exact search checks every vector; Hierarchical Navigable Small World (HNSW) walks graph links; inverted file (IVF) opens selected partitions; and product quantization (PQ) compresses stored vectors. The release decision comes from recovered neighbors, latency, memory, and update behavior measured together.

The embedding lesson established the ranking rule: compare vectors using the metric and normalization expected by the embedding model. Keep that rule fixed here. An index approximates those rankings; it doesn't decide whether the embedding model captures the meaning of a rollback correctly.

The brute-force problem

Start with exact search, also called flat search. Given a query vector $q$, it computes a distance to every stored vector and returns the $k$ nearest neighbors; k-NN is shorthand for $k$-nearest-neighbor search.

Use the incident corpus as a concrete baseline: 100 million embeddings, each with 1,536 dimensions, stored as 4-byte floats. An unfiltered flat query scores all 100 million vectors, or 153.6 billion scalar components before considering SIMD vectorization, batching, memory bandwidth, or accelerator hardware. For $N$ vectors with $d$ dimensions, distance scoring takes $O(N \cdot d)$ work: doubling either quantity doubles the components processed.

Why not use a k-d tree? Spatial trees prune regions whose distance bounds cannot beat the current best neighbor. That can work well in low dimensions, but neither low dimension nor a balanced tree guarantees logarithmic nearest-neighbor query time. SciPy warns that even 20 dimensions can make its k-d tree no faster than brute force.^{[1]Reference 1SciPy KDTree: High-Dimensional Search Caveathttps://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html}

One reason is distance concentration: under suitable distributional assumptions, distances become similar relative to their scale, weakening useful bounds. It isn't a theorem about every high-dimensional dataset. Intrinsic dimension, clustering, metric, and sample size matter. Pad a one-dimensional dataset with 767 zero coordinates and its distances remain unchanged. Also, similar radii don't imply similar high-dimensional ball volumes: volume scales as radius raised to the dimension. Measure pruning on your embeddings rather than declaring trees unusable from their dimension alone.

The memory picture is just as stark:

$100{,}000{,}000 \text{ vectors} \times 1{,}536 \text{ dims} \times 4 \text{ bytes} \approx 614 \text{ GB} \approx 572 \text{ GiB}$

That's raw vector storage alone, before adding any index overhead, operating-system page caches, or application state. Fitting that working set on a single node demands a massive memory budget.

import math

def gib_for_float32_vectors(count: int, dimensions: int) -> float:
    return count * dimensions * 4 / (1024 ** 3)

def scalar_components_scored(count: int, dimensions: int) -> int:
    return count * dimensions

n_vectors = 100_000_000
dimensions = 1_536

print(f"raw float32 storage: {gib_for_float32_vectors(n_vectors, dimensions):.1f} GiB")
print(f"scalar components scored per flat query: {scalar_components_scored(n_vectors, dimensions):,}")

query = [0.0] * 768
padded_points = [[value] + [0.0] * 767 for value in (1.0, 10.0)]
print(f"zero-padded 768D distances: {[math.dist(query, point) for point in padded_points]}")

raw float32 storage: 572.2 GiB
scalar components scored per flat query: 153,600,000,000
zero-padded 768D distances: [1.0, 10.0]

Exact search defines 100% ANN recall when the vectors, metric, filter, numerical conventions, and tie policy match the evaluation baseline. The component count alone doesn't tell us milliseconds or QPS (queries per second). Approximate nearest-neighbor (ANN) search saves work by accepting possible misses, but its speedup and recall depend on data, hardware, concurrency, and settings. Recovering 97% of exact neighbors is a possible measured operating point, not a built-in promise of an index family.

Measured settings form a Recall@K versus QPS Pareto frontier when no other tested setting is at least as good on both axes and better on one. Many tested points lie below that frontier; a tuning change doesn't necessarily move along it. Exact flat search remains your recall baseline, and can be a good execution path when a metadata filter leaves a small eligible subset. For example, pgvector defaults to exact nearest-neighbor search and recommends considering a filter-column index for highly selective queries.^{[2]Reference 2pgvectorhttps://github.com/pgvector/pgvector}

Recall@k answers one question: of the exact top-k nearest neighbors, how many did the ANN index recover? A low latency can hide poor neighbor recovery. For example, recovering 98 of the exact top 100 gives 98% ANN recall; it doesn't establish that those documents answer the user's question.

This is ANN recall, not relevance recall against human-labeled documents. An index can perfectly reproduce a poor embedding ranking. Compute the exact baseline with the same metric, corpus snapshot, and filter as the approximate query, and use a consistent policy for ties at the cutoff.

def recall_at_k(exact_ids: list[int], approximate_ids: list[int]) -> float:
    expected = set(exact_ids)
    if not expected or len(expected) != len(exact_ids):
        raise ValueError("exact_ids must contain distinct IDs and be nonempty")
    if len(approximate_ids) > len(exact_ids):
        raise ValueError("compare at the same cutoff k, not an overfetched buffer")
    if len(set(approximate_ids)) != len(approximate_ids):
        raise ValueError("approximate_ids must contain distinct IDs")
    return len(expected.intersection(approximate_ids)) / len(expected)

exact_top_5 = [10, 21, 34, 55, 89]
fast_but_weak = [10, 21, 8, 13, 5]
slower_but_better = [10, 21, 34, 55, 3]

print(f"fast candidate recall@5: {recall_at_k(exact_top_5, fast_but_weak):.0%}")
print(f"better candidate recall@5: {recall_at_k(exact_top_5, slower_but_better):.0%}")

fast candidate recall@5: 40%
better candidate recall@5: 80%

Recall gate: Latency without recall is incomplete. Keep an exact-search evaluation set, measure ANN recall against it, and choose an operating point on the Recall@K vs QPS Pareto frontier that satisfies your product SLA.

HNSW (Hierarchical Navigable Small World)

With exact search held as ground truth, start with HNSW when the working set can stay in memory. It provides a strong recall-latency trade-off without requiring an offline centroid-training phase.^{[3]Reference 3Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphshttps://arxiv.org/abs/1603.09320}

Skip-lists in high dimensions: layers skip, then search locally

To understand HNSW, picture a 1D skip-list: an ordered linked list with tiers of express pointers. With promotion probability $1/2$, level 1 contains about half the elements and level 2 about a quarter. One pointer can skip many elements; the whole search still takes multiple hops. HNSW borrows that hierarchy while replacing ordered-list pointers with proximity-graph edges.^{[3]Reference 3Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphshttps://arxiv.org/abs/1603.09320} The analogy explains sparse upper layers, not a universal logarithmic guarantee for arbitrary graphs and embeddings.

When inserting vector $v$, its maximum layer $\ell$ is drawn from an exponential decay distribution:

$P(\text{level} \ge \ell) = \exp(-\ell / m_L)$

For $M > 1$, setting the scale parameter to $m_L = 1 / \ln(M)$ produces an intuitive geometric progression:

$P(\text{level} \ge \ell) = \exp\left(-\ell \cdot \ln(M)\right) = M^{-\ell} = \left(\frac{1}{M}\right)^\ell$

The probability of reaching Layer 1 is $1/M$; reaching Layer 2 has probability $1/M^2$. Expected populations are $N$, $N/M$, and $N/M^2$. Near level $\log_M N$, the expected population is about one; the realized highest level and its population vary randomly. A stored entry point starts the search. Sparse upper layers can connect more distant regions than the dense base layer.

Upper-layer traversal uses greedy routing. Starting at the global entry point on the top layer, search evaluates the distance from query $q$ to each neighbor of the current node. If a neighbor is closer to $q$, search hops to that neighbor. It repeats this greedy walk until no neighbor is closer to $q$ than the current node. That identifies the local minimum on that layer. The search then drops down to the next lower layer at the exact same physical node, using that node as the entry point for the denser layer below.

At the base layer (Layer 0), a greedy walk can get trapped at a local minimum. HNSW uses a wider beam search with a retained result set bounded by $ef_{\text{search}}$. The expansion queue and visited set can exceed that size, so this parameter doesn't cap total distance evaluations or wall time. The search maintains two heaps:

1. candidates: A min-heap of visited, unexpanded nodes sorted by ascending distance to $q$.
2. results: A max-heap of size at most $ef_{\text{search}}$ storing the closest vectors encountered so far.

At each step, search pops the closest node $c$ from candidates. If it is farther than the worst retained result, the paper's search stops. This is an approximate stopping rule: a farther node could lead to a closer unseen node. Otherwise, previously unvisited neighbors enter both heaps when they improve the retained set or that set is still below capacity; overflowing results are pruned. Finally, search returns up to $k$ retained items.

Graph connectivity is governed by three critical knobs:

• M: Number of neighbors selected for a new node; implementations commonly use it as the upper-layer adjacency cap too. Reciprocal insertion followed by pruning can leave asymmetric links.
• M0: Layer-0 adjacency cap, commonly $2M$. A larger base-layer budget can improve connectivity at a memory cost; it doesn't guarantee a connected graph.
• ef_construction: The candidate beam size used during index insertion to select neighbors.

Why can't we simply connect each node to its $M$ nearest neighbors? If you connect a node only to its closest neighbors, those neighbors often cluster together in the same direction, creating redundant cliques with no edges pointing toward other clusters. A query approaching from another direction can't route past this cluster!

HNSW addresses redundant neighbors with a diversity heuristic (SELECT-NEIGHBORS-HEURISTIC). It examines candidates in ascending distance to the base node $v$. Its first selection pass accepts $e$ when:

$d(e, v) < d(e, n) \quad \forall n \in \text{selected}$

If $e$ is closer to a selected neighbor than to $v$, that pass treats it as redundant. This favors diverse routes but doesn't prove that an actual edge from the selected neighbor to $e$ exists. The paper also offers candidate extension and keepPrunedConnections, which can refill unused slots with initially rejected candidates. Connectivity and recall still depend on the built graph.^{[3]Reference 3Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphshttps://arxiv.org/abs/1603.09320}

A worked example: tracing one insertion

To see the layers work, insert one new runbook vector into a graph that already has a few nodes.

First, a random process samples the new node's top layer using $P(\text{level} \ge \ell) = (1/M)^\ell$. Most nodes live only on layer 0; a few appear higher, which keeps upper layers sparse.

Next, start at the current entry point and greedily walk each layer above the new node's top layer. Stop when no neighbor is closer, then drop down. Those upper layers locate a useful neighborhood without wiring the new node into distant parts of the graph.

On each layer the new node actually occupies, run a beam search retaining up to ef_construction candidates. Select up to M neighbors using the diversity heuristic and add links in both directions. Prune each overflowing adjacency list to its cap. Those local pruning decisions can leave asymmetric links; the final graph needn't be strictly undirected. The layer-0 cap is commonly 2M.

Finally, update the entry point only when the sampled level is above the graph's current maximum. Landing on an existing top layer changes local wiring, not the global starting point.

This incremental construction is why HNSW doesn't need an offline training phase. Every new vector is wired into the existing graph using local search.

Build a tiny graph, then search it

Insertion follows the paper's two phases: greedy descent through layers above the new node's top layer, then a wider construction search while wiring the layers it occupies.^{[3]Reference 3Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphshttps://arxiv.org/abs/1603.09320} Two simplifications keep the lab readable: it selects the nearest M candidates and carries only the nearest entry to the next layer. The paper also gives a diversity heuristic and carries the construction candidate set downward. Diversity can retain a route to a different cluster instead of spending every edge on near-duplicates.

The search loop uses two heaps. candidates expands the closest unexplored node first; results exposes the farthest retained node using negative distances. If the best unexplored distance is already worse than the full retained set, this search stops. That's an approximate stopping rule, not proof that every unseen vector is farther away.

Level sampling is exponential. sample_level is the random process a real builder uses. The lab then inserts with explicit levels so the wiring stays reproducible. Before running it, predict the distinction: the returned neighbors should match the exact top-2 in this tiny graph, but that result doesn't establish large-scale recall.

import heapq
import math
import random
from dataclasses import dataclass, field

def squared_l2(left: tuple[float, ...], right: tuple[float, ...]) -> float:
    if len(left) != len(right):
        raise ValueError("vectors must have equal dimensions")
    return sum((a - b) ** 2 for a, b in zip(left, right))

def sample_level(mL: float, rng: random.Random) -> int:
    u = max(rng.random(), 1e-12)
    return math.floor(-math.log(u) * mL)

@dataclass
class ToyHNSW:
    M: int = 2
    ef_construction: int = 4
    vectors: dict[int, tuple[float, ...]] = field(default_factory=dict)
    edges: dict[tuple[int, int], list[int]] = field(default_factory=dict)
    entry_point: int | None = None
    max_level: int = -1

    def neighbors(self, node_id: int, level: int) -> list[int]:
        return list(self.edges.get((node_id, level), []))

def greedy_search(graph: ToyHNSW, query: tuple[float, ...], entry_id: int, level: int) -> int:
    current = entry_id
    improved = True
    while improved:
        improved = False
        for neighbor in graph.neighbors(current, level):
            if squared_l2(query, graph.vectors[neighbor]) < squared_l2(query, graph.vectors[current]):
                current = neighbor
                improved = True
    return current

def search_layer(
    graph: ToyHNSW, query: tuple[float, ...], entry_id: int, level: int, ef: int
) -> list[int]:
    visited = {entry_id}
    entry_dist = squared_l2(query, graph.vectors[entry_id])
    candidates = [(entry_dist, entry_id)]
    results = [(-entry_dist, entry_id)]
    while candidates:
        dist, current = heapq.heappop(candidates)
        if len(results) >= ef and dist > -results[0][0]:
            break
        for neighbor in graph.neighbors(current, level):
            if neighbor in visited:
                continue
            visited.add(neighbor)
            neighbor_dist = squared_l2(query, graph.vectors[neighbor])
            if len(results) < ef or neighbor_dist < -results[0][0]:
                heapq.heappush(candidates, (neighbor_dist, neighbor))
                heapq.heappush(results, (-neighbor_dist, neighbor))
                if len(results) > ef:
                    heapq.heappop(results)
    return [node for _, node in sorted((-neg, node) for neg, node in results)]

def prune(graph: ToyHNSW, node_id: int, level: int, cap: int) -> None:
    linked = graph.edges[(node_id, level)]
    if len(linked) <= cap:
        return
    keep = sorted(
        linked, key=lambda other: squared_l2(graph.vectors[node_id], graph.vectors[other])
    )[:cap]
    graph.edges[(node_id, level)] = keep

def insert(graph: ToyHNSW, node_id: int, vector: tuple[float, ...], level: int) -> None:
    if node_id in graph.vectors:
        raise ValueError("insertion requires a new ID")
    if level < 0 or graph.M < 1 or graph.ef_construction < graph.M:
        raise ValueError("require level >= 0 and ef_construction >= M >= 1")
    if not vector or not all(math.isfinite(x) for x in vector):
        raise ValueError("vectors must be nonempty and finite")
    if graph.vectors and len(vector) != len(next(iter(graph.vectors.values()))):
        raise ValueError("vectors must have equal dimensions")
    graph.vectors[node_id] = vector
    for layer in range(level + 1):
        graph.edges.setdefault((node_id, layer), [])
    if graph.entry_point is None:
        graph.entry_point = node_id
        graph.max_level = level
        return

    entry = graph.entry_point
    for layer in range(graph.max_level, level, -1):
        entry = greedy_search(graph, vector, entry, layer)
    for layer in range(min(level, graph.max_level), -1, -1):
        candidates = search_layer(graph, vector, entry, layer, graph.ef_construction)
        chosen = sorted(candidates, key=lambda i: squared_l2(vector, graph.vectors[i]))[: graph.M]
        cap = 2 * graph.M if layer == 0 else graph.M
        for neighbor in chosen:
            if neighbor == node_id:
                continue
            if neighbor not in graph.edges[(node_id, layer)]:
                graph.edges[(node_id, layer)].append(neighbor)
            graph.edges.setdefault((neighbor, layer), [])
            if node_id not in graph.edges[(neighbor, layer)]:
                graph.edges[(neighbor, layer)].append(node_id)
            prune(graph, neighbor, layer, cap)
        prune(graph, node_id, layer, cap)
        entry = min(candidates, key=lambda i: squared_l2(vector, graph.vectors[i]))
    if level > graph.max_level:
        graph.entry_point = node_id
        graph.max_level = level

def search(graph: ToyHNSW, query: tuple[float, ...], k: int = 2, ef_search: int = 4) -> list[int]:
    if graph.entry_point is None:
        raise ValueError("empty graph")
    if k < 1 or ef_search < k:
        raise ValueError("require ef_search >= k >= 1")
    if not all(math.isfinite(x) for x in query):
        raise ValueError("query must be finite")
    current = graph.entry_point
    for layer in range(graph.max_level, 0, -1):
        current = greedy_search(graph, query, current, layer)
    candidates = search_layer(graph, query, current, 0, ef_search)
    return sorted(candidates, key=lambda i: squared_l2(query, graph.vectors[i]))[:k]

rng = random.Random(0)
mL = 1 / math.log(16)
draws = 0
level = 0
while level == 0:
    level = sample_level(mL, rng)
    draws += 1
print(f"mL for M=16: {mL:.3f}")
print(f"P(level >= 1) = {1 / 16:.1%}")
print(f"first upper-layer draw: level {level} after {draws} samples")

graph = ToyHNSW()
for node_id, vector, level in [
    (0, (0.0, 0.0), 1),
    (1, (0.2, 0.1), 0),
    (2, (0.3, 0.0), 1),
    (3, (5.0, 5.0), 0),
    (4, (5.1, 4.8), 0),
    (5, (0.1, 0.3), 0),
]:
    insert(graph, node_id, vector, level)

query = (0.25, 0.05)
nearest_ids = search(graph, query, k=2, ef_search=4)
exact_ids = sorted(graph.vectors, key=lambda i: squared_l2(query, graph.vectors[i]))[:2]
print(f"nearest ids: {nearest_ids}")
print(f"exact top-2: {exact_ids}")

# A search-only counterexample, not a claim about this builder's output.
bridge = ToyHNSW(
    vectors={0: (0.9, 0.0), 1: (2.0, 0.0), 2: (0.1, 0.0)},
    edges={(0, 0): [1], (1, 0): [2], (2, 0): []},
    entry_point=0,
    max_level=0,
)
print(f"farther bridge, ef=1: {search(bridge, (0.0, 0.0), k=1, ef_search=1)}")
print(f"farther bridge, ef=3: {search(bridge, (0.0, 0.0), k=1, ef_search=3)}")

mL for M=16: 0.361
P(level >= 1) = 6.2%
first upper-layer draw: level 1 after 36 samples
nearest ids: [1, 2]
exact top-2: [1, 2]
farther bridge, ef=1: [0]
farther bridge, ef=3: [2]

The lab returns the exact top-2 for these six vectors. Agreement on this query checks the example, not the correctness of all possible graph builds or large-scale recall. Nearest-only pruning can discard useful cross-cluster routes, which is one reason to use a maintained implementation for real indexes.

In the second graph, node 1 is farther from the query than entry node 0, but it is the only route to the true nearest node 2. With ef=1, it isn't admitted for expansion. With ef=3, it survives and reveals node 2. The beam budget buys exploration, not a certificate that every unexplored route is useless.

If you set ef_search = 5 but ask for k = 10, this lab rejects the request. Hnswlib documents that ef must be at least k; other systems can raise the effective budget or return fewer results.^{[4]Reference 4HNSW algorithm parametershttps://github.com/nmslib/hnswlib/blob/master/ALGO_PARAMS.md[2]Reference 2pgvectorhttps://github.com/pgvector/pgvector} Even a valid budget slightly larger than k can miss better neighbors outside the explored region.

Common mistake: Setting ef_search from intuition rather than an evaluation curve. A small beam can miss true neighbors; an unnecessarily large beam spends latency without a useful recall gain. Measure ef_search values against exact top-k results on representative queries.

Key parameters

M, ef_construction, and ef_search are the knobs that actually move recall, RAM, build time, and latency. Use the table as a starting map, then measure on your queries before copying a default.

These settings illustrate separate controls, not recommended defaults. With the lab's sampling rule, the probability of reaching layer $\ell$ is $\exp(-\ell/m_L)$. Setting $m_L=1/\ln(M)$ gives probability $1/M$ of reaching layer 1.^{[3]Reference 3Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphshttps://arxiv.org/abs/1603.09320}

At 4 bytes per packed neighbor ID, $M=16$ permits 128 bytes of layer-0 IDs beside a 1,536-dimensional float32 vector (6,144 bytes). Vectors dominate this partial budget. Upper-layer links, per-node headers, allocation, metadata, replicas, and retained originals add storage too. Graph links can become a large fraction after vector compression or with fewer dimensions.

def hnsw_layer0_bytes_per_vector(dimensions: int, M: int) -> dict[str, int]:
    vector = dimensions * 4
    neighbor_ids = (2 * M) * 4
    return {
        "vector": vector,
        "layer0_ids": neighbor_ids,
        "total": vector + neighbor_ids,
    }

budget = hnsw_layer0_bytes_per_vector(1536, 16)
print(f"float32 vector: {budget['vector']:,} bytes")
print(f"layer-0 ids at M=16: {budget['layer0_ids']:,} bytes")
print(f"vector share: {budget['vector'] / budget['total']:.1%}")

float32 vector: 6,144 bytes
layer-0 ids at M=16: 128 bytes
vector share: 98.0%

ef_search can change at query time without rebuilding. This decision exercise uses invented measurements, not a benchmark of any library or machine. It selects the lowest-p95 setting meeting both constraints and refuses to choose when no setting qualifies.

measurements = [
    {"ef_search": 24, "recall": 0.91, "p95_ms": 4.1},
    {"ef_search": 48, "recall": 0.97, "p95_ms": 6.8},
    {"ef_search": 96, "recall": 0.985, "p95_ms": 12.4},
]
required_recall = 0.96
latency_budget_ms = 10.0

eligible = [
    point for point in measurements
    if point["recall"] >= required_recall and point["p95_ms"] <= latency_budget_ms
]
if not eligible:
    raise RuntimeError("no tested setting meets both recall and latency constraints")
choice = min(eligible, key=lambda point: point["p95_ms"])
print(f"release ef_search={choice['ef_search']} recall={choice['recall']:.3f} p95_ms={choice['p95_ms']}")

release ef_search=48 recall=0.970 p95_ms=6.8

IVF (Inverted File Index)

HNSW chooses where to search through graph links. IVF (Inverted File Index) makes that choice through coarse geometric space partitioning. Under Euclidean distance, $k$-means clustering partitions continuous space $\mathbb{R}^d$ into $K = \text{nlist}$ discrete Voronoi cells:

$V_i = \{x \in \mathbb{R}^d \mid ||x - c_i||^2 \le ||x - c_j||^2 \; \forall j \ne i\}$

Each cell is represented by its centroid $c_i$. Search evaluates query distance against these coarse centroids first, then opens only selected inverted posting lists.

Centroids select lists

Ask the same question as before: where can we avoid work without losing the rollback runbook? If a true neighbor sits just across a partition boundary, opening only the closest partition will miss it completely. IVF protects against that miss by probing a configurable subset of coarse regions rather than committing to just one.

Training happens offline before serving begins. Run K-means clustering on a representative sample of embeddings to learn $\text{nlist}$ cluster centroids. In Faiss terminology, those centroids form the coarse quantizer.

During indexing, choose a list ID $i(x) = \arg\min_j ||x - c_j||^2$ and append the record ID and representation to that list. The centroid is the vector $c_{i(x)}$, whereas the argmin returns an integer. Lists group IDs with full-precision vectors in IVF-Flat or compressed codes in IVF-PQ; their physical allocation and storage layout depend on the backend.

With a flat coarse quantizer, query $q$ scores all $\text{nlist}$ centroids ($O(\text{nlist} \cdot d)$ scalar work) and selects the closest $n_{\text{probe}}$ cells. Top-list selection doesn't require sorting every centroid. Search then scans the selected lists. Faiss also supports an HNSW approximate coarse quantizer, changing the routing cost and introducing possible centroid-search misses.^{[5]Reference 5Faiss indexeshttps://github.com/facebookresearch/faiss/wiki/Faiss-indexes}

IVF-Flat scores full-precision vectors inside the probed lists. IVF-PQ instead scores compressed codes using asymmetric distance computation (ADC).^{[6]Reference 6Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

A worked example: counting comparisons

Suppose you have 1 million embeddings with 128 dimensions. Compare brute force against IVF with nlist = 1,024 and nprobe = 5. Brute force performs $1{,}000{,}000$ distance computations per query.

IVF first scores its $1{,}024$ centroids. With balanced lists, each list averages $1{,}000{,}000 / 1{,}024 = 976.5625$ vectors, so five probes add about $5 \times 976.5625 \approx 4{,}883$ vector scores.

Together, centroid scoring and list scans cost roughly $5{,}907$ distance computations, about 169× fewer than the flat scan. That isn't a latency speedup: this arithmetic contains no time measurement. List imbalance, batching, memory access, top-k selection, and hardware change the cost per score. nlist = 1,024 is a teaching number, not a universal default.

def balanced_ivf_scores(total_vectors: int, nlist: int, nprobe: int) -> int:
    return nlist + round(total_vectors / nlist * nprobe)

total_vectors = 1_000_000
nlist = 1_024
nprobe = 5
estimated_scores = balanced_ivf_scores(total_vectors, nlist, nprobe)

print(f"flat vector scores: {total_vectors:,}")
print(f"balanced IVF vector and centroid scores: {estimated_scores:,}")
print(f"estimated reduction: {total_vectors / estimated_scores:.1f}x")

flat vector scores: 1,000,000
balanced IVF vector and centroid scores: 5,907
estimated reduction: 169.3x

A boundary miss: nprobe = 1 drops a true neighbor

Before running the lab, predict what nprobe = 1 keeps. Query (4.9, 0) is closer to centroid 0, so only list 0 opens. Vector 3 at (5.4, 0) is the true second neighbor, but it lives in list 1 and stays invisible until both lists are probed.

The example uses two hand-set centroids: payments-like vectors near the origin and GPU-like vectors near (10, 0). It isolates the failure mode without hiding it behind clustering noise.

Faiss's IndexIVFFlat is the production form of this loop: train centroids, assign inverted lists, then search with nprobe.^{[6]Reference 6Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

def squared_l2(left: tuple[float, ...], right: tuple[float, ...]) -> float:
    return sum((a - b) ** 2 for a, b in zip(left, right))

centroids = {0: (0.0, 0.0), 1: (10.0, 0.0)}
vectors = {
    0: (0.2, 0.1),
    1: (0.4, -0.1),
    2: (4.6, 0.0),
    3: (5.4, 0.0),
    4: (9.8, 0.2),
}

def nearest_centroid(vector: tuple[float, ...]) -> int:
    return min(centroids, key=lambda cid: squared_l2(vector, centroids[cid]))

inverted_lists: dict[int, list[int]] = {0: [], 1: []}
for vector_id, vector in vectors.items():
    inverted_lists[nearest_centroid(vector)].append(vector_id)

def ivf_search(query: tuple[float, ...], nprobe: int, k: int = 2) -> tuple[list[int], list[int]]:
    if not 1 <= nprobe <= len(centroids) or k < 1:
        raise ValueError("require 1 <= nprobe <= nlist and k >= 1")
    ranked_lists = sorted(centroids, key=lambda cid: squared_l2(query, centroids[cid]))[:nprobe]
    scored: list[tuple[float, int]] = []
    for list_id in ranked_lists:
        for vector_id in inverted_lists[list_id]:
            scored.append((squared_l2(query, vectors[vector_id]), vector_id))
    scored.sort()
    return [vector_id for _, vector_id in scored[:k]], ranked_lists

query = (4.9, 0.0)
exact = sorted(vectors, key=lambda vid: squared_l2(query, vectors[vid]))[:2]
nprobe_1, lists_1 = ivf_search(query, nprobe=1)
nprobe_2, lists_2 = ivf_search(query, nprobe=2)

print(f"inverted lists: {inverted_lists}")
print(f"exact top-2: {exact}")
print(f"nprobe=1 lists {lists_1} -> {nprobe_1}")
print(f"nprobe=2 lists {lists_2} -> {nprobe_2}")

inverted lists: {0: [0, 1, 2], 1: [3, 4]}
exact top-2: [2, 3]
nprobe=1 lists [0] -> [2, 1]
nprobe=2 lists [0, 1] -> [2, 3]

nprobe is the main query-time knob. With balanced lists, the scanned fraction is about nprobe / nlist. Adding lists adds candidates. For IVF-Flat with exact centroid ordering, nested probed sets, consistent ties, and no other scan limit, this can't lower ANN recall. With PQ scoring, however, extra candidates can displace a true neighbor through quantization errors; final recall against originals needn't rise monotonically.

Scanning every list makes IVF-Flat exhaustive when no other scan limit is active. It doesn't make IVF-PQ exact against the original vectors: quantization still changes scores. A larger list budget repairs partition misses, not information lost in compression.

Distance metrics

Before comparing index families, fix the ranking rule. The same stored vectors can produce a different neighbor order when magnitude matters, so changing the metric changes both search and any IVF centroids trained for it. Faiss supports L2 and inner product across its main ANN indexes; cosine similarity can use normalized vectors with inner product search.^{[7]Reference 7MetricType and distanceshttps://github.com/facebookresearch/faiss/wiki/MetricType-and-distances}

L2 distance measures straight-line separation. Faiss returns squared L2 distance, avoiding the square root without changing the ordering. Choose the metric expected by the embedding model, not a rule that all semantic search must use cosine.

Inner product (IP) ranks by maximum dot-product. Query norm doesn't affect ranking, but database vector norms do, so large-norm items can dominate if that's how the embeddings behave.

Cosine similarity ignores magnitude and keeps only direction. Normalize both database and query vectors, then use inner product search. On normalized vectors, L2 and inner product give equivalent rankings because $||x-y||^2 = 2 - 2\langle x, y \rangle$.

If you move from raw L2 geometry to cosine, normalize the training and stored vectors and retrain the coarse quantizer. A metric-name change alone doesn't logically require retraining: normalized L2 and IP give equivalent rankings when both operands are unit vectors. But unit database vectors don't imply unit centroids. Check coarse routing, centroid normalization, and any compressed scoring as well as final-vector ranking before reusing an index.

import math

def normalize(vector: list[float]) -> list[float]:
    norm = math.sqrt(sum(value * value for value in vector))
    if norm == 0 or not math.isfinite(norm):
        raise ValueError("cosine requires a finite nonzero vector")
    return [value / norm for value in vector]

vectors = [[3.0, 0.0], [1.0, 1.0], [0.0, 2.0]]
query = [1.0, 0.8]
normalized_vectors = [normalize(vector) for vector in vectors]
normalized_query = normalize(query)
inner_product = [
    sum(left * right for left, right in zip(vector, normalized_query))
    for vector in normalized_vectors
]
l2 = [
    sum((left - right) ** 2 for left, right in zip(vector, normalized_query))
    for vector in normalized_vectors
]

print(f"inner-product rank: {sorted(range(3), key=lambda i: -inner_product[i])}")
print(f"L2 rank after normalization: {sorted(range(3), key=lambda i: l2[i])}")

inner-product rank: [1, 0, 2]
L2 rank after normalization: [1, 0, 2]

HNSW vs IVF

IVF requires a training step on representative data before indexing. If the vector distribution drifts, stale centroids can unbalance lists or lower recall; retraining means reassigning and rebuilding the index, not just replacing centroid coordinates. Uncompressed HNSW has no codebook-training step, but insertion order and graph quality still affect recall.

Graph search and compression aren't mutually exclusive. Faiss exposes IndexHNSWFlat, IndexHNSWSQ, and IndexHNSWPQ; compressed variants introduce their own training and accuracy trade-offs.^{[5]Reference 5Faiss indexeshttps://github.com/facebookresearch/faiss/wiki/Faiss-indexes} The table compares HNSW with raw storage against IVF-Flat, not every possible encoding.

Product Quantization (PQ)

Neither HNSW's links nor IVF-Flat's partitions remove the raw vectors. For a separate capacity exercise, use a 768-dimensional embedding model and one billion records. This changes the dimension from the earlier 1,536-dimensional example; it's an illustrative storage choice, not a free conversion of the existing index.

$10^9 \text{ vectors} \times 768 \text{ dims} \times 4 \text{ bytes} \approx 3 \text{ TB raw vector storage}$

One billion vectors at 768 float32 dimensions need about 3 TB of raw vector storage alone. Add index overhead, operating-system buffers, and application memory on top of that.

Product Quantization (PQ) compresses vectors by breaking them into smaller chunks and quantizing those chunks independently.^{[8]Reference 8Product Quantization for Nearest Neighbor Search.https://doi.org/10.1109/TPAMI.2010.57} Combined with IVF, PQ is one established way to make billion-point memory budgets tractable; whether a deployment also needs sharding depends on code size, metadata, throughput, and availability requirements.

The algorithm

Product quantization splits coordinates into disjoint subspaces and quantizes each separately.^{[8]Reference 8Product Quantization for Nearest Neighbor Search.https://doi.org/10.1109/TPAMI.2010.57} This is a factorized representation, not an assumption that the data's chunks are statistically independent. With 96 sub-codebooks of 256 entries, the Cartesian product has $256^{96} = 2^{768}$ possible reconstructed vectors, using just $96 \times 256$ stored sub-centroids. A flat codebook explicitly storing all those combinations would be impractical. How accurately that product represents your data remains an empirical question.

Decompose a $d$-dimensional vector $x \in \mathbb{R}^d$ into $m$ equal subvectors:

$x = [u_1, u_2, \dots, u_m], \quad u_j \in \mathbb{R}^{d^*}, \quad d^* = d / m$

For a 768-dimensional embedding with $m = 96$, each subvector has dimension $d^* = 768 / 96 = 8$.

Next, cluster each subspace separately. Run $k$-means on training data to learn a codebook $C_j$ of $K^* = 256$ centroids for each subspace. Why exactly 256 centroids? Because $256 = 2^8$. An integer index in $[0, 255]$ fits into a single unsigned 8-bit byte (uint8).

Finally, map each subvector $u_j$ to the index of its nearest centroid in codebook $C_j$:

$\text{code}_j(x) = \arg\min_{k \in \{0, \dots, 255\}} ||u_j - c_{j, k}||^2$

The original 768-dimensional float32 vector (3,072 bytes) becomes $m = 96$ single-byte IDs: 32× compression for the code alone. These 96 float32 codebooks consume $96 \times 256 \times 8 \times 4 = 786{,}432$ bytes, or 768 KiB, shared across records in this setup.

In L2 IVF-PQ, codes normally represent the residual $r = x - c_{\text{list}}$.^{[9]Reference 9Faiss Implementation Noteshttps://github.com/facebookresearch/faiss/wiki/Implementation-notes} The coarse centroid captures part of the vector, leaving PQ to encode deviations within lists. This can improve reconstruction at a given code budget. Moving data near the origin alone isn't a proof of lower error: translating a distribution and its codebook together leaves reconstruction error unchanged.

With 256 centroids, an ID requires one byte ($2^8 = 256$). The 3,072-byte vector becomes 96 single-byte IDs: 32× compression for the code alone. Record IDs, coarse centroids, and other index state add separate overhead.

def bytes_per_raw_vector(dimensions: int) -> int:
    return dimensions * 4

def bytes_per_pq_code(chunks: int, bits_per_chunk: int = 8) -> int:
    return (chunks * bits_per_chunk + 7) // 8

raw_bytes = bytes_per_raw_vector(768)
code_bytes = bytes_per_pq_code(96)
ivf_pq_bytes_with_id = code_bytes + 8

print(f"raw vector bytes: {raw_bytes}")
print(f"PQ code bytes: {code_bytes}")
print(f"IVF-PQ code plus 64-bit id bytes: {ivf_pq_bytes_with_id}")
print(f"raw-to-code compression: {raw_bytes / code_bytes:.0f}x")

raw vector bytes: 3072
PQ code bytes: 96
IVF-PQ code plus 64-bit id bytes: 104
raw-to-code compression: 32x

OPQ: rotating before you split

Plain PQ has a weakness: it splits dimensions into fixed contiguous chunks. If the variance in your embeddings is unevenly spread across dimensions, some subspaces carry most of the signal while others are nearly constant. Their codebooks spend centroids on uninformative directions.

Optimized Product Quantization (OPQ) learns an orthogonal rotation matrix $R$ together with the codebooks to reduce reconstruction error.^{[10]Reference 10Optimized Product Quantization for Approximate Nearest Neighbor Searchhttps://openaccess.thecvf.com/content_cvpr_2013/html/Ge_Optimized_Product_Quantization_2013_CVPR_paper.html} Rotating can improve how information is distributed across chunks, but simply balancing variance isn't the full optimization objective. A square orthogonal rotation preserves L2 distances: it adds a matrix multiply without losing information before quantization.

In Faiss you can request OPQ96,IVF4096,PQ96 to retain the original dimension, or OPQ96_384,IVF4096,PQ96 to output 384 dimensions, with 4 dimensions per chunk.^{[11]Reference 11The index factoryhttps://github.com/facebookresearch/faiss/wiki/The-index-factory} The dimension-reducing version is a projection: unlike a square orthogonal rotation, it can lose information and doesn't preserve all original L2 distances. Both transform stored vectors as well as queries. Benchmark OPQ at the same code size; its benefit depends on the distribution and training sample.

Asymmetric distance computation (ADC)

How can search score compressed PQ codes without first reconstructing each full vector? Reconstruction is possible, but adds work that the product structure lets us avoid.

This is where Asymmetric Distance Computation (ADC) shines. In ADC, the query $q$ remains completely uncompressed! The database vectors remain compressed as $m$-byte codes.

When query $q$ arrives:

1. Slice $q$ into $m$ subvectors: $[q_1, q_2, \dots, q_m]$.
2. Precompute a distance lookup table (LUT) of shape $m \times 256$, where cell $(j, k)$ stores the squared distance between query subvector $q_j$ and centroid $k$ of codebook $C_j$:

$T[j][k] = ||q_j - c_{j, k}||^2 \quad \text{for } j \in \{1, \dots, m\}, \; k \in \{0, \dots, 255\}$

With float32 entries, the table occupies $m \times 256 \times 4$ bytes. For $m=96$, that is 98,304 bytes, exactly 96 KiB. It can fit in some CPU caches; capacity, competing working sets, access patterns, and implementation determine actual residency. Additional precomputed IVF-PQ tables can be much larger.^{[9]Reference 9Faiss Implementation Noteshttps://github.com/facebookresearch/faiss/wiki/Implementation-notes}

Now, to score any stored database vector $y$ encoded as $[c_1, c_2, \dots, c_m]$, the squared Euclidean distance is simply:

$d(q, y)^2 \approx d(q, C(y))^2 = \sum_{j=1}^{m} T[j][c_j]$

After table construction, the basic score uses $m$ indexed floating-point distances and $O(m)$ additions, plus reading the byte-sized codes. It needs no full-vector reconstruction or per-coordinate multiplication in that loop. The indices are bytes; the ordinary table values aren't. Specialized kernels may use different table representations, and this operation count doesn't promise cache hits or a particular speedup.

For L2 IVF-PQ, Faiss normally encodes the residual after subtracting the coarse centroid.^{[9]Reference 9Faiss Implementation Noteshttps://github.com/facebookresearch/faiss/wiki/Implementation-notes} ADC compares the query residual $(q - c_{\text{list}})$ with those codes; optimized implementations can combine precomputed terms instead of rebuilding every table from scratch. The lab uses non-residual PQ and floating-point distances, not Hamming distance between codes.

def squared_l2(left: list[float], right: list[float]) -> float:
    return sum((a - b) ** 2 for a, b in zip(left, right))

def adc_pq_search(
    query: list[float],
    pq_codes: list[list[int]],
    codebooks: list[list[list[float]]],
    k: int = 2,
) -> list[int]:
    subspaces = len(codebooks)
    if not subspaces or not query or len(query) % subspaces:
        raise ValueError("query dimensions must split evenly into nonempty subspaces")
    dim_per_chunk = len(query) // subspaces
    if k < 1 or any(not book for book in codebooks):
        raise ValueError("require k >= 1 and nonempty codebooks")
    if any(len(centroid) != dim_per_chunk for book in codebooks for centroid in book):
        raise ValueError("codebook centroid has the wrong chunk dimension")
    if any(len(row) != subspaces for row in pq_codes):
        raise ValueError("each code needs one ID per subspace")
    if any(code < 0 or code >= len(codebooks[j]) for row in pq_codes for j, code in enumerate(row)):
        raise ValueError("code ID is outside its codebook")
    tables = []
    for index, codebook in enumerate(codebooks):
        query_chunk = query[index * dim_per_chunk : (index + 1) * dim_per_chunk]
        tables.append([squared_l2(query_chunk, centroid) for centroid in codebook])

    distances = []
    for row in pq_codes:
        distances.append(sum(tables[index][code] for index, code in enumerate(row)))
    ranked = sorted(range(len(pq_codes)), key=lambda vector_id: (distances[vector_id], vector_id))
    return ranked[:k]

query = [0.0, 0.0, 0.0, 0.0]
codebooks = [
    [[0.0, 0.0], [2.0, 0.0], [0.0, 2.0], [2.0, 2.0]],
    [[0.0, 0.0], [2.0, 0.0], [0.0, 2.0], [2.0, 2.0]],
]
pq_codes = [
    [0, 0],
    [1, 0],
    [0, 1],
    [1, 1],
]

print(f"nearest ids: {adc_pq_search(query, pq_codes, codebooks, k=2)}")
reconstructed = [
    [value for j, code in enumerate(row) for value in codebooks[j][code]]
    for row in pq_codes
]
print(f"reconstructed squared distances: {[squared_l2(query, row) for row in reconstructed]}")

collision_query = [0.9, 0.0, 0.0, 0.0]
originals = [[0.1, 0.0, 0.0, 0.0], [0.9, 0.0, 0.0, 0.0]]
# Both originals map to centroid 0 in each chunk of these codebooks.
same_codes = [[0, 0], [0, 0]]
compressed_top_1 = adc_pq_search(collision_query, same_codes, codebooks, k=1)
exact_top_1 = sorted(range(2), key=lambda i: squared_l2(collision_query, originals[i]))[:1]
reranked_top_1 = sorted(compressed_top_1, key=lambda i: squared_l2(collision_query, originals[i]))[:1]
overfetched = adc_pq_search(collision_query, same_codes, codebooks, k=2)
reranked_top_2 = sorted(overfetched, key=lambda i: squared_l2(collision_query, originals[i]))[:1]
print(f"same-code compressed top-1: {compressed_top_1}")
print(f"original-vector top-1: {exact_top_1}")
print(f"rerank retrieved top-1: {reranked_top_1}")
print(f"rerank overfetched top-2 to top-1: {reranked_top_2}")

nearest ids: [0, 1]
reconstructed squared distances: [0.0, 4.0, 4.0, 8.0]
same-code compressed top-1: [0]
original-vector top-1: [1]
rerank retrieved top-1: [0]
rerank overfetched top-2 to top-1: [1]

IDs 1 and 2 tie at squared distance 4, so the lab breaks that tie by ID. These are exact distances to the reconstructed vectors, not necessarily the original embeddings. Two different originals can receive the same PQ code and become indistinguishable. Full-precision reranking can repair their order only if both survived candidate retrieval and their originals are available.

Filtered search

An index can deliver 99% recall on unfiltered queries and still fail catastrophically once access controls or business metadata narrow the candidate pool. Suppose a support assistant queries: "runbooks like this incident, but only from the last 30 days and restricted to the EU region." Before choosing a filter strategy, predict the failure: will the filter shrink work, starve the candidate buffer, or sever graph routes needed to reach valid documents? Three strategies make that trade-off concrete.

Filter then exact scan: Resolve the predicate, perhaps through a metadata index, then score all eligible vectors. A 200-record subset needs far less distance work than a 10-million-record subset; neither count specifies milliseconds. This is one form of pre-filtering, but the term also covers filtered ANN. Removing every disallowed node from graph traversal can sever routes to eligible nodes, so a small eligible subset doesn't automatically imply good graph-search recall.

Post-filtering: Retrieve an ANN buffer of size $L$, then discard nonmatches. This can cause buffer starvation. As a toy model, suppose each retrieved candidate has matching probability $s=0.005$. With $L=100$, linearity of expectation gives:

$E[M] = L \cdot s = 100 \times 0.005 = 0.5$

If those match indicators are also independent, the probability of an empty buffer is:

$P(M = 0) = (1 - s)^L = (0.995)^{100} \approx 60.6\%$

That 60.6% is a model prediction, not an observed query rate. Global metadata selectivity needn't equal selectivity near a query, and neighboring candidates' metadata can be correlated. Even within this model, the buffer can contain more than two matches; low expectation isn't a maximum.

Compare two distributions with the same expected count. In the second, the entire buffer shares one matching indicator: either all 100 match, or none do.

L = 100
s = 0.005
print(f"expected matches in either model: {L * s:.2f}")
print(f"independent-candidate empty probability: {(1 - s) ** L:.1%}")
print(f"fully correlated empty probability: {1 - s:.1%}")

expected matches in either model: 0.50
independent-candidate empty probability: 60.6%
fully correlated empty probability: 99.5%

pgvector supports iterative ANN scans that expand exploration until enough results are found or configured scan/resource limits are reached. Relevant controls include hnsw.max_scan_tuples, hnsw.scan_mem_multiplier, and ivfflat.max_probes; these aren't automatic latency deadlines. Its HNSW iterative scan supports strict or relaxed ordering, while IVFFlat supports relaxed ordering.^{[2]Reference 2pgvectorhttps://github.com/pgvector/pgvector} Check the current version's supported modes and measure filtered recall separately.

Filter-aware graph traversal: An allow-list identifies eligible results while traversal retains ways to reach them. Weaviate's sweeping strategy can traverse disallowed nodes without returning them. Its custom ACORN, inspired by the research algorithm, instead skips distance evaluations for nonmatches and uses multi-hop traversal plus eligible entry points to find matching regions.^{[12]Reference 12ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Datahttps://arxiv.org/abs/2403.04871[13]Reference 13Filteringhttps://docs.weaviate.io/weaviate/concepts/filtering} The documentation checked September 22, 2026 names ACORN the default since v1.34. These are different search strategies; neither guarantees high recall for every filtered workload.

Filter placement changes which work is done before scoring and which candidates can reach the result set:

Authorization must be enforced inside a trusted boundary, independently of the retrieval strategy. Database-side post-filtering is safe if unauthorized rows never leave that boundary. App-side filtering after fetching privileged text can expose it to logs, traces, caches, or partial failures. Graph traversal may inspect disallowed vectors internally without returning them; that isn't the same as granting the application access. RAG Security & Access Control develops that distinction.

candidate_ids = ["eu-1", "us-1", "us-2", "us-3", "eu-2"]
region = {"eu-1": "eu", "us-1": "us", "us-2": "us", "us-3": "us", "eu-2": "eu"}

def post_filter(candidates: list[str], required_region: str, k: int) -> list[str]:
    return [item for item in candidates if region[item] == required_region][:k]

initial_candidates = candidate_ids[:3]
expanded_candidates = candidate_ids

print(f"initial result: {post_filter(initial_candidates, 'eu', k=2)}")
print(f"expanded result: {post_filter(expanded_candidates, 'eu', k=2)}")

initial result: ['eu-1']
expanded result: ['eu-1', 'eu-2']

Four questions before choosing a database

When you evaluate a vector database, ask four questions that survive vendor churn. Each one connects an index choice to an operating constraint:

1. Which ANN families are exposed: HNSW, IVF, PQ, disk-backed graphs, or a managed index whose internals aren't exposed?
2. How does filtered search work: before search, after search, or during traversal?
3. Where does the index body live: RAM, SSD, or object storage?
4. Which compression knobs are available, and what recall do they cost?

That framing travels better than product trivia. As a working heuristic, Postgres-style extensions expose a small set of explicit index types such as HNSW or IVFFlat inside SQL workflows.

General-purpose vector databases often center HNSW for RAM-resident search, then layer in quantization and filter-aware traversal. That makes filtered-search behavior part of the index evaluation, not a later integration detail.

Faiss and Faiss-derived stacks expose broad ANN menus, which shifts more tuning responsibility onto the engineer. The freedom is useful when you can own benchmarking and deployment decisions.

Storage-first systems move more bytes out of RAM and onto SSD or object storage. Measure the resulting storage cost and I/O latency together; moving bytes alone doesn't establish lower total serving cost.

These questions lead to a workload decision, not a vendor slogan: HNSW is a candidate when you want strong in-memory recall without centroid training, while IVF and PQ are candidates when scan fraction or bytes per vector become central constraints. Choose from measured recall, tail latency, build/update cost, and memory on your workload.

Scaling to billions

When the rollback corpus grows past RAM, two budgets compete: compress the vectors, or move most of the index body to storage. A billion-vector incident-search platform might compress each trace-summary vector with PQ, keep a sparse graph in memory, or compare both against a sharded design. The right branch depends on bytes, recall, and tail latency together.

1. Hybrid approaches (IVF-PQ)

Combining IVF (to reduce search scope) and PQ (to compress vectors) targets both budgets. In Faiss, IndexIVFPQ stores ceil(m_pq * nbits / 8) + 8 bytes per vector for the code and 64-bit record ID.^{[5]Reference 5Faiss indexeshttps://github.com/facebookresearch/faiss/wiki/Faiss-indexes} A 32-byte code therefore uses about 40 GB for 1B records before shared codebooks and other overhead. The earlier 96-byte code instead needs about 104 GB including IDs. Smaller codes buy capacity at a potentially larger quantization error.

2. Disk-based indexes (DiskANN)

Microsoft's DiskANN^{[14]Reference 14DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.https://proceedings.neurips.cc/paper/2019/hash/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Abstract.html} keeps a compact in-memory structure and places the large graph body on SSD. The graph is still navigational, but its layout is optimized for storage access rather than assuming every edge traversal hits RAM. Search quality therefore depends on read amplification and layout as well as graph degree and beam width.

The NeurIPS 2019 paper abstract reports >5000 queries per second, <3 ms mean latency, and 95%+ 1-recall@1 on SIFT1B on a 16-core machine with 64 GB RAM plus SSD. Those are benchmark-specific measurements, not a universal promise for every embedding workload.

3. Distributed sharding

Horizontal sharding can divide storage and query work across machines. It also changes result completeness and latency. The full-fan-out design below is one possible architecture; real services may route to selected partitions or replicas rather than broadcasting every query everywhere.

Suppose the corpus is split across $S$ disjoint shards. This example runs two phases:

1. Scatter: A coordinator sends the query and candidate cutoff to every shard. Each searches its local index and returns a ranked list of IDs and scores. Choose a local cutoff $L \ge K$ if later reranking needs an overfetched buffer.
2. Gather: Merge the $S$ sorted lists using comparable scores, keeping the best $K$. This is an $S$-way merge, because $S$ is the number of input streams. With overfetching, the coordinator can instead fetch originals for the $S L$ candidates and rerank before cutting to $K$. Different PQ codebooks introduce different score errors; comparing their estimates doesn't establish the exact original-vector order.

For disjoint shards using the same exact metric, vector representation, and tie order, local top-$K$ sets suffice: an omitted item already has $K$ predecessors on its own shard, so it can't enter the global top-$K$. This proof assumes every required shard responds. With ANN, a coordinator can't recover locally missed candidates. Exact reranking only repairs the order of candidates it receives; overfetching can improve coverage but doesn't guarantee it. Deduplication or document grouping can also require more than $K$ local results.

Waiting for all shards can amplify latency tails. Let $T_i$ measure each response's elapsed time from a common fan-out start, including its network round trip. Let $T_{\text{merge}}$ be the final reduction work done after the last response. Then:

$T_{\text{query}} \ge \max(T_1, T_2, \dots, T_S) + T_{\text{merge}}$

Streaming can overlap earlier merge work with arrivals; only the remaining work belongs in that final term. To reason about tails, use a time threshold $t_{99}$ such that each shard's latency distribution satisfies $P(T_i \le t_{99})=0.99$. The probability 0.99 is dimensionless; $t_{99}$ is measured in time. If shard latencies are independent:

$P\!\left(\max_i T_i \le t_{99}\right) = \prod_{i=1}^{S} P(T_i \le t_{99}) = (0.99)^S$

Under that model, four shards meet the single-shard threshold 96.1% of the time; twenty meet it 81.8% of the time, before merge overhead. For independent identically distributed shard latencies, a cluster's 99th percentile of the maximum corresponds to single-shard CDF value $0.99^{1/S}$. With twenty shards, that's about the 99.95th percentile, not the 99.9th. Perfectly correlated latencies instead meet the common threshold 99% of the time. Shared infrastructure makes the dependence an empirical question.

for shards in (4, 20):
    print(f"{shards} independent shards within single-shard t99: {0.99 ** shards:.1%}")
print(f"single-shard percentile for 20-shard maximum p99: {100 * 0.99 ** (1 / 20):.4f}%")
print(f"perfectly correlated shards within common t99: {0.99:.1%}")

4 independent shards within single-shard t99: 96.1%
20 independent shards within single-shard t99: 81.8%
single-shard percentile for 20-shard maximum p99: 99.9498%
perfectly correlated shards within common t99: 99.0%

Hedged requests send a backup to another replica after a chosen delay. Tune that delay against measured latency and extra load rather than prescribing p95 universally. Per-shard deadlines can bound waiting, but missing-shard responses must be identified as partial; they no longer carry the exact global-top-$K$ guarantee.

When vector indexes break

Most failures announce themselves as one of three symptoms: recall drops after the data or metric changes, results underfill after filtering or deletes, or p99 rises while local work looks healthy. Use the table to connect each symptom to the budget that moved and the evidence needed before changing a knob.

Index family trade-offs

Evaluate HNSW when you can afford RAM and need low-latency high-recall retrieval. Evaluate IVF-PQ when raw vector storage becomes the bottleneck. Consider DiskANN-style systems when a graph index remains attractive but the index body no longer fits in memory. In each case, release from a recall-and-latency curve measured on representative queries.

Release from a measured index frontier

Replay metric migration and deletion with Faiss

The earlier loops expose algorithm mechanics. This CPU replay uses Faiss's maintained API on two authored vectors, with explicit record IDs. It checks result identity, not latency or semantic relevance.^{[5]Reference 5Faiss indexeshttps://github.com/facebookresearch/faiss/wiki/Faiss-indexes[7]Reference 7MetricType and distanceshttps://github.com/facebookresearch/faiss/wiki/MetricType-and-distances}

Predict the winner before running it. Under raw L2, [1, 1] is closer to [1, 0.1] than [10, 0]. Under cosine, [10, 0] points more closely along the query's direction. Reusing an old raw-vector index while normalizing only the query would keep the wrong geometry.

Save the code as vector-index-replay.py and run uv run vector-index-replay.py. Its script metadata pins the CPU packages; it builds separate indexes rather than mutating the original into a different metric.

#!/usr/bin/env -S uv run --script
# /// script
# requires-python = ">=3.12"
# dependencies = ["faiss-cpu==1.15.1", "numpy==2.4.3"]
# ///
import faiss
import numpy as np

faiss.omp_set_num_threads(1)
vectors = np.array([[10.0, 0.0], [1.0, 1.0]], dtype="float32")
ids = np.array([101, 202], dtype="int64")
query = np.array([[1.0, 0.1]], dtype="float32")

raw_l2 = faiss.IndexIDMap2(faiss.IndexFlatL2(2))
raw_l2.add_with_ids(vectors, ids)
_, raw_ids = raw_l2.search(query, 1)

unit_vectors, unit_query = vectors.copy(), query.copy()
faiss.normalize_L2(unit_vectors)
faiss.normalize_L2(unit_query)
cosine = faiss.IndexIDMap2(faiss.IndexFlatIP(2))
cosine.add_with_ids(unit_vectors, ids)
_, cosine_ids = cosine.search(unit_query, 1)
print("Raw L2 winner:", int(raw_ids[0, 0]))
print("Cosine winner after rebuilding:", int(cosine_ids[0, 0]))
assert int(raw_ids[0, 0]) == 202
assert int(cosine_ids[0, 0]) == 101

removed = cosine.remove_ids(np.array([101], dtype="int64"))
_, after_delete = cosine.search(unit_query, 2)
print("Removed records:", removed)
print("Results after delete:", after_delete[0].tolist())
assert removed == 1 and cosine.ntotal == 1
assert after_delete[0].tolist() == [202, -1]
assert raw_l2.ntotal == 2  # The old index still exists independently.

Raw L2 winner: 202
Cosine winner after rebuilding: 101
Removed records: 1
Results after delete: [202, -1]

-1 is Faiss's missing-result sentinel when fewer than k records remain; never resolve it as a real source ID. This deletion works for the flat index wrapped in IndexIDMap2, not every Faiss index type. The old index still contains both records. During a real migration, every serving path and retained replica needs the same deletion and access policy before cutover. The replay doesn't implement replication, tombstone propagation, or authorization. An IVF migration additionally retrains centroids and reassigns lists for the new geometry.

Freeze the embedding model, distance normalization, representative query set, filters, and exact top-$k$ baseline. That fixes what "correct" means while you compare candidates.

Then sweep each candidate's search budget and plot recall against p95 latency and bytes per vector under target concurrency. Report CPU/GPU model, RAM, storage, library version, thread count, batch size, warm/cold state, and query count. Hold build settings fixed within a query-budget sweep. Separate index latency from embedding, network, and reranking time, and measure p99 as well as throughput under load.

Add build time, update/delete visibility, filtered-search completeness, and relevance quality to the scorecard. The executable examples here check arithmetic and small deterministic mechanisms; none measures hundred-million-vector performance. Choose a feasible operating point from your workload's measurements, not from the illustrative p95 values above.