💻 computer science

An In-depth Study of LLM Contributions to the Bin Packing Problem

Este artigo contesta a afirmação de que os Grandes Modelos de Linguagem avançam significativamente a descoberta matemática no problema de empacotamento de itens ao demonstrar que as heurísticas geradas por eles são opacas e que as instâncias do problema são, na verdade, simples o suficiente para serem resolvidas por algoritmos mais eficientes, interpretáveis e generalizáveis, destacando, assim, a necessidade de uma validação rigorosa das contribuições científicas geradas por LLMs.

Autores originais: Julien Herrmann, Guillaume Pallez

Publicado 2026-06-19

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Julien Herrmann, Guillaume Pallez

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está administrando um armazém enorme. Todos os dias, caminhões chegam com caixas de todos os tamanhos diferentes e você tem que empacotá-las em contêineres de envio (bins) conforme elas chegam. Você não sabe como será a próxima caixa; você só tem que tomar uma decisão rápida: "Coloco esta caixa no Contêiner A, no Contêiner B ou abro um novo Contêiner C?"

O objetivo é simples: usar o menor número possível de contêineres. Este é um clássico enigma conhecido como o Problema do Empacotamento de Caixas (Bin Packing Problem).

Recentemente, um estudo famoso (de Romera-Paredes et al.) afirmou que Modelos de Linguagem de Grande Escala (LLMs) — a mesma tecnologia de IA que escreve ensaios e códigos — haviam descoberto um "novo segredo matemático" para resolver este enigma de empacotamento melhor do que os humanos poderiam. Eles disseram que a IA encontrou uma regra nova e inteligente que era tão genial que contava como uma "descoberta matemática".

Este artigo de Julien Herrmann e Guillaume Pallez é como uma equipe de detetives especialistas vindo investigar essa afirmação. Eles colocaram suas lupas e disseram: "Espere um pouco. Vamos ver o que a IA realmente fez."

Aqui está o que eles descobriram, explicado de forma simples:

1. O "Segredo" da IA Não Era Tão Secreto

A IA produziu um conjunto de instruções de computador (uma heurística) que empacotou as caixas um pouco melhor do que os métodos humanos padrão. O estudo original alegava que essas instruções eram "interpretáveis", o que significa que os humanos podiam ler facilmente e entender a lógica.

A Verificação de Realidade do Artigo:
Os autores examinaram o código da IA e descobriram que era como ler uma receita escrita em um dialeto estranho.

O Código "c12": Este era uma longa lista de regras do tipo "Se isso, então aquilo". Era legível, mas a lógica era bagunçada. Era como um chef dizendo: "Se a panela estiver entre 7 e 8 graus, adicione sal. Se estiver entre 8 e 9, adicione uma pitada a menos". Funcionava, mas não explicava por que funcionava.
O Código "c14": Este era ainda pior. Era uma fórmula matemática complexa que parecia um amontoado de símbolos sem sentido. Os autores tiveram que realizar milhares de experimentos apenas para adivinhar o que o código estava realmente fazendo. Eles perceberam que, embora o código fosse escrito em inglês simples (Python), o raciocínio por trás dele estava oculto. Era uma "caixa preta" usando uma máscara transparente.

A Analogia: Imagine que a IA lhe deu uma bússola mágica que sempre aponta para o Norte. O estudo original disse: "Olhem, a bússola é feita de vidro, então podemos ver a agulha! Ela é totalmente compreensível!" Os autores dizem: "Sim, podemos ver a agulha, mas não temos ideia de como o ímã dentro dela funciona. Só sabemos que ela aponta para o Norte porque a testamos um milhão de vezes."

2. A IA Não Descobriu uma Nova Lei da Física

O estudo original alegou que a IA fez uma "descoberta matemática". Os autores argumentam que isso é um exagero.

A Verificação de Realidade do Artigo:
A IA foi testada em cenários muito específicos e estreitos (como caixas que têm todas entre 20 e 100 unidades de tamanho). Os autores descobriram que a IA não inventou uma nova forma de pensar; ela apenas encontrou uma versão levemente modificada de um truque antigo e simples.

Eles perceberam que o "tempero secreto" da IA era, na verdade, apenas dois números simples (parâmetros) que diziam:

"Se uma caixa se encaixar de forma muito justa, coloque-a lá."
"Se não se encaixar de forma justa, coloque-a em um contêiner que tenha bastante espaço sobrando."

Os autores pegaram essa ideia simples, removeram o código complexo da IA e construíram um novo algoritmo super simples (chamado ab-FirstFit ou ab-WorstFit).

O Resultado: Este novo algoritmo criado por humanos era mais rápido, mais fácil de entender e funcionava melhor do que o código complexo da IA. Ele até funcionava em diferentes tipos de tamanhos de caixas, enquanto o código da IA quebrava quando as regras mudavam ligeiramente.

A Analogia: É como se a IA tivesse encontrado uma maneira ligeiramente melhor de amarrar um cadarço, inventando um nó complexo com 15 voltas. Os autores olharam para isso e perceberam: "Ah, você só precisa puxar os cadarços com mais força e deixar um pouco de folga", e mostraram que um nó duplo simples funciona melhor, é mais fácil de aprender e não exige um doutorado em teoria de nós.

3. A "Descoberta" Foi Apenas uma Falta de Pesquisa Prévia

O estudo original alegou que encontraram algo "novo" porque ninguém havia publicado um artigo sobre esses tamanhos de caixa específicos antes.

A Verificação de Realidade do Artigo:
Os autores sugerem que ninguém estudou esses tamanhos de caixa específicos não porque fossem muito difíceis ou misteriosos, mas porque não eram tão importantes. É como alegar que você fez uma "descoberta científica" ao encontrar a melhor maneira de empilhar pedregulhos em um formato específico de jardim. É uma questão válida, mas não é uma descoberta fundamental do universo.

Os autores argumentam que, se a IA tivesse realmente descoberto uma verdade matemática profunda, outros pesquisadores teriam sido capazes de ler o código da IA, entender o princípio e usá-lo para resolver outros problemas. Em vez disso, ninguém foi capaz de fazer isso. O "insight" morreu com o código específico que a IA escreveu.

A Conclusão

O artigo conclui que, embora usar IA para ajudar a projetar algoritmos seja uma ideia legal, precisamos ter cuidado com o hype.

A IA não fez uma "descoberta matemática". Ela apenas encontrou uma maneira ligeiramente melhor de realizar uma tarefa simples através de tentativa e erro.
O código da IA não era verdadeiramente "interpretável". Era difícil de entender, e a "lógica" só foi encontrada através de suposições baseadas em experimentos, não pela leitura do código.
Humanos podem fazer melhor. Ao compreender o princípio simples que a IA tropeçou, os humanos criaram uma ferramenta mais simples, rápida e confiável.

A Metáfora Final:
A IA era como um macaco digitando em uma máquina de escrever. Eventualmente, ele digitou uma frase que fazia sentido. O estudo original disse: "Vejam! O macaco descobriu o sentido da vida!" Os autores deste artigo dizem: "Não, o macaco apenas digitou uma frase que funciona para este parágrafo específico. Nós podemos escrever uma frase melhor, explicá-la claramente e aplicá-la a todo o livro sem precisar de um macaco."

O artigo insta os cientistas a serem rigorosos: só porque uma IA produz um resultado que parece inteligente, não significa que ela tenha verdadeiramente compreendido o problema ou feito uma descoberta que mude a forma como pensamos sobre a matemática.

Resumo Técnico: Um Estudo Aprofundado das Contribuições de LLMs para o Problema de Empacotamento de Caixas (Bin Packing)

1. Definição do Problema e Contexto

O artigo investiga a validade das afirmações feitas por Romera-Paredes et al. [2024] relativas à contribuição de Modelos de Linguagem de Grande Escala (LLMs) para a "descoberta matemática" em otimização combinatória. Especificamente, foca-se no Problema de Empacotamento de Caixas Online (OBPP), onde itens de tamanhos variados chegam sequencialmente e devem ser empacotados em caixas de capacidade fixa sem o conhecimento de itens futuros. O objetivo é minimizar o número total de caixas utilizadas.

O estudo examina criticamente a estrutura FunSearch, que utiliza um LLM (Codey) dentro de um algoritmo evolutivo para gerar heurísticas para instâncias estocásticas específicas de OBPP. As instâncias alvo envolvem tamanhos de itens extraídos de distribuições Uniform(20, 100) e Weibull(3.0, 45). Embora Romera-Paredes et al. afirmem que estas heurísticas geradas por LLM representam novas descobertas científicas e são interpretáveis, este artigo argumenta que as instâncias não foram estudadas anteriormente devido à sua relativa simplicidade e que as heurísticas geradas carecem de verdadeira interpretabilidade e generalização.

2. Metodologia

Os autores empregam uma metodologia multifacetada para reavaliar as heurísticas geradas por LLM:

Análise de Código e Avaliação de Interpretabilidade: Os autores analisam manualmente o código-fonte das melhores heurísticas geradas por LLM (denominadas c12 para Uniform e c14 para Weibull, juntamente com a heurística EoH de Liu et al. [2024]). Eles avaliam se a lógica é transparente para especialistas do domínio ou se requer experimentação extensiva para ser compreendida.
Engenharia Reversa Comportamental: Para heurísticas opacas (especificamente a c14), os autores realizam comparações item a item contra estratégias de referência (ex: WorstFit, BestFit) para deduzir as regras de decisão subjacentes. Eles analisam as capacidades remanescentes das caixas e os limiares de decisão para formular uma aproximação legível por humanos do comportamento do algoritmo.
Derivação de Algoritmos Simplificados: Com base na análise comportamental, os autores propõem uma nova classe de heurísticas de dois parâmetros (denominadas ab-FirstFit, ab-BestFit e ab-WorstFit). Estes algoritmos formalizam os padrões observados:
1. Se uma caixa puder acomodar o item de modo que o espaço restante seja $\le a$ (ajuste apertado/ tight fit), aplica-se uma estratégia específica (ex: BestFit).
2. Se o espaço restante for $> b$ (ajuste folgado/ loose fit), aplica-se uma estratégia de referência (ex: FirstFit ou WorstFit).
3. Caso contrário, abre-se uma nova caixa.
Avaliação Empírica: Os ab-Baselines propostos são testados contra as heurísticas geradas por LLM (c12, c14, EoH) e contra as bases padrão (BestFit, FirstFit) através das distribuições originais e de variações adicionais (diferentes parâmetros de Uniform e Weibull). A avaliação mede o número de caixas utilizadas e as capacidades de generalização.

3. Principais Contribuições

Crítica da Interpretabilidade: O artigo demonstra que, embora o código gerado pelo LLM seja sintaticamente legível, ele não é semanticamente interpretável. As heurísticas c14 e EoH contêm operações matemáticas opacas (ex: atualizações de pontuação dependentes de vizinhança, termos exponenciais complexos) que não revelam a lógica subjacente. Compreender o seu comportamento exigiu observação experimental em vez de inspeção de código, contradizendo a afirmação de que oferecem insights "interpretáveis".
Identificação da Simplicidade Subjacente: Os autores mostram que os ganhos de desempenho das heurísticas de LLM dependem de duas condições específicas: (H1) um grande número de itens a serem agendados, e (H2) uma distribuição com um limite inferior positivo nos tamanhos dos itens (impedindo que itens muito pequenos preencham grandes lacunas). Estas condições tornam as instâncias específicas relativamente simples.
Proposta de Heurísticas Superiores e Generalizáveis: Os autores introduzem os ab-Baselines, uma classe de algoritmos simples de dois parâmetros. Estas heurísticas:
- Igualam ou superam ligeiramente as heurísticas geradas por LLM nas suas distribuições de treino.
- São significativamente mais eficientes computacionalmente (exigindo minutos de ajuste vs. milhões de consultas ao LLM).
- Generalizam-se eficazmente para outras parametrizações das distribuições Uniform e Weibull, enquanto as heurísticas de LLM falham em generalizar fora dos seus clusters de treino específicos.
Reavaliação da "Descoberta Matemática": O artigo argumenta que as instâncias estudadas (Uniform(20, 100) e Weibull(3.0, 45)) não tinham sido estudadas anteriormente não porque fossem difíceis, mas porque provavelmente foram consideradas pouco interessantes ou triviais pela comunidade. Os LLMs essencialmente redescobriram padrões de otimização conhecidos (ajuste apertado vs. folgado) através de busca estocástica, em vez de gerarem insights conceituais inovadores.

4. Resultados

Desempenho: Na distribuição Uniform(20, 100), o ab-FirstFit simplificado (com parâmetros $a=5, b=24$ ) supera a heurística de LLM c12 em 0,71% em média e a BestFit em 2,71%. Na distribuição Weibull(3.0, 45), o ab-WorstFit ( $a=1, b=21$ ) supera a c14 em 0,12% e a BestFit em 3,39%.
Generalização: Enquanto as heurísticas de LLM degradam significativamente quando testadas em distribuições com parâmetros diferentes, os ab-Baselines mantêm um desempenho robusto através de várias configurações de Uniform e Weibull.
Eficiência: A derivação e o ajuste dos ab-Baselines foram concluídos em minutos num computador portátil pessoal, contrastando fortemente com os dias de treino e milhões de consultas ao LLM necessários para produzir c12 e c14.
Lacuna de Interpretabilidade: Os autores conseguiram realizar a engenharia reversa da lógica da c14 para uma regra simples (BestFit para ajustes apertados, WorstFit para ajustes folgados, nova caixa caso contrário), provando que a "descoberta" foi uma reparametrização de estratégias existentes e não um novo conceito algorítmico.

5. Significância e Alegações

O artigo conclui com uma avaliação modesta, mas crítica, do papel dos LLMs na descoberta científica:

Refutação da "Descoberta": Os autores afirmam que a estrutura evolutiva baseada em LLM não produziu uma "descoberta matemática" no sentido de fornecer uma nova compreensão teórica ou avanços conceituais. Em vez disso, atuou como um hiper-heurístico poderoso que otimizou parâmetros para uma instância específica, estreita e anteriormente não estudada.
Limitações das Alegações Atuais: A afirmação de que os LLMs podem resolver problemas abertos estabelecidos é considerada insuficientemente sustentada pelo estudo de caso de empacotamento de caixas. A falta de trabalhos anteriores sobre estas distribuições específicas sugere que o problema não era "aberto" devido à dificuldade, mas devido a uma falta de importância percebida.
Direção Futura: O artigo defende protocolos de validação rigorosos. Para que os LLMs recebam crédito por uma genuína contribuição científica, devem ser aplicados a problemas significativos e bem estabelecidos, onde as soluções resultantes demonstrem melhorias sobre a melhor literatura existente e ofereçam insights conceituais transferíveis, em vez de apenas ganhos empíricos em instâncias sintéticas estreitas.
Papel dos LLMs: Os autores posicionam os LLMs como uma ferramenta para estender o espaço de busca de algoritmos genéticos e automatizar o design de heurísticas, mas enfatizam que, neste contexto, funcionam como otimizadores empíricos e não como agentes de insight teórico.