Resumo Técnico: Descoberta de um Algoritmo do Mapa Zeta em Caminhos de Dyck via Interpretabilidade Mecanística

Declaração do Problema

O aprendizado de máquina é cada vez mais aplicado à pesquisa matemática, mas uma lacuna fundamental permanece entre a previsão de alta precisão e a geração de construções matemáticas explícitas e verificáveis. Na combinatória, o resultado desejado é frequentemente uma conjectura, construção ou algoritmo que possa ser independentemente checado, em vez de uma aproximação numérica. Este artigo aborda essa lacuna investigando se ferramentas de interpretabilidade mecanística podem extrair algoritmos combinatórios explícitos de redes neurais treinadas.

O caso de teste específico é o mapa zeta ($\zeta$) em caminhos de Dyck, uma bijeção clássica central na teoria dos números de $q,t$-Catalan. O mapa zeta troca as estatísticas $(dinv, area)$ pelas estatísticas $(area, bounce)$. Embora o mapa zeta seja bem compreendido e admita várias descrições algorítmicas existentes (por exemplo, via sequências de área ou sweep maps), ele serve como um ambiente controlado ideal para descoberta assistida por IA porque os dados são exatamente geráveis, a correção é exaustivamente verificável e o alvo é um procedimento combinatório discreto.

Metodologia

1. Configuração Experimental

Os autores treinaram modelos transformer para aprender o mapa zeta em caminhos de Dyck de semicomprimento $n$.

• Dados: Conjuntos de dados supervisionados de palavras de Dyck e suas imagens sob o mapa zeta (especificamente $\text{rev} \circ \zeta$, onde $\text{rev}$ denota a leitura da palavra de trás para frente e a inversão de 0s e 1s, consistente com a implementação em SAGEMATH utilizada).
• Treinamento Inicial: Transformers codificador-decodificador padrão (4 camadas, 8 cabeças) alcançaram $>99\%$ de precisão em vários semcomprimentos ($n=11$ a $16$).
• Compressão: Para permitir a análise mecanística, os autores treinaram um Transformer de Dyck Minimalista: uma arquitetura deliberadamente pequena com uma camada de codificador, uma camada de decodificador e uma cabeça de atenção (dimensão de embedding 128, ~340k parâmetros). Este modelo alcançou precisão perfeita ou quase perfeita.

2. Análise de Interpretabilidade Mecanística

O núcleo da metodologia envolve a análise do funcionamento interno do Transformer de Dyck Minimalista usando três ferramentas principais:

• Análise de Cross-Attention do Decodificador: Os autores rastrearam quais posições de entrada receberam os pesos de atenção mais altos durante a geração da sequência de saída.
• Ablação Causal: Eles mascararam a cross-attention para posições de entrada específicas (por exemplo, passos ascendentes onde $w_i=1$) para testar se essas posições eram funcionalmente necessárias para a decodificação.
• Probing Linear: Classificadores lineares foram treinados nos estados ocultos do codificador para prever o "nível" (level) de cada posição no caminho de Dyck, testando se essa estatística combinatória era linearmente acessível nas representações.

3. Extração do Algoritmo

Com base nos padrões observados no modelo minimalista, os autores formularam um novo algoritmo explícito, o Mapa de Andaime (Scaffolding Map), e subsequentemente provaram sua equivalência ao mapa zeta.

Principais Descobertas e Contribuições

1. Descoberta de um Mecanismo Baseado em Níveis

A análise de interpretabilidade revelou que o modelo não trata o mapa zeta como uma tabela de consulta arbitrária, mas organiza a geração através de um mecanismo estruturado baseado em níveis:

• Seleção de Nível Máximo: O decodificador atende consistentemente às posições de entrada com níveis máximos entre as posições relevantes, particularmente nas etapas iniciais de geração.
• Evitação Sistemática de Passos Ascendentes: O decodificador raramente atende a posições onde $w_i=1$ (passos Norte). A ablação causal confirmou que mascarar a atenção para essas posições causou uma degradação de precisão negligenciável, implicando que o decodificador não "lê" essas posições diretamente, mas depende de informações agregadas.
• Deslocamento Sequencial Triangular: O padrão de atenção exibe um deslocamento de uma posição de passo Leste (East-step) de nível alto ($w_i=0$) para a próxima posição elegível de passo Leste ($i+1$), correspondendo a uma diminuição sequencial de nível ($\ell_{i+1} = \ell_i - 1$).
• Acessibilidade Linear: Probes lineares confirmaram que as representações do codificador tornam a sequência de níveis ($\ell_i$) do caminho de Dyck linearmente acessível (84% de precisão preditiva).

2. O Mapa de Andaime (Scaffolding Map)

Traduzindo esses sinais para a combinatória, os autores propuseram o Mapa de Andaime, um algoritmo de travessia centrado em picos:

• Mecanismo: O algoritmo agrupa posições de pico por seu nível. Ele inicializa "agentes" nesses picos e atravessa o caminho nível por nível, do topo para baixo.
• Travessia: Os agentes movem-se ao longo de posições adjacentes de passo Leste e não-Leste. A palavra de saída é gerada pela leitura dos símbolos encontrados pelos agentes enquanto eles atravessam o "andaime" construído pelos passos ascendentes.
• Estrutura: O algoritmo separa a estrutura de suporte latente (os níveis construídos pelos passos ascendentes) do processo de travessia que gera a saída.

3. Verificação Teórica

Os autores forneceram uma prova formal (Teorema 6.1) estabelecendo que o Mapa de Andaime é equivalente ao mapa zeta (modulo a convenção de reversão usada no conjunto de dados).

• Estratégia de Prova: A prova compara o Mapa de Andaime nível por nível com a descrição da sequência de área de $\text{rev} \circ \zeta$. Ela demonstra que as subsequências geradas pelo mecanismo de fila ($Q'_k$) do Mapa de Andaime correspondem exatamente às subsequências geradas pelo algoritmo padrão do mapa zeta ($P_k$) ao escanear a sequência de área em ordem reversa.

Significância e Alegações

O artigo afirma fornecer um exemplo controlado de descoberta matemática assistida por IA, onde a interpretabilidade mecanística transforma o comportamento do modelo em um algoritmo combinatório preciso e verificável por humanos.

• Novidade: Tanto quanto é do conhecimento dos autores, esta é a primeira instância do uso da interpretação mecanística de um modelo de sequência neural treinado para extrair uma nova descrição bijetiva explícita de um mapa combinatório bem estudado.
• Fluxo de Trabalho: O artigo articula um fluxo de trabalho onde:
  1. O modelo fornece sinais estruturais recorrentes (padrões de atenção, probes lineares).
  2. Investigadores humanos interpretam esses sinais como operações combinatórias.
  3. Intervenções (ablações) testam a relevância causal.
  4. O procedimento resultante torna-se um objeto matemático (o Mapa de Andaime) que pode ser enunciado e provado independentemente da rede neural.
• Limitações: Os autores são modestos quanto ao escopo, observando que:
  • Padrões de atenção sozinhos não são prova; a combinação com ablação e prova formal é essencial.
  • O mecanismo aprendido no transformer parece ser uma versão "difusa" (fuzzy) do algoritmo (evidenciado pelos resultados imperfeitos de probing), sugerindo que modelos maiores ou treinados de forma diferente podem implementar mecanismos mais complexos ou "limpos".
  • O Mapa de Andaime foi extraído de um modelo especificamente simples; modelos maiores podem implementar soluções internas diferentes.

O artigo conclui que, embora os detalhes específicos desta descoberta possam não se transferir diretamente para todos os problemas matemáticos, o conceito de usar a interpretabilidade mecanística para preencher a lacuna entre a previsão de caixa-preta e a construção combinatória explícita é amplamente aplicável dentro da pesquisa em combinatória.