💬 NLP

An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars

Diese Arbeit liefert eine theoretische Analyse, die zeigt, dass tiefe Transformer über die strukturelle Kapazität verfügen, abstrakte grammatikalische Zustände aus kontextfreien Grammatiken mit beschränkter Tiefe in niedrigdimensionale, linear separierbare Unterräume zu kodieren, und validiert damit die Hypothese der linearen Repräsentation für hierarchische Modellierung.

Ursprüngliche Autoren: Vinoth Nandakumar, Qiang Qu, Pramod Thebe, Sakshi Khachariya, Tongliang Liu

Veröffentlicht 2026-06-17

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Vinoth Nandakumar, Qiang Qu, Pramod Thebe, Sakshi Khachariya, Tongliang Liu

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 Roboter beizubringen, die komplexe, verschachtelte Struktur der menschlichen Sprache zu verstehen. Sie wissen, dass Sätze nicht einfach nur zufällige Wortfolgen sind; sie sind aufgebaut wie russische Matroschka-Puppen oder ein Stammbaum, bei dem kleine Wortgruppen Phrasen bilden, Phrasen Klauseln bilden und Klauseln Sätze bilden.

Dieses Paper stellt eine grundlegende Frage: Wie baut ein tiefes neuronales Netz (speziell ein „Transformer“, das Gehirn hinter moderner KI) tatsächlich diese mentalen Bäume auf?

Obwohl wir wissen, dass diese Modelle darin gut sind, hatten wir keinen klaren mathematischen Beweis dafür, wie sie das schaffen, ohne davon überwältigt zu werden. Dieses Paper liefert diesen Beweis, indem es einen „theoretischen Roboter“ konstruiert, der eine bestimmte Art von Sprachrätsel perfekt verstehen kann.

Hier ist die Aufschlüsselung ihrer Entdeckung unter Verwendung einfacher Analogien:

1. Das Problem: Das „Unendliche“ vs. das „Begrenzte“

Sprache ist theoretisch unendlich. Man kann Sätze unendlich oft in Sätze verschachteln (z. B. „Die Katze, die der Hund, der der Mann...“). Menschliche Gehirne haben jedoch Grenzen; wir können nur eine bestimmte Anzahl von Verschachtelungsschichten gleichzeitig in unserem Arbeitsgedächtnis halten.

Die Forscher entschieden sich, das Problem zu vereinfachen. Anstatt zu versuchen, unendliche Rekursion zu modellieren, untersuchten sie beschränkt tiefe Grammatiken (bounded-depth grammars). Denken Sie an eine Sprache, in der jeder Satz garantiert genau 3 oder 4 Ebenen tief ist, nicht mehr. Es ist, als würde man ein Haus bauen, mit der strengen Regel: „Jedes Haus muss genau 3 Stockwerke haben.“ Dies macht die Struktur vorhersehbar und leichter mathematisch analysierbar.

2. Die Lösung: Das „geschichtete Fließband“

Die Autoren konstruierten einen spezifischen Typ eines Transformer-Modells, um zu beweisen, dass es solche Rätsel lösen kann. Sie sagten nicht nur „es funktioniert einfach“; sie bauten die Maschine Teil für Teil auf, um genau zu zeigen, wie sie funktioniert.

Sie verglichen die Schichten des Transformers mit einem Fließband oder einer Baustelle:

Der Input: Stellen Sie sich einen Haufen roher Ziegelsteine (Wörter) vor.
Die Schichten: Der Transformer hat viele übereinander gestapelte Schichten.
- Schicht 1 betrachtet die Ziegelsteine und klebt sie zusammen, um kleine Wände (einfache Phrasen) zu bilden.
- Schicht 2 nimmt diese Wände und klebt sie zusammen, um Räume (Klauseln) zu bilden.
- Schicht 3 nimmt die Räume und setzt sie zu einem vollständigen Haus (dem Satz) zusammen.
Die Magie: Das Paper beweist, dass, wenn Ihre Sprache eine Tiefe von $d$ hat (z. B. 3 Stockwerke), Sie nur einen Transformer mit $d$ Schichten benötigen, um sie perfekt zu verstehen. Die Tiefe des Modells wächst linear mit der Komplexität der Sprache. Sie benötigen keine massive, exponentielle Explosion von Schichten; Sie benötigen lediglich eine Schicht für jede Ebene der Hierarchie.

3. Der „Attention“-Mechanismus: Das Klemmbrett des Vorarbeiters

Wie weiß das Modell, welche Ziegelsteine es zusammenkleben soll? Das Paper beschreibt den „Attention“-Mechanismus (den Teil des Transformers, der entscheidet, worauf er sich konzentriert) als einen Vorarbeiter mit einem Klemmbrett.

In ihrer Konstruktion schaut der Vorarbeiter nicht auf die gesamte chaotische Baustelle auf einmal. Stattdessen hat er eine spezifische, vorprogrammierte Regel: „Schaue nur auf die Ziegelsteine, die zu dieser spezifischen Gruppe gehören.“

Er ignoriert alles andere.
Er konzentriert sich nur auf die unmittelbaren Nachbarn, die benötigt werden, um die nächste Ebene darüber zu bauen.
Dies wird als Sparse Attention bezeichnet. Es ist wie ein Scheinwerfer, der nur auf die spezifischen Arbeiter leuchtet, die einen Ziegelstein an die Person darüber weiterreichen müssen.

4. Die Entdeckung der „Linearen Repräsentation“

Eine der spannendsten Behauptungen des Papers betrifft die Frage, wo das Modell diese Informationen speichert.

Es gibt eine Theorie in der KI namens „Linear Representation Hypothesis“. Sie besagt, dass komplexe Ideen (wie „dies ist eine Nominalphrase“) im Gehirn des Modells als einfache, gerade Linien in einem hochdimensionalen Raum gespeichert werden.

Die Autoren haben dies für ihr konstruiertes Modell mathematisch bewiesen. Sie zeigten:

Das Modell erstellt einen spezifischen „Ordner“ oder einen Subraum für jede Art von grammatikalischer Struktur.
Wenn das Modell eine „Nominalphrase“ baut, leuchtet eine spezifische, einfache Linie in seiner internen Mathematik auf.
Wenn es zu einer „Verbalphrase“ übergeht, leuchtet eine andere, deutlich unterscheidbare Linie auf.
Diese Linien sind orthogonal (wie die X- und Y-Achsen in einem Diagramm), was bedeutet, dass sie sich nicht überschneiden oder gegenseitig verwirren.

Dies erklärt, warum „Probing“ (eine Technik, bei der Forscher das Modell testen, um zu sehen, was es weiß) so gut funktioniert. Das Modell versteckt die Grammatik nicht in einem chaotischen, verhedderten Knoten; es sortiert sie ordentlich in geraden, leicht lesbaren Linien ab.

5. Warum das wichtig ist (laut dem Paper)

Das Paper behauptet nicht, dass dies sofort Krankheiten heilen oder selbstfahrende Autos bauen wird. Es behauptet vielmehr, ein theoretisches Rätsel gelöst zu haben:

Es beweist Effizienz: Es zeigt, dass Transformer nicht exponentiell groß sein müssen, um komplexe Grammatik zu verstehen. Sie müssen nur tief genug sein, um der Tiefe der Sprache zu entsprechen.
Es validiert die „Lineare Hypothese“: Es liefert einen strengen mathematischen Beweis dafür, dass diese Modelle in der Lage sind, komplexe Regeln in einfachen, linearen Strukturen zu organisieren, was bestätigt, was empirische Experimente jahrelang vermutet haben.
Es schließt die Lücke: Es verbindet die abstrakte Mathematik der „Kontextfreien Grammatiken“ (klassische Linguistik) mit der modernen Architektur der „Transformer“ (moderne KI) und zeigt, dass sie kompatibler sind, als wir dachten.

Zusammenfassende Analogie

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, einen komplexen Origami-Kranich zu falten.

Alte Sichtweise: Wir dachten, der Roboter müsste jede einzelne mögliche Kranichform auswendig lernen, was ein Gehirn von der Größe einer Galaxie erfordern würde.
Diese Sichtweise des Papers: Wir haben bewiesen, dass, wenn Sie dem Roboter eine Schritt-für-Schritt-Anleitung (eine Grammatik) geben, bei der der Kranich eine feste Anzahl von Faltungen hat, der Roboter nur ein Gehirn mit einer Anzahl an Schritten benötigt, die der Anzahl der Faltungen entspricht. Darüber hinaus organisiert der Roboter diese Schritte in ordentlichen, separaten Ordnern (linearen Subräumen), damit er nie verwirrt wird, welcher Faltschritt als Nächstes kommt.

Das Paper sagt im Wesentlichen: „Wir haben einen theoretischen Roboter gebaut, der beweist, dass Deep-Learning-Modelle natürlich gut darin sind, hierarchische Strukturen aufzubauen, und dass sie dies, indem sie Informationen auf eine überraschend einfache, lineare Weise organisieren.“

Technisches Resümee: Expressivitätsanalyse der hierarchischen Modellierung in tiefen Transformern mittels beschränkter Tiefengrammatiken

Problemstellung

Tiefe neuronale Netze, insbesondere Transformer, zeigen empirisch beobachtbar eine expressive Kraft, die aus der Bildung hierarchischer Repräsentationen resultiert und abstrakte sowie kompositionale Merkmale über Schichten hinweg erfasst. In der Sprachmodellierung erfassen frühe Transformer-Schichten lokale syntaktische Muster, während spätere Schichten komplexe klauselbasierte Abhängigkeiten kodieren. Trotz der Tatsache, dass diese Intuition das Modelldesign prägt, mangelt es an fundierter theoretischer Arbeit, die nachweist, wie tiefe Transformer solche hierarchischen Strukturen repräsentieren.

Bestehende theoretische Analysen konzentrieren sich oft auf eingeschränkte Settings, wie etwa Dyck-Sprachen (balancierte Klammern) oder endliche Automaten, denen die komplexen Verzweigungsstrukturen realer Grammatiken fehlen. Darüber hinaus stützen zwar empirische Studien (z. B. Allen-Zhu & Li, 2025; Saglam et al., 2525) die „Hypothese der linearen Repräsentation“ – indem sie zeigen, dass abstrakte grammatikalische Zustände über lineare Probes im Residualstrom rekonstruiert werden können –, diese Arbeiten erklären jedoch nicht theoretisch, warum Transformer-Architekturen die strukturelle Kapazität besitzen, diese komplexen Strukturen explizit in niedrigdimensionalen, linear separierbaren Subräumen zu kodieren.

Diese Arbeit adressiert die Lücke, indem sie die Expressivität tiefer Transformer-Modelle durch die formale Linse von beschränkter Tiefe, nicht-rekursiver kontextfreier Grammatiken (CFGs) analysiert. Das Ziel ist eine explizite Konstruktion eines Transformers, der solche Grammatiken prädiktiv modellieren kann, um die Mechanik der hierarchischen Kompositionalität zu formalisieren.

Methodik

Die Autoren formalisieren das Problem unter Verwendung einer spezifischen Klasse von CFGs mit den folgenden Eigenschaften:

Feste Tiefe ( $d$ ): Jeder Ableitungsbaum hat exakt die Höhe $d$ .
Nicht-rekursiv: Die Grammatiken erzeugen endliche Sprachen und vermeiden unbegrenzte Verschachtelung.
Uniformität: Produktionsregeln für ein gegebenes Nicht-Terminal haben dieselbe Länge.
Beschränkte Parameter: Die Analyse betrachtet die maximale Regelanzahl ( $M$ ), den maximalen Verzweigungsfaktor ( $B$ ) und die Anzahl der gültigen Ableitungsbaum-Formen ( $c = |C(G)|$ ).

Die Autoren konstruieren einen Decoder-only Transformer mit einem positionellen Attention-Mechanismus, um diese Grammatiken zu modellieren. Die Konstruktion stützt sich auf drei Kernkomponenten:

Sparse Attention Heads: Das Modell nutzt einen vereinfachten relativen Position-Attention-Mechanismus, bei dem die Attention-Gewichte nur von Token-Positionen abhängen, nicht vom Inhalt. Dies ermöglicht eine „harte“ Attention, die spezifische Token basierend auf ihrer Position im Ableitungsbaum auswählt.
Hierarchische Verarbeitung: Die Tiefe des Transformers wächst linear mit der Grammatiktiefe ( $d$ ). Jeder Transformer-Block entspricht einer Ebene in der grammatikalischen Hierarchie und verarbeitet Konstituenten von den Blättern (Terminals) aufwärts bis zur Wurzel (Startsymbol).
Feedforward-Memorierung: Positionswiese Feedforward-Netzwerke (FFNs) werden so konstruiert, dass sie als diskrete Look-up-Tabellen fungieren. Unter Verwendung von Ergebnissen zur Memorierungskapazität neuronaler Netze (Zhang et al., 2017), bilden diese Schichten aggregierte lokale syntaktische Kontexte auf übergeordnete Nicht-Terminal-Symbole ab.

Die Konstruktion implementiert einen Bottom-up-Dynamikprogramm-Algorithmus (ähnlich dem CKY-Parser), wobei:

Attention Heads lokale syntaktische Kontexte von Kindknoten aggregieren, um die Grenzen grammatikalischer Konstituenten zu identieren.
FFNs die resultierenden Eltern-Nicht-Terminal-Symbole in den Residualstrom kodieren und dabei unterer Ebene liegende Zustände über Residualverbindungen bewahren.
Letzte Schichten gestapelte Feedforward-Netzwerke nutzen, um gültige nächste Wort-Vorhersagen basierend auf den akkumulierten hierarchischen Zuständen zu berechnen.

Zentrale Beiträge

Explizite Transformer-Konstruktion: Die Arbeit liefert einen konstruktiven Beweis, dass ein Transformer der Tiefe $d$ (linear zur Grammatiktiefe) eine uniforme, nicht-rekursive CFG der Tiefe $d$ prädiktiv modellieren kann.
Skalierbarkeitsgrenzen: Die Autoren leiten spezifische Schranken für die Modellgröße ab:
- Tiefe: Wächst linear mit der Grammatiktiefe ( $d$ ).
- Neuronenanzahl: Skaliert linear mit der Anzahl der Ableitungsbaum-Formen ( $c$ ) und quadratisch mit der Anzahl der Produktionsregeln ( $M$ ).
- Verborgene Dimension: Skaliert mit $c \cdot d$ .
Theoretische Unterstützung der linearen Repräsentation: Die Konstruktion zeigt, dass die Architektur die strukturelle Kapazität besitzt, abstrakte grammatikalische Zustände in niedrigdimensionalen, linear separierbaren Subräumen innerhalb des Residualstroms zu kodieren. Speziell für eine feste Ableitungsbaum-Form finden Parsing-Berechnungen in distinkten Subräumen statt, was es ermöglicht, Nicht-Terminal-Symbole durch einfache affine Transformationen zu isolieren.
Abgrenzung zu vorangegangener Arbeit: Im Gegensatz zu früheren Schranken, die mit der maximalen Satzlänge skalieren (welche in der Grammatiktiefe exponentiell sein kann), skaliert diese Konstruktion mit der Grammatiktiefe selbst. Dies unterstreicht die Effizienz hierarchischer Modellierung gegenüber flachen Repräsentationen (wie n-Grammen oder endlichen Automaten, die exponentielle Zustandsräume für tiefe CFGs erfordern würden).

Ergebnisse

Das zentrale theoretische Resultat (Theorem 4.1) etabliert, dass für jedes $\epsilon > 0$ ein Transformer-Sprachmodell $f_T$ existiert, das die Sprache $L(G)$ mit einem Fehler von höchstens $\epsilon$ prädiktiv modelliert. Das Modell besteht aus $d$ Transformer-Blöcken gefolgt von $5d + 7$ Feedforward-Schichten.

Effizienz: Die Anzahl der benötigten Schichten ist linear in der Grammatiktiefe, was eine signifikante Verbesserung gegenüber Konstruktionen darstellt, bei denen die Schichtanzahl mit der Satzlänge skaliert.
Sparsity: Die Konstruktion nutzt einen spärlichen Schaltkreis (sparse circuit), bei dem jede Eingabesequenz durch einen einzelnen Attention Head pro Block verarbeitet wird, was mit empirischen Befunden über spärliche computationale Subgraphen im Deep Learning übereinstimmt.
Lineare Separierbarkeit: Der Beweis zeigt, dass Nicht-Terminal-Symbole einer gegebenen Tiefe auf Vektoren in einem Subraum des entsprechenden Residualstroms abgebildet werden, was die Hypothese der linearen Repräsentation stützt. Die Autoren merken jedoch an, dass ihre Konstruktion eine strikt orthogonale Basis (distinkte Indikator-Neuronen) verwendet, während reale Modelle dies wahrscheinlich über dichte Superposition erreichen.

Bedeutung und Limitationen

Bedeutung:
Die Arbeit bietet einen rigorosen Existenzbeweis dafür, dass tiefe Transformer explizit hierarchische grammatikalische Strukturen repräsentieren können. Sie schließt die Lücke zwischen empirischen Beobachtungen linearer Repräsentationen und den theoretischen Fähigkeiten der Architektur. Durch die Formalisierung, wie Transformer ein Bottom-up-Dynamikprogramm implementieren können, liefert die Arbeit eine theoretische Grundlage dafür, warum tiefere Architekturen effektiv darin sind, komplexe linguistische Strukturen zu erfassen, ohne unter dem „Fluch der Dimensionalität“ flacher Modelle zu leiden.

Limitationen:

Vereinfachtes Framework: Die Analyse beschränkt sich auf beschränkte Tiefen, nicht-rekursive CFGs. Sie adressiert nicht direkt rekursive Grammatiken oder unendliche Sprachen, obwohl das Framework als Abstraktion zur Analyse hierarchischer Kompositionalität bezeichnet wird.
Orthogonalität vs. Superposition: Die theoretische Konstruktion beruht auf einem orthogonalen Basisraum, in dem jeder grammatikalische Zustand ein dediziertes Neuron besitzt. Dies vereinfacht den Beweis, berücksichtigt aber nicht das Phänomen der „Superposition“, das in realen Modellen beobachtet wird, wo Merkmale in dichten Vektoren komprimiert werden. Zu verstehen, wie Standard-Trainingsdynamiken solche komprimierten Repräsentationen hervorbringen, bleibt eine offene Frage.
Skalierbarkeit auf reale Korpora: Die Schranken hängen von $c$ (der Anzahl der Baumformen) ab, was groß sein kann. Während das Framework die Kernmechanismen formalisiert, räumen die Autoren ein, dass es noch keine engen Schranken für komplexe reale Korpora wie die Penn Treebank liefert.

Zusammenfassend legt diese Arbeit den Grundstein für das Verständnis der inneren Funktionsweise von Transformer-Modellen durch die formale Sprachtheorie und legt nahe, dass die Tiefe des Transformers die Tiefe der zu modellierenden grammatikalischen Hierarchie natürlich widerspiegelt.