Vector Indexes: Exact Search, HNSW, and IVF

Vector retrieval represents questions and documents as vectors, then finds the documents closest to a question. As the corpus grows, comparing every vector on every query becomes more expensive. Approximate nearest neighbor search (ANN) reduces the number of comparisons, at the cost of possibly missing vectors that belong among the closest results.

Embeddings, rerankers, and classifiers explains where vectors come from; the retrieval pipeline explains how candidates become evidence. The index sits between them: it determines which vectors a search visits. To decide whether an index is worthwhile, first fix what “close” means, then measure both its savings and its omissions against exact search.

Fix the metric and normalization first

Common choices are Euclidean distance (L2), inner product, and cosine similarity. The Faiss metric documentation states that L2 returns squared distance, with smaller values indicating closer vectors. For inner product, larger is better, but an unnormalized inner product is not cosine similarity.

For nonzero vectors, cosine similarity compares direction. Dividing both query and database vectors by their respective lengths makes their inner product equal to cosine similarity. Unit vectors also satisfy:

$$\|q-x\|^2 = 2 - 2(q^\top x).$$

Thus, for unit vectors, ascending L2 and descending inner product produce equivalent rankings. A zero vector cannot be normalized this way and needs separate handling before indexing.

A two-dimensional example shows how the metric changes the result. Let the query be q = (1, 0) and compare these vectors; decimals are rounded to three places:

Vector	Raw inner product	Cosine similarity	Raw squared L2	Squared L2 after normalization
a = (1, 1)	1	0.707	1	0.586
b = (3, 4)	3	0.600	20	0.800

Raw inner product ranks b first; cosine and, in this example, raw L2 rank a first. Choose the metric according to the embedding model’s retrieval conventions. Normalization removes length information, so it is not harmless preprocessing for every model. Otherwise, even an index that finds every neighbor correctly may be answering a different definition of “close.”

Exact search provides the baseline

The Faiss index documentation lists IndexFlatL2 and IndexFlatIP as exhaustive searches: store uncompressed vectors, compare each one, and select top-k. Here, “exact” means the true top-k for the given vectors, metric, and numerical precision. It does not establish document relevance.

For N vectors of dimension d, the distance computation in a straightforward full scan grows with N × d; selecting top-k adds work. For example, one million 768-dimensional float32 vectors contain 768,000,000 coordinates. The vectors alone occupy 1,000,000 × 768 × 4 = 3,072,000,000 bytes, or 3.072 GB in decimal units. One query compares those coordinates, and concurrent queries add to the total work.

Batching, vectorization, and accelerated hardware can reduce elapsed time, so size alone does not decide whether ANN is needed. Measure full-scan latency on the intended hardware and query load first. A complex index may not pay off with a small corpus, few queries, or a requirement to retain every nearest neighbor.

HNSW searches a graph with several layers

Section 4 and Algorithms 1, 2, and 5 of the original HNSW paper describe construction and search. HNSW stands for Hierarchical Navigable Small World. Vectors are graph nodes: the bottom layer contains every node, while higher layers are progressively sparser.

On insertion, a new node’s highest layer is sampled from an exponentially decaying distribution. The algorithm searches downward from the existing graph’s top layer. On layers the new node joins, it finds candidates, selects neighbors, and adds connections in both directions; existing nodes with too many connections are pruned. A neighbor-selection heuristic considers distances between candidates to retain connections in different directions, rather than connecting only to one tight group of nearby nodes.

A query begins at the top-layer entry point, greedily moves to closer neighbors, and uses its current position as the entry for the next layer. At the bottom, search maintains a set of good results and expands nearby pending candidates first. It stops when the nearest pending candidate is farther than the farthest node in the retained result set. The final k results come from discovered nodes; an unvisited node may still be closer.

The Faiss HNSW parameter documentation lists three parameters governing different costs: M controls the connection budget, efConstruction the width of the retained candidate set during insertion, and efSearch that width during querying. The query width should accommodate at least k results. These widths are not counts of actual distance computations. More construction effort can improve the graph, and more query exploration usually improves recall, without guaranteeing exact results for every query.

IVF selects partitions before comparing their vectors

IVF, or Inverted File, assigns vectors to nlist inverted lists. The Faiss description of partition search gives a common L2 arrangement: k-means produces centroids, each vector enters its nearest centroid’s list, and a query selects nprobe lists before scanning their vectors. Inner-product indexes select centroids by maximum inner product, so L2 partition boundaries do not apply directly; see the Faiss explanation of inner-product clustering.

A true neighbor in an unselected list never becomes a candidate. The ratio nprobe / nlist is only a rough estimate of the scanned fraction; unequal list sizes prevent treating it as actual work. Increasing nprobe broadens the candidate pool and increases scanning.

IndexIVFFlat still computes distances using uncompressed vectors inside selected lists, so its approximation mainly comes from skipping lists. The Faiss accuracy troubleshooting guide explains that nprobe = nlist scans every list. With exact centroid selection, the same metric and numerical precision, and no additional scan limit, IVFFlat can recover full-scan results, though tied distances may be ordered differently. IndexIVFPQ also compresses vectors with product quantization (PQ), introducing another distance approximation. Raising nprobe alone cannot remove compression error.

A complete example of a missed neighbor across a boundary

Take six invented one-dimensional vectors, query q = 4, and request two neighbors. With supplied centers at 0 and 10, points below 5 enter list 0 and points above 5 enter list 1; a point at 5 enters list 0 because the smaller list number wins ties. The centers are chosen by hand to isolate candidate selection; no k-means training is performed.

ID	Coordinate	List	Squared distance to query
A	0	0	16
B	1	0	9
C	3	0	1
D	6	1	4
E	8	1	16
F	10	1	36

The query’s squared distances to the centers are 16 and 36, so probing one list selects list 0. Exact top-2 is C, D, but the best two in list 0 are C, B. D is closer than B, yet its list was never visited.

This Python 3 program uses only the standard library and executes assignment, full scanning, partition scanning, and recall calculation. Equal distances are ordered by ID, and tied centroid distances by list number; this example has no tie at the top-2 boundary. The program requires nonempty centers and an integer k satisfying 1 <= k <= len(points); otherwise it raises ValueError.

points = {"A": 0, "B": 1, "C": 3, "D": 6, "E": 8, "F": 10}
centers = [0, 10]
query, k = 4, 2

if not centers:
    raise ValueError("centers must not be empty")
if type(k) is not int or not 1 <= k <= len(points):
    raise ValueError("k must be an integer between 1 and len(points)")

def distance2(a, b):
    return (a - b) ** 2

def rank(ids):
    return sorted(ids, key=lambda i: (distance2(query, points[i]), i))

lists = {j: [] for j in range(len(centers))}
for i, x in points.items():
    j = min(lists, key=lambda j: (distance2(x, centers[j]), j))
    lists[j].append(i)

exact = rank(points)[:k]
print("lists:", lists)
print("distances:", [(i, distance2(query, points[i])) for i in rank(points)])
print("exact:", exact)
for nprobe in (1, 2):
    selected = sorted(lists, key=lambda j: (distance2(query, centers[j]), j))[:nprobe]
    candidates = [i for j in selected for i in lists[j]]
    found = rank(candidates)[:k]
    recall = len(set(found) & set(exact)) / k
    print(f"nprobe={nprobe}: lists={selected}, scanned={len(candidates)}, "
          f"found={found}, ANN recall@{k}={recall:.3f}")

Output:

lists: {0: ['A', 'B', 'C'], 1: ['D', 'E', 'F']}
distances: [('C', 1), ('D', 4), ('B', 9), ('A', 16), ('E', 16), ('F', 36)]
exact: ['C', 'D']
nprobe=1: lists=[0], scanned=3, found=['C', 'B'], ANN recall@2=0.500
nprobe=2: lists=[0, 1], scanned=6, found=['C', 'D'], ANN recall@2=1.000

Probing one list reduces scanned database vectors from 6 to 3 and recovers one exact neighbor; probing both recovers two. Center selection requires two more distance computations, so this small example uses 5 and 8 query distance computations respectively, versus 6 for a full scan. It demonstrates how omissions happen, not a speedup factor for a real index.

Building, memory, updates, and deletion

An index moves some query work into construction. The Faiss selection guide distinguishes Flat and HNSW, which require no training, from IVF, which clusters first using a representative vector sample. The comparison below uses uncompressed variants and the storage components in the Faiss index table:

Index	Construction work	Storage and query cost	Adding vectors
Flat	No training; store vectors	float32 vectors use 4d bytes each; queries scan every vector	Append vectors
HNSWFlat	Search, connect, and prune for each insertion; larger construction exploration budgets add work	Full vectors plus connections across layers; larger M stores more connections	Search the existing graph and connect a new node
IVFFlat	Train centroids, then assign vectors to lists	Vectors and IDs use 4d + 8 bytes each, plus centroids and list overhead; queries select centers, then scan lists	Assign to lists of existing centroids

These components are not total process memory: document text, metadata, allocation overhead, and query workspace add to the budget. HNSW and IVF can also be combined; IVF can use HNSW to search centroids.

Deletion and replacement depend on the implementation. The Faiss special-operations documentation explains that removing a Flat entry shifts subsequent sequential IDs, whereas IVF stores explicit IDs and preserves other IDs on deletion. ID-based access and updates in IVF involve DirectMap; Array does not support removal, while Hashtable with IDSelectorArray can avoid scanning the entire index during removal. Do not bind document identity directly to a sequential position that can move.

Faiss HNSW does not support direct vector removal. If an application uses invalidation markers, result filtering, and periodic rebuilding, design them as additional maintenance mechanisms. Filtering may leave fewer than k results, and invalidation markers do not reclaim vector or graph storage. After text changes, invalidate its old vector and put the new one into a searchable index. When changing embedding models or normalization conventions, migrate database and queries together. After incremental additions, measure recall and list distributions again to decide whether rebuilding is needed. To retrain IVF centroids, train a new index and reassign all active vectors; Faiss does not support directly retraining a populated index.

Measure ANN recall against exact neighbors

For one query, let E be the set of exact top-k IDs and A the set of top-k IDs returned by ANN. Define:

$$\operatorname{ANN\ recall@k} = \frac{|A \cap E|}{k}.$$

This is the intersection-style R-recall@R in the Faiss IntersectionCriterion implementation. It differs from 1-recall@R, defined in the same file, which checks whether the first exact neighbor appears among R results. The tuning documentation lists both criteria. Here k must be a positive integer, with at least k eligible vectors. A contains only actual neighbor IDs; padding with -1 when results are missing does not count as a neighbor. With tied distances, use the same deterministic ordering or agree beforehand on a scoring rule that accepts ties.

A practical measurement sequence is:

1. Freeze the corpus snapshot, embeddings, normalization, metric, k, and filters. Compute the exact baseline over the same eligible corpus.
2. Compute exact top-k for queries representative of actual use, then run ANN. Calculate intersection recall per query, report the mean, and inspect low-recall queries.
3. Keep the index fixed while varying HNSW efSearch or IVF nprobe. Record recall, latency distributions, throughput, and memory, keeping hardware, batch size, concurrency, and cache conditions fixed.
4. If a larger query budget still misses the target, inspect graph construction, centroid training, filtering, and vector compression. Confirm tuned performance on an independent query set. Include construction time, peak memory, and update cost in the choice.

Rather than automatically maximizing the search budget, choose a setting that reaches the required recall within the latency and resource budget. Recall of 1.0 on one query does not establish exact search across the corpus.

Neighbor recall, evidence relevance, and answer correctness

These judgments need different references:

Judgment	Reference	Failure it can locate
ANN recall	Exact neighbors for the same vectors and metric	The index misses neighbors
Retrieval relevance and evidence recall	Labeled relevant passages and required facts	Embeddings, chunking, or ranking miss usable evidence
Answer correctness and completeness	Applicable facts and necessary conditions	Generation uses evidence incorrectly

Even with ANN recall of 1.0, exact neighbors may be obsolete instructions that merely share the topic. Conversely, another passage may supply enough evidence despite a missed vector neighbor. Retrieval and generation evaluation covers the latter two evaluations; reranking can only reorder passages already in the candidate pool.

When using semantic-search tools such as zvec-grep, this distinction helps separate “the index missed vector neighbors” from “the vector neighbors did not answer the question.” Consult the tool’s own implementation for its index and exposed parameters, and open the returned source files to verify their content.

My reading · Opened notes are remembered in this browser.