Resumo Técnico: Processamento Sintático Neuro-simbólico: Moldando uma Rede Neural com o Algoritmo CYK

Declaração do Problema

O artigo aborda uma limitação fundamental nas atuais Grandes Modelos de Linguagem (LLMs) e arquiteturas baseadas em transformers: sua incapacidade de aprender e extrapolar de forma confiável conhecimentos algorítmicos complexos a partir de dados de treinamento. Embora os transformers exibam "grokking" (generalização além do overfitting) em tarefas simples, eles têm dificuldade com a generalização algorítmica exigente, como aprender um algoritmo de processamento complexo como o Cocke-Younger-Kasami (CYK) do zero. Os autores argumentam que esperar que os transformers descubram algoritmos conhecidos puramente através de dados é uma expectativa exagerada, pois esses modelos frequentemente funcionam meramente como "grandes memórias de linguagem" em vez de motores algorítmicos. O problema central é se algoritmos conhecidos podem ser diretamente codificados em arquiteturas de redes neurais governadas por multiplicações matriz-vetor, em vez de depender da emergência passiva de capacidades através de escala massiva e treinamento.

Metodologia

Os autores propõem o CYKNN, uma arquitetura de rede neural recorrente simples projetada para injetar diretamente o algoritmo CYK em uma estrutura de rede neural. A metodologia baseia-se em três componentes principais:

1. Representações Reduzidas Holográficas (HRRs): Para codificar a tabela de processamento CYK bidimensional e as regras gramaticais simbólicas, os autores utilizam HRRs. Neste framework, os símbolos são representados como matrizes derivadas de vetores aleatórios. Uma propriedade específica dessas representações é que um símbolo e seu inverso (ex: $[a]^\oplus$ e $[a]^\ominus$) se cancelam na multiplicação de matrizes, aproximando uma matriz identidade. Isso permite operações "holísticas" onde sequências de símbolos podem ser manipuladas algebricamente, de forma semelhante a peças de um jogo de Tetris.

2. Injeção Algorítmica via Operações Matriciais:

   • Representação: As células da tabela CYK $P[i, j]$ são representadas como matrizes distribuídas. As regras gramaticais (ex: $A \to BC$) são codificadas como matrizes de peso ($W$) construídas a partir das representações inversas e diretas dos não-terminais.
   • Atualização Holística: Em vez de iterar através de loops para preencher a célula da tabela célula por célula (como no algoritmo clássico $O(n^3)$ do CYK), os autores formulam o passo de atualização como uma única multiplicação matriz-vetor: $P' = PRP$. Aqui, $P$ é o estado atual da tabela e $R$ codifica as regras gramaticais. Esta operação teoricamente realiza a lógica de combinar constituintes em paralelo.
   • Refinamento: Para mitigar os erros de aproximação introduzidos pelo colapso da complexidade $O(n^3)$ em uma única operação, a arquitetura inclui um Decodificador Diagonal (Dd). Este módulo extrai informações diagonais específicas da matriz distribuída, purifica o sinal e o alimenta de volta no loop recorrente para refinamento.

3. Arquitetura (CYKNN): A rede consiste em:

   • Codificador Holográfico (He): Transforma tokens de entrada na matriz inicial $P_0$.
   • Módulo Unário (U): Aplica regras gramaticais unárias para inicializar a primeira diagonal.
   • Módulo Binário (B): Implementa a operação central $P_{i+1} = P_i R_B P_i$ para propagar aplicações de regras binárias.
   • Decodificador Diagonal (Dd): Extrai e refina o conteúdo simbólico da matriz distribuída em cada etapa.

Contribuições Principais

• Injeção Direta de Algoritmo: O artigo demonstra uma abordagem inovadora de metodologias neuro-simbólicas onde um algoritmo complexo e bem conhecido (CYK) é explicitamente moldado na arquitetura de uma rede neural, em vez de ser aprendido implicitamente.
• Raciocínio Holístico via Álgebra Linear: Os autores mostram que a lógica iterativa de programação dinâmica (preenchimento de uma tabela de processamento) pode ser traduzida em multiplicações matriz-vetor holísticas que alteram o status dos dados em uma única operação, aproveitando as propriedades das HRRs.
• Desempenho Superior em Tarefas Algorítmicas: O proposto CYKNN supera os LLMs de estado da arte existentes na tarefa específica de processamento CYK, mesmo quando esses LLMs possuem parâmetros significativamente maiores (20B+).

Resultados Experimentais

Os autores avaliaram o CYKNN contra duas classes de modelos baseados em transformer:

1. Modelos com Fine-tuning: Qwen2.5-1.5B e Qwen3-8B, submetidos a fine-tuning com LoRA na tarefa de CYK.
2. Modelos de Aprendizado em Contexto (ICL): gpt-oss-20B e Gemma-27B, utilizando prompts com exemplos de poucos disparos (few-shot).

Descobertas:

• Dominância do CYKNN: O CYKNN, particularmente quando inicializado com as regras gramaticais corretas, alcançou pontuações de F-measure significativamente superiores a todos os LLMs comparados, tanto em conjuntos pequenos (comprimento 5-8) quanto nos conjuntos de teste completos.
• Limitações dos LLMs: Os modelos Qwen com fine-tuning tiveram um desempenho ruim, frequentemente falhando em aprender a estrutura algorítmica e, em vez disso, memorizando associações de prefixos. Eles apenas superaram um CYKNN com inicialização aleatória em sequências muito longas (>12 tokens), sugerindo que não estavam induzindo o algoritmo. Os modelos de aprendizado em contexto mostraram alta precisão, mas baixa revocação (recall), indicando uma abordagem conservadora e não algorítmica para preencher a tabela.
• Sensibilidade à Inicialização: O desempenho do CYKNN foi fortemente dependente da inicialização das matrizes gramaticais. A inicialização aleatória levou a um desempenho inferior, enquanto a inicialização com as regras gramaticais específicas permitiu que o modelo convergisse para uma alta acurácia.
• Generalização: Ao contrário dos transformers, que tiveram dificuldades com variações no comprimento da sequência, o CYKNN demonstrou um comportamento mais intuitivo em relação ao comprimento da sequência, mantendo o desempenho mesmo com gramáticas mais complexas.

Significância e Alegações

O artigo afirma pavimentar o caminho para uma abordagem diferente de metodologias neuro-simbólicas. Os autores argumentam que, se os algoritmos são conhecidos, existe uma alternativa viável a depender das "capacidades emergentes" de transformers massivos: codificar diretamente esses algoritmos nas arquiteturas neurais.

A significância reside na demonstração de que:

1. Algoritmos podem moldar arquiteturas: Redes neurais podem ser projetadas para incorporar uma lógica algorítmica específica (CYK) através de operações matriz-vetor, em vez de apenas aprender padrões estatísticos.
2. Eficiência em Tarefas Neuro-Simbólicas: Para tarefas que exigem adesão algorítmica estrita (como processamento sintático), uma rede especializada e moldada algoritmicamente pode superar LLMs de propósito geral e escala massiva, mesmo aqueles com bilhões de parâmetros.
3. Alternativa ao "Grokking": O artigo sugere que, para tarefas algorítmicas complexas, esperar que os transformers "grok" a solução a partir dos dados é ineficiente e muitas vezes malsucedido; a injeção explícita de estrutura algorítmica é um caminho mais robusto.

Os autores permanecem modestos, reconhecendo que a gramática utilizada é simples e que a implementação atual não é computacionalmente otimizada, mas afirmam que a simplicidade da gramática já foi suficiente para expor as limitações dos atuais LLMs baseados em transformer.