Technische Samenvatting: Expressiviteitsanalyse van Hiërarchische Modellering in Diepe Transformers via Grammatica's met Begrensde Diepte

Probleemstelling

Diepe neurale netwerken, in het bijzonder transformers, vertonen empirisch de eigenschap dat ze expressieve kracht ontlenen aan het vormen van hiërarchische representaties, waarbij ze abstracte en compositionele kenmerken over verschillende lagen heen vastleggen. In taalmodellering vangen vroege transformer-lagen lokale syntactische patronen op, terwijl latere lagen complexe clausale afhankelijkheden coderen. Ondanks het feit dat deze intuïtie het ontwerp van modellen vormgeeft, is er een gebrek aan rigoureus theoretisch werk dat aantoont hoe diepe transformers dergelijke hiërarchische structuren representeren.

Bestaande theoretische analyses richten zich vaak op beperkte settings, zoals Dyck-talen (gebalanceerde haakjes) of eindige toestandsautomaten, die de complexe vertakkende structuren van echte grammatica's missen. Bovendien ondersteunen empirische studies (bijv. Allen-Zhu & Li, 2025; Saglam et al., 2025) de "lineaire representatiehypothese"—die aantoont dat abstracte grammaticale toestanden kunnen worden teruggevonden via lineaire probes in de residual streams—maar deze werken verklaren niet theoretisch waarom transformer-architecturen de structurele capaciteit bezitten om deze complexe structuren expliciet te coderen in laagdimensionale, lineair scheidbare subruimten.

Dit artikel adresseert deze kloof door de expressiviteit van diepe transformer-modellen te analyseren vanuit de formele lens van begrensde diepte, niet-recursieve contextvrije grammatica's (CFG's). Het doel is om een expliciete constructie te bieden van een transformer die dergelijke grammatica's voorspellend kan modelleren, waardoor de mechanica van hiërarchische compositionaliteit wordt geformaliseerd.

Methodologie

De auteurs formaliseren het probleem met behulp van een specifieke klasse CFG's met de volgende eigenschappen:

• Vaste diepte ($d$): Elke afleidingsboom heeft exact een hoogte $d$.
• Niet-recursief: De grammatica's genereren eindige talen, waardoor onbegrensde nesting wordt vermeden.
• Uniformiteit: Productieregels voor een gegeven niet-terminaal hebben dezelfde lengte.
• Begrensde parameters: De analyse beschouwt het maximale aantal regels ($M$), de maximale vertakkingsfactor ($B$) en het aantal geldige afleidingsboomvormen ($c = |C(G)|$).

De auteurs construeren een decoder-only transformer met een positionele attention-mechanisme om deze grammatica's te modelleren. De constructie rust op drie kerncomponenten:

1. Sparse Attention Heads: Het model maakt gebruik van een vereenvoudigd relatief positioneel attention-mechanisme waarbij de attention-gewichten alleen afhangen van de positie van tokens, niet van de inhoud. Dit maakt "harde" attention mogelijk die specifieke tokens selecteert op basis van hun positie in de afleidingsboom.
2. Hiërarchische Verwerking: De diepte van de transformer groeit lineair met de diepte van de grammatica ($d$). Elk transformer-blok komt overeen met een niveau in de grammaticale hiërarchie en verwerkt constituenten van de bladeren (terminalen) naar de wortel (start symbool).
3. Feedforward Memorisatie: Position-wise feedforward networks (FFN's) worden geconstrueerd om te fungeren als discrete lookup-tabellen. Gebruikmakend van resultaten over de memorisatiecapaciteit van neurale netwerken (Zhang et al., 2017), mappen deze lagen de geaggregeerde lokale syntactische contexten naar de ouderlijke niet-terminale symbolen.

De constructie implementeert een bottom-up dynamisch programmeeralgoritme (vergelijkbaar met de CKY-parser) waarbij:

• Attention Heads lokale syntactische contexten van kind-nodes aggregeren om de grenzen van grammaticale constituenten te identificeren.
• FFN's de resulterende ouderlijke niet-terminale symbolen coderen in de residual stream, waarbij lagere niveaus worden behouden via residual connections.
• Laatste Lagen gestapelde feedforward networks gebruiken om geldige volgende-woord-voorspellingen te berekenen op basis van de geaccumuleerde hiërarchische toestanden.

Belangrijkste Bijdragen

1. Expliciete Transformer Constructie: Het artikel levert een constructief bewijs dat een transformer met diepte $d$ (lineair in de grammaticale diepte) een uniforme, niet-recursieve CFG van diepte $d$ voorspellend kan modelleren.
2. Schaalbaarheidsgrenzen: De auteurs leiden specifieke grenzen af voor de benodigde modelgrootte:
   • Diepte: Groeit lineair met de grammaticale diepte ($d$).
   • Aantal Neuronen: Schaalt lineair met het aantal afleidingsboomvormen ($c$) en kwadratisch met het aantal productieregels ($M$).
   • Hidden Dimensie: Schaalt met $c \cdot d$.
3. Theoretische Onderbouwing van Lineaire Representatie: De constructie toont aan dat de architectuur de structurele capaciteit bezit om abstracte grammaticale toestanden te coderen in laagdimensionale, lineair scheidbare subruimten binnen de residual stream. Specifiek, voor een vaste afleidingsboomvorm vinden parsing-berekeningen plaats in onderscheidende subruimten, waardoor niet-terminale symbolen geïsoleerd kunnen worden via eenvoudige affine transformaties.
4. Differentiatie van Voorgaand Werk: In tegen tegenstelling tot eerdere grenzen die schalen met de maximale zinlengte (die exponentieel kan zijn in de grammaticale diepte), schaalt deze constructie met de grammaticale diepte zelf. Dit benadrukt de efficiëntie van hiërarchische modellering ten opzichte van platte representaties (zoals n-grammen of eindige toestandsautomaten, die exponentiële toestandsruimtes zouden vereisen voor diepe CFG's).

Resultaten

Het belangrijkste theoretische resultaat (Theorem 4.1) stelt dat er voor elke $\epsilon > 0$ een transformer taalmodel $f_T$ bestaat dat de taal $L(G)$ voorspellend modelleert met een fout van maximaal $\epsilon$. Het model bestaat uit $d$ transformer-blokken gevolgd door $5d + 7$ feedforward-lagen.

• Efficiëntie: Het aantal vereiste lagen is lineair in de grammaticale diepte, een significante verbetering ten opzichte van constructies waarbij het aantal lagen schaalt met de zinlengte.
• Sparsity: De constructie maakt gebruik van een sparse circuit waarbij elke inputsequentie wordt verwerkt door een enkele attention head per blok, wat aansluit bij empirische bevindingen over sparse computationele subgrafen in deep learning.
• Lineaire Scheidbaarheid: Het bewijs toont aan dat niet-terminale symbolen op een bepaald diepteniveau worden gemapt naar vectoren in een subruimte van de bijbehorende residual stream, wat de lineaire representatiehypothese ondersteunt. De auteurs merken echter op dat hun constructie een strikt orthogonale basis gebruikt (onderscheidende indicator-neuronen), terwijl empirische modellen dit waarschijnlijk bereiken via dense superpositie.

Betekenis en Beperkingen

Betekenis:
Het artikel biedt een rigoureus existentiebewijs dat diepe transformers expliciet hiërarchische grammaticale structuren kunnen representeren. Het overbrugt de kloof tussen empirische observaties van lineaire representaties en theoretische architecturale capaciteiten. Door te formaliseren hoe transformers bottom-up dynamische programmering kunnen implementeren, biedt het werk een theoretische fundering voor waarom diepere architecturen effectief zijn bij het vastleggen van complexe linguïstische structuren zonder te lijden onder de "vloek van dimensionaliteit" die gepaard gaat met platte modellen.

Beperkingen:

• Vereenvoudigd Kader: De analyse is beperkt tot bounded-depth, niet-recursieve CFG's. Het adresseert niet direct recursieve grammatica's of oneindige talen, hoewel het kader wordt genoteerd als een abstractie voor het analyseren van hiërarchische compositionaliteit.
• Orthogonaal vs. Superpositie: De theoretische constructie steunt op een orthogonale basisruimte waar elke grammaticale toestand een toegewezen neuron heeft. Dit vereenvoudigt het bewijs, maar houdt geen rekening met het "superpositie"-fenomeen dat in echte modellen wordt waargenomen, waarbij kenmerken worden gecomprimeerd in dichte vectoren. Begrijpen hoe standaard trainingsdynamiek dergelijke gecomprimeerde representaties voortbrengt, blijft een open vraag.
• Schaalbaarheid naar Real-world Corpora: De grenzen zijn afhankelijk van $c$ (het aantal boomvormen), wat groot kan zijn. Hoewel het kader de kernmechanismen formaliseert, erkennen de auteurs dat het nog geen nauwe grenzen oplevert voor complexe real-world corpora zoals de Penn Treebank.

Concluderend legt dit werk de basis voor het begrijpen van de interne werking van transformer-modellen door middel van formele taaltheorie, en suggereert het dat de diepte van de transformer van nature de diepte weerspiegelt van de grammaticale hiërarchie die het modelleert.