Résumé Technique : Une Comparaison Formelle entre la Chaîne de Pensée et la Pensée Latente

Énoncé du Problème

Les Grands Modèles de Langage (LLM) ont démontré des capacités de raisonnement améliorées grâce à la Chaîne de Pensée (CoT), qui suscite le raisonnement en générant explicitement des tokens intermédiaires. À l'inverse, les paradigmes de Pensée Latente (tels que la Chaîne de Pensée Continue/Coconut et les Transformers en Boucle) opèrent directement dans l'espace des états cachés continus, en itérant sans générer de tokens linguistiques discrets. Bien que les deux approches utilisent un calcul itératif pour améliorer l'expressivité, la séparation théorique fondamentale entre leurs capacités reste peu explorée. Plus précisément, il est incertain si la pensée latente est universellement plus expressive que la CoT, ou s'il existe des régimes de calcul spécifiques où l'un des paradigmes surpasse strictement l'autre.

Méthodologie

Les auteurs emploient une analyse formelle de la théorie de la complexité pour comparer la puissance expressive de la CoT et de la pensée latente. La méthodologie comprend :

1. Définitions Formelles : L'article définit la CoT, le Coconut et les Transformers en Boucle comme des applications itératives de blocs de Transformers. La CoT génère des tokens de manière autorégressive, tandis que les modèles de pensée latente (Coconut et Transformers en Boucle) mettent à jour les états cachés de manière itérative, soit en réinjectant les états cachés sous forme d'embeddings (Coconut), soit en recalculant l'ensemble de la séquence (Transformers en Boucle).
2. Modélisation du Calcul :
   • Problèmes de Décision : Le raisonnement est formalisé comme l'évaluation de graphes orientés acycliques (DAG), représentant des circuits booléens. Les auteurs analysent comment le nombre d'étapes de raisonnement (pour la CoT) ou d'itérations (pour la pensée latente) évolue avec la taille de l'entrée $n$ pour résoudre ces problèmes.
   • Classes de Complexité : L'étude mappe ces modèles vers des classes de complexité standard, spécifiquement $TC_k$ (circuits à seuil de profondeur polylogarithmique) et des classes liées au comptage approximatif ($FPRAS$ vs $FPTAS$).
   • Cadres Probabilistes : L'analyse s'étend aux modèles probabilistes où la CoT utilise un décodage stochastique pour échantillonner des tokens intermédiaires, tandis que la pensée latente est analysée sous des transformations déterministes dans l'espace latent.
3. Preuves Théoriques : Les auteurs construisent des preuves démontrant des bornes supérieures et inférieures pour chaque paradigme. Ils utilisent des réductions vers des circuits booléens et des propriétés de relations auto-réductibles pour établir des séparations.
4. Validation Empirique : Les affirmations théoriques sont validées sur des tâches fondamentales de raisonnement algorithmique (Problèmes de Mots, Connexité de Graphes, Évaluation Arithmétique, Distance d'Édition) et des tâches de comptage/échantillonnage approximatif (Comptage DNF, Coloration de Graphes).

Contributions Clés

1. La Pensée Latente Permet un Raisonnement Parallèle Efficace

L'article établit que la pensée latente est strictement plus efficace que la CoT pour les problèmes nécessitant un calcul parallèle.

• Parallélisme : Les modèles de pensée latente peuvent simuler l'évaluation d'un DAG couche par couche. Si un graphe de calcul a une profondeur $d$, un modèle de pensée latente peut le résoudre en $O(d)$ itérations.
• Limitation Séquentielle de la CoT : En revanche, la CoT doit simuler le DAG nœud par nœud en raison de sa nature autorégressive, nécessitant $O(\text{taille}(G))$ étapes.
• Séparation Formelle : Sous des itérations polylogarithmiques ($O(\log^k n)$), la pensée latente (Coconut et Transformers en Boucle) capture exactement la puissance de la classe de complexité $TC_k$. Cependant, la CoT avec le même nombre d'étapes est strictement bornée dans $TC_{k-1}$. Cela prouve que la pensée latente admet un calcul parallèle plus efficace que la CoT intrinsèquement séquentielle.

2. La CoT Permet le Comptage Approximatif via la Stochasticité

L'article identifie un régime où la CoT surpasse strictement la pensée latente : le comptage et l'échantillonnage approximatifs.

• Décodage Stochastique : La CoT échantillonne explicitement des tokens de raisonnement intermédiaires. Cette stochasticité permet à la CoT d'émuler des algorithmes randomisés, spécifiquement les Schémas d'Approximation Randomisés en Temps Polynomial Complet (FPRAS).
• Limitation Déterministe : La pensée latente, opérant de manière déterministe dans l'espace continu (sans échantillonnage au niveau des tokens pendant le raisonnement), est limitée aux schémas d'approximation déterministes (FPTAS).
• Séparation Formelle : En supposant que $FPTAS \subsetneq FPRAS$ pour les relations auto-réductibles (une hypothèse standard de complexité), les auteurs prouvent que la CoT peut approximer des problèmes de comptage et échantillonner à partir de distributions cibles que la pensée latente ne peut pas. Spécifiquement, la CoT peut générer des distributions que la pensée latente échoue à approximer, fournissant la première séparation formelle en faveur de la CoT.

3. Validation Empirique

Les expériences confirment les séparations théoriques :

• Tâches Parallèles : Sur des tâches comme la Connexité de Graphes et l'Évaluation Arithmétique, les Transformers en Boucle atteignent une haute précision avec nettement moins d'itérations (logarithmiques par rapport à la taille de l'entrée) comparé à la CoT, qui nécessite un nombre d'étapes proportionnel à la taille du problème.
• Tâches de Comptage/Échantillonnage : Sur le comptage DNF et l'échantillonnage de coloration de graphes, la CoT démontre la capacité à produire des distributions plus proches de la distribution cible uniforme (distance de variation totale plus faible) comparé aux Transformers en Boucle, validant sa capacité supérieure en approximation stochastique.

Résultats

• Séparation d'Expressivité : Il existe une séparation stricte de la puissance expressive. La pensée latente est supérieure pour les problèmes pilotés par la profondeur et parallélisables (régime polylogarithmique), tandis que la CoT est supérieure pour les problèmes nécessitant une approximation stochastique et du comptage.
• Efficacité des Itérations : La pensée latente atteint des performances comparables à la CoT sur des tâches parallèles avec $O(\log n)$ itérations, alors que la CoT nécessite $O(n)$ ou $O(\text{taille}(G))$ étapes.
• Capacité d'Échantillonnage : La CoT peut approximer des distributions inaccessibles aux modèles de pensée latente déterministes, spécifiquement dans le contexte des problèmes de comptage auto-réductibles.

Importance

L'article fournit un cadre théorique rigoureux pour choisir entre les paradigmes de raisonnement en fonction de la nature de la tâche :

• Raisonnement Latent est plus adapté aux problèmes qui peuvent être résolus efficacement via un calcul parallèle (par exemple, algorithmes de graphes, évaluation arithmétique), offrant des gains significatifs en efficacité des itérations.
• Chaîne de Pensée reste plus efficace pour les problèmes complexes nécessitant une approximation randomisée, du comptage ou de l'échantillonnage, où la stochasticité de la génération de tokens est un atout computationnel plutôt qu'un inconvénient.

Les auteurs concluent qu'aucun paradigme n'est universellement dominant ; plutôt, leurs forces sont complémentaires, dictées par le compromis entre parallélisabilité et stochasticité. Ce travail offre des orientations pratiques pour la conception de modèles et la sélection de tâches, suggérant que les architectures futures pourraient bénéficier d'approches hybrides ou d'une sélection spécifique aux tâches des mécanismes de raisonnement.