Arrêt précoce adaptatif pour HNSW dans Elasticsearch

Elasticsearch utilise l'algorithme Hierarchical Navigable Small World (HNSW) pour effectuer une recherche vectorielle sur un graphe de proximité. HNSW est reconnu pour offrir un bon compromis entre la qualité des résultats des k plus proches voisins (kNN) et le coût associé.

Dans HNSW, la recherche s'effectue par expansion itérative des nodes candidats dans le graphe, en conservant un ensemble limité des voisins les plus proches découverts jusqu'à présent. Chaque expansion a un coût (opérations vectorielles, recherches aléatoires sur disque, etc.), et le bénéfice marginal de ce coût tend à diminuer à mesure que la recherche progresse.

Une façon d'optimiser le parcours du graphe HNSW est d'interrompre la recherche lorsque la probabilité marginale de trouver de nouveaux les plus proches n'augmente plus. C'est pourquoi, dans Elasticsearch 9.2, nous avons introduit un nouveau mécanisme d'arrêt précoce. Ce mécanisme interrompt la recherche lorsque la visite des nodes du graphe ne fournit pas suffisamment de nouveaux voisins les plus proches, de façon consécutive, pendant un nombre déterminé de fois.

Cet article explique comment nous avons amélioré le mécanisme mentionné d'arrêt précoce dans HNSW afin de mieux l'adapter à différents ensembles de données et distributions de données.

Arrêt précoce dans HNSW

Dans HNSW, la recherche se déroule en étendant itérativement les nodes candidats dans le graphe de proximité, en conservant un ensemble limité des voisins les plus proches découverts jusqu'à présent, jusqu'à avoir exploré l'ensemble du graphe ou répondu à certains critères d'arrêt précoce.

L'arrêt précoce n'est donc pas toujours une optimisation ; il fait partie intégrante de l'algorithme de recherche lui-même. Le moment où nous décidons d'interrompre la recherche détermine l'équilibre entre l'efficacité et le rappel. Dans Elasticsearch, il existe déjà plusieurs façons d'interrompre prématurément une requête sur HNSW :

• Un nombre maximal déterminé de nodes est exploré.
• Un délai d'expiration déterminé est atteint.

Bien que simples et prévisibles, ces règles sont largement indépendantes de ce qu'effectue réellement la recherche. De plus, elles servent principalement à garantir que la requête se termine dans un délai raisonnable pour l'utilisateur final.

Dans un article de blog précédent, nous avons introduit le concept de redondance dans HNSW. En bref, les calculs redondants se produisent lorsque HNSW continue d'évaluer de nouveaux nodes candidats qui ne permettent pas de trouver davantage de voisins les plus proches.

Patience : mesurer les progrès plutôt que les efforts

La notion de patience recadre l'arrêt précoce sur le progrès plutôt que sur l'effort.

Au lieu de demander :

"Combien d'étapes avons-nous franchies ?"

La nouvelle question devient :

« Quelle est la quantité de calcul que nous acceptons de gaspiller, jusqu'à ce que nous perdions espoir ? »

Lors d'une recherche HNSW, l'exploration précoce génère généralement des améliorations maximales de l'ensemble des k meilleurs candidats. Au cours des premières étapes de l'exploration du graphe HNSW, l'ensemble des voisins est mis à jour en continu à mesure que l'algorithme découvre des voisins de plus en plus proches du vecteur de requête. Avec le temps, ces améliorations deviennent plus rares à mesure que la recherche converge. L'arrêt basé sur la patience surveille ce schéma et interrompt la recherche lorsque les améliorations cessent de se produire pendant une période prolongée.

En pratique, lors de l'exploration du graphe HNSW, nous calculons également le taux de saturation de la file d'attente à chaque étape du parcours des nodes candidats. Ce taux mesure le pourcentage de voisins les plus proches restés inchangés lors de la visite du dernier node du graphe (ou l'inverse du nombre de nouveaux voisins introduits lors de la dernière itération). Si ce taux devient trop élevé pendant plusieurs itérations consécutives, l'exploration du graphe est interrompue.

D'un point de vue conceptuel, la patience considère la recherche HNSW comme un processus à rendements décroissants. Lorsque les rendements se stabilisent, continuer à explorer le graphe apporte peu d'avantages.

Ce recadrage est puissant car il lie directement l'arrêt aux résultats observables plutôt qu'à des limites fixes arbitraires.

L'avantage de cette technique d'arrêt précoce intelligent est que les explorations de graphes HNSW ont tendance à visiter un nombre plus restreint de nodes tout en conservant un rappel relatif quasi parfait.

Pour visualiser cela, nous pouvons tracer le nombre de rappels par node visité que nous avons obtenus avec l'arrêt précoce basé sur la patience (étiqueté et=static), par rapport au comportement par défaut du HNSW (étiqueté et=no) sur quelques ensembles de données, FinancialQA et Quora, ainsi que des modèles JinaV3 et E5-small.

Seuils statiques et dynamiques HNSW

Dans Elasticsearch, cela se traduit concrètement par l'utilisation de seuils statiques. Le premier seuil correspond au seuil de saturation, c'est-à-dire le niveau de saturation que nous considérons comme sous-optimal. Le second seuil correspond au nombre de nodes consécutifs du graphe pouvant être visités tout en maintenant une saturation de la file d'attente sous-optimale, soit le seuil de patience.

Lors de l'introduction de cette stratégie d'arrêt précoce dans Elasticsearch 9.2, nous avons opté pour des valeurs par défaut prudentes afin de maximiser le rappel tout en optimisant la latence et la consommation de mémoire. C'est pourquoi nous avons fixé le seuil de saturation à 100 % et le seuil de patience à 30 % (limité) de la valeur de num_candidates dans la requête KNN.

Dans de nombreux cas, ces paramètres ont donné de bons résultats. Cependant, deux requêtes demandant le même nombre de voisins peuvent avoir des comportements de convergence radicalement différents. Certaines requêtes rencontrent des voisinages locaux denses et saturent rapidement ; d'autres doivent parcourir de longs chemins épars avant de trouver des candidats compétitifs. Ces dernières se sont avérées les plus difficiles à gérer efficacement.

De ce fait, nous avons parfois constaté :

• Une surexploration pour les requêtes simples.
• Un arrêt prématuré pour les requêtes complexes.

Nous avons donc estimé que les valeurs de seuil déterminées codifiaient des hypothèses globales sur la convergence, alors que nous pouvions mieux adapter le HNSW à différentes dynamiques.

Rendre l'arrêt précoce de HNSW adaptatif

L'arrêt précoce adaptatif aborde ce problème sous un angle différent. Au lieu d'imposer des seuils d'arrêt prédéfinis, l'algorithme détermine le moment où il doit s'arrêter à partir de la dynamique de recherche elle-même.

Ainsi, au lieu de comparer le taux de saturation de la file d'attente entre deux candidats consécutifs, nous avons décidé d'introduire à la fois un taux de découverte lissé instantané $d_{q,i}$ (combien de nouveaux voisins ont été introduits pour une requête q lors de la dernière visite i), ainsi qu'une moyenne glissante $\mu_{q,i}$ et un écart-type $\sigma_{q,i}$ d'un tel taux de découverte pendant la visite du graphe (en utilisant l'algorithme de Welford). Ces statistiques sur le taux de découverte sont calculées par requête, permettant ainsi de déterminer différents niveaux de patience pour chacune d'entre elles.

Les seuils auparavant statiques deviennent adaptatifs aux statistiques du taux de découverte : le seuil de saturation devient la moyenne mobile plus l'écart type, tandis que nous faisons en sorte que la patience s'adapte et évolue inversement avec l'écart type.

Les règles de sortie précoce restent les mêmes ; la saturation survient lorsque le taux de découverte instantané est inférieur au seuil de saturation adaptatif. La visite du graphe s'arrête si la saturation persiste pendant un nombre d'explorations de candidats consécutives supérieur au seuil de patience adaptatif.

De cette façon, nous obtenons un comportement qui ne dépend pas du paramètre num_candidates dans la requête KNN (qui peut toujours être défini ou laissé par défaut, indépendamment d'une sortie anticipée) et qui s'adapte mieux à chaque requête et distribution vectorielle de manière dynamique.

Le rappel par node visité sur FinancialQA et Quora avec la stratégie adaptative (étiquetée et=adaptive) indique un rappel plus élevé par node visité, par rapport à la stratégie statique (et=static) et au comportement par défaut de HNSW (et=no).

L'arrêt précoce adaptatif est activé par défaut dans Elasticsearch 9.3 pour les champs vectoriels denses HNSW (et peut éventuellement être désactivé via le même paramètre de niveau d'index).