Resumo Técnico: ALGOBENCH

Declaração do Problema

Os atuais benchmarks de geração de código para grandes modelos de linguagem (LLMs), como HumanEval e LiveCodeBench, frequentemente apresentam taxas de aprovação elevadas que não refletem necessariamente capacidades genuínas de raciocínio algorítmico. Uma limitação primária é a contaminação de dados: enunciados de problemas estabelecidos, editoriais e soluções de referência estão amplamente disponíveis em corpora de treinamento públicos. Consequentemente, os modelos podem alcançar pontuações altas ao recrutar padrões de solução memorizados em vez de derivar algoritmos a partir de restrições. Embora benchmarks recentes tentem mitigar isso usando problemas mais novos ou difíceis (ex: LiveCodeBench, ProBench, HLCE), estes permanecem estáticos. Uma vez lançados, seus enunciados de problemas e soluções geradas por modelos inevitavelmente entram nos dados de treinamento, permitindo que modelos futuros melhorem via exposição em vez de um raciocínio aprimorado. Há uma necessidade de um benchmark que gere problemas dinamicamente onde a memorização da solução de origem seja insuficiente, forçando os modelos a adaptar suas estratégias algorítmicas.

Metodologia

Estrutura Central: ALGOBENCH

Os autores propõem o ALGOBENCH, um framework para construir automaticamente problemas algorítmicos inéditos a partir de fontes conhecidas de programação competitiva. A filosofia central é a transformação por deslocamento de restrição: modificar um problema de origem de modo que o algoritmo de referência original falhe, necessitando de uma nova abordagem algorítmica ou de uma complexidade assintótica diferente.

1. Operadores de Transformação
O framework emprega dez operadores de transformação baseados em regras para gerar variantes ($q'$) a partir de problemas de origem ($q$). Estes incluem:

• Escalonamento de Restrição (CS): Aumentar os limites de entrada (ex: $N \le 2000 \to N \le 2 \times 10^5$).
• Estático-para-Dinâmico (SD): Converter problemas estáticos em problemas dinâmicos (ex: adicionar operações de atualização).
• Perturbação de Objetivo (OP): Alterar o objetivo de otimização.
• Injeção de Armadilha Greedy (GT): Introduzir restrições que invalidam heurísticas gulosas (greedy), exigindo programação dinâmica.
• Outros operadores incluem Acoplamento de Restrição, Expansão de Casos de Borda, Mudança de Requisito de Saída e transformações mais amplas como Envoltório de Mundo Real e Mudança de Estrutura de Grafo.

2. Portões de Qualidade (Quality Gates)
Para garantir a validade e evitar a trivialidade, os problemas gerados devem passar por quatro portões automatizados:

• Portão 1 (Rejeição da Solução Antiga): A solução de referência original ($a^*$) deve falhar no novo problema (produzindo WA, TLE ou MLE).
• Portão 2 (Verificação da Nova Solução): Uma nova solução de referência ($\hat{a}^*$) deve ser verificada contra um oráculo de força bruta em entradas pequenas.
• Portão 3 (Não-Paráfrase): O enunciado gerado deve ser suficientemente distinto da origem (TextSim $< \tau_{text}$).
• Portão 4 (Certificação de Complexidade): A nova solução deve satisfazer a complexidade de tempo e espaço alvo.

3. Verificador de Complexidade Determinístico
Um verificador de três camadas avalia as soluções submetidas para distinguir entre correção funcional e otimalidade algorítmica:

• Camada 1 (Análise Estática de AST): Analisa o código para estimar a complexidade de tempo/espaço com base em aninhamento de loops, recursão e estruturas de dados.
• Camada 2 (Verificação de Tag de Algoritmo): Verifica evidências estruturais dos algoritmos esperados (ex: propagação preguiçosa para segment trees) e a ausência de algoritmos proibidos.
• Camada 3 (Escalonamento de Tempo de Execução Calibrado): Executa as soluções em tamanhos de entrada crescentes para ajustar um modelo de tempo de execução $T(n) = cn^\alpha (\log n)^\gamma$. As soluções são penalizadas se o expoente ajustado exceder o alvo por mais de 0.15.

Métricas de Avaliação

Além do padrão pass@k, o ALGOBENCH introduz métricas conscientes de complexidade:

• OPTT/OPTS: Taxas de submissões que são corretas e atendem à complexidade de tempo/espaço alvo.
• TRAPRATE: A fração de submissões incorretas que reutilizam estruturalmente o algoritmo de origem (indicando a "armadilha da solução antiga").
• GAPT (Gap de Eficiência): Mede o gap entre o expoente de tempo de execução ajustado e o expoente alvo.
• CONSENS: Mede a queda de desempenho conforme a magnitude da restrição aumenta.
• $\Delta_{gen}$: A queda de desempenho dos problemas de origem para as variantes geradas.

Principais Contribuições

1. Framework: Introdução do ALGOBENCH, um pipeline automático para gerar problemas rastreáveis, porém algoritmicamente distintos.
2. Transformação & Validação: Design de dez operadores de transformação e um sistema de controle de qualidade de quatro portões que garante que os problemas gerados rejeitem soluções antigas e exijam nova complexidade.
3. Dataset de Benchmark: Construção de um benchmark com 598 variantes aceitas (420 usadas nos experimentos principais) derivadas de 300 problemas de origem (Codeforces, AtCoder, Kattis, LeetCode Hard), completos com metadados, soluções de referência e oráculos de força bruta.
4. Métricas: Proposta de métricas (OPTT, OPTS, TRAPRATE, GAPT, CONSENS) que avaliam a adequação assintótica, não apenas a correção funcional.
5. Achados Empíricos: Avaliação de sete LLMs através de seis estratégias de prompting, demonstrando que o desempenho degrada significativamente nas variantes geradas e que muitas soluções "corretas" falham nos requisitos de complexidade.

Resultados Experimentais

Queda de Desempenho e Adaptação

• Gap de Generalização: Os modelos mostram um declínio acentuado no desempenho ao passar dos problemas de origem para as variantes do ALGOBCH. Modelos mais antigos caíram de uma média de 85,1% de pass@1 nas origens para 53,6% nas variantes. Mesmo os modelos de fronteira mais recentes (GPT-5.4, Claude Opus 4.5) caíram 33,3%.
• Desajuste de Complexidade: Existe um gap significativo entre pass@k e OPTT. Por exemplo, o GPT-4o alcançou 72,7% de pass@5, mas apenas 63,6% de OPTT, indicando que muitas soluções aprovadas usaram algoritmos subótimos.
• Riscos de Recuperação (Retrieval): A Geração Aumentada por Recuperação (RAG) usando os problemas de origem como contexto frequentemente aumentou o TRAPRATE. Para o Gemini 2.5 Flash, o RAG aumentou a taxa de armadilha de 3,6% para 30,0%, sugerindo que a recuperação ancora os modelos à solução original (agora inválida).

Análise de Erro

A análise de 400 falhas de submissão revelou que as falhas são predominantemente algorítmicas em vez de nível de implementação:

• Armadilha da Solução Antiga (42,3%): O modelo implementou o algoritmo de origem, passando nos exemplos públicos, mas falhando nos testes de armadilha ocultos.
• Muito Lento (21,8%): O modelo identificou a abordagem correta, mas perdeu as otimizações necessárias (ex: falha ao mudar de $O(N^2)$ para $O(N \log N)$).
• Bugs de Implementação: Responderam por apenas 9,0% das falhas.

Sensibilidade e Contaminação

• Sensibilidade de Restrição: O desempenho degradou bruscamente conforme os limites de entrada aumentaram (ex: $N=10K \to 50K$), precisamente onde soluções quadráticas sofrem timeout.
• Efeito de Contaminação: Os modelos performaram significativamente melhor em problemas de origem mais antigos (2020) comparados aos mais novos (2024), sugerindo memorização. No entanto, esse gap diminuiu para as variantes do ALGOBENCH, que permaneceram consistentemente difíceis independentemente do ano de publicação do problema de origem.

Significância e Alegações

O artigo afirma que o ALGOBENCH avalia uma capacidade distinta dos benchmarks de código padrão: a habilidade de adaptar o raciocínio algorítmico a novas restrições, em vez de depender de templates memorizados.

• Além da Correção Funcional: O benchmark demonstra que altas taxas de aprovação em datasets estáticos não garantem adequação assintótica. Muitos modelos produzem soluções que são funcionalmente corretas, mas algoritmicamente ineficientes.
• Robustez à Memorização: Ao gerar automaticamente problemas onde a solução de origem falha, o ALGOBNECH mitiga o risco de contaminação de dados de treinamento, fornecendo uma medida mais confiável do verdadeiro raciocínio algorítmico.
• Valor Diagnóstico: O framework identifica modos de falha específicos (ex: incapacidade de transitar de Greedy para DP, ou falha em lidar com atualizações dinâmicas) que são obscurecidos em benchmarks tradicionais.

Os autores concluem que os atuais LLMs lutam quando templates familiares são insuficientes, e que o progresso futuro no raciocínio algorítmico requer benchmarks que demandem adaptação genuína em vez de apenas correspondência de padrões (pattern matching).