💻 computer science

Relation Reasoning with LLMs in Expensive Optimization

Ce papier présente R2SAEA, un nouvel algorithme évolutionnaire assisté par un modèle de substitution qui exploite un grand modèle de langage entraîné par renforcement pour effectuer un raisonnement efficace basé sur les relations en zéro-shot pour des problèmes d'optimisation coûteux, surmontant ainsi la surcharge de réentraînement des modèles de substitution traditionnels et atteignant des performances de l'état de l'art.

Auteurs originaux : Ye Lu, Bingdong Li, Aimin Zhou, Hao Hao

Publié 2026-05-06

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ye Lu, Bingdong Li, Aimin Zhou, Hao Hao

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

Imaginez que vous essayez de trouver la meilleure route à travers une immense chaîne de montagnes enveloppée de brouillard. Le problème est que vérifier l'altitude d'un seul endroit prend une journée entière de randonnée (c'est ce que l'article appelle une « évaluation coûteuse »). Vous disposez d'un nombre limité de jours (un budget serré), vous ne pouvez donc pas simplement randonner partout.

Traditionnellement, les scientifiques utilisent des « cartes » (des modèles mathématiques) pour deviner où se trouvent les points bas. Mais ces cartes sont trompeuses : à mesure que vous explorez de nouvelles zones, les anciennes cartes deviennent inutiles, et vous devez passer un temps précieux à les redessiner à partir de zéro. C'est le goulot d'étranglement que l'article tente de résoudre.

Voici la solution proposée par l'article, décomposée en concepts simples :

1. La nouvelle « carte » : Un juge intelligent plutôt qu'un calculateur

Au lieu d'essayer de prédire l'altitude exacte d'un endroit (ce qui est difficile et nécessite un redessin constant), les auteurs enseignent à une IA d'agir comme un juge dans un match de boxe.

Ancienne méthode : L'IA tente de deviner le score exact de chaque combattant.
Nouvelle méthode (R2SAEA) : L'IA ne regarde que deux combattants à la fois et répond à une question simple : « Le Combattant A est-il meilleur que le Combattant B ? »

Ceci est appelé le raisonnement relationnel. Puisque les algorithmes évolutionnaires (la méthode de recherche) se soucient principalement de savoir quelle option est meilleure qu'une autre, et non des chiffres exacts, cette approche de « juge » est beaucoup plus efficace.

2. L'astuce de l'« Ancre » : Éviter la surcharge de la bibliothèque

Si vous avez 100 randonneurs et que vous voulez savoir comment chacun se compare à tous les autres, vous devriez demander au juge environ 10 000 paires. C'est trop de questions pour que l'IA puisse les traiter à la fois (elle manquerait de « mémoire » ou de contexte).

Les auteurs ont inventé une stratégie d'« Ancre » :

Au lieu de demander à tout le monde en même temps, ils choisissent un randonneur comme « Ancre » (le point de référence).
Ils demandent à l'IA : « Comment le Randonneur A se compare-t-il à l'Ancre ? Comment le Randonneur B se compare-t-il à l'Ancre ? Comment le Randonneur C se compare-t-il à l'Ancre ? »
Ils font cela pour chaque randonneur, un par un.
Le résultat : Cela transforme un énorme tas confus de questions en une série de petites listes gérables. C'est comme demander à un professeur de noter une classe en comparant chaque élève à la « moyenne de la classe » un par un, plutôt que d'essayer de comparer chaque élève à tous les autres simultanément.

3. Le système de « vote » : Transformer les opinions en un score

Après que l'IA a jugé toutes les paires, elle possède un tas d'opinions « Meilleur/Pire ». Comment choisir le meilleur randonneur ?

Le système utilise un mécanisme de vote.
Si l'IA dit « Le Randonneur X est meilleur que 90 % des Ancres », le Randonneur X obtient un score élevé.
Si le Randonneur X est pire que la plupart, il obtient un score faible.
Cela convertit les « opinions » de l'IA en un classement clair, afin que l'algorithme de recherche sache exactement quels randonneurs envoyer pour la vérification réelle et coûteuse.

4. Entraîner le juge : L'apprentissage par renforcement (Le « Coach »)

Les auteurs n'ont pas simplement utilisé une IA générique ; ils ont entraîné une IA spécifique (basée sur un modèle appelé Qwen2.5) pour être un juge maître.

Ils ont créé un « Coach » (Apprentissage par renforcement) qui a observé l'IA faire des hypothèses.
Si l'IA devinait correctement la relation, le Coach accordait une récompense. Si elle se trompait, elle recevait une pénalité.
Avec le temps, l'IA a appris à repérer les différences subtiles entre les solutions bien mieux qu'une IA générique ne l'aurait pu.
La magie : Une fois entraînée, cette IA n'a pas besoin d'être réentraînée tous les jours. Elle peut simplement « réfléchir » (inférer) sur le vif. Cela économise énormément de temps et d'argent.

5. Le juge « de poche » : Fonctionnement sur de petits appareils

Habituellement, les IA puissantes nécessitent d'énormes superordinateurs coûteux. Les auteurs ont montré qu'en réduisant la taille du modèle et en compressant son « cerveau » (un processus appelé quantification), ce juge intelligent peut fonctionner sur de petits appareils portables comme un ordinateur portable haut de gamme ou même une puce spécialisée utilisée dans des drones ou des robots (appareils périphériques).

La conclusion

L'article affirme qu'en transformant le problème en une série de simples comparaisons « A contre B », en utilisant une méthode d'« Ancre » astucieuse pour maintenir les questions gérables, et en entraînant un juge IA spécialisé, ils peuvent trouver les meilleures solutions à des problèmes difficiles en utilisant beaucoup moins de tests coûteux que les méthodes précédentes.

C'est plus rapide : Pas besoin de redessiner la carte à chaque fois.
C'est moins cher : L'IA peut fonctionner sur du matériel plus petit et moins coûteux.
C'est plus efficace : Dans les tests, cette méthode a trouvé de meilleures solutions que d'autres méthodes de premier plan, tant pour les problèmes à objectif unique que pour les problèmes multi-objectifs.

Les auteurs ont rendu leur « juge intelligent » et le code disponibles pour que d'autres puissent les utiliser, prouvant que vous n'avez pas besoin d'un superordinateur pour résoudre des problèmes d'optimisation coûteux si vous posez les bonnes questions.

Résumé Technique : R2SAEA – Raisonnement de Relations avec des LLM dans l'Optimisation Coûteuse

Énoncé du Problème
Les Problèmes d'Optimisation Coûteuse (EOP) se caractérisent par des fonctions objectif en boîte noire dont les évaluations sont coûteuses (par exemple, expériences physiques, simulations haute fidélité) et pour lesquelles les gradients sont indisponibles. Le goulot d'étranglement principal dans la résolution des EOP est la limitation du budget d'évaluation. Bien que les Algorithmes Évolutionnaires Assistés par Surrogats (SAEA) atténuent ce problème en utilisant des modèles appris pour filtrer les candidats, les surrogats conventionnels (modèles de régression, de classification ou de relations) nécessitent généralement un réentraînement fréquent à mesure que la population évolue. Cette boucle « entraînement-prédiction » engendre une surcharge computationnelle significative, qui peut annuler les gains d'efficacité de l'assistance par surrogat. De plus, bien que les Grands Modèles de Langage (LLM) aient montré des promesses en optimisation, le déploiement direct de modèles de pointe dans des boucles évolutionnaires est souvent peu pratique en raison des coûts d'inférence élevés et de la latence, et les modèles plus petits manquent des capacités de raisonnement spécifiques requises pour une inférence de relations fiable.

Méthodologie : R2SAEA
L'article propose R2SAEA (Algorithme évolutionnaire assisté par surrogat de LLM basé sur des relations et entraîné par renforcement), un cadre qui remplace la boucle de réentraînement traditionnelle par un surrogat basé sur des relations, ne nécessitant que de l'inférence et alimenté par un LLM finement ajusté. La méthodologie se compose de trois composants principaux :

Raisonnement de Relations comme Apprentissage en Contexte :
Au lieu d'entraîner un modèle paramétrique, l'article présente la modélisation de surrogat de relations comme une tâche de raisonnement par paires en contexte. Le LLM est invité à prédire la supériorité relative entre des paires de solutions sur la base d'un ensemble d'exemples étiquetés (contexte). Deux critères principaux sont pris en charge :
- Critère Fonctionnel (C1) : Étiquetage binaire ( $+1/-1$ ) basé sur la supériorité de la valeur de l'objectif.
- Critère Catégorie (C2) : Étiquetage ternaire ( $+1/0/-1$ ) distinguant les relations inter-classes (bonnes vs mauvaises) et intra-classes.
Construction Itérative de Contexte Basée sur des Ancres :
Pour résoudre la complexité quadratique des comparaisons par paires ( $O((n+q)^2)$ ) qui dépasse les limites de contexte, les auteurs introduisent une stratégie itérative basée sur des ancres.
- La tâche est décomposée en $n$ rounds d'inférence, où chaque solution existante dans l'ensemble de contexte agit comme une « ancre » fixe.
- Pour chaque ancre, le LLM reçoit une invite contenant les relations étiquetées entre l'ancre et les autres solutions du contexte, ainsi que les relations non étiquetées entre l'ancre et les solutions candidates.
- Cela réduit la complexité de l'invite à linéaire ( $O(n+q)$ ) par round, assurant stabilité et évolutivité.
Agrégation Basée sur le Vote :
Le LLM produit une matrice de relations par paires. Celles-ci sont agrégées en scores de qualité absolus pour la sélection des candidats via un mécanisme de vote :
- Pour C1, le score est la somme négative des relations prédites (comptant combien d'ancres un candidat bat).
- Pour C2, un score normalisé est calculé en fonction de la fréquence à laquelle les candidats sont jugés « meilleurs » ou « pires » par les groupes d'ancres « bons » et « mauvais ».
Ajustement Fin par Apprentissage par Renforcement (GRPO) :
Pour permettre un déploiement efficace en zéro-shot sans réentraînement par génération, les auteurs affinent un LLM compact (Qwen2.5-7B) en utilisant l'Optimisation de Politique Relative par Groupes (GRPO).
- Données : Les trajectoires d'entraînement sont générées à partir de runs évolutionnaires sur des fonctions de référence (LZG, CEC), créant des paires d'instructions où la vérité terrain est la relation par paires réelle.
- Récompense : Une fonction de récompense basée sur des règles évalue la conformité au format de sortie JSON, l'exactitude des relations et la diversité de la sortie (pénalisant les prédictions dégénérées).
- Avantage : GRPO élimine le besoin d'un modèle critique séparé, utilisant une normalisation de récompense au niveau du groupe pour fournir des signaux d'apprentissage stables pour les étiquettes de relations discrètes.

Contributions Clés

Formulation : L'article formule la modélisation de surrogat basée sur des relations comme un problème de raisonnement par LLM en contexte sous les critères C1 et C2, introduisant un mécanisme de construction d'invite itérative basé sur des ancres pour réduire la complexité du contexte de quadratique à linéaire.
Stratégie d'Agrégation : Une stratégie d'agrégation basée sur le vote est conçue pour convertir les relations par paires prédites en scores absolus pour le classement des candidats, permettant aux opérateurs de sélection SAEA standard d'utiliser les sorties des LLM.
Pipeline RL : Un pipeline complet d'ajustement fin par RL est établi en utilisant des trajectoires évolutionnaires et GRPO. Les modèles résultants (ReLLM-C1/C2) démontrent une précision de prédiction de relations supérieure à celle des LLM généralistes puissants et permettent un déploiement en zéro-shot sans réentraînement.
Performance : Le cadre atteint des performances de pointe (SOTA) sur les benchmarks d'optimisation coûteuse mono-objectif (SOP) et multi-objectif (MOP), surpassant les SAEA classiques (régression, classification et basés sur des relations) et les bases de référence LLM généralistes.

Résultats Expérimentaux

Performance d'Optimisation : Sur les benchmarks mono-objectif (suites LZG, YLL), R2SAEA-SOP a obtenu le meilleur rang moyen (2,69) parmi sept algorithmes, surpassant DRSO basé sur des relations dans 22/45 cas et l'optimisation bayésienne dans 23/45 cas. Dans les tests multi-objectifs (DTLZ, WFG, MaF), R2SAEA-MOP s'est classé premier avec un rang moyen de 2,84, surpassant significativement les surrogats basés sur la classification (CPS-MOEA, CSEA) et la régression (K-RVEA).
Prédiction de Relations : Les évaluations hors ligne ont montré que les modèles ReLLM affinés par RL surpassent significativement leurs modèles de base pré-affinement et les LLM généralistes de pointe (y compris GPT-4o, Gemini-2.5-Pro et Qwen3-235B) en précision des relations par paires et en cohérence du classement (Spearman's $\rho$ ). Notamment, les LLM généralistes ont souvent produit des corrélations proches de zéro ou négatives, échouant à produire des classements significatifs sans entraînement spécifique à la tâche.
Évolutivité et Robustesse : Le modèle a démontré une robustesse face aux changements de dimensionalité de l'espace de décision ( $D \in \{5, 10, 30\}$ ) et de la taille du contexte. La normalisation locale (au niveau de l'invite) s'est révélée supérieure à la normalisation globale pour l'inférence relationnelle.
Déploiement : Les variantes quantifiées (4 bits et 8 bits) d'un modèle de 3 milliards de paramètres ont conservé une haute précision tout en permettant une inférence efficace sur des périphériques embarqués (par exemple, Jetson Orin NX), soutenant un paradigme de surrogat pratique au niveau matériel.

Signification et Revendications
L'article revendique que R2SAEA comble le fossé entre le fort potentiel de raisonnement des LLM et les exigences strictes d'efficacité de l'optimisation coûteuse. En passant d'un paradigme « entraînement-prédiction » à un paradigme « inférence uniquement », la méthode élimine la surcharge du réentraînement fréquent des surrogats. Les auteurs soulignent que leur approche fournit un paradigme de surrogat en zéro-shot, où un modèle unique et spécialisé peut être intégré dans des boucles évolutionnaires sans adaptation ultérieure. Ce travail représente le premier ajustement fin explicite de LLM spécifiquement pour l'optimisation évolutionnaire assistée par surrogat, offrant une voie réalisable vers une optimisation en temps réel et compatible matériel dans des environnements à ressources limitées.