Resumo Técnico: Busca de Árvore de Conceitos Contrastiva para Descoberta de Algoritmos Assistida por LLM

Declaração do Problema

A descoberta de algoritmos assistida por Grandes Modelos de Linguagem (LLMs) opera como um processo de otimização iterativo e de caixa-preta, onde um LLM propõe programas candidatos e um avaliador externo fornece o feedback da tarefa. Embora paradigmas recentes (ex: FunSearch, AlphaEvolve) tenham redescoberto ou melhorado soluções para problemas combinatórios (como problemas do tipo Erdős), eles dependem amplamente de atualizações evolutivas impulsionadas pelo fitness. Nestes sistemas existentes, a seleção de pais é determinada pelo desempenho bruto (fitness) dos programas, e a busca prossegue como uma caminhada sobre a linhagem de programas ordenados por desempenho.

Uma limitação crítica desta abordagem é que o espaço de programas permanece fracamente estruturado. Mesmo quando restringidos por um LLM, os algoritmos gerados frequentemente carecem de noções claras de localidade, variação suave ou estrutura composicional que possam ser exploradas por algoritmos de busca. Consequentemente, a orientação é derivada principalmente de sinais de fitness brutos e do prior implícito do LLM, em vez de uma compreensão explícita e aprendida de quais componentes semânticos dos algoritmos são de fato úteis. Este artigo aborda a questão aberta de como explorar maximamente a representação interna do LLM do espaço de programas para melhorar a eficiência e a interpretabilidade da busca.

Metodologia: Busca de Árvore de Conceitos Contrastiva (CCTS)

Os autores introduzem a Busca de Árvore de Conceitos Contrastiva (CCTS), um framework que desloca a orientação da busca do fitness bruto para um espaço de conceitos semânticos hierárquico e aprendido. A hipótese central é que os algoritmos podem ser descritos por um espaço de conceitos semânticos subjacente organizado como uma hierarquia, onde os nós representam conceitos e as arestas codificam refinamento ou especialização.

1. Representação de Conceito e Construção da Árvore

• Extração de Características: Cada programa candidato $x$ é mapeado para uma representação de característica semântica $b = \Phi(x)$, extraída ao solicitar ao LLM a geração de uma lista de conceitos relevantes.
• Estrutura Hierárquica: Estes conceitos são organizados em uma árvore de conceitos enraizada. Um vetor de conceito $b$ é um vetor indicativo onde as ativações são fechadas por ancestralidade (ativar um conceito filho implica ativar todos os seus ancestrais). A árvore é dinâmica, crescendo à medida que novos conceitos são descozbertos durante a busca.

2. Aprendizado Contrastivo de Utilidade de Conceito

Em vez de selecionar pais baseando-se apenas em sua pontuação de fitness, a CCTS aprende quais conceitos estão empiricamente associados ao alto desempenho através de uma abordagem contrastiva:

• Particionamento: O arquivo de programas avaliados é particionado em subconjuntos "bons" ($y_i \ge \tau_t$) e "ruins" ($y_i < \tau_t$) com base em um limiar de desempenho.
• Ajuste de Modelo: Dois modelos probabilísticos, $\hat{p}_{\eta^+}(b)$ e $\hat{p}_{\eta^-}(b)$, são ajustados às distribuições de características dos subconjuntos bons e ruins, respectivamente. Os autores utilizam uma abordagem do tipo Estimador de Parzen Estruturado em Árvore (TPE) com um modelo Bernoulli hierárquico fatorado. Este modelo assume independência condicional de características dado o seu pai na hierarquia.
• Pontuação de Razão de Verossimilhança: Uma pontuação de razão de verossimilhança (utilidade de conceito logarítmica) é computada para cada programa:
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  Esta pontuação quantifica o quão fortemente um conjunto específico de conceitos distingue soluções de alto desempenho de soluções de baixo desempenho.

3. Seleção de Pais e Dinâmica de Busca

• Amostragem Enviesada: Os pais são selecionados do arquivo com uma probabilidade proporcional à sua pontuação de razão de verossimilhança. Isso enviesa a busca para programas que contêm combinações de conceitos empiricamente associadas à melhoria.
• Mecanismo de Exploração: Para evitar a convergência prematura e incentivar a descoberta de novos conceitos, a CCTS incorpora um mecanismo de exploração leve. Isso inclui:
  • Priors Beta: Suavização de contagens para garantir que novos conceitos nunca tenham probabilidade zero.
  • Viés de Novidade: Redução do peso de conceitos que foram frequentemente testados, favorecendo regiões subexploradas da árvore de conceitos.
  • Estratégia de Mistura: Uma mistura de explotação (baseada no modelo contrastivo aprendido) e exploração (baseada na novidade) guia a seleção de conceitos para injetar no prompt do LLM para a geração de filhos.

Principais Contribuições

1. Estrutura Semântica Explícita: O artigo propõe tornar explícita a estrutura latente do espaço de algoritmos através do aprendizado de uma árvore de conceitos hierárquica, indo além do espaço de programas não estruturado usado em algoritmos evolutivos padrão.
2. Orientação Contrastiva: Introduz um framework estatístico contrastivo que aprende a identificar quais conceitos priorizar e, crucialmente, quais conceitos evitar, em vez de apenas rastrear quais programas performam melhor.
3. Interpretabilidade: O método produz árvores de conceitos interpretáveis e específicas para a tarefa que revelam a estrutura semântica explorada durante a busca, oferecendo insights sobre as estratégias algorítmicas sendo descobertas.
4. Validação Sintética: Os autores constroem um ambiente sintético controlado com uma árvore de conceitos "professora" e utilidades de verdade fundamental (ground-truth). Isso permite validar que a CCTS recupera a estrutura semântica subjacente e que a dinâmica de busca observada é impulsionada pelo aprendizado das utilidades dos conceitos, e não por artefatos específicos do LLM.

Resultados Experimentais

Os autores avaliaram a CCTS em um benchmark de problemas combinatórios do tipo Erdős, incluindo empacotamento de círculos (circle packing), a conjectura de Kakeya aritmética, o problema do triângulo de Heilbronn e o problema de quadrados em quadrados.

• Ganhos de Desempenho: A CCTS alcançou consistentemente pontuações mais altas e melhoria mais rápida em comparação com estratégias de base (Uniforme, Gananciosa e seleção $k$-elite) em múltiplas tarefas.
• Mecanismo de Melhoria: A análise revelou que os ganhos de desempenho são impulsionados amplamente pelo aprendizado de quais conceitos evitar. Execuções bem-sucedidas identificaram um conjunto semelhante de conceitos de alta utilidade em relação às execuções malsucedidas, mas demonstraram uma capacidade significativamente melhor de suprimir conceitos de baixa utilidade (prejudiciais). Isso sugere que a CCTS estabiliza a busca ao reduzir a exploração improdutiva causada por correlações enganosas no prior inicial do LLM.
• Validação Sintética: No ambiente sintético, as utilidades de conceito aprendidas mostraram forte correlação ($r=0.94$) com as utilidades da professora de verdade fundamental, confirmando que o método recupera efetivamente representações semânticas significativas.
• Dependência de Estrutura: O equilíbrio ideal entre exploração e explotação dependeu da estrutura da árvore de conceitos subjacente (ex: razão de ramificação), sugerindo que as estratégias de busca devem ser adaptadas à topologia específica do espaço do problema.

Significância e Alegações

O artigo afirma que a CCTS aborda um descompasso fundamental na descoberta de algoritmos assistida por LLM: algoritmos de alta pontuação não geram necessariamente descendentes fortes porque o fitness é um mau substituto para a evoluibilidade em um espaço fracamente estruturado. Ao deslocar a seleção do fitness bruto para a evidência semântica de melhoria, a CCTS permite que a busca opere em um espaço de conceitos onde distância, recombinação e direção de busca são significativas.

Os autores posicionam este trabalho como um avanço metodológico em direção a uma descoberta de algoritmos mais confiável e escalável. Eles enfatizam que, embora os resultados atuais demonstrem melhorias relativas sobre as bases em benchmarks específicos, a principal contribuição é a demonstração de como estruturas de conceitos semânticos explícitas e compatíveis com humanos podem tornar a descoberta automatizada mais transparente, controlável e eficiente. O trabalho sugere que sistemas futuros devem focar no aprendizado e na exploração dessas hierarquias semânticas latentes, em vez de depender apenas de sinais de fitness de caixa-preta.