💻 computer science

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

Cet article conteste l'affirmation selon laquelle les grands modèles de langage font progresser de manière significative la découverte mathématique dans le problème du bin packing en démontrant que les heuristiques qu'ils génèrent sont opaques et que les instances du problème sont en réalité suffisamment simples pour être résolues par des algorithmes plus efficaces, interprétables et généralisables, mettant ainsi en évidence la nécessité d'une validation rigoureuse des contributions scientifiques générées par les LLM.

Auteurs originaux : Julien Herrmann, Guillaume Pallez

Publié 2026-06-19

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Julien Herrmann, Guillaume Pallez

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous dirigez un entrepôt massif. Chaque jour, des camions arrivent avec des boîtes de toutes tailles différentes, et vous devez les ranger dans des conteneurs d'expédition (des bacs) au fur et à mesure qu'elles arrivent. Vous ne savez pas à quoi ressemblera la prochaine boîte ; vous devez simplement prendre une décision rapide : « Est-ce que je mets cette boîte dans le Conteneur A, le Conteneur B ou est-ce que j'ouvre un tout nouveau Conteneur C ? »

L'objectif est simple : utiliser le moins de conteneurs possible. C'est un casse-tête classique connu sous le nom de Problème de mise en boîte (Bin Packing Problem).

Récemment, une étude célèbre (par Romera-Paredes et al.) a affirmé que les Grands Modèles de Langage (LLM) — la même technologie d'IA qui écrit des essais et du code — avaient découvert un « nouveau secret mathématique » pour résoudre ce casse-tête de rangement mieux que les humains ne le pourraient. Ils ont dit que l'IA avait trouvé une nouvelle règle astucieuse qui était si intelligente qu'elle comptait comme une « découverte mathématique ».

Ce papier de Julien Herrmann et Guillaume Pallez est comme une équipe de détectives experts venant enquêter sur cette affirmation. Ils ont sorti leurs loupes et disent : « Attendez une minute. Regardons ce que l'IA a réellement fait. »

Voici ce qu'ils ont trouvé, expliqué simplement :

1. Le « secret » de l'IA n'était pas très secret

L'IA a produit un ensemble d'instructions informatiques (une heuristique) qui rangeait les boîtes légèrement mieux que les méthodes humaines standards. L'étude originale affirmait que ces instructions étaient « interprétables », ce qui signifie que les humains pouvaient facilement lire et comprendre la logique.

La réalité du papier :
Les auteurs ont examiné le code de l'IA et ont constaté que c'était comme lire une recette écrite dans un dialecte étrange.

Le code « c12 » : C'était une longue liste de règles de type « Si ceci, alors cela ». C'était lisible, mais la logique était désordonnée. C'était comme un chef qui dirait : « Si la marmite est entre 7 et 8 degrés, ajoutez du sel. Si elle est entre 8 et 9, ajoutez une pincée de moins. » Cela fonctionnait, mais cela n'expliquait pas pourquoi cela fonctionnait.
Le code « c14 » : Celui-ci était encore pire. C'était une formule mathématique complexe qui ressemblait à du charabia. Les auteurs ont dû mener des milliers d'expériences juste pour deviner ce que le code faisait réellement. Ils ont réalisé que même si le code était écrit en langage clair (Python), le raisonnement derrière était caché. C'était une « boîte noire » portant un masque transparent.

L'analogie : Imaginez que l'IA vous donne une boussole magique qui pointe toujours le Nord. L'étude originale dit : « Regardez, la boussole est en verre, donc on peut voir l'aiguille ! Elle est totalement compréhensible ! » Les auteurs disent : « Oui, nous pouvons voir l'aiguille, mais nous n'avons aucune idée de la façon dont l'aimant à l'intérieur fonctionne. Nous savons juste qu'elle pointe le Nord parce que nous l'avons testée un million de fois. »

2. L'IA n'a pas découvert une nouvelle loi de la physique

L'étude originale affirmait que l'IA avait fait une « découverte mathématique ». Les auteurs soutiennent que c'est exagéré.

La réalité du papier :
L'IA a été testée sur des scénarios très spécifiques et étroits (comme des boîtes dont la taille est comprise entre 20 et 100 unités). Les auteurs ont trouvé que l'IA n'avait pas inventé une nouvelle façon de penser ; elle avait simplement trouvé une version légèrement modifiée d'une vieille astuce simple.

Ils ont réalisé que la « recette secrète » de l'IA n'était en fait que deux nombres simples (paramètres) qui disaient :

« Si une boîte s'ajuste très étroitement, mets-la là. »
« Si elle ne s'ajuste pas étroitement, mets-la dans un conteneur qui a beaucoup d'espace restant. »

Les auteurs ont pris cette idée simple, ont dépouillé le code complexe de l'IA, et ont construit un nouvel algorithme humain très simple (appelé ab-FirstFit ou ab-WorstFit).

Le résultat : Cet algorithme créé par l'homme était plus rapide, plus facile à comprendre et fonctionnait mieux que le code complexe de l'IA. Il fonctionnait même sur différents types de tailles de boîtes, alors que le code de l'IA se brisait lorsque les règles changeaient légèrement.

L'analogie : C'est comme si l'IA avait trouvé une meilleure façon de nouer une chaussure en inventant un nœud complexe de 15 boucles. Les auteurs ont regardé cela et ont réalisé : « Oh, vous avez juste besoin de tirer les lacets plus fort et de laisser un peu de mou, » et ils ont montré qu'un simple double nœud fonctionne mieux, est plus facile à apprendre et ne nécessite pas un doctorat en théorie des nœuds.

3. La « découverte » n'était qu'un manque de recherche préalable

L'étude originale affirmait qu'ils avaient trouvé quelque chose de « nouveau » parce que personne n'avait publié de papier sur ces tailles de boîtes spécifiques auparavant.

La réalité du papier :
Les auteurs suggèrent que personne n'avait étudié ces tailles de boîtes spécifiques non pas parce qu'elles étaient trop difficiles ou mystérieuses, mais parce qu'elles n'étaient pas si importantes. C'est comme prétendre que vous avez fait une « percée scientifique » en trouvant la meilleure façon d'empiler des cailloux dans une forme de jardin spécifique. C'est une question valable, mais ce n'est pas une découverte fondamentale de l'univers.

Les auteurs soutiennent que si l'IA avait véritablement découvert une vérité mathématique profonde, d'autres chercheurs auraient été capables de lire le code de l'IA, d'en comprendre le principe et de l'utiliser pour résoudre d'autres problèmes. Au lieu de cela, personne n'a été capable de le faire. L'« intuition » est morte avec le code spécifique écrit par l'IA.

Le mot de la fin

Le papier conclut que, bien que l'utilisation de l'IA pour aider à concevoir des algorithmes soit une idée intéressante, nous devons être prudents face au battage médiatique.

L'IA n'a pas fait de « découverte mathématique ». Elle a juste trouvé une meilleure façon de réaliser une tâche simple par essais et erreurs.
Le code de l'IA n'était pas vraiment « interprétable ». Il était difficile à comprendre, et la « logique » n'a été trouvée qu'en devinant par des expériences, et non en lisant le code.
Les humains peuvent faire mieux. En comprenant le principe simple sur lequel l'IA est tombée par hasard, les humains ont créé un outil plus simple, plus rapide et plus fiable.

La métaphore finale :
L'IA était comme un singe tapant sur une machine à écrire. Finalement, il a tapé une phrase qui a du sens. L'étude originale dit : « Regardez ! Le singe a découvert le sens de la vie ! » Les auteurs de ce papier disent : « Non, le singe vient juste de taper une phrase qui fonctionne pour ce paragraphe spécifique. Nous pouvons écrire une meilleure phrase, l'expliquer clairement et l'appliquer à tout le livre sans avoir besoin d'un singe. »

Le papier exhorte les scientifiques à être rigoureux : ce n'est pas parce qu'une IA produit un résultat qui semble intelligent qu'elle a réellement compris le problème ou qu'elle a fait une découverte qui change notre façon de concevoir les mathématiques.

Résumé Technique : Une étude approfondie des contributions des LLM au problème de la mise en boîte (Bin Packing)

1. Définition du problème et contexte

L'article examine la validité des affirmations de Romera-Paredes et al. [2024] concernant la contribution des modèles de langage étendus (LLM) à la « découverte mathématique » dans l'optimisation combinatoire. Il se concentre spécifiquement sur le problème de la mise en boîte en ligne (Online Bin Packing Problem - OBPP), où des objets de tailles variables arrivent séquentiellement et doivent être emballés dans des bacs de capacité fixe sans connaissance des objets futurs. L'objectif est de minimiser le nombre total de bacs utilisés.

L'étude scrute le cadre FunSearch, qui utilise un LLM (Codey) au sein d'un algorithme évolutionnaire pour générer des heuristiques pour des instances stochastiques spécifiques de l'OBPP. Les instances cibles impliquent des tailles d'objets tirées des distributions Uniforme(20, 100) et Weibull(3.0, 45). Alors que Romera-Paredes et al. affirment que ces heuristiques générées par LLM représentent de nouvelles découvertes scientifiques et sont interprétables, cet article soutient que les instances n'avaient pas été étudiées auparavant en raison de leur simplicité relative et que les heuristiques générées manquent de véritable interprétabilité et de généralisabilité.

2. Méthodologie

Les auteurs emploient une méthodologie multidimensionnelle pour réévaluer les heuristiques générées par LLM :

Analyse de code et évaluation de l'interprétabilité : Les auteurs analysent manuellement le code source des meilleures heuristiques générées par LLM (notées c12 pour l'Uniforme et c14 pour la Weibull, ainsi que l'heuristique EoH de Liu et al. [2024]). Ils évaluent si la logique est transparente pour les experts du domaine ou si elle nécessite une expérimentation extensive pour être comprise.
Rétro-ingénierie comportementale : Pour les heuristiques opaques (spécifiquement c14), les auteurs effectuent des comparaisons objet par objet par rapport aux stratégies de référence (ex: WorstFit, BestFit) afin de déduire les règles de décision sous-jacentes. Ils analysent les capacités restantes des bacs et les seuils de décision pour formuler une approximation lisible par l'humain du comportement de l'algorithme.
Dérivation d'algorithmes simplifiés : Sur la base de l'analyse comportementale, les auteurs proposent une nouvelle classe d'heuristiques à deux paramètres (notées ab-FirstFit, ab-BestFit et ab-WorstFit). Ces algorithmes formalisent les schémas observés :
1. Si un bac peut contenir l'objet de telle sorte que l'espace restant est $\le a$ (ajustement serré), appliquer une stratégie spécifique (ex: BestFit).
2. Si l'espace restant est $> b$ (ajustement lâche), appliquer une stratégie de référence (ex: FirstFit ou WorstFit).
3. Sinon, ouvrir un nouveau bac.
Évaluation empirique : Les ab-Baselines proposées sont comparées aux heuristiques générées par LLM (c12, c14, EoH) et aux références standards (BestFit, FirstFit) à travers les distributions originales et des variations supplémentaires (différents paramètres Uniforme et Weibull). L'évaluation mesure le nombre de bacs utilisés et les capacités de généralisation.

3. Contributions clés

Critique de l'interprétabilité : L'article démontre que bien que le code généré par LLM soit syntaxiquement lisible, il n'est pas sémantiquement interprétable. Les heuristiques c14 et EoH contiennent des opérations mathématiques opaques (ex: mises à jour de scores dépendantes du voisinage, termes exponentiels complexes) qui ne révèlent pas la logique sous-jacente. Comprendre leur comportement a nécessité une observation expérimentale plutôt qu'une inspection du code, contredisant l'affirmation selon laquelle elles offrent des informations « interprétables ».
Identification de la simplicité sous-jacente : Les auteurs montrent que les gains de performance des heuristiques de LLM reposent sur deux conditions spécifiques : (H1) un grand nombre d'objets à planifier, et (H2) une distribution avec une borne inférieure positive sur les tailles d'objets (empêchant les très petits objets de combler les grands espaces). Ces conditions rendent les instances spécifiques relativement simples.
Proposition d'heuristiques supérieures et généralisables : Les auteurs introduisent les ab-Baselines, une classe d'algorithmes simples à deux paramètres. Ces heuristiques :
- Égalent ou surpassent légèrement les heuristiques générées par LLM sur leurs distributions d'entraînement.
- Sont nettement plus efficaces sur le plan computationnel (nécessitant des minutes de réglage contre des millions de requêtes LLM).
- Se généralisent efficacement à d'autres paramétrages des distributions Uniforme et Weibull, là où les heuristiques de LLM échouent à se généraliser en dehors de leurs clusters d'entraînement spécifiques.
Réévaluation de la « découverte mathématique » : L'article soutient que les instances étudiées (Uniforme(20, 100) et Weibull(3.0, 45)) n'avaient pas été étudiées auparavant non pas parce qu'elles étaient difficiles, mais parce qu'elles étaient probablement jugées peu intéressantes ou triviales par la communauté. Les LLM ont essentiellement redécouvert des schémas d'optimisation connus (ajustement serré vs lâche) via une recherche stochastique plutôt que de générer des idées conceptuelles novatrices.

4. Résultats

Performance : Sur la distribution Uniforme(20, 100), la version simplifiée ab-FirstFit (avec les paramètres $a=5, b=24$ ) surpasse l'heuristique LLM c12 de 0,71 % en moyenne et BestFit de 2,71 %. Sur la distribution Weibull(3.0, 45), ab-WorstFit ( $a=1, b=21$ ) surpasse c14 de 0,12 % et BestFit de 3,39 %.
Généralisation : Alors que les heuristiques de LLM se dégradent considérablement lorsqu'elles sont testées sur des distributions aux paramètres différents, les ab-Baselines maintiennent une performance robuste à travers diverses configurations Uniforme et Weibull.
Efficacité : La dérivation et le réglage des ab-Baselines ont été achevés en quelques minutes sur un ordinateur portable personnel, contrastant fortement avec les jours d'entraînement et les millions de requêtes LLM nécessaires pour produire c12 et c14.
Écart d'interprétabilité : Les auteurs ont réussi à rétro-concevoir la logique de c14 en une règle simple (BestFit pour les ajustements serrés, WorstFit pour les ajustements lâches, sinon un nouveau bac), prounant que la « découverte » était un reparamétrage de stratégies existantes plutôt qu'un nouveau concept algorithmique.

5. Signification et affirmations

L'article conclut par une réévaluation modeste mais critique du rôle des LLM dans la découverte scientifique :

Réfutation de la « découverte » : Les auteurs affirment que le cadre évolutionnaire basé sur le LLM n'a pas produit de « découverte mathématique » au sens de fourniture d'une nouvelle compréhension théorique ou de percées conceptuelles. Au lieu de cela, il a agi comme un hyper-heuristique puissant qui a optimisé les paramètres pour une instance spécifique, étroite et auparavant non étudiée.
Limites des affirmations actuelles : L'affirmation selon laquelle les LLM peuvent résoudre des problèmes ouverts établis est jugée insuffisamment étayée par l'étude de cas du bin packing. L'absence de travaux antérieurs sur ces distributions spécifiques suggère que le problème n'était pas « ouvert » en raison de sa difficulté, mais en raison d'un manque d'intérêt perçu.
Direction future : L'article préconise des protocoles de validation rigoureux. Pour que les LLM puissent être crédités d'une véritable contribution scientifique, ils doivent être appliqués à des problèmes significatifs et bien établis où les solutions résultantes démontrent des améliorations par rapport à la meilleure littérature existante et offrent des idées conceptuelles transférables, plutôt que de simples gains empiriques sur des instances synthétiques étroites.
Rôle des LLM : Les auteurs positionnent les LLM comme un outil pour étendre l'espace de recherche des algorithmes génétiques et automatiser la conception d'heuristiques, mais soulignent que, dans ce contexte, ils fonctionnent comme des optimiseurs empiriques plutôt que comme des agents d'intuition théorique.