Résumé technique : Recherche par arbre de concepts contrastifs pour la découverte d'algorithmes assistée par LLM

Énoncé du problème

La découverte d'algorithmes assistée par les grands modèles de langage (LLM) opère comme un processus d'optimisation itératif et de type boîte noire, où un LLM propose des programmes candidats et un évaluateur externe fournit un retour sur la tâche. Bien que des paradigmes récents (par exemple, FunSearch, AlphaEvolve) aient réussi à redécouvrir ou à améliorer des solutions à des problèmes combinatoires (tels que les problèmes de type Erdős), ils reposent largement sur des mises à jour évolutives pilotées par le fitness (aptitude). Dans ces systèmes existants, la sélection des parents est déterminée par la performance brute (fitness) des programmes, et la recherche progresse comme une marche sur la lignée des programmes ordonnés par performance.

Une limitation critique de cette approche est que l'espace des programmes reste faiblement structuré. Même lorsqu'ils sont contraints par un LLM, les algorithmes générés manquent souvent de notions claires de localité, de variation fluide ou de structure compositionnelle qui pourraient être exploitées par des algorithmes de recherche. Par conséquent, le guidage provient principalement de signaux de fitness bruts et du prior implicite du LLM, plutôt que d'une compréhension explicite et apprise de quels composants sémantiques des algorithmes sont réellement utiles. Cet article traite de la question ouverte de savoir comment exploiter au maximum la représentation interne de l'espace des programmes par le LLM pour améliorer l'efficacité et l'interprétabilité de la recherche.

Méthodologie : Recherche par arbre de concepts contrastifs (CCTS)

Les auteurs introduisent la Recherche par Arbre de Concepts Contrastifs (CCTS), un cadre qui déplace le guidage de la recherche du fitness brut vers un espace de concepts sémantiques hiérarchique et appris. L'hypothèse centrale est que les algorithmes peuvent être décrits par un espace de concepts sémantiques sous-jacent organisé sous forme de hiérarchie, où les nœuds représentent des concepts et les arêtes codent le raffinement ou la spécialisation.

1. Représentation des concepts et construction de l'arbre

• Extraction de caractéristiques : Chaque programme candidat $x$ est mappé vers une représentation de caractéristiques sémantiques $b = \Phi(x)$, extraite en demandant au LLM de générer une liste de concepts pertinents.
• Structure hiérarchique : Ces concepts sont organisés en un arbre de concepts enraciné. Un vecteur de concept $b$ est un vecteur indicateur où les activations sont ancêtres-fermées (l'activation d'un concept enfant implique l'activation de tous ses ancêtres). L'arbre est dynamique, croissant à mesure que de nouveaux concepts sont découverts durant la recherche.

2. Apprentissage contrastif de l'utilité des concepts

Au lieu de sélectionner les parents uniquement sur la base de leur score de fitness, le CCTS apprend quels concepts sont empiriquement associés à une haute performance grâce à une approche contrastive :

• Partitionnement : L'archive des programmes évalués est partitionnée en sous-ensembles « bons » ($y_i \ge \tau_t$) et « mauvais » ($y_i < \tau_t$) basés sur un seuil de performance.
• Ajustement du modèle : Deux modèles probabilistes, $\hat{p}_{\eta^+}(b)$ et $\hat{p}_{\eta^-}(b)$, sont ajustés aux distributions de caractéristiques des sous-ensembles bons et mauvais, respectivement. Les auteurs utilisent une approche de type Estimateur de Parzen structuré en arbre (TPE) avec un modèle de Bernoulli hiérarchique factorisé. Ce modèle suppose l'indépendance conditionnelle des caractéristiques étant donné leur parent dans la hiérarchie.
• Score de rapport de vraisemblance : Un score de rapport de vraisemblance (log-utilité du concept) est calculé pour chaque programme :
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  Ce score quantifie la force avec laquelle un ensemble spécifique de concepts distingue les solutions performantes des solutions peu performantes.

3. Sélection des parents et dynamique de recherche

• Échantillonnage biaisé : Les parents sont sélectionnés dans l'archive avec une probabilité proportionnelle à leur score de rapport de vraisemblance. Cela biaise la recherche vers les programmes contenant des combinaisons de concepts empiriquement associées à une amélioration.
• Mécanisme d'exploration : Pour éviter la convergence prématurée et encourager la découverte de nouveaux concepts, le CCTS incorpore un mécanisme d'exploration léger. Cela inclut :
  • Priors Beta : Lissage des comptages pour garantir que les nouveaux concepts n'aient jamais une probabilité nulle.
  • Biais de nouveauté : Dépréciation des concepts qui ont été fréquemment essayés, favorisant les régions sous-explorées de l'arbre de concepts.
  • Stratégie de mélange : Un mélange d'exploitation (basée sur le modèle contrastif appris) et d'exploration (basée sur la nouveauté) guide la sélection des concepts à injecter dans le prompt du LLM pour la génération des enfants.

Contributions clés

1. Structure sémantique explicite : L'article propose de rendre explicite la structure latente de l'espace des algorithmes en apprenant un arbre de concepts hiérarchique, allant au-delà de l'espace de programmes non structuré utilisé dans les algorithmes évolutifs standards.
2. Guidage contrastif : Il introduit un cadre statistique contrastif qui apprend à identifier quels concepts prioriser et, surtout, quels concepts éviter, plutôt que de simplement suivre les programmes les plus performants.
3. Interprétabilité : La méthode produit des arbres de concepts interprétables et spécifiques à la tâche qui révèlent la structure sémantique explorée pendant la recherche, offrant des perspectives sur les stratégies algorithmiques découvertes.
4. Validation synthétique : Les auteurs construisent un environnement synthétique contrôlé avec un « enseignant » (arbre de concepts) et des utilités de vérité terrain. Cela leur permet de valider que le CCTS récupère la structure sémantique sous-jacente et que la dynamique de recherche observée est pilotée par l'apprentissage des utilités de concepts plutôt que par des artefacts spécifiques au LLM.

Résultats expérimentaux

Les auteurs ont évalué le CCTS sur un benchmark de problèmes de combinatoire de type Erdős, incluant le compactage de cercles (circle packing), la conjecture de Kakeya arithmétique, le problème du triangle de Heilbronn et le problème des carrés dans un carré.

• Gains de performance : Le CCTS a systématiquement obtenu des scores plus élevés et une amélioration plus rapide par rapport aux stratégies de référence (Uniforme, Greedy, et sélection $k$-élite) à travers plusieurs tâches.
• Mécanisme d'amélioration : L'analyse a révélé que les gains de performance sont largement pilotés par l'apprentissage de quels concepts éviter. Les exécutions réussies ont identifié un ensemble similaire de concepts à haute utilité que les exécutions infructueuses, mais ont démontré une bien meilleure capacité à supprimer les concepts à faible utilité (nuisibles). Cela suggère que le CCTS stabilise la recherche en réduisant l'exploration improductive causée par des corrélations trompeuses dans le prior initial du LLM.
• Validation synthétique : Dans l'environnement synthétique, les utilités de concepts apprises ont montré une forte corrélation ($r=0,94$) avec les utilités de l'enseignant de vérité terrain, confirmant que la méthode récupère efficacement des représentations sémantiques significatives.
• Dépendance à la structure : L'équilibre optimal entre exploration et exploitation dépend de la structure de l'arbre de concepts sous-jacent (par exemple, le ratio de branchement), suggérant que les stratégies de recherche doivent être adaptées à la topologie spécifique de l'espace du problème.

Signification et affirmations

L'article affirme que le CCTS répond à un décalage fondamental dans la découverte d'algorithmes assistée par LLM : les algorithmes à haut score ne génèrent pas nécessairement des descendants performants car le fitness est un mauvais indicateur de l'évolutivité dans un espace faiblement structuré. En déplaçant la sélection du fitness brut vers une preuve sémantique d'amélioration, le CCTS permet à la recherche d'opérer dans un espace de concepts où la distance, la recombinaison et la direction de recherche sont significatives.

Les auteurs positionnent ce travail comme une avancée méthodologique vers une découverte d'algorithmes plus fiable et scalable. Ils soulignent que, bien que les résultats actuels démontrent des améliorations relatives par rapport aux bases de référence sur des benchmarks spécifiques, la contribution principale est la démonstration de la manière dont des structures de concepts sémantiques explicites et compatibles avec l'humain peuvent rendre la découverte automatisée plus transparente, contrôlable et efficace. Le travail suggère que les futurs systèmes devraient se concentrer sur l'apprentissage et l'exploitation de ces hiérarchies sémantiques latentes plutôt que de compter uniquement sur des signaux de fitness de type boîte noire.