Resumo Técnico: DecompRL

Definição do Problema

Os Grandes Modelos de Linguagem (LLMs) atualmente têm dificuldade em resolver problemas complexos onde a política base possui uma probabilidade próxima de zero de gerar uma solução correta. As estratégias existentes enfrentam gargalos significativos:

• Amostragem Repetida (pass@k): Embora eficaz para escalar o computo em tempo de teste, o custo de GPU cresce linearmente com o número de tentativas. Os ganhos de desempenho frequentemente crescem de forma logarítmica em relação a esses custos lineares.
• Aprendizado por Reforço (RL) Padrão: Métodos como Proximal Policy Optimization (PPO) ou Group Relative Policy Optimization (GRPO) melhoram a precisão de tentativa única (pass@1), mas frequentemente reduzem a diversidade de amostras. Isso compromete sua eficácia ao escalar a inferência para valores de $k$ elevados ($k \gg 100$).
• A Limitação Central: Quando o espaço de busca é muito grande, nem o aumento da amostragem nem os sinais de gradiente podem superar a baixa probabilidade de a política base produzir uma solução correta.

Metodologia: DecompRL

Os autores propõem o DecompRL, um framework de aprendizado por reforço que desloca o gargalo de escala do caro custo de inferência em GPU para a avaliação barata em CPU, através do aproveitamento de geração modular hierárquica.

1. Inferência Hierárquica

Em vez de gerar uma solução de código monolítica, o DecompRL treina modelos para decompor um problema em uma hierarquia de subfunções independentemente solucionáveis.

• Política de Decomposição ($\pi(D)$): Decompõe um problema $x$ em um conjunto de $n$ funções especificadas por assinaturas e docstrings em linguagem natural ($D$).
• Política de Implementação ($\pi(I|D)$): Gera $k$ implementações independentes para cada função em $D$.
• Recombinação: Ao gerar $k$ implementações para cada uma das $n$ funções, o sistema cria $k^n$ soluções candidatas através da recombinação. Isso permite uma explosão combinatória de programas potenciais ($k^n$) com apenas um custo de inferência linear ($k \times n$ tokens).

2. Objetivos de Aprendizado por Reforço

O DecompRL trata a inferência hierárquica como um problema de RL multi-agente cooperativo envolvendo duas políticas. Para lidar com a recompensa esparsa e a alta variância inerentes à recombinação, os autores introduzem adaptações algorítmicas específicas:

• Objetivo LogMeanExp: Para equilibrar exploração e explotação, os autores utilizam uma função objetivo suave definida como $\text{logmeanexp}_\beta(r_1, \dots, r_n) = \beta \log(\frac{1}{n} \sum e^{r_i/\beta})$. Esta interpola entre a média ($\beta \to \infty$) e o máximo ($\beta \to 0$), aproximando um objetivo de mistura log-uniforme de pass@k.
• Baseline Leave-One-Out: Para calcular os gradientes da política, os autores utilizam um baseline leave-one-out. Para uma ação específica (decomposição ou implementação), a vantagem é calculada comparando o objetivo de múltiplas amostras do conjunto total de recompensas contra o objetivo computado a partir do conjunto excluindo aquela ação. Isso reduz a variância do gradiente e evita o viés.
• Treinamento Sequencial: As políticas de decomposição e implementação são treinadas sequencialmente (etapas alternadas) em vez de conjuntamente. Isso aborda o problema do "alvo móvel" (moving target) no RL multi-agente, impedindo que a política de implementação sofra overfitting a uma decomposição específica e vice-versa.

3. Mudança Computacional

O método desloca fundamentalmente o gargalo computacional:

• RL Padrão: Dominado pelos custos de inferência de GPU para gerar soluções completas.
• DecompRL: Dominado pelos custos de execução de CPU para avaliar soluções recombinadas. A geração de tokens em GPU é reduzida em aproximadamente 50× para orçamentos de avaliação equivalentes (ex: 512 avaliações).

Resultados Principais

Experimentos foram conduzidos no LiveCodeBench e CodeContests utilizando Qwen 2.5 7B, Llama 3.1 8B Instruct e Code World Model 32B.

• Desempenho em Problemas Difíceis: O DecompRL supera as linhas de base de RL padrão (GRPO, treinamento pass@k, SPO) quando os orçamentos de tokens excedem $10^5$. Ele resolve problemas que a geração padrão não consegue alcançar, atingindo até 35% de taxa de solução no subconjunto "difícil" do LiveCodeBench.
• Comportamento de Escala: Enquanto os métodos padrão saturam conforme os orçamentos de tokens aumentam, o sucesso do DecompRL continua a escalar. Com até 3 milhões de tokens por problema, ele supera significativamente os métodos existentes.
• Diversidade e Recombinação: O método gera soluções diversas. A análise mostra que os modelos treinados com DecompRL aprendem a criar decomposições maiores (mais funções) conforme o treinamento progride, o que correlaciona com taxas de sucesso mais altas em grandes orçamentos de inferência.
• Eficiência: Com 512 avaliações por problema, o DecompRL reduz a geração de tokens em GPU de ~198k (padrão) para ~4k, deslocando o domínio do tempo de execução para a CPU (99,6% de tempo de CPU vs. 0,4% de tempo de GPU).

Significância e Alegações

O artigo afirma que o DecompRL oferece um novo caminho para resolver problemas "mais difíceis" onde a política base possui uma taxa de sucesso próxima de zero:

1. Superando o Cold Start: Atua como uma ferramenta de exploração para descobrir soluções corretas para tarefas inalcançáveis pela amostragem de alto pass@k padrão, tornando-se um complemento natural para pipelines de destilação de política.
2. Escalabilidade Eficiente: Ao desacoplar o custo de geração do custo de avaliação, permite escalar a busca em clusters de CPU baratos sem aumentar proporcionalmente as pegadas de GPU.
3. Modularidade como Eixo de Controle: O pipeline de geração resultante oferece eixos de interpretabilidade e controle não disponíveis na amostragem repetida ou nos métodos de cadeia de pensamento (chain-of-thought) escalados.
4. Limitações: Os autores observam um "imposto de formato" (format tax) onde a inferência hierárquica tem desempenho inferior em problemas fáceis ou orçamentos de tokens baixos em comparação com a geração monolítica. Eles também observam uma tendência de "colapso de tamanho" (redução do tamanho da decomposição) durante o treinamento, que mitigam via objetivo logmeanexp e treinamento sequencial.

Os autores posicionam o DecompRL não como um substituto para o RL pós-treinamento padrão (que permanece mais eficiente em amostras para políticas iniciais fortes), mas como uma estratégia de exploração especializada para descobrir dados de alta qualidade e resolver tarefas anteriormente insolúveis.