Resumo Técnico: Escalando o Verificador Agêntico para Programação Competitiva

Definição do Problema

Embora os Grandes Modelos de Linguagem (LLMs) tenham demonstrado fortes capacidades em síntese de programas, eles frequentemente têm dificuldade em resolver problemas de programação competitiva corretamente em uma única tentativa. Uma estratégia comum para melhorar a precisão é o escalonamento em tempo de teste (test-time scaling), onde múltiplas soluções candidatas são amostradas e um verificador seleciona a melhor delas.

Os métodos de verificação existentes enfrentam limitações significativas no contexto da programação competitiva:

1. Geração de Casos de Teste Completos: Gerar casos de teste completos (entradas + saídas de referência/ground-truth) é frequentemente tão difícil quanto resolver o problema original, tornando o processo computacionalmente caro e pouco confiável.
2. Execução Apenas de Entradas: Abordagens recentes geram apenas entradas válidas e selecionam soluções com base no acordo de saída (votação). No entanto, esses métodos geralmente dependem de amostragem de entrada aleatória.
3. Ineficiência da Amostragem Aleatória: O espaço de entradas válidas na programação competitiva é vasto, mas apenas uma pequena fração é "discriminativa" (ou seja, capaz de expor diferenças comportamentais entre soluções corretas e incorretas). Os experimentos preliminares do artigo demonstram que escalar o número de entradas aleatórias gera retornos decrescentes e falha em fechar a lacuna de desempenho em comparação com os casos de teste de referência (ground-truth).

Metodologia: Verificador Agêntico

Os autores propõem o Verificador Agêntico, um agente baseado em LLM projetado para raciocinar ativamente sobre comportamentos de programas e buscar entradas de teste altamente discriminativas que exponham discrepâncias entre soluções candidatas.

Mecanismo Central

Em vez de amostragem aleatória cega, o verificador envolve-se em uma interação de múltiplos turnos com um ambiente de execução de código:

1. Formulação da Tarefa: Dada uma questão $Q$ e um par de soluções candidatas $(C_a, C_b)$, o objetivo do agente é gerar um programa gerador de entrada $G$ que produza uma entrada válida $x$ onde $Exec(C_a, x) \neq Exec(C_b, x)$.
2. Loop de Interação: O agente propõe iterativamente entradas, executa soluções candidatas, inspeciona o feedback (erros de tempo de execução, saídas) e refina suas hipóteses para descobrir contraexemplos.
3. Estratégia de Seleção: No tempo de inferência, o verificador treinado gera entradas de teste direcionadas para pares de soluções candidatas. Essas entradas são usadas em uma estratégia de votação baseada em execução para selecionar a solução final.

Pipeline de Treinamento

O verificador é treinado através de um pipeline escalável de três estágios:

1. Síntese de Dados em Larga Escala: Os autores constroem um conjunto de dados de problemas de programação competitiva com soluções rotuladas. Para problemas que carecem de casos de teste de referência, eles sintetizam suítes de teste de alta qualidade usando um mecanismo de votação majoritária baseado em consenso entre múltiplas soluções de referência para garantir a confiabilidade.
2. Refinamento por Rejeição (Rejection Fine-Tuning): Utilizando um modelo professor forte (Qwen3-235B), eles coletam trajetórias de interação de múltiplos turnos bem-sucedidas onde o agente gera com sucesso entradas distintivas. O modelo base é ajustado finamente nessas trajetórias de alta qualidade, mascarando os prompts iniciais e o feedback para aprender padrões de interação eficazes.
3. Aprendizado por Reforço Agêntico (RL): O verificador é otimizado adicionalmente usando GRPO (Group Relative Policy Optimization). A função de recompensa é esparsa e baseada em resultados:
   • $+1$: Entrada válida que distingue as duas soluções.
   • $0$: Entrada válida que não distingue (as soluções concordam).
   • $-1$: Entrada inválida ou gerador vazio.
     O currículo de treinamento prioriza pares de "negativos difíceis" onde entradas distintivas são raras, incentivando o agente a aprender comportamentos de geração direcionados.

Principais Contribuições

1. Análise Empírica: O artigo demonstra empiricamente que a geração de entradas aleatórias é altamente ineficiente para a verificação baseada em execução de apenas entrada, revelando uma lacuna substancial de desempenho em comparação com entradas de teste discriminativas.
2. Verificador Agêntico: Introdução de um agente que gera ativamente entradas de teste altamente discriminativas através de interação de múltiplos turnos, indo além da amostragem estática ou aleatória.
3. Pipeline de Treinamento Escalável: Um novo pipeline que combina síntese de dados, refinamento por rejeição e aprendizado por reforço agêntico para treinar o verificador.
4. Escalonamento em Tempo de Teste: Demonstração de que o método proposto se beneficia continuamente do aumento do computação em tempo de teste, escalando efetivamente tanto com o número de soluções candidatas quanto com o número de entradas geradas.

Resultados Experimentais

A abordagem foi avaliada em cinco benchmarks de programação competitiva (USACO, LiveCodeBench, OJBench, ICPC-Eval e um novo benchmark de CodeForces) usando dois modelos de política (Qwen3-30B e Qwen3-235B).

• Ganhos de Desempenho: O Verificador Agêntico superou consistentemente bases fortes, incluindo geração de entrada aleatória, casos de teste gerados por modelos (CodeT, CodeRM) e seleção baseada em modelo de recompensa.
  • Alcançou ganhos absolutos de +10–15% na acurácia Best@k sobre bases de execução fortes.
  • No subconjunto "Hard" do OJBench, o verificador treinado de 30B melhorou o desempenho em +34,1% sobre a base, superando significativamente um modelo zero-shot de 235B.
• Comportamento de Escalonamento: Ao contrário das bases que mostraram saturação precoce, o Verificador Agêntico exibiu um claro comportamento de escalonamento em tempo de teste, com o desempenho melhorando continuamente à medida que o número de entradas de teste aumentava.
• Zero-Shot vs. Treinado: LLMs zero-shot forneceram algum melhoria, mas o verificador treinado para a tarefa específica superou significativamente os modelos zero-shot, mesmo quando o modelo treinado era 7x menor que seu correspondente zero-shot.

Significância e Alegações

O artigo afirma que a eficácia da votação baseada em execução é determinada principalmente pela qualidade discriminativa das entradas de teste, e não apenas pela sua quantidade.

Além de melhorar a seleção Best-of-N, os autores destacam uma implicação mais ampla: Suítes de teste de benchmarks são verificadores imperfeitos. Suítes de teste fixas cobrem apenas uma parte limitada do espaço de entradas válidas, levando a falsos positivos onde soluções incorretas passam em todos os testes do benchmark. O Verificador Agêntico pode expor ativamente essas falhas ao descobrir contraexemplos direcionados. Assim, os autores posicionam o verificador não apenas como uma ferramenta de reclassificação (reranking), mas como um mecanismo complementar de verificação de correção que pode expandir a cobertura de entradas e mitigar o ruído induzido por benchmarks na avaliação de código em larga escala.