Évaluer les modèles de langage dans la résolution de problèmes de graphes

Les grands modèles de langage (LLMs) sont des outils qui peuvent faire plein de tâches liées aux langues. Ils commencent à être utilisés pour des jobs qui impliquent des graphes, comme la planification, répondre à des questions et du raisonnement. Un graphe, c'est un peu comme une carte où des points (appelés nœuds) sont liés par des lignes (appelées arêtes). C'est super important de comprendre si ces modèles peuvent vraiment gérer des problèmes de graphes, surtout quand les problèmes sont décrits en langage courant.

Pour explorer ça, on a créé un nouveau benchmark appelé NLGraph, qui signifie Graphes en Langage Naturel. Ce benchmark a plein de problèmes-29 370 précisément-répartis sur huit types de tâches graphiques différentes. Les tâches varient en complexité, allant de simples questions sur la connexion de deux points à des trucs plus compliqués comme trouver le meilleur chemin dans un réseau de connexions.

On a testé plusieurs modèles de langage, y compris GPT-3 et GPT-4, en utilisant différentes manières de les guider dans leurs réponses. Nos résultats montrent que :

1. Les modèles de langage peuvent montrer une certaine capacité à raisonner sur les graphes.
2. Les avantages des méthodes de prompting avancées s'effacent quand il s'agit de problèmes graphiques complexes.
3. Les modèles peuvent avoir du mal avec des motifs trompeurs dans les graphes qu'ils analysent.

On a introduit deux nouvelles méthodes pour améliorer les performances des modèles : le "Build-a-Graph Prompting" et l'"Algorithmic Prompting". Ces méthodes ont amélioré les scores des modèles sur les tâches NLGraph de 3% à 17% en fonction de la tâche.

#Qu'est-ce que NLGraph ?

NLGraph est un ensemble de défis conçu pour tester si les modèles de langage peuvent résoudre des problèmes graphiques décrits en langage naturel. Ça inclut des problèmes de niveaux de difficulté variés et cible huit tâches spécifiques qui impliquent le raisonnement sur les graphes.

Les huit tâches qu'on a incluses sont :

1. Connectivité : Déterminez si deux nœuds sont connectés.
2. Cycle : Identifiez s'il y a un chemin qui commence et finit au même nœud.
3. Tri Topologique : Arrangez les nœuds de manière à respecter la direction des arêtes dans les graphes orientés.
4. Chemin le plus court : Trouvez le chemin entre deux nœuds qui a le poids total le plus faible.
5. Flux Maximum : Déterminez la quantité maximale de flux qui peut passer d'un nœud à un autre.
6. Appariement de Graphe Bipartite : Trouvez des paires de nœuds de deux groupes qui peuvent être appariées sans partager un nœud.
7. Chemin Hamiltonien : Identifiez un chemin qui visite chaque nœud exactement une fois.
8. Réseaux de Neurones Graphiques : Simulez un processus où les valeurs des nœuds sont mises à jour à travers plusieurs couches selon certaines règles.

En générant divers graphes avec différentes propriétés, on a créé des problèmes pour ces tâches et on les a regroupés en catégories faciles, moyennes et difficiles. Ça permet une analyse détaillée de la façon dont les modèles de langage peuvent performer en raisonnement graphique.

#Tester les Modèles de Langage

En utilisant le benchmark NLGraph, on voulait voir si les modèles de langage pouvaient résoudre précisément des problèmes graphiques et comment différentes méthodes de prompting peuvent influencer leur performance.

Nos étapes principales étaient :

1. Établir des Références : On a testé diverses approches pour guider les modèles, y compris sans indices (zero-shot), en fournissant quelques exemples (few-shot), et en utilisant un raisonnement séquentiel (chain-of-thought). On a aussi inclus une référence de devinette aléatoire pour comparer.

2. Évaluer les Modèles : On s'est concentrés sur des modèles comme text-davinci-003 et d'autres pour voir comment ils performent sur les différentes tâches.

#Principaux Résultats

1. Raisonnement Graphique Préliminaire : Pour les tâches plus simples, les modèles de langage ont bien performé, montrant qu'ils peuvent raisonner sur des graphes dans une certaine mesure. Ils ont eu des scores beaucoup mieux que des devinettes aléatoires, ce qui suggère un certain niveau de compréhension de la structure des graphes.

2. Problèmes Complexes : Quand les problèmes devenaient plus complexes, l'efficacité des méthodes de prompting avancées était minimale. Ça indique que, même si les modèles peuvent gérer des tâches simples, ils ont des difficultés avec un raisonnement plus compliqué.

3. Performance Fragile : On a aussi trouvé que les modèles s’appuyaient souvent sur des motifs trompeurs plutôt que d'analyser vraiment les graphes. Par exemple, les modèles jugeaient parfois la connectivité en fonction de la fréquence d'apparition des nœuds dans les prompts, plutôt qu'en comprenant la vraie structure du graphe.

#Améliorer les Capacités de Raisonnement Graphique

Pour aider à améliorer la capacité des modèles à résoudre des problèmes de graphes, on a proposé deux nouvelles méthodes :

#Build-a-Graph Prompting (BaG)

Avec cette méthode, on guide le modèle à d'abord comprendre la structure du graphe en lui demandant de visualiser ou d’imaginer les connexions avant de résoudre un problème spécifique. Par exemple, après avoir donné la description d'un graphe, on invite le modèle : "Construisons d'abord un graphe avec les nœuds et les arêtes." Ça permet au modèle de clarifier sa compréhension avant d'essayer de répondre aux questions basées sur le graphe.

#Algorithmic Prompting

Dans cette technique, on demande au modèle de revoir les algorithmes pertinents relatifs à la tâche. Par exemple, avant un problème sur la recherche du chemin le plus court, on pourrait dire, "On peut utiliser un algorithme de Recherche en Profondeur (DFS)." Cette guidance structurée encourage les modèles à réfléchir aux étapes de résolution de problèmes qu'ils doivent suivre.

#Performance des Tâches dans NLGraph

On a réalisé plusieurs tests en utilisant ces méthodes sur différentes tâches. Voici comment les modèles ont performé :

1. Tâches de Connectivité et de Cycle : Sur les tâches plus faciles comme déterminer la connectivité et trouver des Cycles, l'utilisation des méthodes BaG et d'algorithmic prompting a conduit à une amélioration significative des performances.

2. Tâche de Chemin le Plus Court : De même, pour la tâche du chemin le plus court, les modèles utilisant nos techniques ont montré de meilleurs résultats.

3. Tâches Complexes : Cependant, pour les tâches plus difficiles, comme le chemin hamiltonien, ces méthodes ont eu peu d'effet, montrant que l'amélioration des performances sur ces types de problèmes reste un défi complexe.

#Conclusion

En conclusion, notre enquête sur la capacité des modèles de langage à résoudre efficacement des problèmes de graphes montre des résultats prometteurs, surtout pour les tâches plus simples. Bien qu'ils montrent des capacités initiales, le raisonnement complexe sur les graphes est encore un domaine qui nécessite beaucoup d'exploration. Les méthodes que nous avons proposées peuvent améliorer les performances sur certaines tâches, mais de nombreux défis demeurent. Les recherches futures devront se concentrer sur des moyens de renforcer les compétences des modèles pour gérer ces problèmes avancés de graphes.

En avançant, NLGraph offre une ressource riche pour tester davantage et développer des méthodes pour améliorer comment les modèles de langage analysent et raisonnent sur les graphes et leurs structures. La compréhension acquise en abordant ces tâches sera essentielle pour exploiter pleinement les capacités des modèles de langage dans diverses applications pratiques.