Résumé technique : Conception d'algorithmes sensibles à la distribution avec des agents LLM

Énoncé du problème

Ce papier comble une lacune de la théorie classique de l'apprentissage où l'objet appris est un code exécutable de solveur plutôt qu'un modèle prédictif. Dans les configurations traditionnelles, la généralisation est mesurée par la précision (exactitude). Cependant, lorsque la sortie est un algorithme, deux solveurs peuvent tous deux retourner des solutions valides sur une distribution de déploiement tout en différant considérablement en temps d'exécution. Les auteurs soutiennent que pour les procédures exécutables, la généralisation doit englober à la fois la qualité de la solution et le calcul.

Le défi central est l'apprentissage de programmes sensibles à la distribution : étant donné des échantillons d'une distribution de déploiement $D$ inconnue, l'apprenant doit retourner un code de solveur spécialisé pour $D$. L'objectif n'est pas seulement de résoudre la classe de problèmes ambiante (par exemple, SAT ou TSP général), mais d'apprendre un algorithme dont l'exécution est optimisée pour les régularités structurelles spécifiques du régime cible. Cela se situe entre la conception d'algorithmes dans le pire des cas (qui suppose aucune information distributionnelle) et la complexité en moyenne (qui suppose une description analytique de la distribution).

Méthodologie : L'abstraction de l'indice de solveur

Le papier introduit une abstraction centrale appelée indice de solveur : une structure réutilisable inférée à partir d'échantillons et compilée en un code de solveur spécialisé. Le processus d'apprentissage est factorisé comme $S \mapsto \hat{h}_S \mapsto \hat{c}_S = \text{Comp}(\hat{h}_S)$, où :

1. $S$ : Un échantillon d'instances provenant de la distribution inconnue.
2. $\hat{h}_S$ : Un indice de solveur (par exemple, un ensemble de porte dérobée dans SAT, une décomposition latente dans les graphes, ou un motif de goulot d'étranglement de ressources).
3. $\text{Comp}(\hat{h}_S)$ : Un solveur compilé qui exploite cet indice.

Crucialement, le cadre sépare l'exactitude du calcul appris. L'exactitude est souvent garantie par un retour à un solveur générique et complet. L'échantillon est utilisé uniquement pour identifier quel raccourci computationnel compiler, réduisant ainsi le temps d'exécution sur les instances futures.

Pipeline de synthèse par LLM

Les auteurs implémentent ce cadre en utilisant des agents de code LLM. Le processus de synthèse implique trois étapes séquentielles pour chaque candidat :

1. Hypothèse ($H_c$) : L'agent propose une description structurée en langage naturel d'une règle distributionnelle suspectée (par exemple, « règles booléennes latentes » ou « palettes plantées »).
2. Analyse ($A_c$) : Un programme d'entraînement qui estime l'indice à partir de l'échantillon d'entraînement public, produisant un résumé compact et réutilisable (l'indice empirique).
3. Solveur ($s_c$) : Un programme de déploiement qui prend une nouvelle instance et le résumé récupéré pour produire une solution.

Le système emploie une recherche en faisceau sur les candidats. Il affine, divise ou remplace itérativement les candidats en fonction de métriques de validation (qualité, optimalité et temps d'exécution). La diversité est préservée en suivant des « clés de diversité » (classes d'explications larges) pour garantir que la recherche explore différentes hypothèses structurelles.

Contributions théoriques

Le papier fournit des garanties formelles pour deux régimes :

1. ERM sensible au temps d'exécution sur une bibliothèque fixe :
   Les auteurs prouvent que si une bibliothèque de solveurs $\mathcal{C}$ est fixe, le solveur cohérent avec l'échantillon empiriquement le plus rapide généralise à la fois en exactitude et en temps d'exécution. Plus précisément, avec une forte probabilité, le temps d'exécution du solveur sélectionné s'approche de celui du meilleur solveur spécialisé pour la distribution et correct dans la classe, jusqu'à un terme dépendant de la taille de la bibliothèque et du nombre d'échantillons. Cela établit que la minimisation empirique du temps d'exécution est une stratégie valide pour identifier des solveurs spécifiques à la distribution lorsque la spécialisation existe dans la bibliothèque.

2. Synthèse via des indices apprenables :
   Pour des contextes plus riches où la spécialisation n'est pas pré-énumérée, le papier modélise la récupération d'un indice à partir d'un espace d'indices fini $\mathcal{H}$. Sous une hypothèse de réalisabilité (la vraie distribution correspond à un certain $h^* \in \mathcal{H}$) et une condition de marge (l'indice vrai est statistiquement distinguable des autres), le papier prouve que $O(\frac{1}{\gamma^2} \log \frac{|\mathcal{H}|}{\delta})$ échantillons suffisent pour récupérer l'indice correct avec une forte probabilité.

   • Exemple concret : Le papier détaille un modèle de Porte dérobée SAT cachée. Ici, l'indice est un ensemble de variables qui, une fois fixées, réduisent la formule à une classe traitable. La théorie montre qu'une statistique de saillance peut identifier cette porte dérobée à partir d'échantillons, permettant au solveur compilé d'atteindre une accélération exponentielle sur la distribution de déploiement tout en maintenant l'exactitude via un retour à la sécurité.

Résultats expérimentaux

Les auteurs ont évalué le cadre sur 21 distributions cibles d'optimisation combinatoire structurées couvrant sept classes de problèmes : Coloration de graphes, MAXSAT, Ensemble indépendant maximum (MIS), Ensemble dominant minimum (MDS), LP de bin-packing, Sac à dos multidimensionnel (MDKP) et Problème du voyageur de commerce (TSP).

Métriques de performance clés

• Qualité : Les solveurs synthétisés ont atteint une qualité normalisée moyenne de 0,971. Cela représente une amélioration de +0,224 par rapport au pool moyen d'heuristiques et de +0,098 par rapport à l'heuristique de la plus haute qualité.
• Temps d'exécution : Les solveurs synthétisés étaient significativement plus rapides que les références :
  • 336,9× plus rapides que l'heuristique de meilleure qualité.
  • 342,8× plus rapides que Gurobi (avec une limite de temps de 10 secondes).
  • 16,1× plus rapides que le backend exact limité dans le temps sélectionné.
• Validation externe (PACE 2025) : Sur des instances privées publiées du problème de l'ensemble dominant, le solveur synthétisé était valide sur les 100 graphes et s'est exécuté environ deux ordres de grandeur plus vite que les meilleurs solveurs de compétition (par exemple, Fontan–Verger, Root), bien qu'avec un écart de qualité modéré (taille de la solution ~3,3 % plus grande).

Mécanisme d'amélioration

L'analyse du code généré révèle que les gains proviennent d'un changement d'échelle computationnelle. Les solveurs synthétisés remplacent souvent la recherche exponentielle ambiante ou l'optimisation à usage général par des calculs d'ordre inférieur, spécifiques à la distribution. Les exemples incluent :

• Le remplacement d'une recherche $O^*(2^n)$ par une vérification de modèle et une réparation bornée.
• L'utilisation d'un tri par densité pour les ressources actives dans le LP de bin-packing au lieu de la résolution complète du LP.
• L'exploitation de structures géométriques latentes dans le TSP pour construire des tournées sans programmation dynamique complète.

Importance et revendications

Le papier revendique offrir une voie constructive vers la traçabilité spécifique à la distribution. Contrairement à l'analyse lissée ou à la complexité paramétrée, qui reposent sur des voies conçues à la main, ce cadre apprend la voie directement à partir des échantillons.

Les auteurs soulignent que l'objet appris est plus proche d'un algorithme spécialisé pour le régime de déploiement que d'une heuristique ajustée pour des instances isolées. L'« indice de solveur » sert de description réutilisable de la structure spécifique à la distribution qui amortit le coût de l'inférence : un coût de synthèse unique sur les échantillons produit un solveur avec un coût par instance inférieur.

Le travail est modeste dans son ampleur : il ne prétend pas résoudre les classes de problèmes ambiantes dans le pire des cas. Au lieu de cela, il démontre que pour des distributions structurées, les échantillons peuvent révéler des raccourcis réutilisables permettant aux agents LLM de compiler des solveurs à la fois hautement précis et considérablement plus rapides que les outils généraux de l'état de l'art. Le cadre met en évidence que le temps d'exécution est une propriété apprenable lorsque la distribution de déploiement est accessible via des échantillons.