Why exhaustive search costs so much?: detailed explanation with examples (RAG)

1. Overview

In the RAG (Retrieval-Augmented Generation) pipeline, the retrieval step typically matches question vectors against vectors of hundreds of thousands of passages. The simplest approach — sequentially comparing each vector — always yields correct results but costs grow linearly with data size. This article explains why “comparing everything” is expensive, how Inverted-File Index (IVF) reduces costs through clustering, and the price you pay when accepting approximate results. After reading, you’ll be able to write a simple flat index and an IVF index in Java yourself, measure the tradeoff between speed and recall, and know when you should — or shouldn’t — use approximate search.

2. Problem: Flat Index and O(n) Complexity

2.1. How flat search works

Flat index (or brute-force search) compares the query against every vector in the dataset, then selects vectors with the highest scores (typically cosine similarity or dot product). There’s no intermediate filtering step.

public record Passage(String id, float[] vector) {}

public class FlatVectorIndex {

    private final List<Passage> passages;

    public FlatVectorIndex(List<Passage> passages) {
        this.passages = passages;
    }

    public List<Passage> search(float[] query, int topK) {
        return passages.stream()
                .sorted(Comparator.comparingDouble(p -> -cosine(query, p.vector())))
                .limit(topK)
                .toList();
    }

    private double cosine(float[] a, float[] b) {
        double dot = 0, na = 0, nb = 0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            na += a[i] * a[i];
            nb += b[i] * b[i];
        }
        return dot / (Math.sqrt(na) * Math.sqrt(nb));
    }
}

Each call to search, the hidden loop in stream() must compute cosine with every passages. If the dataset has n vectors and each vector has d dimensions, the cost per query is O(n × d). Double the number of passages, double the comparisons — that’s exactly what “O(n)” means.

Note: Flat search gives “exact” results — meaning perfectly correct according to the distance formula you chose. But “exact” doesn’t mean the passage actually contains a semantically correct answer. Geometric precision and semantic accuracy are two different things.

2.2. Measuring cost growth with data size

public static void main(String[] args) {
    for (int n : List.of(10_000, 100_000)) {
        var passages = TestData.generatePassages(n, 128, 42);
        var index = new FlatVectorIndex(passages);
        float[] query = TestData.randomVector(128, 7);

        long start = System.nanoTime();
        index.search(query, 5);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        System.out.printf("n=%d -> %d ms%n", n, elapsedMs);
    }
}

Results illustrated on a development machine (actual numbers depend on hardware, but the trend always holds):

n=10000  -> 18 ms
n=100000 -> 176 ms

Data increases 10x, time increases nearly 10x — exactly as predicted by O(n). With a million passages and many queries per second, this cost adds up very quickly. This is why flat index doesn’t scale well for production RAG systems.

3. Solution: Inverted-File Index (IVF)

3.1. The clustering idea

IVF reduces costs by not comparing against every vector. Instead:

1. When building the index, run clustering (typically k-means) to find “centroids” that represent each group of nearby vectors.
2. Each vector in the dataset is assigned to the group whose centroid is nearest.
3. When searching, select only a few groups whose centroids are nearest the query, then compare only against vectors in those groups.

Imagine a million passages divided into 1000 groups. If you scan only 10 groups, you compare roughly 10,000 passages instead of the entire million — reducing cost by nearly 100x.

3.2. The nprobe parameter

The number of groups scanned is called nprobe. Scanning more groups typically improves recall (the ratio of finding correct results) but also increases cost. This is a parameter you’ll tune directly in production.

public class IvfIndex {

    private final List<float[]> centroids;
    private final Map<Integer, List<Passage>> buckets = new HashMap<>();

    public IvfIndex(List<Passage> passages, List<float[]> centroids) {
        this.centroids = centroids;
        for (Passage p : passages) {
            int cluster = nearestCentroidIndex(p.vector());
            buckets.computeIfAbsent(cluster, k -> new ArrayList<>()).add(p);
        }
    }

    public List<Passage> search(float[] query, int topK, int nprobe) {
        List<Integer> clusters = nearestCentroidIndices(query, nprobe);
        return clusters.stream()
                .flatMap(c -> buckets.getOrDefault(c, List.of()).stream())
                .sorted(Comparator.comparingDouble(p -> -cosine(query, p.vector())))
                .limit(topK)
                .toList();
    }

    private int nearestCentroidIndex(float[] v) {
        return nearestCentroidIndices(v, 1).get(0);
    }

    private List<Integer> nearestCentroidIndices(float[] v, int k) {
        return IntStream.range(0, centroids.size())
                .boxed()
                .sorted(Comparator.comparingDouble(i -> -cosine(v, centroids.get(i))))
                .limit(k)
                .toList();
    }

    private double cosine(float[] a, float[] b) {
        double dot = 0, na = 0, nb = 0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            na += a[i] * a[i];
            nb += b[i] * b[i];
        }
        return dot / (Math.sqrt(na) * Math.sqrt(nb));
    }
}

nearestCentroidIndices finds the k centroids nearest the query — this is where nprobe takes effect when calling search(query, topK, nprobe). Building the index (constructor) runs once, the search part runs per query — that’s why IVF is much faster at query time.

Note: The example above uses pre-set centroids (sampled from data) to keep the code short. In practice, you need to run real k-means (many iterations of centroid updates) so clusters have good quality — libraries like FAISS, Milvus, or pgvector do this for you.

3.3. Wiring in practice with pgvector

If you’re using PostgreSQL with the pgvector extension, the concepts of IVF and nprobe appear directly in SQL:

CREATE INDEX ON passages USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 1000);

SET ivfflat.probes = 10;

lists is equivalent to the number of clusters when building the index, probes is equivalent to nprobe when querying. You don’t need to write k-means yourself — just understand the tradeoff to choose reasonable numbers.

4. Tradeoff: recall vs. speed

IVF is a form of approximate nearest neighbor (ANN). It trades absolute accuracy for speed. The issue is: clusters are formed from mathematical distance, not from clean topical boundaries the way humans organize documents.

A concrete RAG example: a clause about “refund if flight is delayed” might lie closer to the vector cluster of insurance documents than the “business travel expenses policy” cluster — yet topically, an employee would look for it in travel policy. If nprobe scans only the expenses cluster, the correct answer gets completely missed, even though it’s in the data.

4.1. Test: verifying recall drops with low nprobe

class IvfIndexTest {

    @Test
    void lowNprobeCanMissCorrectResults() {
        var passages = TestData.generatePassages(2000, 64, 42);
        var centroids = TestData.sampleCentroids(passages, 40, 42);
        var ivf = new IvfIndex(passages, centroids);
        var flat = new FlatVectorIndex(passages);

        float[] query = passages.get(1337).vector();

        var exact = flat.search(query, 5);
        var approxFewProbes = ivf.search(query, 5, 1);
        var approxManyProbes = ivf.search(query, 5, 40); // = scan all, equivalent to flat

        assertThat(approxManyProbes).containsExactlyInAnyOrderElementsOf(exact);
        assertThat(approxFewProbes).isNotEqualTo(approxManyProbes);
    }
}

approxManyProbes scans all 40 clusters so the result exactly matches flat search — this is our baseline to confirm IVF has no logic errors. approxFewProbes scans only 1 cluster, and the final assertion confirms the result differs from the exact case — illustrating the risk of losing recall when nprobe is too low.

exact            = [p1337, p0892, p0456, p1890, p0023]
approxFewProbes  = [p1337, p0456, p0901, p0234]   // only 4 results, missing p0892, p1890
approxManyProbes = [p1337, p0892, p0456, p1890, p0023]

When nprobe is low, the index doesn’t just return fewer results than correct — it can miss important passages lying “outside the chosen cluster” — matching the insurance/travel expenses example above.

5. When to use flat, when to use IVF

• Use flat search when: dataset is small (tens of thousands of passages or less), or you need absolute accuracy for audit/compliance purposes, or you’re still in prototype phase and don’t want to tune more parameters.
• Use IVF (or HNSW) when: dataset is large (hundreds of thousands to millions of passages), query latency is critical (chatbots, real-time search), and you accept recall under 100% to trade off for speed.

Note: Don’t choose nprobe too low just because the speed benchmark looks nice. Measure recall on real questions from your RAG system — a response missing important context is worse than a query that’s a few tens of milliseconds slower.

A common production pattern: use IVF (or HNSW) to quickly get top-100 candidates with acceptable recall, then use a reranking step (cross-encoder or flat search on just those 100 candidates) to recover the lost precision. This keeps ANN speed while improving final result quality.

6. Conclusion

Flat search is perfectly accurate but costs grow linearly with the number of passages — it doesn’t scale when your RAG has to serve millions of documents. IVF solves this with clustering and the nprobe parameter, trading some recall for speed. The price is that vector clusters don’t align with topical boundaries the way humans understand them, so important passages sometimes end up “lost” in an unscanned cluster. Understanding this tradeoff helps you choose the right index, tune parameters correctly, and know when you need a reranking step to recover precision.