Können LLMs zu Computern werden? — Wie man Programme direkt in Transformern ausführt

• Um die Grenze zu überwinden, dass LLMs zwar Probleme auf dem Niveau der Mathematik-Olympiade lösen, aber selbst einfache Addition oder Sudoku ohne externe Tools nicht zuverlässig ausführen können, wird ein Ansatz vorgestellt, bei dem ein echter Computer im Inneren des Transformers aufgebaut wird
• Beliebiger C-Code wird in Tokens umgewandelt, und das Modell erzeugt selbst direkt Ausführungsspuren über Millionen von Schritten; auf der CPU ist Streaming mit mehr als 30.000 Tokens pro Sekunde möglich
• Die Kerntechnik besteht darin, die Dimension der Attention-Heads auf 2D zu beschränken und sie in eine geometrische Suche auf Basis der konvexen Hülle (convex hull) umzuwandeln, wodurch lineare Zeitscans durch logarithmische Zeit ersetzt werden
• Durch die Implementierung eines WebAssembly-Interpreters in den Transformer-Gewichten wird Programmausführung transparent innerhalb der Decoding-Schleife des Modells möglich, ohne Aufrufe externer Tools
• Perspektivisch wird die Möglichkeit aufgezeigt, Programme direkt in Gewichte zu kompilieren und gelernte Repräsentationen sowie kompilierte Algorithmen in einer einzigen Rechenbasis zu integrieren

---

Die Rechengrenzen von LLMs

• Modernste LLMs können Aufgaben auf Goldmedaillen-Niveau der Internationalen Mathematik-Olympiade lösen oder sich an ungelösten Problemen aus Mathematik und Wissenschaft versuchen, scheitern aber bei reinen Rechenaufgaben weiterhin
• Schon bei einfacher Addition treten Fehler auf, und bei Benchmarks wie Sudoku-Bench ist die Erfolgsquote ohne externe Hilfe sehr niedrig
• Derzeit gibt es zwei Workarounds, um diese Lücke zu überbrücken
  • Tool use: Das Modell schreibt Code, ein externer Interpreter führt ihn aus und liefert das Ergebnis zurück
  • Agent-Orchestrierung: Eine externe Schleife speichert Zwischenzustände, zerlegt Aufgaben und ruft das Modell wiederholt auf
• Diese Ansätze sind nützlich, machen aber die grundlegende Grenze deutlich, dass die eigentliche Rechenfähigkeit außerhalb des Modells liegt
• Das ist vergleichbar damit, dass Menschen Flugzeuge gebaut haben, ohne deshalb selbst fliegen zu können
• Ein Modell kann über Berechnung nachdenken oder Tools koordinieren, aber wenn es nicht selbst ausführen kann, ist es kein echter Computer

Wie der Transformer zum Computer gemacht wurde

• Die theoretische Universalität der Transformer-Architektur, also ihre Fähigkeit, eine Turing-Maschine zu simulieren, wurde in mehreren Arbeiten gezeigt, doch theoretische Ausdrucksstärke garantiert keine praktische Ausführungseffizienz
• Statt eines rein theoretischen Rechenmodells wird ein moderner RAM-Computer innerhalb des Transformers implementiert, wobei jede Instruktion auf höchstens 5 Tokens abgebildet wird
• Das tiefere Problem liegt jedoch im Decoding-Prozess selbst
  • Standardmäßiges autoregressives Decoding interagiert in jedem Schritt mit der ständig wachsenden gesamten Historie
  • KV-Caching vermeidet zwar die Neuberechnung früherer Key/Value-Paare, doch die Attention-Kosten wachsen weiterhin proportional zur Cache-Größe
• Um diese Grenze zu überwinden, wird die Dimension der Attention-Heads auf 2D beschränkt und ein effizienter Decoding-Pfad für ausführungsartige Traces eingeführt
  • Wichtige Such- und Update-Operationen lassen sich in logarithmischer Zeit bezüglich der Sequenzlänge ausführen
  • Dadurch wird die Ausführung von Programmen mit Millionen von Schritten im Inneren des Transformers möglich

Was Rechnen bedeutet — Tool use vs. Ausführung im Modell

• Beim bisherigen Tool-use-Ansatz gibt das Modell Code wie python -c "print(3+5)" aus → ein externer Interpreter führt ihn aus → das Ergebnis wird in den Token-Stream eingespeist
• In diesem System wird ein WebAssembly-Interpreter in die Transformer-Gewichte implementiert
  • WebAssembly ist ein Low-Level-Befehlssatz für schnelle und deterministische Ausführung sowie ein universelles Kompilierungsziel für C/C++
  • Für die Berechnung von 3 + 5 gibt das Modell wasm-Instruktionen (i32.const, i32.add) aus und wechselt dann in einen schnellen Decoding-Modus, um die schrittweise Ausführungsspur direkt zu erzeugen
• Der zentrale Unterschied
  • Tool use ist opak: Das Modell gibt die Kontrolle ab und erhält eine Blackbox-Antwort zurück
  • Ausführung im Modell ist transparent: Alle Zwischenschritte erscheinen im Trace, und das Modell verlässt seine eigene Decoding-Schleife nicht

Sudoku-Demo — ein Stresstest für exakte Langzeitberechnung

• Gelernte neuronale Ansätze zeigen bei leichtem Sudoku gute Leistung, scheitern aber bei schwierigen Problemen vollständig
• Häufig wird erklärt, autoregressive Modelle seien grundsätzlich ungeeignet für Constraint-Satisfaction-Probleme, doch dieses System ist vollständig autoregressiv und erreicht dennoch 100 % Genauigkeit
  • Der eigentliche Flaschenhals ist nicht das autoregressive Paradigma selbst, sondern dass schwierige Sudokus sehr lange Ausführungsspuren erfordern und Standard-Attention die Erzeugung langer Kontexte unpraktisch macht
• Ein vollständig kompilierter Sudoku-Solver wird innerhalb des Transformers ausgeführt; statt gelernter Heuristiken wird ein echter Algorithmus Schritt für Schritt ausgeführt
• Arto Inkalas „schwerstes Sudoku der Welt“ wird in weniger als 3 Minuten korrekt gelöst
• Ist der kompilierte Solver korrekt, dann ist auch die Ausführung im Transformer korrekt — das liefert eine allgemeine Garantie

Wie die Berechnung codiert wird — ein nur anhängbarer Trace

• Ein autoregressiver Transformer wird mit einer Maschine verglichen, die in ihrer eigenen Historie lebt
  • Ein traditioneller Computer aktualisiert editierbaren Speicher, doch ein solches Konzept gibt es im Transformer nicht
  • Stattdessen gibt es einen festen Prompt (Eingabe/Programm) und einen ständig wachsenden Trace (generierte Tokens)
• Die Analogie eines Notizbuchs, in das nur angehängt werden kann
  • Die ersten Zeilen sind die Eingabe (Prompt), jede weitere Zeile protokolliert den nächsten Rechenschritt
  • Frühere Zeilen können nicht verändert werden, und in jedem Schritt können nur wenige frühere Positionen referenziert werden
• Viele Algorithmen lassen sich als „nur anhängbarer Trace, der in jedem Schritt auf eine feste kleine Anzahl früherer Positionen verweist“ darstellen
• Die vom Modell erzeugten Tokens repräsentieren in diesem System den sich entwickelnden Zustand der virtuellen Maschine, etwa Instruction Pointer, Speicher-/Stack-Operationen, Arithmetik, Kontrollfluss und Ausgabe
• Attention-Heads arbeiten wie ein gemeinsam genutztes eindimensionales Array und stellen ein Write-then-read-Primitive bereit, bei dem jedes Token an einen Index schreibt und von anderen Indizes liest
• Attention kann auch kumulative Summen (cumulative sums) berechnen, sodass Instruction Pointer, Stack-Tiefe und Ähnliches als kumulative Summen von Delta-Inkrementen verfolgt werden können

Der entscheidende Durchbruch: exponentiell schnellere Attention

• Echte Computer aktualisieren pro Instruktion einen kleinen Zustand mit nahezu konstantem Aufwand, während Standard-Transformer im t-ten Decoding-Schritt mit einem Präfix der Länge t interagieren, wodurch die Gesamtkosten quadratisch wachsen
• Mit HullKVCache wird diese quadratische Explosion gelöst
  • In realen Benchmarks erreicht HullKVCache 31.037 Tokens pro Sekunde (6.747 Zeilen/Sekunde), Standard-KVCache dagegen 272 Tokens pro Sekunde (59 Zeilen/Sekunde) — ein Unterschied um etwa den Faktor 114
  • Statt Θ(t) Zeit pro Schritt wird die Attention-Suche in O(log t) ausgeführt

• Der schnelle Pfad für 2D-Attention

  • Es geht nicht darum, Transformer allgemein zu beschleunigen oder eine neue Architektur einzuführen, sondern um eine handhabbare Parametrisierung in Vanilla-Transformern mit auf 2D beschränkten Heads
  • Mit d_model = 36 und n_heads = 18 ergibt sich pro Head genau zweidimensional, bei 7 Layern, Standard-nn.MultiheadAttention und einem Gated-Feedforward-Netzwerk
    • Das Ganze ist in reinem Vanilla-PyTorch aufgebaut, ohne benutzerdefinierte Attention-Kernel oder Sparse Masks
  • Zahl der Layer, Heads und Embedding-Größe können beliebig größer gewählt werden, daher muss das Gesamtmodell nicht klein sein
    • Mehr Heads werden mit n_heads = d_model / 2 verwendet

• Die geometrische Sicht auf 2D-Attention

  • Der Attention-Mechanismus: Frühere Tokens liefern 2D-Key-Vektoren kⱼ und Werte vⱼ, der aktuelle Schritt bildet eine Query q und gibt den Wert des Keys mit maximalem Skalarprodukt zurück (Hardmax-Attention)
  • Das ist exakt identisch mit der klassischen „Supporting-Point-Query“ aus der algorithmischen Geometrie: Für eine Richtung q wird der Punkt auf der konvexen Hülle gesucht, der in diese Richtung am weitesten reicht
  • Indem beim Generieren der Tokens gleichzeitig eine Datenstruktur für die konvexe Hülle gepflegt wird, ist Suche in logarithmischer Zeit über alle bisherigen Punkte möglich
  • Für Speicher-/Stack-Operationen muss der „zuletzt an Index i gespeicherte Wert“ abgefragt werden; genau deshalb werden 2D-Keys benötigt
    • Speichert man Index j als 2D-Key kⱼ = (2j, -j²) und fragt mit Richtung q = (i, 1) ab, wirkt der quadratische Term -j² als Strafe, sodass nur exakte Treffer gewinnen
  • 2D-Attention reicht für Turing-Vollständigkeit aus, und wie in diesem Blog gezeigt wird, kann damit ein kompletter RAM-Computer dargestellt werden

Ausblick

• Reichhaltigere Attention-Mechanismen

  • Die aktuelle Implementierung nutzt Hardmax-Attention, doch das ist keine grundlegende Einschränkung
  • Eine Approximation über k-sparse Softmax-Attention ist möglich: Die besten k Keys werden aus verschachtelten konvexen Hüllen abgerufen und Softmax nur über diese berechnet, mit Kosten von O(k + log n)
  • Der geometrische schnelle Pfad ist nicht nur auf Ausführungsstrukturen beschränkt, sondern kann prinzipiell die Decoding-Zeit jedes Transformers mit 2D-Heads beschleunigen
  • Auch eine natürliche Erweiterung auf 3D-Heads über 3D-konvexe Hüllen ist möglich, wenngleich die Effizienz in höheren Dimensionen stark abnimmt

• Große Modelle mit 2D-Heads trainieren

  • Die 2D-Head-Parametrisierung ist nicht von Natur aus klein — mit mehr Heads und Layern lässt sich eine Gesamtparameterzahl ähnlich wie bei Standard-Transformern beibehalten
  • Mehrere Einsatzmodi sind denkbar
    • Ein dedizierter schneller Pfad in Kombination mit einem langsameren, allgemeineren Modell
    • Eine Hybridarchitektur aus schnellem und langsamem Pfad innerhalb eines einzelnen Systems
    • Speculative Decoding, bei dem ein 2D-Modell Tokens schnell vorschlägt und ein Modell mit normaler Attention sie verifiziert
  • Da der Ausführungstrace Teil des Forward-Passes ist, bleibt der gesamte Prozess differenzierbar (differentiable) — grundlegend anders als bei externen Tools und eine lernbare Rechenbasis, die sich direkt in größere Modelle integrieren lässt

• Programme in Gewichte kompilieren

  • Derzeit lernt das Modell einen in die Gewichte codierten Interpreter, doch eine Erweiterung zu einer gewichteerzeugenden Kompilierungsmaschine würde es ermöglichen, beliebige Programme direkt in Gewichte zu kompilieren, ohne Tokensequenzen
  • Die Gewichte selbst würden damit zum Deployment-Ziel von Software: Das Modell lernt nicht nur softwareähnliches Verhalten, sondern enthält kompilierte Programmlogik als Teil seiner inneren Schaltkreise
  • Wenn sich Logik in Gewichte kompilieren lässt, ist Gradientenabstieg nicht mehr der einzige Weg, ein Modell zu verändern — Struktur, Algorithmen und Garantien könnten direkt in das Netzwerk eingebracht werden
  • Langfristig könnten daraus Systeme entstehen, die nicht nur aus Erfahrung lernen, sondern durch Modifikation oder Erweiterung ihrer Gewichte ihre innere Maschine selbst umschreiben

• KI-Systeme wie Software wachsen lassen

  • So wie moderne Software-Ökosysteme durch Module, Abstraktionen und wiederverwendbare Komponenten wachsen, könnte auch innerhalb von KI-Systemen ein ähnlicher Prozess möglich sein, bei dem nach und nach neue Rechenfähigkeiten hinzugefügt werden
  • Neue Funktionen würden an bestehende Schaltkreise angeschlossen, ohne das Gesamtsystem neu trainieren zu müssen
  • Zukünftige KI-Systeme würden Software nicht nur verwenden, sondern Software in sich selbst enthalten und gelernte Repräsentationen mit kompilierten Algorithmen in einer einzigen Rechenbasis integrieren

[GN⁺]

Hacker-News-Kommentare

• Das ist ein deutlich interessanterer Ansatz als bloß Berechnungen auszuführen
  Das Modell kann dynamische Attention-Umschaltungen durchführen, die proportional zum Logarithmus der Token-Anzahl sind
  Dadurch kann es Programmabläufe nachahmen, indem es als Text dargestellte Register und Stacks verfolgt
  Wenn ein LLM in einen „Fokusmodus“ wechseln und sehr schnell Tokens erzeugen könnte, ließe sich die Reasoning-Phase beschleunigen, in der zahlreiche Hypothesen erkundet und sortiert werden
  Im Paper wird vorgeschlagen, dass sich das für Hybridstrukturen mit schnellem und langsamem Pfad oder als Modell für speculative execution nutzen ließe

• Zuerst dachte ich: „Warum sollte man so etwas tun?“, aber inzwischen sehe ich es aus der Perspektive des Training-Bootstrapping
  Man könnte zum Beispiel ein Expertensystem mit 80 % Genauigkeit in das Modell einbauen und dessen Ergebnisse als Trainingsdaten verwenden, um die Genauigkeit zu steigern
  Je stärker die Trainingskosten für unterschiedliche Aufgaben sinken, desto niedriger wird die Eintrittsbarriere im AI-Wettbewerb

  • Für das Training ist dieser Ansatz allerdings ungeeignet
    Anders als Softmax-Attention ist Average-Hard-Attention bezüglich Keys und Queries nicht differenzierbar
    Selbst mit Straight-Through-Schätzung wird Backpropagation dadurch nicht schneller
  • Das Training dürfte schwierig sein, aber als interessante verwandte Arbeit lohnt sich dieses Paper

• Das menschliche Gehirn ist nicht besonders stark in Berechnungen
  Selbst die Multiplikation zweier 10-stelliger Zahlen dauert lange. Solche Rechnungen werden von Logikgattern viel effizienter verarbeitet
  Deshalb frage ich mich, ob es nicht besser wäre, wenn ein LLM statt selbst zu rechnen eher externe Module wie eine ALU aufruft

  • Wenn man ein eingebettetes Programm aber mit den übrigen Gewichten des Modells verbindet, kann man weit mehr als bloße Berechnung integrieren, nämlich verschiedenste feste Algorithmen
  • Außerdem könnte dieser Ansatz ein Mechanismus sein, um dem Modell geometrische Intuition und räumliches Denken beizubringen
  • Wenn man es nicht einmal versucht, wird man das Potenzial nie kennen. Deterministische Berechnung innerhalb des neuronalen Netzes könnte auch den Overhead von Tool-Calls senken

• Der Stil wirkt, als wäre er von AI geschrieben, aber die Kernaussage ist unklar
  Warum es gut sein soll, dass das Modell Programme intern statt über externe Systeme ausführt, ist nicht eindeutig — ob der Vorteil bei Geschwindigkeit, Backpropagation oder Benchmarks liegt

  • Statt bloß zu kritisieren, dass es „wie von AI geschrieben“ klingt, sollte man lieber den Inhalt selbst diskutieren
    Manche glauben, symbolische Logik sei unverzichtbar, aber man kann solche Versuche auch einfach als interessantes Experiment sehen
  • Wenn man das Paper tatsächlich liest, sieht man, dass der Execution Trace Teil des Forward-Pass ist und daher differenzierbar ist; Gradienten können also durch die Berechnung selbst propagiert werden
    Das unterscheidet sich grundlegend von externen Tool-Calls
    Außerdem liegen die Decoding-Kosten bei O(k + log n), und wenn Probleme wie Sudoku damit mit 100 % Genauigkeit gelöst werden, ist das durchaus bedeutsam
    Man könnte solche Verfahren auch im MoE-Stil kombinieren oder verschiedene Interpreter ausprobieren, etwa eine eingebettete WASM-basierte VM
  • Wenn man externe Tool-Calls eliminiert, verbessert das auch die Sicherheit. Das Risiko kompromittierter externer Tools entfällt
  • Entscheidend ist, dass das Modell während der Ausführung Code schreiben und ändern kann. Das ist eine Form dynamischer Ausführung, ähnlich einem menschlichen „Aha-Moment“
  • Die Wiederholungen im Stil könnten einfach Erklärungen für ein allgemeines Publikum sein. Auch Menschen machen solche Fehler oft

• Die Idee, Tools in den internen Berechnungspfad des Modells zu integrieren, ist im Hinblick auf Interpretierbarkeit äußerst spannend
  Es ist überraschend, dass sich mit einem einfachen Transformer solche Effizienz erreichen lässt

• Es gibt Potenzial, aber im jetzigen Zustand ist der praktische Nutzen gering
  Gewichte oder „Compiler“-Tools wurden nicht veröffentlicht, daher sind Experimente schwierig
  Trotzdem könnte die Idee nützlich bleiben, vordefinierte Berechnungsprimitiven in ein LLM einzubetten

  • Wer kleine Programme in Transformer-Gewichte hardcoden will, sollte sich ALTA ansehen
  • Ich frage mich, was mit dem Ausdruck „neurosymbolic garbage“ gemeint ist

• Dieser Satz ist der Kernpunkt:
  „Weil der Execution Trace Teil des Forward-Pass ist, können Gradienten durch die Berechnung selbst propagiert werden“
  Anders gesagt: Im Unterschied zu externen Tool-Calls ist das eine trainierbare, berechnungsbasierte Grundlage

  • In der Praxis ist die Struktur allerdings nicht vollständig differenzierbar, und auch im Paper werden nur approximative Methoden vorgeschlagen
    Zudem bleiben die Trainingsdaten und das Design der Loss-Funktion unklar
    Da Tool-Calls jedoch die Batch-Effizienz zerstören, könnte ein interner Rechen-Subnetzpfad große Effizienzgewinne ermöglichen
    Dieses Subnetz müsste allerdings nicht zwingend ein Transformer sein; vermutlich würde auch eine GPU-optimierte nicht lernende Schicht genügen

• Das Paper versteckt den eigentlichen Kern
  Wenn man die Dimension eines Attention-Heads auf 2 beschränkt, kann man Tokens mit logarithmischer Zeitkomplexität suchen und aktualisieren
  Warum diese Strategie aber nur auf „Code-Tokens“ angewandt wird, ist unklar
  Auch die Wahl von WASM als Ziel wirft Effizienzfragen auf

  • Mit zwei Dimensionen, RoPE und Hard-Max-Attention lässt sich relative Adressierung mit einem einzelnen Head implementieren
  • Dem Paper fehlen jedoch Formeln und Trainingsdetails, außerdem verwendet es nicht standardisierte Begriffe
    Zum Beispiel ist es ungenau, Self-Attention als „lookup table“ zu bezeichnen
    Im Codebeispiel wird mit d_model = 36, n_heads = 18 eine 2D-Struktur pro Head aufgebaut, aber trotzdem bleibt vieles unklar

• Es gibt keine konkrete Erklärung, wie der Sudoku-Solver in Transformer-Gewichte kompiliert wurde
  Es ist unklar, ob wirklich direkt von Code zu Gewichten kompiliert wurde oder ob das Verhalten angelernt wurde

  • Meine Interpretation wäre, dass eine einfache virtuelle Maschine in die Gewichte eingebettet und darauf eine WASM-Runtime kompiliert wurde, auf der dann der Solver läuft
  • Tatsächlich steht im Paper ausdrücklich, dass ein WASM-Interpreter trainiert wurde

• Interessant ist es, aber die Frage bleibt: „Warum sollte man das überhaupt so machen?“
  Auch das menschliche Gehirn kann eine Turing-Maschine simulieren, aber langsam. Deshalb verwenden wir externe Werkzeuge
  Für Modelle könnte es ebenso effizienter sein, externe Tools zu nutzen

  • Das Paper schlägt eingebettetes WebAssembly vor, um den Overhead von Python-Aufrufen zu senken, aber das erinnert an die Prozess-vs.-Thread-Debatten der 90er Jahre
    Man könnte ebenso eine Sprache wie Elixir einbetten und kürzeren Code ausführen
  • Auch die philosophische Behauptung „Ein System, das nicht rechnen kann, kann Berechnung nicht verstehen“ ist interessant
    Gemeint ist die Vorstellung, dass das Modell während der Ausführung Code verändern oder Debugging-Fähigkeiten besitzen könnte
  • Das Paper untersucht solche Möglichkeiten jedoch nicht, sondern bleibt auf der Ebene einer bloßen Execution Engine stehen
  • Wenn man Programme ohnehin in Gewichte kompilieren will, könnte Optimierung von Tool-Calls die vernünftigere Wahl sein
  • Man könnte auch die Analogie ziehen, dass Menschen schneller und effizienter wären, wenn sie einen Taschenrechner direkt im Gehirn eingebaut hätten