💻 computer science

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

This paper challenges the claim that Large Language Models significantly advance mathematical discovery in the bin packing problem by demonstrating that their generated heuristics are opaque and that the problem instances are actually simple enough to be solved by more efficient, interpretable, and generalizable algorithms, thereby highlighting the need for rigorous validation of LLM-generated scientific contributions.

Original authors: Julien Herrmann, Guillaume Pallez

Published 2026-06-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Julien Herrmann, Guillaume Pallez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive warehouse. Every day, trucks arrive with boxes of all different sizes, and you have to pack them into shipping containers (bins) as they come. You don't know what the next box will look like; you just have to make a quick decision: "Do I put this box in Container A, Container B, or open a brand new Container C?"

The goal is simple: use as few containers as possible. This is a classic puzzle known as the Bin Packing Problem.

Recently, a famous study (by Romera-Paredes et al.) claimed that Large Language Models (LLMs)—the same AI technology that writes essays and code—had discovered a "new mathematical secret" to solve this packing puzzle better than humans could. They said the AI found a clever new rule that was so smart, it counted as a "mathematical discovery."

This paper by Julien Herrmann and Guillaume Pallez is like a team of expert detectives coming in to investigate that claim. They put on their magnifying glasses and say, "Hold on. Let's look at what the AI actually did."

Here is what they found, explained simply:

1. The AI's "Secret" Wasn't Very Secret

The AI produced a set of computer instructions (a heuristic) that packed the boxes slightly better than the standard human methods. The original study claimed these instructions were "interpretable," meaning humans could easily read them and understand the logic.

The Paper's Reality Check:
The authors looked at the AI's code and found it was like reading a recipe written in a strange dialect.

The "c12" Code: This was a long list of "If this, then that" rules. It was readable, but the logic was messy. It was like a chef saying, "If the pot is between 7 and 8 degrees, add salt. If it's between 8 and 9, add a pinch less." It worked, but it didn't explain why it worked.
The "c14" Code: This one was even worse. It was a complex math formula that looked like gibberish. The authors had to run thousands of experiments just to guess what the code was actually doing. They realized that even though the code was written in plain English (Python), the reasoning behind it was hidden. It was a "black box" wearing a clear mask.

The Analogy: Imagine the AI gave you a magic compass that always pointed North. The original study said, "Look, the compass is made of glass, so you can see the needle! It's fully understandable!" The authors say, "Yes, we can see the needle, but we have no idea how the magnet inside works. We just know it points North because we tested it a million times."

2. The AI Didn't Discover a New Law of Physics

The original study claimed the AI made a "mathematical discovery." The authors argue this is a stretch.

The Paper's Reality Check:
The AI was tested on very specific, narrow scenarios (like boxes that are all between 20 and 100 units in size). The authors found that the AI didn't invent a new way of thinking; it just found a slightly tweaked version of an old, simple trick.

They realized the AI's "secret sauce" was actually just two simple numbers (parameters) that said:

"If a box fits really tightly, put it there."
"If it doesn't fit tightly, put it in a container that has plenty of space left."

The authors took this simple idea, stripped away the complex AI code, and built a new, super-simple algorithm (called ab-FirstFit or ab-WorstFit).

The Result: This new human-made algorithm was faster, easier to understand, and worked better than the AI's complex code. It even worked on different types of box sizes, whereas the AI's code broke when the rules changed slightly.

The Analogy: It's like the AI found a slightly better way to tie a shoelace by inventing a complex knot with 15 loops. The authors looked at it, realized, "Oh, you just need to pull the laces tighter and leave a little slack," and showed that a simple double-knot works better, is easier to learn, and doesn't require a PhD in knot theory.

3. The "Discovery" Was Just a Lack of Prior Research

The original study claimed they found something "new" because no one had published a paper on these specific box sizes before.

The Paper's Reality Check:
The authors suggest that no one had studied these specific box sizes not because they were too hard or mysterious, but because they weren't that important. It's like claiming you made a "scientific breakthrough" by finding the best way to stack pebbles in a specific shape of garden. It's a valid question, but it's not a fundamental discovery of the universe.

The authors argue that if the AI had truly discovered a deep mathematical truth, other researchers would have been able to read the AI's code, understand the principle, and use it to solve other problems. Instead, nobody has been able to do that. The "insight" died with the specific code the AI wrote.

The Bottom Line

The paper concludes that while using AI to help design algorithms is a cool idea, we need to be careful with the hype.

The AI did not make a "mathematical discovery." It just found a slightly better way to do a simple task by trial and error.
The AI's code was not truly "interpretable." It was hard to understand, and the "logic" was only found by guessing through experiments, not by reading the code.
Humans can do better. By understanding the simple principle the AI stumbled upon, humans created a simpler, faster, and more reliable tool.

The Final Metaphor:
The AI was like a monkey typing on a typewriter. Eventually, it typed a sentence that made sense. The original study said, "Look! The monkey has discovered the meaning of life!" The authors of this paper say, "No, the monkey just typed a sentence that works for this specific paragraph. We can write a better sentence, explain it clearly, and apply it to the whole book without needing a monkey."

The paper urges scientists to be rigorous: just because an AI produces a result that looks smart, doesn't mean it has truly understood the problem or made a discovery that changes how we think about math.

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

1. Problem Definition and Context

The paper investigates the validity of claims made by Romera-Paredes et al. [2024] regarding Large Language Models (LLMs) contributing to "mathematical discovery" in combinatorial optimization. Specifically, it focuses on the Online Bin Packing Problem (OBPP), where items of varying sizes arrive sequentially and must be packed into bins of fixed capacity without knowledge of future items. The goal is to minimize the total number of bins used.

The study scrutinizes the FunSearch framework, which uses an LLM (Codey) within an evolutionary algorithm to generate heuristics for specific stochastic instances of OBPP. The target instances involve item sizes drawn from Uniform(20, 100) and Weibull(3.0, 45) distributions. While Romera-Paredes et al. claim these LLM-generated heuristics represent new scientific discoveries and are interpretable, this paper argues that the instances were previously unstudied due to their relative simplicity and that the generated heuristics lack true interpretability and generalizability.

2. Methodology

The authors employ a multi-faceted methodology to reassess the LLM-generated heuristics:

Code Analysis and Interpretability Assessment: The authors manually analyze the source code of the best-performing LLM-generated heuristics (denoted as c12 for Uniform and c14 for Weibull, along with the EoH heuristic from Liu et al. [2024]). They evaluate whether the logic is transparent to domain experts or if it requires extensive experimentation to understand.
Behavioral Reverse Engineering: For opaque heuristics (specifically c14), the authors conduct item-by-item comparisons against baseline strategies (e.g., WorstFit, BestFit) to deduce the underlying decision rules. They analyze remaining bin capacities and decision thresholds to formulate a human-readable approximation of the algorithm's behavior.
Derivation of Simplified Algorithms: Based on the behavioral analysis, the authors propose a new class of two-parameter heuristics (denoted ab-FirstFit, ab-BestFit, and ab-WorstFit). These algorithms formalize the observed patterns:
1. If a bin can fit the item such that the remaining space is $\le a$ (tight fit), apply a specific strategy (e.g., BestFit).
2. If the remaining space is $> b$ (loose fit), apply a baseline strategy (e.g., FirstFit or WorstFit).
3. Otherwise, open a new bin.
Empirical Evaluation: The proposed ab-Baselines are benchmarked against the LLM-generated heuristics (c12, c14, EoH) and standard baselines (BestFit, FirstFit) across the original distributions and additional variations (different Uniform and Weibull parameters). The evaluation measures the number of bins used and generalization capabilities.

3. Key Contributions

Critique of Interpretability: The paper demonstrates that while LLM-generated code is syntactically readable, it is not semantically interpretable. The heuristics c14 and EoH contain opaque mathematical operations (e.g., neighbor-dependent score updates, complex exponential terms) that do not reveal the underlying logic. Understanding their behavior required experimental observation rather than code inspection, contradicting the claim that they offer "interpretable" insights.
Identification of Underlying Simplicity: The authors show that the performance gains of LLM heuristics rely on two specific conditions: (H1) a large number of items to be scheduled, and (H2) a distribution with a positive lower bound on item sizes (preventing very small items from filling large gaps). These conditions make the specific instances relatively simple.
Proposal of Superior, Generalizable Heuristics: The authors introduce ab-Baselines, a class of simple, two-parameter algorithms. These heuristics:
- Match or slightly outperform the LLM-generated heuristics on their training distributions.
- Are significantly more efficient computationally (requiring minutes of tuning vs. millions of LLM queries).
- Generalize effectively to other parameterizations of Uniform and Weibull distributions, whereas LLM heuristics fail to generalize outside their specific training clusters.
Reassessment of "Mathematical Discovery": The paper argues that the instances studied (Uniform(20, 100) and Weibull(3.0, 45)) had not been studied previously not because they were difficult, but because they were likely deemed uninteresting or trivial by the community. The LLMs essentially rediscovered known optimization patterns (tight vs. loose fitting) through stochastic search rather than generating novel conceptual insights.

4. Results

Performance: On the Uniform(20, 100) distribution, the simplified ab-FirstFit (with parameters $a=5, b=24$ ) outperforms the LLM heuristic c12 by 0.71% on average and BestFit by 2.71%. On the Weibull(3.0, 45) distribution, ab-WorstFit ( $a=1, b=21$ ) outperforms c14 by 0.12% and BestFit by 3.39%.
Generalization: While LLM heuristics degrade significantly when tested on distributions with different parameters, the ab-Baselines maintain robust performance across various Uniform and Weibull configurations.
Efficiency: The derivation and tuning of the ab-Baselines were completed in minutes on a personal laptop, contrasting sharply with the days of training and millions of LLM queries required to produce c12 and c14.
Interpretability Gap: The authors successfully reverse-engineered the logic of c14 into a simple rule (BestFit for tight fits, WorstFit for loose fits, new bin otherwise), proving that the "discovery" was a reparameterization of existing strategies rather than a new algorithmic concept.

5. Significance and Claims

The paper concludes with a modest but critical reassessment of the role of LLMs in scientific discovery:

Refutation of "Discovery": The authors assert that the LLM-based evolutionary framework did not produce a "mathematical discovery" in the sense of providing new theoretical understanding or conceptual breakthroughs. Instead, it acted as a powerful hyper-heuristic that optimized parameters for a specific, narrow, and previously unstudied instance.
Limitations of Current Claims: The claim that LLMs can solve established open problems is deemed insufficiently supported by the bin packing case study. The lack of prior work on these specific distributions suggests the problem was not "open" due to difficulty, but due to a lack of perceived importance.
Future Direction: The paper advocates for rigorous validation protocols. For LLMs to be credited with genuine scientific contribution, they must be applied to significant, well-established problems where the resulting solutions demonstrate improvements over the best existing literature and offer transferable conceptual insights, rather than just empirical gains on narrow, synthetic instances.
Role of LLMs: The authors position LLMs as a tool for extending the search space of genetic algorithms and automating heuristic design, but emphasize that, in this context, they function as empirical optimizers rather than agents of theoretical insight.