Mathematical discoveries from program search with large language models
Evolutionary search over programs an LLM writes, filtered by a systematic evaluator, produced new results in extremal combinatorics. It is the direct predecessor of AlphaEvolve and the first case of a language model making a discovery on an established open problem.
Ask this paper
An evaluator, not the model's own judgment, decides which programs survive.
Published in Nature rather than on arXiv, so it is written directly to the hub.
Abstract
Large language models (LLMs) have demonstrated tremendous capabilities in solving complex tasks, from quantitative reasoning to understanding natural language. However, LLMs sometimes suffer from confabulations (or hallucinations), which can result in them making plausible but incorrect statements. This hinders the use of current large models in scientific discovery. Here we introduce FunSearch (short for searching in the function space), an evolutionary procedure based on pairing a pretrained LLM with a systematic evaluator. We demonstrate the effectiveness of this approach to surpass the best-known results in important problems, pushing the boundary of existing LLM-based approaches. Applying FunSearch to a central problem in extremal combinatorics, the cap set problem, we discover new constructions of large cap sets going beyond the best-known ones, both in finite dimensional and asymptotic cases. This represents the first discoveries made for established open problems using LLMs.