Contexte et enjeux
Maximum inner product search (MIPS) constitue le moteur des systèmes de recommandation, de recherche et de génération augmentée par récupération (RAG). Dans les déploiements réels, la base de clés atteint des millions d'éléments et chaque vecteur possède des milliers de dimensions. La comparaison exhaustive entre la requête et l’ensemble des clés devient alors prohibitive en temps de calcul.
Les méthodes approximatives classiques s’appuient sur le clustering ou la quantisation pour réduire le nombre de comparaisons. Elles supposent implicitement que la distribution des requêtes ressemble à celle des clés, ce qui n’est pas le cas en RAG où les requêtes sont de courtes questions tandis que les clés sont de longs documents curés.
Approche proposée
Dans l’article Amortizing Maximum Inner product Search with Learned Support Functions, présenté à ICML 2026, les chercheurs d’Apple entraînent de petits réseaux neuronaux hors ligne sur une base de clés fixe. Deux architectures sont introduites : SupportNet, un ICNN (input convex neural network) qui approxime la fonction de support du jeu de clés, et KeyNet, qui prédit directement le vecteur clé optimal.
La fonction de support, définie en analyse convexe, est convexe et son gradient renvoie le meilleur vecteur clé. En régressant sur un jeu d’entraînement constitué de paires (requête, score optimal ou vecteur clé), les réseaux apprennent à reproduire ce comportement à moindre coût.
Analyse des mécanismes
Un système MIPS typique segmente les n clés en k clusters (k ≪ n) et compare la requête aux k centroïdes. Cette étape réduit le nombre de comparaisons à l’ordre de n/k, soit un gain de vitesse proportionnel à k. Cependant, le routage basé sur les centroïdes est approximatif : un vecteur clé éloigné du centroïde mais proche de la requête peut être exclu, entraînant des erreurs de routage.
En apprenant la fonction de support de chaque cluster, SupportNet fournit k scores exacts au lieu de simples distances centroïdes. Le routage s’effectue alors en sélectionnant le score maximal, garantissant que le cluster contenant le meilleur vecteur clé est choisi. KeyNet, quant à lui, utilise une perte de cohérence dérivée du théorème d’Euler pour les fonctions homogènes, assurant que les prédictions restent ancrées dans la géométrie du problème même sans contrainte de convexité explicite.
Implications et limites
L’amortissement du coût d’entraînement permet de déplacer la charge computationnelle hors ligne et d’obtenir un temps d’inférence nettement inférieur à celui des méthodes basées uniquement sur les centroïdes. La dépendance à une distribution de requêtes pré‑définie implique toutefois que le modèle doit être ré‑entraîné si le profil d’utilisation évolue, ce qui peut limiter la flexibilité dans des environnements à requêtes très dynamiques.
En l’absence de mesures chiffrées dans la publication, l’efficacité reste quantifiée uniquement par le facteur k et par la capacité du réseau à reproduire la fonction de support. Des évaluations supplémentaires sur des jeux de données publics seraient nécessaires pour établir des gains de précision et de latence comparables aux approches de quantisation existantes.
