Parity, Sensitivity, and Transformers

Op basis van de verstrekte tekst volgt hier een gedetailleerde technische samenvatting van het artikel "Parity, Sensitivity, and Transformers".

Probleemstelling

Het artikel adresseert de fundamentele vraag naar de expressiviteit van Transformer-architecturen, specifiek met betrekking tot de PARITY-taak. PARITY is een Booleaanse functie die 1 oplevert als het aantal enen in een binaire invoersequentie oneven is, en 0 anderszins. Het is een canoniek probleem in de theoretische informatica, bekend om zijn hoge gevoeligheid (het omkeren van een enkel bit verandert de uitvoer).

Hoewel eerdere onderzoeken hebben vastgesteld dat Transformers met harde attentiemechanismen (specifiek Unique Hard Attention of UHAT) PARITY niet kunnen berekenen met een constante diepte, blijven de mogelijkheden van Transformers met zachte (softmax) attentie minder duidelijk. Bestaande constructies voor soft-attention Transformers die PARITY kunnen berekenen, vertrouwen op "onpraktische" aannames, zoals:

• Positieve coderingen die afhankelijk zijn van de totale invoerlengte ($n$).
• Harde attentiemechanismen.
• Laagnormalisatie met een regularisatieparameter $\epsilon = 0$.
• Incompatibiliteit met causale masking.

Bovendien bleef het een open vraag of een enkelvoudige laag (single-layer) Transformer PARITY kon berekenen.

Methodologie

De auteurs hanteren twee verschillende methodologische benaderingen om de ondergrens en de bovengrens (constructie) van de Transformer-expressiviteit voor PARITY te adresseren.

1. Ondergrens via Gemiddelde Gevoeligheid
Om te bewijzen dat een Transformer met één laag PARITY niet kan berekenen, maken de auteurs gebruik van het concept van gemiddelde gevoeligheid.

• Definitie: De gemiddelde gevoeligheid van een functie $f$ is het verwachte aantal invoer-bitposities waarbij het omkeren van het bit de uitvoer van de functie verandert. Voor PARITY is deze waarde exact $n$ (lineaire groei).
• Logica: De auteurs modelleren de berekening van een Transformer met één laag als een functie die uitdrukkelijk is in de eerste-orde logica van reële getallen $(\mathbb{R}, <, +, \cdot)$. Door het stelling van Tarski-Seidenberg (kwantoreneliminatie) toe te passen, tonen ze aan dat elke functie die door een Transformer met één laag wordt berekend, kan worden weergegeven als een Booleaanse combinatie van een vast aantal polynomiale drempelfuncties (PTF's) met lage graad.
• Bovenbegrenzing: Met verwijzing naar een resultaat van Kane stellen ze vast dat de gemiddelde gevoeligheid van PTF's met lage graad groeit met een snelheid van $O(\sqrt{n} \cdot (\log n)^{O(1)})$. Aangezien de gemiddelde gevoeligheid van PARITY lineair groeit ($n$), kan een Transformer met één laag deze niet berekenen.

2. Bovengrens via Nieuwe Constructie
Om aan te tonen dat PARITY wel berekenbaar is door een Transformer zonder onpraktische aannames, stellen de auteurs een nieuwe vierlaags constructie voor.

• Mechanisme: De constructie maakt gebruik van softmax-attentie en lengte-onafhankelijke, polynomiaal begrenste positieve coderingen. Het vermijdt laagnormalisatie en werkt onder zowel volledige attentie als causale masking.
• Algoritmische Strategie:
  1. Laag 1: Berekent een gewogen som van invoerbits om een waarde $\gamma$ af te leiden die gerelateerd is aan het aantal enen ($\Sigma$).
  2. Laag 2: Gebruikt positieve coderingen ($i \mapsto (\ln i, i^{10})$) en de waarde $\gamma$ om een gewogen gemiddelde $\Gamma$ te berekenen. Deze waarde benadert een functie $f(\rho)$ die informatie over $\Sigma$ encodeert.
  3. Laag 3: Construeert attentiegewichten $L_{i,n}$ die sterk geconcentreerd zijn op de positie $i = \Sigma$. Dit wordt bereikt door de waarde $\Gamma$ (berekend in Laag 2) te gebruiken om een specifieke kwadratische vorm te benaderen die piekt bij $i = \Sigma$. De auteurs bewijzen dat voor de juiste positie het attentiegewicht aanzienlijk groter is (met een marge van $\Omega(n^6)$) dan voor elke andere positie.
  4. Laag 4: Berekent een gewogen som van $(-1)^i$ met behulp van de geconcentreerde attentiegewichten. Het resultaat is een waarde $z$ die dicht bij $(-1)^\Sigma$ ligt, waardoor de laatste laag onderscheid kan maken tussen even en oneven pariteit.
• Omgaan met Grote Invoeren: Om gevallen te hanteren waarin het aantal enen ($\Sigma$) groot is, splitst de constructie de invoer op in $M$ subsequenties (waarbij $M$ een even constante is), berekent de pariteit van elk parallel, en aggregeert de resultaten.

Belangrijkste Bijdragen en Resultaten

1. Oplossing van het Open Probleem voor Eén Laag: Het artikel geeft een definitief antwoord op de open vraag of een Transformer met één laag PARITY kan berekenen. Het resultaat is negatief. De auteurs bewijzen dat de gemiddelde gevoeligheid van elke functie die door een Transformer met één laag kan worden berekend, begrensd is door $O(\sqrt{n} \cdot (\log n)^{O(1)})$, wat ontoereikend is voor de lineaire gevoeligheid van PARITY.
2. Verbeterde Constructie voor PARITY: De auteurs presenteren een nieuwe vierlaags Transformer-constructie die PARITY berekent. Deze constructie verbetert eerdere werken (bijv. Chiang en Cholak, 2022; Yang et al., 2025) door verschillende restrictieve aannames te verwijderen:
   • Het maakt gebruik van zachte attentie (softmax) in plaats van harde attentie.
   • Het hanteert lengte-onafhankelijke positieve coderingen.
   • Het vereist geen laagnormalisatie (of specifiek, vertrouwt niet op $\epsilon=0$).
   • Het is compatibel met causale masking.
   • De positieve coderingen zijn polynomiaal begrensd, waardoor ze haalbaar zijn voor praktische invoerlengtes.
3. Diepte-eisen: Het artikel stelt vast dat terwijl één laag ontoereikend is, vier lagen voldoende zijn onder realistische ontwerprichtlijnen. Dit verfijnt het begrip van de diepte-eisen voor het berekenen van sterk gevoelige functies.

Betekenis

Het artikel bevordert het theoretische begrip van Transformer-architecturen door hun diepte-eisen voor de PARITY-taak nauwkeurig te karakteriseren. Door de expressiviteit van Transformers te koppelen aan de gemiddelde gevoeligheid van Booleaanse functies, bieden de auteurs een rigoureuze ondergrens die modellen met één laag uitsluit. Tegelijkertijd, door een vierlaags constructie te leveren die voldoet aan standaard architecturale praktijken (zachte attentie, causale masking, begrenste coderingen), toont het artikel aan dat PARITY berekenbaar is door Transformers zonder terug te grijpen op theoretische artefacten.

De auteurs merken op dat deze resultaten helpen verklaren waarom Transformers moeite kunnen hebben om te generaliseren op taken zoals PARITY tijdens het trainen: de functie vereist een specifieke diepte en architecturale configuratie die mogelijk niet eenvoudig te leren is via standaard gradiëntafdalingsmethoden als het model te ondiep of beperkt is. Het werk vult de bestaande literatuur over de expressiviteit van modellen met harde attentie aan en biedt een realistischere baseline voor de mogelijkheden van soft-attention Transformers.