Five Ways to Index Vectors for RAG, Tested on a Million Wikipedia Embeddings

A RAG system lives or dies on retrieval, and retrieval gets harder as the corpus grows. This walk-through compares five ways of indexing vectors, using a real experiment, so the choice of method rests on numbers and not on habit.

What vector indexing is and why it matters

Vector indexing is a way of organizing a large set of vectors so that similar ones can be found quickly, without comparing the query to every single vector. Relational databases have an equivalent in bucketing and Z-ordering, which reduce how much data a query scans. Vector databases apply specialized structures to shrink the search space in the same spirit.

Accurate, low-latency retrieval is the base of any scalable RAG setup. Large products already depend on it: Amazon retrieves from catalogs with millions of products, Netflix from thousands of titles personalized across a global audience, and X from billions of posts and accounts. Data now arrives at terabytes per day, so scaling cannot be an afterthought. It has to be part of the architecture from the first design.

Each method below is judged on three measures:

• Latency: how fast the index returns the top-K results.
• Retrieval accuracy: how closely the results match those of an exact search.
• Maintenance complexity: how painful it is to keep the index current. The ground truth behind a RAG application rarely stands still, and data may need refreshing as often as every 24 hours, so an index must be practical to update within that window without heavy engineering effort.

The test setup

The experiment used the first one million rows of the CohereLabs/wikipedia-2023-11-embed-multilingual-v3 dataset, a scale that is big enough to show differences between methods. Queries were embedded with mxbai-embed-large, which produces 1,024-dimensional vectors that match the dataset's embeddings. The indexes were built in PostgreSQL with pgvector.

Method 1: flat search

Flat search, also called brute force, is the simplest option. Compute the similarity between the query and every vector, then keep the best matches.

• Latency: the worst of the group, since every vector is compared. Time grows linearly with the number of vectors.
• Accuracy: the best, because the search is exact and returns the true nearest vectors.
• Maintenance: none, since there is no index.

Average latency in the test was 6.25 seconds. A big retailer would reject that immediately, and so would a small startup.

Method 2: IVFFlat

Inverted File Flat is an approximate nearest neighbor technique. It uses K-Means to cut the vector space into clusters. Rather than scanning everything, it finds the centroids closest to the query and searches only inside those clusters, using exact distance calculations within them.

The flow looks like this:

Query → closest centroids → search selected clusters → Top-K

Two settings control it in pgvector. The number of clusters, called lists, is chosen up front, and the test used 1,000 lists. At query time a second setting, probes, decides how many of those lists get searched. With probes set to 10, the ten lists whose centroids sit nearest the query are scanned.

Latency was acceptable. With a million vectors and 1,000 clusters, queries finished in at most a second.

Accuracy was poor, for two reasons. First comes the boundary problem. Proximity is measured against centroids and not against the actual vectors, so some of the very closest vectors are missed when they belong to a cluster whose centroid happens to lie farther from the query. Second, probes caps the search at a fixed number of clusters, so relevant vectors in unsearched clusters never get considered.

Raising probes from 10 to 500 increased latency, though only slightly in this test. But there is no way to know in advance whether 10, 100, 500 or 900 probes will give the best recall, because the true neighbors might sit in a cluster that was skipped. Using all 1,000 probes defeats the point, since it turns the index back into brute force.

Maintenance was also poor. Building the index over a million vectors took roughly 2.37 minutes, which is acceptable. The pain comes with updates. Centroid-based indexes may need recalculating, or the vectors re-indexed, whenever a new batch of data arrives. At billions of vectors, that engineering overhead may not be worth paying.

For this use case the tradeoff between latency and accuracy was simply not acceptable. The next question is whether another method can cut latency and still retrieve better.

Method 3: HNSW

A postman looking for a house offers a good analogy. Given an address, he does not search every street. He takes major highways to the right region, where connections are few but cover long distances. Then he moves onto main roads, where the network is denser. Finally he walks local streets, where the network is densest, until he reaches the exact door.

HNSW, short for hierarchical navigable small world, works the same way. It begins with sparse, long-range links at the upper levels and moves through increasingly dense links at lower levels until it arrives at the nearest vectors. If the road hierarchy is well organized, the search heads straight toward the target, and good construction translates into good recall.

Latency was acceptable again, at most one second over a million vectors.

Accuracy was good, with caveats that come from the build parameters. The index is created with a statement of this shape:

    CREATE INDEX wikipedia_embeddings_hnsw_idx
    ON wikipedia_embeddings
    USING hnsw (emb vector_cosine_ops)
    WITH (
        m = 16,
        ef_construction = 64
    );

That statement builds the index over the corpus. Three parameters matter:

• m is the number of neighbors each vector may link to in the graph. It controls connectivity and density.
• ef_construction is the number of candidate neighbors considered while building. It controls the search space during construction.
• ef_search limits the search space at query time, since it sets how many candidates are explored while answering.

How does the graph pick its m links? For a million vectors, each one has 999,999 potential neighbors. The builder does not choose at random. It weighs candidates by distance plus a neighbor-selection heuristic and keeps a small set, around 16, that are useful for navigating the graph.

Why does that yield better accuracy?

1. A small number of useful neighbors per vector forms the highways of the graph.
2. Those links are picked to keep the graph connected and easy to navigate.
3. During a query, the search follows them step by step toward vectors that look more like the query.
4. Because the graph offers efficient paths into the relevant region, it is likelier to reach the true nearest neighbors.
5. So careful construction and navigation raise accuracy while avoiding an exhaustive comparison.

In short, the graph is built deliberately and not randomly. Setting m and ef_construction determines how it is built, which in turn shapes recall.

Maintenance is where HNSW hurts. Creating the index over a million vectors took a startling 37 minutes. On updates, if the initial dataset is large and represents the overall data distribution well, new data can keep being added without rebuilding. But as incoming data grows relative to the original set, the distribution may shift, the graph becomes less optimal and a rebuild eventually becomes necessary. That happens less often than with IVF, but it does happen.

Because the graph rests on a principled construction, it is a better option than IVF despite the extra engineering work. The latency and recall balance is acceptable, if not outstanding.

Method 4: BM25 plus vector search

Sometimes the obvious answer is the right one. While attention goes to ever more elaborate approaches, a thirty-year-old veteran has been sitting in plain sight. BM25 is a lexical ranking algorithm that scores documents by how often the query terms occur, how rare those terms are across the corpus and how long the document is.

The mechanics:

1. Documents are split into terms and an inverted index maps each term to the documents containing it.
2. Term frequency measures how often a term appears in a given document.
3. Inverse document frequency measures how rare or common the term is across the collection.
4. A term that is frequent in one document but uncommon overall earns higher importance.
5. BM25 combines these with document length to score relevance.
6. At query time, the query terms are looked up in the inverted index, scored against the matching documents, and the top-scoring ones are returned.

The formula itself is not pretty, but the idea is simple: find the documents most relevant to the words in the search.

Once those documents are retrieved, the search space has shrunk considerably. A flat vector search over that small set then finds the best chunks. That is hybrid retrieval.

One caution: the first stage looks for exact keywords, so a user's spelling mistake can hurt. An AI-assisted normalization step that fixes typos and variants before the search starts handles this easily.

Latency. The vector part answers in the expected milliseconds, but the lexical part hovered around 12 to 14 seconds in this setup. Caching can solve that, though the first request stays slow. Caching deserves a note here because it works especially well for BM25: exact documents are retrieved by matching keywords. For other indexing methods, caching has to be semantic, which needs a similarity threshold and may cost some retrieval accuracy.

Maintenance. None, since no vector index is built.

In practice, for most AI products with up to about 50,000 documents, hybrid retrieval with BM25 has been a consistent pick, offering a strong balance between latency and accuracy at that scale.

Method 5: DiskANN and the Vamana graph

This one is more abstract, like embeddings themselves. The process runs in eight steps:

1. Begin with the large collection of vectors that need efficient search.
2. Build a graph by linking each vector to a carefully chosen set of neighbors. This is the Vamana graph.
3. Store the graph on disk and not in memory, so datasets far larger than RAM can be handled.
4. When a query arrives, start from an entry point in the graph.
5. Follow connections between vectors, moving step by step toward regions near the query.
6. Load the needed nodes from the SSD as the search advances.
7. After exploring enough of the graph, collect a small set of promising candidates.
8. Compare those candidates more precisely and return the top-K nearest.

The key point is that the navigation graph lives on SSD and not in RAM, which makes size less of a limit than memory cost.

Do metadata filtering first

One technique deserves an honorable mention, and it should come before any of the methods above. Metadata filtering is the same idea as bucketing in a relational database: narrow the candidate set by attributes such as category, date or owner before any vector search runs.

Which one to choose

• Brute force: small to medium datasets, up to about 20,000 documents. Best accuracy with acceptable latency.
• BM25 plus vector search: medium datasets, roughly 20,000 to 100,000 documents. A strong balance of lexical and semantic retrieval.
• HNSW: large datasets with millions of vectors or more. Good latency and accuracy, at the price of higher build complexity.
• DiskANN and Vamana: when RAM becomes expensive. SSD carries the very large scale, so memory, not size, is the constraint.
• IVFFlat: large datasets, about one to ten million vectors, when the data distribution clusters well. Otherwise recall suffers.