🤖 AI

SkillDAG: Self-Evolving Typed Skill Graphs for LLM Skill Selection at Scale

SkillDAG introduit un cadre de graphe orienté typé et auto-évolutif qui permet aux agents LLM de récupérer dynamiquement et de raisonner structurellement sur les relations entre compétences lors de l'exécution, surpassant de manière significative les références existantes dans des environnements de tâches complexes en accumulant des connaissances fondées sur l'exécution et en maintenant un classement robuste des candidats à mesure que les bibliothèques de compétences augmentent.

Auteurs originaux : Tong Bai, Zhenglin Wan, Pengfei Zhou, Xingrui Yu, Wangbo Zhao, Yang You, Ivor W. Tsang

Publié 2026-06-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tong Bai, Zhenglin Wan, Pengfei Zhou, Xingrui Yu, Wangbo Zhao, Yang You, Ivor W. Tsang

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 engagiez une équipe massive de travailleurs spécialisés (compétences) pour aider un robot à résoudre des énigmes complexes. Par le passé, lorsque l'équipe était petite, vous pouviez simplement lire le CV de chacun et choisir les bonnes personnes. Mais maintenant, imaginez que votre équipe soit passée à des milliers de travailleurs.

Si vous essayez de lire tous leurs CV en même temps, vous manquerez de temps et d'espace. Si vous demandez simplement à un ordinateur de trouver le CV le plus « similaire » à la tâche, vous pourriez passer à côté de la personne cruciale dont vous avez réellement besoin parce que son CV ne ressemble pas à la tâche, même si elle est essentielle pour celle-ci.

SkillDAG est un nouveau système conçu pour résoudre ce problème de « trop de travailleurs » pour les agents IA. Voici comment il fonctionne, en utilisant des analogies simples :

1. Le Problème : La liste « plate » vs La « carte »

Les systèmes actuels traitent souvent les compétences comme une liste plate de noms. Si vous demandez une « compétence de cuisine », le système trouve le mot « cuisiner ». Mais il pourrait oublier que vous avez aussi besoin d'une « compétence de découpe » (un prérequis) ou que vous ne devriez pas utiliser « cuisiner » et « congeler » en même temps (un conflit).

L'ancienne méthode : C'est comme essayer de naviguer dans une ville en utilisant seulement une liste de noms de rues. Vous connaissez peut-être la destination, mais vous ne savez pas quelles rues y mènent, lesquelles sont des impasses ou lesquelles sont à sens unique.
La méthode SkillDAG : Elle construit une carte vivante (un graphe) où chaque compétence est un pâté de maisons, et les connexions entre elles sont des routes clairement étiquetées. Certaines routes disent « Vous devez prendre ceci pour y arriver » (Prérequis), d'autres disent « Ceci est un raccourci » (Spécialisation), et d'autres disent « Ne pas passer par ici » (Conflit).

2. L'Innovation : L'Agent détient la carte

Dans les systèmes précédents, un programme informatique fixe décidait quelles compétences charger en fonction de la carte, et l'agent IA recevait simplement une liste pré-emballée. L'agent ne pouvait pas demander : « Pourquoi as-tu choisi cela ? » ou « Puis-je ajouter une nouvelle route ? ».

SkillDAG inverse la tendance.

L'Agent est le Navigateur : L'agent IA se voit lui-même donner la carte. Il peut observer les connexions, poser des questions et décider quelles compétences charger.
L'outil de « Recherche » : Au lieu de simplement recevoir une liste de noms, l'agent interroge la carte : « Qui est proche de cette tâche ? » (Correspondances), « Qui est connecté à eux ? » (Voisins), et « Qui dois-je éviter ? » (Conflits). Cela donne à l'agent trois types d'indices différents pour prendre une décision intelligente.

3. La partie « Auto-Évolutive » : Tracer de nouvelles routes

La carte n'est pas parfaite au départ. Elle est construite à partir d'un « démarrage à froid » (la lecture des CV), mais elle passe à côté de choses qui n'apparaissent que lorsque le robot effectue réellement le travail.

Le protocole « Proposer et Valider » : Si l'agent tente une tâche et réalise : « Hé, j'avais besoin de la Compétence A avant de pouvoir utiliser la Compétence B », il peut proposer une nouvelle route sur la carte reliant ces deux éléments.
Les garde-fous de sécurité : Avant qu'une nouvelle route ne soit tracée, le système vérifie trois règles :
1. Pas de boucles : On ne peut pas créer un cercle où A nécessite B, et B nécessite A (cela piégerait l'agent).
2. Pas de contradictions : On ne peut pas tracer une route disant « Allez ici » et une autre disant « N'allez pas ici » pour la même paire.
3. Bouton Annuler : Si l'agent fait une erreur, le système conserve un journal afin que la route puisse être effacée plus tard.

Cela signifie que la carte devient plus intelligente et plus détaillée à chaque fois que l'agent résout une énigme, apprenant de sa propre expérience.

4. Les Résultats : Plus intelligent et plus rapide

L'article a testé cela sur deux types de défis :

ALFWorld (Maison virtuelle) : L'agent devait déplacer des objets dans une maison.
SkillsBench (Tâches de codage) : L'agent devait écrire du code pour résoudre des problèmes.

Le résultat :

Meilleur succès : L'agent SkillDAG a résolu nettement plus d'énigmes que les méthodes précédentes les plus performantes. Il était particulièrement efficace pour choisir les bons outils lorsque la bibliothèque d'outils était immense.
Meilleure mémoire : Même lorsque le nombre de compétences a été multiplié par 10, l'agent SkillDAG ne s'est pas confondu. Il continuait à trouver les bonnes compétences, alors que les autres méthodes commençaient à échouer.
Amélioration intrinsèque : Le système n'a pas seulement eu de la chance ; il a réellement récupéré les compétences de la « vérité terrain » (ground truth) plus souvent, prouvant que la structure de la carte fonctionnait.

Résumé de l'analogie

Considérez SkillDAG comme un GPS qui se met à jour tout seul donné à un agent IA.

Ancien système : Vous donnez à l'agent une carte papier statique. Si la route change ou si un nouveau raccourci s'ouvre, l'agent est coincé avec sa vieille carte.
SkillDAG : L'agent tient un GPS numérique. Il peut voir le trafic (conflits), les connexions (dépendances), et au fur et à mesure qu'il conduit, il dessine de nouveaux raccourcis sur la carte pour les futurs trajets. L'agent décide où aller, en utilisant la carte comme un outil, et non comme une règle.

L'article affirme que cette approche permet aux agents IA de bien mieux choisir les bons outils parmi une bibliothèque massive, ce qui conduit à des taux de réussite plus élevés dans des tâches complexes.

Résumé Technique : SkillDAG

1. Énoncé du Problème

À mesure que les agents basés sur les Grands Modèles de Langage (LLM) adoptent des bibliothèques de compétences externes étendues, le goulot d'étranglement passe de l'auteur de compétences à la sélection de compétences. Lorsque les bibliothèques atteignent des milliers d'entrées, les méthodes de recherche traditionnelles ne parviennent pas à capturer les relations structurelles complexes entre les compétences.

Limites de la Recherche Plate : Les approches standards (par exemple, la similitude de cosinus top- $K$ ou BM25) traitent les compétences comme des vecteurs indépendants. Cela conduit à des « échecs silencieux » où des prérequis structurellement nécessaires sont omis, des compétences redondantes ou interférantes sont sélectionnées, et des paires synergiques sont manquées.
Limites des Graphes Statiques : Les travaux antérieurs comme Graph of Skills (GoS) modélisent les relations inter-compétences mais reposent sur un pipeline de recherche hors ligne fixe (par exemple, le PageRank personnalisé). Le lot de compétences résultant est opaque pour l'agent ; le LLM ne peut pas interroger la structure du graphe, raisonner sur la raison pour laquelle une compétence a été choisie, rétracter une récupération bruitée ou enregistrer de nouvelles relations découvertes lors de l'exécution.

Le problème central est que les systèmes actuels cachent la structure relationnelle de la bibliothèque à l'agent, empêchant le LLM de prendre des décisions structurelles éclairées pendant l'inférence.

2. Méthodologie : SkillDAG

SkillDAG propose une inversion fondamentale : plutôt que d'incorporer le graphe à l'intérieur d'un algorithme de classement fixe, il expose le graphe de relations de compétences typées comme une interface de recherche structurelle appelable par l'agent. Le graphe est interrogé, inspecté et fait évoluer par le LLM pendant l'exécution.

2.1. Graphe de Relations de Compétences Typées

La bibliothèque de compétences est modélisée comme un graphe dirigé $G = (V, E, \tau)$ où les arêtes sont assignées à l'un des cinq types opérationnels :

depends_on (dépend de) : La compétence $A$ nécessite le prérequis $B$ .
specializes (se spécialise en) : La compétence $D$ est une variante plus étroite et préférée de $A$ .
composes_with (se compose avec) : Les compétences $A$ et $B$ ont un usage de co-utilisation synergique.
similar_to (similaire à) : Redondance fonctionnelle ; l'agent doit en choisir une, pas les deux.
conflicts_with (entre en conflit avec) : Les compétences $A$ et $B$ ne doivent pas être co-sélectionnées (signal d'élagage).

Choix de Conception Clé : conflicts_with est traité comme un signal d'élagage, et non comme une arête de parcours, pour empêcher l'agent de naviguer vers des compétences qu'il est explicitement informé d'éviter. L'ossature (depends_on, specializes) est contrainte d'être acyclique.

2.2. Interface Appelable par l'Agent

L'agent interagit avec le graphe via une fonction search qui renvoie trois canaux de preuves distincts, plutôt qu'un simple lot classé :

Matches (Correspondances) : Top- $K$ compétences basées sur la similitude d'embedding des nœuds de requête.
Neighbors (Voisins) : Compétences atteintes via un parcours BFS borné (profondeur $D$ ) sur les quatre types d'arêtes « positives » (depends_on, specializes, composes_with, similar_to).
Conflicts (Conflits) : Arêtes conflicts_with à un saut incident à toute correspondance.

Cette décomposition permet à l'agent d'abandonner des champs spécifiques sous des budgets de contexte serrés, de planifier des recherches dynamiquement et de maintenir une trace de raisonnement pour les décisions de sélection/exclusion.

2.3. Construction de Démarrage à Froid (Cold-Start)

Pour initialiser le graphe avant toute exécution d'agent, une stratégie d'embedding à deux vues est employée pour récupérer les paires trans-fonctionnelles que la similitude à vue unique manque :

$e_{self}$ : Encode l'identifiant, la description et le corps de la compétence (ce qu'elle fait).
$e_{needs}$ : Un LLM génère un résumé de type HyDE de ce que la compétence nécessite (prérequis) basé sur des tâches d'invocation imaginées, qui est ensuite encodé.

Les paires candidates sont formées si l'un des classements dépasse un seuil adaptatif, suivi d'un classificateur de paires par LLM pour assigner les types d'arêtes. conflicts_with est exclu de cette phase statique car cela nécessite des preuves d'exécution.

2.4. Évolution du Graphe en Ligne

SkillDAG introduit un protocole de proposition-puis-validation pour les mises à jour du graphe en ligne :

propose-edge : Un essai à blanc où l'agent prévisualise un changement potentiel d'arête et examine l'historique existant pour cette paire de compétences.
edit-edge : L'agent valide le changement avec une raison en langage naturel et une trace d'exécution.

Invariants Structurels : Pour prévenir l'incohérence, chaque validation doit passer par trois vérifications :

Acyclicité : Empêche les cycles dans l'ossature depends_on/specializes.
Non-contradiction : Empêche une paire d'avoir à la fois une arête positive (ex: depends_on) et une arête conflicts_with.
Réversibilité : Un journal d'historique de type "append-only" permet de revenir en arrière sur les éditions erronées.

3. Contributions Clés

Identification des Modes de Défaillance Structurelle : L'article identifie que la recherche plate omet silencieusement des compétences structurellement nécessaires et concatène des compétences redondantes, un échec invisible à la seule correspondance de similitude.
Interface Appelable par l'Agent : SkillDAG expose un graphe de relations typées via search/show/propose-edge/edit-edge, remplaçant les politiques de classement fixes par des preuves structurelles sur lesquelles l'agent peut raisonner directement.
Protocole d'Évolution en Ligne : Un mécanisme permettant aux agents de faire croître le graphe à partir de preuves de l'épisode unique sous des invariants structurels stricts, couplé à un constructeur de démarrage à froid à deux vues pour récupérer les paires trans-fonctionnelles.
Validation Empirique : Démontré des améliorations sur ALFWorld et SkillsBench à travers différents backbones de modèles.

4. Résultats Expérimentaux

Les expériences ont été menées sur ALFWorld (environnement incarné textuel) et SkillsBench (tâches de génération de code conteneurisées) en utilisant MiniMax-M2.7 et gpt-5.2-codex.

Gains de Performance (MiniMax-M2.7) :
- ALFWorld : Le taux de succès est passé de 54,3 % (baseline GoS) à 67,1 % (+12,8 points).
- SkillsBench : La récompense est passée de 18,7 % à 27,3 % (+8,6 points).
- Récupération Intrinsèque : Le Ret@K sur SkillsBench est passé de 65,5 % à 78,2 %, indiquant que le pipeline de récupération est lui-même plus précis avant l'exécution.
Gains de Performance (gpt-5.2-codex) :
- SkillDAG égale la baseline GoS sur ALFWorld (93,6 %) et s'améliore sur SkillsBench (34,4 % $\to$ 36,8 %).
- L'article note que la signature d'« aide au routage » est la plus importante là où le modèle de base ne peut pas raisonner au-delà d'un mauvais lot, et disparaît une fois que le modèle est assez fort pour gérer des lots opaques.
Scalabilité : La qualité de la récupération de SkillDAG est restée stable (Ret@K $\approx$ 78,2 %) alors que le pool de compétences augmentait de 10x (de 200 à 2000 compétences), tandis que la baseline GoS se dégradait significativement.
Persistance des Éditions : Les éditions en ligne validées pendant l'entraînement se sont transférées efficacement aux épisodes de test non vus, et le graphe édité récupère plus de compétences de vérité terrain par requête sans évincer les succès précédents (propriété de monotonie d'ensemble).

5. Signification et Revendications

L'article affirme que SkillDAG valide l'hypothèse selon laquelle la structure de graphe fonctionne mieux comme une interface pour les décisions de routage, plutôt que comme une politique opaque.

Inversion de la Conception : En faisant du graphe une interface appelable par l'agent plutôt qu'un substrat de récupérateur fixe, le système permet au LLM de décider comment les preuves structurelles affectent l'exécution.
Robustesse : L'approche isole le gain du pipeline de récupération, montrant que la récupération par graphe typé surpasse le classement par diffusion (PPR) à mesure que la bibliothèque s'étend, sans compter sur l'exécution de l'agent pour corriger un système de récupération défectueux.
Auto-évolution : Le système permet des mises à jour précises et auditables de la structure des compétences basées sur les preuves d'exécution, permettant au graphe d'accumuler des connaissances à travers les épisodes sans curation humaine.

Les auteurs reconnaissent les limites concernant le comportement à long terme de l'auto-évolution à observation unique, notant que bien que les effets d'édition agrégés soient positifs, la stabilité d'une telle évolution sur de très longues périodes reste une question ouverte pour des travaux futurs.