Evaluando Modelos de Lenguaje en la Resolución de Problemas de Grafos

Los modelos de lenguaje grandes (LLMs) son herramientas que pueden hacer muchas cosas relacionadas con el lenguaje. Ahora se están usando para trabajos que involucran gráficos, como planificación, responder preguntas y razonamiento. Un gráfico es como un mapa donde los puntos (llamados nodos) están conectados por líneas (llamadas aristas). Es importante entender si estos modelos realmente pueden manejar problemas de gráficos, especialmente cuando los problemas se describen en el lenguaje cotidiano.

Para investigar esto, creamos un nuevo estándar llamado NLGraph, que significa Gráfico de Lenguaje Natural. Este estándar tiene un montón de problemas-29,370 para ser exactos-en ocho tipos diferentes de tareas gráficas. Las tareas varían en complejidad, desde preguntas simples sobre si dos puntos están conectados hasta problemas más complicados como encontrar la mejor ruta a través de una red de conexiones.

Probamos varios modelos de lenguaje, incluidos GPT-3 y GPT-4, usando diferentes maneras de motivar o guiar sus respuestas. Nuestros hallazgos muestran que:

1. Los modelos de lenguaje pueden mostrar cierta habilidad para razonar sobre gráficos.
2. Las ventajas de los métodos de prompting avanzados desaparecen cuando se trata de problemas de gráficos complejos.
3. Los modelos pueden tener dificultades con patrones engañosos en los gráficos que analizan.

Introdujimos dos nuevos métodos para mejorar el rendimiento de los modelos: Construir un Gráfico con Indicación y Algoritmos de Indicación. Estos métodos mejoraron las puntuaciones de los modelos en las tareas de NLGraph entre un 3% y un 17% según la tarea.

#¿Qué es NLGraph?

NLGraph es un conjunto de desafíos diseñado para probar si los modelos de lenguaje pueden resolver problemas de gráficos descritos en lenguaje natural. Incluye problemas de diferentes niveles de dificultad y se enfoca en ocho tareas específicas que involucran razonamiento gráfico.

Las ocho tareas que incluimos son:

1. Conectividad: Determinar si dos nodos están conectados.
2. Ciclo: Identificar si hay un camino que comienza y termina en el mismo nodo.
3. Ordenamiento Topológico: Organizar nodos de una manera que respete la dirección de las aristas en gráficos orientados.
4. Camino más corto: Encontrar el camino entre dos nodos que tenga el peso total más pequeño.
5. Flujo Máximo: Determinar la cantidad máxima de flujo que puede pasar de un nodo a otro.
6. Emparejamiento de Gráficos Bipartitos: Encontrar pares de nodos de dos grupos que pueden ser emparejados sin compartir un nodo.
7. Camino de Hamilton: Identificar un camino que visita cada nodo exactamente una vez.
8. Redes Neuronales de Gráficos: Simular un proceso donde los valores de los nodos se actualizan a través de múltiples capas según ciertas reglas.

Al generar varios gráficos con diferentes propiedades, creamos problemas para estas tareas y los agrupamos en categorías fáciles, medias y difíciles. Esto permite un análisis detallado de cuán bien los modelos de lenguaje pueden desempeñarse en el razonamiento gráfico.

#Pruebas de los Modelos de Lenguaje

Usando el estándar NLGraph, queríamos ver si los modelos de lenguaje podrían resolver con precisión problemas de gráficos y cómo diferentes métodos de prompting pueden afectar su rendimiento.

Nuestros pasos principales fueron:

1. Establecer Líneas Base: Probamos varios enfoques para motivar a los modelos, incluyendo sin pistas (zero-shot), proporcionando algunos ejemplos (few-shot), y usando razonamiento secuencial (chain-of-thought). También incluimos una línea base de adivinanza aleatoria para comparación.

2. Evaluar Modelos: Nos enfocamos en modelos como text-davinci-003 y otros para ver cómo se desempeñaron en las diferentes tareas.

#Hallazgos Clave

1. Razonamiento Gráfico Preliminar: En tareas más simples, los modelos de lenguaje se desempeñaron bien, mostrando que pueden razonar sobre gráficos hasta cierto punto. Obtuvieron mejores resultados que la adivinanza aleatoria, lo que sugiere que había cierta comprensión de la estructura del gráfico.

2. Problemas Complejos: Cuando los problemas se volvieron más complejos, la efectividad de los métodos de prompting avanzados fue mínima. Esto indica que, aunque los modelos pueden manejar tareas directas, tienen dificultades con razonamientos más intrincados.

3. Rendimiento Frágil: También encontramos que los modelos a menudo dependían de patrones engañosos en lugar de analizar realmente los gráficos. Por ejemplo, a veces los modelos juzgaban la conectividad basándose en cuántas veces aparecían los nodos en los prompts, en lugar de entender la estructura real del gráfico.

#Mejorando las Habilidades de Razonamiento Gráfico

Para ayudar a mejorar la capacidad de los modelos para resolver problemas de gráficos, propusimos dos nuevos métodos:

#Construcción de Gráfico con Indicación (BaG)

Con este método, guiamos al modelo para que primero entienda la estructura del gráfico pidiéndole que visualice o imagine las conexiones antes de resolver un problema específico. Por ejemplo, después de dar la descripción de un gráfico, motivamos al modelo diciendo: "Primero, construyamos un gráfico con los nodos y las aristas." Esto permite que el modelo aclare su comprensión antes de intentar responder preguntas basadas en el gráfico.

#Algoritmos de Indicación

En esta técnica, pedimos al modelo que revise los algoritmos relevantes relacionados con la tarea en cuestión. Por ejemplo, antes de un problema sobre encontrar el camino más corto, podríamos decir: "Podemos usar un algoritmo de Búsqueda en Profundidad (DFS)." Esta guía estructurada anima a los modelos a pensar sobre los pasos que necesitan seguir para resolver el problema.

#Rendimiento de las Tareas en NLGraph

Realizamos varias pruebas utilizando estos métodos en varias tareas. Así es como se desempeñaron los modelos:

1. Tareas de Conectividad y Ciclo: En tareas más fáciles como determinar conectividad y encontrar Ciclos, usar los métodos BaG y de algoritmos llevó a una mejora significativa en el rendimiento.

2. Tarea de Camino más Corto: De manera similar, para la tarea del camino más corto, los modelos que usaron nuestras técnicas de colocación mostraron mejores resultados.

3. Tareas Complejas: Sin embargo, para las tareas más desafiantes, como el camino de Hamilton, estos métodos tuvieron poco efecto, mostrando que mejorar el rendimiento en estos tipos de problemas sigue siendo un desafío complejo.

#Conclusión

En conclusión, nuestra investigación sobre si los modelos de lenguaje pueden resolver efectivamente problemas de gráficos muestra resultados prometedores, especialmente para tareas más simples. Si bien muestran habilidades iniciales, el razonamiento complejo en gráficos sigue siendo un área que necesita mucha exploración. Los métodos que propusimos pueden mejorar el rendimiento en algunas tareas, pero quedan muchos desafíos por delante. La investigación futura tendrá que enfocarse en maneras de fortalecer las habilidades de los modelos para manejar estos problemas avanzados de gráficos.

A medida que avancemos, NLGraph proporciona un recurso rico para seguir probando y desarrollando métodos para mejorar cómo los modelos de lenguaje analizan y razonan sobre gráficos y sus estructuras. La comprensión obtenida al enfrentar estas tareas será clave para aprovechar al máximo las capacidades de los modelos de lenguaje en una variedad de aplicaciones prácticas.