Average Attention Transformers and Arithmetic Circuits

Technische Samenvatting: Gemiddelde Aandacht Transformers en Aritmetische Circuits

Probleemstelling
Bestaande theoretische analyses van de expressiviteit van Transformers hebben zich voornamelijk gericht op beslissingsproblemen over eindige alfabetten, waarbij Transformers worden vergeleken met Booleaanse circuitklassen (bijvoorbeeld $AC^0$, $TC^0$) of logische formalismen. Deze resultaten zijn beperkt tot taalherkenning. Dit artikel adresseert een lacune in het begrip van de rekenkracht van Transformers als sequentie-naar-sequentie-functies die opereren op vectoren van reële of rationale getallen. De auteurs beogen de expressiviteit van Transformer-encoders te karakteriseren door ze direct te vergelijken met aritmetische circuits, die functies over halfringen berekenen met behulp van bewerkingen zoals optelling, vermenigvuldiging en de tekenfunctie.

Methodologie
De auteurs passen een gegeneraliseerd Transformer-model (gebaseerd op Hao et al., 2022) aan om te opereren over willekeurige halfringen. Belangrijke methodologische keuzes omvatten:

1. Modeldefinitie: Zij definiëren "gemiddelde-aandacht-circuittransformers", waarbij de standaard feed-forward netwerken worden vervangen door aritmetische circuits, en het aandachtsmechanisme gebruikmaakt van "gemiddelde harde aandacht" (het richten op alle vectoren met maximale aandachtscores).
2. Circuitfamilies: Zij analyseren drie klassen van aritmetische circuitfamilies met constante diepte en polynomiale grootte:
   • $FNC^0_R$: Beperkte fan-in.
   • $FSAC^0_R$: Semi-onbeperkte fan-in (onbeperkte optelling, binaire vermenigvuldiging).
   • $FAC^0_R$: Onbeperkte fan-in (onbeperkte optelling en vermenigvuldiging).
     Deze klassen worden uitgebreid met de teken-functie om discontinu operaties te behandelen.
3. Simulatieconstructie:
   • Circuits naar Transformers: Om een circuit te simuleren, coderen de auteurs de grafstructuur van het circuit (poorten en randen) in een sequentie van vectoren. Elke vector vertegenwoordigt een rand of een poort, en bevat indices voor voorgangers/nopvolgers, poorttypes en waarden.
   • Aandachtsmechanismen: Zij ontwerpen specifieke aandachtsfuncties ($f^{att}_E$ en $f^{att}_V$) die vectoren in staat stellen zich te richten op hun voorgangers op basis van indexovereenstemming.
   • Pooling en Activering: Zij maken gebruik van gemiddelde harde aandachtspooling om waarden van voorgangers te aggregeren. Cruciaal is dat zij activeringsfuncties construeren die de juiste bewerking selecteren (optelling, vermenigvuldiging of identiteit) op basis van het in de vector gecodeerde poorttype.
   • Omgaan met schaling: Aangezien gemiddelde aandacht resultaten schaalt met $1/k$ (waarbij $k$ het aantal bekeken vectoren is), bevat de constructie mechanismen om voorgangers te tellen en de output te herschalen om de juiste aritmetische waarde te herstellen.

Belangrijkste Resultaten
Het artikel vestigt een precieze correspondentie tussen de rekenkracht van deze specifieke Transformers en aritmetische circuitklassen:

1. Bovenste Grens: Voor elke halfring $R$ zijn de functies die door gemiddelde-aandacht-circuittransformers worden berekend, bevat in de klasse $FSAC^0_R[\text{teken}]$. Dit geldt zelfs voor standaard Transformers met typische gemiddelde aandacht, mits hun activeringsfuncties beperkt zijn tot dezelfde circuitklasse.
2. Onderste Grens (Simulatie): Als de onderliggende halfring $R$ een $\mathbb{Z}$-geordende ringuitbreiding is van de rationale getallen ($\mathbb{Q}$), dan bestaat er voor elke circuitfamilie in $FSAC^0_R[\text{teken}]$ met diepte $K$ een Transformer met $2K$ lagen die de gehele familie kan simuleren.
   • De simulatie werkt voor circuits met onbeperkte fan-in met behulp van gemiddelde aandacht.
   • Voor circuits met semi-onbeperkte fan-in kan de constructie worden aangepast om standaard dot-product-aandacht te gebruiken.
   • Voor circuits met beperkte fan-in kan de constructie verder worden beperkt tot het gebruik van linkermste of rechtste harde aandacht.
3. Specifieke Stellingen:
   • Stelling 4.5: Een Transformer met dimensie 7 en $2K$ lagen kan elke $R$-circuit met onbeperkte fan-in en diepte $\le K$ simuleren (waarbij $R$ een $\mathbb{Z}$-geordende uitbreiding is van $\mathbb{Q}$).
   • Stelling 4.11: Een Transformer met dimensie 9 en $2K$ lagen kan elke $FSAC^0_R[\text{teken}]$-circuit simuleren.

Betekenis en Claims
De auteurs claimen dat hun resultaten een nieuw perspectief bieden op Transformer-expressiviteit door de velden van machinelearningtheorie en algebraïsche berekening te verbinden.

• Theoretische Equivalentie: Zij demonstreren dat gemiddelde-aandacht-Transformers computationeel equivalent zijn aan de klasse van aritmetische circuits met constante diepte, onbeperkte optelling, binaire vermenigvuldiging en tekenpoorten ($FSAC^0_R[\text{teken}]$).
• Beperkingen: Het artikel merkt expliciet op dat deze equivalentie berust op het feit dat de Transformer aritmetische circuits (of equivalente functies) gebruikt als activeringsfuncties. Standaard Transformers met feed-forward netwerken kunnen deze circuits niet simuleren, omdat feed-forward netwerken inherent niet in staat zijn de vermenigvuldiging van twee willekeurige invoeren uit te voeren die voor de simulatie vereist is.
• Niet-uniformiteit: De auteurs verduidelijken dat hoewel Transformers specifieke circuitfamilies kunnen simuleren, dit niet impliceert dat elke functie in $FSAC^0_R[\text{teken}]$ wordt berekend door een enkele Transformer, aangezien circuitfamilies een niet-uniform model van berekening zijn.
• Toekomstpotentieel: Het artikel suggereert dat theoretische vooruitgang in algebraïsche berekening machinelearningtheorie ten goede kan komen en vice versa, en dat theoretische resultaten praktische ontwikkelingen kunnen inspireren, hoewel er geen specifieke toepassingen worden voorgesteld.

Het werk wordt gepresenteerd als een preprint (mei 2026) van het Instituut voor Theoretische Informatica aan de Leibniz Universiteit Hannover.