Résumé Technique : Apprendre le Raisonnement avec un Curriculum II : Généralisation Compositionnelle

1. Énoncé du Problème

Le papier étudie les fondements théoriques de la généralisation compositionnelle — la capacité à résoudre des problèmes complexes en combinant les solutions de sous-problèmes plus simples — un mécanisme central du raisonnement par chaîne de pensée (Chain-of-Thought, CoT) en intelligence artificielle. La question centrale abordée est la suivante : Quand et pourquoi la décomposition d'un problème en parties produit-elle un apprentissage plus efficace que la résolution directe ?

Pour y répondre, les auteurs formalisent le problème en utilisant la simulation de semiautomate. Un semiautomate est défini par une fonction de transition inconnue, markovienne et stationnaire $\pi^*: S \times \Sigma \to S$. Étant donné un état initial $s_0$ et un mot d'entrée $w_{1:T}$, l'objectif est de prédire l'état terminal $s_T$ après $T$ étapes. Les états intermédiaires $s_{1:T}$ constituent une chaîne de pensée. Ce modèle capture le suivi d'état, la reconnaissance de langages réguliers et l'arithmétique modulaire.

L'article étudie deux contextes d'apprentissage spécifiques :

1. Supervision Interactive de la Chaîne de Pensée (iSFT) : l'apprenant a accès à un oracle capable de retourner l'état à n'importe quelle étape $t$ d'un calcul pour un coût d'une unité. L'objectif est de minimiser le nombre de requêtes à l'oracle (complexité de requête) et les instances d'entraînement (complexité d'échantillonnage) nécessaires pour apprendre un modèle avec une erreur faible.
2. Apprentissage par Renforcement avec Récompenses Vérifiables (RLVR) : l'apprenant a accès à un modèle de référence "faible" pré-entraîné $\pi_{ref}$ capable de résoudre des instances courtes de longueur $B \ll T$ avec une probabilité constante, et à un vérificateur de résultat qui vérifie la correction d'une prédiction d'état terminal. L'objectif est d'améliorer le modèle de référence pour résoudre des instances de longueur $T$ efficacement, en surmontant la chute exponentielle de la probabilité de succès qui se produit lors du déploiement d'un modèle faible sur de longs horizons.

2. Méthodologie

Les auteurs proposent des approches basées sur l'autocurriculum qui décomposent de manière récursive de longues séquences en sous-problèmes plus courts, apprennent à les résoudre, puis composent les solutions. Cette approche s'appuie sur la Partie I de la série, utilisant un modèle de composition et de boosting.

Composantes Algorithmiques Clés

• Composition : Un modèle entraîné pour résoudre des instances de longueur $\tau$ peut être composé $L$ fois (où $T = L\tau$) pour résoudre des instances de longueur $T$. Cependant, les erreurs s'accumulent lors de la composition ; ainsi, les modèles à courte portée doivent être entraînés avec une grande précision.
• Boosting : Pour atteindre la précision nécessaire sur les sous-problèmes courts, les auteurs emploient une stratégie de boosting multi-échelle. Cela implique l'entraînement d'un ensemble d'apprenants faibles sur des distributions repondérées qui se concentrent sur les instances "difficiles" (là où l'ensemble actuel échoue) et leur agrégation (par exemple, via un vote à la majorité).
• Curriculum Auto-généré : Au lieu d'un calendrier fixe, l'apprenant sélectionne de manière adaptative les sous-problèmes sur lesquels s'entraîner en fonction des échecs des modèles entraînés à des échelles plus fines.

Innovations Techniques Clés

• Échantillonnage Inversé (Inverted Sampling) : Une contribution technique centrale est une nouvelle technique d'échantillonnage pour gérer le décalage de distribution inhérent au boosting. L'échantillonnage de rejet standard à partir de mélanges repondérés de marginales est inefficace (nécessitant $\Omega(L)$ échantillons dans le pire des cas). Les auteurs introduisent l'échantillonnage inversé, qui applique d'abord l'échantillonnage de rejet indépendamment aux $L$ sous-instances d'une séquence longue, puis sélectionne uniformément l'une des instances acceptées. Cela permet d'obtenir une probabilité d'acceptation proportionnelle au nombre de sous-instances, réduisant considérablement la complexité d'échantillonnage tout en maintenant des garanties d'approximation suffisantes pour l'algorithme d'apprentissage.
• Récursion Multi-échelle : L'algorithme (AutoLearn) applique le modèle de composition + boosting de manière récursive. Il décompose les instances de longueur $T$ en sous-problèmes de longueur $\tau$, qui sont eux-mêmes décomposés jusqu'à atteindre la longueur 1 (prédiction du prochain jeton). Cela crée une hiérarchie où les modèles résolvant des problèmes plus courts et plus faciles sont composés pour résoudre des problèmes plus difficiles.
• Guess-and-Check pour RLVR : Dans le contexte RLVR, où les étiquettes d'états intermédiaires ne sont pas directement disponibles, les auteurs simulent l'oracle interactif en utilisant le modèle de référence faible et le vérificateur. En générant des déploiements pour chaque bloc et en vérifiant l'état terminal du bloc, ils peuvent effectivement "étiqueter" les états intermédiaires pour construire le curriculum.

3. Contributions et Résultats Clés

Contexte I : iSFT (Supervision Interactive)

Le papier présente AutoLearn, un algorithme qui apprend des semiautomates avec une complexité de requête et d'échantillonnage sous-polynomiale par rapport à la longueur de la séquence $T$.

• Résultat : La complexité de requête et d'échantillonnage est bornée supérieurement par $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.
• Comparaison : Cela brise la barrière $\Omega(T)$ inhérente aux méthodes de simulation directe.
  • Supervision Full CoT : Nécessite $\Omega(T)$ requêtes par instance pour étiqueter chaque état.
  • Feedback End-to-End : Nécessite une complexité d'échantillonnage de $\Omega(T)$ en raison de l'incapacité à généraliser à partir des états terminaux sans ancrage intermédiaire.
• Mécanisme : En sélectionnant de manière adaptative les sous-problèmes et en utilisant l'échantillonnage inversé pour gérer le décalage de distribution, AutoLearn atteint une complexité sous-polynomiale en $T$, spécifiquement $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.

Contexte II : RLVR (Récompenses Vérifiables)

Le papier présente AutoLearn.RL, qui améliore un modèle de référence faible $\pi_{ref}$ de la compétence au niveau du bloc ($B$) vers la compétence de pleine longueur ($T$).

• Résultat : L'algorithme atteint une haute précision sur les instances de longueur $T$ avec des coûts régis par la couverture du modèle de référence à la longueur de bloc plus courte $B$, plutôt qu'à la longueur complète $T$.
• Expansion de la Couverture : Les méthodes RLVR standard nécessitent que le modèle de référence ait une couverture non triviale à la longueur $T$, ce qui est exponentiellement improbable si le modèle n'a une couverture qu'à la longueur $B$ (c'est-à-dire $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$). AutoLearn.RL réduit cette exigence à la couverture à la longueur $B$.
• Complexité :
  • Complexité d'échantillonnage : $\tilde{\mathcal{O}}(d/\varepsilon)$.
  • Complexité de requête : $\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$.
  • Coût de calcul : $\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$.
• Signification : Le coût de "chauffe" (burn-in) dépend de la couverture à l'échelle courte $B$, permettant à la couverture effective à la longueur $T$ de passer d'exponentiellement petite à constante grâce au curriculum.

4. Signification et Revendications

Le papier affirme que la composition combinée à un curriculum auto-généré peut atteindre des réductions superpolynomiales du coût de supervision et de calcul par rapport aux bases non-curriculaires.

• Fondement Théorique : Il fournit un cadre théorique rigoureux expliquant pourquoi la décomposition des problèmes aide : elle permet à l'apprenant de troquer la longueur de séquence contre des exigences de précision via la composition, tandis que le boosting garantit la précision nécessaire sur les sous-problèmes.
• Efficacité : Les résultats démontrent que pour des tâches comme la simulation de semiautomate, l'apprentissage peut être réalisé avec une complexité de $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$, une amélioration spectaculaire par rapport à la complexité linéaire $\Omega(T)$ des approches standards.
• Généralisation : Les conclusions suggèrent que les autocurricula, où l'apprenant conçoit ses propres problèmes, ne sont pas seulement des heuristiques mais peuvent être théoriquement justifiés comme un mécanisme pour surmonter les barrières statistiques et computationnelles du raisonnement à long horizon.
• Limites et Travaux Futurs : Les auteurs reconnaissent des simplifications, telles que la restriction de la classe de modèles aux modèles markoviens (excluant l'attention à historique complet comme les Transformers) et l'hypothèse de transitions déterministes. Ils notent que l'extension de ces résultats aux modèles non-markoviens et aux transitions stochastiques est une direction clé pour les travaux futurs. Ils soulignent également que bien que leurs résultats actuels atteignent une dépendance sous-polynomiale vis-à-vis de $T$, atteindre une dépendance polylogarithmique reste une question ouverte, nécessitant potentiellement des hypothèses plus fortes comme des bornes d'erreur finies.

En résumé, l'article établit que la généralisation compositionnelle, lorsqu'elle est guidée par un curriculum adaptatif et soutenue par des techniques comme l'échantillonnage inversé, offre une voie prouvablement efficace pour apprendre des tâches séquentielles complexes qui sont intraitables pour les méthodes d'apprentissage directes.