KNN early termination in Manticore Search
Les moteurs de recherche modernes convertissent requêtes et documents en vecteurs et Manticore utilise HNSW pour retrouver rapidement les voisins les plus proches, mais l'algorithme effectue beaucoup de calculs inutiles une fois que l'ensemble de résultats a convergé. L'arrêt anticipé détecte cette convergence en suivant le taux de découvertes (la fraction des calculs de distance qui améliorent l'ensemble de résultats) et stoppe la traversée quand ce taux reste sous un seuil adaptatif basé sur un quantile des rounds récents, avec un mécanisme de patience et une phase de warm‑up. Les seuils ont été calibrés pour limiter la perte de précision à 2–4 %, et des benchmarks sur 1M de vecteurs montrent que les calculs de distance diminuent fortement avec k élevé (par exemple ≈65 % de visites à k=60, ≈30 % à k=1000 et ≈20 % à k=10000), avec des gains accrus en présence de quantification et d'oversampling. En pratique l'arrêt anticipé réduit aussi la latence, surtout sous charge concurrente, parce qu'il diminue la pression sur le cache et la bande passante mémoire, entraînant par exemple des améliorations de latence d'environ 24 % en mono‑thread jusqu'à ≈48 % à 16 threads pour k=1000. La fonctionnalité est activée par défaut (désactivée automatiquement pour k ≤ 10) et peut être désactivée si l'on exige une précision maximale, pour de petits k ou pour des benchmarks de rappel, et elle s'additionne avantageusement à d'autres optimisations comme le préfiltrage, l'oversampling et le rescoring.