GTA: Graph Theory Agent e benchmark per il ragionamento algoritmico sui grafi con gli LLM

Abstract degli autori

Ai modelli linguistici di grandi dimensioni (LLM) viene sempre più spesso chiesto di ragionare su dati strutturati come i grafi, ma non è ancora chiaro quanto siano affidabili nell’eseguire algoritmi sui grafi in più passaggi usando il linguaggio naturale. Le valutazioni esistenti tendono a basarsi su compiti semplici con grafi piccoli, a valutare la generazione di codice anziché il ragionamento sul grafo in sé, oppure a fissare un unico formato di input. Presentiamo Graph Theory Bench (GT Bench), un benchmark che comprende 24 problemi classici di teoria dei grafi in 44 configurazioni della struttura dei compiti, con oltre 100.000 esempi in quattro rappresentazioni: linguaggio naturale, linguaggio strutturato, liste di adiacenza e matrici di adiacenza. La valutazione di otto LLM su GT Bench mostra che la precisione dipende strettamente dalla rappresentazione dell’input, che la rappresentazione migliore varia in funzione della densità, delle dimensioni e della topologia del grafo, oltre che del modello, e che questa sensibilità persiste, seppure attenuata, nei modelli di ragionamento più avanzati. Sulla base di queste osservazioni, proponiamo Graph Theory Agent (GTA), che abbina un selettore di rappresentazione addestrato sulle preferenze a una struttura di pianificazione e scomposizione applicata a un LLM esecutore congelato. GTA porta Phi-4 dal 53,5% al 69,1% nella partizione facile del benchmark e dal 33,0% al 41,5% in quella difficile, superando otto baseline basate su prompting e agenti; inoltre, viene trasferito a GraCoRe e NLGraph senza riaddestramento. Codice per la generazione e la valutazione del benchmark: https://github.com/xzx34/GTA. La homepage del progetto è disponibile all’indirizzo https://xzx34.github.io/gta/.