Parity, Sensitivity, and Transformers

Com base no texto fornecido, segue um resumo técnico detalhado do artigo "Parity, Sensitivity, and Transformers".

Declaração do Problema

O artigo aborda a questão fundamental da expressividade das arquiteturas Transformer, especificamente em relação à tarefa PARITY (Paridade). PARITY é uma função booleana que retorna 1 se o número de 1s em uma sequência de entrada binária for ímpar, e 0 caso contrário. É um problema canônico na ciência da computação teórica, conhecido por sua alta sensibilidade (inverter qualquer bit único altera a saída).

Embora pesquisas anteriores tenham estabelecido que Transformers com mecanismos de atenção rígida (especificamente Unique Hard Attention ou UHAT) não podem calcular PARITY em profundidade constante, as capacidades de Transformers com atenção suave (softmax) permanecem menos claras. Construções existentes para Transformers de atenção suave capazes de calcular PARITY dependem de suposições "impraticáveis", tais como:

• Codificações posicionais que dependem do comprimento total da entrada ($n$).
• Mecanismos de atenção rígida.
• Normalização de camada com um parâmetro de regularização $\epsilon = 0$.
• Incompatibilidade com mascaramento causal.

Além disso, permanecia um problema em aberto se um Transformer de camada única poderia calcular PARITY.

Metodologia

Os autores empregam duas abordagens metodológicas distintas para abordar o limite inferior e o limite superior (construção) da expressividade do Transformer para PARITY.

1. Limite Inferior via Sensibilidade Média
Para provar que um Transformer de camada única não pode calcular PARITY, os autores utilizam o conceito de sensibilidade média.

• Definição: A sensibilidade média de uma função $f$ é o número esperado de posições de bits de entrada tais que inverter o bit altera a saída da função. Para PARITY, esse valor é exatamente $n$ (crescimento linear).
• Lógica: Os autores modelam o cálculo de um Transformer de camada única como uma função expressível na lógica de primeira ordem dos números reais $(\mathbb{R}, <, +, \cdot)$. Ao aplicar o teorema de Tarski-Seidenberg (eliminação de quantificadores), eles demonstram que qualquer função calculada por um Transformer de camada única pode ser representada como uma combinação booleana de um número fixo de funções de limiar polinomial de baixo grau (PTFs).
• Limitação: Citando um resultado de Kane, eles estabelecem que a sensibilidade média de PTFs de baixo grau cresce a uma taxa de $O(\sqrt{n} \cdot (\log n)^{O(1)})$. Como a sensibilidade média de PARITY cresce linearmente ($n$), um Transformer de camada única não pode calculá-lo.

2. Limite Superior via Nova Construção
Para demonstrar que PARITY é calculável por um Transformer sem suposições impraticáveis, os autores propõem uma nova construção de quatro camadas.

• Mecanismo: A construção utiliza atenção softmax e codificações posicionais independentes do comprimento e limitadas polinomialmente. Ela evita a normalização de camada e funciona tanto sob atenção total quanto sob mascaramento causal.
• Estratégia Algorítmica:
  1. Camada 1: Calcula uma soma ponderada dos bits de entrada para derivar um valor $\gamma$ relacionado à contagem de 1s ($\Sigma$).
  2. Camada 2: Utiliza codificações posicionais ($i \mapsto (\ln i, i^{10})$) e o valor $\gamma$ para calcular uma média ponderada $\Gamma$. Esse valor aproxima uma função $f(\rho)$ que codifica informações sobre $\Sigma$.
  3. Camada 3: Constrói pesos de atenção $L_{i,n}$ que estão altamente concentrados na posição $i = \Sigma$. Isso é alcançado usando o valor $\Gamma$ (calculado na Camada 2) para aproximar uma forma quadrática específica que atinge o pico em $i = \Sigma$. Os autores provam que, para a posição correta, o peso de atenção é significativamente maior (com uma margem de $\Omega(n^6)$) do que para qualquer outra posição.
  4. Camada 4: Calcula uma soma ponderada de $(-1)^i$ usando os pesos de atenção concentrados. O resultado é um valor $z$ próximo de $(-1)^\Sigma$, permitindo que a camada final distinga entre paridade par e ímpar.
• Tratamento de Entradas Grandes: Para lidar com casos onde o número de 1s ($\Sigma$) é grande, a construção divide a entrada em $M$ subsequências (onde $M$ é uma constante par), calcula a paridade de cada uma em paralelo e agrega os resultados.

Contribuições e Resultados Principais

1. Resolução do Problema Aberto de Camada Única: O artigo responde definitivamente à questão em aberto de se um Transformer de camada única pode calcular PARITY. O resultado é negativo. Os autores provam que a sensibilidade média de qualquer função calculável por um Transformer de camada única é limitada por $O(\sqrt{n} \cdot (\log n)^{O(1)})$, o que é insuficiente para a sensibilidade linear de PARITY.
2. Construção Aprimorada para PARITY: Os autores apresentam uma nova construção de Transformer de quatro camadas que calcula PARITY. Essa construção melhora trabalhos anteriores (por exemplo, Chiang e Cholak, 2022; Yang et al., 2025) ao remover várias suposições restritivas:
   • Utiliza atenção suave (softmax) em vez de atenção rígida.
   • Emprega codificações posicionais independentes do comprimento.
   • Não requer normalização de camada (ou, especificamente, não depende de $\epsilon=0$).
   • É compatível com mascaramento causal.
   • As codificações posicionais são limitadas polinomialmente, tornando-as viáveis para comprimentos de entrada práticos.
3. Requisitos de Profundidade: O artigo estabelece que, embora uma camada seja insuficiente, quatro camadas são suficientes sob restrições de design realistas. Isso refina a compreensão dos requisitos de profundidade para calcular funções altamente sensíveis.

Significado

O artigo avança a compreensão teórica das arquiteturas Transformer ao caracterizar precisamente seus requisitos de profundidade para a tarefa PARITY. Ao vincular a expressividade do Transformer à sensibilidade média de funções booleanas, os autores fornecem um limite inferior rigoroso que exclui modelos de camada única. Simultaneamente, ao fornecer uma construção de quatro camadas que adere a práticas arquitetônicas padrão (atenção suave, mascaramento causal, codificações limitadas), o artigo demonstra que PARITY é calculável por Transformers sem recorrer a artefatos teóricos.

Os autores observam que esses resultados ajudam a explicar por que os Transformers podem ter dificuldade em generalizar em tarefas como PARITY durante o treinamento: a função requer uma profundidade específica e uma configuração arquitetônica que podem não ser facilmente aprendidas por métodos padrão de descida de gradiente se o modelo for muito raso ou restrito. O trabalho complementa a literatura existente sobre a expressividade de modelos de atenção rígida e fornece uma linha de base mais realista para as capacidades de Transformers de atenção suave.