Resumo Técnico: Aprendendo a Raciocinar com Currículo II: Generalização Composicional

1. Definição do Problema

O artigo investiga os fundamentos teóricos da generalização composicional — a capacidade de resolver problemas complexos combinando soluções para subproblemas mais simples — um mecanismo central para o raciocínio de cadeia de pensamento (chain-of-thought ou CoT) em inteligência artificial. A questão central abordada é: Quando e por que decompor um problema em partes produz um aprendizado mais eficiente do que resolvê-lo diretamente?

Para responder a isso, os autores formalizam o problema usando simulação de semiautomatos. Um semiautomato é definido por uma função de transição desconhecida, Markoviana e estacionária $\pi^*: S \times \Sigma \to S$. Dado um estado inicial $s_0$ e uma palavra de entrada $w_{1:T}$, o objetivo é prever o estado terminal $s_T$ após $T$ passos. Os estados intermediários $s_{1:T}$ constituem uma cadeia de pensamento. Este modelo captura rastreamento de estado, reconhecimento de linguagem regular e aritmética modular.

O artigo estuda dois cenários de aprendizado específicos:

1. Supervisão de Cadeia de Pensamento Interativa (iSFT): O aprendiz tem acesso a um oráculo que pode retornar o estado em qualquer passo $t$ de um computação pelo custo de uma unidade. O objetivo é minimizar o número de consultas ao oráculo (complexidade de consulta) e as instâncias de treinamento (complexidade de amostra) necessárias para aprender um modelo com baixo erro.
2. Aprendizado por Reforço com Recompensas Verificáveis (RLVR): O aprendiz tem acesso a um modelo de referência "fraco" pré-treinado $\pi_{ref}$ que pode resolver instâncias curtas de comprimento $B \ll T$ com probabilidade constante, e um verificador de resultados que checa a correção de um palpite de estado terminal. O objetivo é melhorar o modelo de referência para resolver instâncias de comprimento $T$ de forma eficiente, superando a queda exponencial na probabilidade de sucesso que ocorre ao executar um modelo fraco sobre horizontos longos.

2. Metodologia

Os autores propõem abordagens baseadas em autocurrículo que decompõem recursivamente sequências longas em subproblemas mais curtos, aprendem a resolvê-los e compõem as soluções. Esta abordagem baseia-se na Parte I da série, utilizando um modelo de composição e boosting.

Componentes Algorítmicos Principais

• Composição: Um modelo treinado para resolver instâncias de comprimento $\tau$ pode ser composto $L$ vezes (onde $T = L\tau$) para resolver instâncias de comprimento $T$. No entanto, erros se acumulam sob composição; portanto, os modelos de curto alcance devem ser treinados com alta precisão.
• Boosting: Para alcançar a precisão necessária em subproblemas de curto alcance, os autores empregam uma estratégia de multiscale boosting. Isso envolve o treinamento de um conjunto de aprendizes fracos em distribuições reponderadas que focam em instâncias "difíceis" (onde o conjunto atual falha) e a agregação deles (por exemplo, via voto de pluralidade).
• Currículo Autogerado: Em vez de um cronograma fixo, o aprendiz seleciona adaptativamente em quais subproblemas treinar, baseando-se nas falhas dos modelos treinados em escalas mais finas.

Inovações Técnicas Chave

• Amostragem Invertida: Uma contribuição técnica central é uma nova técnica de amostragem para lidar com o desvio de distribuição inerente ao boosting. A amostragem de rejeição padrão a partir de misturas reponderadas de marginais é ineficiente (exigindo $\Omega(L)$ amostras no pior caso). Os autores introduzem a amostragem invertida, que primeiro aplica a amostragem de rejeição independentemente a todos os $L$ sub-instâncias dentro de uma sequência longa e, em seguida, seleciona uma das instâncias aceitas uniformemente. Isso alcança uma probabilidade de aceitação proporcional ao número de sub-instâncias, reduzindo significativamente a complexidade de amostra enquanto mantém garantias de aproximação suficientes para o algoritmo de aprendizado.
• Recursão Multiescala: O algoritmo (AutoLearn) aplica o modelo de boosting + composição recursivamente. Ele decompõe instâncias de comprimento $T$ em subproblemas de comprimento $\tau$, que são posteriormente decompostos até atingir o comprimento 1 (previsão do próximo token). Isso cria uma hierarquia onde modelos que resolvem problemas mais curtos e fáceis são compostos para resolver problemas mais difíceis.
• Guess-and-Check para RLVR: No cenário RLVR, onde os rótulos de estado intermediário não estão diretamente disponíveis, os autores simulam o oráculo interativo usando o modelo de referência fraco e o verificador. Ao gerar execuções (rollouts) para cada bloco e verificar o estado terminal do bloco, eles podem efetivamente "rotular" estados intermediários para construir o currículo.

3. Contribuições e Resultados Principais

Cenário I: iSFT (Supervisão Interativa)

O artigo apresenta o AutoLearn, um algoritmo que aprende semiautomatos com complexidade de consulta e de amostra subpolinomial na sequência de comprimento $T$.

• Resultado: A complexidade de consulta e de amostra é limitada superiormente por $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.
• Comparação: Isso quebra a barreira $\Omega(T)$ inerente aos métodos de simulação direta.
  • Supervisão de CoT Total: Requer $\Omega(T)$ consultas por instância para rotular cada estado.
  • Feedback de Ponta a Ponta: Requer complexidade de amostra $\Omega(T)$ devido à incapacidade de generalizar a partir de estados terminais sem fundamentação intermediária.
• Mecanismo: Ao selecionar adaptativamente subproblemas e usar amostragem invertida para gerenciar o desvio de distribuição, o AutoLearn alcança uma complexidade que é subpolinomial em $T$, especificamente $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$.

Cenário II: RLVR (Recompensas Verificáveis)

O artigo apresenta o AutoLearn.RL, que melhora um modelo de referência fraco $\pi_{ref}$ da competência ao nível de bloco ($B$) para a competência de comprimento total ($T$).

• Resultado: O algoritmo alcança alta precisão em instâncias de comprimento $T$ com custos governados pela cobertura do modelo de referência no comprimento de bloco mais curto $B$, em vez do comprimento total $T$.
• Expansão de Cobertura: Métodos padrão de RLVR exigem que o modelo de referência tenha cobertura não trivial no comprimento $T$, o que é exponencialmente improvável se ele tiver apenas cobertura no comprimento $B$ (ou seja, $C^{(T)}_{seq} \approx (C^{(B)}_{seq})^{T/B}$). O AutoLearn.RL reduz este requisito para a cobertura no comprimento $B$.
• Complexidade:
  • Complexidade de amostra: $\tilde{\mathcal{O}}(d/\varepsilon)$.
  • Complexidade de consulta: $\tilde{\mathcal{O}}(d/\varepsilon) + \tilde{\mathcal{O}}(\frac{T}{B} \cdot d C^{(B)}_{ans} + d C^{(B)}_{seq})$.
  • Custo computacional: $\tilde{\mathcal{O}}(dT/\varepsilon) + \tilde{\mathcal{O}}(dT C^{(B)}_{ans} + dB C^{(B)}_{seq})$.
• Significância: O custo de "aquecimento" (burn-in) depende da cobertura na escala curta $B$, permitindo que a cobertura efetiva no comprimento $T$ se expanda de exponencialmente pequena para constante através do currículo.

4. Significância e Alegações

O artigo afirma que a composição combinada com um autocurrículo gerado pode alcançar reduções superpolinomiais nos custos de supervisão e computação em comparação com as bases não curriculares.

• Fundamentação Teórica: Fornece um arcabouço teórico rigoroso explicando por que a decomposição de problemas ajuda: ela permite que o aprendiz troque o comprimento da sequência pela exigência de precisão via composição, enquanto o boosting garante a precisão necessária nos subproblemas.
• Eficiência: Os resultados demonstram que para tarefas como simulação de semiautomatos, o aprendizado pode ser alcançado com complexidade $2^{\tilde{\mathcal{O}}(\sqrt{\log T})}$, uma melhoria dramática em relação à complexidade linear $\Omega(T)$ das abordagens padrão.
• Generalização: As descobertas sugerem que autocurrículos, onde o aprendiz projeta seus próprios problemas, não são apenas heurísticas, mas podem ser teoricamente justificados como um mecanismo para superar barreiras estatísticas e computacionais de raciocínio de longo horizonte.
• Limitações e Trabalho Futuro: Os autores reconhecem simplificações, como restringir a classe de modelos a modelos Markovianos (excluindo atenção de histórico completo como Transformers) e assumir transições determinísticas. Eles observam que estender estes resultados para modelos não-Markovianos e transições estocásticas é uma direção importante para trabalhos futuros. Eles também destacam que, embora seus resultados atuais alcancem dependência subpolinomial de $T$, alcançar dependência polilogarítmica permanece uma questão aberta, potencialmente exigindo suposições mais fortes, como limites de erro finitos.

Em resumo, o artigo estabelece que a generalização composicional, quando guiada por um currículo adaptativo e apoiada por técnicas como amostragem invertida, oferece um caminho provadamente eficiente para aprender tarefas sequenciais complexas que são intratáveis para métodos de aprendizado direto.