Les chercheurs enseignent aux LLM à résoudre des défis de planification complexes

Imaginez une entreprise de café essayant d’optimiser sa chaîne d’approvisionnement. L’entreprise s’approvisionne sur trois fournisseurs, les rôtidra dans deux installations en café sombre ou léger, puis expédie le café rôti à trois emplacements de vente au détail. Les fournisseurs ont des capacités fixes différentes, les frais de torréfaction et les frais d’expédition varient d’un endroit à l’autre.

L’entreprise cherche à minimiser les coûts tout en remplissant une augmentation de 23% de la demande.

Ne serait-il pas plus facile pour l’entreprise de demander à Chatgpt de proposer un plan optimal? En fait, malgré toutes leurs capacités incroyables, les modèles de grandes langues (LLM) fonctionnent souvent mal lorsqu’ils sont chargés de résoudre directement de tels problèmes de planification compliqués par eux-mêmes.

Plutôt que d’essayer de changer le modèle pour faire d’un LLM un meilleur planificateur, les chercheurs du MIT ont adopté une approche différente. Ils ont introduit un cadre qui guide un LLM pour briser le problème comme le ferait un humain, puis le résoudre automatiquement à l’aide d’un puissant outil logiciel.

Un utilisateur n’a besoin que de décrire le problème en langage naturel – aucun exemple spécifique à la tâche n’est nécessaire pour former ou inviter le LLM. Le modèle code pour l’invite de texte d’un utilisateur dans un format qui peut être démêlé par un solveur d’optimisation conçu pour retirer efficacement des défis de planification extrêmement difficiles.

Pendant le processus de formulation, le LLM vérifie ses travaux à plusieurs étapes intermédiaires pour s’assurer que le plan est décrit correctement au solveur. S’il repère une erreur, plutôt que d’abandonner, le LLM essaie de réparer la partie cassée de la formulation.

Lorsque les chercheurs ont testé leur cadre sur neuf défis complexes, tels que la minimisation des robots de l’entrepôt à distance doivent se déplacer pour effectuer des tâches, il a atteint un taux de réussite de 85%, tandis que la meilleure base de référence n’a atteint qu’un taux de réussite de 39%.

Le cadre polyvalent pourrait être appliqué à une gamme de tâches de planification en plusieurs étapes, telles que la planification des équipes aériennes ou la gestion du temps de la machine dans une usine.

« Our research introduces a framework that essentially acts as a smart assistant for planning problems. It can figure out the best plan that meets all the needs you have, even if the rules are complicated or unusual, » says Yilun Hao, a graduate student in the MIT Laboratory for Information and Decision Systems (LIDS) and lead author of a paper on this research posted to the arxiv serveur de préimprimée.

Elle est rejointe sur l’article par Yang Zhang, un chercheur scientifique au MIT-IBM Watson AI Lab; et l’auteur principal Chuchu Fan, professeur agrégé d’aéronautique et d’astronautique et d’enquêteur principal de light. La recherche sera présentée à la Conférence internationale sur les représentations de l’apprentissage (ICLR 2025) tenue à Singapour du 24 au 28 avril.

Optimisation 101

Le groupe de ventilateurs développe des algorithmes qui résolvent automatiquement ce que l’on appelle des problèmes d’optimisation combinatoire. Ces vastes problèmes ont de nombreuses variables de décision interdépendantes, chacune avec plusieurs options qui s’ajoutent rapidement à des milliards de choix potentiels.

Les humains résolvent de tels problèmes en les rétrécissant en quelques options, puis en déterminant lequel conduit au meilleur plan global. Les solveurs algorithmiques des chercheurs appliquent les mêmes principes aux problèmes d’optimisation qui sont beaucoup trop complexes pour un humain.

Mais les résolveurs qu’ils développent ont tendance à avoir des courbes d’apprentissage élevées et ne sont généralement utilisés que par des experts.

« Nous pensions que les LLM pourraient permettre aux non-experts d’utiliser ces algorithmes de résolution. Dans notre laboratoire, nous prenons un problème d’expert du domaine et le formalisons dans un problème que notre solveur peut résoudre. Pourrions-nous enseigner à un LLM pour faire la même chose? » Le fan dit.

En utilisant le cadre que les chercheurs ont développé, appelé programmation formalisée basée sur LLM (LLMFP), une personne fournit une description du langage naturel du problème, des informations de base sur la tâche et une question qui décrit leur objectif.

Ensuite, LLMFP invite un LLM à raisonner sur le problème et déterminer les variables de décision et les contraintes de clés qui façonneront la solution optimale.

LLMFP demande au LLM de détailler les exigences de chaque variable avant de coder les informations dans une formulation mathématique d’un problème d’optimisation. Il écrit du code qui code le problème et appelle le solveur d’optimisation joint, qui arrive à une solution idéale.

« C’est similaire à la façon dont nous enseignons aux étudiants de premier cycle sur les problèmes d’optimisation au MIT. Nous ne leur enseignons pas un seul domaine. Nous leur enseignons la méthodologie », ajoute Fan.

Tant que les entrées du solveur sont correctes, elle donnera la bonne réponse. Toutes les erreurs dans la solution proviennent d’erreurs dans le processus de formulation.

Pour s’assurer qu’il a trouvé un plan de travail, LLMFP analyse la solution et modifie toutes les étapes incorrectes de la formulation du problème. Une fois que le plan réussit cette auto-évaluation, la solution est décrite à l’utilisateur en langage naturel.

Perfectionner le plan

Ce module d’auto-évaluation permet également au LLM d’ajouter toutes les contraintes implicites qu’il a manquées la première fois, dit Hao.

Par exemple, si le cadre optimise une chaîne d’approvisionnement pour minimiser les coûts pour un coffeeshop, un humain sait que le coffeeshop ne peut pas expédier une quantité négative de haricots rôtis, mais un LLM pourrait ne pas s’en rendre compte.

L’étape d’auto-évaluation signalerait cette erreur et inciterait le modèle à le réparer.

« De plus, un LLM peut s’adapter aux préférences de l’utilisateur. Si le modèle réalise qu’un utilisateur particulier n’aime pas modifier le temps ou le budget de ses plans de voyage, cela peut suggérer de modifier des choses qui correspondent aux besoins de l’utilisateur », explique Fan.

Dans une série de tests, leur cadre a atteint un taux de réussite moyen entre 83% et 87% sur neuf problèmes de planification diverses en utilisant plusieurs LLM. Alors que certains modèles de référence étaient meilleurs à certains problèmes, LLMFP a atteint un taux de réussite global environ deux fois plus élevé que les techniques de référence.

Contrairement à ces autres approches, LLMFP ne nécessite pas d’exemples spécifiques au domaine pour la formation. Il peut trouver la solution optimale à un problème de planification dès la sortie de la boîte.

De plus, l’utilisateur peut adapter LLMFP pour différents solveurs d’optimisation en ajustant les invites alimentées au LLM.

« Avec les LLM, nous avons la possibilité de créer une interface qui permet aux gens d’utiliser des outils d’autres domaines pour résoudre des problèmes de manière à laquelle ils n’auraient peut-être pas pensé auparavant », a déclaré Fan.

À l’avenir, les chercheurs souhaitent permettre à LLMFP de prendre des images en entrée pour compléter les descriptions d’un problème de planification. Cela aiderait le cadre à résoudre des tâches qui sont particulièrement difficiles à décrire avec le langage naturel.