Resumen Técnico: GraphPO - Optimización de Políticas Basada en Grafos para Modelos de Razonamiento

1. Planteamiento del Problema

El Aprendizaje por Refuerzo con Recompensas Verificables (RLVR) se ha convertido en el paradigma estándar para mejorar los Grandes Modelos de Razonamiento (LRM). Sin embargo, los métodos actuales de RLVR enfrentan dos limitaciones primarias:

1. Exploración Redundante: El muestreo independiente de respuestas a menudo resulta en trayectorias diferentes que contienen pasos de razonamiento intermedios similares. Esto conduce a un desperdicio de computación y limita la diversidad de la exploración.
2. Señales de Recompensa Dispersas: El RLVR típicamente depende de recompensas de respuesta final binarias. Esta dispersión dificulta la asignación de crédito a pasos de razonamiento intermedios específicos que contribuyen a la respuesta final.

Aunque los métodos basados en árboles (por ejemplo, TreeRL, PROS) abordan parte de la redundancia mediante el uso de prefijos compartidos y la provisión de señales finas en los puntos de ramificación, estos siguen tratando las ramas divergentes como caminos independientes. En consecuencia, si diferentes ramas alcanzan estados intermedios semánticamente similares, no pueden compartir información, lo que conduce a una exploración repetitiva y a una mayor varianza en la estimación de la ventaja.

2. Metodología: GraphPO

Los autores proponen GraphPO, un nuevo marco de RL que modela los despliegues (rollouts) de razonamiento como un Grafo Acíclico Dirigido (DAG) en lugar de una cadena o un árbol.

2.1 Construcción y Fusión de Grafos

• Estructura: En GraphPO, los pasos de razonamiento se representan como aristas (edges), y los estados semánticos intermedios (resumidos a partir de la ruta de razonamiento que comienza desde el prompt) se representan como nodos.
• Clases de Equivalencia: El marco construye incrementalmente el grafo detectando estados semánticamente similares a través de diferentes rutas utilizando incrustaciones (embeddings) de nodos (vía similitud de coseno). Cuando la similitud supera un umbral $\kappa$, los nodos se fusionan en clases de equivalencia.
• Reasignación de Presupuesto: Cuando una ruta alcanza una clase de equivalencia existente, la expansión posterior se considera probablemente redundante. GraphPO reduce a la mitad el presupuesto de la siguiente capa para esa ruta (manteniendo al menos una continuación) y reasigna la computación ahorrada a estados de frontera novedosos, fomentando así una exploración más amplia.

2.2 Recompensa de Grafo (Supervisión de Proceso a partir de Resultados)

GraphPO convierte las recompensas de resultados dispersas en recompensas densas por paso sin requerir etiquetas de proceso anotadas:

• Calificación de Estados: A cada nodo se le asigna una puntuación basada en las respuestas verificadas alcanzables desde él. Si un nodo pertenece a una clase de equivalencia, su puntuación se agrupa con las puntuaciones de otros nodos en esa clase, ponderada por un coeficiente de agrupación $w$.
• Recompensas de Paso: La recompensa para una arista específica (paso) se calcula como la diferencia en las puntuaciones de estado entre los nodos de destino y origen, descontada por la similitud entre los extremos. Esto permite que las ramas que se detienen prematuramente reciban crédito de sus socios equivalentes que alcanzaron correctamente una respuesta.

2.3 Ventaja de Doble Grupo de Grafos

Para mejorar tanto la eficiencia del razonamiento como la asignación de crédito, GraphPO introduce una estimación de ventaja de doble grupo:

1. Grupo de Corrección ($A_{cor}$): Compara los pasos salientes desde el mismo estado semántico. Calcula la ventaja de un paso específico en relación con otros pasos que salen del mismo estado, proporcionando una asignación de crédito fina.
2. Grupo de Eficiencia ($A_{eff}$): Compara las rutas entrantes que alcanzan el mismo estado fusionado. Recompensa las rutas más cortas (menos tokens/pasos) que alcanzan un estado semántico útil, incentivando a la política a encontrar trayectorias de razonamiento más eficientes.

2.4 Optimización de la Política

La política se optimiza utilizando un objetivo de estilo PPO que combina la ventaja de doble grupo ($A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$). La función objetivo maximiza el retorno esperado mientras mantiene una restricción de divergencia KL respecto a una política de referencia.

3. Contribuciones Clave

• Marco de Despliegue Basado en Grafos: GraphPO es el primer marco de RL que representa los despliegues de razonamiento como un DAG, agregando explícitamente estados de razonamiento equivalentes para permitir el intercambio de sufijos y la reasignación de presupuesto.
• Estimación de Ventaja de Doble Grupo: El artículo propone un método para optimizar simultáneamente la corrección del razonamiento (comparando pasos salientes) y la eficiencia del razonamiento (comparando rutas entrantes), reduciendo la varianza de la estimación de la ventaja.
• Supervisión de Proceso sin Anotaciones: El método deriva supervisión densa por paso a partir de recompensas de resultados dispersas aprovechando la estructura del grafo y las clases de equivalencia, eliminando la necesidad de costosas anotaciones de Modelos de Recompensa de Proceso (PRM).

4. Resultados Experimentales

Los experimentos se realizaron en tres LLMs (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) a través de pruebas de razonamiento matemático (AIME24/25, MATH500, GPQA, LiveCodeBench) y tareas de búsqueda agéntica.

• Desempeño: GraphPO superó consistentemente a las líneas base basadas en cadenas (GRPO, DAPO) y en árboles (TreeRL, SPO, PROS, TreePO) en todos los modelos y conjuntos de datos bajo los mismos presupuestos de tokens y respuestas. Por ejemplo, en el modelo Qwen2.5-7B-Math, GraphPO logró una precisión promedio del 40.9%, superando a la mejor línea base basada en árboles (PROS con 37.7%).
• Eficiencia de Exploración: GraphPO demostró una mayor eficiencia de exploración, lo que significa que una mayor proporción de la computación se asignó a progresos de razonamiento útiles en lugar de expansiones redundantes. Mantuvo una mayor entropía durante el entrenamiento en comparación con los métodos basados en árboles, que tienden a colapsar en patrones de razonamiento específicos más rápido.
• Longitud de Respuesta: GraphPO produjo respuestas más cortas que los métodos basados en árboles al fusionar estados equivalentes y recompensar rutas más cortas, mejorando así la eficiencia de la inferencia.
• Tareas Agénticas: El método mostró un desempeño superior en tareas de búsqueda profunda y agénticas (General AI Assistant, WebWalker, BrowseComp, XBench), validando su aplicabilidad a procesos de toma de decisiones secuenciales.
• Comparación con PRMs: GraphPO superó a los métodos basados en PRM (ReasonFlux-PRM) sin utilizar ningún dato de proceso anotado adicional.

5. Significado y Reivindicaciones

El artículo afirma que GraphPO proporciona un mecanismo práctico para obtener supervisión de proceso auto-emergente a partir únicamente de recompensas de resultados. Al modelar los despliegues como un grafo, aborda las limitaciones estructurales de los árboles, que no pueden representar estados equivalentes alcanzados por diferentes rutas.

Los autores sostienen que GraphPO:

1. Reduce la Varianza: Fusionar estados equivalentes y agrupar la evidencia descendente disminuye la varianza de la estimación de la ventaja.
2. Mejora la Eficiencia: Reasigna presupuestos computacionales lejos de expansiones redundantes hacia una exploración diversa y recompensa rutas de razonamiento más cortas.
3. Mejora la Utilización: Estabiliza las actualizaciones de la política al permitir que las ramas que se detienen prematuramente reciban crédito de sus socios exitosos equivalentes, mejorando la utilización del presupuesto de despliegue.

El trabajo sugiere que los despliegues con estructura de grafo ofrecen una alternativa robusta a los métodos basados en árboles para escalar las capacidades de razonamiento de los grandes modelos de lenguaje bajo configuraciones de recompensa verificables.