Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently

Resumen Técnico: Beneficios Probables de RLVR sobre SFT para Modelos de Razonamiento

Formulación del Problema
Este trabajo aborda una brecha fundamental en la comprensión de por qué el Aprendizaje por Refuerzo con Recompensas Verificables (RLVR, por sus siglas en inglés) suele producir capacidades de razonamiento superiores en los Modelos de Lenguaje Grande (LLM) en comparación con el Ajuste Fino Supervisado (SFT) basado en demostraciones de expertos. Mientras que la evidencia empírica sugiere que los modelos RLVR generalizan mejor y exhiben un razonamiento más robusto, carecía de un marco teórico basado en principios que explicara esta divergencia.

Los autores modelan el razonamiento de Cadena de Pensamiento (CoT) como un problema de búsqueda de caminos en una estructura de multigrafo específica. El grafo consiste en un nodo de origen, un nodo de bifurcación que se ramifica en $W$ caminos distintos, y $K$ subgrafos de tipo "diamante" secuenciales a lo largo de cada rama. Cada diamante contiene $L$ multiaristas paralelas. La tarea de razonamiento consiste en navegar desde el nodo de origen hacia un nodo hoja específico. Crucialmente, el grafo está diseñado de tal manera que la navegación eficiente requiere la capacidad de detectar callejones sin salida (entrar en una rama que no es el objetivo) y retroceder (backtrack) eficientemente hacia la bifurcación para explorar ramas alternativas.

Metodología
El artículo proporciona un análisis dinámico comparando dos paradigmas de post-entrenamiento aplicados a un modelo bigrama preentrenado (que representa el modelo del mundo):

1. Ajuste Fino Supervisado (SFT): El modelo se entrena en trayectorias "doradas" de la ruta más corta desde el origen hacia los objetivos. Estas trayectorias no contienen retrocesos, exploración ni intentos fallidos; solo demuestran el camino correcto hacia adelante. El objetivo de entrenamiento es la pérdida de entropía cruzada estándar.
2. Aprendizaje por Refuerzo con Recompensas Verificables (RLVR): El modelo se entrena mediante ejecuciones (rollouts) on-policy. La función de recompensa combina una recompensa de resultado (alcanzar el objetivo) con una penalización por longitud (para desincentivar caminos largos e ineficientes). El modelo aprende mediante actualizaciones de gradiente de política, analizando específicamente la dinámica del flujo de gradiente con signo.

Los autores analizan la evolución de las probabilidades de transición para estados de arista específicos:

• Estados de avance (forward states): Moverse más profundamente en una rama.
• Estados de retroceso (backward states): Moverse de regreso hacia la bifurcación (backtracking).

Derivan la dinámica del flujo de gradiente para los logits que gobiernan estas transiciones bajo SFT y RLVR, probando propiedades de convergencia en tiempo finito.

Contribuciones Clave y Resultados

1. Fallo de SFT al aprender el retroceso (backtracking):
   Los autores demuestran que el SFT entrenado exclusivamente en rutas cortas doradas no logra aprender una estrategia de retroceso eficiente. Debido a que los datos de entrenamiento nunca exponen al modelo a callejones sin salida o a la necesidad de retirarse, las probabilidades de transición para los estados de retroceso permanecen fijas en sus valores uniformes de preentrenamiento. El modelo aprende a avanzar con probabilidad 1, pero no retiene ningún mecanismo para retirarse eficientemente cuando una rama es incorrecta.

2. Éxito de RLVR al aprender el retroceso:
   En contraste, los autores demuestran que los modelos entrenados con RLVR aprenden a retroceder eficientemente. La naturaleza on-policy de RLVR obliga al modelo a generar y experimentar ejecuciones fallidas (callejones sin salida). La penalización por longitud proporciona una señal de gradiente que penaliza explícitamente los caminos largos y errantes, incentivando al modelo a aprender que moverse hacia atrás desde un callejón sin salida es una acción necesaria para alcanzar el objetivo rápidamente. El modelo converge a una política donde tanto las probabilidades de transición de avance como las de retroceso se acercan a 1, aprendiendo efectivamente a atravesar una rama y retirarse inmediatamente si esta no es el objetivo.

3. Separación Exponencial en el Cómputo de Tiempo de Inferencia:
   El artículo establece una separación demostrable en el tiempo de cómputo esperado de inferencia (tiempo de impacto o hitting time) requerido para encontrar un objetivo:

• Modelo RLVR: Requiere un tiempo esperado de $\Theta(WK)$. El modelo explora las ramas secuencialmente, atravesando cada una en un tiempo de $O(K)$ y retrocediendo inmediatamente ante un fallo.
• Modelo SFT: Requiere un tiempo esperado de $\Theta(WLK)$. Debido a que el modelo SFT no puede retroceder eficientemente (trata las aristas de retroceso como un paseo aleatorio entre $L$ opciones), le toma $O(LK)$ tiempo salir de una rama incorrecta.
  Esto resulta en una separación exponencial respecto a la profundidad del grafo ($K$) y una separación lineal respecto al factor de ramificación de los diamantes ($L$).

4. Destilación de Trazas de Razonamiento:
   Los autores demuestran que los beneficios de RLVR pueden transferirse a un modelo base mediante destilación. Si un modelo base se ajusta finamente con las trazas de razonamiento (incluyendo los pasos de retroceso) generadas por un modelo RLVR convergido, este hereda la capacidad de retroceso eficiente, recuperando la complejidad de tiempo de inferencia de $\Theta(WK)$. Esto sugiere que el factor crítico no es el algoritmo de RL en sí, sino la inclusión de datos de retroceso en el conjunto de entrenamiento.

Significado y Reivindicaciones
El artículo afirma proporcionar la primera prueba teórica de que la superioridad de RLVR sobre SFT para tareas de razonamiento proviene de la capacidad de la exploración on-policy para enseñar el retroceso eficiente. Los autores argumentan que el SFT sobre demostraciones de expertos es inherentemente limitado porque carece de exposición al "espacio negativo" del razonamiento (rutas fallidas), lo que conduce a un modelo que no puede recuperarse eficientemente de los errores.

El trabajo destaca que:

• El retroceso es una habilidad aprendible: No es una propiedad inherente de la arquitectura, sino un comportamiento inducido por la señal de entrenamiento.
• La composición de los datos importa: La inclusión de intentos fallidos y pasos de retroceso en los datos de entrenamiento (ya sea mediante exploración de RL o destilación) es crucial para reducir la complejidad de búsqueda.
• Fundamentación teórica: Los resultados ofrecen una perspectiva de sistemas dinámicos sobre por qué RLVR generaliza mejor, yendo más allá de las observaciones empíricas para ofrecer garantías demostrables de eficiencia en el tiempo de inferencia.

Los autores concluyen que, si bien la destilación puede transferir estas capacidades, el proceso de RLVR es el mecanismo que genera los datos necesarios para aprender el retroceso eficiente en primer lugar. Los hallazgos respaldan el uso de RLVR o la destilación de trazas generadas por RL para mejorar las capacidades de razonamiento de los LLM en tareas complejas de múltiples pasos.