💻 computer science

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

Diese Arbeit stellt die Behauptung in Frage, dass Large Language Models die mathematische Entdeckung im Bereich des Bin-Packing-Problems signifikant vorantreiben, indem sie aufzeigt, dass die von ihnen generierten Heuristiken opak sind und die Probleminstanzen tatsächlich einfach genug sind, um durch effizientere, interpretierbare und generalisierbare Algorithmen gelöst zu werden, wodurch die Notwendigkeit einer rigorosen Validierung von durch LLMs generierten wissenschaftlichen Beiträgen hervorgehoben wird.

Ursprüngliche Autoren: Julien Herrmann, Guillaume Pallez

Veröffentlicht 2026-06-19

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Julien Herrmann, Guillaume Pallez

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie leiten ein riesiges Lagerhaus. Jeden Tag treffen LKWs mit Kartons unterschiedlichster Größen ein, und Sie müssen diese in Versandcontainern (Behälter) verpacken, während sie eintreffen. Sie wissen nicht, wie der nächste Karton aussehen wird; Sie müssen nur eine schnelle Entscheidung treffen: „Lege ich diesen Karton in Behälter A, Behälter B oder öffne ich einen brandneuen Behälter C?“

Das Ziel ist einfach: So wenige Behälter wie möglich zu verwenden. Dies ist ein klassisches Rätsel, bekannt als das Bin Packing Problem (Behälterproblem).

Kürzlich behauptete eine berühmte Studie (von Romera-Paredes et al.), dass Large Language Models (LLMs) – dieselbe KI-Technologie, die Aufsätze und Code schreibt – ein „neues mathematisches Geheimnis“ entdeckt hatten, um dieses Verpackungsrätsel besser zu lösen, als es Menschen könnten. Sie sagten, die KI habe eine clevere neue Regel gefunden, die so klug war, dass sie als „mathematische Entdeckung“ galt.

Dieses Papier von Julien Herrmann und Guillaume Pallez ist wie ein Team von Experten-Detektiven, das kommt, um diesen Anspruch zu untersuchen. Sie setzen ihre Lupen auf und sagen: „Moment mal. Schauen wir uns doch mal an, was die KI eigentlich gemacht hat.“

Hier ist, was sie herausgefunden haben, einfach erklärt:

1. Das „Geheimnis“ der KI war nicht besonders geheim

Die KI erzeugte eine Reihe von Computeranweisungen (eine Heuristik), die die Kartons etwas besser verpackten als die Standardmethoden des Menschen. Die ursprüngliche Studie behauptete, diese Anweisungen seien „interpretierbar“, was bedeutet, dass Menschen die Logik leicht lesen und verstehen könnten.

Der Realitätscheck des Papers:
Die Autoren betrachteten den Code der KI und fanden heraus, dass es war, als würde man ein Rezept in einem seltsamen Dialekt lesen.

Der „c12“-Code: Dies war eine lange Liste von „Wenn dies, dann das“-Regeln. Er war lesbar, aber die Logik war chaotisch. Es war wie ein Koch, der sagt: „Wenn der Topf zwischen 7 und 8 Grad warm ist, füge Salz hinzu. Wenn er zwischen 8 und 9 Grad ist, füge eine Spur weniger hinzu.“ Es funktionierte, aber es erklärte nicht, warum es funktionierte.
Der „c14“-Code: Dieser war noch schlimmer. Es war eine komplexe mathematische Formel, die wie Kauderwelsch aussah. Die Autoren mussten tausende Experimente durchführen, nur um zu erraten, was der Code eigentlich tat. Sie stellten fest, dass der Code zwar in einfachem Englisch (Python) geschrieben war, das Denkprinzip dahinter jedoch verborgen blieb. Es war eine „Black Box“, die eine klare Maske trug.

Die Analogie: Stellen Sie sich vor, die KI gäbe Ihnen einen magischen Kompass, der immer nach Norden zeigt. Die ursprüngliche Studie sagte: „Schauen Sie, der Kompass ist aus Glas, man kann die Nadel sehen! Er ist vollkommen verständlich!“ Die Autoren sagen: „Ja, wir können die Nadel sehen, aber wir haben keine Ahnung, wie der Magnet im Inneren funktioniert. Wir wissen nur, dass er nach Norden zeigt, weil wir ihn eine Million Mal getestet haben.“

2. Die KI hat kein neues Naturgesetz entdeckt

Die ursprüngliche Studie behauptete, die KI habe eine „mathematische Entdeckung“ gemacht. Die Autoren argumentieren, dass dies eine Übertreibung ist.

Der Realitätscheck des Papers:
Die KI wurde in sehr spezifischen, engen Szenarien getestet (wie zum Beispiel bei Kartons, die alle zwischen 20 und 100 Einheiten groß sind). Die Autoren fanden heraus, dass die KI nicht eine neue Art des Denkens erfunden hatte, sondern lediglich eine leicht modifizierte Version eines alten, einfachen Tricks fand.

Sie erkannten, dass das „Geheimrezept“ der KI eigentlich nur aus zwei einfachen Zahlen (Parametern) bestand, die besagten:

„Wenn ein Karton wirklich eng hineinpasst, lege ihn dort hinein.“
„Wenn er nicht eng hineinpasst, lege ihn in einen Behälter, der noch viel Platz übrig hat.“

Die Autoren nahmen diese einfache Idee, entfernten den komplexen KI-Code und bauten einen neuen, super-einfachen Algorithmus (genannt ab-FirstFit oder ab-WorstFit).

Das Ergebnis: Dieser neue, vom Menschen geschaffene Algorithmus war schneller, leichter zu verstehen und funktionierte besser als der komplexe Code der KI. Er funktionierte sogar bei unterschiedlichen Arten von Kartongrößen, während der Code der KI versagte, wenn sich die Regeln leicht änderten.

Die Analogie: Es ist, als hätte die KI einen etwas besseren Weg gefunden, einen Schnürsenkel zu binden, indem sie einen komplexen Knoten mit 15 Schlaufen erfand. Die Autoren sahen sich das an und stellten fest: „Du musst eigentlich nur die Schnürsenkel fester ziehen und ein wenig Spiel lassen“, und zeigten, dass ein einfacher Doppelknoten besser funktioniert, leichter zu lernen ist und keinen PhD in Knotentheorie erfordert.

3. Die „Entdeckung“ war nur ein Mangel an vorangegangener Forschung

Die ursprüngliche Studie behauptete, sie hätten etwas „Neues“ gefunden, weil zuvor niemand eine Arbeit über diese spezifischen Kartongrößen veröffentlicht hatte.

Der Realitätscheck des Papers:
Die Autoren legen nahe, dass niemand diese spezifischen Kartongrößen untersucht hatte, nicht weil sie zu schwierig oder mysteriös waren, sondern weil sie nicht besonders wichtig waren. Es ist, als würde man behaupten, man habe einen „wissenschaftlichen Durchbruch“ erzielt, indem man den besten Weg fand, Kieselsteine in einer bestimmten Gartenform aufzustapeln. Das ist eine gültige Frage, aber es ist keine fundamentale Entdeckung des Universums.

Die Autoren argumentieren, dass, wenn die KI wirklich eine tiefe mathematische Wahrheit entdeckt hätte, andere Forscher in der Lage gewesen wären, den Code der KI zu lesen, das Prinzip zu verstehen und es zur Lösung anderer Probleme zu verwenden. Stattdessen war niemand in der Lage, dies zu tun. Die „Einsicht“ starb mit dem spezifischen Code, den die KI schrieb.

Das Fazit

Das Paper kommt zu dem Schluss, dass es zwar eine coole Idee ist, KI zur Unterstützung beim Design von Algorithmen einzusetzen, wir aber vorsichtig mit dem Hype sein müssen.

Die KI hat keine „mathematische Entdeckung“ gemacht. Sie hat lediglich durch Ausprobieren einen etwas besseren Weg für eine einfache Aufgabe gefunden.
Der Code der KI war nicht wirklich „interpretierbar“. Er war schwer zu verstehen, und die „Logik“ wurde nur durch Experimente erraten, nicht durch das Lesen des Codes.
Menschen können es besser machen. Indem sie das einfache Prinzip verstanden, das die KI eher zufällig gestreift hatte, schufen Menschen ein einfacheres, schnelleres und zuverlässigeres Werkzeug.

Die abschließende Metapher:
Die KI war wie ein Affe, der auf einer Schreibmaschine tippt. Irgendwann tippte er einen Satz, der Sinn ergab. Die ursprüngliche Studie sagte: „Seht her! Der Affe hat den Sinn des Lebens entdeckt!“ Die Autoren dieses Papers sagen: „Nein, der Affe hat nur einen Satz getippt, der für diesen speziellen Absatz funktioniert. Wir können einen besseren Satz schreiben, ihn klar erklären und ihn auf das ganze Buch anwenden, ohne einen Affen zu benötigen.“

Das Paper fordert Wissenschaftler dazu auf, rigoros zu sein: Nur weil eine KI ein Ergebnis liefert, das intelligent aussieht, bedeutet das nicht, dass sie das Problem wirklich verstanden oder eine Entdeckung gemacht hat, die unser Denken über die Mathematik verändert.

Technische Zusammenfassung: Eine eingehende Untersuchung der Beiträge von LLMs zum Bin-Packing-Problem

1. Problemdefinition und Kontext

Die vorliegende Arbeit untersucht die Validität der Behauptungen von Romera-Paredes et al. [2024] bezüglich der Fähigkeit von Large Language Models (LLMs), zu „mathematischer Entdeckung“ im Bereich der kombinatorischen Optimierung beizutragen. Konkret konzentriert sie sich auf das Online Bin Packing Problem (OBPP), bei dem Objekte unterschiedlicher Größe sequenziell eintreffen und in Behälter (Bins) fester Kapazität verpackt werden müssen, ohne dass Wissen über zukünftige Objekte vorliegt. Das Ziel ist es, die Gesamtzahl der verwendeten Behälter zu minimieren.

Die Studie hinterfragt das FunSearch-Framework, welches ein LLM (Codey) innerhalb eines evolutionären Algorithmus verwendet, um Heuristiken für spezifische stochastische Instanzen des OBPP zu generieren. Die Zielinstanzen beinhalten Objektgrößen, die aus Uniform(20, 100)- und Weibull(3.0, 45)-Verteilungen gezogen werden. Während Romera-Paredes et al. behaupten, dass diese LLM-generierten Heuristiken neue wissenschaftliche Entdeckungen darstellen und interpretierbar sind, argumentiert dieses Paper, dass die Instanzen aufgrund ihrer relativen Einfachheit zuvor ununtersucht blieben und die generierten Heuristiken keine echte Interpretierbarkeit und Verallgemeinerbarkeit besitzen.

2. Methodik

Die Autoren wenden eine facettenreiche Methodik an, um die LLM-generierten Heuristiken neu zu bewerten:

Code-Analyse und Bewertung der Interpretierbarkeit: Die Autoren analysieren manuell den Quellcode der leistungsfähigsten LLM-generierten Heuristiken (bezeichnet als c12 für Uniform und c14 für Weibull, sowie die EoH-Heuristik von Liu et al. [2024]). Sie bewerten, ob die Logik für Domänenexperten transparent ist oder ob sie umfangreiche Experimente erfordert, um verstanden zu werden.
Verhaltens-Reverse-Engineering: Für opake Heuristiken (speziell c14) führen die Autoren einen objektweise Vergleich gegen Baseline-Strategien (z. B. WorstFit, BestFit) durch, um die zugrunde liegenden Entscheidungsregeln abzuleiten. Sie analysieren die verbleibenden Behälterkapazitäten und Entscheidungsschwellen, um eine menschenlesbare Annäherung an das Verhalten des Algorithmus zu formulieren.
Ableitung vereinfachter Algorithmen: Basierend auf der Verhaltensanalyse schlagen die Autoren eine neue Klasse von Zwei-Parameter-Heuristiken vor (bezeichnet als ab-FirstFit, ab-BestFit und ab-WorstFit). Diese Algorithmen formalisieren die beobachteten Muster:
1. Wenn ein Behälter das Objekt so aufnehmen kann, dass der verbleibende Platz $\le a$ ist (Tight Fit), wird eine spezifische Strategie angewendet (z. B. BestFit).
2. Wenn der verbleibende Platz $> b$ ist (Loose Fit), wird eine Baseline-Strategie angewendet (z. B. FirstFit oder WorstFit).
3. Andernfalls wird ein neuer Behälter geöffnet.
Empirische Evaluierung: Die vorgeschlagenen ab-Baselines werden gegen die LLM-generierten Heuristiken (c12, c14, EoH) und Standard-Baselines (BestFit, FirstFit) über die ursprünglichen Verteilungen und zusätzliche Variationen (andere Uniform- und Weibull-Parameter) hinweg benchmarked. Die Evaluierung misst die Anzahl der verwendeten Behälter und die Generalisierungsfähigkeit.

3. Zentrale Beiträge

Kritik der Interpretierbarkeit: Das Paper zeigt, dass der LLM-generierte Code zwar syntaktisch lesbar, aber nicht semantisch interpretierbar ist. Die Heuristiken c14 und EoH enthalten opake mathematische Operationen (z. B. nachbarschaftsabhängige Score-Updates, komplexe exponentielle Terme), die die zugrunde liegende Logik nicht offenlegen. Das Verständnis ihres Verhaltens erforderte experimentelle Beobachtung statt Code-Inspektion, was der Behauptung widerspricht, sie böten „interpretierbare“ Einblicke.
Identifizierung der zugrunde liegenden Einfachheit: Die Autoren zeigen, dass die Leistungssteigerungen der LLM-Heuristiken auf zwei spezifischen Bedingungen beruhen: (H1) eine große Anzahl von zu planenden Objekten und (H2) eine Verteilung mit einer positiven unteren Grenze der Objektgrößen (was verhindert, dass sehr kleine Objekte große Lücken füllen). Diese Bedingungen machen die spezifischen Instanzen relativ einfach.
Vorschlag überlegener, generalisierbarer Heuristiken: Die Autoren führen ab-Baselines ein, eine Klasse einfacher Zwei-Parameter-Algorithmen. Diese Heuristiken:
- Erreichen das Niveau oder übertreffen die LLM-generierten Heuristiken auf deren Trainingsverteilungen leicht.
- Sind signifikant recheneffizienter (Minuten der Feinabstimmung vs. Millionen von LLM-Abfragen).
- Generalisieren effektiv auf andere Parametrisierungen von Uniform- und Weibull-Verteilungen, während LLM-Heuristiken außerhalb ihrer spezifischen Trainingscluster versagen.
Neubewertung der „Mathematischen Entdeckung“: Das Paper argumentiert, dass die untersuchten Instanzen (Uniform(20, 100) und Weibull(3.0, 45)) nicht deshalb zuvor nicht untersucht wurden, weil sie schwierig waren, sondern weil sie von der Fachwelt wahrscheinlich als uninteressant oder trivial angesehen wurden. Die LLMs haben im Wesentlichen bekannte Optimierungsmuster (Tight vs. Loose Fitting) durch stochastische Suche wiederentdeckt, anstatt neue konzeptionelle Erkenntnisse zu generieren.

4. Ergebnisse

Leistung: Auf der Uniform(20, 100)-Verteilung übertrifft die vereinfachte ab-FirstFit (mit den Parametern $a=5, b=24$ ) die LLM-Heuristik c12 im Durchschnitt um 0,71 % und BestFit um 2,71 %. Auf der Weibull(3.0, 45)-Verteilung übertrifft ab-WorstFit ( $a=1, b=21$ ) c14 um 0,12 % und BestFit um 3,39 %.
Generalisierung: Während LLM-Heuristiken bei Tests auf Verteilungen mit anderen Parametern signifikant an Leistung verlieren, behalten die ab-Baselines eine robuste Performance über verschiedene Uniform- und Weibull-Konfigurationen hinweg bei.
Effizienz: Die Ableitung und Feinabstimmung der ab-Baselines wurde in Minuten auf einem persönlichen Laptop abgeschlossen, was in starkem Kontrast zu den Tagen des Trainings und den Millionen von LLM-Abfragen steht, die zur Erzeugung von c12 und c14 erforderlich waren.
Interpretierbarkeitslücke: Den Autoren gelang es, die Logik von c14 erfolgreich in eine einfache Regel zu dekonstruieren (BestFit für Tight Fits, WorstFit für Loose Fits, andernfalls neuer Behälter), was beweist, dass die „Entdeckung“ eine Reparametrisierung bestehender Strategien war und kein neues algorithmisches Konzept.

5. Bedeutung und Behauptungen

Das Paper schließt mit einer bescheidenen, aber kritischen Neubewertung der Rolle von LLMs in der wissenschaftlichen Entdeckung:

Widerlegung der „Entdeckung“: Die Autoren behaupten, dass der LLM-basierte evolutionäre Rahmen keine „mathematische Entdeckung“ im Sinne einer neuen theoretischen Verständniss oder konzeptionellen Durchbrüche geliefert hat. Stattdessen fungierte er als leistungsfähiger Hyper-Heuristik-Optimierer für die Parameter einer spezifischen, engen und zuvor ununtersuchten Instanz.
Limitierungen aktueller Behauptungen: Die Behauptung, LLMs könnten etablierte offene Probleme lösen, wird durch die Fallstudie zum Bin Packing als unzureichend fundiert eingestuft. Das Fehlen früherer Arbeiten zu diesen spezifischen Verteilungen deutet darauf hin, dass das Problem nicht aufgrund seiner Schwierigkeit „offen“ war, sondern aufgrund mangelnder wahrgenommener Relevanz.
Zukünftige Ausrichtung: Das Paper plädiert für rigorose Validierungsprotokolle. Damit LLMs als echte wissenschaftliche Beiträge anerkannt werden können, müssen sie auf signifikanten, gut etablierten Problemen angewendet werden, bei denen die resultierenden Lösungen Verbesserungen gegenüber der besten bestehenden Literatur zeigen und transferierbare konzeptionelle Erkenntnisse bieten, anstatt nur empirische Gewinne auf engen, synthetischen Instanzen zu erzielen.
Rolle der LLMs: Die Autoren positionieren LLMs als Werkzeuge zur Erweiterung des Suchraums genetischer Algorithmen und zur Automatisierung des Heuristik-Designs, betonen jedoch, dass sie in diesem Kontext eher als empirische Optimierer denn als Agenten theoretischer Einsicht fungieren.