Average Attention Transformers and Arithmetic Circuits

Riepilogo Tecnico: Trasformatori a Media Attenzione e Circuiti Aritmetici

Enunciato del Problema
Le analisi teoriche esistenti sull'espressività dei Trasformatori si sono concentrate principalmente su problemi decisionali su alfabeti finiti, confrontando i Trasformatori con classi di circuiti booleani (ad esempio, $AC^0$, $TC^0$) o formalismi logici. Questi risultati sono limitati al riconoscimento del linguaggio. Questo lavoro affronta una lacuna nella comprensione del potere computazionale dei Trasformatori come funzioni da sequenza a sequenza che operano su vettori di numeri reali o razionali. Gli autori mirano a caratterizzare l'espressività degli encoder Trasformatore confrontandoli direttamente con i circuiti aritmetici, che calcolano funzioni su semianelli utilizzando operazioni come addizione, moltiplicazione e la funzione segno.

Metodologia
Gli autori adattano un modello Trasformatore generalizzato (basato su Hao et al., 2022) per operare su semianelli arbitrari. Le scelte metodologiche chiave includono:

1. Definizione del Modello: Definiscono i "trasformatori a circuito di attenzione media", in cui le reti feed-forward standard sono sostituite da circuiti aritmetici, e il meccanismo di attenzione utilizza "attenzione dura media" (che presta attenzione a tutti i vettori con punteggi di attenzione massimali).
2. Famiglie di Circuiti: Analizzano tre classi di famiglie di circuiti aritmetici con profondità costante e dimensione polinomiale:
   • $FNC^0_R$: Fan-in limitato.
   • $FSAC^0_R$: Fan-in semi-sconfinato (addizione sconfinata, moltiplicazione binaria).
   • $FAC^0_R$: Fan-in sconfinato (addizione e moltiplicazione sconfinata).
     Queste classi sono estese con la funzione sign per gestire operazioni discontinue.
3. Costruzione della Simulazione:
   • Da Circuiti a Trasformatori: Per simulare un circuito, gli autori codificano la struttura del grafo del circuito (porte e archi) in una sequenza di vettori. Ogni vettore rappresenta un arco o una porta, contenente indici per predecessori/successori, tipi di porta e valori.
   • Meccanismi di Attenzione: Progettano funzioni di attenzione specifiche ($f^{att}_E$ e $f^{att}_V$) che permettono ai vettori di prestare attenzione ai loro predecessori basandosi sulla corrispondenza degli indici.
   • Pooling e Attivazione: Utilizzano il pooling di attenzione dura media per aggregare i valori dai predecessori. Crucialmente, costruiscono funzioni di attivazione che selezionano l'operazione appropriata (addizione, moltiplicazione o identità) in base al tipo di porta codificato nel vettore.
   • Gestione della Scalatura: Poiché l'attenzione media scala i risultati per $1/k$ (dove $k$ è il numero di vettori a cui si presta attenzione), la costruzione include meccanismi per contare i predecessori e riscalare l'output per recuperare il corretto valore aritmetico.

Risultati Chiave
Il lavoro stabilisce una corrispondenza precisa tra il potere computazionale di questi specifici Trasformatori e le classi di circuiti aritmetici:

1. Limite Superiore: Per ogni semianello $R$, le funzioni calcolate dai trasformatori a circuito di attenzione media sono contenute nella classe $FSAC^0_R[\text{sign}]$. Ciò vale anche per i Trasformatori standard con attenzione media tipica, a condizione che le loro funzioni di attivazione siano limitate alla stessa classe di circuiti.
2. Limite Inferiore (Simulazione): Se il semianello sottostante $R$ è un'estensione ordinata su $\mathbb{Z}$ dei razionali ($\mathbb{Q}$), allora per qualsiasi famiglia di circuiti in $FSAC^0_R[\text{sign}]$ con profondità $K$, esiste un Trasformatore con $2K$ livelli che può simulare l'intera famiglia.
   • La simulazione funziona per circuiti a fan-in sconfinato utilizzando l'attenzione media.
   • Per i circuiti a fan-in semi-sconfinato, la costruzione può essere adattata per utilizzare l'attenzione standard a prodotto scalare.
   • Per i circuiti a fan-in limitato, la costruzione può essere ulteriormente ristretta per utilizzare l'attenzione dura sinistra o destra.
3. Teoremi Specifici:
   • Teorema 4.5: Un Trasformatore con dimensione 7 e $2K$ livelli può simulare qualsiasi circuito $R$ a fan-in sconfinato di profondità $\le K$ (dove $R$ è un'estensione ordinata su $\mathbb{Z}$ di $\mathbb{Q}$).
   • Teorema 4.11: Un Trasformatore con dimensione 9 e $2K$ livelli può simulare qualsiasi circuito $FSAC^0_R[\text{sign}]$.

Significato e Affermazioni
Gli autori affermano che i loro risultati offrono una nuova prospettiva sull'espressività dei Trasformatori colmando i campi della teoria dell'apprendimento automatico e del calcolo algebrico.

• Equivalenza Teorica: Dimostrano che i Trasformatori a attenzione media sono computazionalmente equivalenti alla classe dei circuiti aritmetici a profondità costante con addizione sconfinata, moltiplicazione binaria e porte segno ($FSAC^0_R[\text{sign}]$).
• Limitazioni: Il lavoro nota esplicitamente che questa equivalenza dipende dal fatto che il Trasformatore utilizzi circuiti aritmetici (o funzioni equivalenti) come funzioni di attivazione. I Trasformatori standard con reti feed-forward non possono simulare questi circuiti perché le reti feed-forward non possono intrinsecamente eseguire la moltiplicazione di due input arbitrari richiesta per la simulazione.
• Non Uniformità: Gli autori chiariscono che, sebbene i Trasformatori possano simulare specifiche famiglie di circuiti, ciò non implica che ogni funzione in $FSAC^0_R[\text{sign}]$ sia calcolata da un singolo Trasformatore, poiché le famiglie di circuiti sono un modello di calcolo non uniforme.
• Potenziale Futuro: Il lavoro suggerisce che i progressi teorici nel calcolo algebrico potrebbero avvantaggiare la teoria dell'apprendimento automatico e viceversa, e che i risultati teorici potrebbero ispirare sviluppi pratici, sebbene non vengano proposte applicazioni specifiche.

Il lavoro è presentato come un preprint (maggio 2026) dell'Istituto di Informatica Teorica dell'Università di Leibniz di Hannover.