Characterizing the Expressivity of Local Attention in Transformers

1. Enunciato del Problema

L'architettura Transformer si basa su un meccanismo di attenzione globale, che aggrega informazioni da tutti i token precedenti, risultando in una complessità computazionale quadratica ($O(N^2)$). Per mitigare ciò, l'attenzione locale limita l'aggregazione a una finestra fissa di predecessori, riducendo la complessità a lineare ($O(N)$).

Sebbene l'attenzione locale sia motivata principalmente dall'efficienza, studi empirici hanno dimostrato che spesso migliora la qualità del modello (ad esempio, nella traduzione automatica e nella modellazione linguistica) anche quando i budget computazionali sono mantenuti costanti. Ciò presenta un enigma teorico: Perché limitare il campo ricettivo (un meccanismo apparentemente "più debole") porta talvolta a prestazioni migliori?

Gli autori mirano a risolvere ciò caratterizzando formalmente l'espressività di diversi pattern di attenzione (globale, locale e ibida) in termini dei linguaggi formali che possono riconoscere.

2. Metodologia

Il lavoro adotta un approccio basato sulla teoria dei linguaggi formali, collegando le architetture Transformer alla Logica Temporale Lineare (LTL) e alla teoria degli automi algebrica.

• Quadro Teorico:

  • Gli autori analizzano i Transformer a precisione fissa come riconoscitori di linguaggi.
  • Mappano i meccanismi di attenzione su frammenti di LTL:
    • Attenzione Globale: Corrisponde a LTL[P] (Operatore Passato), che permette di guardare indietro arbitrariamente ma solo all'esistenza di un evento passato.
    • Attenzione Locale (dimensione finestra $k$): Corrisponde a LTL[$Y_{\le k}$] (Operatore Ieri Limitato), che verifica se una condizione è valsa negli ultimi $k$ passi.
    • Attenzione Ibrida: Corrisponde a LTL[P, $Y_{\le k}$], combinando entrambi gli operatori.
  • Utilizzano caratterizzazioni algebriche (semigruppi sintattici, monoidi sintattici) e proprietà teoriche degli automi (configurazioni DFA) per dimostrare separazioni strette tra questi frammenti logici.

• Validazione Sperimentale:

  • Riconoscimento di Linguaggi Formali: Gli autori hanno addestrato Transformer a riconoscere classi specifiche di linguaggi formali (ad esempio, stringhe che terminano con 'a', stringhe contenenti 'ab', linguaggi Dyck limitati) con lunghezze variabili per testare la generalizzazione.
  • Modellazione del Linguaggio Naturale: Hanno condotto esperimenti leggeri di previsione del token successivo sul dataset WikiText-2 utilizzando architetture nello stile di GPT-2-small.
  • Variabili: Hanno confrontato tre pattern di attenzione (Solo Globale, Solo Locale, Ibrido) attraverso diverse dimensioni di finestra ($k \in \{1, 2, 4, \dots\}$) e codifiche posizionali (Apprese, RoPE, SiPE).

3. Contributi Chiave

A. Caratterizzazione Teorica

1. Attenzione Globale = LTL[P]: Ribadisce che l'attenzione globale corrisponde alla logica con un singolo operatore passato, capace di riconoscere polinomi left-deterministici ma fallente in certi compiti basati sui suffissi.
2. Attenzione Locale = LTL[$Y_{\le k}$]: Dimostra che l'attenzione locale corrisponde alla logica temporale limitata. Crucialmente, mostrano che LTL[P] e LTL[$Y_{\le k}$] sono incomparabili.
   • L'attenzione globale non può riconoscere linguaggi definiti da suffissi specifici (ad esempio, stringhe che terminano con 'a').
   • L'attenzione locale non può riconoscere linguaggi definiti da prefissi specifici (ad esempio, stringhe che iniziano con 'a').
3. Attenzione Ibrida = LTL[P, $Y_{\le k}$]: Dimostra che combinare attenzione globale e locale amplia strettamente la classe dei linguaggi regolari riconoscibili. Il modello ibrido può riconoscere i Linguaggi Localmente Testabili (un soprainsieme dei linguaggi definitivi), che né l'attenzione globale pura né quella locale pura possono catturare completamente.
4. Ottimalità della Dimensione della Finestra $k=1$: Dimostra teoricamente che all'interno della famiglia dell'attenzione locale, una dimensione di finestra di $k=1$ (guardare solo al predecessore immediato) è strettamente più espressiva di finestre più grandi ($k > 1$) in assenza di codifiche posizionali. Questo perché $k=1$ introduce l'operatore "Ieri" ($Y$), che è l'operatore locale più potente.

B. Risultati Empirici

1. Generalizzazione su Linguaggi Formali:

   • I modelli ibridi (in particolare con $k=1$) hanno raggiunto una generalizzazione perfetta (100% di accuratezza) su tutti i linguaggi definibili in LTL[P, Y], inclusi quelli che fallivano per i modelli solo-globali o solo-locali.
   • I modelli Solo Globali fallivano su compiti basati sui suffissi (LTL[Y]).
   • I modelli Solo Locali fallivano su compiti basati sui prefissi (LTL[P]).
   • Dimensione della Finestra: $k=1$ ha costantemente superato $k=2$ e $k=4$ in assenza di codifiche posizionali.

2. Linguaggio Naturale (WikiText-2):

   • L'attenzione ibrida con $k=1$ ha costantemente raggiunto la perplessità più bassa attraverso tutti gli schemi di codifica posizionale (Apprese, RoPE, SiPE).
   • Il divario di prestazioni tra i modelli ibridi e quelli solo-globali è stato significativo (ad esempio, una riduzione di ~69 punti di perplessità sotto embedding appresi).
   • Interessantemente, i modelli solo-locali hanno talvolta superato i modelli solo-globali, supportando la teoria che essi siano complementari piuttosto che uno strettamente "migliore" dell'altro.

3. Ruolo delle Codifiche Posizionali:

   • I divari teorici tra l'attenzione locale $k=1$ e $k>1$ possono essere colmati se le codifiche posizionali agiscono come "predicati modulari" (permettendo al modello di contare i passi).
   • Tuttavia, nella pratica, le codifiche standard (RoPE, SiPE) non hanno compensato pienamente la mancanza di attenzione locale, e i modelli ibridi sono rimasti superiori.

4. Significato

• Risoluzione del "Paradosso dell'Attenzione Locale": Il lavoro fornisce la prima spiegazione formale del motivo per cui l'attenzione locale migliora le prestazioni. Non è semplicemente un'ottimizzazione della velocità; introduce un bias induttivo complementare (la capacità di tracciare i predecessori immediati tramite l'operatore $Y$) che manca all'attenzione globale.
• Linee Guida di Progettazione: I risultati suggeriscono fortemente che le architetture ibride (che mescolano teste globali e locali) sono teoricamente ed empiricamente superiori. Inoltre, raccomandano l'uso di una dimensione di finestra di 1 per le teste locali, poiché massimizza l'espressività catturando il predecessore immediato senza il sovraccarico di profondità di finestre più grandi.
• Ponte Teorico: Il lavoro solidifica la connessione tra la progettazione delle architetture neurali e la logica formale, offrendo una lente rigorosa per prevedere le capacità del modello su compiti che richiedono specifici tipi di dipendenze a lungo raggio o locali.

In sintesi, gli autori dimostrano che l'attenzione locale non è un degrado dell'attenzione globale ma un complemento necessario. Combinando la visione globale (esistenza passata) con la visione locale (storia immediata), i transformer ibridi raggiungono il frammento più ricco del riconoscimento dei linguaggi regolari, portando a prestazioni superiori sia nei compiti formali che nella modellazione del linguaggio naturale.