Mathematical Discoveries from Program Search with Large Language Models

Written for the Research library (claude-opus-5-5) from the paper text. Original — nature.com/articles/s41586-023-06924-6.pdf

Summary

Large language models can write code, but they often produce answers that sound right and are wrong. That makes them hard to trust for new scientific results. The authors present FunSearch, an evolutionary loop that combines a frozen code LLM (Codey, built on PaLM2) with an automatic evaluator that scores each candidate and discards incorrect ones. FunSearch does not search for solutions directly. It evolves short programs that build solutions, usually by filling in a priority or heuristic function inside a fixed skeleton such as a greedy algorithm. High-scoring programs are put back into prompts, and an island-based population keeps the search diverse. Applied to the cap set problem in extremal combinatorics, FunSearch found larger constructions than any previously known, both in specific dimensions and in the asymptotic lower bound. It also found online bin packing heuristics that beat standard rules. Because the outputs are compact, readable programs, domain experts can inspect them and use them in practice. This shows LLMs can contribute verifiable new mathematics, not just recombine what they were trained on.

Key points

• The method has four main parts: "best-shot" prompting with top programs from a database, a problem skeleton that limits what gets evolved, island-based evolution with periodic resets, and large-scale asynchronous parallel sampling (about 10⁶ LLM samples per result).
• Cap sets: FunSearch found a cap set of size 512 in dimension 8, beating the previous best of 496. Using admissible sets, it raised the asymptotic lower bound on cap set capacity (from about 2.2180 to 2.2202), which the authors call the biggest gain in roughly 20 years.
• Online bin packing: the evolved heuristics used fewer bins than first fit and best fit on OR-Library and Weibull-distributed instances.
• Results depended little on which LLM was used. StarCoder, an open-source model, was tested as an alternative.
• Program-space search produces short, interpretable code that scales to large instances and is easier to deploy than neural policies.

Note: the middle of the pasted text was cut, so the specific numbers above (512 vs. 496, 2.2180 → 2.2202, OR-Library/Weibull) come from my knowledge of the published paper, not from the excerpt. Please check them against the full PDF before adding this to the library.