🤖 machine learning

Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

Cet article présente une analyse systématique de la recherche ANN basée sur des grilles à sondes multiples, révélant sa supériorité en matière de scalabilité dans les hautes dimensions et de coûts d'indexation moindres par rapport aux méthodes de graphes, d'arbres et de partitionnement, suggérant ainsi son potentiel pour optimiser les applications nécessitant des reconstructions fréquentes et les architectures de transformeurs efficaces.

Auteurs originaux : Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

Publié 2026-07-03

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La vue d'ensemble : Trouver une aiguille dans une botte de foin croissante et mouvante

Imaginez que vous cherchez une aiguille spécifique dans une botte de foin.

L'Aiguille : La réponse exacte que vous recherchez (le « plus proche voisin »).
La Botte de foin : Une collection massive de points de données (comme des millions de mots ou d'images).
Le Problème : À mesure que la botte de foin s'agrandit (plus de données) ou que les aiguilles deviennent plus complexes (dimensions plus élevées), trouver cette aiguille spécifique devient incroyablement lent et difficile.

Cet article présente une nouvelle façon, de type « vieille école », de trouver des aiguilles appelée « Multiprobe Grid Search » (Recherche par grille multiprobe). Les auteurs ont testé cette méthode contre les outils modernes et de haute technologie que tout le monde utilise (comme les systèmes basés sur les graphes ou les arbres) et ont découvert quelque chose de surprenant : les méthodes basées sur les grilles sont en réalité très performantes lorsque les données deviennent énormes ou très complexes.

L'analogie : Le supermarché vs Le labyrinthe

Pour comprendre la différence entre les méthodes, utilisons deux analogies :

1. Les méthodes modernes (Graphes et Arbres) : Le labyrinthe complexe
Les méthodes populaires actuelles sont comme un labyrinthe complexe à plusieurs niveaux. Pour trouver une aiguille, vous devez suivre un chemin sinueux à travers le labyrinthe.

Le piège : À mesure que le labyrinthe s'agrandit (plus de données) ou que les murs deviennent plus déroutants (dimensions plus élevées), le chemin devient plus long et plus emmêlé. Vous passez beaucoup de temps à faire marche arrière et à vous perdre. L'article a constaté qu'à mesure que les données deviennent plus complexes, ces « marcheurs de labyrinthe » ralentissent considérablement.

2. La nouvelle méthode (Grille Multiprobe) : Le supermarché organisé
La méthode de cet article est comme un supermarché parfaitement organisé.

Comment ça marche : Au lieu d'un labyrinthe, le magasin est divisé en allées carrées simples (une grille).
L'astuce : Quand vous voulez trouver un article, vous ne vérifiez pas seulement l'allée où vous pensez qu'il se trouve. Vous vérifiez cette allée, plus les allées immédiatement adjacentes, et celles qui sont à côté de celles-ci. C'est ce qu'on appelle le « multiprobe ».
La recette secrète : Pour décider quelles allées vérifier, le système utilise une carte simplifiée (une « projection PCA ») qui ignore certains détails déroutants. Il ne regarde que la disposition principale. Une fois qu'il a choisi les bonnes allées, il effectue une vérification finale rapide dans le monde réel et détaillé.

Ce que l'article a découvert

Les auteurs ont mené des expériences pour voir comment la vitesse de ces méthodes change en fonction de deux facteurs : la taille des données et la complexité des données.

1. Le test de la « Taille » (Plus de bottes de foin)

Le montage : Ils ont doublé et triplé la quantité de données.
Le résultat : La méthode du « Supermarché » (Grille) a ralenti de manière presque parfaitement proportionnelle à la taille. Si vous doublez les données, cela prend environ le double de temps. C'est ce qu'on appelle une mise à l'échelle quasi linéaire.
Les concurrents : Les méthodes du « Labyrinthe » ont ralenti beaucoup moins que prévu au début, mais à mesure que les données devenaient énormes, elles ont commencé à éprouver plus de difficultés que la méthode de la Grille.
À retenir : La méthode de la Grille est très prévisible et honnête sur le temps dont elle a besoin à mesure que les données croissent.

2. Le test de la « Complexité » (Le croisement des dimensions)

Le montage : Ils ont rendu les données plus complexes (en ajoutant plus de caractéristiques, comme passer d'un dessin en 2D à un modèle en 3D, puis à un modèle en 100D).
La surprise : C'est la plus grande découverte de l'article.
- Les méthodes du « Labyrinthe » (Graphes/Arbres) sont devenues beaucoup plus lentes à mesure que la complexité augmentait. Plus les données étaient complexes, plus il était difficile pour elles d'élaguer (ignorer) les mauvais chemins.
- La méthode du « Supermarché » (Grille) est restée stable. Parce qu'elle utilise une carte simplifiée pour décider quelles allées vérifier, elle n'est pas déroutée par la complexité supplémentaire.
Le croisement : À un certain niveau de complexité, la méthode de la Grille est devenue plus rapide que les méthodes modernes du Labyrinthe. L'article appelle cela un « croisement » (crossover).

3. Le coût de configuration (Construire le magasin)

Le montage : Combien de temps faut-il pour construire l'index (installer les étagères) avant de pouvoir commencer la recherche ?
Le résultat : La méthode de la Grille est incroyablement rapide à configurer. La méthode de la Grille a mis 4 à 36 secondes pour organiser un million d'éléments. Les méthodes modernes du Labyrinthe ont pris des minutes, voire plus de 25 minutes.
Pourquoi c'est important : Si vous avez un système où vous jetez constamment d'anciennes données et construisez un nouvel index à partir de zéro (comme un système de recommandation qui se met à jour toutes les heures), la méthode de la Grille est gagnante car elle se construit très vite.

L'équation du « Coût Total »

L'article soutient que vous ne devriez pas regarder uniquement la vitesse d'une recherche pendant la recherche. Vous devez regarder le Coût Total :

Coût Total = (Temps de Construction) + (Temps de Recherche × Fréquence de Recherche)

Scénario A : Vous construisez l'index une fois et vous effectuez un million de recherches. Les méthodes du Labyrinthe, lentes à construire, pourraient gagner car elles sont rapides à utiliser pour la recherche.
Scénario B : Vous construisez l'index souvent (reconstruction fréquente) ou vous effectuez peu de recherches. La méthode de la Grille gagne car elle est si peu coûteuse et rapide à construire.

Pourquoi cela importe pour l'IA (La connexion avec l'« Attention »)

L'article mentionne que l'IA moderne (Transformers) fonctionne en effectuant des recherches de « plus proche voisin approximatif » pour décider quels mots doivent recevoir l'« attention ».

Si un modèle d'IA doit constamment mettre à jour sa mémoire (index) à mesure que de nouveaux mots arrivent, la faible vitesse de configuration et la capacité de la méthode de la Grille à gérer des données complexes sans ralentir pourraient rendre l'IA plus rapide et moins coûteuse à exploiter.

Résumé

L'article dit : « Ne négligez pas la grille simple. »
Alors que tout le monde est obsédé par les méthodes de recherche complexes, semblables à des labyrinthes, l'approche de la « Grille Multiprobe » (le Supermarché organisé) est en fait meilleure pour gérer :

Des ensembles de données énormes (vitesse prévisible).
Des données très complexes (elle n'est pas déroutée par les hautes dimensions).
Des reconstructions fréquentes (elle s'installe en quelques secondes, pas en minutes).

C'est un rappel que parfois, la méthode « vieille école », lorsqu'elle est ajustée correctement, est l'outil le plus efficace pour la tâche.

Résumé technique : Lois d'échelle pour la recherche de plus proches voisins approximatifs basée sur une grille en haute dimension

Énoncé du problème

La recherche de plus proches voisins approximatifs (ANN) est une primitive fondamentale dans l'apprentissage automatique moderne, servant à la fois les tâches de recherche traditionnelles et des rôles émergents en tant que bloc de construction computationnel pour les architectures transformer (où l'auto-attention est formalisée comme une opération ANN). Alors que les lois d'échelle empiriques guident la conception de modèles à grande échelle, le comportement d'échelle des algorithmes ANN par rapport à la taille de l'ensemble de données ( $N$ ) et à la dimensionnalité ( $d$ ) reste un domaine d'étude critique, bien que sous-caractérisé.

La littérature existante a analysé de manière approfondie les méthodes basées sur les graphes (ex: HNSW), les arbres et le partitionnement. Cependant, les approches basées sur des grilles, malgré leur rôle fondamental dans la théorie précoce de l'ANN, ont été largement absentes des analyses d'échelle modernes. Cet article comble cette lacune en caractérisant systématiquement la dynamique d'échelle d'un algorithme de grille multiprobe, en étudiant spécifiquement comment ses performances évoluent avec $N$ et $d$ par rapport aux concurrents de pointe.

Méthodologie

L'algorithme de grille multiprobe

Les auteurs proposent un algorithme de grille multiprobe qui découple la sélection des cellules de la dimensionnalité complète $d$ . Le flux de travail implique :

Projection PCA : Les points de données sont projetés de $\mathbb{R}^d$ vers un sous-espace de dimension inférieure $\mathbb{R}^m$ ( $m \ll d$ ).
Partitionnement en grille : Le sous-espace est partitionné en une grille uniforme de $G^m$ cellules.
Sélection multiprobe : Lors de la requête, l'algorithme identifie la cellule "domicile" et sonde jusqu'à $2^m - 1$ cellules voisines, ordonnées par leur distance murale au carré ( $w_i^2$ ) par rapport à la requête.
Re-classement (Re-ranking) : Les candidats collectés des cellules sondées sont re-classés dans l'espace de haute dimension d'origine $\mathbb{R}^d$ .

Modèle théorique

Les auteurs dérivent une relation en forme close entre le coût de requête (Requêtes Par Seconde, QPS) et le rappel ( $R$ ).

Modèle de coût : Le coût de la requête est linéaire dans le nombre de cellules sondées ( $n_{probe}$ ) et le nombre de points par cellule ( $N/G^m$ ).
Modèle de rappel : En supposant une distribution uniforme, la probabilité que le plus proche voisin réel se trouve dans une cellule sondée décroît exponentiellement avec la distance murale.
Relation résultante : Le modèle prédit une relation log-linéaire entre le QPS et le rappel : $\log(\text{QPS}) \approx \log(\text{const}) - \log(R)$ . Cela découle de la décroissance exponentielle de la probabilité d'appartenance à travers les cellules et de la croissance linéaire de la taille de l'ensemble de candidats.

Évaluation empirique

L'étude évalue la grille multiprobe contre quatre bases de référence représentant les principales familles d'ANN :

Basées sur les graphes : Voyager, PyNNDescent.
Basées sur les arbres : Annoy.
Partitionnement/Quantification : FAISS-IVF.

Les expériences ont été menées à l'aide du framework ann-benchmarks sur deux ensembles de données :

GloVe-200-angular (Embeddings de mots, $d=200$ , $N \approx 1.18 \times 10^6$ ).
SIFT-128-euclidean (Descripteurs d'images, $d=128$ ).

L'évaluation s'est concentrée sur les exposants d'échelle pour $N$ ( $\alpha_N$ ) et $d$ ( $\alpha_d$ ), les fronts de Pareto (débit vs rappel) et l'analyse du coût total.

Résultats clés

1. Relation débit-rappel log-linéaire

L'analyse du front de Pareto sur GloVe-200 confirme la prédiction théorique : la grille multiprobe présente une diminution log-linéaire du débit à mesure que le rappel augmente. Ce comportement est distinct de celui des bases de référence et est piloté par la géométrie de la grille et la décroissance exponentielle de la probabilité d'appartenance du plus proche voisin.

2. Échelle en $N$ : Dégradation quasi-linéaire

La grille multiprobe évolue de manière quasi-linéaire avec la taille de l'ensemble de données ( $N$ ).

À un rappel@10 = 0.80, l'exposant d'échelle est $\alpha_N \approx -0.94$ (GloVe) et $-0.83$ (SIFT).
En revanche, les bases de référence basées sur les graphes et les arbres présentent une évolution sous-linéaire ( $\alpha_N$ allant de $-0.44 $à$ -0.59$).
Implication : Bien que le débit de la grille multiprobe se dégrade plus rapidement à mesure que $N$ croît par rapport aux méthodes de graphes, il s'agit d'une conséquence mécaniste de la conception de l'algorithme (le nombre de candidats croît linéairement avec $N$ ).

3. Échelle en $d$ : Un croisement critique

Un croisement d'échelle en $d$ (d-scaling crossover) jusqu'alors non rapporté est observé sur la famille d'embeddings GloVe.

Bases de référence : À mesure que la dimensionnalité $d$ augmente, le débit des méthodes de graphes, d'arbres et de partitionnement se dégrade significativement ( $\alpha_d$ élevé), reflétant la "malédiction de la dimensionnalité" et l'échec du élagage géométrique en hautes dimensions.
Grille multiprobe : L'exposant d'échelle $\alpha_d$ reste relativement plat et favorable à mesure que $d$ augmente.
Mécanisme : En effectuant la sélection des cellules dans un sous-espace PCA de faible dimension ( $m \ll d$ ) et en adaptant les paramètres de la grille ( $m, G$ ) en fonction de $d$ et du rappel cible, l'algorithme évite de traverser tout l'espace de haute dimension. Les coûts de re-classement croissent seulement linéairement avec le nombre de candidats, ce qui est moins agressif que la croissance du coût des méthodes traversant l'espace complet de dimension $d$ .

4. Coût total et efficacité d'indexation

L'article analyse le coût total $J(N) = f_I \cdot I(N) + f_C \cdot C(N) + M(N)$ , où $I$ est le coût d'indexation, $C$ le coût de calcul et $M$ l'empreinte mémoire.

Vitesse d'indexation : La grille multiprobe est nettement plus rapide à construire que les bases de référence. Pour $N = 1.18 \times 10^6$ , elle construit un index en 4 à 36 secondes, contre 1 569 secondes pour Voyager.
Latence de requête : La grille multiprobe a une latence par requête plus élevée (environ 120 fois plus lente que Voyager à haut rappel).
Régime compétitif : La méthode devient compétitive lorsque le ratio reconstruction-requête ( $f_I/f_C$ ) est élevé. Plus précisément, si un index est reconstruit environ une fois tous les 2 600 à 20 400 requêtes, la grille multiprobe offre un coût total inférieur. Cela la rend adaptée aux scénarios de type "reconstruction intensive".

Signification et affirmations

L'article affirme que les méthodes basées sur les grilles, souvent négligées dans les analyses d'échelle modernes, offrent un ensemble distinct et compétitif de compromis dans des contextes spécifiques :

Robustesse dimensionnelle : La grille multiprobe est exceptionnellement robuste à l'augmentation de la dimensionnalité ( $d$ ), surpassant les méthodes de graphes et d'arbres dans les contextes de haute dimension où l'élagage géométrique échoue.
Faible surcharge d'indexation : L'algorithme offre une indexation quasi instantanée par rapport aux méthodes de graphes qui nécessitent une construction de graphe complexe et dépendante des données.
Pertinence pour les Transformers : Étant donné la formalisation de l'auto-attention comme une opération ANN, les propriétés d'échelle en $N$ $N$ et $d$ $d$ des algorithmes ANN sont directement pertinentes pour l'efficacité des transformers. Les auteurs suggèrent que la grille multiprobe peut être avantageuse dans les architectures transformer où :
- La longueur du contexte ( $N$ ) ou la dimension de la tête ( $d$ ) varie.
- Les mises à jour incrémentielles sont fréquentes (ex: extension du cache KV), car l'ajout d'un jeton à une grille nécessite seulement une assignation de cellule plutôt qu'une reconstruction complète du graphe.
Perspective du coût total : L'article soutient que la sélection d'une méthode ANN ne doit pas reposer uniquement sur la latence de requête, mais doit considérer la fonction de coût total, incluant la fréquence d'indexation et les coûts de reconstruction. Dans les scénarios de reconstruction fréquente, le faible coût d'indexation des méthodes de grille peut compenser leur latence de requête plus élevée.

En résumé, ce travail rétablit les méthodes basées sur les grilles comme une option viable pour les systèmes d'apprentissage de haute dimension, particulièrement là où l'indice de coût d'indexation, la fréquence de reconstruction et la robustesse dimensionnelle sont les contraintes primaires.