Characterizing the Expressivity of Local Attention in Transformers

1. Declaração do Problema

A arquitetura Transformer depende de um mecanismo de atenção global, que agrega informações de todos os tokens precedentes, resultando em complexidade computacional quadrática ($O(N^2)$). Para mitigar isso, a atenção local restringe a agregação a uma janela de tamanho fixo de predecessores, reduzindo a complexidade para linear ($O(N)$).

Embora a atenção local seja motivada principalmente pela eficiência, estudos empíricos mostraram que ela frequentemente melhora a qualidade do modelo (por exemplo, em tradução automática e modelagem de linguagem) mesmo quando os orçamentos computacionais são mantidos constantes. Isso apresenta um enigma teórico: Por que restringir o campo receptivo (um mecanismo aparentemente "mais fraco") às vezes leva a um melhor desempenho?

Os autores visam resolver isso caracterizando formalmente a expressividade de diferentes padrões de atenção (global, local e híbrida) em termos das linguagens formais que elas podem reconhecer.

2. Metodologia

O artigo emprega uma abordagem de teoria das linguagens formais, conectando arquiteturas Transformer à Lógica Temporal Linear (LTL) e à teoria de autômatos algébricos.

• Estrutura Teórica:

  • Os autores analisam Transformers de precisão fixa como reconhecedores de linguagens.
  • Eles mapeiam mecanismos de atenção para fragmentos da LTL:
    • Atenção Global: Corresponde à LTL[P] (Operador Passado), que permite olhar para trás arbitrariamente, mas apenas para a existência de um evento passado.
    • Atenção Local (tamanho de janela $k$): Corresponde à LTL[$Y_{\le k}$] (Operador Ontem Limitado), que verifica se uma condição se manteve nos últimos $k$ passos.
    • Atenção Híbrida: Corresponde à LTL[P, $Y_{\le k}$], combinando ambos os operadores.
  • Eles utilizam caracterizações algébricas (semigrupos sintáticos, monoides sintáticos) e propriedades teóricas de autômatos (configurações de DFA) para provar separações estritas entre esses fragmentos lógicos.

• Validação Experimental:

  • Reconhecimento de Linguagem Formal: Os autores treinaram Transformers para reconhecer classes específicas de linguagens formais (por exemplo, strings terminando em 'a', strings contendo 'ab', linguagens Dyck limitadas) com comprimentos variados para testar a generalização.
  • Modelagem de Linguagem Natural: Eles conduziram experimentos leves de previsão do próximo token no conjunto de dados WikiText-2 usando arquiteturas no estilo GPT-2-small.
  • Variáveis: Eles compararam três padrões de atenção (Apenas Global, Apenas Local, Híbrida) através de diferentes tamanhos de janela ($k \in \{1, 2, 4, \dots\}$) e codificações posicionais (Aprendida, RoPE, SiPE).

3. Principais Contribuições

A. Caracterização Teórica

1. Atenção Global = LTL[P]: Reafirma que a atenção global corresponde à lógica com um único operador passado, capaz de reconhecer polinômios left-determinísticos, mas falhando em certas tarefas baseadas em sufixos.
2. Atenção Local = LTL[$Y_{\le k}$]: Prova que a atenção local corresponde à lógica temporal limitada. Crucialmente, eles mostram que LTL[P] e LTL[$Y_{\le k}$] são incomparáveis.
   • A atenção global não consegue reconhecer linguagens definidas por sufixos específicos (por exemplo, strings terminando em 'a').
   • A atenção local não consegue reconhecer linguagens definidas por prefixos específicos (por exemplo, strings começando com 'a').
3. Atenção Híbrida = LTL[P, $Y_{\le k}$]: Demonstra que combinar atenção global e local amplia estritamente a classe de linguagens regulares reconhecíveis. O modelo híbrido pode reconhecer Linguagens Localmente Testáveis (um superconjunto de linguagens definitivas), que nem a atenção global pura nem a atenção local pura conseguem capturar totalmente.
4. Optimalidade do Tamanho de Janela $k=1$: Prova teoricamente que, dentro da família de atenção local, um tamanho de janela de $k=1$ (olhando apenas para o predecessor imediato) é estritamente mais expressivo do que janelas maiores ($k > 1$) na ausência de codificações posicionais. Isso ocorre porque $k=1$ introduz o operador "Ontem" ($Y$), que é o operador local mais poderoso.

B. Achados Empíricos

1. Generalização em Linguagens Formais:

   • Modelos Híbridos (especificamente com $k=1$) alcançaram generalização perfeita (100% de precisão) em todas as linguagens definíveis em LTL[P, Y], incluindo aquelas que falharam para modelos apenas globais ou apenas locais.
   • Modelos Apenas Globais falharam em tarefas baseadas em sufixos (LTL[Y]).
   • Modelos Apenas Locais falharam em tarefas baseadas em prefixos (LTL[P]).
   • Tamanho da Janela: $k=1$ consistentemente superou $k=2$ e $k=4$ na ausência de codificações posicionais.

2. Linguagem Natural (WikiText-2):

   • A atenção híbrida com $k=1$ consistentemente alcançou a menor perplexidade em todos os esquemas de codificação posicional (Aprendida, RoPE, SiPE).
   • A lacuna de desempenho entre modelos híbridos e apenas globais foi significativa (por exemplo, uma redução de ~69 pontos de perplexidade sob embeddings aprendidos).
   • Curiosamente, modelos apenas locais às vezes superaram modelos apenas globais, apoiando a teoria de que eles são complementares, em vez de um ser estritamente "melhor" que o outro.

3. Papel das Codificações Posicionais:

   • As lacunas teóricas entre atenção local $k=1$ e $k>1$ podem ser fechadas se as codificações posicionais atuarem como "predicados modulares" (permitindo que o modelo conte passos).
   • No entanto, na prática, codificações padrão (RoPE, SiPE) não compensaram totalmente a falta de atenção local, e os modelos híbridos permaneceram superiores.

4. Significado

• Resolvendo o "Paradoxo da Atenção Local": O artigo fornece a primeira explicação formal de por que a atenção local melhora o desempenho. Não é meramente uma otimização de velocidade; ela introduz um viés indutivo complementar (a capacidade de rastrear predecessores imediatos via o operador $Y$) que a atenção global carece.
• Diretrizes de Projeto: Os resultados sugerem fortemente que arquiteturas híbridas (misturando cabeças globais e locais) são teórica e empiricamente superiores. Além disso, eles defendem o uso de um tamanho de janela de 1 para cabeças locais, pois maximiza a expressividade ao capturar o predecessor imediato sem a sobrecarga de profundidade de janelas maiores.
• Ponte Teórica: O trabalho solidifica a conexão entre o design de arquiteturas neurais e a lógica formal, oferecendo uma lente rigorosa para prever as capacidades do modelo em tarefas que exigem tipos específicos de dependências de longo alcance ou locais.

Em resumo, os autores demonstram que a atenção local não é uma degradação da atenção global, mas um complemento necessário. Ao combinar a visão global (existência passada) com a visão local (história imediata), os transformers híbridos alcançam o fragmento mais rico de reconhecimento de linguagem regular, levando a um desempenho superior tanto em tarefas formais quanto em modelagem de linguagem natural.