Duel-Evolve: Reward-Free Test-Time Scaling via LLM Self-Preferences

O artigo apresenta o Duel-Evolve, um algoritmo de otimização evolutiva que melhora a qualidade das respostas de LLMs em tarefas complexas sem recompensas externas, utilizando preferências pareadas auto-geridas e um modelo de Bradley-Terry bayesiano para guiar a busca em espaços de saída discretos.

O essencial

Imagine que você está tentando resolver um quebra-cabeça extremamente difícil, como um problema de matemática complexa ou escrever um código de computador perfeito. Você tem um assistente muito inteligente (uma Inteligência Artificial ou LLM), mas ele não sabe exatamente qual é a resposta certa de primeira.

A maioria dos métodos atuais tenta dar uma "nota" para cada tentativa do assistente (como uma nota de 0 a 100). O problema é que, em muitas tarefas, é muito difícil inventar uma regra para dar essa nota. É como tentar julgar uma pintura abstrata: é difícil dizer "essa é 85,5 pontos". Às vezes, a nota é confusa, raramente aparece ou simplesmente não existe.

É aqui que entra o DUEL-EVOLVE (o método descrito no artigo). Em vez de pedir uma nota, eles mudaram a estratégia para algo muito mais natural: um torneio de duelos.

Aqui está como funciona, explicado de forma simples:

1. A Ideia Central: O Torneio de Duelos

Em vez de perguntar ao assistente: "De 0 a 10, o quão bom é esta resposta?", o sistema pergunta: "Entre esta resposta A e esta resposta B, qual delas você prefere?"

É muito mais fácil para uma pessoa (ou uma IA) dizer "A é melhor que B" do que dar uma nota exata. É como em um campeonato de tênis: não precisamos saber exatamente quantos pontos o jogador fez para saber quem ganhou o set; basta saber quem venceu o ponto.

2. O Processo: Evolução e Seleção Natural

O DUEL-EVOLVE funciona como um jogo de "sobrevivência dos mais aptos" (evolução), mas feito inteiramente pela própria IA:

• A Geração (Os Atletas): A IA cria várias tentativas de solução (como se fossem atletas nascendo).
• O Duelo (A Seleção): A IA pega duas soluções aleatórias e pergunta a si mesma: "Qual dessas duas é melhor?". Ela faz isso milhares de vezes, criando uma grande lista de quem venceu quem.
• O Juiz Sábio (O Modelo de Bradley-Terry): O sistema não confia apenas em uma única decisão. Ele usa uma "estatística mágica" (chamada Modelo de Bradley-Terry) para juntar todas essas pequenas batalhas. Ele calcula: "Se o Candidato A venceu o B, e o B venceu o C, então o A provavelmente é muito bom". Isso cria uma classificação global, mesmo que as decisões individuais às vezes estejam erradas.
• A Incerteza (O Mapa do Tesouro): O sistema também sabe quando está "chutando". Ele mantém um mapa de confiança. Se ele não tem certeza sobre qual é a melhor solução, ele foca em duelar aquelas opções incertas para aprender mais. Se ele já sabe que uma opção é ruim, ele para de gastar tempo nela.

3. O Ciclo de Melhoria

A cada rodada, o sistema faz três coisas:

1. Luta: Faz duelos entre as melhores soluções atuais para refinar quem é o campeão.
2. Aprende: Atualiza seu "mapa de confiança" sobre quem é bom e quem é ruim.
3. Cria: Pega as soluções que estão no topo do ranking (os "pais") e pede para a IA criar novas versões delas, tentando melhorar ainda mais.

É como um treinador de futebol que, em vez de dar notas aos jogadores, os faz jogar partidas entre si. O treinador observa quem ganha, descobre os melhores jogadores e pede para eles treinarem juntos para criar uma equipe ainda mais forte para a próxima partida.

4. Por que isso é incrível?

A grande vantagem do DUEL-EVOLVE é que ele não precisa de um professor externo.

• Métodos antigos precisavam de um "professor" (um modelo de recompensa) para dar notas. Se o professor fosse ruim, o aluno não aprendia.
• O DUEL-EVOLVE é auto-suficiente. A própria IA é o aluno e o juiz. Ela gera as soluções e decide qual é melhor.

5. Os Resultados (O "Placar")

Os autores testaram isso em duas áreas difíceis:

• Matemática (MathBench): O sistema conseguiu acertar 94% dos problemas, superando os melhores métodos antigos em 20 pontos percentuais.
• Programação (LiveCodeBench): No código, ele melhorou os resultados em mais de 12 pontos percentuais, encontrando soluções que outros métodos não conseguiam.

Resumo em uma Metáfora Final

Imagine que você está tentando encontrar o caminho mais curto para sair de um labirinto gigante no escuro.

• Métodos antigos: Alguém segura uma lanterna e diz "Você está a 50 metros do fim" ou "Você está a 48 metros". Se a lanterna estiver quebrada, você fica perdido.
• DUEL-EVOLVE: Você não mede a distância. Você manda dois exploradores (soluções) saírem em direções diferentes. Depois, você pergunta: "Quem chegou mais longe?". Você repete isso com muitos exploradores, descobre quem tem o melhor instinto e manda eles criarem novos exploradores baseados no que aprenderam. Com o tempo, você encontra a saída sem nunca ter precisado de uma lanterna ou de uma régua.

O artigo mostra que, quando não temos uma régua para medir a qualidade, podemos usar a comparação (quem é melhor que quem) para evoluir e encontrar as melhores soluções possíveis.

Resumo técnico

Título: DUEL-EVOLVE: Escalabilidade no Tempo de Teste sem Recompensa via Preferências Automáticas de LLM

1. O Problema

Muitas aplicações de Grandes Modelos de Linguagem (LLMs) buscam otimizar saídas no tempo de teste (test-time) iterando sobre um espaço de saída discreto e combinatório (ex: sequências de tokens para raciocínio matemático ou código). O objetivo é encontrar uma candidata $y$ que maximize uma função de utilidade $f(y)$.

As abordagens existentes geralmente dependem de:

• Avaliadores escalares calibrados: Modelos de recompensa treinados ou funções de pontuação manuais que atribuem um valor numérico a cada candidata.
• Desafios: Em muitas tarefas complexas (como provas matemáticas ou geração de código), essas pontuações escalares são indisponíveis, esparsas (ex: apenas "correto/incorreto" no final) ou pouco confiáveis. Além disso, métodos de refinamento iterativo que usam auto-avaliação (LLM avaliando sua própria resposta com notas) frequentemente sofrem de má calibração e inconsistência.

O artigo propõe resolver esse problema utilizando preferências pareadas (pairwise comparisons) como único sinal de otimização, eliminando a necessidade de um modelo de recompensa externo ou rótulos de verdade fundamental (ground-truth) durante a busca.

2. Metodologia: DUEL-EVOLVE

O DUEL-EVOLVE é um algoritmo de otimização evolutiva que substitui recompensas escalares por preferências pareadas elicidas pelo próprio LLM (que atua como gerador e juiz). O método é estruturado em três fases principais dentro de um loop evolutivo:

A. Formulação como Problema de Bandit Duelante (Dueling Bandits)
O problema é mapeado para o framework de Dueling Bandits, onde o algoritmo seleciona pares de candidatos para comparar. O LLM atua como um juiz $J$ que, dado um par $(y_i, y_j)$, indica qual é preferido.

B. Agregação Bayesiana (Modelo Bradley-Terry)
Para lidar com o ruído e a natureza local das comparações, o DUEL-EVOLVE utiliza um Modelo de Bradley-Terry Bayesiano:

• Atribui uma utilidade latente $\theta_y$ a cada candidato.
• Modela a probabilidade de $y_i$ ser preferido a $y_j$ como $P(c_{ij}=+1) = \sigma(\theta_i - \theta_j)$.
• Mantém uma distribuição posterior sobre as utilidades.
• Utiliza uma aproximação de Laplace em torno da estimativa MAP (Maximum A Posteriori) para obter médias e intervalos de confiança (incerteza) para cada candidato de forma computacionalmente viável.

C. O Loop Evolutivo e Amostragem Dupla de Thompson (Double Thompson Sampling - DTS)
O algoritmo alterna entre três etapas para explorar e explorar o espaço de soluções:

1. Atualização (Update): Ajusta o modelo de Bradley-Terry com o histórico de comparações para obter estimativas de qualidade $(\mu, \sigma)$ para todos os candidatos avaliados.
2. Avaliação (Evaluate): Seleciona pares de candidatos para comparar usando Amostragem Dupla de Thompson (DTS). Em vez de comparar aleatoriamente, o algoritmo amostra utilidades da distribuição posterior e compara os candidatos que têm alta probabilidade de serem ótimos. Isso foca o orçamento de avaliação nos candidatos mais promissores.
3. Evolução (Evolve): Seleciona "pais" (candidatos de alta pontuação) com base nas estimativas posteriores e no mapeamento de incerteza. O LLM gerador é condicionado a esses pais e suas utilidades estimadas para propor novos candidatos (filhos) que tentam melhorar as soluções existentes.

Mecanismos de Otimização:

• Poda (Pruning): Mantém um conjunto de sobreviventes, removendo candidatos cujos limites de confiança superior caem abaixo do limite inferior do melhor candidato, economizando recursos.
• Memória Evolutiva (no LiveCodeBench): Para tarefas de código, o prompt inclui uma "memória evolutiva" onde o modelo pode anotar insights, casos de borda e padrões algorítmicos para usar em iterações futuras.

3. Contribuições Principais

1. Otimização sem Recompensa Externa: Demonstra que preferências pareadas internas ao modelo são suficientes para otimizar em espaços discretos grandes, sem necessidade de modelos de recompensa treinados ou funções de pontuação manuais.
2. Incerteza Consciente: A integração de inferência Bayesiana (Bradley-Terry + Laplace) permite que o algoritmo quantifique a incerteza sobre a qualidade dos candidatos, guiando a alocação de orçamento de comparação de forma eficiente.
3. Escalabilidade no Tempo de Teste: O método continua a melhorar conforme mais poder computacional (mais gerações e comparações) é investido, superando métodos estáticos e de refinamento simples.
4. Arquitetura Unificada: Combina a seleção inteligente de pares (DTS) com a geração evolutiva baseada em LLM, criando um ciclo fechado de melhoria contínua.

4. Resultados Experimentais

O método foi avaliado em dois benchmarks desafiadores:

• MathBench (Raciocínio Matemático):

  • Tarefa: Resolver problemas de múltipla escolha de matemática (do ensino médio ao universitário).
  • Resultado: O DUEL-EVOLVE alcançou 94% de precisão.
  • Comparação: Superou a melhor linha de base (Feedback Descent) em 20 pontos percentuais e superou métodos estáticos (como Few-shot CoT e Self-consistency) significativamente. A convergência foi rápida, atingindo 90% de precisão nas primeiras 10 gerações.

• LiveCodeBench (Geração de Código):

  • Tarefa: Resolver problemas de programação competitiva em Python com testes ocultos.
  • Resultado: O DUEL-EVOLVE alcançou 37,4% de precisão (passando em 100% dos testes ocultos).
  • Comparação: Superou métodos evolutivos comparáveis em mais de 12 pontos percentuais e superou o Feedback Descent e o GEPA.
  • Observação: O método demonstrou robustez mesmo quando os testes públicos (feedback intermediário) eram insuficientes para garantir a correção nos testes ocultos.

5. Significância e Impacto

O trabalho é significativo porque oferece uma solução viável para a otimização de LLMs em cenários onde a definição de uma função de recompensa escalar é difícil ou impossível.

• Viabilidade Prática: Elimina a necessidade de treinar modelos de recompensa caros ou criar rubricas manuais complexas.
• Generalização: A abordagem de usar o próprio LLM como juiz e gerador, guiado por um modelo estatístico de preferências, é aplicável a diversas domínios (matemática, código, redação, etc.).
• Eficiência de Recursos: Ao focar as comparações nos candidatos mais prováveis de serem ótimos (via DTS), o método maximiza o retorno sobre o custo computacional de inferência do LLM.

Em resumo, o DUEL-EVOLVE estabelece que as preferências pareadas auto-geradas, quando agregadas estatisticamente com consciência de incerteza, fornecem um sinal de otimização forte e robusto para melhorar a qualidade de respostas de LLMs em tempo de teste, superando métodos que dependem de recompensas escalares ou refinamento cego.