GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

Resumen Técnico: GraphWalker

1. El Problema

La Respuesta a Preguntas sobre Grafos de Conocimiento (KGQA) Agente requiere que un agente interactúe iterativamente con un Grafo de Conocimiento (KG) global para razonar y encontrar respuestas. A pesar del avance de los Modelos de Lenguaje Grandes (LLMs), existen dos cuellos de botella críticos en el estado del arte actual:

• Escasez de datos de entrenamiento: Los métodos basados en prompting carecen de actualizaciones de parámetros dedicadas para navegar KGs ruidosos, mientras que los métodos de entrenamiento suelen limitarse a trayectorias predefinidas o subgrafos extraídos, lo que restringe la capacidad de exploración autónoma.
• Generalización deficiente: Los agentes existentes a menudo fallan al enfrentarse a estructuras de razonamiento fuera de distribución (OOD) o caminos de inferencia complejos no vistos durante el entrenamiento. Además, la optimización por Refuerzo (RL) suele ser ineficaz sin una base sólida de exploración previa (SFT), ya que el agente no puede descubrir trayectorias recompensadas si no sabe explorar el espacio de búsqueda.

2. Metodología: GraphWalker

El artículo propone GraphWalker, un marco de trabajo novedoso que aborda estos desafíos mediante la Síntesis Automatizada de Trayectorias y un Ajuste Fino por Etapas (Stage-wise Fine-tuning). El enfoque se basa en un entorno donde el agente interactúa directamente con el KG global (Freebase) en tiempo real, utilizando herramientas de recuperación (SPARQL).

El proceso de entrenamiento sigue un paradigma de tres fases:

A. Construcción de Datos (Síntesis de Trayectorias)
Se generan dos corpus complementarios para el entrenamiento:

1. GraphSynth-15k (Exploración Amplia): Un conjunto de 15.000 trayectorias sintetizadas automáticamente.
   • Utiliza Caminatas Aleatorias Constrainadas (CRW) sobre el KG para generar estructuras topológicas diversas (cadenas de composición de 2-5 saltos y grafos de conjunción).
   • Se generan preguntas naturales a partir de estas rutas y se filtran semánticamente para asegurar coherencia y evitar fugas de información.
   • Objetivo: Establecer un "prior" de exploración amplia sobre la estructura del KG.
2. GraphRoll-6k (Reflexión y Recuperación): Un conjunto de 6.000 trayectorias de expertos.
   • Generadas mediante muestreo estratificado y validación por rechazo basada en resultados (solo trayectorias con respuesta correcta y evidencia en el historial).
   • Incluyen explícitamente casos de detección de errores, retroceso (backtracking) y recuperación de callejones sin salida.
   • Objetivo: Enseñar al agente a reflexionar sobre observaciones no informativas y corregir su curso.

B. Entrenamiento por Etapas (Two-Stage SFT)

1. Etapa 1 (SFT en GraphSynth): El agente se entrena para internalizar comportamientos de navegación robustos y patrones de invocación de herramientas bajo ruido de recuperación realista. Esto crea una base sólida para explorar estructuras complejas.
2. Etapa 2 (SFT en GraphRoll): Se ajusta el modelo con las trayectorias expertas para desarrollar capacidades de reflexión y autocorrección, enseñando al agente a identificar cuándo un camino es erróneo y cómo recuperarse.

C. Optimización por Refuerzo (RL)

• Tras el SFT de dos etapas, se aplica Optimización de Política Relativa por Grupos (GRPO).
• Se utiliza una recompensa dispersa basada en la coincidencia exacta (Exact Match - EM) a nivel de trayectoria.
• Gracias a los priors establecidos en las etapas anteriores, este RL ligero es suficiente para empujar el rendimiento más allá del "techo" del SFT, alineando la toma de decisiones a largo plazo sin necesidad de supervisión densa intermedia.

3. Contribuciones Clave

• Identificación y Solución de la Escasez de Datos: Se identifica la falta de datos de entrenamiento diversos como el principal obstáculo para la generalización en KGQA agéntica. Se proponen dos datasets sintéticos complementarios (GraphSynth y GraphRoll) que cubren tanto la exploración estructural como la recuperación de errores.
• Paradigma de Entrenamiento por Etapas: Se demuestra que un orden de entrenamiento específico (primero exploración amplia, luego refinamiento con expertos) es crucial. Un entrenamiento mixto o sin esta secuencia resulta significativamente inferior.
• Desbloqueo del Techo de Rendimiento: Se demuestra empíricamente que el SFT de dos etapas actúa como un andamio que permite que una optimización RL posterior sea efectiva, logrando un rendimiento superior al de los métodos puramente RL o puramente SFT.

4. Resultados Experimentales

Los experimentos se realizaron en los benchmarks estándar CWQ (Complex WebQuestions) y WebQSP, además de GrailQA y un nuevo conjunto de pruebas GraphWalkerBench (con estructuras no vistas).

• Rendimiento de Estado del Arte (SOTA): GraphWalker supera a todos los métodos basados en prompting y entrenamiento existentes.
  • En CWQ, alcanza un 79.6% de Exact Match (EM) con un modelo de 7B, superando a métodos como GoG (+4.4%) y KG-Agent (+7.4%).
  • En WebQSP, logra un 91.5% de EM, superando a modelos entrenados directamente en ese dataset.
• Generalización Zero-Shot: El modelo muestra una capacidad excepcional para transferir lo aprendido a estructuras no vistas. En GraphWalkerBench, que contiene estructuras de conjunción y composiciones profundas no presentes en los datos de entrenamiento, GraphWalker mantiene un rendimiento alto, mientras que los modelos sin la Etapa 1 de GraphSynth sufren caídas drásticas (-6.8% a -11.1% de EM).
• Análisis de Ablación:
  • Eliminar la Etapa 1 (GraphSynth) reduce la capacidad de exploración (menor Pass@k).
  • Eliminar la Etapa 2 (GraphRoll) degrada severamente la capacidad de corrección de errores.
  • Eliminar RL reduce el rendimiento final, confirmando que el RL es necesario para refinar la política, pero solo funciona bien con el pre-entrenamiento adecuado.

5. Significado e Impacto

GraphWalker representa un avance significativo en la integración de LLMs con bases de conocimiento estructuradas. Su principal contribución es demostrar que la calidad y diversidad del curriculum de entrenamiento (síntesis de trayectorias) son más críticas que simplemente aumentar la escala del modelo o la complejidad del algoritmo de RL.

Al permitir que los agentes naveguen en KGs globales completos (en lugar de subgrafos pre-extraídos) y desarrollen habilidades de autocorrección, GraphWalker ofrece una solución escalable y robusta para el razonamiento complejo en entornos de conocimiento real, llenando la brecha entre la capacidad de razonamiento de los LLMs y la necesidad de precisión factual de los sistemas basados en grafos. El código y los datos están disponibles públicamente, fomentando la reproducibilidad y el avance futuro en el campo.