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

1. Il Problema

Il routing dei Large Language Models (LLM) è diventato cruciale per bilanciare efficienza e prestazioni selezionando il modello più adatto per una data query. Tuttavia, le metodologie esistenti presentano limiti significativi:

• Router a turno singolo (Single-round): Assegnano una query a un modello in un'unica chiamata basandosi su embedding o classificatori. Manca la capacità di ragionamento multi-step, decomposizione del compito o coordinamento tra modelli diversi.
• Router a turno multiplo (Multi-round): Migliorano la flessibilità intercalando ragionamento e routing, ma trattano ogni chiamata come indipendente. Non modellano esplicitamente la collaborazione tra agenti, portando a chiamate ridondanti, conflitti contestuali e mancato sfruttamento delle capacità complementari dei diversi modelli.
• Mancanza di memoria storica: I sistemi attuali non sfruttano sistematicamente le tracce storiche delle interazioni passate (pattern di collaborazione di successo, modalità di errore) per migliorare il coordinamento futuro.

L'obiettivo è estendere il routing a ambienti agentici, dove il sistema deve non solo scegliere il modello (backbone), ma anche decidere il ruolo dell'agente (es. Pianificatore, Esecutore, Riassuntore) e orchestrare un flusso di lavoro collaborativo dinamico.

2. Metodologia: GraphPlanner

GraphPlanner è un router agentic eterogeneo basato su memoria grafica che genera flussi di lavoro (workflow) per ogni query.

Formulazione come Processo Decisionale di Markov (MDP)

Il paper formula la generazione del workflow come un MDP $(S, A, T, r, \gamma)$:

• Stato ($S$): La query corrente da risolvere.
• Azione ($A$): Una coppia $(\alpha_t, m_t)$ che seleziona contemporaneamente il ruolo dell'agente (Planner, Executor, Summarizer) e il modello LLM (backbone) da invocare.
• Transizione ($T$): Aggiorna il flusso di lavoro. Un "Planner" scompone la query in sottodomande; un "Executor" genera risposte; un "Summarizer" aggrega i risultati.
• Ricompensa ($r$): Bilancia l'utilità del compito (accuratezza) e il costo computazionale.

Memoria Eterogenea (GARNet)

Il cuore del sistema è GARNet, un grafo eterogeneo che integra due tipi di memoria:

1. G_workflow: Memorizza lo stato corrente del flusso di lavoro (query, risposte, ruoli attivi).
2. G_history: Memorizza le interazioni passate tra query, agenti e risposte.

Architettura del Grafo:

• Nodi: Query, Risposte e Hub di Ruolo (LLM + Ruolo).
• Nodi Hub Condivisi: Un set fisso di nodi hub rappresenta ogni combinazione (LLM, Ruolo). Questi nodi fungono da ponte tra il grafo del workflow corrente e quello storico, permettendo di aggregare informazioni senza creare nodi ridondanti ad ogni passo.
• Codifica: Utilizza un doppio schema di codifica. Prima si codifica la memoria storica per aggiornare gli embedding degli hub di ruolo, che vengono poi iniettati nel codificatore del workflow corrente. Questo permette al sistema di comprendere come i ruoli hanno interagito in passato e come stanno evolvendo ora.

Ottimizzazione

L'intera pipeline è ottimizzata tramite Reinforcement Learning (PPO - Proximal Policy Optimization). L'agente impara a massimizzare la ricompensa cumulata (accuratezza meno costo) scegliendo dinamicamente la sequenza di azioni (ruolo + modello) più efficiente.

3. Contributi Chiave

1. Routing Agentic Eterogeneo: Sposta il paradigma dal semplice "quale modello scegliere" a "quale workflow collaborativo costruire", selezionando dinamicamente ruoli e modelli.
2. Memoria Grafica Ibrida (GARNet): Introduce un meccanismo innovativo per integrare memoria storica e memoria di workflow corrente tramite un grafo eterogeneo, permettendo sia inferenza induttiva (senza memoria storica specifica) che transdutiva (sfruttando la memoria storica).
3. Efficienza e Prestazioni: Dimostra che un approccio basato su RL e grafi può superare i router statici e sequenziali, riducendo drasticamente i costi computazionali.
4. Generalizzazione Robusta: Il modello mostra forti capacità zero-shot su task e modelli LLM mai visti durante l'addestramento.

4. Risultati Sperimentali

Il sistema è stato valutato su 14 task in 6 domini (Matematica, Codice, Ragionamento, Conoscenza Mondiale, ecc.) confrontandolo con router a turno singolo e multiplo.

• Prestazioni Superiori:
  • Fase 1 (Ottimizzazione in workflow esistenti): Migliora l'accuratezza media del +3.8% rispetto ai baseline.
  • Fase 2 (Generazione di workflow ottimali): Migliora l'accuratezza media del +9.3% rispetto al miglior baseline.
  • Riduzione dei costi GPU da 186.26 GiB a 1.04 GiB (rispetto a metodi RL complessi come Router-R1).
• Generalizzazione Zero-Shot:
  • Su task non visti (es. LogicGrid, MGSM, CommonGen), GraphPlanner raggiunge un'accuratezza media del 78%, superando di 20-40 punti percentuali i router precedenti.
  • Si adatta efficacemente a LLM mai visti durante l'addestramento senza bisogno di ulteriore fine-tuning.
• Efficienza:
  • GraphPlanner si posiziona sulla frontiera di Pareto, offrendo il miglior compromesso tra accuratezza e costo.
  • Richiede meno tempo di training (120 minuti totali) e meno token rispetto ai metodi supervisionati o RL basati su prompt.
• Ablazioni:
  • L'uso della memoria storica e la struttura eterogenea del grafo sono fondamentali: rimuoverli causa un crollo delle prestazioni.
  • La modalità transdutiva (con memoria storica) offre la massima accuratezza, mentre quella induttiva offre un'efficienza superiore con prestazioni comunque competitive.

5. Significato e Impatto

GraphPlanner rappresenta un passo avanti significativo verso sistemi multi-agente scalabili e cooperativi.

• Superamento dei limiti attuali: Risolve il problema della mancanza di coordinamento nei router multi-round, trasformando chiamate indipendenti in flussi di lavoro strutturati.
• Sostenibilità: Dimostra che è possibile ottenere prestazioni di stato dell'arte riducendo drasticamente l'impronta computazionale e i costi, rendendo l'uso di sistemi multi-agente più accessibile.
• Flessibilità: La capacità di adattarsi a nuovi ruoli (es. "Thinker", "Verifier") e nuovi modelli LLM senza riaddestramento completo apre la strada a ecosistemi di agenti LLM più dinamici e resilienti.

In sintesi, GraphPlanner non è solo un selettore di modelli, ma un orchestratore intelligente che impara a costruire e gestire collaborazioni complesse tra agenti eterogenei, sfruttando la memoria storica per prendere decisioni di routing sempre più efficaci.