Resumo Técnico: Descoberta de LLM Consciente de Orçamento via Utilidade de Fronteira Calibrada por Custo

Formulação do Problema

Modelos de linguagem de grande escala (LLMs) são cada vez mais empregados para descoberta científica e algorítmica através de busca em tempo de inferência, onde soluções candidatas são geradas, avaliadas e refinadas sequencialmente. Em domínios como otimização matemática, design de algoritmos e descoberta de programas executáveis, avaliadores determinísticos fornecem sinais de qualidade repetíveis. No entanto, controladores de descoberta adaptativos existentes tipicamente atribuem crédito às ações de busca baseando-se apenas no progresso do escore, ignorando a heterogeneidade dos custos das ações.

Sob o modelo de preços de API baseado em tokens, diferentes ações de busca incorrem em custos vastamente distintos. Um refinamento curto pode custar uma geração de referência, enquanto uma chamada de orientação de contexto longo ou uma tentativa de erro de código pode custar seis ou mais. Quando um controlador atribui crédito a uma ação de alto custo e a uma ação de baixo custo igualmente porque ambas geraram o mesmo progresso de escore, ele falha em considerar o custo de oportunidade do orçamento restante. O artigo formaliza isso como um problema de alocação de nível populacional sobre um espaço discreto de candidatos executáveis, onde o horizonte de busca efetivo é definido por um orçamento de tokens acumulado e realizado, em vez de um número fixo de iterações.

Os autores provam (Proposição 1) que, em instâncias com custos de ação heterogêneos, um controlador "cego ao custo" — um cujo distribuição de ações depende apenas do histórico de escore e não dos custos realizados — pode atingir apenas uma fração evanescente do objetivo orçamentário ideal conforme o número de fronteiras de busca e as disparidades de custo aumentam.

Metodologia: CostAda

Para abordar essa lacuna, os autores introduzem o CostAda, um controlador adaptativo calibrado por custo projetado para descoberta de LLM sob orçamentos explícitos de tokens do lado da busca. O CostAda substitui o crédito baseado apenas em progresso pela utilidade de fronteira calibrada por custo, que integra o progresso da fronteira local, a melhor melhoria global até o momento, o custo da ação realizada e o orçamento restante.

O mecanismo central opera através de três controles acoplados:

1. Utilidade de Fronteira Calibrada por Custo:
   A utilidade $u_t^{(k)}$ para uma fronteira $k$ na iteração $t$ é definida como:
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   Onde:

   • $g_t$ é o ganho global (melhoria sobre o melhor global até o momento).
   • $\delta_t^{(k)}$ é o ganho local (melhoria sobre o arquivo local da fronteira).
   • $\lambda_t = 1 - \rho_t$ é o peso global, condicionado à razão do orçamento restante $\rho_t$. À medida que o orçamento se esgota, o controlador muda o foco do desenvolvimento local para a melhoria global.
   • $d_t = 1 + \lambda_t^c \phi_t$ é um divisor de custo baseado no custo de etapa realizado normalizado. Isso garante que ganhos iguais de ações caras recebam menos crédito do que ganhos de ações baratas.

2. Decisões de Controle Conscientes do Orçamento:

   • Intensidade de Exploração Local: A amplitude de amostragem ao redor de uma fronteira é ajustada com base em sua utilidade suavizada. Alta utilidade leva a um refinamento de baixa intensidade; baixa utilidade dispara uma exploração mais ampla. Crucialmente, a razão do orçamento restante $\rho_t$ suprime a exploração dispendiosa conforme o orçamento se aproxima da exaustão.
   • Alocação de Fronteira: O controlador aloca o orçamento futuro para as fronteiras com base no ganho global por custo realizado ($r_t^{(k)} = g_t / d_t$). Fronteiras que melhoram apenas contra arquivos locais fracos não recebem crédito de alocação. Uma regra de limite superior de confiança (upper-confidence bound) equilibra a explotação de fronteiras de alto desempenho com a exploração de fronteiras subamostradas, sendo limitada pelo orçamento restante.
   • Intervenção de Tática Orçada: Orientações de nível superior (ex: chamadas de "guia" ou "tática") são compradas apenas quando predicados de evidência específicos são atendidos: (1) o orçamento restante pode arcar com o guia mais uma reserva para testes; (2) há uma ausência sustentada de progresso global (estagnação) ou gastos acumulados de baixo rendimento; e (3) nenhuma janela de consolidação está ativa. Isso evita intervenções caras perto do horizonte, a menos que sejam estritamente necessárias.

Principais Contribuições

1. Formulação do Problema e Limite Teórico: O artigo formaliza a descoberta de LLM sob orçamentos explícitos de tokens do lado da busca e prova que estratégias de crédito cegas ao custo perdem o objetivo orçamentário em configurações de custo heterogêneo.
2. Utilidade de Fronteira Calibrada por Custo: Os autores introduzem um princípio de crédito que condiciona o progresso ao custo da ação realizada e ao orçamento restante, garantindo que o custo de oportunidade de cada ação seja explícito.
3. Controlador CostAda: Uma instanciação deste princípio que coordena a exploração local limitada pelo orçamento, a alocação de fronteira consciente do custo e a intervenção de tática orçada.
4. Validação Empírica: Experimentos extensos demonstrando que o CostAda alcança eficiência de orçamento e qualidade de solução final superiores em comparação com baselines de estado da arte.

Resultados Experimentais

Os autores avaliaram o CostAda contra o AdaEvolve (um baseline consciente de progresso) e o EvoX (um controlador de evolução de estratégia) através de oito benchmarks (abrangendo empacotamento geométrico, geometria extrema, combinatória aditiva e otimização de programas executáveis) usando dois modelos de base: GLM-5 e GPT-5.4.

• Eficiência: O CostAda atinge a qualidade do orçamento total do melhor baseline com no máximo metade do orçamento em 12 de 16 pares benchmark–backbone.
• Qualidade Final: Em ambos os backbones, o CostAda atinge a melhor média de qualidade final em todos os oito benchmarks.
• Caminho do Orçamento: Em um quarto do orçamento, o escore normalizado médio do CostAda excede a média do orçamento total do melhor baseline. Ele atinge a maior Área Sob a Curva (AUC) normalizada em 15 de 16 pares benchmark–backbone.
• Estabilidade: O CostAda demonstra menor variância nos resultados em comparação aos baselines, particularmente em benchmarks como Circle Packing Rect sob o GLM-5.

Significância e Alegações

O artigo alega que o CostAda muda fundamentalmente como os recursos de busca são gerenciados na descoberta impulsionada por LLM. Ao tratar o custo realizado e o orçamento restante como entradas de controle ativas, em vez de variáveis de contabilidade post-hoc ou simples regras de parada, o CostAda alinha a estratégia de busca com a realidade econômica da precificação baseada em tokens.

Os autores afirmam que sua abordagem preserva a qualidade da solução final enquanto melhora significativamente a eficiência do orçamento. Os resultados sugerem que a calibração de custo é essencial para escalar a descoberta por LLM, pois ignorar a heterogeneidade de custo leva a uma alocação de recursos subótima que não pode ser recuperada simplesmente suavizando os sinais de progresso. O trabalho demonstra que um controlador pode navegar efetivamente o trade-off entre exploração e explotação quando o "custo" de uma ação é tão variável quanto o "ganho" que ela produz.