Mathematical discoveries from program search with large language models
Open accessThe DOI matches its Crossref record; 94 of the 94 references it cites were found in a registry or an index; 12 of the 32 sources its claims cite were checked for support.
Abstract
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 1,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 approaches 3 . 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.
Overview
CoChat Summary
TL;DR
FunSearch pairs a frozen pretrained LLM with a systematic evaluator in an evolutionary loop that searches over programs rather than raw solutions. It discovers new cap set constructions and online bin packing heuristics that surpass best-known or widely used baselines.
Key findings
- In the cap set problem, FunSearch found a cap set of size 512 in dimension n = 8, larger than previously known; only 4 out of 140 experiments discovered it. It also discovered a program generating the set, which researchers manually simplified into an explicit construction.
- For admissible sets, FunSearch improved the lower bound on cap set capacity from 2.2180 to 2.2184. After inspecting the discovered program and identifying a new symmetry, it found a full-size admissible set implying C ≥ 2.219486 and a partial admissible set of size 237,984 implying C ≥ 2.2202.
- For online bin packing, FunSearch outperformed first fit and best fit across OR1–OR4 and Weibull datasets. Reported excess-bin fractions: OR1 5.30% vs 6.42% first fit and 5.81% best fit; OR4 2.47% vs 5.23% and 4.94%; Weibull 100k 0.03% vs 4.00% and 3.79%.
- Discovered bin packing heuristics often use a strategy of assigning an item to a least-capacity bin only if the fit is very tight after placement; otherwise they place it elsewhere to avoid leaving small unusable gaps.
Methods
- FunSearch uses a pretrained, frozen LLM (Codey, built on PaLM2) as a mutation/crossover-like operator, paired with an evaluator that scores candidate programs. It uses best-shot prompting with k = 2 sampled programs, a program skeleton where only the critical function is evolved, an island-based evolutionary method, and asynchronous distributed workers (typically 15 samplers and 150 CPU evaluators).
- For cap sets, it evolves a priority function that iteratively grows a cap set; for admissible sets, it evolves a priority function to grow admissible sets; for online bin packing, it evolves a heuristic starting from best fit, evaluated on OR-Library OR1–OR4 and Weibull-distributed instances.
- Performance is measured as the fraction of excess bins over the L2 lower bound for bin packing; the paper reports statistical analyses in the Supplementary Information and notes robustness across runs.
Limitations
- The paper states FunSearch works best for problems with an efficient evaluator, a rich scoring feedback signal, and the ability to provide a skeleton with an isolated part to evolve. It explicitly says generating proofs for theorems falls outside this scope because it is unclear how to provide a rich enough scoring signal.
- The paper states that randomness in LLM sampling and the evolutionary procedure means repeated experiments can differ; some problems require many repetitions, such as the n = 8 cap set result, found in only 4 out of 140 experiments.
- The paper notes a performance tradeoff between LLM sample quality and inference speed, choosing a fast-inference model and using on the order of 10^6 samples; it also says results are not too sensitive to the exact LLM choice as long as it was trained on a large enough code corpus.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures









Verification
Claims the paper makes
8 Valid · 1 Not valid · 11 Not checked · 67 Own results and interpretations
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“This is in contrast to traditional genetic programming that does not have this bias (and in addition requires hand-tuning the mutation operators51).”
§ Mathematical discoveries from program search with large language models > Discussion
What the sources say
- Partly supportedcites [51] O’Neill, M., Vanneschi, L., Gustafson, S. & Banzhaf, W. Open issues in genetic programming. Genet. Program. Evolvable Mach. 11, 339–363 (2010). sourceExperimental — accuracy not yet measured
Section 2.6 (Generalization in GP; page unavailable) describes parsimony pressure as an added method for reducing solution complexity, which supports the narrower point that GP does not necessarily favor parsimonious solutions on its own. The passages do not establish a lack of bias toward symmetry, compare GP with FunSearch, or say that mutation operators require hand-tuning. (LLM, conf=0.73)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Partly supported
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“For example, the problem of generating proofs for theorems52–54 falls outside this scope, because it is unclear how to provide a rich enough scoring signal.”
§ Mathematical discoveries from program search with large language models > Discussion
What the sources say
- Supportedcites [52] Polu, S. & Sutskever, I. Generative language modeling for automated theorem proving. Preprint at https://arxiv.org/abs/2009.03393 (2020). source
The citation follows “generating proofs for theorems,” identifying this paper as an example of that problem. Appendix B (p. 18) explicitly displays proofs generated by GPT-f. The statement about FunSearch’s scope and scoring signal is the citing authors’ framing, not a finding attributed to this source. (LLM, conf=0.91)
- Partly supportedcites [53] Polu, S. et al. Formal mathematics statement curriculum learning. In International Conference on Learning Representations (2023). sourceExperimental — accuracy not yet measured
Our copy is squarely work on generating proofs for theorems (Abstract, p. 1: expert iteration applied to formal mathematics, state-of-the-art on miniF2F; Introduction, p. 1), so the identification part of the citing sentence holds. But the rationale attributed alongside it — that it is unclear how to provide a rich enough scoring signal — is not what this paper says: the Introduction (p. 1) states that 'formal mathematics has an automated way of determining whether a trajectory (i.e. a proof) is successful (i.e. formally correct)', and Section 4.3.2 (p. 3) builds an explicit proofsize objective/value function to guide search. The difficulties this paper actually names are the infinite action space and absence of a direct self-play setup (Introduction, p. 1) and the inability to chain more than 2-3 non-trivial reasoning steps within its compute horizon (Section 7.2 Limitations, p. 8) — not the unavailability of a scoring signal. (LLM, conf=0.72)
- Could not verifycites [54] Jiang, A. Q. et al. THOR: wielding hammers to integrate language models and automated theorem provers. Adv. Neural Info. Process. Syst. 35, 8360–8373 (2022). sourceExperimental — accuracy not yet measured
Our copy of Thor (Jiang et al., 2022) never addresses FunSearch or the availability of a scoring/fitness signal for evolutionary search: searches for 'FunSearch', 'scoring signal', 'evolutionary search program synthesis', and 'sparse reward / automatic evaluation' returned only Thor's own proof-search machinery (4.1 Experimental Setup, p. 6 — best-first search ordered by accumulated log likelihoods, termination conditions) and its premise-selection scope (Abstract p. 1; 6 Discussion p. 9, which limits Thor to hammer-based premise selection and Isabelle only). Nothing in the paper states or implies that generating theorem proofs lacks a rich enough scoring signal; conversely, it reports concrete proof-success rates (39%→57% on PISA, 29.9% on MiniF2F), so no contrary statement is made either. The cited point therefore cannot be checked against this source. (LLM, conf=0.72)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
The sources with a verdict support this claim; the rest weren’t checked yet, have no full text we could read, or their verdicts aren’t rated yet.
In the paper
“However, using an LLM mitigates several issues in traditional genetic programming51, as shown in Supplementary Information Appendix A and discussed in ref. 3.”
§ Mathematical discoveries from program search with large language models > Methods > Related work
What the sources say
- Supportedcites [51] O’Neill, M., Vanneschi, L., Gustafson, S. & Banzhaf, W. Open issues in genetic programming. Genet. Program. Evolvable Mach. 11, 339–363 (2010). source
Section 2, “Open Issues,” explicitly outlines significant issues in genetic programming and discusses their limitations. The citation supports the existence of those issues; the citing sentence points to its own supplementary appendix and another reference for the claim that an LLM mitigates them. (LLM, conf=0.88)
- Not checked — no full text of the sourcecites [3] Lehman, J. et al. in Handbook of Evolutionary Machine Learning (eds Banzhaf, W. et al.) 331–366 (Springer, 2023). source
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“We demonstrate the effectiveness of this approach to surpass the best-known results in important problems, pushing the boundary of existing LLM-based approaches3.”
§ Mathematical discoveries from program search with large language models > Abstract
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“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.”
§ Mathematical discoveries from program search with large language models > Abstract
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
41 more claims
Create a free account to see all 87 claims and to verify the 2 references still open.
- Probably not a substantial claim. 18
- It may state two separate claims as one. 27
- The quote only partly states this claim. 1
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Furthermore, AlphaEvolve discovered novel, provably correct algorithms that surpass state-of-the-art solutions on a spectrum of problems in mathematics and computer science, significantly expanding the scope of prior automated discovery methods (Romera-Paredes et al., 2023).”
From AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025) · cites this paper as Romera-Paredes et al., 2023
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Applying AlphaEvolve in different ways comes with different biases (for example, finding constructive functions may favor discovering highly symmetric objects [83]) and thus can suit different problems.”
From AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025) · cites this paper as [83]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Large language models are most reliable when they are not used as final authorities, but as proposal mechanisms inside systems that can check their outputs.”
From Executable World Models for ARC-AGI-3 in the Era of Coding Agents (2026) · cites this paper as [10]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“Similar architectures have already shown some success [35]”
From On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks (2024) · cites this paper as [35]
The cited source says what the claim attributes to it.
In the citing paper
“In the latter case, discovering the algorithm is only an instrumental goal, but it turns out to be a surprisingly effective strategy compared to searching for the solution directly [83].”
From AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025) · cites this paper as [83]
4 more claims about this paper
Create a free account to see every claim other papers make about this one.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Self-check results appear here once an independent check has confirmed them.
Cited works that were retracted
Works this paper cites that were later retracted, from the retraction notices publishers deposit. Major when the notice came out before this paper was published.
Rated major: it would touch a result — a value a result rests on, reported and recomputed p-values on opposite sides of the significance level, two passages that conflict with no sign which is right, or a cited work retracted before this paper was published.
In the paper
“Yang, F. et al. Launchpad: a programming model for distributed machine learning research. Preprint at https://arxiv.org/abs/2106.04516 (2021).”
Cited work 10.1155/2021/6593438 · retracted 2023-08-02 · notice 10.1155/2023/9790230 · this paper published 2023-12-14
Citations
Cites
1 retracted
Research on Students’ Adaptive Learning System Based on Deep Learning Model
Yang, X., Zhou, Z., & Xiao, Y. (2021) · Scientific Programming · doi:10.1155/2021/6593438 · Cited by 16
RetractedGenetic Algorithms and Machine Learning
Goldberg, D. E., & Holland, J. H. (1988) · Machine Learning · doi:10.1023/a:1022602019183 · Cited by 3,193
Distilling Free-Form Natural Laws from Experimental Data
Schmidt, M., & Lipson, H. (2009) · Science · doi:10.1126/science.1165893 · Cited by 2,890 · cited 1×
“Genetic programming is a subfield of computer science concerned with automatically generating or discovering computer programs using evolutionary methods 15,72,73 and is used for symbolic regression applications 74,75 and discovery of optimization algorithms 76 among others.”
MethodGenerative Agents: Interactive Simulacra of Human Behavior
Park, J. S., O'Brien, J., Cai, C. J., Morris, M. R., Liang, P., & Bernstein, M. S. (2023) · Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology · doi:10.1145/3586183.3606763 · Cited by 2,187
Generative Agents: Interactive Simulacra of Human Behavior
Park, J. S., O'Brien, J. C., Cai, C. J., Morris, M. R., Liang, P., & Bernstein, M. S. (2023) · arXiv · doi:10.48550/arxiv.2304.03442 · Cited by 2,173
Genetic programming II: Automatic discovery of reusable programs
(1995) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(95)90099-3 · Cited by 1,901
OR-Library: Distributing Test Problems by Electronic Mail
Beasley, J. E. (1990) · Journal of the Operational Research Society · doi:10.1057/jors.1990.166 · Cited by 1,899
Genetic programming as a means for programming computers by natural selection
Koza, J. (1994) · Statistics and Computing · doi:10.1007/bf00175355 · Cited by 1,685 · cited 3×
“To surpass the ‘nominal’ capabilities of LLMs, recent studies 3 have combined them with evolutionary algorithms 14,15 , leading to important improvements on diverse synthetic problems 16 , searching for neural network architectures 17–19 and solving puzzles 20 .”
BackgroundMethodEvaluating Large Language Models Trained on Code
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. D. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. (2021) · arXiv · doi:10.48550/arxiv.2107.03374 · Cited by 1,436
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (2008) · Texts in Computer Science · doi:10.1007/978-0-387-49820-1 · Cited by 1,424
Research works printed but not linked: 9
- Tanese, R. Distributed Genetic Algorithms for Function Optimization. PhD thesis, Univ. Michigan (1989).
- Cantú-Paz, E. A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systemes Repartis 10, 141–171 (1998).
- Hill, R. On the largest size of cap in S5,3. Rend Lincei. Sci. Fis. Mat. Nat. 54, 378–384 (1973).
- de la Maza, M. An analysis of selection procedures with particular attention paid to proportional and Boltzmann selection. In Proc. Fifth International Conference on Genetic Algorithms (Morgan Kaufmann, 1993).
- Yao, S. et al. ReAct: dynergizing reasoning and acting in language models. In Proc. International Conference on Learning Representations (2023).
- Banzhaf, W., Nordin, P., Keller, R. E. & Francone, F. D. Genetic Programming: An Introduction: On The Automatic Evolution of Computer Programs and its Applications (Morgan Kaufmann, 1998).
- Langdon, W. B. & Poli, R. Foundations of Genetic Programming (Springer Science & Business Media, 2013).
- Burke, E. et al. in Handbook of Metaheuristics (eds Glover, F. & Kochenberger, G. A.) 457–474 (Springer, 2003).
- Ross, P. in Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (eds Burke, E. K. & Kendall, G.) 529–556 (Springer, 2005).
Cited by
Darwin Godel Machine: Open-Ended Evolution of Self-Improving Agents
Zhang, J., Hu, S., Lu, C., Lange, R., & Clune, J. (2025) · arXiv · doi:10.48550/arxiv.2505.22954 · Cited by 344
Human-AI agency in the age of generative AI
Krakowski, S. (2025) · Information and Organization · doi:10.1016/j.infoandorg.2025.100560 · Cited by 162
Bewersdorff, A., Hartmann, C., Hornberger, M., Seßler, K., Bannert, M., Kasneci, E., Kasneci, G., Zhaı, X., & Nerdel, C. (2025) · Learning and Individual Differences · doi:10.1016/j.lindif.2024.102601 · Cited by 251
Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap
Wu, X., Wu, S.-H., Wu, J., Feng, L., & Tan, K. C. (2024) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2024.3506731 · Cited by 330
“…data cleaning methods [53], reward function design in reinforcement learning [52], [114], [115], automated AI accelerator design [54], mathematical and scientific discoveries [21], [117], decision-based adversarial attacks [116], and criticality evaluation of nodes in complex networks [118].”
InfluentialExtending Minds with Generative AI
Clark, A. (2025) · Nature Communications · doi:10.1038/s41467-025-59906-9 · Cited by 171
Metadata
- Authors
- Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., Kohli, P., & Fawzi, A.
- Affiliations
- Google DeepMind (United Kingdom) (GB)
- University of Wisconsin–Madison (US)
- Lyon 1 Université (FR)
- Corresponding author
- Fawzi, Alhussein
- ORCID
- Venue
- Nature
- Published
- 2023-12-14
- Volume
- 625
- Issue
- 7995
- Pages
- 468-475
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- PMC
- PMC10794145
- OpenAlex
- W4389727268
- Cited by
- 544
- References
- 73
- Citations by year
- 2026: 273 · 2025: 183 · 2024: 84 · 2023: 3
- FWCI
- 51.05
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- Nature (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- HAL (submittedVersion, cc-by)
- RePEc: Research Papers in Economics (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Keywords
- large language models, program search, evolutionary search, extremal combinatorics, online bin packing, heuristics, LLM hallucination
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
The claim verdicts this report counts are experimental: their accuracy is not yet measured.
A language model drew the claims from the paper on 2026-10-11, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-11 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Cited sources are checked with a language model’s help (gpt-6-sol and qwen3.8-omni-flash).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Mathematical discoveries from program search with large language models. https://app.cochat.ai/papers/10.1038/s41586-023-06924-6
- The paper
- Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., Kohli, P., & Fawzi, A. (2024). Mathematical discoveries from program search with large language models. Nature. https://doi.org/10.1038/s41586-023-06924-6
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.