Vector Indexing in FAISS

Similarity search asks a simple question: given a query vector, which stored vectors are closest to it? Many systems that work with embeddings need to answer this question again and again, often over very large collections. The answer has to be fast as well as useful, and that pressure is what makes vector indexing necessary.

The techniques covered in this article are ways of organizing stored vectors so that a search does not have to examine everything. Each one takes a different route around the cost of comparison. Before looking at those routes, it helps to understand the baseline they are trying to beat.

The obvious way to answer a similarity query is to measure the distance from the query to every stored vector and keep the best matches. This approach is accurate, because no candidate is skipped. Its weakness is cost: as the number of stored vectors grows, the number of comparisons grows with it, and the search becomes slow.

Each of the three techniques attacks that cost in a different place. Some decide which vectors are worth comparing at all. Some decide how the search moves through the stored data. Others decide how expensive each individual comparison is. Keeping these three questions separate will make the rest of the article easier to follow.

Locality-sensitive hashing, usually written LSH, is an algorithm for similarity search that works with more than just vectors. Its central move is to hash similar vectors into the same buckets. A bucket is simply a group of stored items that share one hash result. Because similar vectors land in the same bucket, the index already holds a rough grouping of likely neighbors before any query arrives.

When a query arrives, the search does not need to look at every vector in the collection. It hashes the query, finds the bucket or buckets the query lands in, and examines only the vectors stored there. The diagram below shows a small collection of nine stored vectors spread across three buckets. The query lands in Bucket A, so only the three vectors in that bucket are candidates.

The diagram is illustrative, with invented vector names and bucket contents, but the mechanism is the one the source describes: the query is compared only against the bucket it lands in, not against the full collection of nine.

HNSW, which stands for Hierarchical Navigable Small World, takes a different approach from LSH. Instead of grouping vectors into buckets, it constructs a multi-layer graph in which each node represents a vector and each edge connects two similar vectors. The graph is built ahead of time, and the search runs over it.

A nearest-neighbor search in HNSW works by traversing graph edges. The search moves from vector to vector along links that connect similar items, so each step takes it to a nearby node. The diagram shows the multi-layer structure as levels, with the search descending from a top layer toward the bottom layer, where the vectors are linked by edges.

The layers are what make the structure hierarchical. The source pack describes the graph and the edge traversal, but it does not give a full layer-by-layer procedure, so this article limits its claims to those two ideas: vectors are nodes, edges link similar vectors, and the search moves along edges.

Product quantization, often abbreviated PQ, works on the vectors themselves. It reduces each vector into a much simpler, lower-dimensional representation by decomposing it into multiple subvectors, which are smaller pieces of the original vector. The full vector is split into parts, and the parts are used to build a compact form.

The diagram shows one vector split into three illustrative subvectors, feeding into a lower-dimensional representation. The point of the decomposition is what happens next: distances are computed using these lower-dimensional representations rather than the full vectors. The source notes that these representations are much faster to work with.

This is why product quantization is about the cost of each comparison. The number of stored vectors may stay the same, but every distance calculation touches a smaller, more compact form. The source pack does not quantify any accuracy loss from this step, so it should not be assumed to be zero or any particular value.

The three techniques answer the same question from different angles. LSH controls which vectors get compared by hashing them into buckets. HNSW controls how the search moves by following edges in a graph. Product quantization controls how much work each comparison costs by shrinking the vectors that are compared.