Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

1. Declaração do Problema

Embora o prompting de Cadeia de Pensamento (CoT) tenha melhorado empiricamente o desempenho dos Transformers e teoricamente demonstrado aumentar sua expressividade até a Completude de Turing, uma lacuna crítica permanece: Os Transformers podem aprender a generalizar o raciocínio CoT para comprimentos maiores do que aqueles vistos durante o treinamento?

Evidências empíricas existentes sugerem que a precisão dos Transformers degrada-se abruptamente à medida que o comprimento da trilha de CoT aumenta, mesmo em tarefas algorítmicas e lógicas. O artigo investiga se a afirmação teórica de completude de Turing se mantém sob o requisito mais estrito de aprendizabilidade generalizável em comprimento. Especificamente, ele pergunta:

• Os formatos padrão de CoT permitem que os Transformers resolvam problemas além da classe de complexidade $\text{TC}^0$ (circuitos de limiar de profundidade constante) ao generalizar para sequências mais longas?
• Quais barreiras estruturais específicas impedem essa generalização?
• Essas barreiras podem ser superadas por meio de estratégias específicas de formatação?

2. Metodologia

Os autores empregam uma combinação de formalismo teórico e validação empírica:

Framework Teórico

O estudo utiliza frameworks teóricos recentes para generalização de comprimento em Transformers:

• C-RASP: Um formalismo para raciocinar sobre Transformers com alfabetos finitos e codificações posicionais. A pertença implica garantias de generalização de comprimento.
• C-RASP:* Uma extensão do C-RASP que permite um alfabeto infinito (especificamente, tokens de sinalização ilimitados) e predicados de correspondência local.
• Modelo de Aprendizado: Os autores adotam um modelo de aprendizado idealizado onde uma sequência de Transformers treinada em comprimentos de entrada crescentes converge para um único algoritmo subjacente. A generalização é garantida se a tarefa puder ser expressa dentro desses formalismos.

Configuração Empírica

• Tarefas: Três tarefas de raciocínio algorítmico foram selecionadas:
  1. Paridade: Determinar se o número de 1s em uma string binária é par ou ímpar.
  2. Avaliação Booleana: Avaliar o valor de verdade de fórmulas lógicas aninhadas.
  3. Permutação S5: Rastrear o estado de 5 objetos após uma série de operações de troca.
• Modelos:
  • Do Zero: Modelos GPT-2 (25M parâmetros) treinados em trilhas de CoT com e sem formatação específica.
  • LLMs Pré-treinados: Experimentos de prompting zero-shot e few-shot em Qwen2.5-7B, Mistral-Small-24B e Llama-3.3-70B.
• Variantes de Formatação:
  • CoT Ingênua: Raciocínio sequencial padrão.
  • Tokens de Sinalização: Atribuição de identificadores únicos (por exemplo, <34>) a posições ou operações específicas para permitir endereçamento arbitrário.
  • Codificação de Mudança de Valor: Em vez de registrar o estado completo a cada passo, o modelo registra apenas mudanças nos valores (por exemplo, 1 -> 0) ou registra explicitamente quando um valor permanece inalterado.

3. Principais Contribuições e Resultados Teóricos

Contribuição 1: O Limite dos Alfabetos Finitos (O Resultado Negativo)

Os autores provam que, sob codificações posicionais padrão e um alfabeto finito, Transformers com CoT não podem generalizar em comprimento para resolver problemas fora de $\text{TC}^0$.

• Teorema 3.4: Se uma linguagem $L$ tem uma trilha de CoT expressível em C-RASP (com primitivas posicionais), então $L$ é definível em $\text{TC}^0$.
• Implicação: Embora o CoT teoricamente permita completude de Turing, a aprendizabilidade de tais simulações é limitada por $\text{TC}^0$ se o vocabulário for fixo. Os benefícios de expressividade não se traduzem em aprendizagem generalizável em comprimento.

Contribuição 2: Superando Barreiras com Alfabetos Infinitos (O Resultado Positivo)

O artigo identifica duas barreiras centrais à generalização de comprimento:

1. Cópia Repetida: A dificuldade de copiar strings arbitrárias para novas posições.
2. Recuperação da Última Ocorrência: A dificuldade de recuperar o valor mais recente de uma variável quando múltiplas atualizações ocorrem (recuperação não única).

Para superar essas barreiras, os autores propõem uma construção usando C-RASP*:

• Tokens de Sinalização: Atribuir um token único e ilimitado (de um alfabeto infinito) a cada posição da fita ou etapa de operação. Isso resolve a barreira de cópia permitindo indexação arbitrária sem memorizar identidades absolutas.
• Codificação de Mudança de Valor: Em vez de registrar o estado completo, o CoT registra apenas transições (por exemplo, "valor mudou de $x$ para $y$"). O estado atual é recuperado contando as mudanças líquidas em relação ao estado inicial. Isso resolve a barreira de recuperação tornando o valor atual uma função de contagens em vez de uma busca pela última ocorrência.
• Teorema 3.8: Transformers com CoT podem generalizar em comprimento para simular qualquer Máquina de Turing se utilizarem um alfabeto infinito de tokens de sinalização e codificarem computações por meio de mudanças de valor. O comprimento da trilha de CoT permanece linear no tempo de execução simulado.

4. Resultados Empíricos

Treinamento do Zero

• Paridade: O CoT padrão falhou em generalizar além dos comprimentos de treinamento. A codificação de mudança de valor permitiu uma generalização robusta para $2\times$ o comprimento de treinamento.
• Avaliação Booleana e Permutação S5: Essas tarefas mais difíceis (fora de $\text{TC}^0$) falharam com CoT ingênua. Adicionar tokens de sinalização melhorou significativamente a generalização de comprimento, embora a S5 permanecesse desafiadora devido a possíveis "atalhos" (heurísticas) que o modelo poderia explorar.
• Permutação Binária: Uma variante da S5 com alta repetição. CoTs ingênuas e apenas com Sinalização falharam devido a erros de "recuperação não única". A combinação de Sinalização + Mudança de Valor produziu os melhores resultados, confirmando a necessidade teórica de ambos os mecanismos.

Prompting de LLMs Pré-treinados

• Sinalização: Usar números naturais como dicas de sinalização em prompts few-shot melhorou o desempenho nas tarefas Booleanas e S5 para todos os LLMs testados (de 7B a 70B), especialmente em comprimentos de sequência mais longos.
• Mudança de Valor: Em uma tarefa de execução de código (rastreamento de atribuições de variáveis), fornecer comentários inline que registravam explicitamente mudanças de valor (por exemplo, # nó a: 9 -> 0) melhorou significativamente a precisão da resposta final em comparação com a formatação padrão de código, mesmo sem etapas de raciocínio intermediárias.

5. Significado e Conclusão

• Redefinindo o Sucesso do CoT: O artigo argumenta que o sucesso do CoT não é inerente ao próprio processo de "pensamento", mas depende fortemente da formatação da trilha. Formatos padrão de CoT frequentemente falham em generalizar porque violam as restrições necessárias para a aprendizagemabilidade (localidade e invariância de tradução).
• Limites Teóricos: Ele esclarece que a completude de Turing para Transformers é condicional. Ela vale para expressividade (codificar manualmente uma solução), mas não para aprendizabilidade (treinar um modelo para generalizar), a menos que ajudas estruturais específicas (alfabetos infinitos/sinalização) sejam fornecidas.
• Diretrizes Práticas: As descobertas oferecem princípios acionáveis para melhorar o desempenho de LLMs em tarefas de raciocínio difíceis:
  1. Use Dicas de Índice: Marque explicitamente posições ou etapas com identificadores únicos para auxiliar na recuperação.
  2. Registre Mudanças, Não Estados: Formate trilhas de raciocínio para destacar transições de estado em vez de despejos completos de estado para evitar ambiguidade na recuperação.
• Direções Futuras: O trabalho sugere que futuros dados de pré-treinamento e esquemas de CoT devem ser projetados com essas restrições teóricas em mente para desbloquear o potencial computacional completo dos Transformers em tarefas de raciocínio de longo horizonte.

Em resumo, o artigo demonstra que, embora os Transformers sejam teoricamente capazes de raciocínio universal, realizar essa capacidade de maneira generalizável em comprimento exige superar barreiras arquitetônicas e de formatação específicas por meio do uso de tokens de sinalização e codificações de mudança de valor.