Resumo Técnico: AlgoSkill

Declaração do Problema

Projetar algoritmos eficientes a partir de enunciados de problemas em linguagem natural é uma tarefa complexa que vai além da simples geração de código. Requer que um resolvedor compreenda formatos de entrada/saída, infira restrições, determine classes de complexidade viáveis, selecione paradigmas algorítmicos apropriados, justifique a corretude e refine soluções para atender aos limites de tempo e memória.

As abordagens existentes de Grandes Modelos de Linguagem (LLMs), como geração direta, prompting de Cadeia de Pensamento (CoT) e métodos de autorrefinamento, frequentemente tratam o design de algoritmos como uma tarefa de geração de texto livre. Esses métodos falham frequentemente em problemas difíceis ao selecionar paradigmas incorretos, omitir as restrições de complexidade pretendidas, definir estados incompletos ou aplicar regras gulosas sem argumentos válidos. Além disso, sistemas baseados em busca que operam sobre programas brutos ou rascunhos de texto livre podem ser difíceis de inspecionar, reutilizar ou verificar de forma eficaz. O desafio central é que os métodos atuais não modelam explicitamente os passos de raciocínio sequenciais e dependentes de estado inerentes ao design de algoritmos humano.

Metodologia: Estrutura AlgoSkill

Os autores propõem o AlgoSkill, uma estrutura que modela o design de algoritmos como uma tomada de decisão sequencial sobre uma biblioteca tipada de habilidades algorítmicas. Em vez de gerar código diretamente, o sistema navega por um estado de design selecionando e compondo habilidades específicas e verificáveis.

1. Biblioteca de Habilidades Algorítmicas Tipadas

A estrutura utiliza uma biblioteca de 20 habilidades algorítmicas tipadas ($O$), cada uma definida por uma precondição, uma função de transição de estado, uma pós-condição, efeitos de complexidade, regras de verificação e modos comuns de falha. As habilidades cobrem todo o espectro do design de algoritmos:

• Estágio inicial: Abstração do problema ($o_{abs}$), análise de restrições ($o_{constraint}$).
• Construção: Construção de força bruta ($o_{brute}$), design de estado ($o_{state}$), seleção de estrutura de dados ($o_{ds}$).
• Verificação e Reparo: Verificação de prova ($o_{inv}$), construção de contraexemplo ($o_{counter}$), refinamento de complexidade ($o_{complex}$).
• Especializadas: Detecção de monotonicidade, relaxação, dualidade, simetria, randomização, etc.

2. Estado de Design e Transições

O sistema mantém um estado de design $s_t$ contendo o enunciado do problema, entidades analisadas, plano de solução atual, código gerado, estimativas de complexidade e um histórico de testes falhos ou mensagens do verificador. Em cada etapa, um escalonador seleciona uma habilidade válida da biblioteca com base no estado atual, atualizando o estado via uma função de transição $T(s_t, o_t)$. Este processo continua até que um estado terminal seja alcançado, que é então decodificado em um algoritmo candidato.

3. Busca e Escalonamento

O AlgoSkill emprega um controlador de Busca em Árvore Monte Carlo (MCTS) para explorar sequências de habilidades.

• Filtro de Habilidade Válida: Antes da seleção, as habilidades são mascaradas com base em precondições (ex: se um risco de timeout for detectado, habilidades de refinamento de complexidade são habilitadas).
• Política Aprendida: Uma política neural $\pi_\theta$ pontua habilidades válidas com base no estado atual.
• Controlador MCTS: O controlador usa o algoritmo Upper Confidence Bound (UCB) para equilibrar exploração e explotação, selecionando sequências de habilidades que maximizam as recompensas esperadas.
• Feedback de Verificação: A busca é guiada por um verificador externo que avalia candidatos usando compilação, testes unitários, testes de estresse e análise de complexidade simbólica.

4. Treinamento com Recompensas de Verificação

O escalonador é treinado usando aprendizado por reforço de gradiente de política. A função de recompensa $R$ é decomposta em cinco componentes:

• Corretude ($R_{cor}$): Baseada no sucesso de compilação, taxas de aprovação em testes unitários, taxas de aprovação em testes de estresse e concordância com o oráculo.
• Eficiência ($R_{eff}$): Penaliza violações de limites de tempo e memória.
• Explicação ($R_{expl}$): Recompensa a inclusão de ideias algorítmicas, pseudocódigo e análise de complexidade.
• Reparo ($R_{rep}$): Credita o sistema por transformar um candidato falho em um candidato aprovado.
• Risco ($R_{risk}$): Penaliza riscos de complexidade identificados durante o rastreamento simbólico.

Principais Contribuições

1. Biblioteca de Habilidades Tipadas: A definição de uma biblioteca de 20 habilidades algorítmicas tipadas que formalizam etapas comuns no design de algoritmos, afastando-se da geração de texto livre.
2. Estrutura Guiada por Habilidades: A introdução do AlgoSkill, que compõe essas habilidades sob feedback de verificação usando um escalonador aprendido e MCTS.
3. Avaliação Empírica: Avaliação abrangente em benchmarks de programação competitiva e otimização combinatória, demonstrando melhorias sobre a geração direta, prompting, refinamento e baselines de busca.

Resultados Experimentais

Os autores avaliaram o AlgoSkill em um benchmark de 275 problemas do Codeforces, AtCoder e LeetCode Hard, bem como em um benchmark de regras livre de contaminação e um "Benchmark Difícil" de problemas novos e complexos.

• Benchmarks de Programação Competitiva: O AlgoSkill melhorou as taxas de aprovação sobre a geração direta de LLM. Por exemplo, no benchmark CP-275, melhorou o desempenho do Haiku de 78,2% para 80,7% e do Gemini de 11,6% para 18,2%.
• Otimalidade de Tempo: Em problemas onde o juiz retornou um veredito de complexidade determinado, o AlgoSkill melhorou significamente a otimalidade de tempo (T-opt). Por exemplo, no backbone Haiku, a T-opt melhorou de 91,4% (Direto) para 96,0% (AlgoSkill-G).
• Análise de Contaminação: Em um benchmark de regras gerado proceduralmente e livre de contaminação, o AlgoSkill alcançou 89% de otimalidade de tempo (T-optimality) comparado a 45% do LLM Direto, sugerindo que os ganhos advêm do raciocínio e não da memorização.
• Benchmarks Difíceis: Em um subconjunto de 15 problemas difíceis que exigem variantes algorítmicas não padronizadas, o AlgoSkill (MCTS) resolveu 7/15 problemas (47%), igualando-se ao Reflexion e superando significativamente o LLM Direto (20%).
• Estudos de Ablação: Remover habilidades específicas (ex: Abstração de Problema) causou quedas significativas de desempenho, confirmando a necessidade da estrutura de habilidades tipadas. O escalonamento por MCTS superou a seleção gulosa e a busca em largura (beam search) em amostras difíceis.
• Eficiência de Tokens: O overhead do AlgoSkill foi modesto, variando de 1,1× a 1,7× o consumo de tokens da geração direta, dependendo do modelo de base.

Significância e Alegações

O artigo afirma que o design automático de algoritmos deve ser visto como um processo de escalonamento de habilidades guiado por verificação em vez de geração de código em uma única etapa. Ao estruturar o espaço de busca sobre habilidades algorítmicas tipadas e verificáveis, o AlgoSkill permite que os LLMs:

• Rastreiem explicitamente estados de design e estimativas de complexidade.
• Realizem reparos direcionados baseados em modos de falha específicos (ex: contraexemplos, violações de complexidade).
• Alcancem maior otimalidade de tempo e robustez em problemas novos e difíceis em comparação com métodos existentes.

Os autores concluem que a composição de habilidades estruturadas é uma abordagem eficaz para melhorar o design de algoritmos baseado em LLM, particularmente para tarefas que exigem derivação algorítmica genuína em vez de recuperação de templates. Eles reconhecem limitações, incluindo a dependência da cobertura da biblioteca de habilidades predefinida e o custo computacional do MCTS, mas enfatizam o sucesso da estrutura em separar o raciocínio algorítmico da memorização.