--- title: "Mathematical Discoveries from Program — Romera-Paredes 2023" description: "Large language models can write code, but they often produce answers that sound right and are wrong." authors: ["Bernardino Romera-Paredes", "Mohammadamin Barekatain", "Alexander Novikov", "Matej Balog", "M. Pawan Kumar", "Emilien Dupont", "Francisco J. R. Ruiz", "Jordan S. Ellenberg", "Pengming Wang", "Omar Fawzi", "Pushmeet Kohli", "Alhussein Fawzi"] year: 2023 venue: "Nature 625" source: "https://www.nature.com/articles/s41586-023-06924-6.pdf" licence: "CC BY 4.0" licence_url: "https://creativecommons.org/licenses/by/4.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/paredes-2023-mathematical-discoveries-program-search-large/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/paredes-2023-mathematical-discoveries-program-search-large/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2023](https://md.research.elamur.ai/free/en/papers/2023/page/5/) / Mathematical Discoveries from Program Search with Large Language Models # Mathematical Discoveries from Program Search with Large Language Models **Authors:** Bernardino Romera-Paredes, Mohammadamin Barekatain, [Alexander Novikov](https://md.research.elamur.ai/free/en/authors/alexander-novikov/), Matej Balog, [M. Pawan Kumar](https://md.research.elamur.ai/free/en/authors/m-pawan-kumar/), [Emilien Dupont](https://md.research.elamur.ai/free/en/authors/emilien-dupont/), [Francisco J. R. Ruiz](https://md.research.elamur.ai/free/en/authors/francisco-j-r-ruiz/), Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, [Pushmeet Kohli](https://md.research.elamur.ai/free/en/authors/pushmeet-kohli/), Alhussein Fawzi · **Year:** 2023 · **Venue:** Nature 625 · **Licence:** [CC BY 4.0](https://creativecommons.org/licenses/by/4.0/) **Links:** [Publisher's page](https://www.nature.com/articles/s41586-023-06924-6.pdf) · [PDF](https://www.nature.com/articles/s41586-023-06924-6.pdf) **Citations:** [184](#cited-by) in our library, of the 140884 papers whose bibliographies we read ## 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. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* Fields: [Computing & GPUs](https://md.research.elamur.ai/free/en/shelves/computing/) ## Cited by Cited by 184 papers of our library cite it (of the 140884 whose bibliographies we read); 6 of them have a page here, 178 not yet. - [Large Language Models for Mathematical Reasoning: Progresses and Challenges](https://md.research.elamur.ai/free/en/papers/ahn-2024-large-language-models-mathematical-reasoning/) - [Cutting Through the Noise: Boosting LLM Performance on Math Word Problems](https://md.research.elamur.ai/free/en/papers/anantheswaran-2024-cutting-through-noise-boosting-llm/) - [ResearchAgent: Iterative Research Idea Generation over Scientific Literature with Large Language Models](https://md.research.elamur.ai/free/en/papers/baek-2024-researchagent-iterative-research-idea/) - [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://md.research.elamur.ai/free/en/papers/lu-2024-ai-scientist-fully-automated/) - [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://md.research.elamur.ai/free/en/papers/novikov-2025-alphaevolve-coding-agent-scientific-algorithmic/) - [Agent Laboratory: Using LLM Agents as Research Assistants](https://md.research.elamur.ai/free/en/papers/schmidgall-2025-agent-laboratory-using-llm/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{romeraparedes2023mathematical, title = {{Mathematical Discoveries from Program Search with Large Language Models}}, author = {Romera-Paredes, Bernardino and Barekatain, Mohammadamin and Novikov, Alexander and Balog, Matej and Kumar, M. Pawan and Dupont, Emilien and Ruiz, Francisco J. R. and Ellenberg, Jordan S. and Wang, Pengming and Fawzi, Omar and Kohli, Pushmeet and Fawzi, Alhussein}, booktitle = {Nature 625}, year = {2023}, url = {https://www.nature.com/articles/s41586-023-06924-6.pdf} } ``` - [← previous Mathematical Capabilities of ChatGPT](https://md.research.elamur.ai/free/en/papers/frieder-2023-mathematical-capabilities-chatgpt/) - [next → MathPrompter: Mathematical Reasoning using Large Language Models](https://md.research.elamur.ai/free/en/papers/imani-2023-mathprompter-mathematical-reasoning-large-language/) - [↑ back to papers of 2023](https://md.research.elamur.ai/free/en/papers/2023/page/5/)