La chaîne de pensée est une méthode naturelle d'inférence pour augmenter la puissance de calcul des modèles de langage de grande taille basés sur des transformateurs, mais cela a un coût en termes de décodage séquentiel. Existe-t-il des alternatives plus efficientes pour élargir la puissance expressive d'un transformateur sans ajouter de paramètres ? Nous considérons les transformateurs avec des jetons de remplissage comme une forme de calcul testable parallélisable. Nous montrons que les transformateurs à attention dure moyenne et pré-normés masqués avec remplissage polynomial convergent précisément vers la classe TC⁰ de problèmes extrêmement parallélisables. Bien que la borne supérieure TC⁰ soit connue, prouver une borne inférieure correspondante s'est avéré difficile. De plus, notre analyse novatrice révèle la puissance élargie précise des transformateurs remplis lorsqu'ils sont associés à une autre forme de calcul d'inférence, à savoir l'augmentation dynamique de la profondeur via des boucles. Notre contribution technique principale est de montrer comment le remplissage aide à intégrer les notions de problèmes complets et de réductions, qui ont été une pierre angulaire de la théorie classique de la complexité, dans l'étude formelle des transformateurs. Armés de cet nouvel outil, nous prouvons que les transformateurs remplis avec O (ᵈ n) de bouclage sur des entrées de longueur n reconnaissent exactement la classe TCᵈ de problèmes modérément parallélisables. Ainsi, le remplissage et les boucles élargissent systématiquement la puissance expressive des transformateurs : avec un bouclage polylogarithmique, les transformateurs remplis convergent vers la classe NC, le meilleur résultat qu'on puisse espérer sans perdre le parallélisme (sauf si NC = P). Nos résultats motivent donc une exploration plus approfondie du remplissage et du bouclage comme alternatives parallélisables à la chaîne de pensée.
Merrill et al. (Sat,) ont étudié cette question.