Resumen Técnico: MURPHY – GRPO Consciente de Retroalimentación con Asignación de Crédito Retrospectiva

Enunciado del Problema

El Aprendizaje por Refuerzo con Recompensas Verificables (RLVR) se ha convertido en un enfoque estándar para el post-entrenamiento de Modelos de Lenguaje Grandes (LLM) en tareas de razonamiento, con la Optimización de Política Relativa de Grupo (GRPO) emergiendo como un método líder. Sin embargo, el GRPO estándar y sus variantes son inherentemente de un solo turno: optimizan basándose en recompensas terminales de pares aislados de prompt-respuesta. Esta arquitectura es inadecuada para entornos agénticos, particularmente en la generación de código, donde los modelos deben refinar iterativamente las soluciones en respuesta a la retroalimentación del entorno (por ejemplo, errores de ejecución, trazas de pila, casos de prueba fallidos).

Los métodos multi-turno existentes a menudo dependen de maquinaria auxiliar compleja, como verificadores aprendidos (µCODE), críticos estilo PPO (RLEF) o políticas de verificación separadas (REVEAL). Una línea base natural, GRPO-MT, extiende el GRPO a múltiples turnos tratando las interacciones condicionadas a la retroalimentación como trayectorias. Sin embargo, GRPO-MT sufre de asignación de crédito grosera: asigna la misma recompensa terminal a todos los tokens en una trayectoria, independientemente de si los intentos fallidos intermedios proporcionaron retroalimentación informativa que permitió un refinamiento posterior exitoso. En la generación de código, un intento fallido no es uniformemente negativo; puede exponer un caso límite específico o un error de tiempo de ejecución que es crucial para la solución eventual. Los métodos actuales no logran distinguir entre "fallos informativos" y "fallos no informativos" cuando comparten el mismo resultado terminal.

Metodología: MURPHY

Los autores introducen MURPHY (Actualización Multi-turno con Optimización de Política Retrospectiva), una extensión mínima del GRPO diseñada para hacer que la receta estándar de post-entrenamiento sea consciente de la retroalimentación sin introducir críticos aprendidos o verificadores auxiliares.

1. Árboles de Despliegue Condicionados a la Retroalimentación

MURPHY construye una estructura de árbol para cada prompt de entrada en lugar de una trayectoria lineal:

• Turno 1: El modelo muestrea un grupo de programas candidatos.
• Ejecución y Retroalimentación: Cada candidato se ejecuta contra un conjunto de pruebas, generando una recompensa escalar (por ejemplo, tasa de aprobación) y retroalimentación cualitativa (por ejemplo, mensajes de error).
• Expansión:
  • Los candidatos resueltos terminan y se convierten en nodos hoja.
  • Los candidatos fallidos se expanden. Se forma un nuevo prompt concatenando la tarea original, la salida fallida y la retroalimentación del ejecutor. El modelo se vuelve a invocar en este prompt condicionado a la retroalimentación para generar un nuevo grupo de refinamientos.
• Este proceso se repite durante un número fijo de turnos, creando un árbol donde las aristas representan pasos de refinamiento condicionados a una retroalimentación específica.

2. Asignación de Crédito Retrospectiva

La innovación central es la asignación de crédito retrospectiva. Una vez completado el árbol de despliegue, las recompensas se propagan hacia atrás desde las hojas hasta la raíz. Esto permite que los refinamientos posteriores exitosos "criden" a los intentos fallidos anteriores que produjeron retroalimentación útil. El artículo propone dos estrategias de propagación:

• Recompensa Máxima (MARS): Una copia de seguridad optimista. Para un nodo $v$, la recompensa ajustada $\tilde{r}(v)$ es el máximo de su recompensa inmediata $r(v)$ y la recompensa ajustada máxima de sus hijos:
  $$\tilde{r}(v) = \max\left(r(v), \max_{u \in C(v)} \tilde{r}(u)\right)$$
  Esto acredita un intento fallido si cualquiera de sus descendientes resuelve eventualmente la tarea.
• Recompensa Media (MERS): Una copia de seguridad basada en la expectativa. Propaga un promedio descontado de recompensas futuras:
  $$\tilde{r}(v) = r(v) + \gamma \cdot \frac{\text{media}_{u \in C(v)} \tilde{r}(u)}{Z(v)}$$
  donde $\gamma$ es un factor de descuento y $Z(v)$ es un término de normalización.

3. Actualización Local de GRPO

Una vez que se ajustan las recompensas, MURPHY aplica el objetivo estándar de GRPO localmente a cada grupo de respuestas dentro del árbol. En lugar de usar recompensas inmediatas, utiliza las recompensas ajustadas por crédito ($\tilde{r}$) para calcular las ventajas. Esto preserva la estructura de línea base relativa al grupo del GRPO mientras incorpora el crédito temporal de la estructura del árbol.

4. Estrategias de Poda

Para abordar el costo computacional de expandir árboles (que pueden crecer exponencialmente), MURPHY introduce mecanismos de poda posteriores al despliegue que retienen trayectorias informativas antes de la propagación de recompensas:

• Poda Intra-grupo (INTRAP): Mantiene un número fijo de trayectorias dentro de cada grupo de respuestas, seleccionando específicamente aquellas que contribuyen más a la varianza de la recompensa (preservando señales de aprendizaje diversas).
• Poda Inter-grupo (INTERP): Mantiene grupos enteros de refinamiento basados en su varianza de recompensa dentro del grupo. Esto asigna el presupuesto de optimización a contextos de retroalimentación que producen los refinamientos candidatos más diversos e informativos.

Contribuciones Clave

1. Algoritmo MURPHY: Una extensión de GRPO multi-turno que entrena LLMs de código para utilizar la retroalimentación de ejecución mediante una asignación de crédito temporal estructurada, eliminando la necesidad de verificadores o críticos aprendidos.
2. Estrategias de Propagación de Recompensas: La introducción de estrategias MARS (optimista) y MERS (basada en expectativa) para asignar crédito desde refinamientos exitosos hacia atrás a fallos anteriores e informativos.
3. Mecanismos de Poda: Diseño de estrategias INTRAP e INTERP que hacen viable la optimización multi-turno filtrando trayectorias no informativas mientras preservan la señal de aprendizaje.
4. Validación Empírica: Evaluación exhaustiva en tres benchmarks (HumanEval, MBPP, LiveCodeBench-v6) y dos familias de modelos (Qwen, OLMo), demostrando ganancias significativas sobre métodos multi-turno anteriores.

Resultados Experimentales

Los autores evaluaron MURPHY en HumanEval, MBPP y LiveCodeBench-v6 utilizando modelos Qwen3 (1.7B, 4B) y OLMo-2-7B.

• Ganancias de Rendimiento: MURPHY logró hasta 6% de ganancias absolutas en pass@1 sobre los métodos multi-turno de retroalimentación de ejecución anteriores más fuertes (incluyendo GRPO-MT, µCODE y REVEAL).
• Escalado de Dificultad: Las ganancias fueron más pronunciadas en los subconjuntos Medio y Difícil. Por ejemplo, en LiveCodeBench-v6 (subconjunto Medio), MURPHY mostró una ganancia de +4.38% en la Iteración-5, y en el subconjunto Difícil, una ganancia de +4.20%. Esto sugiere que el método es particularmente efectivo donde la autocorrección iterativa es crítica.
• Comparación con Líneas Base:
  • En OLMo-2-7B, MURPHY superó a la línea base más fuerte en +6.20 pp en HumanEval y +6.07 pp en MBPP en la configuración Iter-3.
  • En Qwen3-4B (LiveCodeBench-v6), MURPHY superó a REVEAL (un método con un auto-verificador entrenado conjuntamente) en todos los subconjuntos de dificultad, a pesar de la arquitectura más compleja de REVEAL.
• Estudios de Ablación:
  • MARS vs. MERS: MARS generalmente superó a MERS, particularmente en configuraciones de recompensa dispersa, propagando el resultado más fuerte en lugar de diluir la señal mediante el promedio.
  • Poda: La estrategia de poda INTERP ofreció el mejor equilibrio costo-calidad, reduciendo el tiempo de optimización en un 74.1% (lo que resulta en una reducción del 21.4% en el tiempo total de entrenamiento por paso) mientras mantenía el rendimiento dentro del 0.8% del modelo sin podar. INTRAP, aunque mejoró el rendimiento de un solo turno, causó un retroceso en el rendimiento multi-turno.

Significado y Afirmaciones

El artículo afirma que MURPHY demuestra que la receta estándar de post-entrenamiento de GRPO puede hacerse consciente de la retroalimentación mediante un cambio estructural en la asignación de crédito únicamente.

• Minimalismo Arquitectónico: A diferencia de trabajos anteriores que requieren funciones de valor auxiliares, verificadores aprendidos o políticas de verificación explícitas, MURPHY es una "extensión mínima que preserva la arquitectura". Se basa únicamente en la retroalimentación de ejecución inherente a la tarea de generación de código.
• Discrepancia en la Asignación de Crédito: El trabajo aborda una discrepancia fundamental en la generación de código agéntica: la falla en distinguir entre errores no informativos y fallos informativos. Al propagar recompensas hacia atrás, MURPHY enseña al modelo que "errar y errar de nuevo" (como se cita de Piet Hein) es valioso si los errores proporcionan la señal necesaria para la corrección.
• Escalabilidad: Las estrategias de poda propuestas hacen que el entrenamiento multi-turno sea computacionalmente viable, reduciendo la carga de optimización sin sacrificar la calidad de la señal de aprendizaje.

Los autores concluyen que, aunque los despliegues multi-turno aumentan los costos de entrenamiento en relación con el GRPO de un solo turno, las ganancias en capacidades de autocorrección, particularmente en problemas difíciles, justifican el enfoque. Señalan limitaciones relacionadas con el aumento del costo de entrenamiento y la dependencia de una retroalimentación de ejecución limpia, sugiriendo que trabajos futuros podrían explorar señales de retroalimentación más ruidosas y presupuestos de turnos adaptativos.