What is vector indexing, and how do vector indexes work?

In this article

1. Before you start
2. Why interviewers ask this
3. Vector indexing from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This topic sits inside how a vector database answers a query.

Why interviewers ask this

A retrieval system with the wrong index is either slow, expensive or quietly wrong, and the failure shows only at scale. A question about indexing tests whether you know that exact search stops being affordable, that every faster index gives up something, and that you can name what.

A weak answer says "the database uses an index to make search fast." A strong answer names the families (flat, inverted file, graph, compressed), says which knob trades recall for speed in each, and says how you would measure the loss. A Staff-level answer adds memory, build time, filtering and what happens when the data changes.

Vector indexing from first principles

Vector index

A vector index is a data structure that stores embeddings in an arrangement, such as clusters, a graph or compressed codes, that lets a vector database find the vectors closest to a query without comparing it with every stored vector.

Approximate nearest-neighbor search

Approximate nearest-neighbor (ANN) search is a nearest-neighbor search that may miss a few of the true closest vectors in exchange for visiting only a small part of the data, so it runs much faster than an exact scan.

Recall at k

Recall at k is the share of the true k closest vectors, found by an exact search, that an approximate search also returns; one means nothing was missed, and it is the standard way to measure what an index gives up.

In plain words

Think of a huge warehouse where every item has coordinates. To find the items nearest a spot, you could walk past every shelf. That always works and is always slow. An index is a floor plan that tells you which aisles to visit. The analogy breaks in one place: a floor plan never lies, while a vector index sometimes sends you past an aisle that held a closer item.

In one precise sentence, vector indexing builds a structure over the stored vectors once, so each query can skip most of them.

The vectors usually come from an encoder such as a transformer; the index does not create them, it only organizes them. The four steps below go from the slowest, exact baseline to the main ways of skipping work.

Step 1: A flat index compares the query with every vector

A flat index stores the vectors as they are and scans all of them for each query, so its answer is exact. It is the baseline against which every other index is judged. Input: one query vector. Output: the true nearest vectors.

The cost is the number of vectors N times their dimension d. For 10,000,000 vectors of 128 numbers each, one query takes 1,280,000,000 multiply-adds, and the raw 32-bit vectors fill 5.12 GB of memory (illustrative sizes).¹ That is fine for thousands of vectors and painful for hundreds of millions. You now know the cost every other index tries to cut, by looking at fewer vectors, at smaller vectors, or at both.

Step 2: An inverted file index searches only the nearest cells

An inverted file index (IVF) is a vector index that splits the vectors into cells with a clustering method such as k-means and, at query time, scans only the few cells whose centers lie nearest the query. Input: a query. Output: the best vectors found inside the probed cells.

The setting that matters is the number of cells probed per query, often called nprobe. With nlist of 4,096 cells and 8 probed (illustrative), a balanced index scans about 19,531 of the 10,000,000 vectors, roughly 423 times fewer multiply-adds than a flat scan once the cell-center comparisons are counted.¹ The catch: if the true neighbor sits just across a cell border in an unprobed cell, it is missed. Probing more cells lowers that risk and raises the cost. The worked example measures the trade.

Step 3: Product quantization compresses the vectors

Product quantization (PQ) is a compression method that cuts each vector into pieces and replaces every piece by the id of its nearest entry in that piece's own small learned codebook, so a vector becomes a few bytes. Jégou, Douze and Schmid (2011) describe it for nearest neighbor search. Input: a full vector. Output: a short code.

With 16 pieces and one byte per piece (illustrative; one byte can name 256 entries, so each piece has its own codebook of 256 centroids), a 128-number 32-bit vector shrinks from 512 bytes to 16, which is 32 times smaller, and 10,000,000 vectors fit in 160 MB.¹ Distances computed on codes are approximate, so PQ adds error on top of any other index, and it is usually combined with IVF. The graphics processing unit (GPU) paper behind the open-source Faiss library (Johnson, Douze and Jégou, 2017) combines these ideas.

Step 4: HNSW walks a layered graph from the top down

A hierarchical navigable small world (HNSW) index links each vector to nearby vectors in a graph and stacks several graphs in layers. Malkov and Yashunin describe it as "a multi-layer structure consisting from hierarchical set of proximity graphs" over nested subsets of the stored elements.

Each element's top layer is chosen at random with an exponentially decaying probability, so upper layers hold few elements. A query enters at the top layer, hops to the closest vector it can see, drops a layer and repeats. The authors report that starting at the upper layer gives logarithmic complexity scaling, and they compare the structure to a skip list. If each layer kept 1 in 16 of the layer below (illustrative, matching the link count M described below, because the paper's level normalisation of 1/ln(M) shrinks each layer by about a factor of M), 10,000,000 vectors would need 6 layers, with 10 at the top.¹ HNSW needs no separate clustering step, but its links cost extra memory.

Three settings, named in the full paper, control it. M is the number of links kept per element, which sets the graph's memory and recall. efConstruction is the size of the candidate list used while building the graph. efSearch, written ef in the paper, is the candidate-list size used at query time; raising it raises recall and latency, just as raising nprobe does. Input: a query vector. Output: the closest vectors found in the bottom layer.

1 · Flat scan2 · Cells3 · Compression4 · GraphReplay

Step-by-step description

1. Compare with every vector: exact but slow.
2. Probe only the nearest cells.
3. Shrink each vector to a short code.
4. Walk a layered graph from the top.

• A flat index compares the query with every vector and is exact.
• An inverted file index probes only the nearest cells.
• Product quantization compresses each vector into a short code.
• HNSW walks a layered graph from the top layer down.

Worked example

To see the recall trade, the script builds a toy IVF index: 5,000 random vectors of 16 numbers drawn around 32 cluster centers, clustered into 32 cells, then 200 queries compared with an exact flat search for the top 10.¹ All inputs are illustrative and the data is cleanly clustered, so real recall is usually lower than here.

Probing 1 cell scans on average 213 vectors, 4.26% of the index, and finds 0.9555 of the true top 10. Probing 2 cells scans 389 vectors, 7.78%, for a recall of 0.997. Probing 4 cells scans 777 vectors, 15.54%, and recall reaches 1.0, and probing 8 scans 31.23% for the same recall.¹ Past the point where recall is 1.0, extra probes only cost time.

Text description of the diagram

• Probing 1 cell gives recall 0.9555 at 4.26% of the index.
• Probing 4 cells gives recall 1.0 at 15.54% of the index.
• Probing 8 cells scans 31.23% of the index for the same recall.

Trade-offs and edge cases

Every index trades some of recall, speed, memory and build effort. Flat search is exact and needs no build. IVF needs a clustering step and loses recall at cell borders. HNSW searches fast but stores graph links beside the vectors, and PQ saves memory but adds approximation error.

Text description of the diagram

• Flat search is exact and compares the query with every vector.
• An inverted file index searches only the nearest cells.
• HNSW walks a layered graph from the top layer down.

Edge cases follow. An index built on today's data can drift: IVF cells are fitted to the vectors seen at build time, so heavy new data of a different kind may need a rebuild. Metadata filtering is awkward, because a filter applied after the search can leave fewer than k results, and a filter applied during the search changes which neighbors are reachable.

Keyword matches are not found by vectors alone, which is why systems add hybrid search, and the top results are often reordered by a cross-encoder reranker. The vectors themselves may come from a two-tower model, whose index must be rebuilt when the encoder is retrained. Graph indexes also moved onto disk: DiskANN (Subramanya et al., 2019) keeps a graph index on solid-state disk so very large sets need far less memory. Recall depends on the data, so measure it on your own queries against a flat baseline.

How to answer it in an interview

The spoken structure: define the index, name the families in order of how they skip work, state that they are approximate, then say how you would measure and tune.

Common mistakes

• "A vector index returns the exact nearest neighbors." (wrong) Except for flat search, indexes are approximate. (right) "Approximate indexes trade recall for speed, and I measure recall against a flat baseline."
• "Indexing and embedding are the same step." (wrong) Embedding creates the vectors; indexing organizes them for search. (right) "The encoder makes the vectors; the index makes them searchable."
• "HNSW needs a clustering stage first." (wrong) It is a graph structure and needs no separate search structure. (right) "HNSW is a layered graph; IVF is the one that clusters."
• "More probes is always better." (wrong) Past full recall it only adds latency. (right) "I raise the probe count until recall on my queries plateaus, then stop."

Follow-up questions

What is vector indexing and how is it used in vector databases?

Vector indexing builds a structure over stored embeddings so the database answers nearest-neighbor queries without a full scan. The vector database overview shows where the index sits between the stored vectors and the query.

What are vector database indexing algorithms?

The common families are flat (exact scan), inverted file (cells), graph-based such as HNSW, and compression such as product quantization, often combined. Locality-sensitive hashing (LSH) is the classic hashing family: it hashes vectors so that near ones tend to land in the same bucket (Indyk and Motwani, 1998). Each skips work differently, as the comparison table above shows.

What happens if you double the number of cells probed?

The search scans about twice as many vectors and recall rises with diminishing returns. In the toy run, going from 1 to 2 probes moved the vectors scanned from 213 to 389 and recall from 0.9555 to 0.997.¹

Does building an index change the search results?

For approximate indexes, yes: the index can miss a true neighbor that a flat scan would return. Only flat search is exact, so the flat result is the reference for measuring recall.

Is embedding the same thing as indexing?

No. Embedding turns an item into a vector; indexing arranges many vectors for fast search. See what an embedding is for the first step.

How do filters and keyword search fit with a vector index?

A filter can shrink the candidate set after or during the search, and either choice can lower recall or return fewer than k results. Keyword matching is a separate signal that hybrid search merges with the vector results.

Sources

1. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320) — arXiv (Malkov and Yashunin), 30 Mar 2016
2. Billion-scale similarity search with GPUs (arXiv 1702.08734) — arXiv (Johnson, Douze, Jegou), 28 Feb 2017
3. Product quantization for nearest neighbor search (DOI 10.1109/TPAMI.2010.57) — IEEE TPAMI (Jegou, Douze, Schmid), 1 Jan 2011
4. Approximate nearest neighbors: towards removing the curse of dimensionality — ACM STOC (Indyk and Motwani), 1 Jan 1998
5. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node — NeurIPS proceedings (Subramanya et al.), 1 Dec 2019