Length Generalization Bounds for Transformers

Diese Arbeit beweist, dass für Transformer-Modelle und die zugehörige Sprachklasse CRASP keine berechenbaren Generalisierungsgrenzen existieren, liefert jedoch für den positiven Teil von CRASP und festgenaue Transformer-Modelle optimale exponentielle Schranken.

Das Wesentliche

Die große Frage: Können KI-Modelle „in die Ferne" sehen?

Stell dir vor, du unterrichtest einen Schüler (das KI-Modell) in Mathe. Du gibst ihm nur Aufgaben mit Zahlen bis 100 (das ist dein Trainingsdaten). Die Frage ist: Wird dieser Schüler auch Aufgaben mit Zahlen bis 1.000 oder 1 Million richtig lösen können, ohne dass er diese spezifischen Zahlen je gesehen hat?

Das nennt man Längen-Verallgemeinerung (Length Generalization). In der Welt der modernen KI (Transformern) ist das ein riesiges Problem. Oft lernen Modelle Muster, die nur für kurze Texte funktionieren, und scheitern, wenn die Texte länger werden.

Dieses Paper stellt eine fundamentale Frage: Gibt es eine mathematische Garantie dafür, dass wir wissen, wie viel Training nötig ist, damit ein Transformer auch lange Texte versteht?

Die Antwort der Autoren ist überraschend und in zwei Teile gespalten:

---

Teil 1: Das böse Ungeheuer (Allgemeine Transformer)

Die Erkenntnis: Für normale Transformer-Modelle gibt es keine Garantie. Es ist mathematisch unmöglich, vorherzusagen, wie viel Training nötig ist.

Die Analogie:
Stell dir vor, du versuchst, einen Detektiv zu trainieren, der Verbrechen aufklären soll. Du zeigst ihm nur Fälle, die in kleinen Häusern passiert sind.
Die Autoren sagen: „Es gibt keine Formel, die dir sagen kann: 'Wenn du ihm 100 kleine Fälle zeigst, wird er auch Fälle in Wolkenkratzern lösen können.'"

Warum? Weil die Logik, die diese Modelle verwenden (im Paper C-RASP genannt), so mächtig ist, dass sie Probleme lösen kann, die so komplex sind, dass sie mit dem Hilbertschen 10. Problem (einem berühmten mathematischen Rätsel über Gleichungen) gleichgesetzt werden können.

Das Bild:
Es ist, als würdest du versuchen, die Länge einer Schnur zu messen, die sich in ein Labyrinth verwandelt, das sich selbst ständig neu erfindet. Die Schnur könnte theoretisch unendlich lang sein, oder sie könnte so schnell wachsen, dass kein Computer sie jemals berechnen könnte (schneller als die berühmte Ackermann-Funktion, die schon für winzige Zahlen gigantisch wird).

Die Konsequenz:
Wenn du ein normales Transformer-Modell trainierst, weißt du nie wirklich, ob es genug gelernt hat, um lange Texte zu verstehen. Du könntest Millionen von Beispielen geben, und es könnte trotzdem bei einem etwas längeren Text versagen. Es gibt keine „Sicherheitsgrenze", die du berechnen kannst.

---

Teil 2: Der disziplinierte Schüler (Fixed-Precision Transformer)

Die Erkenntnis: Es gibt aber eine Ausnahme! Wenn man die Modelle etwas einschränkt (man nennt sie Fixed-Precision Transformer oder „Transformer mit fester Genauigkeit"), dann funktioniert die Garantie wieder.

Die Analogie:
Stell dir vor, du nimmst dem Detektiv eine Brille ab, die ihm erlaubt, unendlich feine Details zu sehen, und gibst ihm stattdessen eine Brille, die nur grobe Strukturen erkennt. Er kann nicht mehr jedes winzige Detail zählen, aber er kann klare Muster erkennen.

In diesem eingeschränkten Szenario gibt es eine klare Regel:
Um sicherzustellen, dass das Modell lange Texte versteht, musst du ihm exponentiell viele Beispiele zeigen.

Was bedeutet „exponentiell"?
Stell dir vor, du lernst ein neues Wort.

• Um ein Wort mit 1 Buchstabe zu lernen, brauchst du 2 Beispiele.
• Um ein Wort mit 2 Buchstaben zu lernen, brauchst du 4 Beispiele.
• Um ein Wort mit 10 Buchstaben zu lernen, brauchst du 1.024 Beispiele.
• Um ein Wort mit 20 Buchstaben zu lernen, brauchst du schon über eine Million Beispiele.

Das ist die exponentielle Kurve. Die Autoren sagen: „Ja, es ist möglich, eine Garantie zu geben. Aber der Preis ist hoch: Du musst dem Modell eine riesige Menge an Daten zeigen, die exponentiell mit der Komplexität des Problems wächst."

Das Bild:
Es ist wie beim Lernen eines neuen Spiels. Wenn die Regeln einfach sind (Fixed-Precision), kannst du sagen: „Wenn du 100 Runden gegen den Computer spielst, wirst du das Spiel auch gegen einen Profi beherrschen." Aber wenn das Spiel extrem komplex ist (normale Transformer), gibt es keine solche Regel. Du könntest 100 Jahre spielen und immer noch scheitern, weil die Komplexität des Spiels sich in einer Weise verändert, die man nicht vorhersagen kann.

---

Zusammenfassung für den Alltag

1. Das Problem: Wir wissen oft nicht, warum KI-Modelle bei langen Texten versagen.
2. Die schlechte Nachricht: Für die mächtigen Modelle, die wir heute nutzen, gibt es keine mathematische Garantie. Man kann nicht berechnen, wie viel Training nötig ist, um sicherzugehen, dass sie funktionieren. Es ist wie ein mathematisches „Unmögliches".
3. Die gute (aber teure) Nachricht: Wenn man die Modelle etwas „dümmer" macht (indem man ihre Rechengenauigkeit begrenzt), gibt es eine Garantie. Aber diese Garantie verlangt, dass man sie mit unvorstellbar vielen Beispielen trainiert (exponentiell viele).
4. Der Grund für aktuelle Probleme: Vielleicht ist das der Grund, warum KI-Modelle in der Praxis oft bei langen Texten versagen. Um sie perfekt zu machen, bräuchten wir theoretisch Datenmengen, die so groß sind, dass wir sie gar nicht sammeln können.

Fazit: Die Autoren haben bewiesen, dass wir bei den aktuellen KI-Modellen im Dunkeln tappen, wenn es um die Vorhersage von Längen-Verallgemeinerung geht. Es gibt keinen „Schalter", den man umlegen kann, um sicherzustellen, dass das Modell für lange Texte bereit ist. Entweder ist es unmöglich zu garantieren, oder es ist so teuer (in Daten), dass es unpraktisch ist.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert das fundamentale Problem der Längen-Verallgemeinerung (Length Generalization) bei Transformer-Modellen. Längen-Verallgemeinerung beschreibt die Fähigkeit eines Lernalgorithmus, korrekte Vorhersagen auf Eingaben beliebiger Länge zu treffen, obwohl er nur mit endlich vielen Trainingsdaten (begrenzte Länge) trainiert wurde.

Während empirische Studien zeigen, dass Transformer in manchen Fällen Längen-Verallgemeinerung erreichen, ist dieses Verhalten oft inkonsistent und stark von Hyperparametern abhängig. Bisherige theoretische Arbeiten (z. B. Chen et al., 2025) haben gezeigt, dass für eingeschränkte Klassen von Transformer-Programmen (C-RASP mit 1 oder 2 Schichten) berechenbare Schranken für die benötigte Trainingslänge existieren. Die offene Frage war jedoch, ob für allgemeine Transformer (insbesondere mit mehr als zwei Schichten) überhaupt berechenbare Schranken für die Längen-Verallgemeinerung existieren.

Das Paper untersucht, ob es einen Algorithmus gibt, der bestimmen kann, wie lange die Trainingsdaten sein müssen, um eine perfekte Verallgemeinerung zu garantieren (nicht-asymptotische Längen-Verallgemeinerung).

2. Methodik und theoretischer Rahmen

Die Autoren nutzen eine Verbindung zwischen Transformer-Architekturen und formaler Logik, um das Problem zu analysieren:

• C-RASP (Counting RASP): Eine Programmiersprache, die ausdrucksstark genug ist, um Transformer mit fester Genauigkeit (außerhalb der Attention) exakt zu modellieren. Sie basiert auf temporaler Logik mit Zähloperatoren.
• Äquivalenz: Es wird die bekannte Äquivalenz zwischen C-RASP und Transformer-Modellen genutzt (Yang et al., 2025).
• Reduktion auf Entscheidbarkeitsprobleme: Das Paper nutzt ein zentrales Ergebnis von Chen et al. (2025): Die Existenz einer berechenbaren Schranke für die Längen-Verallgemeinerung ist äquivalent zur Entscheidbarkeit des Äquivalenzproblems für die betreffende Sprachklasse.
• Beweistechnik:
  • Um die Nicht-Berechenbarkeit zu zeigen, wird das Leerheitsproblem (Emptiness Problem) für C-RASP auf das 10. Hilbert-Problem (Entscheidbarkeit diophantischer Gleichungen) reduziert. Da das 10. Hilbert-Problem unentscheidbar ist, ist auch das Leerheitsproblem für C-RASP unentscheidbar.
  • Um positive Ergebnisse für eingeschränkte Klassen zu zeigen, wird eine Reduktion auf die unäre temporale Logik TL[-3] (nur strikte Vergangenheit) durchgeführt.

3. Wichtige Beiträge und Ergebnisse

A. Unberechenbarkeit für allgemeine C-RASP und Transformer (Hauptergebnis)

Das Paper beweist, dass für die allgemeine Klasse C-RASP (und damit für Transformer) keine berechenbare Schranke für die Längen-Verallgemeinerung existiert.

• Theorem 1.1 (Informal): Es gibt keinen Algorithmus, der perfekt lernt, ob ein C-RASP-Programm (selbst mit nur zwei Schichten) eine bestimmte Sprache akzeptiert, basierend auf Trainingsdaten endlicher Länge.
• Konsequenz: Da C-RASP und Transformer äquivalent sind, gilt dies auch für Transformer mit 2 und mehr Schichten. Die notwendige Länge der Trainingsdaten, um eine Verallgemeinerung zu garantieren, wächst schneller als jede berechenbare Funktion (sogar schneller als die Ackermann-Funktion).
• Bedeutung: Dies bedeutet, dass kein Lernalgorithmus im Voraus bestimmen kann, ob ein Transformer genug Daten gesehen hat, um auf längeren Eingaben korrekt zu funktionieren.

B. Berechenbare Schranken für den positiven Fragment C-RASP+

Als Gegenstück zeigen die Autoren, dass für eine eingeschränkte Unterklasse, C-RASP+, berechenbare Schranken existieren.

• Definition: C-RASP+ erlaubt nur Gleichungen/Ungleichungen der Form $\sum \alpha_i \cdot \# \phi_i \sim c$, wobei $\alpha_i, c$ natürliche Zahlen sind (keine negativen Koeffizienten oder Subtraktionen, die zu komplexen Interaktionen führen).
• Theorem 1.2 (Informal): Um ein C-RASP+-Programm perfekt zu lernen, ist es notwendig und hinreichend, Trainingsstrings bis zu einer Länge zu sehen, die exponentiell in der Größe des Programms ist.
• Optimalität: Die Autoren beweisen, dass diese exponentielle Schranke im Worst-Case optimal ist. Es gibt Programme, die zwingend exponentiell lange Strings benötigen, um erkannt zu werden.

C. Implikationen für Transformer-Varianten

• Standard-Transformer: Da sie C-RASP ausdrücken können, unterliegen sie der Unberechenbarkeit (kein garantierter Lernprozess für Längen-Verallgemeinerung).
• Fixed-Precision Transformer: Diese Modelle, die auch innerhalb der Attention-Schicht auf eine feste Bit-Genauigkeit runden, sind ausdrucksäquivalent zu C-RASP+.
  • Ergebnis: Fixed-Precision Transformer erlauben Längen-Verallgemeinerung, jedoch nur mit einer exponentiellen Schranke für die benötigte Trainingslänge.
  • Dies erklärt, warum solche Modelle in der Praxis oft Verallgemeinerung zeigen, aber theoretisch immer noch sehr große Datenmengen benötigen könnten.

4. Signifikanz und Diskussion

• Theoretische Erklärung für empirische Beobachtungen: Die Ergebnisse liefern eine theoretische Begründung dafür, warum Längen-Verallgemeinerung in Transformer oft instabil ist und stark von Initialisierung und Parametern abhängt. Wenn die benötigte Trainingslänge unendlich schnell wächst (unberechenbar), ist es für einen Lernprozess praktisch unmöglich, eine perfekte Verallgemeinerung zu garantieren, ohne unvorstellbar lange Trainingsdaten zu sehen.
• Unterscheidung zu Skalierungsgesetzen: Die Arbeit zeigt, dass Längen-Verallgemeinerung nicht durch konventionelle Skalierungsgesetze (mehr Parameter, mehr Daten) vorhergesagt werden kann. Es ist ein qualitativ anderes Problem, das von der strukturellen Komplexität des zu lernenden Problems abhängt.
• Praktische Konsequenz: Für die Entwicklung robuster Modelle ist es entscheidend, Architekturen oder Trainingsziele zu wählen, die in die Klasse der „positiven Fragmente" (wie Fixed-Precision) fallen, um überhaupt eine theoretische Garantie für Verallgemeinerung zu erhalten. Andernfalls bleibt die Verallgemeinerung ein Glücksspiel.

Zusammenfassung

Das Paper liefert eine definitive Antwort auf die Frage nach der Berechenbarkeit von Längen-Verallgemeinerung bei Transformern:

1. Für allgemeine Transformer (und C-RASP) ist sie unberechenbar (schon bei 2 Schichten).
2. Für Fixed-Precision Transformer (und C-RASP+) ist sie berechenbar, erfordert aber exponentielle Trainingslängen.

Dies stellt einen Meilenstein im theoretischen Verständnis der Grenzen von Transformer-Modellen dar und grenzt die Möglichkeiten der perfekten Verallgemeinerung scharf ein.