Indexation Vectorielle : Techniques et Algorithmes

Introduction à l'indexation vectorielle

Pourquoi l'indexation est-elle nécessaire ?

Lorsque vous travaillez avec des embeddings dans une application IA, la recherche de similarité devient rapidement un goulot d'étranglement. Imaginez une base vectorielle contenant 10 millions de documents représentés par des vecteurs de 1536 dimensions (OpenAI ada-002). Une recherche naïve nécessiterait de calculer la distance entre votre requête et les 10 millions de vecteurs stockés.

Complexité algorithmique : Cette approche dite "brute force" ou k-NN exhaustive a une complexité O(n × d), où n est le nombre de vecteurs et d la dimensionnalité. Pour notre exemple :

• 10M vecteurs × 1536 dimensions × 4 bytes (float32) = 58.6 GB de données à parcourir
• Temps de calcul : 3-15 secondes sur CPU moderne (single-thread)
• Impossible à scaler pour applications temps réel (SLA <100ms)

L'indexation vectorielle résout ce problème en créant des structures de données spécialisées qui permettent de trouver les vecteurs les plus similaires en temps logarithmique ou sous-linéaire : O(log n) au lieu de O(n). C'est l'équivalent d'un index B-tree pour les bases SQL, mais adapté aux espaces vectoriels haute dimension.

Recherche exacte vs approximative (ANN)

Il existe deux approches fondamentales pour la recherche de voisins dans un espace vectoriel :

k-NN Exact (k-Nearest Neighbors Exhaustive)

La recherche k-NN exacte garantit de trouver les k vecteurs les plus proches en calculant la distance avec tous les vecteurs de la base. C'est la "vérité terrain" (ground truth) utilisée comme référence pour évaluer les algorithmes approximatifs.

• Avantages : Précision 100% (recall@k = 1.0), pas de faux négatifs
• Inconvénients : Complexité O(n), impossible à scaler au-delà de 1-10M vecteurs
• Cas d'usage : Datasets <100K vecteurs, benchmarks, validation d'algorithmes
• Implémentations : FAISS IndexFlatL2, NumPy/SciPy pairwise_distances

ANN (Approximate Nearest Neighbors)

Les algorithmes ANN acceptent un compromis précision/vitesse en ne garantissant pas de trouver les k voisins exacts, mais en offrant une très bonne approximation (recall 95-99%+) avec une latence drastiquement réduite.

• Avantages : Complexité O(log n), scalable à des milliards de vecteurs, latence <100ms
• Inconvénients : Précision non garantie, tuning des hyperparamètres nécessaire
• Cas d'usage : Production ML, RAG, moteurs de recommandation, recherche sémantique
• Algorithmes : HNSW, IVF, Product Quantization, LSH (voir sections dédiées)

Le compromis vitesse-précision-mémoire

L'indexation vectorielle implique trois dimensions à optimiser simultanément. Il est impossible d'optimiser les trois à leur maximum : vous devez faire des arbitrages selon vos contraintes.

Scénarios Typiques d'Arbitrage

Vue d'ensemble des familles d'algorithmes

Les algorithmes d'indexation vectorielle se regroupent en quatre grandes familles, chacune avec ses principes, avantages et limites :

Dans la pratique moderne (2024-2025), HNSW domine pour la précision/latence (utilisé par Qdrant, Weaviate, Vespa), tandis que IVF+PQ reste le champion de la compression (FAISS, Milvus en mode économique). LSH et Annoy sont progressivement remplacés par ces solutions plus performantes.

HNSW (Hierarchical Navigable Small World)

Principe de fonctionnement

HNSW (Hierarchical Navigable Small World Graphs) est l'algorithme d'indexation vectorielle le plus performant en termes de rapport recall/latence depuis sa publication en 2016 par Yury Malkov et Dmitry Yashunin. Il combine deux concepts clés :

1. Navigable Small World (NSW) : Un graphe où chaque nœud est connecté à ses voisins proches + quelques connexions longue distance, permettant une navigation efficace (inspiration : six degrés de séparation)
2. Hiérarchie multi-niveaux : Plusieurs couches de graphes superposées, des plus éparses (en haut) aux plus denses (en bas), à la manière d'un skip-list probabiliste

L'idée centrale : au lieu de parcourir tous les vecteurs, HNSW navigue dans un graphe en "sautant" de voisin en voisin, en se rapprochant progressivement de la zone cible. La hiérarchie permet de faire de grands bonds initiaux, puis d'affiner progressivement.

Structure de graphe hiérarchique

HNSW organise les vecteurs en L couches (layers) superposées, où chaque couche l contient un sous-ensemble des nœuds de la couche l-1 :

• Couche 0 (base layer) : Contient TOUS les vecteurs, densément connectés (M*2 connexions par nœud)
• Couches supérieures (1, 2, ..., L) : Sous-échantillonnage exponentiel décroissant, connexions longue distance
• Point d'entrée : Un nœud unique dans la couche la plus haute, point de départ de toutes les recherches

Construction de l'index

La construction d'un index HNSW se fait par insertions séquentielles des vecteurs. Pour chaque vecteur inséré :

1. Détermination du niveau : Tirage aléatoire du niveau max lc pour ce nœud avec probabilité exponentielle décroissante : lc = floor(-ln(uniform(0,1)) * ml)
2. Recherche des voisins : Navigation depuis l'entry point jusqu'à la couche 0 pour trouver les M plus proches voisins à chaque niveau ≤ lc
3. Connexion bidirectionnelle : Création d'arêtes entre le nouveau nœud et ses M voisins + ajout de l'arête retour
4. Pruning : Si un nœud existant dépasse M connexions, suppression des arêtes les plus longues (heuristique de diversité)

Complexité de construction : O(N * log(N) * M * d) pour N vecteurs de dimension d. Sur CPU moderne, compter 500-2000 vecteurs/sec pour des dimensions 768-1536.

Algorithme de recherche

La recherche dans HNSW se déroule en trois phases, de haut en bas des couches :

Phase 1 : Navigation Grossière (Couches Hautes)

Départ depuis l'entry point de la couche supérieure. À chaque étape :

• Évaluation des voisins directs du nœud courant
• Sélection du voisin le plus proche du vecteur de requête
• Si aucun voisin n'est plus proche → descendre d'une couche

Phase 2 : Recherche Locale (Couches Intermédiaires)

Même processus que phase 1, mais avec une liste de candidats étendue (efSearch au lieu de 1).

Phase 3 : Affinement Final (Couche 0)

Sur la couche de base, exploration exhaustive de la zone locale avec :

• Priority queue des efSearch meilleurs candidats
• Expansion itérative vers les voisins non visités
• Arrêt quand aucun candidat ne peut améliorer les top-k actuels

Complexité de recherche : O(log(N) * M * d) en moyenne. Nombre typique de calculs de distance : 500-3000 pour efSearch=100 (vs 10M en brute force).

Paramètres clés (M, efConstruction, efSearch)

HNSW expose trois hyperparamètres principaux qui contrôlent le trade-off précision/latence/mémoire :

Avantages et limitations

Avantages de HNSW

• Meilleur rapport recall/latence : Systématiquement en tête des benchmarks ANN (ann-benchmarks.com)
• Robustesse dimensionnelle : Performant de 128 à 2048 dimensions sans tuning majeur
• Insertion dynamique : Support natif des insertions/suppressions (contrairement à LSH statique)
• Pas de phase d'entraînement : Contrairement à IVF (clustering k-means), construction incrémentale
• Parallélisation : Recherches indépendantes facilement multi-threadées

Limitations de HNSW

• Consommation mémoire : 40-60 bytes/vecteur (index) + 4*d bytes (vecteurs bruts). Pour 10M vecteurs 1536-dim : 60GB+ RAM
• Construction lente : O(N log N), peut prendre plusieurs heures pour 100M+ vecteurs
• Pas de compression native : Doit être combiné avec PQ pour réduire l'empreinte mémoire
• Sensibilité aux données déséquilibrées : Clustering fort peut dégrader les performances (curse of dimensionality)
• Coût de mise à jour : Les modifications fréquentes peuvent fragmenter le graphe

Cas d'usage recommandés

IVF (Inverted File Index)

Concept de partitionnement de l'espace

IVF (Inverted File Index) adopte une approche radicalement différente de HNSW : au lieu de naviguer dans un graphe, IVF partitionne l'espace vectoriel en régions (clusters) et effectue la recherche uniquement dans les clusters les plus proches du vecteur de requête.

L'analogie : imaginez une bibliothèque organisée par thèmes (sciences, littérature, histoire...). Pour trouver un livre sur la physique quantique, vous n'avez pas besoin de parcourir TOUTE la bibliothèque : vous allez directement à la section "Sciences" puis cherchez localement. IVF applique ce principe aux vecteurs.

Architecture IVF en 3 Composants

1. Centroid list : nlist vecteurs centraux (centroids) représentant chaque cluster
2. Inverted lists : nlist listes contenant les IDs des vecteurs appartenant à chaque cluster
3. Vector storage : Stockage des vecteurs originaux (IVF-Flat) ou compressés (IVF-PQ)

Clustering avec k-means

La construction d'un index IVF commence par une phase d'entraînement (training) qui partitionne l'espace vectoriel via l'algorithme k-means :

Étape 1 : Entraînement k-means

• Initialisation : Sélection aléatoire de nlist centroids initiaux (ou k-means++)
• Itérations : Assignation de chaque vecteur au centroid le plus proche, puis recalcul des centroids (moyenne des vecteurs assignés)
• Convergence : Arrêt quand les centroids bougent de moins de ε (typiquement 20-100 itérations)
• Complexité : O(nlist * N * d * iterations) → peut prendre 10-60 minutes pour 10M vecteurs

Étape 2 : Assignation des Vecteurs

Une fois les centroids entraînés, chaque vecteur de la base est assigné au cluster de son centroid le plus proche. Cette assignation est stockée dans les inverted lists.

Choix du Nombre de Clusters (nlist)

Le paramètre nlist contrôle la granularité du partitionnement. Règle empirique :

• Formule heuristique : nlist ≈ sqrt(N) où N = nombre total de vecteurs
• 1M vecteurs → nlist = 1,000
• 10M vecteurs → nlist = 4,096 (puissance de 2 pour optimisations)
• 100M vecteurs → nlist = 16,384

Processus de recherche

La recherche IVF se déroule en trois étapes distinctes :

Phase 1 : Quantization Grossière (Coarse Quantization)

Calcul des distances entre le vecteur de requête et les nlist centroids, puis sélection des nprobe clusters les plus proches. Cette phase est un k-NN exhaustif, mais sur seulement nlist vecteurs (ex: 4096 au lieu de 10M).

Phase 2 : Recherche Locale dans Clusters

Pour chaque cluster sélectionné, calcul de la distance entre le vecteur de requête et tous les vecteurs de ce cluster. Les vecteurs sont chargés depuis le storage (RAM ou disque selon implémentation).

Phase 3 : Agrégation et Reranking

Fusion des résultats des nprobe clusters, tri par distance, et retour des top-k.

IVF-Flat vs IVF-PQ

IVF existe en deux variantes principales, selon le stockage des vecteurs :

Combinaison optimale : IVF-PQ est le choix par défaut pour datasets >10M vecteurs. La compression PQ (voir section dédiée) réduit drastiquement les besoins mémoire avec une perte de recall acceptable (95-98% vs 98-99% pour IVF-Flat).

Paramètre nprobe et optimisation

Le paramètre nprobe contrôle le nombre de clusters explorés lors de la recherche. C'est le levier principal du trade-off recall/latence pour IVF.

Avantages et limitations

Avantages d'IVF

• Scalabilité massive : Performant jusqu'à plusieurs milliards de vecteurs (avec IVF-PQ)
• Efficacité mémoire : Avec PQ, 10-30x moins de RAM que HNSW
• Parallélisation naturelle : Recherche dans clusters indépendants = GPU-friendly
• Coût prévisible : Latence proportionnelle à nprobe (contrairement à HNSW où worst-case difficile à borner)
• Insertion batch efficace : Ajout de millions de vecteurs sans dégradation (contrairement à HNSW)

Limitations d'IVF

• Phase d'entraînement : Clustering k-means prend 10-60 min (vs construction incrémentale HNSW)
• Recall inférieur à HNSW : À latence égale, recall typiquement -2 à -5% vs HNSW
• Sensibilité à la distribution : Clusters déséquilibrés (certains avec 100x plus de vecteurs) dégradent les performances
• Mise à jour coûteuse : Modifications importantes nécessitent re-training complet des centroids
• Curse of dimensionality : Efficacité réduite au-delà de 2048 dimensions (centroids trop proches)

Cas d'usage recommandés

PQ (Product Quantization)

Principe de compression vectorielle

Product Quantization (PQ) n'est pas un algorithme d'indexation à proprement parler, mais une technique de compression qui réduit drastiquement l'empreinte mémoire des vecteurs en les encodant avec des codes compacts. PQ est souvent combiné avec IVF (IVF-PQ) ou HNSW pour permettre l'indexation de milliards de vecteurs.

L'idée centrale : au lieu de stocker un vecteur de 1536 dimensions en float32 (6144 bytes), PQ le représente avec un code de 16-64 bytes, soit une compression de 50-400x, tout en préservant suffisamment d'information pour calculer des distances approximatives.

Décomposition en sous-espaces

PQ fonctionne en décomposant chaque vecteur haute dimension en m sous-vecteurs de dimension d/m, puis en quantifiant indépendamment chaque sous-vecteur.

Étape 1 : Partitionnement du Vecteur

Un vecteur x ∈ ℝ^d est découpé en m segments contigus :

• Exemple : Vecteur 1536-dim avec m=64 → 64 sous-vecteurs de 24 dimensions chacun
• x = [x₁, x₂, ..., xₖ₄] où chaque xᵢ ∈ ℝ²⁴
• Le découpage est fixe et identique pour tous les vecteurs

Codebooks et quantification

Pour chaque sous-espace, PQ entraîne un codebook (dictionnaire) via k-means contenant k centroids (typiquement k=256 pour encoding sur 8 bits = 1 byte).

Phase d'Entraînement

1. Découpage : Tous les vecteurs du training set sont découpés en m sous-vecteurs
2. Clustering indépendant : Pour chaque sous-espace i (i=1..m), exécution de k-means sur tous les sous-vecteurs xᵢ pour obtenir k=256 centroids
3. Stockage codebooks : Résultat = m codebooks de k centroids chacun (ex: 64 × 256 × 24 floats)

Phase d'Encodage

Pour encoder un nouveau vecteur x :

1. Découpage en m sous-vecteurs : x = [x₁, ..., xₘ]
2. Pour chaque sous-vecteur xᵢ, trouver le centroid le plus proche dans le codebook i → index cᵢ ∈ [0, 255]
3. Le vecteur compressé est la concaténation des m indices : code(x) = [c₁, c₂, ..., cₘ]
4. Stockage : m bytes au lieu de d × 4 bytes

Calcul de distance approximatif

La magie de PQ : il est possible de calculer une distance approximative entre deux vecteurs compressés SANS les décompresser, via des lookup tables précalculées.

Asymmetric Distance Computation (ADC)

Cas typique : requête (non compressée) vs base de données (compressée PQ)

1. Précalcul : Pour le vecteur de requête q, découper en m sous-vecteurs [q₁, ..., qₘ]
2. Distance tables : Pour chaque sous-espace i, calculer les distances entre qᵢ et les k=256 centroids du codebook i → m tables de 256 distances
3. Lookup : Pour un vecteur compressé code(x)=[c₁,...,cₘ], la distance approximative est : d(q,x) ≈ √(Σᵢ distance_tableᵢ[cᵢ]²)
4. Complexité : O(m) au lieu de O(d) → gain 16-64x en vitesse de calcul

Réduction de la consommation mémoire

Au-delà de la compression des vecteurs, PQ impacte positivement toute la chaîne de traitement :

Bénéfices Cascades de PQ

• Cache CPU : Plus de vecteurs tiennent dans L3 cache (30-100MB) → moins de cache misses
• Bande passante mémoire : Transfert RAM → CPU 50-100x réduit → goulot d'étranglement éliminé
• Stockage disque : Bases 100M+ vecteurs tiennent sur SSD au lieu de RAM → coût 10x inférieur
• Réseau : Si recherche distribuée, transfert inter-nœuds accéléré
• GPU : Plus de vecteurs dans VRAM (16-80GB) → batch processing plus efficace

Variantes de Quantization

Avantages et limitations

Avantages de Product Quantization

• Compression extrême : 50-400x réduction mémoire, permet datasets massifs
• Vitesse de calcul : ADC 16-64x plus rapide que distance float32
• Scalabilité coût : Coût infrastructure réduit de 10-50x pour gros volumes
• Complémentarité : S'intègre avec IVF, HNSW, disk-based indexes
• GPU-friendly : Lookups vectorisés exploitent massivement les CUDA cores

Limitations de PQ

• Perte de précision : Recall -3 à -8% vs vecteurs non compressés
• Phase d'entraînement : Clustering k-means sur m sous-espaces = 30-120 min pour 10M vecteurs
• Sensibilité à la distribution : Vecteurs très clusterés ou outliers dégradent la quantization
• Tuning délicat : Choix de m et k impacte fortement recall et latence, nécessite expérimentation
• Moins efficace en basse dimension : PQ optimal pour d ≥ 128, peu utile pour d < 64

LSH (Locality Sensitive Hashing)

Concept de hashing sensible à la localité

Locality Sensitive Hashing (LSH) adopte une approche radicalement différente des méthodes précédentes : au lieu de structurer l'espace avec des graphes (HNSW) ou des clusters (IVF), LSH utilise des fonctions de hachage spéciales qui mappent les vecteurs similaires vers les mêmes buckets (hash codes) avec haute probabilité.

Propriété fondamentale : Si deux vecteurs sont proches selon une métrique de distance (cosine, euclidean), ils ont une forte probabilité de collision (même hash). Inversement, des vecteurs éloignés ont une faible probabilité de collision.

Formalisation Mathématique

Une famille de fonctions de hachage H est dite locality-sensitive pour une distance d s'il existe des constantes r, cr, p₁, p₂ telles que pour toute paire de vecteurs x, y :

• Si d(x, y) ≤ r (vecteurs proches) → P[h(x) = h(y)] ≥ p₁ (haute collision)
• Si d(x, y) ≥ cr (vecteurs éloignés, c>1) → P[h(x) = h(y)] ≤ p₂ (faible collision)
• Où p₁ > p₂

Familles de fonctions de hachage

Selon la métrique de distance utilisée, différentes familles LSH existent :

Random projections

Pour la similarité cosinus (cas le plus fréquent pour les embeddings), LSH utilise la méthode des hyperplans aléatoires (Random Hyperplane Projection) :

Algorithme Random Hyperplane LSH

1. Génération des hyperplans : Tirer k vecteurs aléatoires w₁, ..., wₖ depuis une distribution gaussienne N(0,1)^d
2. Projection : Pour un vecteur x, calculer le produit scalaire avec chaque wᵢ : pᵢ = wᵢ · x
3. Binarisation : hᵢ(x) = 1 if pᵢ ≥ 0 else 0
4. Hash code : Concaténation des k bits : hash(x) = [h₁(x), h₂(x), ..., hₖ(x)] → entier de 0 à 2^k - 1

Intuition géométrique : Chaque hyperplan wᵢ partitionne l'espace vectoriel en deux demi-espaces (+/-). Avec k hyperplans, l'espace est découpé en 2^k régions. Les vecteurs proches ont forte probabilité d'être dans la même région → même hash.

Amplification avec Tables Multiples

Un seul ensemble de k hyperplans donne un recall faible (~60-80%). Pour l'améliorer, LSH utilise L tables de hash indépendantes avec différents hyperplans aléatoires :

• Construction : Générer L ensembles de k hyperplans, calculer L hash codes par vecteur
• Recherche : Hasher la requête avec les L tables, collecter tous les candidats des L buckets
• Trade-off : ↑ L augmente recall mais aussi le nombre de faux positifs (et donc latence)

Configuration typique : k=10-20 bits (1024-1M buckets), L=10-50 tables. Recall@10 = 85-95% selon paramètres.

Multi-probing et optimisations

LSH basique souffre d'un problème : un vecteur proche de la frontière d'un hyperplan peut être hashé dans un bucket adjacent. Multi-probing LSH résout cela en explorant plusieurs buckets voisins.

Stratégie Multi-Probing

1. Hash principal : Calculer le hash code normal de la requête → bucket principal
2. Buckets voisins : Générer des hash codes avec 1-3 bits flipés (distance de Hamming 1-3)
3. Exploration : Chercher dans le bucket principal + T buckets voisins (T=5-20)
4. Gain : Recall +10-20% pour même nombre de tables L

Autres Optimisations LSH

• Cross-polytope LSH : Utilise des polytopes réguliers au lieu d'hyperplans → meilleure distribution
• Data-dependent LSH : Apprend les projections depuis les données (au lieu d'aléatoire) → +5-10% recall
• Spherical LSH : Optimisé pour vecteurs normalisés (unit sphere)
• Asymmetric LSH : Hash asymétrique requête vs base pour réduire faux positifs

Avantages et limitations

Avantages de LSH

• Construction ultra-rapide : Pas de k-means ou construction de graphe, juste projection linéaire → 1-5 minutes pour 100M vecteurs
• Scalabilité théorique : Complexité sous-linéaire prouvable : O(n^(1/(1+ε)))
• Insertion dynamique triviale : Ajout d'un vecteur = calcul de L hash codes et insertion dans buckets (microseconde)
• Distribution facile : Tables indépendantes → sharding naturel sur plusieurs machines
• Empreinte mémoire : Seulement les hash codes + pointeurs (quelques bytes/vecteur)

Limitations de LSH

• Recall inférieur : Typiquement 85-92% vs 95-99% pour HNSW/IVF à latence comparable
• Tuning complexe : Choix de k et L est délicat et dataset-dependent
• Sensibilité dimensionnelle : Performance se dégrade significativement au-delà de 512-1024 dimensions (curse of dimensionality)
• Distribution de buckets : Certains buckets peuvent être sur-peuplés (power law), causant des hotspots
• Évolution technologique : Largement supplanté par HNSW/IVF dans les benchmarks récents (2020+)

Autres techniques d'indexation

Annoy (Approximate Nearest Neighbors Oh Yeah)

Développé par Spotify en 2013, Annoy est un algorithme basé sur des arbres de projection aléatoire (random projection trees). Annoy était très populaire avant l'avènement de HNSW grâce à sa simplicité et sa compatibilité mmap (memory-mapped files).

Principe de Fonctionnement

1. Construction des arbres : Création de n_trees arbres binaires indépendants (typiquement 10-100)
2. Partitionnement récursif : À chaque nœud, choisir 2 points aléatoires, tracer l'hyperplan médiateur, partitionner
3. Feuilles : Arrêt quand <K vecteurs dans un nœud (K=100-1000)
4. Recherche : Descendre dans chaque arbre jusqu'aux feuilles, agréger candidats, reranker

Caractéristiques

• Points forts :
  • Index statique optimisé (mmap = pas de chargement RAM)
  • Construction rapide (plus rapide que HNSW)
  • Empreinte mémoire faible
  • Implémentation simple (1500 lignes C++)
• Points faibles :
  • Recall inférieur à HNSW (-5 à -10%)
  • Pas d'insertion dynamique (rebuild complet nécessaire)
  • Performance se dégrade en haute dimension (>512)
• Use cases : Systèmes de recommandation musicale (Spotify), index statiques mis à jour quotidiennement/hebdomadairement

ScaNN (Scalable Nearest Neighbors)

Développé par Google Research en 2019, ScaNN combine plusieurs innovations pour atteindre un rapport recall/latence exceptionnellement bon, surpassant même HNSW dans certains benchmarks.

Innovations Clés de ScaNN

• Anisotropic Vector Quantization : Quantization qui préserve mieux les distances que PQ standard (+3-5% recall)
• Two-phase search :
  1. Phase 1 : Recherche grossière avec quantization agressive (recall 70-80%, très rapide)
  2. Phase 2 : Reranking sur top-N candidats avec vecteurs float32 (recall 98%+)
• SIMD optimization : Exploitation intensive des instructions vectorielles (AVX-512) pour calculs de distance
• Tree + quantization hybrid : Partitionnement hiérarchique + compression pour le meilleur des deux mondes

Performance

Sur le benchmark GLOVE-100 (1.2M vecteurs 100-dim), ScaNN atteint :

• Recall@10 = 99.0% en 0.3ms (vs HNSW : 98.5% en 0.5ms)
• Empreinte mémoire : 30-50% inférieure à HNSW grâce à quantization
• Construction : Plus rapide que HNSW grâce au tree-building parallélisé

NGT (Neighborhood Graph and Tree)

Développé par Yahoo Japan, NGT (Neighborhood Graph and Tree) combine graphes et arbres pour un équilibre construction/recherche.

Architecture Hybride

• ANNG (Approximate Nearest Neighbor Graph) : Graphe type HNSW mais avec heuristiques différentes
• ONNG (Optimized ANNG) : Variante avec pruning agressif des arêtes pour réduire mémoire
• QG (Quantized Graph) : Compression des vecteurs avec quantization
• Tree-based index : Alternative plus rapide à construire que graphe

Spécificités

• Optimisé pour CPUs Intel/AMD (pas GPU)
• Très performant sur datasets japonais (embeddings multilingues)
• Insertion dynamique supportée (mieux que Annoy, moins bien que HNSW)
• Documentation principalement en japonais (barrière adoption)

Position dans l'écosystème : NGT est une alternative solide à HNSW/FAISS, particulièrement en Asie, mais moins utilisé en Occident faute de communauté.

DiskANN pour données massives

Développé par Microsoft Research, DiskANN résout un problème crucial : comment indexer des milliards de vecteurs quand la RAM est insuffisante, en utilisant des SSD NVMe comme extension de mémoire.

Principe : Graph on Disk

1. Construction : Création d'un graphe HNSW-like optimisé pour accès SSD (minimiser I/O)
2. Graph layout : Organisation des nœuds sur disque pour maximiser locality (voisins proches physiquement)
3. Compressed vectors : Vecteurs compressés avec PQ stockés sur SSD
4. In-memory index : Petit index en RAM (5-10% du dataset) pour point d'entrée rapide
5. Beam search : Navigation dans le graphe avec prefetching I/O agressif

Performance

Use Cases DiskANN

Comparaison et benchmarks

Méthodologie de benchmark

Évaluer les algorithmes d'indexation vectorielle nécessite une méthodologie rigoureuse car les performances varient drastiquement selon le dataset, la dimensionnalité, et les paramètres. Voici le framework standard utilisé par ann-benchmarks.com et la communauté recherche.

Datasets de Référence

Métriques Évaluées

• Recall@k : Pourcentage des vrais k plus proches voisins retournés (métrique principale)
• Latence P95/P99 : Temps de réponse 95e/99e percentile (plus réaliste que moyenne)
• QPS : Queries per second en multi-threading
• Memory footprint : RAM consommée (index + vecteurs originaux si nécessaire)
• Build time : Temps de construction index (important pour re-indexation)
• Update throughput : Insertions/suppressions par seconde

Protocole Standardisé

1. Split train/test : 90% construction index, 10% requêtes test
2. Tuning paramètres : Grid search pour optimiser recall@10 = 95% ± 1%
3. Mesures multiples : 3-5 runs, report median + std deviation
4. Hardware fix : Machine AWS c5.4xlarge (16 vCPU, 32GB RAM) pour reproductibilité
5. Concurrence réaliste : Tests mono-thread ET multi-thread (8-16 threads)

Performance selon la taille du dataset

Les algorithmes d'indexation ont des profils de scalabilité très différents. Voici l'évolution des performances selon la taille N :

Analyse des Tendances

• HNSW : Excellent jusqu'à 10-50M, puis contrainte RAM devient prohibitive
• IVF-PQ : Scalabilité linéaire exceptionnelle, choix #1 pour 100M+ vecteurs
• LSH : Dégradation continue du recall (curse of dimensionality)
• DiskANN : Seule solution viable pour datasets multi-milliards

Précision (recall) vs latence

Le graphique recall vs latence est LA métrique de référence pour comparer algorithmes. Voici les résultats sur SIFT1M (1M vecteurs, 128 dim) :

Résultats Détaillés par Algorithme

Consommation mémoire

L'empreinte mémoire est souvent le facteur limitant en production. Voici la consommation pour 10M vecteurs 1024-dim (float32) :

Temps de construction de l'index

Le temps de construction impacte la fréquence de re-indexation possible et donc la fraîcheur des données. Mesures sur 10M vecteurs 1024-dim (16-core CPU) :

Tableau récapitulatif

Synthèse des algorithmes selon 6 critères principaux (note /10) :

Optimisation et tuning

Choisir l'algorithme selon vos contraintes

Le choix de l'algorithme d'indexation dépend de votre profil de contraintes. Utilisez cet arbre de décision pour identifier la solution optimale :

Arbre de Décision Algorithmique

Cas d'Usage Types et Recommandations

Tuning des hyperparamètres

L'optimisation des paramètres est cruciale pour atteindre les performances optimales. Voici une méthodologie systématique :

Méthodologie de Tuning

1. Baseline : Démarrer avec paramètres par défaut de la documentation
2. Objectif : Définir recall@k target (ex: 95%) et latence P95 limite (ex: 50ms)
3. Grid search : Tester combinaisons de paramètres sur sample représentatif
4. Validation : Mesurer sur dataset complet avec traffic patterns réalistes
5. Production : Déployer avec monitoring continu

Guide de Tuning par Algorithme

HNSW - Optimisation Détaillée

IVF-PQ - Optimisation Avancée

• nlist : Commencer par sqrt(N), ajuster selon distribution
  • Si clusters déséquilibrés : augmenter nlist
  • Si trop de clusters vides : réduire nlist
• nprobe : Équilibre recall/latence
  • Démarrer avec nprobe = nlist / 128
  • Doubler jusqu'à atteindre recall target
• PQ.m : Nombre de sous-espaces
  • Contrainte : dimension doit être divisible par m
  • Plus élevé = meilleur recall mais plus de mémoire
  • Sweet spot : m = dimension / 24

Stratégies hybrides

Les systèmes de production combinent souvent plusieurs techniques pour optimiser différents aspects. Voici les patterns les plus efficaces :

Hot/Cold Tiering

Principe : Séparer les données selon leur fréquence d'accès

• Tier Hot (20% des données, 80% du trafic) : HNSW en RAM pour latence minimale
• Tier Warm (60% des données, 18% du trafic) : IVF-PQ en RAM
• Tier Cold (20% des données, 2% du trafic) : DiskANN sur SSD

Multi-Index Serving

Utiliser plusieurs index différents pour le même dataset :

• Index principal : IVF-PQ pour 95% des requêtes (latence normale)
• Index backup : HNSW pour 5% des requêtes critiques (latence ultra-faible)
• Routing intelligent : Dispatcher basé sur priorité requête (temps réel vs batch)

Recherche en Cascade

Exécution séquentielle d'algorithmes de précision croissante :

1. Étape 1 : IVF-PQ rapide (recall 90%, 5ms) → top-100 candidats
2. Étape 2 : Reranking HNSW sur top-100 (recall 99%, +3ms) → top-10 final
3. Bénéfice : Combiner vitesse IVF + précision HNSW

Monitoring et métriques en production

Un système de recherche vectorielle en production doit être instrumenté pour détecter dégradations et optimiser continuellement.

Métriques Clés à Tracker

Monitoring Avancé : Drift Detection

Les embeddings peuvent dériver avec le temps (concept drift), dégradant la qualité de recherche :

• Distribution monitoring : Tracker moyenne/variance des embeddings par batch
• Cluster drift : Pour IVF, surveiller l'équilibre des clusters (coefficient Gini)
• Query patterns : Détecter changements dans distribution des requêtes
• Semantic coherence : Évaluer périodiquement sur jeu de test semantique

Quand réindexer ?

La réindexation est coûteuse mais parfois nécessaire. Voici les triggers et stratégies :

Triggers de Réindexation

Stratégies de Réindexation

• Blue-Green Deployment :
  • Construire nouvel index en parallèle ("green")
  • Une fois prêt, switcher le trafic atomiquement
  • Conserver ancien index ("blue") pour rollback rapide
• Incremental Reindexing :
  • Pour algorithmes supportant updates (HNSW)
  • Réindexer par batches de 10-100K vecteurs
  • Plus complexe mais zéro downtime
• Sharded Reindexing :
  • Réindexer un shard à la fois
  • Trafic redirigé sur shards sains temporairement
  • Scalabilité linéaire mais capacité réduite temporairement