Mathematical discoveries from program search with large language models

By Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. P. Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi and 7 more. Nature, 2023

1,101 citations recorded by the source corpus.

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 statements1,2. 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 approaches3. 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 shows that it is possible to make discoveries for established open problems using LLMs. We showcase the generality of FunSearch by applying it to an algorithmic problem, online bin packing, finding new heuristics that improve on widely used baselines. In contrast to most computer search approaches, FunSearch searches for programs that describe how to solve a problem, rather than what the solution is. Beyond being an effective and scalable strategy, discovered programs tend to be more interpretable than raw solutions, enabling feedback loops between domain experts and FunSearch, and the deployment of such programs in real-world applications. FunSearch makes discoveries in established open problems using large language models by searching for programs describing how to solve a problem, rather than what the solution is.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d32ba88571141ed0ebe7aeefbaa4ccaf8cda7be3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025, positive): “In AlphaEvolve , the evolutionary database implements an algorithm that is inspired by a combination of the MAP elites algorithm [74] and island-based population models [83, 97].”
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (2024, neutral): “We elicit the power of LHH by presenting Reflective Evolution (ReEvo) .”
Neurosymbolic Program Synthesis (positive): “This synthesis problem is solved using a variety of strategies that bring together deep learning (including the use of large language models [5,6]) and symbolic search and reasoning techniques.”
ATLAS: Scaffold-Free Algorithm Synthesis by LLMs via Embedding-Guided Quality-Diversity Search (2026, unknown): “Representative examples include F UN S EARCH [36], E O H [25], R E E VO [57], HSEvo [9], MCTS-AHD [61], CALM [18], H EUR A GENIX [55], ME O H [56], and E O H-S [27].”