🤖 machine learning

Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

Dieser Artikel zeigt, dass Standard-Chain-of-Thought-Transformer zwar aufgrund inhärenter Einschränkungen beim Kopieren und Abrufen nicht auf längere Denkpfade verallgemeinern können, aber durch den Einsatz eines wachsenden Vokabulars mit eindeutigen Wegweiser-Token und Wertänderungs-Codierungen, um diese Barrieren zu überwinden, eine längenverallgemeinerbare Turing-Vollständigkeit erreichen können.

Ursprüngliche Autoren: Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

Veröffentlicht 2026-04-29

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, Michael Hahn

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Der „kluge Schüler", der vergisst

Stellen Sie sich einen sehr klugen Schüler (den Transformer) vor, der lernt, komplexe Rätsel zu lösen. Um ihm zu helfen, geben ihm die Lehrer ein „Kladde", auf dem er seine Gedanken schrittweise aufschreiben kann. Dies nennt man Chain-of-Thought (CoT).

Vorherige Forschung zeigte, dass dieser Schüler mit dieser Kladde theoretisch jedes Rätsel lösen könnte, egal wie schwer es ist. Es war, als würde man ihm eine Superkraft geben.

Die Autoren dieses Papers entdeckten jedoch einen gravierenden Mangel: Der Schüler ist hervorragend darin, Rätsel zu lösen, die er geübt hat, aber er versagt kläglich, wenn die Rätsel länger werden. Wenn Sie ihn an einem 10-Schritte-Rätsel trainieren, kann er kein 20-Schritte-Rätsel lösen, selbst wenn die Logik identisch ist. Sie scheinen an eine „Decke" zu stoßen, an der ihre Schlussfolgerungen zusammenbrechen.

Dieses Paper fragt: Warum passiert das, und können wir es beheben?

Die zwei großen Hindernisse

Die Autoren fanden heraus, dass das Gehirn des Schülers (der Transformer) zwei spezifische „Fehler" hat, die ihn daran hindern, auf längere Aufgaben zu verallgemeinern.

1. Der „Fotokopierer"-Fehler (Wiederholtes Kopieren)

Stellen Sie sich vor, der Schüler muss eine lange Liste von Anweisungen aus einem Buch in seine Kladde kopieren.

Das Problem: Wenn die Liste kurz ist, kann er sie leicht kopieren. Aber wenn die Liste lang ist, gerät er in Verwirrung. Er kann die genaue Zeile, die er aus der Mitte einer langen Seite kopieren muss, nicht zuverlässig finden, ohne den Überblick zu verlieren.
Die Behauptung des Papers: Standard-Transformer haben Schwierigkeiten, beliebige Informationsstrings zu „kopieren", wenn sich die Länge ändert. Sie verirren sich in der Mitte des Textes.

2. Der „Zuletzt Gesehene"-Fehler (Abruf)

Stellen Sie sich vor, der Schüler verfolgt eine Variable, wie „Der Wert von X".

Das Problem: Wenn der Schüler „X = 5" schreibt, später „X = 7" und dann wieder „X = 5", muss er wissen, welcher der aktuelle Wert ist. In einer langen Kette von Gedanken vergisst der Schüler oft, welche „5" die neueste war. Er könnte eine alte „5" vom Anfang der Seite statt der neuen holen.
Die Behauptung des Papers: Das Modell hat Schwierigkeiten, die neueste Aktualisierung in einer langen Historie von Änderungen zu finden. Es ist, als würde man versuchen, das letzte Mal zu finden, an dem Sie einen Apfel gegessen haben, in einem Tagebuch mit 1.000 Seiten Einträgen.

Die Lösung: Eine neue Art, die Kladde zu schreiben

Die Autoren schlagen zwei clevere Tricks vor, um diese Fehler zu beheben. Sie verändern nicht das Gehirn des Schülers; sie ändern nur, wie die Anweisungen auf der Kladde geschrieben werden.

Trick #1: Die „Namensschilder" (Signpost-Tokens)

Um den Fotokopierer-Fehler zu beheben, schlagen die Autoren vor, jedem Element im Rätsel eine eindeutige ID-Karte oder ein „Namensschild" zu geben.

Wie es funktioniert: Anstatt zu sagen „Gehe zu Zeile 50", lautet die Anweisung „Gehe zum Element mit dem Namensschild #42".
Warum es hilft: Selbst wenn die Liste länger wird, muss der Schüler nicht zählen, um Zeile 50 zu finden. Er sucht einfach nach dem spezifischen Namensschild. Es ist wie in einer Bibliothek, wo jedes Buch einen eindeutigen Barcode hat, sodass Sie nicht das ganze Regal absuchen müssen, um das zu finden, das Sie brauchen.

Trick #2: Das „Änderungsprotokoll" (Value-Change-Encoding)

Um den Zuletzt Gesehene-Fehler zu beheben, schlagen die Autoren vor, was der Schüler aufschreibt, zu ändern.

Alte Methode: Der Schüler schreibt jedes Mal den vollständigen aktuellen Zustand auf (z. B. „X ist 5", dann „X ist 7", dann „X ist 5"). Dies erzeugt viel Rauschen und macht es schwer zu wissen, welche die neueste ist.
Neue Methode: Der Schüler schreibt nur auf, was sich geändert hat.
- Anstatt „X ist 7" zu schreiben, schreiben sie „X hat sich von 5 auf 7 geändert".
- Anstatt wieder „X ist 5" zu schreiben, schreiben sie „X hat sich von 7 auf 5 geändert".
Warum es hilft: Um den aktuellen Wert zu finden, zählt der Schüler einfach die Änderungen. Wenn sie „5 zu 7" und dann „7 zu 5" sehen, wissen sie, dass der aktuelle Wert 5 ist. Es ist wie die Führung eines Kontobuches von Transaktionen anstatt jedes Mal den gesamten Bankguthaben neu zu schreiben, wenn Sie einen Dollar ausgeben.

Die Ergebnisse: Theorie vs. Realität

Das Paper testet diese Ideen auf zwei Arten:

Der mathematische Beweis (Theorie):
- Schlechte Nachricht: Wenn Sie bei einem festen Satz von Wörtern (einem endlichen Alphabet) und Standard-Schreibweisen bleiben, kann der Schüler nicht lernen, Rätsel zu lösen, die länger als eine bestimmte Komplexität sind (speziell können sie nicht über eine Klasse von Problemen hinausgehen, die TC0 genannt wird). Sie sind mathematisch festgefahren.
- Gute Nachricht: Wenn Sie dem Schüler erlauben, eine unendliche Vorrat an eindeutigen Namensschildern (Signposts) zu verwenden und die „Änderungsprotokoll"-Methode anzuwenden, kann er theoretisch jedes Rätsel lösen, egal wie lang es ist.
Die Experimente (Realität):
- Die Autoren trainierten kleine Computermodelle von Grund auf neu an drei schwierigen Aufgaben:
  - Parität: Zählen, ob eine Zahlenkette eine ungerade oder gerade Anzahl von 1en hat.
  - Boolesche Auswertung: Lösen komplexer Logikrätsel (Wahr/Falsch).
  - S5-Permutation: Verfolgen der Bewegung von 5 Objekten, die ausgetauscht werden.
- Das Ergebnis:
  - Modelle, die mit der Standard-Methode trainiert wurden, scheiterten, wenn die Rätsel länger wurden.
  - Modelle, die mit Namensschildern und Änderungsprotokollen trainiert wurden, waren viel besser darin, längere Rätsel zu lösen, die sie noch nie gesehen hatten.
- Sie testeten dies auch an riesigen, vortrainierten KI-Modellen (wie Llama und Mistral). Selbst ohne sie neu zu trainieren, machte sie das einfache Prompting, Namensschilder und Änderungsprotokolle in ihren Antworten zu verwenden, signifikant schlauer beim Lösen langer, schwieriger Probleme.

Das Fazit

Das Paper kommt zu dem Schluss, dass Chain-of-Thought keine Magie ist. Nur einem KI-Modell zu sagen, es solle „Schritt für Schritt denken", reicht nicht aus, wenn die Art, wie es denkt, dazu neigt, sich in langen Listen zu verirren.

Um KI wirklich zuverlässig bei langfristiger Schlussfolgerung zu machen, müssen wir die „Gedanken" so formatieren, dass die zwei Hauptfallen vermieden werden:

Geben Sie jedem Schritt ein eindeutiges Namensschild, damit nichts verloren geht.
Notieren Sie nur Änderungen, damit das Modell nicht durch alte Informationen verwirrt wird.

Indem wir das Format der Schlussfolgerung beheben, können wir KI-Modellen helfen, ihre aktuellen Grenzen zu durchbrechen und viel schwierigere Probleme zu lösen.

1. Problemstellung

Während Chain-of-Thought (CoT)-Prompting die Leistung von Transformern empirisch verbessert und theoretisch gezeigt wurde, ihre Ausdruckskraft bis zur Turing-Vollständigkeit zu steigern, besteht eine kritische Lücke: Können Transformer lernen, CoT-Argumentation auf Längen zu verallgemeinern, die länger sind als die während des Trainings gesehenen?

Bestehende empirische Belege deuten darauf hin, dass die Genauigkeit von Transformern mit zunehmender Länge der CoT-Spur stark abnimmt, selbst bei algorithmischen und logischen Aufgaben. Das Papier untersucht, ob die theoretische Behauptung der Turing-Vollständigkeit unter der strengeren Anforderung der längen-verallgemeinerbaren Lernbarkeit gilt. Konkret fragt es:

Erlauben Standard-CoT-Formate Transformern, Probleme außerhalb der Komplexitätsklasse $\text{TC}^0$ (Threshold-Schaltkreise mit konstanter Tiefe) zu lösen, wenn sie auf längere Sequenzen verallgemeinert werden?
Welche spezifischen strukturellen Barrieren verhindern diese Verallgemeinerung?
Können diese Barrieren durch spezifische Formatierungsstrategien überwunden werden?

2. Methodik

Die Autoren verwenden eine Kombination aus theoretischem Formalismus und empirischer Validierung:

Theoretischer Rahmen

Die Studie nutzt neuere theoretische Rahmenwerke für die Längenverallgemeinerung von Transformern:

C-RASP: Ein Formalismus zum Nachdenken über Transformer mit endlichen Alphabeten und Positionsencodings. Die Mitgliedschaft impliziert Garantien für die Längenverallgemeinerung.
C-RASP:* Eine Erweiterung von C-RASP, die ein unendliches Alphabet (insbesondere unbeschränkte Wegweiser-Token) und lokale Match-Prädikate erlaubt.
Lernmodell: Die Autoren übernehmen ein idealisiertes Lernmodell, bei dem eine Sequenz von Transformern, die auf zunehmenden Eingabelängen trainiert werden, gegen einen einzelnen zugrunde liegenden Algorithmus konvergiert. Verallgemeinerung ist garantiert, wenn die Aufgabe innerhalb dieser Formalismen ausdrückbar ist.

Empirisches Setup

Aufgaben: Drei algorithmische Argumentationsaufgaben wurden ausgewählt:
1. Parität: Bestimmung, ob die Anzahl der 1en in einer Binärkette gerade oder ungerade ist.
2. Boolesche Auswertung: Auswertung des Wahrheitswerts verschachtelter logischer Formeln.
3. S5-Permutation: Verfolgung des Zustands von 5 Objekten nach einer Reihe von Tauschoperationen.
Modelle:
- From-Scratch: GPT-2-Modelle (25 Millionen Parameter), trainiert auf CoT-Spuren mit und ohne spezifische Formatierung.
- Vortrainierte LLMs: Zero-Shot- und Few-Shot-Prompting-Experimente mit Qwen2.5-7B, Mistral-Small-24B und Llama-3.3-70B.
Formatierungsvarianten:
- Naiver CoT: Standardsequenzielle Argumentation.
- Wegweiser-Token: Zuweisung eindeutiger Identifikatoren (z. B. <34>) zu bestimmten Positionen oder Operationen, um eine beliebige Adressierung zu ermöglichen.
- Wertänderungs-Kodierung: Anstatt den gesamten Zustand bei jedem Schritt zu protokollieren, protokolliert das Modell nur Änderungen von Werten (z. B. 1 -> 0) oder notiert explizit, wenn ein Wert unverändert bleibt.

3. Hauptbeiträge und theoretische Ergebnisse

Beitrag 1: Die Grenze endlicher Alphabete (Das negative Ergebnis)

Die Autoren beweisen, dass Transformer mit CoT unter standardmäßigen Positionsencodings und einem endlichen Alphabet nicht in der Lage sind, sich auf die Lösung von Problemen außerhalb von $\text{TC}^0$ zu verallgemeinern.

Satz 3.4: Wenn eine Sprache $L$ eine in C-RASP ausdrückbare CoT-Spur (mit Positionsprimitiven) besitzt, dann ist $L$ in $\text{TC}^0$ definierbar.
Implikation: Obwohl CoT theoretisch Turing-Vollständigkeit ermöglicht, ist die Lernbarkeit solcher Simulationen durch $\text{TC}^0$ begrenzt, wenn das Vokabular festgelegt ist. Die Vorteile der Ausdruckskraft übertragen sich nicht auf die längen-verallgemeinerbare Lernbarkeit.

Beitrag 2: Überwindung von Barrieren mit unendlichen Alphabeten (Das positive Ergebnis)

Das Papier identifiziert zwei Kernbarrieren für die Längenverallgemeinerung:

Wiederholtes Kopieren: Die Schwierigkeit, beliebige Zeichenketten an neue Positionen zu kopieren.
Abruf des letzten Vorkommens: Die Schwierigkeit, den aktuellsten Wert einer Variable abzurufen, wenn mehrere Aktualisierungen auftreten (nicht-eindeutiger Abruf).

Um diese zu überwinden, schlagen die Autoren eine Konstruktion mit C-RASP* vor:

Wegweiser-Token: Zuweisung eines eindeutigen, unbeschränkten Tokens (aus einem unendlichen Alphabet) zu jeder Bandposition oder jedem Operationsschritt. Dies löst die Kopier-Barriere, indem eine beliebige Indexierung ermöglicht wird, ohne absolute Identitäten auswendig lernen zu müssen.
Wertänderungs-Kodierung: Anstatt den gesamten Zustand zu protokollieren, protokolliert die CoT nur Übergänge (z. B. „Wert geändert von $x$ zu $y$ "). Der aktuelle Zustand wird durch Zählen der Nettoänderungen relativ zum Anfangszustand wiederhergestellt. Dies löst die Abruf-Barriere, indem der aktuelle Wert zu einer Funktion von Zählungen wird, anstatt nach dem „letzten" Vorkommen zu suchen.
Satz 3.8: Transformer mit CoT können sich längenverallgemeinernd verhalten, um jede Turing-Maschine zu simulieren, wenn sie ein unendliches Alphabet von Wegweiser-Token nutzen und Berechnungen über Wertänderungen kodieren. Die Länge der CoT-Spur bleibt linear im simulierten Laufzeitverhalten.

4. Empirische Ergebnisse

Training From-Scratch

Parität: Standard-CoT scheiterte an der Verallgemeinerung über die Trainingslängen hinaus. Wertänderungs-Kodierung ermöglichte eine robuste Verallgemeinerung auf das $2\times$ der Trainingslänge.
Boolesche Auswertung & S5-Permutation: Diese schwierigeren Aufgaben (außerhalb von $\text{TC}^0$ ) scheiterten mit naivem CoT. Das Hinzufügen von Wegweiser-Token verbesserte die Längenverallgemeinerung erheblich, obwohl S5 aufgrund potenzieller „Abkürzungen" (Heuristiken), die das Modell ausnutzen könnte, weiterhin herausfordernd blieb.
Binäre Permutation: Eine Variante von S5 mit hoher Wiederholung. Naive und nur-Wegweiser-CoTs scheiterten aufgrund von „nicht-eindeutigen Abruf"-Fehlern. Die Kombination aus Wegweisern + Wertänderung erzielte die besten Ergebnisse und bestätigte die theoretische Notwendigkeit beider Mechanismen.

Prompting vortrainierter LLMs

Wegweiser: Die Verwendung natürlicher Zahlen als Wegweiser-Hinweise in Few-Shot-Prompts verbesserte die Leistung bei booleschen und S5-Aufgaben für alle getesteten LLMs (7B bis 70B), insbesondere bei längeren Sequenzlängen.
Wertänderung: Bei einer Code-Ausführungsaufgabe (Verfolgung von Variablenzuweisungen) verbesserte die Bereitstellung von Inline-Kommentaren, die Wertänderungen explizit protokollierten (z. B. # node a: 9 -> 0), die Genauigkeit der endgültigen Antwort im Vergleich zur Standard-Code-Formatierung erheblich, selbst ohne Zwischenschritte der Argumentation.

5. Bedeutung und Fazit

Neudefinition des CoT-Erfolgs: Das Papier argumentiert, dass der Erfolg von CoT nicht inhärent dem „Denk"-Prozess selbst geschuldet ist, sondern stark von der Formatierung der Spur abhängt. Standard-CoT-Formate scheitern oft an der Verallgemeinerung, weil sie die für die Lernbarkeit erforderlichen Einschränkungen (Lokalität und Translationsinvarianz) verletzen.
Theoretische Grenzen: Es klärt auf, dass Turing-Vollständigkeit für Transformer konditional ist. Sie gilt für Ausdruckskraft (Härten einer Lösung ein), aber nicht für Lernbarkeit (Training eines Modells zur Verallgemeinerung), es sei denn, es werden spezifische strukturelle Hilfen (unendliche Alphabete/Wegweiser) bereitgestellt.
Praktische Leitlinien: Die Erkenntnisse bieten handlungsorientierte Prinzipien zur Verbesserung der LLM-Leistung bei schwierigen Argumentationsaufgaben:
1. Index-Hinweise verwenden: Positionen oder Schritte explizit mit eindeutigen Identifikatoren markieren, um den Abruf zu unterstützen.
2. Änderungen protokollieren, nicht Zustände: Argumentationsspuren so formatieren, dass Zustandsübergänge hervorgehoben werden, anstatt vollständige Zustandsextrakte, um Abrufmehrdeutigkeiten zu vermeiden.
Zukünftige Richtungen: Die Arbeit legt nahe, dass zukünftige Vortrainingsdaten und CoT-Schemata unter Berücksichtigung dieser theoretischen Einschränkungen entwickelt werden sollten, um das volle rechnerische Potenzial von Transformern bei Aufgaben mit langem Horizont zu erschließen.

Zusammenfassend zeigt das Papier, dass Transformer zwar theoretisch zu universeller Argumentation fähig sind, die Realisierung dieser Fähigkeit in einer längenverallgemeinernden Weise jedoch die Überwindung spezifischer architektonischer und formatierungsbedingter Barrieren durch den Einsatz von Wegweiser-Token und Wertänderungs-Kodierungen erfordert.