Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently

Resumo Técnico: Benefícios Prováveis do RLVR sobre o SFT para Modelos de Raciocínio

Formulação do Problema
Este trabalho aborda uma lacuna fundamental na compreensão de por que o Aprendizado por Reforço com Recompensas Verificáveis (RLVR) frequentemente produz capacidades de raciocínio superiores em Grandes Modelos de Linguagem (LLMs) em comparação ao Ajuste Fino Supervisionado (SFT) em demonstrações de especialistas. Embora evidências empíricas sugiram que modelos RLVR generalizam melhor e exibem um raciocínio mais robusto, carecia-se de um arcabouço teórico principiológico para explicar essa divergência.

Os autores modelam o raciocínio de Cadeia de Pensamento (CoT) como um problema de busca de caminho em uma estrutura específica de multigrafo. O grafo consiste em um nó de origem, um nó de bifurcação que se ramifica em $W$ caminhos distintos, e $K$ subgrafos de "diamante" sequenciais ao longo de cada ramo. Cada diamante contém $L$ arestas paralelas. A tarefa de raciocínio envolve navegar da origem até um nó folha específico. Crucialmente, o grafo é projetado de tal forma que a navegação eficiente exige a capacidade de detectar becos sem saída (entrar em um ramo que não é o alvo) e retroceder (backtracking) eficientemente até a bifurcação para explorar ramos alternativos.

Metodologia
O artigo fornece uma análise dinâmica comparando dois paradigmas de pós-treinamento aplicados a um modelo bigrama pré-treinado (representando o modelo de mundo):

1. Ajuste Fino Supervisionado (SFT): O modelo é treinado em trajetórias "douradas" de caminho mais curto da origem aos alvos. Essas trajetórias não contêm retrocesso, exploração ou tentativas falhas; elas apenas demonstram o caminho correto para frente. O objetivo de treinamento é a perda de entropia cruzada padrão.
2. Aprendizado por Reforço com Recompensas Verificáveis (RLVR): O modelo é treinado via rollouts on-policy. A função de recompensa combina uma recompensa de resultado (alcançar o alvo) com uma penalidade de comprimento (para desencorajar caminhos longos e ineficientes). O modelo aprende via atualizações de gradiente de política, especificamente analisando a dinâmica do fluxo de gradiente assinado.

Os autores analisam a evolução das probabilidades de transição para estados de arestas específicos:

• Estados de avanço (forward states): Movendo-se mais profundamente em um ramo.
• Estados de retrocesso (backward states): Movendo-se de volta em direção à bifurcação (backtracking).

Eles derivam a dinâmica do fluxo de gradiente para os logits que governam essas transições sob SFT e RLVR, provando propriedades de convergência em tempo finito.

Principais Contribuições e Resultados

1. Falha do SFT em Aprender o Retrocesso (Backtracking):
   Os autores provam que o SFT treinado exclusivamente em caminhos mais curtos "dourados" falha em aprender uma estratégia de retrocesso eficiente. Como os dados de treinamento nunca expõem o modelo a becos sem saída ou à necessidade de recuar, as probabilidades de transição para estados de retrocesso permanecem fixas em seus valores uniformes pré-treinados. O modelo aprende a mover-se para frente com probabilidade 1, mas não retém nenhum mecanismo para recuar eficientemente quando um ramo está incorreto.

2. Sucesso do RLVR em Aprender o Retrocesso:
   Em contraste, os autores provam que modelos treinados via RLVR aprendem a retroceder eficientemente. A natureza on-policy do RLVR força o modelo a gerar e experienciar rollouts falhos (becos sem saída). A penalidade de comprimento fornece um sinal de gradiente que penaliza explicitamente caminhos longos e errantes, incentivando o modelo a aprender que mover-se para trás de um beco sem saída é uma ação necessária para alcançar o alvo rapidamente. O modelo converge para uma política onde as probabilidades de transição de avanço e retrocesso aproximam-se de 1, efetivamente aprendendo a percorrer um ramo e recuar imediatamente se este não for o alvo.

3. Separação Exponencial no Computação de Tempo de Inferência:
   O artigo estabelece uma separação provável no tempo de computação esperado de inferência (tempo de hit/hitting time) necessário para encontrar um alvo:

   • Modelo RLVR: Requer $\Theta(WK)$ de tempo esperado. O modelo explora os ramos sequencialmente, percorrendo cada um em $O(K)$ de tempo e recuando imediatamente após a falha.
   • Modelo SFT: Requer $\Theta(WLK)$ de tempo esperado. Como o modelo SFT não consegue retroceder eficientemente (ele trata arestas de retrocesso como uma caminhada aleatória entre $L$ opções), ele leva $O(LK)$ de tempo para sair de um ramo errado.
     Isso resulta em uma separação exponencial em relação à profundidade do grafo ($K$) e uma separação linear em relação ao fator de ramificação dos diamantes ($L$).

4. Destilação de Traços de Raciocínio:
   Os autores demonstram que os benefícios do RLVR podem ser transferidos para um modelo base via destilação. Se um modelo base for ajustado finamente nos traços de raciocínio (incluindo passos de retrocesso) gerados por um modelo RLVR convergido, ele herda a capacidade de retrocesso eficiente, recuperando a complexidade de tempo de inferência de $\Theta(WK)$. Isso sugere que o fator crítico não é o algoritmo de RL em si, mas a inclusão de dados de retrocesso no conjunto de treinamento.

Significância e Alegações
O artigo afirma fornecer a primeira prova teórica de que a superioridade do RLVR sobre o SFT para tarefas de raciocínio decorre da capacidade da exploração on-policy de ensinar o retrocesso eficiente. Os autores argumentam que o SFT sobre demonstrações de especialistas é inerentemente limitado porque carece de exposição ao "espaço negativo" do raciocínio (caminhos falhos), levando a um modelo que não consegue se recuperar eficientemente de erros.

O trabalho destaca que:

• O retrocesso é uma habilidade aprendível: Não é uma propriedade inerente da arquitetura, mas um comportamento induzido pelo sinal de treinamento.
• A composição dos dados importa: A inclusão de tentativas falhas e passos de retrocesso no treinamento (seja via exploração de RL ou destilação) é crucial para reduzir a complexidade de busca.
• Fundamentação Teórica: Os resultados oferecem uma perspectiva de sistemas dinâmicos sobre por que o RLVR generaliza melhor, indo além das observações empíricas para garantias prováveis de eficiência de tempo de inferência.

Os autores concluem que, embora a destilação possa transferir essas capacidades, o processo de RLVR é o mecanismo que gera os dados necessários para aprender o retrocesso eficiente em primeiro lugar. As descobertas apoiam o uso de RLVR ou da destilação de traços gerados por RL para melhorar as capacidades de raciocínio de LLMs em tarefas complexas de múltiplos passos.