Pourquoi tout comparer coûte si cher ?: explication détaillée avec exemples (RAG)

1. Aperçu

Dans un pipeline RAG (Retrieval-Augmented Generation), l’étape de retrieval consiste généralement à comparer le vecteur de la question avec les vecteurs de centaines de milliers de passages. L’approche la plus simple — comparer séquentiellement chaque vecteur — donne toujours un résultat exact mais le coût augmente linéairement avec la taille des données. Cet article explique pourquoi « tout comparer » est coûteux, comment l’Inverted-File Index (IVF) réduit les coûts par le clustering, et le prix que vous devez payer en acceptant des résultats approximatifs. Après avoir lu, vous saurez écrire un flat index et un IVF index simples en Java, mesurer le compromis entre la vitesse et le recall, et savoir quand utiliser — ou ne pas utiliser — la recherche approximative.

2. Le problème : Flat Index et complexité O(n)

2.1. Comment fonctionne la recherche plate

Flat index (ou recherche par force brute) compare la requête avec tous les vecteurs de l’ensemble de données, puis sélectionne les vecteurs avec les scores les plus élevés (généralement cosine similarity ou dot product). Il n’y a aucune étape de filtrage intermédiaire.

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

Chaque fois que vous appelez search, la boucle implicite dans stream() doit calculer le cosine avec tous les passages. Si l’ensemble de données a n vecteurs et chaque vecteur a d dimensions, le coût de chaque requête est O(n × d). Doublez le nombre de passages, doublez le nombre de comparaisons — c’est exactement le sens de « O(n) ».

Note: La recherche plate produit des résultats « exacts » — c’est-à-dire absolument corrects selon la formule de distance que vous choisissez. Mais « exact » ne signifie pas que le passage contient la bonne réponse au sens sémantique. La précision géométrique et la précision sémantique sont deux choses différentes.

2.2. Mesurer le coût augmentant avec la taille des données

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

Résultats illustratifs sur une machine de développement (les chiffres réels dépendent du matériel, mais la tendance reste la même) :

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

Les données augmentent de 10 fois, le temps augmente de près de 10 fois — exactement comme prévu avec O(n). Avec un million de passages et plusieurs requêtes par seconde, ce coût s’accumule très rapidement. C’est pourquoi flat index n’évolue pas bien pour les systèmes RAG en production.

3. Solution : Inverted-File Index (IVF)

3.1. Idée du clustering

IVF réduit les coûts en ne comparant pas avec tous les vecteurs. À la place :

Lors de la construction de l’index, exécutez un clustering (généralement k-means) pour trouver les « centroïdes » représentant chaque groupe de vecteurs proches.
Chaque vecteur de l’ensemble de données est assigné au groupe avec le centroïde le plus proche.
Lors de la recherche, sélectionnez seulement quelques groupes avec les centroïdes les plus proches de la requête, puis comparez uniquement avec les vecteurs dans ces groupes.

Imaginez un million de passages divisés en 1000 groupes. Si vous ne balayez que 10 groupes, vous comparez environ 10 000 passages au lieu du million entier — réduisant les coûts de près de 100 fois.

3.2. Le paramètre nprobe

Le nombre de groupes analysés s’appelle nprobe. Analyser plus de groupes améliore généralement le rappel (la proportion de résultats trouvés correctement) mais augmente aussi les coûts. C’est le paramètre que vous allez ajuster directement en 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 trouve les k centroïdes les plus proches de la requête — c’est exactement où nprobe fait la différence lors de l’appel de search(query, topK, nprobe). La partie construction de l’index (constructeur) s’exécute une fois, la partie recherche s’exécute à chaque requête — c’est pourquoi IVF est beaucoup plus rapide au moment de la requête.

Note: L’exemple ci-dessus utilise des centroïdes prédéfinis (échantillonnés à partir des données) pour garder le code court. En pratique, vous devez exécuter un vrai k-means (plusieurs boucles de mise à jour des centroïdes) pour que les groupes soient de bonne qualité — des bibliothèques comme FAISS, Milvus ou pgvector font déjà ce travail pour vous.

3.3. Câblage réel avec pgvector

Si vous utilisez PostgreSQL avec l’extension pgvector, le concept d’IVF et nprobe apparaît directement dans SQL :

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

SET ivfflat.probes = 10;

lists équivaut au nombre de clusters lors de la construction de l’index, probes équivaut à nprobe lors de la requête. Vous n’avez pas besoin d’écrire k-means vous-même — vous devez juste comprendre le compromis pour choisir un nombre approprié.

4. Compromis : recall vs. vitesse

IVF est une forme de recherche de voisin le plus proche approximatif (ANN). Il échange la précision absolue pour la vitesse. Le problème est que : les clusters sont formés à partir de distances mathématiques, pas à partir de limites de sujet « propres » selon la façon dont les gens classent les documents.

Exemple concret dans RAG : une clause sur « remboursement en cas de retard de vol » peut être plus proche du cluster de vecteurs d’un document d’assurance que du cluster « politique de dépenses de voyage » — bien que thématiquement, les employés la consulteraient dans les documents de voyage. Si nprobe analyse uniquement le cluster « politique de dépenses », la bonne réponse est complètement manquée, bien qu’elle existe dans les données.

4.1. Test vérifiant la baisse du rappel selon nprobe

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); // = analyser tout, équivalent à flat

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

approxManyProbes analyse tous les 40 clusters, donc le résultat correspond exactement à la recherche plate — c’est la ligne de base pour confirmer qu’IVF n’a pas d’erreur logique. approxFewProbes n’analyse que 1 cluster, et l’assertion finale confirme que le résultat diffère du cas exact — illustrant le risque de perte de rappel lorsque nprobe est trop bas.

exact            = [p1337, p0892, p0456, p1890, p0023]
approxFewProbes  = [p1337, p0456, p0901, p0234]   // seulement 4 résultats, manquent p0892, p1890
approxManyProbes = [p1337, p0892, p0456, p1890, p0023]

Quand nprobe est bas, l’index non seulement retourne moins de résultats que correct, mais peut aussi manquer des passages importants qui se trouvent « en dehors du cluster » — tout comme l’exemple d’assurance/dépenses de voyage ci-dessus.

5. Quand utiliser flat, quand utiliser IVF

Utilisez flat search lorsque: l’ensemble de données est petit (quelques dizaines de milliers de passages ou moins), ou vous avez besoin d’une précision absolue à des fins d’audit/conformité, ou vous êtes au stade du prototype et ne voulez pas encore ajuster les paramètres.
Utilisez IVF (ou HNSW) lorsque: l’ensemble de données est grand (des centaines de milliers à des millions de passages), la latence des requêtes est critique (chatbot, recherche en temps réel), et vous acceptez un rappel inférieur à 100% pour gagner de la vitesse.

Note: Ne choisissez pas nprobe trop bas juste parce que le benchmark de vitesse est beau. Mesurez le rappel sur un ensemble réel de questions pour votre système RAG — une réponse manquant de contexte important est pire qu’une requête lente de quelques dizaines de ms.

Un pattern courant en production : utilisez IVF (ou HNSW) pour récupérer rapidement les top-100 candidats avec un rappel acceptable, puis utilisez une étape de reclassement (cross-encoder ou flat search sur ce petit ensemble de 100 candidats) pour récupérer la précision perdue. Cette approche conserve la vitesse d’ANN tout en améliorant la qualité du résultat final.

6. Conclusion

La recherche plate est absolument exacte mais le coût augmente linéairement avec le nombre de passages — elle n’évolue pas lorsque votre RAG doit servir des millions de documents. IVF résout ce problème par le clustering et le paramètre nprobe, échangeant une partie du rappel pour gagner de la vitesse. Le prix à payer est que les clusters de vecteurs ne correspondent pas aux limites de sujet selon la compréhension humaine, donc les passages importants se retrouvent parfois « perdus » dans un cluster qui n’est pas analysé. Bien comprendre ce compromis vous aide à choisir le bon index, à régler correctement les paramètres, et à savoir quand vous avez besoin d’une étape de reclassement supplémentaire pour récupérer la précision.