Average Attention Transformers and Arithmetic Circuits

Resumo Técnico: Transformers de Atenção Média e Circuitos Aritméticos

Enunciado do Problema
As análises teóricas existentes sobre a expressividade dos Transformers focaram-se principalmente em problemas de decisão sobre alfabetos finitos, comparando os Transformers a classes de circuitos booleanos (por exemplo, $AC^0$, $TC^0$) ou formalismos lógicos. Estes resultados limitam-se ao reconhecimento de linguagens. Este artigo aborda uma lacuna na compreensão do poder computacional dos Transformers como funções sequência-para-sequência que operam sobre vetores de números reais ou racionais. Os autores visam caracterizar a expressividade dos codificadores de Transformers comparando-os diretamente com circuitos aritméticos, que computam funções sobre semirings utilizando operações como adição, multiplicação e a função sinal.

Metodologia
Os autores adaptam um modelo de Transformer generalizado (baseado em Hao et al., 2022) para operar sobre semirings arbitrários. As escolhas metodológicas-chave incluem:

1. Definição do Modelo: Eles definem "transformers de circuito de atenção média", onde as redes feed-forward padrão são substituídas por circuitos aritméticos, e o mecanismo de atenção utiliza "atenção dura média" (atendendo a todos os vetores com pontuações de atenção máximas).
2. Famílias de Circuitos: Eles analisam três classes de famílias de circuitos aritméticos com profundidade constante e tamanho polinomial:
   • $FNC^0_R$: Entrada limitada (bounded fan-in).
   • $FSAC^0_R$: Entrada semi-ilimitada (adição ilimitada, multiplicação binária).
   • $FAC^0_R$: Entrada ilimitada (adição e multiplicação ilimitadas).
     Estas classes são estendidas com a função sign para lidar com operações descontínuas.
3. Construção de Simulação:
   • Circuitos para Transformers: Para simular um circuito, os autores codificam a estrutura de grafo do circuito (portas e arestas) em uma sequência de vetores. Cada vetor representa uma aresta ou uma porta, contendo índices para predecessores/sucessores, tipos de porta e valores.
   • Mecanismos de Atenção: Eles projetam funções de atenção específicas ($f^{att}_E$ e $f^{att}_V$) que permitem que os vetores atendam aos seus predecessores com base na correspondência de índices.
   • Agrupamento e Ativação: Eles utilizam o agrupamento de atenção dura média para agregar valores dos predecessores. Crucialmente, eles constroem funções de ativação que selecionam a operação apropriada (adição, multiplicação ou identidade) com base no tipo de porta codificado no vetor.
   • Tratamento de Escala: Como a atenção média escala os resultados por $1/k$ (onde $k$ é o número de vetores atendidos), a construção inclui mecanismos para contar predecessores e reescalar a saída para recuperar o valor aritmético correto.

Resultados Principais
O artigo estabelece uma correspondência precisa entre o poder computacional desses Transformers específicos e as classes de circuitos aritméticos:

1. Limite Superior: Para qualquer semiring $R$, as funções computadas por transformers de circuito de atenção média estão contidas na classe $FSAC^0_R[\text{sign}]$. Isso vale mesmo para Transformers padrão com atenção média típica, desde que suas funções de ativação sejam restritas à mesma classe de circuitos.
2. Limite Inferior (Simulação): Se o semiring subjacente $R$ for uma extensão de anel ordenado por $\mathbb{Z}$ dos racionais ($\mathbb{Q}$), então, para qualquer família de circuitos em $FSAC^0_R[\text{sign}]$ com profundidade $K$, existe um Transformer com $2K$ camadas que pode simular toda a família.
   • A simulação funciona para circuitos de entrada ilimitada usando atenção média.
   • Para circuitos de entrada semi-ilimitada, a construção pode ser adaptada para usar atenção padrão de produto escalar.
   • Para circuitos de entrada limitada, a construção pode ser ainda mais restrita para usar atenção dura à esquerda ou à direita.
3. Teoremas Específicos:
   • Teorema 4.5: Um Transformer com dimensão 7 e $2K$ camadas pode simular qualquer circuito $R$ de entrada ilimitada com profundidade $\le K$ (onde $R$ é uma extensão ordenada por $\mathbb{Z}$ de $\mathbb{Q}$).
   • Teorema 4.11: Um Transformer com dimensão 9 e $2K$ camadas pode simular qualquer circuito $FSAC^0_R[\text{sign}]$.

Significado e Alegações
Os autores afirmam que seus resultados fornecem uma nova perspectiva sobre a expressividade dos Transformers, unindo os campos da teoria da aprendizagem de máquina e do cálculo algébrico.

• Equivalência Teórica: Eles demonstram que os Transformers de atenção média são computacionalmente equivalentes à classe de circuitos aritméticos de profundidade constante com adição ilimitada, multiplicação binária e portas de sinal ($FSAC^0_R[\text{sign}]$).
• Limitações: O artigo nota explicitamente que essa equivalência depende do Transformer usar circuitos aritméticos (ou funções equivalentes) como funções de ativação. Transformers padrão com redes feed-forward não podem simular esses circuitos porque as redes feed-forward não podem inerentemente realizar a multiplicação de duas entradas arbitrárias necessária para a simulação.
• Não Uniformidade: Os autores esclarecem que, embora os Transformers possam simular famílias de circuitos específicas, isso não implica que toda função em $FSAC^0_R[\text{sign}]$ seja computada por um único Transformer, pois as famílias de circuitos são um modelo de computação não uniforme.
• Potencial Futuro: O artigo sugere que avanços teóricos no cálculo algébrico poderiam beneficiar a teoria da aprendizagem de máquina e vice-versa, e que resultados teóricos podem inspirar desenvolvimentos práticos, embora nenhuma aplicação específica seja proposta.

O trabalho é apresentado como um pré-impresso (maio de 2026) do Instituto de Ciência da Computação Teórica da Universidade Leibniz de Hanover.