FunSearch: What an AI Packing Rule Has to Prove

Two orders arrive at a small shop. Each contains something that fits into more than one open carton. The obvious move is to choose the carton with the least spare space after packing. But suppose a much larger item arrives next. The first choice may have used space that would have been more valuable later. A rule that looks sensible for a single decision can leave you opening more cartons by the end of the day.

A version of that problem helped researchers test FunSearch, a system that uses a language model to propose computer programs and a separate evaluator to score them. The interest lies in what the model was asked to produce. It did not have to pack one list of items neatly. It had to propose a rule that could make decisions across many lists, including ones it had never seen. The difference is useful even if your own work has nothing to do with boxes.

For a concrete example, take two bins with three and five units of room. Put an item of size two in the tighter bin and the remaining spaces are one and five. Two later items of size three cannot both fit. Put the first item in the looser bin and you leave three units in each, enough for both later items. That does not make the looser bin universally better; the example works because of what arrives next.

The model proposed a rule; the evaluator did the counting

In their Nature paper, published online in December 2023, Bernardino Romera-Paredes and colleagues paired a pretrained language model with an automated evaluator. The model generated variations of program functions. The evaluator ran candidates and assigned scores, and promising programs could be used to prompt later rounds of suggestions. The authors applied this approach to the mathematical cap set problem as well as to online bin packing. The packing example is a useful way to see the division of labour.

In the study’s one-dimensional packing problem, an item has a size and each bin has a fixed capacity. Items arrive in order, and the method must assign the current item without knowing the future arrivals. The program under search helps choose which feasible bin to favour. The evaluator can then run the policy on sequences and count how many bins it uses. No amount of persuasive explanation from the model can reduce that count.

The authors report finding heuristics that improved on widely used baselines in their experiments. Their public repository includes discovered packing heuristics and evaluation code. This is a result about the tested problem and comparisons. It does not imply that the rule is optimal for every input or that it will automatically improve how a real shop packs parcels. A one-dimensional capacity score leaves out shape, fragility and the fact that items from different orders may have to travel separately.

Make the baseline strong enough to be useful

Suppose you want to borrow the research idea for assigning editing jobs to production days. Each job has an estimated duration and each day has a fixed number of available hours. An assistant proposes a rule that uses fewer days than your current process on last month’s work. Before adopting it, ask what the current process knew when it assigned each job. If the new rule was allowed to see the whole month in advance while the old process had to decide as requests came in, you have compared two different jobs.

A fair first comparison gives both methods the same information at each step. It also includes the existing rule exactly as people use it, including exceptions. If an editor reserves time for late changes, a schedule that uses every minute may look more efficient while losing the capacity that makes the service reliable. Decide which requirements are firm and which you are willing to trade off before you look at the results.

Keep the test separate from the search

If you keep improving a rule against the same examples, those examples become part of how you designed it. Set aside a few different sequences to use after you have chosen a candidate. In the editing example, that might mean a week of short jobs followed by a rush order, and another week with long projects arriving early. Record failures as well as average performance. A rule that saves a day on routine work and misses the only fixed deadline may be a poor fit.

The authors’ December 2023 explanation describes the iterative relationship between the generator and evaluator. In a small business, you can use the same distinction without recreating the research system. Let the assistant generate candidate rules. Keep a separate spreadsheet or script that checks what actually happened when each rule was applied. Then read the awkward cases yourself.

• Specify the decision. Write down what arrives, what the rule can see and which choices are allowed.
• Measure what matters. Count the primary outcome and record any constraints that would disqualify a candidate.
• Compare with a fair baseline. Give both approaches the same input and test on examples held back from the design process.

Our article on AlphaDev’s search for small sorting routines offers a related example of AI proposing code under a specific test. FunSearch’s packing case adds a practical question: will the candidate keep working as the sequence changes? You can answer that only when you know what the evaluator sees and what it leaves out.

Sources

• Romera-Paredes and colleagues, Mathematical discoveries from program search with large language models, Nature (online December 2023).
• Google DeepMind, FunSearch research repository and authors’ explanation (14 December 2023).