Resumo Técnico: Análise de Expressividade de Modelagem Hierárquica em Transformers Profundos via Gramáticas de Profundidade Limitada

Declaração do Problema

Redes neurais profundas, particularmente os transformers, são empiricamente observadas ao derivar poder expressivo através da formação de representações hierárquicas, capturando características abstratas e composicionais através das camadas. Na modelagem de linguagem, as camadas iniciais do transformer capturam padrões sintáticos locais, enquanto as camadas posteriores codificam dependências complexas de nível de cláusula. Apesar de essa intuição moldar o design de modelos, há uma carência de trabalhos teóricos rigorosos que demonstrem como os transformers profundos representam tais estruturas hierárquicas.

Análises teóricas existentes frequentemente focam em configurações restritas, como linguagens Dyck (parênteses balanceados) ou autômatos de estados finitos, que carecem das estruturas de ramificação complexas das gramáticas do mundo real. Além disso, embora estudos empíricos (ex: Allen-Zhu & Li, 2025; Saglam et al., 2025) apoiem a "hipótese da representação linear" — mostrando que estados gramaticais abstratos podem ser recuperados via sondas lineares no fluxo residual — esses trabalhos não explicam teoricamente por que as arquiteturas de transformer possuem a capacidade estrutural para codificar explicitamente essas estruturas complexas em subespaços de baixa dimensão e linearmente separáveis.

Este artigo aborda essa lacuna analisando a expressividade de modelos transformer profundos através da lente formal de gramáticas livres de contexto (CFGs) de profundidade limitada e não recursivas. O objetivo é fornecer uma construção explícita de um transformer que possa modelar preditivamente tais gramáticas, formalizando, assim, a mecânica da composicionalidade hierárquica.

Metodologia

Os autores formalizam o problema usando uma classe específica de CFGs com as seguintes propriedades:

• Profundidade Fixa ($d$): Cada árvore de derivação possui uma altura exatamente igual a $d$.
• Não Recursiva: As gramáticas geram linguagens finitas, evitando o aninhamento ilimitado.
• Uniformidade: As regras de produção para um determinado não-terminal possuem o mesmo comprimento.
• Parâmetros Limitados: A análise considera a contagem máxima de regras ($M$), o fator de ramificação máximo ($B$) e o número de formas de árvores de derivação válidas ($c = |C(G)|$).

Os autores constroem um transformer apenas-decodificador (decoder-only) com um mecanismo de atenção posicional para modelar essas gramáticas. A construção baseia-se em três componentes centrais:

1. Cabeças de Atenção Esparsa: O modelo utiliza um mecanismo de atenção posicional relativa simplificado onde os pesos de atenção dependem apenas das posições dos tokens, não do conteúdo. Isso permite uma atenção "rígida" (hard attention) que seleciona tokens específicos com base em sua posição na árvore de derivação.
2. Processamento Hierárquico: A profundidade do transformer cresce linearmente com a profundidade da gramática ($d$). Cada bloco de transformer corresponde a um nível na hierarquia gramatical, processando constituintes das folhas (terminais) até a raiz (símbolo inicial).
3. Memorização por Feedforward: Redes de feedforward (FFNs) por posição são construídas para atuar como tabelas de consulta (look-up tables) discretas. Utilizando resultados sobre a capacidade de memorização de redes neurais (Zhang et al., 2017), essas camadas mapeiam contextos sintáticos locais agregados para símbolos de não-terminais pais.

A construção implementa um algoritmo de programação dinâmica bottom-up (semelhante ao parser CKY) onde:

• Cabeças de Atenção agregam contextos sintáticos locais de nós filhos para identificar as fronteiras dos constituintes gramaticais.
• FFNs codificam os símbolos de não-terminais pais resultantes no fluxo residual, preservando estados de níveis inferiores via conexões residuais.
• Camadas Finais utilizam redes feedforward empilhadas para computar predições de próximas palavras válidas baseadas nos estados hierárquicos acumulados.

Principais Contribuições

1. Construção Explícita de Transformer: O artigo fornece uma prova construtiva de que um transformer com profundidade $d$ (linear à profundidade da gramática) pode modelar preditivamente CFGs uniformes e não recursivas de profundidade $d$.
2. Limites de Escalabilidade: Os autores derivam limites específicos para o tamanho do modelo exigido:
   • Profundidade: Cresce linearmente com a profundidade da gramática ($d$).
   • Contagem de Neurônios: Escala linearmente com o número de formas de árvores de derivação ($c$) e quadraticamente com o número de regras de produção ($M$).
   • Dimensão Oculta: Escala com $c \cdot d$.
3. Suporte Teórico para Representação Linear: A construção demonstra que a arquitetura possui a capacidade estrutural de codificar estados gramaticais abstratos em subespaços de baixa dimensão e linearmente separáveis dentro do fluxo residual. Especificamente, para uma forma de árvore de derivação fixa, os cálculos de parsing ocorrem em subespaços distintos, permitindo que símbolos não-terminais sejam isolados via transformações afins simples.
4. Diferenciação de Trabalhos Anteriores: Diferente de limites anteriores que escalam com o comprimento máximo da sentença (que pode ser exponencial na profundidade da gramática), esta construção escala com a própria profundidade da gramática. Isso destaca a eficiência da modelagem hierárquica sobre representações planas (como n-gramas ou autômatos de estados finitos, que exigiriam espaços de estados exponenciais para CFGs profundas).

Resultados

O principal resultado teórico (Teorema 4.1) estabelece que, para qualquer $\epsilon > 0$, existe um modelo de linguagem transformer $f_T$ que modela preditivamente a linguagem $L(G)$ com erro no máximo $\epsilon$. O modelo consiste em $d$ blocos de transformer seguidos por $5d + 7$ camadas feedforward.

• Eficiência: O número de camadas necessárias é linear na profundidade da gramática, uma melhoria significativa em relação às construções onde a contagem de camadas escala com o comprimento da sentença.
• Esparsidade: A construção utiliza um circuito esparso onde cada sequência de entrada é processada por uma única cabeça de atenção por bloco, alinhando-se com achados empíricos sobre subgrafos computacionais esparsos em deep learning.
• Separabilidade Linear: A prova mostra que os símbolos não-terminais em uma determinada profundidade são mapeados para vetores em um subespaço do fluxo residual correspondente, apoiando a hipótese da representação linear. No entanto, os autores observam que sua construção utiliza uma base estritamente ortogonal (neurônios indicadores distintos), enquanto modelos empíricos provavelmente alcançam isso via superposição densa.

Significância e Limitações

Significância:
O artigo oferece uma prova de existência rigorosa de que transformers profundos podem representar explicitamente estruturas gramaticais hierárquicas. Ele preenche a lacuna entre observações empíricas de representações lineares e capacidades arquiteturais teóricas. Ao formalizar como os transformers podem implementar programação dinâmica bottom-up, o trabalho fornece uma base teórica para o porquê de arquiteturas mais profundas serem eficazes na captura de estruturas linguísticas complexas sem sofrer da "maldição da dimensionalidade" associada a modelos planos.

Limitações:

• Estrutura Simplificada: A análise é restrita a CFGs de profundidade limitada e não recursivas. Não aborda diretamente gramáticas recursivas ou linguagens infinitas, embora a estrutura seja notada como uma abstração para analisar a composicionalidade hierárquica.
• Ortogonalidade vs. Superposição: A construção teórica depende de um espaço de base ortogonal onde cada estado gramatical possui um neurônio dedicado. Isso simplifica a prova, mas não contabiliza o fenômeno da "superposição" observado em modelos reais, onde características são comprimidas em vetores densos. Compreender como a dinâmica de treinamento padrão gera tais representações comprimidas permanece uma questão em aberto.
• Escalabilidade para Corpos Reais: Os limites dependem de $c$ (o número de formas de árvore), que pode ser grande. Embora o framework formalize a mecânica central, os autores reconhecem que ele ainda não produz limites estreitos para corpos de texto complexos do mundo real, como o Penn Treebank.

Em conclusão, este trabalho estabelece as bases para compreender o funcionamento interno dos modelos transformer através da teoria da linguagem formal, sugerindo que a profundidade do transformer espelha naturalmente a profundidade da hierarquia gramatical que ele modela.