GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs

1. Problématique

Le routage des modèles de langage (LLM) vise à équilibrer performance et efficacité en sélectionnant le modèle le plus adapté pour une requête donnée. Cependant, les méthodes existantes souffrent de limitations majeures dans des scénarios réalistes et complexes :

• Routage statique ou simple : Les routeurs "single-round" (un seul tour) assignent une requête à un modèle unique sans capacité de raisonnement itératif, de décomposition de tâche ou de coordination entre plusieurs agents.
• Manque de collaboration explicite : Les routeurs "multi-round" existants traitent souvent les appels successifs comme indépendants, sans modéliser explicitement la collaboration entre des agents hétérogènes, ce qui entraîne des appels redondants et des conflits de contexte.
• Sous-utilisation de la mémoire : Les systèmes actuels ne tirent pas pleinement parti des mémoires historiques riches (traces d'interactions passées, patterns de collaboration réussis) pour améliorer le routage futur.
• Défi du routage agentic : Dans un cadre "agentic", le routeur doit non seulement choisir le modèle de base (LLM backbone), mais aussi décider du rôle de l'agent (Planificateur, Exécutant, Résumé) à chaque étape, ce qui nécessite une gestion de récompenses différées et une compréhension des dépendances complexes.

2. Méthodologie : GraphPlanner

Les auteurs proposent GraphPlanner, un routeur agentic hétérogène augmenté par la mémoire, conçu pour générer des flux de travail (workflows) dynamiques pour chaque requête.

A. Formulation comme Processus de Décision de Markov (MDP)

La génération du flux de travail est formulée comme un MDP $(S, A, T, r, \gamma)$ :

• État ($S$) : Représente la requête en cours de résolution. Le contexte est capturé implicitement via la structure du flux de travail évolutif.
• Action ($A$) : À chaque étape, le routeur sélectionne une paire $(\alpha_t, m_t)$, où $\alpha_t$ est le rôle de l'agent (Planificateur, Exécutant, Résumé) et $m_t$ est le modèle LLM de base choisi parmi une pool hétérogène.
• Transition ($T$) :
  • Planificateur : Décompose la requête en sous-requêtes.
  • Exécutant : Résout une sous-requête.
  • Résumé : Agrège les réponses intermédiaires.
• Récompense ($r$) : Un compromis entre l'utilité de la tâche (précision, BLEU, etc.) et le coût computationnel (nombre de tokens, coût financier).

B. Architecture Graphique Hétérogène (GARNet)

Le cœur de GraphPlanner est GARNet (Graph-Augmented Routing Network), un réseau de neurones graphiques hétérogènes qui intègre deux types de mémoires :

1. Mémoire de flux de travail ($G_{workflow}$) : Capture l'état actuel de la requête, les sous-requêtes générées et les réponses en cours.
2. Mémoire historique ($G_{history}$) : Stocke les interactions passées (requêtes, réponses, modèles utilisés) pour apprendre des patterns de collaboration réussis.

Mécanisme clé : Le graphe utilise des nœuds de rôle partagés (hub nodes) pour chaque paire (LLM, Rôle). Ces nœuds servent d'ancres structurelles entre le graphe de travail actuel et le graphe historique. Cela permet au modèle de propager l'information à travers les tours de conversation et d'intégrer l'expérience passée sans créer de redondance structurelle.

C. Entraînement par Apprentissage par Renforcement (RL)

Le réseau de politique est optimisé via PPO (Proximal Policy Optimization). L'agent apprend à maximiser le retour espéré (réussite de la tâche moins le coût) en explorant différentes combinaisons de rôles et de modèles. Le système supporte deux modes d'inférence :

• Inductif : Génération de décisions sans réutilisation explicite des interactions historiques lors de l'inférence (plus léger).
• Transductif : Utilisation des interactions historiques stockées pour enrichir le contexte (meilleure performance, coût plus élevé).

3. Contributions Clés

1. Routage Agentic Hétérogène : Première approche à généraliser le routage comme un problème de coordination multi-agents, sélectionnant simultanément le modèle et le rôle fonctionnel.
2. Mémoire Graphique Hétérogène (GARNet) : Une architecture innovante qui fusionne la mémoire de travail immédiate et la mémoire historique via un graphe hétérogène, permettant un raisonnement contextuel riche et une généralisation robuste.
3. Optimisation Jointe Performance-Coût : Utilisation du RL pour trouver automatiquement le compromis optimal entre la précision de la réponse et le coût computationnel, surpassant les approches statiques.
4. Généralisation Zero-Shot : Démonstration d'une capacité à fonctionner sur des tâches et des modèles LLM jamais vus durant l'entraînement, grâce à la structure abstraite du graphe.

4. Résultats Expérimentaux

L'évaluation a été menée sur 14 tâches couvrant 6 domaines (Mathématiques, Code, Raisonnement, Connaissance mondiale, etc.) et incluant des tests hors domaine.

• Performance Supérieure :
  • Phase 1 (Optimisation dans un flux existant) : Amélioration de la précision moyenne de +3,8 % par rapport aux meilleurs routeurs de base.
  • Phase 2 (Génération de flux optimaux) : Amélioration de la précision moyenne de +9,3 % par rapport aux routeurs multi-tours les plus avancés (comme Router-R1).
• Efficacité Computationnelle :
  • Réduction drastique du coût GPU : de 186,26 GiB (pour les méthodes RL existantes) à 1,04 GiB pour GraphPlanner.
  • Réduction du nombre d'appels LLM et des tokens utilisés.
  • GraphPlanner se situe sur la frontière de Pareto, offrant le meilleur compromis précision/coût.
• Généralisation :
  • Tâches invisibles : Atteint 78 % de précision moyenne sur des tâches hors domaine (LogicGrid, MGSM, CommonGen), surpassant les autres routeurs de 20 à 40 %.
  • Modèles invisibles : Fonctionne efficacement sur des LLMs non vus durant l'entraînement (ex: Mixtral 8x22b) sans fine-tuning.
• Ablations : L'étude montre que la suppression de la mémoire historique ou l'utilisation d'un graphe homogène entraîne une chute significative des performances, validant l'importance de l'architecture GARNet.

5. Signification et Impact

GraphPlanner représente une avancée majeure dans l'ingénierie des systèmes d'agents LLM. En passant d'un routage statique à un routage dynamique et collaboratif, il permet de débloquer le plein potentiel des systèmes multi-agents hétérogènes.

• Adaptabilité : Le système s'adapte à la complexité de la tâche (décomposition profonde pour les problèmes de mathématiques, exécution directe pour les questions simples).
• Évolutivité : L'approche basée sur le graphe et le RL permet de scaler vers des écosystèmes d'agents plus vastes et plus diversifiés.
• Efficacité : En réduisant considérablement les coûts de calcul tout en augmentant la précision, GraphPlanner rend les systèmes d'agents complexes économiquement viables pour des applications réelles.

Ce travail ouvre la voie à des systèmes d'IA plus autonomes capables de planifier, de collaborer et d'apprendre de leurs interactions passées de manière structurée. Le code est disponible publiquement pour favoriser la reproductibilité.