Bin packing is the problem of fitting items into as few fixed-size containers as possible. It is NP-hard, which in practice means nobody computes the true optimum for a real workload, so everything runs on heuristics.
The classic one is first fit: take each item in turn and put it in the first bin with room. Sorting the items largest first before you start gives first fit decreasing, which is reliably better. The bin packing calculator runs both, and on its default list the sort is worth a whole bin: four containers become three, from exactly the same items.
The online version
Sorting assumes you have the whole list. Often you do not. Virtual machines arrive one at a time and have to be placed on a server immediately, and you cannot wait to see what is coming. That is online bin packing, and it is the version DeepMind pointed FunSearch at in December 2023.
The standard online rules are first fit and best fit, where best fit puts each item in the fullest bin that still has room. FunSearch searched for better rules and found some, improving on both across well-studied input distributions. The improvements are modest and distribution-specific, which is the honest framing: this is not a new theorem about bin packing, it is a better rule of thumb for inputs that look a certain way.
Why a program is better than a network
You could train a neural network to make the same placement decisions. People have. The problem is that you then have a policy nobody can inspect, which is awkward when it is deciding where your production workloads land.
FunSearch returns source code. The rules it found are short functions a human can read, reason about and check, and that turned out to matter more than the size of the improvement. A heuristic you can read is one you can deploy, argue with, and modify when your workload changes. The usual trade between performance and interpretability did not apply, because the search space was programs rather than parameters.
What the calculator shows
Two things worth noticing. The first is that the lower bound is only a bound. Six items of size 51 into bins of capacity 100 gives a bound of four, because the volume divides that way, but no two items fit together so the true answer is six. Volume is not the only constraint, and the gap between the bound and the truth is where all the difficulty lives.
The second is that the sort only matters sometimes. Change the bin capacity on the default list and the two methods usually agree. They diverge at the awkward sizes, where one large item can strand a bin that a different ordering would have filled. That is exactly the situation the online version is stuck in permanently, which is why better online rules are worth searching for.
The cap set result from the same system is in the piece on the cap set problem, and for the related question of how few comparisons a sort needs, see AlphaDev.