Resumo Técnico: Comportamento e Representação em LLMs de Pesos Abertos para Otimização Combinatória

Declaração do Problema

A Otimização Combinatória (CO) depende fortemente de processos manuais e orientados por especialistas para o desenvolvimento e seleção de algoritmos. Embora o Aprendizado de Máquina (ML) tenha começado a se integrar neste domínio, as capacidades de representação interna dos Grandes Modelos de Linguagem (LLMs) em relação às estruturas de problemas de CO permanecem amplamente inexploradas. Estudos existentes avaliam primariamente o desempenho funcional dos LLMs (por exemplo, geração de heurísticas ou código) sem investigar se as suas representações internas capturam informações significativas sobre instâncias de problemas ou comportamento algorítmico.

Este estudo aborda a lacuna entre a competência observável e a compreensão latente nos LLMs. Investiga se LLMs de pesos abertos e congelados codificam informações estruturais e numéricas sobre Problemas de Otimização Combinatória (COPs) que podem ser aproveitadas para tarefas subsequentes. Especificamente, a pesquisa distingue entre informação que pode ser explicitamente recuperada através de prompting direto e informação que é implicitamente codificada nas camadas ocultas, mesmo que não seja acessível via geração.

Metodologia

Os autores propõem um framework experimental unificado combinando análises de Consulta Direta (Direct Querying) e Sondagem (Probing) através de quatro problemas de referência: Bin Packing (BPP), Graph Coloring (GCP), Jobshop Scheduling (JSP) e Knapsack Problem (KP).

1. Configuração Experimental

• Modelos: Cinco LLMs de pesos abertos variando de 3B a 120B de parâmetros, incluindo a família Llama instruct (3B, 8B, 70B) e a família de raciocínio gpt-oss (20B, 120B).
• Dados: Um subconjunto estratificado de 5% de instâncias de benchmarks de estudos anteriores de Análise de Espaço de Instâncias (ISA), preservando a cobertura entre problemas, complexidades de características e portfólios de algoritmos.
• Representações: As instâncias foram apresentadas em três formatos: Padrão (texto estruturado), Semelhante a Código (MiniZinc) e Linguagem Natural.
• Restrições: Nenor fine-tuning específico para a tarefa foi realizado; os modelos foram utilizados "off-the-shelf" para avaliar representações intrínsecas.

2. Consulta Direta (Recuperação Explícita)

Os modelos foram instigados a extrair características específicas da instância (ex: contagem de nós, densidade de grafo, pesos médios) diretamente do texto de entrada.

• Variantes de Prompt:
  • Padrão: Solicitação direta de um valor numérico em JSON.
  • Cadeia de Pensamento (CoT): Solicitação de um rastro de raciocínio seguido pelo valor.
  • Raciocínio Nativo (gpt-oss): Utilização do canal de raciocínio interno do modelo via interface Harmony.
• Avaliação: Os valores previstos foram comparados com valores de verdade fundamental (ground-truth) computados por extratores manuais utilizando métricas como Erro Médio Absoluto (MAE) e a proporção de previsões dentro de 1% da verdade.

3. Sondagem (Decodificabilidade Implícita)

Para avaliar as representações latentes, os autores extraíram ativações de camadas ocultas da última camada dos modelos.

• Agrupamento (Pooling): As ativações foram agrupadas utilizando estratégias de média (mean), máximo (max) e último token (last-token).
• Sondas (Probes): Modelos supervisionados (regressores Ridge, MLPs, LightGBM) foram treinados nestes vetores agrupados para prever características da instância (regressão) ou o melhor algoritmo para uma instância (classificação).
• Objetivo: Determinar se a informação de características é decodificável de forma linear ou não linear no espaço latente, independentemente da saída generativa do modelo.

4. Seleção de Algoritmo

O framework de sondagem foi estendido para uma tarefa de seleção de algoritmo por instância. Embeddings derivados de LLM foram usados como entradas para classificadores para prever o algoritmo ideal de um portfólio, com desempenho comparado contra baselines usando características manuais e baseadas em ISA.

Principais Contribuições

1. Framework Unificado: Introduziu uma metodologia para avaliar conjuntamente a extração de características explícita (consulta) e a análise de representação latente (sondagem) para CO.
2. Análise de Escala e Raciocínio: Validou o framework através de cinco modelos (3B–120B) e analisou o impacto do prompting de Cadeia de Pensamento (CoT), revelando sua forte dependência da escala do modelo.
3. Dissociação de Sinais: Forneceu a primeira evidência em larga escala de que a recuperação explícita e a codificação latente são propriedades distintas; os modelos podem falhar em gerar um valor correto, mas ainda assim codificar essa informação em estados ocultos.
4. Descritores Substitutos (Surrogate Descriptors): Demonstrou que as representações de camadas ocultas de LLMs podem servir como descritores substitutos eficazes para seleção de algoritmos, alcançando poder preditivo comparável a características tradicionais manuais.
5. Reprodutibilidade: Liberou o dataset, código e prompts para fomentar mais pesquisas na interseção entre LLMs e otimização.

Principais Resultados

Desempenho de Consulta Direta

• Complexidade de Características: Os modelos recuperam de forma confiável características simples e diretamente extraíveis (ex: contagens), mas têm dificuldade significativa com características que exigem computação estruturada ou agregação (ex: médias, razões).
• Escala do Modelo: O escalonamento melhora o desempenho para características de baixa complexidade, mas gera retornos decrescentes para características de alta complexidade.
• Cadeia de Pensamento (CoT): O efeito do CoT é não-monotônico e dependente de escala. Ele degrada o desempenho em modelos pequenos (3B), oferece benefícios seletivos em modelos intermediários (8B) e melhora consistentemente o desempenho em modelos grandes (70B). No entanto, sempre aumenta o custo computacional.
• Modos de Falha: Modelos orientados ao raciocínio (gpt-oss) exibem "abstenção calibrada", frequentemente retornando null quando a computação é pouco confiável, enquanto modelos Llama tendem a produzir "alucinações excessivamente confiantes" (números incorretos, mas com aparência válida).

Sondagem e Codificação Latente

• Latente vs. Explícito: Existe uma lacuna consistente entre a recuperação explícita e a decodificabilidade latente. A sondagem frequentemente alcança maior precisão do que a consulta direta, particularmente para características complexas, indicando que a informação relevante está presente nos estados ocultos, mas não é acessível via geração.
• Robustez da Representação: O sinal preditivo nas representações latentes é robusto a variações na representação de entrada (Padrão vs. Linguagem Natural vs. Semelhante a Código) e nas estratégias de agrupamento (pooling).

Seleção de Algoritmo

• Paridade Preditiva: Embeddings derivados de LLM alcançaram precisão preditiva na seleção de algoritmos comparável às características tradicionais manuais e baseadas em ISA em todos os cinco modelos.
• Dependência do Classificador: A escolha do classificador downstream (ex: LightGBM vs. Regressão Logística) teve um impacto mais significativo no desempenho do que a fonte específica da representação (LLM vs. Manual).
• Sem Vantagem Sistemática: Não foi encontrada evidência robusta de que as características baseadas em ISA superam sistematicamente as representações derivadas de LLM, nem vice-versa.

Significância e Alegações

O artigo alega que os LLMs possuem uma assimetria funcional entre suas capacidades de raciocínio explícito e suas representações internas. Embora os LLMs ainda não sejam substitutos confiáveis para extratores de características exatos e manuais devido aos altos custos computacionais e à falta de confiabilidade em computação estruturada, suas representações latentes contêm regularidades estatísticas suficientes para agir como descritores substitutos eficazes.

Os autores argumentam que as representações derivadas de LLM são mais valiosas em cenários onde:

1. A engenharia de características manual não está disponível ou é muito cara para projetar.
2. As instâncias chegam em formatos heterogêneos ou não padronizados.
3. É necessário um descritor de instância agnóstico ao problema antes que a engenharia de características específica seja possível.

O estudo conclui que, embora os LLMs não "computem" características no sentido determinístico exigido por pipelines de otimização exata, seus estados internos codificam um sinal que é altamente preditivo do desempenho algorítmico, preenchendo a lacuna entre dados brutos de instâncias e seleção de algoritmos sem a necessidade de design de características manuais.