Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Resumo Técnico: Raciocínio Recorrente em Quebra-cabeças Simbólicos com Modelos de Sequência

Declaração do Problema
Grandes modelos de linguagem (LLMs) frequentemente demonstram uma proficiência aparente em tarefas simbólicas e algorítmicas, mas esse desempenho frequentemente mascara um comportamento frágil quando os problemas aumentam em comprimento, dificuldade ou se desviam ligeiramente da distribuição de treinamento. Os benchmarks atuais de raciocínio frequentemente priorizam a produção de uma resposta final válida em detrimento da robustez, minimalidade e estabilidade do processo de solução. Este artigo argumenta que, para problemas algorítmicos, a correção requer não apenas um ponto final plausível, mas a capacidade de escolher repetidamente ações válidas, evitar transições ilegais e manter a consistência ao longo de horizontes longos. Os autores postulam que o raciocínio algorítmico serve como um cenário crítico para distinguir a robustez genuína do emparelhamento superficial de padrões (shallow pattern matching).

Metodologia: O Benchmark RecurrReason
Para abordar essas limitações, os autores introduzem o RecurrReason, um benchmark de dificuldade controlada composto por quatro quebra-cabeças de lógica recorrente:

1. Mundo dos Blocos (Block World): Reorganizar blocos em pilhas.
2. Salto de Damas (Checkers Jumping): Trocar as posições de peças vermelhas e azuis em um tabuleiro linear.
3. Torre de Hanói (Tower of Hanoi): Mover discos entre pinos sob restrições de tamanho.
4. Travessia do Rio (River Crossing): Transportar pares de ator-agente através de um rio com restrições de segurança.

O benchmark é construído com as seguintes características:

• Dificuldade Escalável: Cada quebra-cabeça é parametrizado por um único inteiro $N \in \{1, \dots, 10\}$.
• Trajetórias Ótimas: Todas as instâncias são resolvidas usando Busca em Largura (BFS) para gerar trajetórias ótimas, totalizando 10.817 quebra-cabeças únicos e 285.933 movimentos.
• Formulação da Tarefa: A tarefa é formulada como um problema de "prever-o-próximo-passo". Os modelos recebem o estado atual ($s_t$) e o estado objetivo ($g$) e devem prever o próximo estado ($s_{t+1}$). A avaliação envolve rollouts autorregressivos sem estados intermediários de verdade fundamental (ground-truth).
• Protocolo de Avaliação: Os modelos são treinados em instâncias onde $N=1$ a $7$ e avaliados em instâncias fora da distribuição (OOD) ($N=8$ a $10$) e instâncias dentro da distribuição mantidas (held-out) ($N=1$ a $7$). As métricas incluem taxa de sucesso da trajetória, legalidade do movimento e lacuna de otimalidade.

Configuração Experimental
O estudo testa duas famílias de Transformers sob divisões de dados e condições de treinamento consistentes (do zero, zero-shot e ajuste fino/fine-tuned):

1. Estilo T5 (Codificador-Decodificador): Um modelo de 60 milhões de parâmetros (T5-small) onde o codificador computa atenção bidirecional sobre o estado e o objetivo concatenados, tornando o objetivo um sinal de condicionamento de "primeira classe" em cada etapa.
2. Estilo GPT-2 (Apenas Decodificador): Um modelo de 124 milhões de parâmetros (GPT-2) que utiliza uma máscara causal, o que impede que os tokens do estado atual atentem para os tokens do objetivo (que aparecem mais adiante na sequência), criando um gargalo estrutural para o planejamento orientado ao objetivo.

Resultos Principais
Os experimentos revelam que a estrutura do quebra-cabeça é um determinante de aprendizado mais forte do que a escala do modelo ou o pré-treinamento:

• Sucesso no Mundo dos Blocos: O modelo T5 pré-treinado e ajustado alcançou 97,27% de acurácia de validação e 81,00% de acurácia OOD. Esse sucesso é atribuído à sua função de transição local (verificando apenas o topo de uma pilha, complexidade $O(1)$), crescimento linear do comprimento da solução ($L(N) = O(N)$) e sinais de treinamento densos.
• Falha em Outros Quebra-cabeças:
  • Travessia do Rio: Todos os modelos pontuaram 0,00% sob todas as condições. O quebra-cabeça exige verificação de restrição global ($O(N)$) em cada etapa e possui um espaço de ação combinatório, o que derrotou todas as arquiteturas.
  • Torre de Hanói: Os modelos alcançaram no máximo 11,11% de acurácia de validação (apenas em casos triviais de $N=1$) e 0,00% OOD. O comprimento exponencial da solução ($2^N - 1$) causa erros cumulativos que impedem a generalização além de $N=1$.
  • Salto de Damas: Os modelos alcançaram no máximo 1,11% de acurácia de validação, resolvendo apenas instâncias triviais onde o estado inicial é igual ao estado objetivo. O comprimento de solução quadrático e a necessidade de evitar becos sem saída provaram insuperáveis.
• Arquitetura vs. Escala: O modelo T5 menor (60M) superou significativamente o modelo GPT-2 maior (124M). Os autores atribuem isso à capacidade da arquitetura codificador-decodificador de atender bidirecionalmente ao objetivo, enquanto a máscara causal em modelos apenas decodificadores cria um gargalo estrutural que impede o planejamento eficaz, mesmo com maior contagem de parâmetros.
• Transferência de Pré-treinamento: Os benefícios do pré-treinamento foram observados apenas para quebra-cabeças com funções de transição estruturalmente locais (Mundo dos Blocos). Não houve transferência para tarefas que exigem restrições globais (Travessia do Rio) ou decomposição recursiva (Torre de Hanói).

Análise de Modos de Falha
Os autores identificam modos de falha específicos correlacionados com a estrutura do quebra-cabeça:

• Movimentos Inválidos: Dominaram as falhas em quebra-cabeças com restrições globais (Torre de Hanói, Travessia do Rio), indicando uma falha em generalizar restrições.
• Loops (Ciclos): O principal modo de falha para o Mundo dos Blocos em modelos apenas decodificadores, sugerindo aprendizado parcial de regras sem seleção orientada ao objetivo.
• Paradas Prematuras: Observadas no GPT-2 na Torre de Hanói, ligadas à sobre-representação estatística de tokens de parada nos dados de treinamento.

Significância e Alegações
O artigo afirma que os vieses indutivos arquiteturais importam mais do que a escala para o raciocínio algorítmico sistemático. Especificamente:

1. Determinismo Estrutural: A aprendibilidade de um quebra-cabeça é determinada por três propriedades estruturais: localidade da transição, tamanho do espaço de ação e crescimento do comprimento da solução. Os autores formalizam um modelo de erro cumulativo mostrando que a probabilidade de sucesso decai exponencialmente com o comprimento da solução ($P \approx e^{-\epsilon L(N)}$).
2. Condicionamento ao Objetivo: O condicionamento bidirecional ao objetivo (como no T5) é crítico para o planejamento orientado ao objetivo, enquanto a atenção causal (como no GPT-2) cria um gargalo estrutural que impede o planejamento eficaz, mesmo com maiores contagens de parâmetros.
3. Limites do Pré-treinamento: O pré-treinamento confere um viés indutivo hierárquico que se transfere apenas para tarefas com estruturas localmente decomponíveis. Ele não equipa inerentemente os modelos para lidar com restrições globais ou profundidade recursiva.
4. Direção Futura: Os resultados sugerem que o raciocínio de múltiplos passos confiável em LLMs requer ou capacidades de busca arquitetural ou verificação explícita de restrições simbólicas, em vez de meramente escalar o tamanho do modelo.

Os autores concluem que o RecurrReason fornece um ambiente de teste controlado para trabalhos futuros sobre generalização de comprimento, planejamento condicionado ao objetivo e os requisitos arquiteturais para o raciocínio algorítmico sistemático.