💻 computer science

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

Dit artikel daagt de bewering uit dat grote taalmodellen de wiskundige ontdekking binnen het bin packing-probleem significant vooruithelpen door aan te tonen dat de door hen gegenereerde heuristieken opaak zijn en dat de probleeminstanties in werkelijkheid eenvoudig genoeg zijn om te worden opgelost door efficiëntere, interpreteerbare en generaliseerbare algoritmen, waardoor de noodzaak voor rigoureuze validatie van door LLM's gegenereerde wetenschappelijke bijdragen wordt benadrukt.

Oorspronkelijke auteurs: Julien Herrmann, Guillaume Pallez

Gepubliceerd 2026-06-19

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Julien Herrmann, Guillaume Pallez

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorm magazijn runt. Elke dag komen er vrachtwagens aan met dozen van allerlei verschillende maten, en je moet ze in verzendcontainers (bakken) verpakken terwijl ze binnenkomen. Je weet niet hoe de volgende doos eruit zal zien; je moet gewoon snel een beslissing nemen: "Zet ik deze doos in Container A, Container B, of open ik een gloednieuwe Container C?"

Het doel is simpel: zo min mogelijk containers gebruiken. Dit is een klassieke puzzel die bekend staat als het Bin Packing Problem (het pakprobleem).

Onlangs beweerde een beroemde studie (door Romera-Paredes et al.) dat Large Language Models (LLM's) — dezelfde AI-technologie die essays en code schrijft — een "nieuw wiskundig geheim" hadden ontdekt om deze pakpuzzel beter op te lossen dan mensen dat kunnen. Ze zeiden dat de AI een slimme nieuwe regel had gevonden die zo vernuftig was, dat het telt als een "wiskundige ontdekking."

Dit artikel van Julien Herrmann en Guillaume Pallez is als een team van deskundige detectives dat komt om die bewering te onderzoeken. Ze zetten hun vergrootglazen op en zeggen: "Wacht eens even. Laten we eens kijken wat de AI eigenlijk heeft gedaan."

Hier is wat zij vonden, eenvoudig uitgelegd:

1. Het "geheim" van de AI was niet erg geheim

De AI produceerde een reeks computerinstructies (een heuristiek) die de dozen iets beter verpakte dan de standaard menselijke methoden. De oorspronkelijke studie beweerde dat deze instructies "interpreteerbaar" waren, wat betekent dat mensen de logica gemakkelijk konden lezen en begrijpen.

De Reality Check van het artikel:
De auteurs bekeken de code van de AI en vonden dat het leek alsof je een recept las dat geschreven is in een vreemd dialect.

De "c12"-code: Dit was een lange lijst met "Als dit, dan dat"-regels. Het was leesbaar, maar de logica was slordig. Het was alsof een chef zegt: "Als de pan tussen de 7 en 8 graden is, voeg dan zout toe. Als hij tussen de 8 en 9 graden is, voeg dan een snufje minder toe." Het werkte, maar het legde niet uit waarom het werkte.
De "c14"-code: Deze was nog erger. Het was een complexe wiskundige formule die op wartaal leek. De auteurs moesten duizenden experimenten uitvoeren om te raden wat de code eigenlijk deed. Ze realiseerden zich dat hoewel de code in gewone Engelse taal (Python) was geschreven, de redenering erachter verborgen bleef. Het was een "black box" met een helder masker op.

De analogie: Stel je voor dat de AI je een magisch kompas gaf dat altijd naar het Noorden wijst. De oorspronkelijke studie zei: "Kijk, het kompas is gemaakt van glas, dus je kunt de naald zien! Het is volledig begrijpelijk!" De auteurs zeggen: "Ja, we kunnen de naald zien, maar we hebben geen idee hoe de magneet binnenin werkt. We weten alleen dat hij naar het Noorden wijst omdat we hem een miljoen keer hebben getest."

2. De AI heeft geen nieuwe natuurwet ontdekt

De oorspronkelijke studie beweerde dat de AI een "wiskundige ontdekking" had gedaan. De auteurs vinden dat een flinke overdrijving.

De Reality Check van het artikel:
De AI werd getest op zeer specifieke, nauwe scenario's (zoals dozen die allemaal tussen de 20 en 100 eenheden groot zijn). De auteurs ontdekten dat de AI niet een nieuwe manier van denken had uitgevonden, maar slechts een licht aangepaste versie van een oude, simpele truc had gevonden.

Ze realiseerden zich dat het "geheime recept" van de AI eigenlijk uit slechts twee eenvoudige getallen (parameters) bestond die zeiden:

"Als een doos heel strak past, zet hem daar dan."
"Als hij niet strak past, zet hem in een container waar nog veel ruimte over is."

De auteurs namen dit simpele idee, haalden de complexe AI-code weg en bouwden een nieuw, super-eenvoudig algoritme (genaamd ab-FirstFit of ab-WorstFit).

Het resultaat: Dit nieuwe, door mensen gemaakte algoritme was sneller, makkelijker te begrijpen en werkte beter dan de complexe code van de AI. Het werkte zelfs op verschillende soorten doosmaten, terwijl de code van de AI kapotging wanneer de regels licht veranderden.

De analogie: Het is alsof de AI een iets betere manier heeft gevonden om een veters te strikken door een complex knoopje te verzinnen met 15 lussen. De auteurs keken ernaar en zeiden: "Je moet gewoon de veters strakker trekken en een beetje speling laten," en lieten zien dat een simpele dubbele knoop beter werkt, makkelijker te leren is en geen PhD in de knopentheorie vereist.

3. De "ontdekking" was slechts een gebrek aan voorafgaand onderzoek

De oorspronkelijke studie beweerde dat ze iets "nieuws" hadden gevonden omdat niemand eerder een paper had gepubliceerd over deze specifieke doosmaten.

De Reality Check van het artikel:
De auteurs suggereren dat niemand deze specifieke doosmaten had bestudeerd, niet omdat ze te moeilijk of mysterieus waren, maar omdat ze niet zo belangrijk waren. Het is alsof je beweert dat je een "wetenschappelijke doorbraak" hebt geboekt door de beste manier te vinden om kiezelstenen in een specifieke vorm te stapelen. Dat is een geldige vraag, maar het is geen fundamentele ontdekking van het universum.

De auteurs stellen dat als de AI echt een diepe wiskundige waarheid had ontdekt, andere onderzoekers de code van de AI hadden kunnen lezen, het principe hadden kunnen begrijpen en het voor andere problemen hadden kunnen gebruiken. In plaats daarvan is de "inzicht" gestorven met de specifieke code die de AI schreef.

De Kernboodschap

Het artikel concludeert dat, hoewel het gebruik van AI om helpen bij het ontwerpen van algoritmen een cool idee is, we voorzichtig moeten zijn met de hype.

De AI heeft geen "wiskundige ontdekking" gedaan. Het heeft slechts een iets betere manier gevonden om een simpele taak uit te voeren door middel van trial-and-error.
De code van de AI was niet echt "interpreteerbaar". Het was moeilijk te begrijpen, en de "logica" werd alleen gevonden door te gissen via experimenten, niet door de code te lezen.
Mensen kunnen het beter. Door het simpele principe te begrijpen dat de AI per ongeluk had gevonden, hebben mensen een eenvoudiger, sneller en betrouwbaarder hulpmiddel gecreëerd.

De definitieve metafoor:
De AI was als een aap die op een typemachine typt. Uiteindelijk typte het een zin die zin gaf. De oorspronkelijke studie zei: "Kijk! De aap heeft de betekenis van het leven ontdekt!" De auteurs van dit artikel zeggen: "Nee, de aap heeft gewoon een zin getypt die werkt voor deze specifieke paragraaf. Wij kunnen een betere zin schrijven, deze duidelijk uitleggen en deze toepassen op het hele boek zonder dat we een aap nodig hebben."

Het artikel dringt er bij wetenschappers op aan om rigoureus te zijn: alleen omdat een AI een resultaat produceert dat slim lijkt, betekent het niet dat het echt het probleem heeft begrepen of een ontdekking heeft gedaan die onze manier van denken over wiskunde verandert.

Technische Samenvatting: Een diepgaande studie naar de bijdragen van LLM's aan het Bin Packing Probleem

1. Probleemdefinitie en Context

Het artikel onderzoekt de geldigheid van de claims van Romera-Paredes et al. [2024] met betrekking tot de bijdrage van Large Language Models (LLM's) aan "wiskundige ontdekking" in combinatorische optimalisatie. Specifiek richt het zich op het Online Bin Packing Problem (OBPP), waarbij items van variërende grootte sequentieel arriveren en in bakken (bins) met een vaste capaciteit moeten worden verpakt zonder kennis van toekomstige items. Het doel is om het totaal aantal gebruikte bakken te minimaliseren.

De studie onderzoekt het FunSearch-framework, dat een LLM (Codey) gebruikt binnen een evolutionair algoritme om heuristieken te generen voor specifieke stochastische instanties van OBPP. De doelinstanties betreffen itemgroottes getrokken uit de Uniform(20, 100) en Weibull(3.0, 45) distributies. Terwijl Romera-Paredes et al. beweren dat deze door LLM gegenereerde heuristieken nieuwe wetenschappelijke ontdekkingen vertegenwoordigen en interpreteerbaar zijn, betoogt dit artikel dat de instanties voorheen niet bestudeerd waren vanwege hun relatieve eenvoud en dat de gegenereerde heuristieken een gebrek hebben aan ware interpreteerbaarheid en generaliseerbaarheid.

2. Methodologie

De auteurs hanteren een veelzijdige methodologie om de door LLM gegenereerde heuristieken te herbeoordelen:

Code-analyse en Interpretatiebeoordeling: De auteurs analyseren handmatig de broncode van de best presterende door LLM gegenereerde heuristieken (aangeduid als c12 voor Uniform en c14 voor Weibull, samen met de EoH heuristiek van Liu et al. [2024]). Zij evalueren of de logica transparant is voor domeinexperts of dat het uitgebreide experimenten vereist om begrepen te worden.
Gedragsmatige Reverse Engineering: Voor opake heuristieken (specifiek c14) voeren de auteurs item-voor-item vergelijkingen uit met baseline-strategieën (bijv. WorstFit, BestFit) om de onderliggende beslisregels af te leiden. Zij analyseren resterende bakcapaciteiten en beslissingsdrempels om een menselijk leesbare benadering van het gedrag van het algoritme te formuleren.
Afleiding van Vereenvoudigde Algoritmen: Op basis van de gedragsanalyse stellen de auteurs een nieuwe klasse van twee-parameter heuristieken voor (aangeduid als ab-FirstFit, ab-BestFit, en ab-WorstFit). Deze algoritmen formaliseren de geobserveerde patronen:
1. Als een bak het item kan passen zodanig dat de resterende ruimte $\le a$ is (tight fit), pas dan een specifieke strategie toe (bijv. BestFit).
2. Als de resterende ruimte $> b$ is (loose fit), pas dan een baseline-strategie toe (bijv. FirstFit of WorstFit).
3. Zo niet, open dan een nieuwe bak.
Empirische Evaluatie: De voorgestelde ab-Baselines worden getoetst tegen de door LLM gegenereerde heuristieken (c12, c14, EoH) en standaard baselines (BestFit, FirstFit) over de originele distributies en aanvullende variaties (andere Uniform en Weibull parameters). De evaluatie meet het aantal gebruikte bakken en de generalisatiecapaciteiten.

3. Belangrijkste Bijdragen

Kritiek op Interpreteerbaarheid: Het artikel toont aan dat hoewel door LLM gegenereerde code syntactisch leesbaar is, het niet semantisch interpreteerbaar is. De heuristieken c14 en EoH bevatten opake wiskundige operaties (bijv. buur-afhankelijke score-updates, complexe exponentiële termen) die de onderliggende logica niet onthullen. Het begrijpen van hun gedrag vereiste experimentele observatie in plaats van code-inspectie, wat de claim dat ze "interpreteerbare" inzichten bieden, tegenspreekt.
Identificatie van Onderliggende Eenvoud: De auteurs tonen aan dat de prestatiewinst van LLM-heuristieken rust op twee specifieke condities: (H1) een groot aantal items om te plannen, en (H2) een distributie met een positieve ondergrens voor itemgroottes (wat voorkomt dat zeer kleine items grote gaten opvullen). Deze condities maken de specifieke instanties relatief eenvoudig.
Voorstel van Superieure, Generaliseerbare Heuristieken: De auteurs introduceren ab-Baselines, een klasse van eenvoudige, twee-parameter algoritmen. Deze heuristieken:
- Presteren gelijk aan of licht beter dan de door LLM gegenereerde heuristieken op hun trainingsdistributies.
- Zijn aanzienlijk efficiënter computationeel (vereisen minuten aan tuning versus miljoenen LLM-queries).
- Generaliseren effectief naar andere parametriseringen van Uniform en Weibull distributies, terwijl LLM-heuristieken falen in het generaliseren buiten hun specifieke trainingsclusters.
Herbeoordeling van "Wiskundige Ontdekking": Het artikel betoogt dat de bestudeerde instanties (Uniform(20, 100) en Weibull(3.0, 45)) niet eerder zijn bestudeerd omdat ze moeilijk waren, maar omdat ze waarschijnlijk als oninteressant of triviaal werden beschouwd door de gemeenschap. De LLM's hebben in feite bekende optimalisatiepatronen (tight vs. loose fitting) herontdekt via stochastische zoektochten in plaats van nieuwe conceptuele inzichten te genereren.

4. Resultaten

Prestaties: Op de Uniform(20, 100) distributie presteert de vereenvoudigde ab-FirstFit (met parameters $a=5, b=24$ ) gemiddeld 0,71% beter dan de LLM-heuristiek c12 en 2,71% beter dan BestFit. Op de Weibull(3.0, 45) distributie presteert ab-WorstFit ( $a=1, b=21$ ) 0,12% beter dan c14 en 3,39% beter dan BestFit.
Generalisatie: Terwijl LLM-heuristieken significant achteruitgaan wanneer ze worden getest op distributies met verschillende parameters, behouden de ab-Baselines een robuuste prestatie over diverse Uniform en Weibull configuraties.
Efficiëntie: De afleiding en tuning van de ab-Baselines werden voltooid in enkele minuten op een persoonlijke laptop, wat scherp contrasteert met de dagen aan training en miljoenen LLM-queries die nodig waren om c12 en c14 te produceren.
Interpretatiekloof: De auteurs slaagden erin de logica van c14 te reverse-engineeren naar een eenvoudige regel (BestFit voor tight fits, WorstFit voor loose fits, anders een nieuwe bak), wat bewijst dat de "ontdekking" een herparametrisering van bestaande strategieën was in plaats van een nieuw algoritmisch concept.

5. Betekenis en Claims

Het artikel sluit af met een bescheiden maar kritische herbeoordeling van de rol van LLM's in wetenschappelijke ontdekking:

Weerlegging van "Ontdekking": De auteurs stellen dat het door LLM gebaseerde evolutionaire framework geen "wiskundige ontdekking" heeft geproduceerd in de zin van het bieden van nieuw theoretisch begrip of conceptuele doorbraken. In plaats daarvan fungeerde het als een krachtige hyper-heuristiek die parameters optimaliseerde voor een specifieke, smalle en voorheen onbestudeerde instantie.
Beperkingen van Huidige Claims: De claim dat LLM's gevestigde open problemen kunnen oplossen, wordt als onvoldoende ondersteund beschouwd door de bin packing casestudy. Het gebrek aan voorgaand werk op deze specifieke distributies suggereert dat het probleem niet "open" was vanwege de moeilijkheidsgraad, maar door een gebrek aan waargenomen belang.
Toekomstige Richting: Het artikel pleit voor rigoureuze validatieprotocollen. Om LLM's krediet te kunnen geven voor echte wetenschappelijke bijdragen, moeten ze worden toegepast op significante, goed gevestigde problemen waar de resulterende oplossingen verbeteringen laten zien ten opzichte van de beste bestaande literatuur en overdraagbare conceptuele inzichten bieden, in plaats van slechts empirische winsten op smalle, synthetische instanties.
Rol van LLM's: De auteurs positioneren LLM's als een hulpmiddel om de zoekruimte van genetische algoritmen uit te breiden en het ontwerp van heuristieken te automatiseren, maar benadrukken dat ze in deze context fungeren als empirische optimalisatoren in plaats van agenten van theoretisch inzicht.