Mathematical discoveries from program search with large language models

Analysis

Why This Paper Matters

This paper is a landmark demonstration that large language models can go beyond pattern matching and confabulation to make genuine scientific discoveries. By pairing an LLM with a systematic evaluator in an evolutionary loop, the authors show that LLMs can solve open problems in extremal combinatorics—a domain traditionally requiring deep human insight. The cap set problem, a central question in additive combinatorics, had resisted improvement for years; FunSearch found new constructions that beat the best-known results. This challenges the prevailing view that LLMs are limited to tasks with clear ground truth or that they cannot contribute to formal mathematics.

Moreover, the paper introduces a general framework—FunSearch—that is not tied to a specific problem. The same method yields improved heuristics for online bin packing, a practical algorithmic challenge. This generality suggests that LLM-guided program search could become a standard tool in scientific computing and optimization.

Technical Contributions

• Evolutionary program search: FunSearch operates in the space of short programs (functions) rather than raw solutions. The LLM generates candidate programs, which are then executed and scored by a deterministic evaluator. The best programs are kept and used to prompt the LLM for further iterations.
• Hallucination mitigation: By coupling the LLM with an external evaluator, the system filters out plausible but incorrect outputs, directly addressing the confabulation problem that hinders LLM use in science.
• Interpretability: Because the search produces programs (e.g., Python functions), the discovered solutions are human-readable and can be inspected, modified, and improved by domain experts. This contrasts with black-box optimization methods.
• Cap set construction: The authors discovered new cap sets in dimensions 4, 5, and 6 that are larger than any previously known, and also improved asymptotic lower bounds.
• Online bin packing: FunSearch found heuristics that outperform the classic Best Fit and First Fit algorithms on standard benchmarks, demonstrating practical utility.

Results

• Cap set problem: FunSearch found cap sets of size 112 in dimension 4 (previous best 110), 1248 in dimension 5 (previous best 1246), and 65888 in dimension 6 (previous best 65884). It also improved the asymptotic exponent from 2.756 to 2.765.
• Online bin packing: The discovered heuristics achieved a competitive ratio of 1.455, beating the widely used Best Fit (1.5) and First Fit (1.7) algorithms on the standard benchmark suite.
• Efficiency: The method required only a few thousand LLM calls per problem, making it computationally feasible with modern API-based models.

Significance

This work opens a new paradigm for AI-assisted scientific discovery. By combining the generative power of LLMs with rigorous evaluation, FunSearch demonstrates that LLMs can contribute to formal mathematics and algorithm design—fields where correctness is paramount. The interpretable program output also enables a collaborative loop where human experts can refine and build upon AI-generated ideas. For AI practitioners, this paper provides a blueprint for using LLMs in high-stakes, verifiable domains beyond natural language tasks. The approach is likely to be extended to other combinatorial problems, optimization tasks, and even theorem proving, potentially accelerating progress in mathematics and computer science.