Term-Based Retrieval with BM25

Imagine a collection of embeddings large enough that comparing a query against every stored vector is slow. Each comparison is cheap on its own, but multiplied across millions of stored items, the cost of answering one query grows quickly. Vector search algorithms exist to avoid that full comparison. Instead of checking everything, they organize the stored vectors ahead of time so that a query only needs to look at a promising subset.

The trade-off is that the answer becomes approximate. The search may skip some vectors that a full scan would have found. Two of the best-known strategies for this are IVF and Annoy. IVF groups similar vectors into clusters and searches only the clusters that look promising. Annoy builds several random tree structures and gathers candidates from the places a query lands in them. Both accept a small loss of exactness in exchange for a large gain in speed.

An IVF index is built by grouping. Each stored vector is placed into one cluster, so that vectors near one another in the embedding space tend to share a cluster. The grouping is what lets a query skip most of the database. The index is organized by cluster rather than by individual vector, which means the search can reason about whole groups at once.

The diagram above uses invented vector labels. The highlighted cluster is the one whose centroid sits closest to the query. The other clusters stay unsearched, which is where the speed comes from.

Annoy, which stands for Approximate Nearest Neighbors Oh Yeah, takes a different route from IVF. It is a tree-based approach introduced by Bernhardsson in 2013. Rather than computing centroids, Annoy builds a number of binary trees. Each tree divides the vectors using random criteria. One simple way to picture a split is to draw a random line through the space, send the vectors on one side into one branch, and send the vectors on the other side into the other branch. Repeating this splitting produces a tree whose leaves hold groups of vectors.

The diagram shows the idea with invented labels. Annoy does not rely on one tree. It builds several trees, each with its own random splits. During a search, the algorithm traverses these trees and gathers candidate neighbors from the leaves the query reaches. Because each tree splits the space differently, a neighbor missed by one tree may be caught by another. In the diagram, v4 appears in both leaves, while v1 and v2 each come from only one tree. Combining several trees improves the chance of collecting the true close matches.

Annoy is also a practical example of industrial use. Spotify has open sourced its implementation of the approach. The same broad goal is shared by other libraries the source names, namely SPTAG, which stands for Space Partition Tree And Graph and comes from Microsoft, and FLANN, which stands for Fast Library for Approximate Nearest Neighbors. You do not need to memorize their internals to see the pattern: each one trades a small amount of exactness for a large gain in speed.

Long before embeddings, retrieval relied on matching terms, and that history has produced many mature solutions. This is why both term-based and embedding-based retrieval are relatively easy to start with. Each approach has strengths, and the trade-offs the source describes can be laid out side by side.

The speed gap has a clear cause. Term extraction is faster than generating an embedding, and looking up which documents contain a term can be cheaper than a nearest-neighbor search. The strength of embedding-based retrieval is that it can be improved over time. Its weakness is that embeddings can blur exact strings. A specific error code such as EADDRNOTAVAIL (99) can therefore become harder to find later on.

A retriever is judged by the quality of the data it returns. Two metrics are often used by RAG evaluation frameworks: context precision and context recall, often called precision and recall for short. The source notes that context precision is also called context relevance. Precision asks how much of what was retrieved is actually relevant. Recall asks how much of the relevant material was retrieved at all.

These two measures are the natural way to judge an approximate method such as IVF or Annoy, because those methods can trade a missed neighbor for speed. A search that skips clusters or trees may return fewer irrelevant items, which helps precision, yet it may also miss relevant items, which hurts recall.