Warum kostet die Brute-Force-Suche so viel?: Erklärung mit Beispielen

1. Übersicht

In der RAG-Pipeline (Retrieval-Augmented Generation) besteht der Retrieval-Schritt normalerweise darin, den Vektor einer Frage mit Vektoren von Hunderttausenden von Passages abzugleichen. Der einfachste Weg – ein sequenzieller Vergleich jedes Vektors – liefert immer das richtige Ergebnis, aber die Kosten wachsen linear mit der Datengröße. In diesem Artikel wird erklärt, warum die Brute-Force-Suche teuer ist, wie der Inverted-File Index (IVF) die Kosten durch Clustering reduziert und welchen Preis Sie zahlen müssen, wenn Sie ungefähre Ergebnisse akzeptieren. Nach dem Lesen werden Sie einen einfachen Flat-Index und einen IVF-Index in Java schreiben können, das Trade-off zwischen Geschwindigkeit und Recall messen und wissen, wann Sie approximate search verwenden sollten – und wann nicht.

2. Das Problem: Flat Index und O(n)-Komplexität

2.1. Wie Flat Search funktioniert

Der Flat-Index (oder Brute-Force-Suche) vergleicht die Query mit allen Vektoren im Datensatz und wählt dann diejenigen Vektoren mit den höchsten Bewertungen (normalerweise Kosinus-Ähnlichkeit oder Skalarprodukt) aus. Es gibt keinen Zwischenfilterschritt.

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));
    }
}

Bei jedem Aufruf von search muss die versteckte Schleife in stream() den Kosinus mit allen passages berechnen. Wenn der Datensatz n Vektoren hat und jeder Vektor d Dimensionen hat, beträgt die Kosten pro Query O(n × d). Doppelt so viele Passages bedeuten doppelt so viele Vergleiche – das ist, was „O(n)” bedeutet.

Hinweis: Die Flat-Suche liefert „exakte” Ergebnisse – absolut präzise nach der von Ihnen gewählten Abstandsformel. Aber „exakt” bedeutet nicht, dass die Passage semantisch die richtige Antwort enthält. Geometrische Genauigkeit und semantische Genauigkeit sind zwei verschiedene Dinge.

2.2. Messung des Kostenaufstiegs mit der Datengröße

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);
    }
}

Die Ergebnisse sind Beispiele auf einer Entwicklungsmaschine (tatsächliche Zahlen hängen von der Hardware ab, aber der Trend bleibt gleich):

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

Die Daten wachsen um den Faktor 10, die Zeit wächst um den Faktor 10 – exakt wie die O(n) Vorhersage. Mit einer Million Passages und vielen Queries pro Sekunde summieren sich diese Kosten sehr schnell auf. Das ist der Grund, warum Flat-Indizes nicht gut für produktive RAG-Systeme skalieren.

3. Lösung: Inverted-File Index (IVF)

3.1. Die Clustering-Idee

Der IVF reduziert die Kosten, indem er nicht mit jedem Vektor vergleicht. Stattdessen:

1. Beim Erstellen des Index wird Clustering (normalerweise k-means) ausgeführt, um „Zentroiden” zu finden, die jede Gruppe von ähnlichen Vektoren repräsentieren.
2. Jeder Vektor im Datensatz wird der Gruppe mit dem nächstgelegenen Zentroid zugewiesen.
3. Bei der Suche werden nur eine Anzahl von Gruppen mit den nächstgelegenen Zentroiden zur Query ausgewählt, und es wird nur mit Vektoren in diesen Gruppen verglichen.

Stellen Sie sich vor: eine Million Passages verteilt auf 1000 Gruppen. Wenn Sie nur 10 Gruppen durchsuchen, vergleichen Sie etwa 10.000 Passages statt einer Million – eine Kostenreduktion um etwa das 100-fache.

3.2. Der nprobe-Parameter

Die Anzahl der durchsuchten Gruppen heißt nprobe. Die Suche in mehr Gruppen verbessert normalerweise den Recall (die Quote der Treffer), erhöht aber auch die Kosten. Dies ist der Parameter, den Sie direkt in der Produktion abstimmen werden.

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 findet die k dem Query am nächsten gelegenen Zentroiden – hier kommt nprobe zum Einsatz, wenn search(query, topK, nprobe) aufgerufen wird. Der Index-Build-Teil (Konstruktor) läuft einmal, der Search-Teil läuft pro Query – deshalb ist der IVF bei der Abfragezeitpunkt viel schneller.

Hinweis: Das obige Beispiel verwendet vordefinierte Zentroiden (aus den Daten abgetastet), um den Code kurz zu halten. In der Praxis müssen Sie echter k-means ausführen (mehrere Iterationen zur Zentroid-Aktualisierung), um hochwertige Cluster zu erhalten – Bibliotheken wie FAISS, Milvus oder pgvector haben dies bereits für Sie erledigt.

3.3. Praktische Integration mit pgvector

Wenn Sie PostgreSQL mit der pgvector-Erweiterung verwenden, erscheinen die IVF-Konzepte und nprobe direkt im SQL:

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

SET ivfflat.probes = 10;

lists entspricht der Anzahl der Cluster bei der Index-Erstellung, probes entspricht nprobe bei der Query. Sie müssen k-means nicht selbst schreiben – Sie müssen nur das Trade-off verstehen, um angemessene Zahlen zu wählen.

4. Das Trade-off: Recall vs. Geschwindigkeit

Der IVF ist eine Form von Approximate Nearest Neighbor (ANN). Er tauscht absolute Genauigkeit gegen Geschwindigkeit ein. Das Problem ist: Cluster werden basierend auf mathematischen Abständen gebildet, nicht auf „sauberen” Themengrenzen, wie ein Mensch Dokumente klassifizieren würde.

Ein konkretes Beispiel in RAG: Eine Klausel über „Rückerstattung bei verspäteten Flügen” könnte näher bei einem Cluster von Versicherungsdokumenten liegen als bei einem Cluster für „Geschäftsreisekosten-Richtlinien” – obwohl semantisch ein Mitarbeiter danach in den Geschäftsreisedokumenten suchen würde. Wenn nprobe nur den Cluster „Geschäftsreisekosten” durchsucht, wird die richtige Antwort völlig übersehen, auch wenn sie in den Daten vorhanden ist.

4.1. Test, um zu prüfen, wie Recall mit nprobe sinkt

class IvfIndexTest {

    @Test
    void nprobeThapCoTheLamMatKetQuaDung() {
        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); // = alle durchsuchen, entspricht flat

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

approxManyProbes durchsucht alle 40 Cluster, daher stimmen die Ergebnisse vollständig mit der Flat-Suche überein – dies ist die Baseline, um zu bestätigen, dass der IVF keine Fehler in der Logik hat. approxFewProbes durchsucht nur 1 Cluster, und die letzte Assertion bestätigt, dass das Ergebnis unterschiedlich vom genauen Fall ist – dies zeigt das Risiko, Recall zu verlieren, wenn nprobe zu niedrig ist.

exact            = [p1337, p0892, p0456, p1890, p0023]
approxFewProbes  = [p1337, p0456, p0901, p0234]   // nur 4 Ergebnisse, p0892 und p1890 fehlen
approxManyProbes = [p1337, p0892, p0456, p1890, p0023]

Wenn nprobe niedrig ist, gibt der Index nicht nur weniger Ergebnisse zurück als richtig, sondern kann auch wichtige Passages übersehen, die in einem „verschobenen Cluster” liegen – genau wie im Versicherungs-/Geschäftsreisekosten-Beispiel oben.

5. Wann man Flat verwendet, wann man IVF verwendet

• Verwenden Sie Flat Search, wenn: der Datensatz klein ist (einige Zehntausend Passages oder weniger), oder Sie absolute Genauigkeit für Audit-/Compliance-Zwecke benötigen, oder Sie sich in einer Prototyp-Phase befinden und keine zusätzlichen Parameter abstimmen möchten.
• Verwenden Sie IVF (oder HNSW), wenn: der Datensatz groß ist (Hunderttausende bis Millionen Passages), die Query-Latenz ein kritischer Faktor ist (Chatbots, Echtzeit-Suche), und Sie einen Recall unter 100% akzeptieren, um Geschwindigkeit zu gewinnen.

Hinweis: Wählen Sie nprobe nicht zu niedrig nur wegen schöner Speed-Benchmarks. Messen Sie den Recall auf echten Fragen Ihres RAG-Systems – eine Antwort, der wichtige Kontexte fehlen, ist schlechter als eine um einige Dutzend ms langsamere Query.

Ein häufiges Muster in der Produktion: Verwenden Sie IVF (oder HNSW), um schnell die Top-100-Kandidaten mit akzeptablem Recall zu erhalten, dann verwenden Sie einen Reranking-Schritt (Cross-Encoder oder Flat Search auf den kleinen Satz von 100 Kandidaten), um die verlorene Genauigkeit auszugleichen. Auf diese Weise behalten Sie die Geschwindigkeit des ANN, während Sie die Qualität der endgültigen Ergebnisse verbessern.

6. Fazit

Die Flat-Suche ist absolut präzise, aber die Kosten wachsen linear mit der Anzahl der Passages – sie skaliert nicht, wenn Ihre RAG Millionen von Dokumenten bedienen muss. Der IVF löst dieses Problem durch Clustering und den Parameter nprobe, tauscht einen Teil des Recalls gegen Geschwindigkeit ein. Der Preis ist, dass Vektor-Cluster nicht mit Themengrenzen so übereinstimmen, wie Menschen sie verstehen, daher liegen wichtige Passages manchmal „verloren” in nicht durchsuchten Clustern. Wenn Sie dieses Trade-off verstehen, können Sie den richtigen Index wählen, die Parameter korrekt tunen und wissen, wann Sie einen Reranking-Schritt hinzufügen sollten, um die Genauigkeit auszugleichen.