Un LLM apprend au planificateur à se contenter d'une mémoire polynomiale et résout 1709 tâches sur 1890

Les planificateurs classiques butent sur la mémoire avant de buter sur le temps. La recherche heuristique conserve une liste d'états visités, et cette liste croît exponentiellement, même lorsque l'heuristique est presque parfaite. Les auteurs d'un nouveau travail publié sur arXiv proposent de se passer de cette liste. Avec des politiques écrites par un modèle de langage, leur procédure a résolu 1709 des 1890 tâches de test de l'IPC 2023 Learning Track et du jeu Autoscale Agile. C'est plus que LAMA, BFWS et Levitron, et la plupart des tâches ont été traitées en moins d'une seconde et dans la limite de 100 MiB.

Une politique à registres au lieu d'une liste d'états

Plutôt que de recourir à une recherche universelle, les auteurs apprennent à piloter la recherche. Pour chaque domaine, on écrit une spécification sous la forme d'une « politique indexicale ». Il s'agit d'une politique généralisée dotée de registres, qui contiennent des objets, et de modes, qui fixent l'ordre d'application des règles. L'ajout clé est la règle choose. Elle charge un objet dans un registre et pose un point de retour arrière, un seul candidat approprié suffisant. Toutes les autres règles doivent fonctionner quelle que soit l'issue et n'ont pas besoin de recherche.

Le résultat principal du travail est théorique. La terminaison structurelle exclut les exécutions infinies de la politique. Les auteurs montrent qu'elle borne aussi toute exécution par un polynôme en le nombre d'objets. Il s'ensuit que la recherche en profondeur trouve un plan en mémoire polynomiale, quelle que soit la taille de l'espace d'états, et que la liste des états visités devient inutile. Le prix à payer se mesure en temps : celui-ci n'est exponentiel qu'en fonction de la profondeur de choix, c'est-à-dire du nombre de véritables choix le long de l'exécution. Toute classe de tâches résolue par une telle politique relève donc de NP, et de P lorsque la profondeur de choix est constante.

Le rôle du modèle de langage

Les politiques ne sont pas écrites à la main. Un modèle de langage les génère dans une boucle à contre-exemples. À chaque tour, la boucle certifie la terminaison, vérifie la politique sur les tâches d'entraînement et veille à ce que la profondeur de choix reste faible. Cette dernière condition est importante, car c'est elle qui détermine le temps que consommera l'exploration. Le résumé ne précise pas quel modèle a été utilisé.

Les chiffres du résumé

• 1709 tâches de test résolues sur 1890 (environ 90 %), 181 tâches restent non résolues.
• Benchmarks : IPC 2023 Learning Track et Autoscale Agile.
• Les concurrents LAMA, BFWS et Levitron en ont résolu moins.
• La plupart des tâches sont résolues en moins d'une seconde et dans la limite de 100 MiB.
• Mémoire polynomiale, sans liste d'états visités.
• Le temps n'est exponentiel qu'en fonction de la profondeur de choix.
• Les classes de tâches résolues par de telles politiques relèvent de NP, et de P lorsque la profondeur de choix est constante.

À quoi cela peut servir

L'approche paraît la plus prometteuse là où la mémoire coûte plus cher que le temps de calcul : planificateurs embarqués, robots, systèmes qui traitent des tâches du même type sur des entrées différentes. La répartition des rôles apporte aussi un avantage concret. Le modèle de langage écrit un programme-politique vérifiable, et le certificat de terminaison offre une garantie que n'a pas un plan produit directement par le modèle.

Les limites sont elles aussi claires. Il faut une politique par domaine, l'apprentissage exige un jeu de tâches d'entraînement, et les chiffres ont été obtenus par les auteurs eux-mêmes dans un préprint, sans vérification indépendante. Mais un tel hybride procure déjà un gain de mémoire sensible sur des benchmarks de planification standard.