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

Résumé Technique : Bénéfices Prouvables de la RLVR par rapport à la SFT pour les Modèles de Raisonnement

Formulation du Problème
Ce travail aborde une lacune fondamentale dans la compréhension de la raison pour laquelle l'Apprentissage par Renforcement avec Récompenses Vérifiables (RLVR - Reinforcement Learning with Verifiable Rewards) produit souvent des capacités de raisonnement supérieures aux modèles de Fine-Tuning Supervisé (SFT - Supervised Fine-Tuning) basés sur des démonstrations d'experts. Bien que les preuves empiriques suggèrent que les modèles RLVR généralisent mieux et font preuve d'un raisonnement plus robuste, un cadre théorique fondé sur des principes expliquant cette divergence faisait défaut.

Les auteurs modélisent le raisonnement par Chaîne de Pensée (CoT - Chain-of-Thought) comme un problème de recherche de chemin sur une structure de multigraphe spécifique. Le graphe se compose d'un nœud source, d'un nœud de bifurcation (fork) se divisant en $W$ chemins distincts, et de $K$ sous-graphes en "diamant" séquentiels le long de chaque branche. Chaque diamant contient $L$ arêtes parallèles. La tâche de raisonnement consiste à naviguer du nœud source vers un nœud feuille cible spécifique. Crucialement, le graphe est conçu de telle sorte qu'une navigation efficace nécessite la capacité de détecter les impasses (entrer dans une branche non cible) et de revenir en arrière (backtracking) efficacement vers la bifurcation pour explorer d'autres branches.

Méthodologie
Le papier fournit une analyse dynamique comparant deux paradigmes de post-entraînement appliqués à un modèle bigramme pré-entraîné (représentant le modèle du monde) :

1. Fine-Tuning Supervisé (SFT) : Le modèle est entraîné sur des trajectoires "dorées" (golden) de plus court chemin du départ vers les cibles. Ces trajectoires ne contiennent aucun retour en arrière, aucune exploration, ni aucune tentative infructueuse ; elles ne démontrent que le chemin direct correct. L'objectif d'entraînement est la perte d'entropie croisée standard.
2. Apprentissage par Renforcement avec Récompenses Vérifiables (RLVR) : Le modèle est entraîné via des déroulements (rollouts) on-policy. La fonction de récompense combine une récompense de résultat (atteindre la cible) avec une pénalité de longueur (pour décourager les chemins longs et inefficaces). Le modèle apprend via des mises à jour de gradient de politique, analysant spécifiquement la dynamique du flux de gradient signé.

Les auteurs analysent l'évolution des probabilités de transition pour des états d'arêtes spécifiques :

• États vers l'avant (Forward states) : S'enfoncer plus profondément dans une branche.
• États vers l'arrière (Backward states) : Revenir vers la bifurcation (backtracking).

Ils dérivent la dynamique du flux de gradient pour les logits régissant ces transitions sous SFT et RLVR, prouvant des propriétés de convergence en temps fini.

Contributions Clés et Résultats

1. Échec de la SFT à apprendre le Backtracking :
   Les auteurs prouvent que la SFT entraînée exclusivement sur les chemins les plus courts "dorés" échoue à apprendre une stratégie de retour en arrière efficace. Parce que les données d'entraînement n'exposent jamais le modèle aux impasses ou à la nécessité de reculer, les probabilités de transition pour les états vers l'arrière restent fixées à leurs valeurs uniformes pré-entraînées. Le modèle apprend à avancer avec une probabilité de 1, mais ne possède aucun mécanisme pour reculer efficacement lorsqu'une branche est incorrecte.

2. Succès de la RLVR pour apprendre le Backtracking :
   En revanche, les auteurs prouent que les modèles entraînés par RLVR apprennent à effectuer des retours en arrière efficaces. La nature on-policy de la RLVR force le modèle à générer et à expérimenter des déroulements infructueux (impasses). La pénalité de longueur fournit un signal de gradient qui pénalise explicitement les chemins longs et sinueux, incitant le modèle à apprendre que reculer d'une impasse est une action nécessaire pour atteindre la cible rapidement. Le modèle converge vers une politique où les probabilités de transition vers l'avant et vers l'arrière tendent toutes deux vers 1, apprenant efficacement à traverser une branche et à reculer immédiatement si celle-ci n'est pas la cible.

3. Séparation Exponentielle du Calcul au Temps d'Inférence :
   Le papier établit une séparation prouvable dans le calcul attendu au temps d'inférence (temps de passage ou hitting time) requis pour trouver une cible :

• Modèle RLVR : Nécessite un temps attendu de $\Theta(WK)$. Le modèle explore les branches séquentiellement, traversant chaque branche en $O(K)$ et reculant immédiatement en cas d'échec.
• Modèle SFT : Nécessite un temps attendu de $\Theta(WLK)$. Comme le modèle SFT ne peut pas effectuer de retour en arrière efficace (il traite les arêtes vers l'arrière comme une marche aléatoire parmi $L$ options), il lui faut $O(LK)$ pour sortir d'une mauvaise branche.
  Cela résulte d'une séparation exponentielle par rapport à la profondeur du graphe ($K$) et d'une séparation linéaire par rapport au facteur de bifurcation des diamants ($L$).

4. Distillation des Traces de Raisonnement :
   Les auteurs démontrent que les bénéfices de la RLVR peuvent être transférés à un modèle de base via la distillation. Si un modèle de base est affiné sur les traces de raisonnement (incluant les étapes de retour en arrière) générées par un modèle RLVR convergé, il hérite de la capacité de retour en arrière efficace, récupérant la complexité de temps d'inférence de $\Theta(WK)$. Cela suggère que le facteur critique n'est pas l'algorithme RL lui-même, mais l'inclusion de données de retour en arrière dans l'ensemble d'entraînement.

Signification et Revendications
Le papier affirme fournir la première preuve théorique que la supériorité de la RLVR sur la SFT pour les tâches de raisonnement provient de la capacité de l'exploration on-policy à enseigner un retour en arrière efficace. Les auteurs soutiennent que la SFT sur des démonstrations d'experts est intrinsèquement limitée car elle manque d'exposition à l' "espace négatif" du raisonnement (chemins échoués), menant à un modèle incapable de se rétablir efficacement après une erreur.

Le travail souligne que :

• Le backtracking est une compétence apprenable : Ce n'est pas une propriété inhérente à l'architecture, mais un comportement induit par le signal d'entraînement.
• La composition des données est cruciale : L'inclusion de tentatives infructueuses et d'étapes de retour en arrière dans les données d'entraînement (que ce soit via l'exploration RL ou la distillation) est essentielle pour réduire la complexité de recherche.
• Fondement théorique : Les résultats offrent une perspective de système dynamique sur la raison pour laquelle la RLVR généralise mieux, allant au-delà des observations empiriques pour offrir des garanties prouvables sur l'efficacité du temps d'inférence.

Les auteurs concluent que, bien que la distillation puisse transférer ces capacités, le processus de RLVR est le mécanisme qui génère les données nécessaires pour apprendre le retour en arrière efficace en premier lieu. Les conclusions soutiennent l'utilisation de la RLVR ou de la distillation de traces générées par RL pour améliorer les capacités de raisonnement des LLM sur des tâches complexes à plusieurs étapes.