Resumo Técnico: Certificação a partir de Exemplos é Difícil para Circuitos e Transformers sob Superparametrização Mínima

Declaração do Problema

À medida que redes neurais de última geração são cada vez mais implantadas em tarefas de raciocínio e algorítmicas, garantir sua correção exata torna-se crítica. Alta precisão no caso médio frequentemente mascara comportamentos inconsistentes, dificultando a detecção de falhas que se desviam da lógica de raciocínio pretendida. Este artigo aborda o problema da certificação exata: determinar o número mínimo de exemplos rotulados de entrada-saída necessários para identificar unicamente uma hipótese-alvo $f^*$ dentro de uma classe de hipóteses $\mathcal{H}$, de modo que nenhuma outra hipótese em $\mathcal{H}$ concorde com $f^*$ em todo o domínio.

A questão central é quão sensível essa complexidade de certificação é ao tamanho da classe de hipóteses circundante. Especificamente, os autores investigam se um aumento mínimo da classe de hipóteses (por exemplo, adicionar uma única porta ou um número constante de parâmetros) pode tornar a certificação exponencialmente mais difícil, mesmo para alvos que anteriormente eram fáceis de certificar.

Metodologia

O artigo emprega um quadro teórico enraizado na complexidade de ensino e na complexidade de circuitos, complementado por validação empírica em tarefas de adição binária.

Quadro Teórico

1. Definição de Tamanho do Certificado: Os autores definem o tamanho do certificado, $\text{cert}(f^*, \mathcal{H})$, como o tamanho mínimo de uma amostra rotulada $S$ tal que o espaço de versões $V_S^{\mathcal{H}}$ (o conjunto de hipóteses em $\mathcal{H}$ consistentes com $S$) contenha apenas $f^*$.
2. Princípio de Desacordo Disjunto: A estratégia central de prova baseia-se na construção de um conjunto de hipóteses "enganadoras". Para um alvo $f^*$, os autores constroem uma família de hipóteses $\{g_\pi\}$ que concordam com $f^*$ em todos os lugares, exceto em "blocos de gatilho" $B_\pi$ específicos e disjuntos dois a dois.
   • Se uma classe de hipóteses contiver tal família de enganadores onde os conjuntos de desacordo são disjuntos, qualquer certificado exato deve conter pelo menos um exemplo de cada conjunto de desacordo.
   • Consequentemente, o tamanho do certificado é limitado inferiormente pelo número desses blocos disjuntos.
3. Análise de Superparametrização: Os autores analisam como adicionar capacidade mínima (por exemplo, uma porta extra em circuitos, um cabeçalho de atenção extra e largura de incorporação constante em Transformers) permite a construção dessas famílias exponenciais de enganadores para todo alvo na classe original, menor.

Análise Empírica

Os autores complementam a teoria com dois experimentos em reconhecimento de adição binária:

1. Circuitos Construídos: Eles instanciam a construção teórica de enganadores para circuitos de limiar ($TC_0$) que reconhecem adição. Eles geram um conjunto de $2^n$ circuitos incorretos, cada um diferindo do alvo em um bloco distinto de entradas, e medem quantos sobrevivem à amostragem uniforme de candidatos a certificado.
2. Transformers Treinados: Eles treinam Transformers apenas com codificador em adição de 10 bits. Após selecionar modelos que passam em verificações de validação rigorosas (99,9% de precisão), eles os avaliam em um grande conjunto de teste mantido de fora. Eles analisam a "sobrevivência" desses modelos imperfeitos (enganadores) quando submetidos a candidatos a certificado amostrados uniformemente, testando se erros residuais podem ser detectados com amostras de tamanho polinomial.

Principais Contribuições e Resultados

1. Dificuldade Exponencial a partir de Superparametrização Mínima

A principal contribuição teórica é demonstrar que a certificação é altamente sensível ao tamanho da classe de hipóteses.

• Circuitos de Limiar ($TC_0$): Para circuitos de profundidade $d \ge 2$, adicionar uma única porta de limiar extra (aumentando o orçamento de portas de $s$ para $s+1$) força o tamanho do certificado para todo alvo na classe original $TC_{d,s}$ a tornar-se exponencial na dimensão de entrada $n$. Especificamente, $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$.
• Transformers: Para Transformers de precisão logarítmica com atenção dura de média (AHAT), adicionar um cabeçalho de atenção na camada final e seis coordenadas auxiliares de incorporação/resíduo cria uma classe ampliada onde a certificação torna-se exponencialmente difícil. Mesmo que um alvo $f^*$ tenha um tamanho de certificado polinomial na arquitetura menor, ele requer um número exponencial de exemplos para ser certificado contra a arquitetura ligeiramente maior.
• Não-Vacuidade: Os autores provam que esses limites inferiores não são vazios. Eles mostram que as classes menores ($TC_{d,s}$ e Transformers padrão) contêm alvos com tamanhos de certificado polinomiais (especificamente $O(\log |\mathcal{H}|)$), yet esses mesmos alvos tornam-se exponencialmente difíceis de certificar assim que a classe é minimamente ampliada.

2. Dificuldade de Certificação Aproximada

O artigo estende esses resultados para certificação aproximada:

• Tolerância a Erro Absoluto: Se a certificação permitir apenas um número polinomial de erros ($R = \text{poly}(n)$), o tamanho do certificado permanece exponencial ($2^{\Omega(n)}$).
• Tolerância a Erro Relativo: Se a certificação permitir um erro relativo constante ($\epsilon$), o tamanho do certificado pode ser pequeno (polinomial em $1/\epsilon$). No entanto, isso vem ao custo de permitir um número exponencial de erros absolutos. Os autores mostram que garantias de erro relativo constante podem esconder um número exponencial de erros, enquanto garantias de erro absoluto polinomial ainda exigem certificados exponenciais.

3. Validação Empírica

• Experimentos com Circuitos: Os enganadores $TC_0$ construídos confirmaram a barreira teórica. Mesmo com candidatos a certificado de tamanho polinomial, quase todos os enganadores construídos permaneceram consistentes com os rótulos amostrados, exigindo amostragem exponencial para eliminá-los.
• Experimentos com Transformers: Entre 150 modelos treinados que passaram em validação extensa, 63 tinham erros residuais no conjunto de teste mantido de fora. A análise mostrou que, mesmo com um subconjunto direcionado de exemplos ricos em erros, candidatos a certificado amostrados uniformemente de tamanho polinomial falharam em eliminar todas as hipóteses não exatas. Modelos imperfeitos podiam evadir a detecção por grandes candidatos amostrados uniformemente.

Significado e Alegações

O artigo alega fornecer uma forma quantitativa de dificuldade de certificação para aprendizado exato. Seu significado reside nas seguintes afirmações:

1. Sensibilidade à Capacidade do Modelo: A certificação não é meramente uma propriedade da função alvo, mas depende criticamente da classe de hipóteses "ambiental". Um aumento mínimo na capacidade do modelo (sobrecarga constante) pode alterar fundamentalmente a dificuldade de verificar a correção de um modelo.
2. Limitações da Certificação Passiva: Em configurações passivas (onde exemplos são amostrados sem consultar o modelo), conjuntos de dados de tamanho polinomial são insuficientes para certificar que um modelo aprendeu o cálculo pretendido se a classe de hipóteses estiver ligeiramente superparametrizada.
3. Distinção de Aprendibilidade: Os resultados destacam uma lacuna entre aprendibilidade e certificação. Embora uma função possa ser aprendível (ou ter um certificado pequeno em uma classe restrita), certificá-la contra uma classe ligeiramente maior pode ser intratável.
4. Implicações para Modelos de Raciocínio: Para modelos implantados em tarefas algorítmicas (como adição), alta precisão de validação não garante exatidão. O artigo sugere que, sem protocolos mais fortes (por exemplo, aprendizado ativo ou consultas específicas), grandes conjuntos de dados amostrados uniformemente podem falhar em detectar inconsistências sutis e estruturadas em modelos de raciocínio.

Os autores concluem que, embora a certificação exata seja um desafio fundamental, a barreira não é apenas uma anomalia de pior caso, mas uma consequência estrutural da superparametrização mínima em classes relevantes para tarefas modernas de raciocínio. Eles sugerem que trabalhos futuros devem explorar protocolos de certificação ativa para potencialmente superar essas barreiras passivas.