Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States

Título: Rompendo o Teto de Capacidade do Pós-Treinamento de LLMs ao Reintroduzir Estados de Markov

1. O Problema: O "Teto de Capacidade" no RL para LLMs

O artigo identifica um fenômeno crítico no treinamento de Grandes Modelos de Linguagem (LLMs) usando Aprendizado por Reforço (RL): um "teto de capacidade" persistente.

• Contexto Atual: A prática dominante no pós-treinamento de LLMs (como PPO e GRPO) trata o modelo como um agente onde o estado é definido pela concatenação de todo o histórico de ações (tokens) anteriores. Isso cria uma representação baseada em "história como estado".
• A Limitação: Evidências recentes sugerem que o RL atua principalmente como um refinador de padrões já latentes nos pesos pré-treinados, em vez de descobrir novas estratégias ou expandir fundamentalmente o espaço de soluções.
• Causa Raiz: Diferente de ambientes clássicos de RL (como xadrez ou robótica) que utilizam Estados de Markov compactos e informativos, os LLMs atuais operam sobre um histórico de ações em expansão constante e ruidoso. Isso impõe uma complexidade de amostragem exponencial, tornando a descoberta de novas capacidades computacionalmente proibitiva quando o modelo base não cobre a solução ideal.

2. Metodologia: Reintrodução de Estados de Markov Explícitos

Os autores propõem uma mudança de paradigma fundamental: abandonar a modelagem baseada puramente em histórico e reintroduzir Estados de Markov explícitos no pipeline de treinamento.

• Conceito Central: Em vez de o modelo receber (histórico de ações) como entrada, ele recebe um estado atualizado ($s_{h}$) que encapsula toda a informação necessária para decisões futuras, descartando o ruído irrelevante do histórico.
• Mecanismo de Transição:
  1. O agente escolhe uma ação $a_h$.
  2. Uma função de transição de estado (pode ser um ambiente simulado, uma regra lógica ou um modelo aprendido $\hat{P}$) calcula o próximo estado $s_{h+1} = P(s_h, a_h)$.
  3. O próximo passo de decisão é condicionado apenas a $s_{h+1}$, não ao histórico completo.
• Implementação Prática:
  • Os autores utilizam tarefas de raciocínio lógico sintéticas (Sudoku, Sokoban, Futoshiki) onde o estado do tabuleiro é naturalmente um estado de Markov observável.
  • Eles treinam um modelo de previsão de estado ($\hat{P}$) para simular o ambiente em cenários onde o acesso direto ao ambiente não é possível durante a inferência.
  • Comparam três abordagens:
    1. Action-Seq: Modelo baseado puramente no histórico de ações (padrão atual).
    2. State-Action-Seq: Modelo que vê o histórico de estados e ações (mas ainda não é estritamente Markoviano).
    3. Markov (Proposta): Modelo que condiciona apenas no estado atual estimado.

3. Contribuições Principais

1. Quebra do Teto de Capacidade: Demonstração empírica de que modelos com estados de Markov superam consistentemente os limites de desempenho do RL tradicional em tarefas complexas de lógica, onde os modelos baseados em histórico estagnam ou falham.
2. Garantias Teóricas de Eficiência de Amostragem: Prova teórica de que o aprendizado baseado em Markov reduz drasticamente a complexidade de amostragem. Enquanto a abordagem baseada em histórico exige cobertura exponencial do espaço de trajetórias ($O(|A|^H)$), a abordagem de Markov exige apenas cobertura linear do espaço de estados ($O(H)$), evitando o custo computacional exponencial descrito por Foster et al. (2025).
3. Generalização Robusta (OOD): Os modelos de Markov demonstram uma capacidade superior de generalização fora da distribuição (OOD), resolvendo quebra-cabeças com maior complexidade estrutural e profundidade de busca do que os encontrados durante o treinamento.

4. Resultados Experimentais

Os experimentos foram conduzidos em modelos Qwen3-4B e Qwen2.5-3B-Instruct em tarefas de Sudoku, Sokoban e Futoshiki.

• Desempenho em Tarefas Difíceis:
  • Em Sokoban e Futoshiki, modelos baseados em histórico (Action-Seq) tiveram desempenho próximo de zero (0.2% - 2.5% de acerto).
  • A abordagem Markov elevou esses números para 76.1% (Sokoban) e 75.0% (Futoshiki) no Qwen3-4B.
• Eficiência de Treinamento:
  • Curvas de recompensa mostram que os modelos de Markov convergem mais rápido e atingem recompensas mais altas com menos passos de treinamento, validando a menor complexidade de amostragem.
  • Análise de Pass@k (probabilidade de encontrar a solução correta em $k$ amostras) revela que os modelos de Markov expandem o limite de capacidade do modelo base, enquanto os modelos de histórico falham em melhorar ou até degradam o desempenho em relação ao warm-up supervisionado (SFT).
• Ablação:
  • Modelos que têm acesso ao estado atual, mas ainda usam o histórico completo (State-Action-Seq), performam melhor que os baseados apenas em histórico, mas pior que os puramente Markovianos. Isso indica que o histórico extra é muitas vezes redundante e introduz correlações espúrias que dificultam o aprendizado.

5. Significado e Implicações

O trabalho sugere que o caminho para a Inteligência Artificial Geral (AGI) e o crescimento de capacidades abertas em IA Generativa exige uma mudança fundamental na formulação do RL:

• Mudança de Paradigma: É necessário abandonar a modelagem "história-como-estado" em favor de representações de Markov estruturadas que se alinham com a lógica subjacente de tarefas de raciocínio complexo.
• Aplicabilidade Real: A abordagem é aplicável a cenários do mundo real como depuração de código (onde o estado é o snapshot do código), raciocínio matemático (onde o estado é o conjunto de lemas estabelecidos) e refinamento iterativo de respostas.
• Conclusão: A reintrodução de estados de Markov não é apenas uma otimização, mas uma condição necessária para superar as limitações estruturais atuais do pós-treinamento de LLMs, permitindo a descoberta genuína de novas capacidades de raciocínio.