Scaling Test-Time Compute to Achieve IOI Gold Medal with Open-Weight Models

Resumo Técnico: GENCLUSTER e o Alcanço da Medalha de Ouro na IOI com Modelos Open-Weight

1. O Problema

A programação competitiva, especialmente em competições de alto nível como a Olimpíada Internacional de Informática (IOI), tornou-se um benchmark rigoroso para avaliar as capacidades de raciocínio e resolução de problemas de Modelos de Linguagem de Grande Escala (LLMs).

• Desafio Atual: Embora modelos proprietários (como os da OpenAI) tenham alcançado níveis de medalha de ouro na IOI, seus métodos são frequentemente secretos e não reprodutíveis.
• Limitação dos Modelos Open-Weight: Modelos de pesos abertos (open-weight) de ponta, como DeepSeek-R1 e Qwen, embora competitivos em benchmarks menores (como Codeforces), ainda ficam atrás dos sistemas proprietários em tarefas complexas de IOI, especialmente sob restrições estritas de submissão (máximo de 50 submissões por problema).
• Objetivo: Desenvolver uma abordagem escalável, transparente e reprodutível que permita que modelos open-weight atinjam o nível de medalha de ouro na IOI, utilizando Cálculo no Tempo de Teste (Test-Time Compute - TTC).

2. Metodologia: O Framework GENCLUSTER

Os autores propõem o GENCLUSTER, um framework de cálculo no tempo de teste que combina geração em larga escala, agrupamento comportamental, classificação por torneio e uma estratégia de submissão inteligente. O pipeline opera em quatro etapas principais para cada sub-tarefa do problema:

1. Geração Paralela de Candidatos:

   • O modelo gera um grande pool de soluções candidatas (K soluções) em paralelo para cada sub-tarefa.
   • Soluções que não compilam ou não são parseadas são filtradas.

2. Agrupamento Comportamental (Behavioral Clustering):

   • Para reduzir o espaço de busca, as soluções são agrupadas com base na similaridade de seus comportamentos de saída.
   • Geração de Testes Sintéticos: O LLM gera múltiplos geradores de testes aleatórios e validadores independentes para garantir que os casos de teste sejam válidos e cobram as especificações da sub-tarefa.
   • As soluções são executadas nesses casos de teste. Soluções que produzem exatamente a mesma saída para todos os testes são agrupadas no mesmo cluster.
   • Clusters que produzem saídas vazias ou erros de tempo de execução são descartados.

3. Classificação com Torneio (Ranking with Tournament):

   • Como há muitos clusters, é necessário ranqueá-los para selecionar os melhores.
   • Representante do Cluster: A solução com o maior comprimento de raciocínio (mais tokens) é escolhida como representante de cada cluster, assumindo uma correlação positiva entre profundidade de raciocínio e correção.
   • Torneio Round-Robin Parcial: Os representantes dos clusters participam de um torneio onde cada um joga $G_n$ vezes contra outros clusters escolhidos aleatoriamente.
   • Um LLM atua como juiz ("LLM-as-a-judge") comparando pares de soluções e decidindo o vencedor.
   • Os clusters são ranqueados com base no número de vitórias de seus representantes.

4. Estratégia de Submissão (Round-Robin Submission):

   • Respeitando o limite de 50 submissões por problema da IOI, o sistema utiliza uma estratégia cíclica.
   • Começa pelas sub-tarefas mais difíceis.
   • Itera pelos clusters ranqueados, enviando uma solução de cada cluster por vez (rodízio), até que a sub-tarefa seja resolvida (pontuação máxima atingida) ou o limite de submissões seja atingido.

3. Contribuições Principais

1. GENCLUSTER: Proposição de uma abordagem escalável de cálculo no tempo de teste que utiliza agrupamento comportamental e torneios para selecionar candidatos ótimos sob orçamentos de submissão limitados.
2. Primeira Medalha de Ouro Open-Weight: Demonstração, pela primeira vez, de que modelos open-weight (especificamente o gpt-oss-120b) podem alcançar a medalha de ouro na IOI 2025 quando combinados com uma estratégia de cálculo no tempo de teste transparente e reprodutível.
3. Lei de Escala (Scaling Law): Evidência de que o desempenho do GENCLUSTER escala consistentemente com o aumento do poder computacional (número de gerações), reduzindo a lacuna entre sistemas abertos e fechados.

4. Resultados Experimentais

• Modelos Avaliados: Foram testados gpt-oss-120b, gpt-oss-20b, DeepSeek-R1-0528 e Qwen3-235B-A22B.
• Desempenho do Modelo: O gpt-oss-120b superou significativamente os outros modelos, mostrando uma capacidade de escala superior conforme o número de gerações aumentava.
• Pontuação Final:
  • Com 5.000 gerações por sub-tarefa e o pipeline GENCLUSTER, o modelo atingiu uma pontuação de 446,75 na IOI 2025.
  • O limiar para a Medalha de Ouro é de 438,3. Portanto, o sistema alcançou a medalha de ouro.
  • Para comparação, a pontuação não restrita (Score@K) com 5.000 gerações foi de 499,51, indicando que a estratégia de seleção ainda tem margem de melhoria, mas a estratégia de submissão foi eficaz.
• Ablação de Estratégias: A comparação com outras estratégias (seleção aleatória, escolha pela maior cadeia de raciocínio sem clustering, votação majoritária) mostrou que o GENCLUSTER completo superou todas as alternativas por uma margem substancial.
  • Exemplo: GENCLUSTER (446,75) vs. Seleção Aleatória (300,10) vs. Cluster-Majority (314,22).
• Impacto de Parâmetros:
  • Aumentar o número de casos de teste melhora a pureza do cluster, mas também aumenta o número de clusters, tornando a seleção mais difícil.
  • O torneio de classificação satura após cerca de 10 jogos por representante, indicando um ponto ótimo de custo-benefício.

5. Significado e Limitações

Significado:

• O trabalho estabelece um novo marco para a avaliação transparente de raciocínio em LLMs, provando que a "caixa preta" de modelos proprietários não é estritamente necessária para atingir o topo em programação competitiva.
• Demonstra que o investimento em cálculo no tempo de teste (gerar e filtrar milhares de soluções) pode compensar limitações de treinamento em modelos open-weight.

Limitações Identificadas:

• Requisitos Computacionais: O método é extremamente custoso. Gerar 5.000 soluções e realizar o torneio de classificação consome bilhões de tokens (aprox. 14,6 bilhões de tokens no total para o benchmark), tornando-o inviável para aplicações em tempo real ou ambientes com poucos recursos.
• Dependência de Testes Sintéticos: O agrupamento comportamental depende de testes gerados pelo próprio modelo, o que pode criar "pontos cegos" onde soluções incorretas são agrupadas com corretas se os testes sintéticos não cobrirem casos de borda raros.
• Ruído no Julgamento (LLM-as-a-Judge): A classificação baseada em LLM pode ser influenciada por características superficiais (estilo de código, comprimento) em vez de correção lógica, criando uma lacuna entre o desempenho teórico e o prático.
• Correlação Imperfeita: Assumir que "mais tokens de raciocínio = solução mais correta" é uma heurística que nem sempre se sustenta, podendo priorizar soluções verbosas e erradas.

Em conclusão, o GENCLUSTER oferece um caminho escalável para elevar o desempenho de modelos open-weight a níveis de elite em programação competitiva, embora o custo computacional e a complexidade da orquestração permaneçam desafios significativos para adoção generalizada.