Vector search: embeddings and approximate nearest neighbors (HNSW, Faiss)

Why it was needed: the limits of word-matching search and slow sentence comparison

For a long time, the standard for document search was keyword methods such as TF-IDF and BM25. They count how many of the same words a query and a document share, and use an inverted index (a table mapping words to lists of documents) to find matches quickly. They are fast and robust but miss matches when the words differ. The DPR paper paper gives an example. The answer to the question "Who is the bad guy in lord of the rings?" is in a sentence containing "villain Sauron," but "bad guy" and "villain" share no words, so keyword search has trouble finding it.

Why not use a model like BERT, which understands meaning well? The problem is cost. To measure the similarity of two sentences with BERT, both sentences must be fed into the model together. According to the Sentence-BERT paper paper, finding the most similar pair among 10,000 sentences takes about 50 million inference computations, or about 65 hours. That cannot be used for tasks like search, which must answer immediately each time a query comes in.

There is also the problem of scale. The Wikipedia passages used in DPR's experiments alone numbered 21 million, and the whole web holds billions. What was needed was a way to compare by meaning without comparing each query against every document one by one. The solutions to these two problems are, respectively, "embeddings" and "approximate nearest neighbor search."

Core idea: meaning as coordinates, search as "finding nearby points"

As an analogy, it is like plotting every passage in a library as a point on a giant map. Coordinates are chosen so that passages with similar meanings sit close together and different ones sit far apart. These coordinates are embeddings. In practice they are not two-dimensional but lists of numbers with hundreds of dimensions. When a query comes in, it is plotted as a point on the same map, and the few nearest points around it are retrieved; those are the search results.

Two ideas overlap here. First, document coordinates are computed once in advance. When a query arrives, only the query needs to go through the model, so the cost of comparing every pair with BERT disappears. Second, the system does not measure the distance to every point to find the exact "nearest points." It accepts "approximate" search, which is mostly right but may occasionally miss one or two, and gains a large boost in speed in return. This is approximate nearest neighbor (ANN) search.

So the quality of vector search has two layers: whether the coordinates were placed well (the quality of the embedding model), and whether nearby points are retrieved well (the recall and speed of the index). Good search requires both; one alone is not enough.

How it works: build an index, then search with a query

Start with the preparation stage. ① Split documents into search units (chunking). DPR split documents into passages of equal length and reported that fixed lengths worked better than natural paragraphs for both retrieval and final answer accuracy. ② Feed each chunk into an embedding model to turn it into a vector. ③ Put the vectors into an index structure that allows fast lookup. This stage can take time, but it can be done in advance.

The query stage works like this. ④ Turn the query into a vector in the same embedding space. DPR used a "dual encoder" with separate encoders for questions and passages, while SBERT used a "siamese" structure in which both share the same network. Either way, the model is trained so the two vectors can be compared by dot product or cosine similarity. ⑤ Find the top k vectors in the index closest to the query vector. ⑥ If needed, re-sort them with a reranker or pass them to an LLM to produce an answer (RAG).

Indexing methods fall into two main families. HNSW paper, the leading graph-based method, stacks graphs in multiple layers, with vectors as points and close-neighbor relationships as edges. The highest layer each vector enters is set by a random draw whose probability drops sharply at higher layers, so upper layers have sparse points with long links and lower layers are dense. Search starts at the top layer and moves toward closer points while descending one layer at a time, like taking a highway to a nearby city and then moving down to local roads and alleys. The other family partitions the vector space into regions (IVF, inverted file index) and searches only a few regions close to the query, or compresses vectors into short codes, as in product quantization (PQ), to reduce memory and computation. The GPU similarity search paper paper covered designs for running exactly this compressed-domain search, as well as exhaustive comparison, quickly on GPUs.

The measure of performance here is recall: how many of the true top k results, as found by exact computation, the index retrieved. Widening the search range raises recall and lowers speed. Choosing this balance point is the key tuning task in real operations.

How it developed: what each of five starting-point papers did new

Start with indexing. HNSW (2016) completed search with the graph alone, without the separate "coarse search" structure that earlier proximity graph methods used. By separating the scale of link distances across layers and starting from the top layer, it made search cost grow logarithmically with data size. When choosing neighbors, it also selected them with a heuristic rather than simply taking the closest points, which greatly improved performance in the high-recall range and on clustered data. It also noted that its structure resembles a skip list, making distributed implementation easy.

The GPU similarity search paper (2017) redesigned the bottlenecks that kept GPU parallelism from being used well, especially "selecting the smallest k" (k-selection). With a k-selection running at up to 55% of theoretical peak performance, it implemented nearest neighbor search 8.5 times faster than the previous GPU state of the art, and applied it to exhaustive, approximate and product-quantization compressed search alike. Using four Maxwell Titan X GPUs, it built a graph connecting 1 billion vectors in under 12 hours. The implementation was released as open source. Faiss, in this article's title, is commonly used as the name for this line of open similarity search library.

On the embedding side, SBERT (2019) modified BERT into siamese and triplet structures to produce sentence vectors that can be compared directly by cosine similarity. It cut the time to compare 10,000 sentences from about 65 hours to about 5 seconds while maintaining accuracy. DPR (2020) applied this to retrieval for open-domain question answering. It was previously believed that good dense vectors required costly additional pre-training, but DPR trained two encoders using only question-passage pairs and, with a simple objective that compares all question-passage pairs within a batch against each other, clearly outperformed BM25 (Top-5 accuracy of 65.2% vs. 42.9%). It also confirmed that higher retrieval accuracy leads to higher final answer accuracy.

Finally, MTEB (2022) tackled evaluation. At a time when embeddings were evaluated on only a few datasets, it compared 33 models across 8 tasks, 58 datasets and 112 languages. Its conclusion was that "no embedding method wins on every task." In other words, a model that is strong at judging similarity is not guaranteed to be strong at clustering or reranking as well.

Where it is heading: beyond memory, search with conditions, and model swapping

Recent research is moving beyond "finding things fast" to the operational problems that come up in real services. The first is scale that does not fit in memory. RaBitQ-SSD paper addresses searching vectors stored on SSD when there are more vectors than DRAM can hold. It points out that graph traversal discovers candidates one step at a time, which makes SSD reads hard to plan in advance, and that IVF reads whole partition lists at once, which wastes reads. It keeps only the leading part of each binary code in memory and filters candidates using distance estimates with error bounds, so that only the candidates that are actually needed are read from SSD. At 90% recall, it achieved up to 1.74x higher throughput than graph-based methods and up to 3.8x fewer SSD page reads, and it built and searched an index of 10 billion vectors with a single machine and SSD.

The second is search with conditions attached. In practice, filters are applied together with the query, such as "among documents from 2025 onward" or "among this department's materials." VADER paper points out that the same query can vary widely in difficulty depending on how many vectors a filter lets through (selectivity) and how the filter is entangled with the vector space (correlation), so people have to tune parameters by hand. It proposes "declarative recall": the user only sets a target recall, and a predictor estimates recall during search and stops once the target is reached. It reports being up to 53% faster than the best baseline, with 28% better result quality.

The third is the cost of switching embedding models. DGM paper takes issue with the fact that the edges of a graph index are determined by the distances at build time, which ties the index to a specific embedding model. Re-encoding with a new model means rebuilding the graph from scratch. However, because different models still describe the same items, it observes that many of the true neighbors under the new model can be reached within a few steps on the old graph (residual reachability), and it proposes a migration method that uses this to build the new index faster. All three studies take as a given the "fast approximate search" opened up by HNSW and GPU search, and address real-world constraints of scale, conditions and change.

Limitations and open issues

First, an approximation is an approximation. ANN sometimes misses the truly nearest documents. In RAG, if the passage containing the answer drops out of the top k, the LLM ends up answering without grounding, which can lead to hallucination. How to set a recall target and how to verify it is a constant challenge. This tuning is difficult, which is why research like VADER appears.

Second, dense retrieval does not replace keyword search. The DPR paper itself states that dense representations are "complementary by design" to sparse representations. Dense retrieval is good at finding sentences with similar meaning, but for queries that must match the text exactly, such as product codes, people's names or exact numbers, BM25 can be stronger. This is why hybrid search, which combines the two, is widely used in practice.

Third, there is no single right choice of embedding. MTEB reported that no method dominates across all tasks. There is no guarantee that the top model on a public leaderboard will also be the best on your company's documents. Also, as DGM shows, an index is tied to its embedding model, so switching models incurs the cost of re-encoding and re-indexing everything. Choosing a model is not a one-time decision; it is tied to long-term operating costs.

Fourth, there is the balance between memory and cost. Graph indexes are fast but require the original vectors and edges to be kept in memory, and compression (quantization) reduces memory at the cost of some accuracy in distance calculations. As scale grows, the storage location itself has to be redesigned, as with SSD use (RaBitQ-SSD).

Further study

If you are not a specialist, we recommend starting with the SBERT paper abstract. The figure of 65 hours versus 5 seconds makes clear "why we build a vector for each sentence in advance." Next, reading the introduction of DPR paper will help you understand, with examples, the difference between keyword search and semantic search and how retrieval affects overall RAG performance.

For developers curious about index structures, HNSW paper is the starting point. Once you see why the layered structure and the neighbor-selection heuristic are needed, you will get a sense of what the settings in a vector DB actually tune. For large-scale and compressed search and GPU use, continue with the GPU similarity search paper paper.

If you are choosing an embedding model, use MTEB paper to frame how to evaluate. If you have concerns at the operations stage, pick whichever fits your situation among RaBitQ-SSD paper(large scale / SSD), VADER paper(filtered search) and DGM paper(model replacement), in that order.