Probing Structural Mathematical Reasoning in Language Models with Algebraic Trapdoors

Resumo Técnico: Sondagem do Raciocínio Matemático Estrutural em Modelos de Linguagem com Portas Trapaça Algébricas

Declaração do Problema
Padrões de referência (benchmarks) de raciocínio matemático padrão (por exemplo, GSM8K, MATH, ProofNet) tipicamente exibem uma simetria onde a verificação não é mais difícil que a solução. Essa simetria favorece a fluência computacional, mas falha em avaliar o "raciocínio estrutural"—a capacidade de empregar teoremas nomeados, reconhecer padrões algébricos e identificar priores estruturais aplicáveis. Além disso, a pontuação padrão confunde "comprometer-se com uma resposta errada" com "abster-se honestamente", tratando ambas como falhas com pontuação zero.

Este artigo introduz uma suíte de benchmarks projetada para quebrar essa simetria, aproveitando a assimetria criptográfica do tipo verificador-provador dentro do grupo $SL(3, \mathbb{Z})$. O desafio central é que a resposta de cada problema é computável em forma fechada $O(1)$ pelo construtor (que possui os dados de "porta trapaça" $(N, K)$), mas o solucionador, carecendo desses dados, enfrenta ou a detecção heurística estrutural ou uma questão algorítmica de decidibilidade desconhecida (especificamente, o problema de pertinência em $SL(3, \mathbb{Z})$).

Metodologia
O benchmark consiste em quatro famílias de problemas, todas construídas gerando um subgrupo finitamente gerado $H \subseteq SL(3, \mathbb{Z})$ a partir de um par secreto $(N, K)$ onde $K \subseteq SL(3, \mathbb{Z}/N)$. Os geradores são ofuscados usando embaralhamento de Nielsen (reescrita de geradores como produtos profundamente aninhados) e cisalhamentos de Mennicke, resultando em entradas de matriz atingindo $10^{40}$.

1. Família I (Pertinência): Dados geradores e matrizes candidatas, decidir a pertinência. Certificados existem para "SIM" (palavras explícitas) ou "NÃO" (redução mod-$p$), mas o problema geral de pertinência em $SL(3, \mathbb{Z})$ é indecidível.
2. Família II (Lista-prima SIM/NÃO): Determinar se o subgrupo gerado por $(A, B)$ sobrecarrega (surjeta) para $SL(3, \mathbb{F}_p)$ para uma lista de grandes primos. A resposta depende da detecção de uma estrutura ortogonal (Forma Normal de Smith) que é $O(1)$ para o construtor, mas requer detecção estrutural para o solucionador.
3. Família III (Extensão de Congruência SIM/NÃO): Determinar se $H$ é uma extensão de congruência $\pi^{-1}(K)$. Os "primos ruins" são fatores de $N$ onde $K$ é próprio.
4. Família IV (Índice): Output do índice exato $[SL(3, \mathbb{Z}) : H]$, ou "infinito/desconhecido". Esta família inclui três subfamílias:
   • v1: $H = SL(3, \mathbb{Z})$ (Índice 1), indistinguível de um subgrupo genérico de índice infinito via análise mod-$p$.
   • v2: $H = \pi^{-1}(K)$ (Índice finito). O cokernel é computável, mas a contenção do núcleo requer resolver o problema de pertinência.
   • v3: $H = \langle g_1, g_2 \rangle \subset \Gamma(N)$ (Índice infinito pela Propriedade (T)). O raciocínio baseado apenas no cokernel produz uma resposta finita errada; o raciocínio correto requer reconhecer a natureza infinita.

Configuração de Avaliação
Os autores avaliaram dois modelos de última geração: GPT Pro (pensando) e Gemini. Crucialmente, os prompts não afirmam que o subgrupo é de índice finito. Este design força o modelo a distinguir entre calcular um cokernel (fácil) e verificar a contenção do núcleo (difícil/desconhecido), criando um "teste de calibração".

Os autores propõem uma classificação de pontuação de quatro vias:

1. Comprometer-correto: Resposta específica correta.
2. Comprometer-errado: Resposta específica incorreta.
3. Abster-se-correto: Output "infinito/desconhecido" quando a verdade fundamental é infinita/desconhecida (v3).
4. Abster-se-errado: Output "infinito/desconhecido" quando a verdade fundamental é um inteiro específico (v1, v2).

Resultados Chave
O artigo relata cinco rastros de raciocínio detalhados:

• Raciocínio Estrutural (Famílias II e III): Ambos os modelos resolveram com sucesso instâncias que exigiam detecção estrutural (por exemplo, identificar o teorema de McLaughlin, o teorema de Burnside ou apresentações de Coxeter).
  • Gemini baseou-se em correspondência de teoremas nomeados, produzindo respostas curtas e declarativas (por exemplo, reconhecer uma apresentação de Coxeter para $S_4$) em segundos.
  • GPT baseou-se em derivação construtiva, derivando identidades de comutadores e fatorando matrizes a partir de primeiros princípios, levando de minutos a horas.
• O Teste de Calibração (Família IV-v2, Instância X10):
  • GPT gastou 152 minutos em uma instância onde a verdade fundamental era um inteiro de 25 dígitos. Ele calculou com sucesso o cokernel, mas reconheceu explicitamente a questão de pertinência do lado do núcleo como o gargalo. Após tentar verificação construtiva (que falhou em certificar todos os cisalhamentos necessários), ele absteve-se com "NÃO SEI" em vez de comprometer-se com o limite superior computado. Isso demonstra metacognição calibrada na fronteira da decidibilidade aberta.
  • Gemini falhou em produzir um rastro de raciocínio, surgindo um erro interno após minutos.
• A Linha de Base $SL(2, \mathbb{Z})$ (Família V):
  • Quando testado na linha de base decidível $SL(2, \mathbb{Z})$, GPT empregou com sucesso o conjunto completo de ferramentas de posto 1 (frações contínuas, dobramento de Stallings, Reidemeister–Schreier, redução de Nielsen) para distinguir índice finito versus infinito.
  • Gemini travou após tempo de computação estendido na mesma linha de base, falhando em produzir uma saída.

Significância e Alegações
O artigo argumenta que este benchmark expõe uma classificação de quatro vias do comportamento do modelo que a pontuação padrão baseada em chave de resposta obscurece. Suas contribuições primárias são:

1. Evidência de Abstenção Calibrada: O rastro de 152 minutos do GPT fornece a evidência mais forte existente de que modelos de fronteira possuem uma "camada metacognitiva" ativa capaz de reconhecer quando uma prova está incompleta e recusar-se a comprometer-se, mesmo quando um cálculo parcial (cokernel) está disponível.
2. Assimetria Arquitetural: Os resultados sugerem uma diferença fundamental na arquitetura de raciocínio. Os autores propõem um modelo de três camadas para o GPT (Teorema Nomeado $\to$ Primeiros Princípios $\to$ Abstenção Calibrada) versus um modelo de camada única para o Gemini (Apenas Teorema Nomeado), onde a ausência de um mecanismo de fallback leva a loops infinitos ou travamentos quando a heurística primária falha.
3. Valor Diagnóstico do Design de Prompt: O artigo demonstra que omitir a promessa de "índice finito" no prompt é uma escolha de design crítica. Sem ela, a assimetria núcleo/cokernel força o modelo a confrontar a fronteira da decidibilidade, tornando a "abstenção" um comportamento mensurável e significativo em vez de uma falha.
4. Além da Fluência Computacional: O benchmark distingue entre modelos que podem realizar aritmética de inteiros grandes e aqueles que podem empregar priores estruturais (classes de Aschbacher, Propriedade (T), propriedade de subgrupo de congruência) e reconhecer limites algorítmicos.

Os autores concluem que o benchmark separa com sucesso "saber o teorema nomeado" de "ter maquinaria de fallback graciosa", revelando que, embora os modelos atuais possam realizar raciocínio estrutural, sua capacidade de generalizar estratégias algorítmicas (como busca em gráfico de Nielsen) para postos mais altos permanece uma área distinta para investigação.