Skip to main content

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: Similarity, Relevance, and Decisions explains where vectors come from; Retrieval Pipelines: Chunking, Recall, Reranking, and Citations 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 one relation: the squared distance between two unit vectors equals 2 minus twice their inner product.

∥q−x∥2=2−2(q⊤x).\|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:

VectorRaw inner productCosine similarityRaw squared L2Squared L2 after normalization
a = (1, 1)10.70710.586
b = (3, 4)30.600200.800

The table confirms that relation: after normalization, a's inner product with q is its cosine, 0.707, and 2 − 2 × 0.707 = 0.586, exactly the squared L2 after normalization; for b, 2 − 2 × 0.600 = 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.

Where an individual project stores vectors​

For thousands to a few hundred thousand passages, any of three options is enough; they differ in whether the vectors live with the rest of your data. The simplest uses no database: keep the vectors in an in-memory array or a Faiss IndexFlat and compare them one by one, as the baseline in retrieval pipelines does. To keep vectors, text and metadata in one local file, use the SQLite extension sqlite-vec: pip install sqlite-vec, then query with SQL; Basic Memory uses it on SQLite. sqlite-vec is still pre-1.0, so expect breaking changes. If your data already lives in Postgres, use pgvector: vectors sit in the same database as everything else, with JOINs and transactions. pgvector searches exactly by default; adding an HNSW or IVFFlat index makes the search approximate, and recall can drop with it.

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.

Think of a long trip: fly to the city nearest your destination, take a train to the district, then walk to the street number. Upper layers have few nodes and long links, so one step crosses much of the graph; lower layers are denser and the steps get shorter.

Walk through it with six invented one-dimensional points: A = 0, B = 1, C = 3, D = 6, E = 8, F = 10. The query is q = 4 and we want two neighbors; the squared distances to the query are 16, 9, 1, 4, 16, and 36, so the true two nearest neighbors are C and D. The IVF example in the next section uses the same six points. Suppose the graph is already built with these nodes and links:

LayerNodesLinks
2A, FA–F
1A, C, FA–C, C–F
0A, B, C, D, E, FA–B, B–C, C–E, D–E, D–F, E–F
  1. Layer 2 starts at the entry point F (36). Neighbor A (16) is closer, so move to A; A has no closer neighbor, so stop.
  2. Layer 1 starts at A. Neighbor C (1) is closer, so move to C; C's neighbors A and F are both farther, so stop.
  3. Layer 0 starts at C with efSearch = 2, so the result set holds at most two nodes. C's neighbor B (9) joins the results; E (16) is farther than B, the farthest result, and is dropped. B's neighbor A (16) is also farther. No candidate is left to expand, so the search ends and returns C, B.

D's squared distance is only 4, closer than B, but D links only to E and F, and E was dropped at once, so D is never visited. Raise efSearch to 3 and E stays in the result set and gets expanded, D is found, and the search returns C, D; the cost is that layer 0 computes distances for 6 nodes instead of 4.

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 the same six invented one-dimensional vectors from the previous section, 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.

IDCoordinateListSquared distance to query
A0016
B109
C301
D614
E8116
F10136

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.

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

# Input checks: centers must be non-empty and k an integer with
# 1 <= k <= len(points); otherwise the program raises ValueError.
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. Counting the two distance computations for center selection, this small example uses 5 and 8 query distance computations respectively, versus 6 for a full scan: six points are too few for partitioning to save work, and the point here is how D gets missed.

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:

IndexConstruction workStorage and query costAdding vectors
FlatNo training; store vectorsfloat32 vectors use 4d bytes each; queries scan every vectorAppend vectors
HNSWFlatSearch, connect, and prune for each insertion; larger construction exploration budgets add workFull vectors plus connections across layers; larger M stores more connectionsSearch the existing graph and connect a new node
IVFFlatTrain centroids, then assign vectors to listsVectors and IDs use 4d + 8 bytes each, plus centroids and list overhead; queries select centers, then scan listsAssign 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 cause the most trouble. Faiss HNSW cannot remove a vector directly; it relies on invalidation markers, result filtering and periodic rebuilds. Filtering may leave fewer than k results, and invalidation markers do not reclaim storage. Do not bind document identity to a sequential position that can move; the Faiss special-operations documentation lists how IDs change on deletion for each index type. 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:

ANN recall@k⁡=∣A∩E∣k.\operatorname{ANN\ recall@k} = \frac{|A \cap E|}{k}.

This is the intersection-style R-recall@R in the Faiss IntersectionCriterion implementation. In the IVF example, probing one list returns {C, B} while the exact neighbors are {C, D}; only C is shared, so recall@2 = 1 / 2 = 0.5.

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.

The exact baseline and the ANN run must use the same k, the same filters and the same tie-breaking rule. When fewer than k results come back, the -1 padding Faiss adds does not count as a neighbor; and this recall is not the 1-recall@R in the tuning documentation, which checks only the first exact neighbor.

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:

JudgmentReferenceFailure it can locate
ANN recallExact neighbors for the same vectors and metricThe index misses neighbors
Retrieval relevance and evidence recallLabeled relevant passages and required factsEmbeddings, chunking, or ranking miss usable evidence
Answer correctness and completenessApplicable facts and necessary conditionsGeneration 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. Evaluating Retrieval and Generation: From Evidence to Correct Answers covers the latter two evaluations; reranking can only reorder passages already in the candidate pool.

When using semantic-search tools such as zvec-grep: Search Code and Documents by Meaning, 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.

Explore connectionsOpen network