🤖 machine learning

Parity, Sensitivity, and Transformers

Dieser Beitrag löst die offene Frage, ob einlagige Transformer die PARITY-Aufgabe berechnen können, indem er nachweist, dass sie dies aufgrund von Sensitivitätsbeschränkungen nicht können, und präsentiert gleichzeitig eine praktische Konstruktion eines vierlagigen Transformers, der PARITY löst, ohne auf zuvor notwendige unpraktische Annahmen wie längenabhängige Positionsencodierung oder Hardmax zurückzugreifen.

Ursprüngliche Autoren: Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

Veröffentlicht 2026-05-08

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

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

Stellen Sie sich vor, Sie versuchen, einem sehr intelligenten, aber leicht starren Roboter beizubringen, ein einfaches Spiel namens „Das Paritäts-Spiel" zu spielen.

In diesem Spiel wird dem Roboter eine lange Reihe von Lichtern gezeigt, einige rot (0) und einige blau (1). Die einzige Aufgabe des Roboters besteht darin, eine Frage zu beantworten: „Ist die Gesamtzahl der blauen Lichter gerade oder ungerade?"

Wenn es 3 blaue Lichter gibt, lautet die Antwort „Ungerade". Wenn es 4 gibt, lautet die Antwort „Gerade".

Das klingt für uns einfach, doch für eine bestimmte Art von KI-Architektur, die als Transformer bezeichnet wird (die Art, die viele moderne Chatbots und Übersetzer antreibt), war dieses Spiel ein Rätsel. Wissenschaftler haben diskutiert: Wie viele „Denkschichten" benötigt dieser Roboter, um das Spiel zu lösen?

Hier ist das, was diese Arbeit entdeckt hat, einfach erklärt:

1. Der „Ein-Schichten"-Roboter ist zu dumm

Die Autoren stellten zunächst die Frage: Kann ein Transformer mit nur einer Denkschicht dieses Problem lösen?

Sie bewiesen, dass die Antwort nein lautet.

Die Analogie: Stellen Sie sich vor, der Roboter ist eine Person, die in einem Raum voller Menschen steht, die rote oder blaue Karten hochhalten. Die Person kann nur alle gleichzeitig ansehen und einen schnellen „Durchschnittsblick" werfen.

Das „Paritäts"-Spiel ist unglaublich empfindlich. Wenn Sie die Karte nur einer Person von rot auf blau ändern, kehrt sich die Antwort vollständig um (von Gerade zu Ungerade).
Die Autoren zeigten, dass ein Ein-Schichten-Roboter zu „glatt" und zu „faul" ist. Er kann nicht scharf genug auf eine einzelne Änderung reagieren. Es ist, als würde man versuchen, das Fallenlassen einer einzigen Nadel in einem Hurrikan zu erkennen, indem man nur die durchschnittliche Windgeschwindigkeit hört. Die „Empfindlichkeit" des Roboters wächst zu langsam, um die winzigen, entscheidenden Änderungen zu erfassen, die zur Lösung des Spiels nötig sind.

Das Urteil: Man benötigt mindestens zwei Denkschichten, um dies zu lösen.

2. Die „alten Lösungen" hatten zu viele Tricks

Bevor diese Arbeit veröffentlicht wurde, hatten andere Wissenschaftler herausgefunden, wie man einen Transformer baut, der das Spiel lösen kann, aber sie mussten dabei einige „Tricks" oder unrealistische Einstellungen verwenden:

Der „Magische Lineal": Sie gaben dem Roboter ein Lineal, das die genaue Länge der Zeichenkette bevor er mit dem Lesen begann kannte (z. B. „Diese Zeichenkette ist genau 1.000 Zeichen lang"). Echte Roboter wissen die Länge des Satzes, den sie lesen, normalerweise erst, wenn sie fertig sind.
Der „Perfekte Schalter": Sie verwendeten einen „harten Schalter", der binäre Entscheidungen sofort trifft, anstatt die „weichen, verschwommenen" Wahrscheinlichkeitsschalter, die echte Roboter verwenden.
Der „Null-Fehler"-Filter: Sie entfernten einen Sicherheitsfilter (LayerNorm genannt), der normalerweise verhindert, dass die Zahlen des Roboters ins Unendliche explodieren.

Diese Lösungen funktionierten auf dem Papier, würden aber in der realen Welt nicht funktionieren, da sie Annahmen basierten, die im tatsächlichen KI-Training nicht existieren.

3. Die neue, realweltliche Lösung

Die Autoren dieser Arbeit bauten einen neuen Roboter, der das Paritäts-Spiel löst, ohne einen dieser Tricks zu verwenden.

Kein magisches Lineal: Es verwendet eine „längenunabhängige" Positions-Kodierung. Es muss die Gesamtlänge der Zeichenkette nicht im Voraus kennen; es betrachtet einfach, wo Dinge relativ zueinander stehen.
Weiche Schalter: Es verwendet standardmäßige „weiche" Aufmerksamkeit (die Art, die in echten Chatbots verwendet wird).
Sicherheitsfilter: Es funktioniert, ohne dass Sicherheitsfilter entfernt werden müssen.
Der Haken: Um dies ohne Tricks zu tun, benötigt der Roboter vier Denkschichten anstatt zwei.

Die Analogie:
Stellen Sie sich die alten „Trick"-Lösungen wie einen Zauberer vor, der ein Rätsel löst, indem er in den Antwortenschlüssel schaut, der unter dem Tisch versteckt ist.
Die neue Lösung ist wie ein Meisterdetektiv, der dasselbe Rätsel löst, indem er jede Spur sorgfältig untersucht, sie miteinander abgleicht und etwas mehr Arbeit leistet (vier Schichten anstatt zwei). Es ist etwas langsamer und erfordert mehr „Gehirnkraft" (Tiefe), aber es funktioniert vor einem echten Gericht, nicht nur auf einer magischen Bühne.

Zusammenfassung des Durchbruchs

Untere Schranke: Ein Transformer mit nur einer Schicht ist mathematisch unfähig, das Paritäts-Spiel zu lösen. Es ist kein Trainingsproblem; der Roboter hat buchstäblich nicht die Architektur, um es zu tun.
Obere Schranke: Man kann das Spiel mit einem Transformer lösen, aber um dies auf realistische Weise zu tun (ohne mit längenabhängigen Tricks zu schummeln oder Sicherheitsfilter zu entfernen), benötigt man vier Schichten.

Die Arbeit zieht im Wesentlichen eine klare Linie in den Sand: „Wenn Sie eine realistische KI haben wollen, die ungerade und gerade Zahlen zählt, geben Sie ihr mindestens vier Schichten Tiefe. Alles weniger ist mathematisch unmöglich."

Basierend auf dem bereitgestellten Text folgt eine detaillierte technische Zusammenfassung des Papers „Parity, Sensitivity, and Transformers".

Problemstellung

Das Paper adressiert die fundamentale Frage der Ausdruckskraft von Transformer-Architekturen, speziell in Bezug auf die PARITY-Aufgabe. PARITY ist eine boolesche Funktion, die 1 ausgibt, wenn die Anzahl der 1en in einer binären Eingabesequenz ungerade ist, und 0 andernfalls. Es handelt sich um ein kanonisches Problem der theoretischen Informatik, das für seine hohe Sensitivität bekannt ist (das Umkehren eines einzelnen Bits ändert die Ausgabe).

Während frühere Forschung gezeigt hat, dass Transformer mit harten Aufmerksamkeitsmechanismen (speziell Unique Hard Attention oder UHAT) PARITY nicht in konstanter Tiefe berechnen können, bleiben die Fähigkeiten von Transformern mit weichen (Softmax-)Aufmerksamkeit weniger klar. Bestehende Konstruktionen für Soft-Aufmerksamkeits-Transformer, die PARITY berechnen können, beruhen auf „unpraktischen" Annahmen, wie zum Beispiel:

Positionscodierungen, die von der gesamten Eingabelänge ( $n$ ) abhängen.
Harte Aufmerksamkeitsmechanismen.
Schichtnormalisierung mit einem Regularisierungsparameter $\epsilon = 0$ .
Inkompatibilität mit kausaler Maskierung.

Darüber hinaus war es ein offenes Problem, ob ein einlagiger Transformer PARITY berechnen kann.

Methodik

Die Autoren wenden zwei unterschiedliche methodische Ansätze an, um die untere Schranke und die obere Schranke (Konstruktion) der Ausdruckskraft von Transformern für PARITY zu adressieren.

1. Untere Schranke via Durchschnittliche Sensitivität
Um zu beweisen, dass ein einlagiger Transformer PARITY nicht berechnen kann, nutzen die Autoren das Konzept der durchschnittlichen Sensitivität.

Definition: Die durchschnittliche Sensitivität einer Funktion $f$ ist die erwartete Anzahl von Eingabe-Bitpositionen, sodass das Umkehren des Bits die Ausgabe der Funktion ändert. Für PARITY beträgt dieser Wert genau $n$ (lineares Wachstum).
Logik: Die Autoren modellieren die Berechnung eines einlagigen Transformers als eine Funktion, die in der Prädikatenlogik erster Stufe der reellen Zahlen $(\mathbb{R}, <, +, \cdot)$ ausdrückbar ist. Durch Anwendung des Tarski-Seidenberg-Theorems (Quantorenelimination) zeigen sie, dass jede von einem einlagigen Transformer berechnete Funktion als boolesche Kombination einer festen Anzahl von polynomialen Schwellwertfunktionen (PTFs) niedrigen Grades dargestellt werden kann.
Abschätzung: Unter Berufung auf ein Ergebnis von Kane stellen sie fest, dass die durchschnittliche Sensitivität von PTFs niedrigen Grades mit einer Rate von $O(\sqrt{n} \cdot (\log n)^{O(1)})$ wächst. Da die durchschnittliche Sensitivität von PARITY linear wächst ( $n$ ), kann ein einlagiger Transformer sie nicht berechnen.

2. Obere Schranke via Neue Konstruktion
Um zu demonstrieren, dass PARITY von einem Transformer ohne unpraktische Annahmen berechenbar ist, schlagen die Autoren eine neue vierlagige Konstruktion vor.

Mechanismus: Die Konstruktion verwendet Softmax-Aufmerksamkeit und längenunabhängige, polynomial beschränkte Positionscodierungen. Sie verzichtet auf Schichtnormalisierung und funktioniert sowohl unter Voll-Aufmerksamkeit als auch unter kausaler Maskierung.
Algorithmische Strategie:
1. Schicht 1: Berechnet eine gewichtete Summe der Eingabebits, um einen Wert $\gamma$ abzuleiten, der mit der Anzahl der 1en ( $\Sigma$ ) zusammenhängt.
2. Schicht 2: Nutzt Positionscodierungen ( $i \mapsto (\ln i, i^{10})$ ) und den Wert $\gamma$ , um einen gewichteten Durchschnitt $\Gamma$ zu berechnen. Dieser Wert approximiert eine Funktion $f(\rho)$ , die Informationen über $\Sigma$ kodiert.
3. Schicht 3: Konstruiert Aufmerksamkeitsgewichte $L_{i,n}$ , die stark auf die Position $i = \Sigma$ konzentriert sind. Dies wird erreicht, indem der Wert $\Gamma$ (berechnet in Schicht 2) verwendet wird, um eine spezifische quadratische Form zu approximieren, die bei $i = \Sigma$ ihr Maximum erreicht. Die Autoren beweisen, dass für die korrekte Position das Aufmerksamkeitsgewicht signifikant größer ist (mit einem Rand von $\Omega(n^6)$ ) als für jede andere Position.
4. Schicht 4: Berechnet eine gewichtete Summe von $(-1)^i$ unter Verwendung der konzentrierten Aufmerksamkeitsgewichte. Das Ergebnis ist ein Wert $z$ , der nahe an $(-1)^\Sigma$ liegt, was der letzten Schicht ermöglicht, zwischen gerader und ungerader Parität zu unterscheiden.
Umgang mit großen Eingaben: Um Fälle zu behandeln, in denen die Anzahl der 1en ( $\Sigma$ ) groß ist, teilt die Konstruktion die Eingabe in $M$ Teilsequenzen auf (wobei $M$ eine gerade Konstante ist), berechnet die Parität jeder davon parallel und aggregiert die Ergebnisse.

Wichtige Beiträge und Ergebnisse

Lösung des offenen Problems der einlagigen Architektur: Das Paper beantwortet die offene Frage, ob ein einlagiger Transformer PARITY berechnen kann, eindeutig. Das Ergebnis ist negativ. Die Autoren beweisen, dass die durchschnittliche Sensitivität jeder von einem einlagigen Transformer berechenbaren Funktion durch $O(\sqrt{n} \cdot (\log n)^{O(1)})$ beschränkt ist, was für die lineare Sensitivität von PARITY unzureichend ist.
Verbesserte Konstruktion für PARITY: Die Autoren präsentieren eine neue vierlagige Transformer-Konstruktion, die PARITY berechnet. Diese Konstruktion verbessert frühere Arbeiten (z. B. Chiang und Cholak, 2022; Yang et al., 2025), indem sie mehrere restriktive Annahmen entfernt:
- Sie verwendet weiche Aufmerksamkeit (Softmax) statt harter Aufmerksamkeit.
- Sie employs längenunabhängige Positionscodierungen.
- Sie benötigt keine Schichtnormalisierung (oder spezifisch, verlässt sich nicht auf $\epsilon=0$ ).
- Sie ist mit kausaler Maskierung kompatibel.
- Die Positionscodierungen sind polynomial beschränkt, was sie für praktische Eingabelängen machbar macht.
Tiefenanforderungen: Das Paper stellt fest, dass zwar eine Schicht unzureichend ist, vier Schichten jedoch unter realistischen Designbeschränkungen ausreichen. Dies verfeinert das Verständnis der Tiefenanforderungen für die Berechnung hochsensitiver Funktionen.

Bedeutung

Das Paper erweitert das theoretische Verständnis von Transformer-Architekturen, indem es ihre Tiefenanforderungen für die PARITY-Aufgabe präzise charakterisiert. Indem die Autoren die Ausdruckskraft von Transformern mit der durchschnittlichen Sensitivität boolescher Funktionen verknüpfen, liefern sie eine strenge untere Schranke, die einlagige Modelle ausschließt. Gleichzeitig demonstriert das Paper durch Bereitstellung einer vierlagigen Konstruktion, die gängige architektonische Praktiken einhält (weiche Aufmerksamkeit, kausale Maskierung, beschränkte Codierungen), dass PARITY von Transformern berechenbar ist, ohne auf theoretische Artefakte zurückgreifen zu müssen.

Die Autoren weisen darauf hin, dass diese Ergebnisse helfen zu erklären, warum Transformer möglicherweise Schwierigkeiten haben, sich während des Trainings auf Aufgaben wie PARITY zu verallgemeinern: Die Funktion erfordert eine spezifische Tiefe und architektonische Konfiguration, die möglicherweise nicht leicht durch Standard-Gradientenabstiegsverfahren erlernt werden kann, wenn das Modell zu flach oder eingeschränkt ist. Die Arbeit ergänzt die bestehende Literatur zur Ausdruckskraft von Modellen mit harter Aufmerksamkeit und liefert eine realistischere Basislinie für die Fähigkeiten von Soft-Aufmerksamkeits-Transformern.