Les LLM peuvent-ils devenir des ordinateurs ? — Comment exécuter directement des programmes à l’intérieur d’un transformer

• Pour dépasser la limite des LLM, capables de résoudre des problèmes de niveau olympiade de mathématiques mais toujours incapables d’effectuer correctement une simple addition ou même un sudoku sans outil externe, cette approche consiste à construire un véritable ordinateur à l’intérieur du transformer
• Du code C arbitraire est converti en tokens, et le modèle génère lui-même directement la trace d’exécution sur des millions d’étapes, avec un streaming possible sur CPU à plus de 30 000 tokens par seconde
• La technique clé consiste à restreindre la dimension des têtes d’attention à la 2D afin de les transformer en recherche géométrique fondée sur l’enveloppe convexe (convex hull), remplaçant le balayage en temps linéaire par un temps logarithmique
• Un interpréteur WebAssembly est implémenté dans les poids du transformer, ce qui permet une exécution transparente du programme à l’intérieur de la boucle de décodage du modèle, sans appel à un outil externe
• À terme, cette approche pourrait compiler directement des programmes dans les poids et faire évoluer les systèmes d’IA vers une intégration, sur une base opérationnelle unique, des représentations apprises et des algorithmes compilés

---

Les limites opérationnelles des LLM

• Les LLM les plus avancés peuvent résoudre des problèmes de niveau médaille d’or à l’Olympiade internationale de mathématiques ou s’attaquer à des problèmes non résolus en mathématiques et en sciences, mais échouent encore sur les tâches de calcul pur
• Ils commettent des erreurs même sur des additions élémentaires et affichent un très faible taux de réussite sans aide externe sur des benchmarks comme Sudoku-Bench
• Deux contournements sont aujourd’hui utilisés pour combler cet écart
  • Utilisation d’outils (tool use) : le modèle écrit du code, un interpréteur externe l’exécute puis renvoie le résultat
  • Orchestration d’agents : une boucle externe sauvegarde les états intermédiaires, décompose la tâche et rappelle le modèle de façon répétée
• Ces approches sont utiles, mais elles soulignent une limite fondamentale : la véritable capacité de calcul reste située en dehors du modèle
• C’est un peu comme dire que, parce que l’être humain a construit des avions, l’être humain sait voler
• Le modèle peut raisonner sur le calcul ou coordonner des outils, mais s’il ne peut pas exécuter lui-même, ce n’est pas un véritable ordinateur

Comment transformer un transformer en ordinateur

• Plusieurs travaux ont montré l’universalité théorique de l’architecture transformer, capable de simuler une machine de Turing, mais la puissance d’expression théorique ne garantit pas l’efficacité pratique de l’exécution
• Au lieu d’un modèle de calcul purement théorique, l’approche implémente un ordinateur RAM moderne à l’intérieur du transformer, chaque instruction étant mappée sur au plus 5 tokens
• Mais le problème plus profond réside dans le processus de décodage lui-même
  • Le décodage autoregressif standard interagit à chaque étape avec tout l’historique, qui ne cesse de s’allonger
  • Le KV cache évite de recalculer les clés/valeurs passées, mais le coût d’attention reste proportionnel à la taille du cache
• Pour dépasser cette limite, l’approche restreint la dimension des têtes d’attention à 2D et introduit un chemin de décodage efficace pour les traces de type exécution
  • Les principales opérations de recherche et de mise à jour s’effectuent alors en temps logarithmique par rapport à la longueur de séquence
  • Cela permet d’exécuter, à l’intérieur du transformer, des programmes sur des millions d’étapes

Ce que signifie vraiment « calculer » — utilisation d’outils vs exécution dans le modèle

• Dans l’approche classique de tool use, le modèle produit du code comme python -c "print(3+5)" → un interpréteur externe l’exécute → le résultat est injecté dans le flux de tokens
• Ici, le système implémente un interpréteur WebAssembly dans les poids du transformer
  • WebAssembly est un jeu d’instructions de bas niveau, rapide et déterministe, ainsi qu’une cible de compilation universelle pour C/C++
  • Pour calculer 3 + 5, le modèle émet des instructions wasm (i32.const, i32.add), puis passe en mode de décodage rapide afin de générer directement la trace d’exécution étape par étape
• Différence clé
  • Le tool use est opaque : le modèle cède le contrôle et reçoit une réponse de type boîte noire
  • L’exécution dans le modèle est transparente : toutes les étapes intermédiaires apparaissent dans la trace, et le modèle ne sort jamais de sa propre boucle de décodage

Démo sudoku — un stress test pour les calculs longs et exacts

• Les approches par réseaux neuronaux entraînés obtiennent de bons résultats sur les sudokus faciles, mais échouent complètement sur les grilles difficiles
• On explique souvent cela par l’idée que les modèles autoregressifs seraient fondamentalement inadaptés aux problèmes de satisfaction de contraintes, mais ce système, tout en restant entièrement autoregressif, atteint 100 % de précision
  • Le véritable goulot d’étranglement n’est pas le paradigme autoregressif lui-même, mais le fait qu’un sudoku difficile exige une trace d’exécution très longue, et que l’attention standard rend impraticable la génération de longs contextes
• Un solveur complet de sudoku compilé est exécuté à l’intérieur du transformer, ce qui permet de dérouler un véritable algorithme étape par étape plutôt qu’une heuristique apprise
• Le « sudoku le plus difficile du monde » d’Arto Inkala est résolu correctement en moins de 3 minutes
• Si le solveur compilé est correct, alors l’exécution du transformer l’est aussi : cela fournit une garantie générale

Comment le calcul est encodé — une trace en ajout uniquement

• Le transformer autoregressif est comparé à une machine qui vit dans son propre historique
  • Un ordinateur traditionnel met à jour une mémoire modifiable, mais le transformer ne dispose pas d’un tel concept
  • Il se compose d’un prompt fixe (entrée/programme) et d’une trace qui ne fait que croître (les tokens générés)
• Métaphore du carnet en écriture seule
  • Les premières lignes correspondent à l’entrée (le prompt), puis chaque ligne enregistre l’étape suivante du calcul
  • Il est impossible de modifier les lignes précédentes, et chaque étape ne peut référencer qu’un petit nombre de positions antérieures
• De nombreux algorithmes peuvent être représentés comme une trace en ajout uniquement où chaque étape ne référence qu’un nombre fixe et réduit de positions antérieures
• Dans ce système, les tokens générés par le modèle représentent l’état évolutif de la machine virtuelle : pointeur d’instruction, opérations mémoire/pile, arithmétique, contrôle de flux, sortie, etc.
• Les têtes d’attention se comportent comme un tableau unidimensionnel partagé, où chaque token écrit une valeur à un index et lit une valeur à un autre, fournissant une primitive écriture puis lecture
• L’attention peut aussi calculer des sommes cumulées (cumulative sums), ce qui permet de suivre le pointeur d’instruction, la profondeur de pile, etc., comme somme cumulée d’incréments delta

Le déverrouillage clé : une attention exponentiellement plus rapide

• Un ordinateur réel met à jour un petit état avec une quantité de travail presque constante par instruction, alors qu’un transformer standard interagit, à l’étape de décodage t, avec un préfixe de longueur t, ce qui fait croître le coût total de façon quadratique
• L’introduction de HullKVCache résout cette explosion quadratique
  • Sur les benchmarks réels, HullKVCache atteint 31 037 tokens par seconde (6 747 lignes/s), contre 272 tokens par seconde (59 lignes/s) pour un KVCache standard, soit environ 114× plus rapide
  • Au lieu d’un temps Θ(t) par étape, la recherche d’attention s’effectue en O(log t)

• Voie rapide pour l’attention 2D

  • Il ne s’agit pas d’accélérer les transformers en général ni d’introduire une nouvelle architecture, mais de se concentrer sur une paramétrisation gérable consistant à restreindre les têtes à 2D dans un transformer vanilla
  • Avec d_model = 36, n_heads = 18, on obtient exactement 2 dimensions par tête, sur 7 couches, avec nn.MultiheadAttention standard et un réseau feed-forward à portes
    • Le tout est construit en PyTorch vanilla pur, sans kernel d’attention personnalisé ni masque sparse
  • Le nombre de couches, de têtes et la taille d’embedding peuvent être augmentés arbitrairement, de sorte que le modèle n’a pas besoin d’être petit
    • on utilise davantage de têtes avec n_heads = d_model / 2

• Perspective géométrique de l’attention 2D

  • Mécanisme d’attention : les tokens passés fournissent des vecteurs-clés 2D kⱼ et des valeurs vⱼ ; l’étape courante forme une requête q et renvoie la valeur de la clé dont le produit scalaire est maximal (attention hardmax)
  • C’est exactement équivalent à la requête de point d’appui (supporting point query) classique en géométrie algorithmique : étant donnée une direction q, trouver sur l’enveloppe convexe le point le plus éloigné dans cette direction
  • En maintenant une structure de données d’enveloppe convexe au fil de la génération des tokens, on peut effectuer une recherche logarithmique sur l’ensemble des points passés
  • Pour les opérations mémoire/pile, il faut pouvoir retrouver « la valeur stockée le plus récemment à l’index i », ce qui explique le besoin de clés 2D
    • Si l’index j est stocké comme clé 2D kⱼ = (2j, -j²) et que l’on interroge avec la direction q = (i, 1), alors le terme quadratique -j² joue le rôle de pénalité pour que seule la correspondance exacte l’emporte
  • Une attention 2D suffit pour la complétude de Turing, et, comme le montre ce billet, pour représenter un ordinateur RAM complet

Et ensuite ?

• Des mécanismes d’attention plus riches

  • L’implémentation actuelle utilise une attention hardmax, mais ce n’est pas une contrainte fondamentale
  • Une approximation via une attention softmax k-sparse est possible : récupérer les k meilleures clés sur des enveloppes convexes imbriquées, puis n’appliquer le softmax qu’à celles-ci, pour un coût en O(k + log n)
  • Cette voie rapide géométrique n’est pas limitée à la structure de l’exécuteur et pourrait, en principe, accélérer le temps de décodage de tout transformer doté de têtes 2D
  • L’extension vers des têtes 3D via une enveloppe convexe 3D est naturelle, mais l’efficacité se dégrade fortement dans les dimensions supérieures

• Entraîner de grands modèles avec des têtes 2D

  • La paramétrisation en têtes 2D n’est pas intrinsèquement petite : avec davantage de têtes et de couches, on peut conserver un nombre total de paramètres comparable à celui d’un transformer standard
  • Plusieurs modes d’utilisation sont possibles
    • une voie rapide dédiée couplée à un modèle plus lent et plus généraliste
    • une architecture hybride rapide/lente au sein d’un même système
    • un décodage spéculatif (speculative decoding) où le modèle 2D propose rapidement des tokens et où un modèle à attention standard les vérifie
  • Comme la trace d’exécution fait partie du forward pass, l’ensemble du processus est différentiable (differentiable) — une différence fondamentale avec les outils externes, et une base de calcul entraînable directement intégrable à de plus grands modèles

• Compiler des programmes dans les poids

  • Aujourd’hui, le modèle apprend un interpréteur encodé dans les poids, mais l’extension de cette machine de compilation génératrice de poids pourrait permettre de compiler directement n’importe quel programme dans les poids, sans séquence de tokens
  • Les poids eux-mêmes deviendraient alors la cible de déploiement (deployment target) du logiciel : le modèle ne se contenterait plus d’apprendre un comportement de type logiciel, il embarquerait la logique compilée du programme comme partie intégrante de ses circuits internes
  • Si l’on peut compiler la logique dans les poids, alors la descente de gradient ne serait plus le seul moyen de modifier un modèle : ce serait une autre voie pour injecter directement structure, algorithmes et garanties dans le réseau
  • À terme, cela pourrait mener à des systèmes capables non seulement d’apprendre à partir de l’expérience, mais aussi de modifier ou étendre leurs propres poids pour réécrire eux-mêmes leur machine interne

• Faire croître les systèmes d’IA comme des logiciels

  • De la même manière que l’écosystème logiciel moderne a évolué en accumulant modules, abstractions et composants réutilisables, un processus similaire pourrait permettre d’ajouter progressivement de nouvelles capacités de calcul à l’intérieur des systèmes d’IA
  • De nouvelles fonctions viendraient se brancher sur les circuits existants sans réentraîner l’ensemble du système
  • Les systèmes d’IA du futur ne se contenteraient plus d’utiliser des logiciels : ils les intégreraient en interne, unifiant représentations apprises et algorithmes compilés sur une base opérationnelle unique