Vector search and FAISS, explained for evaluators

Before a language system can answer from a large collection of manuals or captured documents, it has to find the right passages, and vector search is the step that does it. Vector search finds the stored vectors that lie closest to a query vector, and Faiss is a library that implements it. The project describes Faiss as a library for efficient similarity search and clustering of dense vectors, written in C++ with Python wrappers, with some of its most useful algorithms available on the graphics processing unit (GPU). An evaluator needs to know whether an index is exact or approximate, because a vendor's recall figure means little without that.

Embeddings and nearest neighbors

The Faiss paper defines embeddings as vector representations, typically produced by a neural network, so that distance between vectors reflects similarity between the original items. Passages and questions can each be turned into vectors, and the passages nearest a question's vector are the ones retrieved.

Nearest-neighbor search returns the database vector closest to a query vector, typically by Euclidean distance. k-nearest-neighbor search returns the k closest, sorted by distance.

Two details affect how results are read. First, Faiss reports squared Euclidean (L2) distance and does not take the square root, as the project wiki states. Second, cosine similarity is obtained by normalizing both the query and database vectors beforehand, which reduces the problem to maximum inner product search.

Exact search is the reference, and it slows with scale

Brute-force search compares the query with every vector in the database. In Faiss this is the flat index. The wiki's guidelines for choosing an index say that only the flat indexes, IndexFlatL2 and IndexFlatIP, can guarantee exact results. The same page recommends a flat index when only about 1,000 to 10,000 searches are planned, because the time to build a faster index would not be recovered.

The cost of exactness is scale. The Faiss paper states that for large datasets brute-force search becomes too slow, which motivates the approximate indexes.

Approximate search trades accuracy for speed

An approximate index gives up the guarantee. The paper frames the design problem as three active constraints: speed, memory usage, and accuracy.

One common design is the inverted file index, abbreviated IVF. The wiki's page on faster search describes it as dividing the space into Voronoi cells, each database vector falling in one cell. At query time only the vectors in the query's cell and a few neighboring cells are compared. Two parameters control this: nlist, the number of cells, and nprobe, the number of cells searched per query.

The page's worked example shows the dial. With nprobe at 1, the results are similar to brute-force search but not identical. Raising nprobe to 10 made the example's results match. Setting nprobe equal to nlist gives the same result as brute force, only slower, and search time rises roughly linearly with the number of cells probed. The page cautions that the perfect match in its example is an artifact of the data distribution, so it does not predict how another dataset will behave.

An IVF index also needs a training stage, because the cells come from clustering. Training can use any collection of vectors, and the example trains on the database vectors themselves. The training sample therefore shapes the cell layout, which is part of the index being evaluated.

The guidelines give sizing advice. For datasets below one million vectors, the number of cells K should fall between 4 and 16 times the square root of the dataset size N, and clustering needs between 30 times K and 256 times K training vectors. The page also notes that all Faiss indexes are stored in random-access memory (RAM), and it lists other index families, including compressed ones, for cases where memory is the main concern. On a machine with no network, that memory is fixed by the hardware at hand.

What recall measures and what it leaves out

The Faiss paper measures accuracy against exact results. The main metric is nn-recall@k: the fraction of the n ground-truth nearest neighbors that appear among the first k search results, with n no larger than k. The paper notes that the most common cases are k equal to 1, or n equal to k, which it also calls the intersection measure.

A recall figure is only interpretable with its setting. The same index gives different recall at different nprobe values and on different datasets. A recall figure reported without the index type, its parameters, the dataset, and the value of k leaves the reader unable to reproduce it.

Recall also has a boundary. Because it is defined against the exact neighbors, it measures how closely an index matches brute-force search. It does not measure whether those nearest vectors answer the question. A flat index with perfect recall still returns the wrong passage if the embeddings place the wrong passage nearest. Evaluating a retrieval system therefore takes two separate checks: index recall against exact search, and retrieval quality against passages a person has marked as relevant.

What to ask

• Is the index flat or approximate, and if approximate, which type and which parameters, such as nlist and nprobe?
• What recall against exact search was measured, at what value of k, and on which dataset?
• What vectors was the index trained on?
• Was retrieval quality measured separately, against passages a person marked as relevant?
• How much RAM does the index need on the target hardware?

Azcuna's BABEL reads, translates, and searches foreign-language documents entirely on-device, with no cloud and no connection, and keeps every claim tied to the passage it came from. The long read on air-gapped RAG goes further.

Sources

1. 1The Faiss library · arXiv (Douze et al.)
2. 2Guidelines to choose an index · Faiss project wiki (facebookresearch/faiss)
3. 3Faster search · Faiss project wiki (facebookresearch/faiss)
4. 4MetricType and distances · Faiss project wiki (facebookresearch/faiss)
5. 5Faiss documentation · Faiss project