CoChat

Mathematical discoveries from program search with large language models

Open access

The 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

Crossref · 10.1038/s41586-023-06924-6

Cites

94 of 94 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Fig. 1 Overview of FunSearch. The input to FunSearch is a specification of the problem in the form of an ‘evaluate’ function, an initial implementation of the function to evolve, which can be trivial, and potentially a skeleton. At each iteration, FunSearch builds a prompt by combining several programs sampled from the programs database (favouring high-scoring ones). The prompt is then fed to the pretrained LLM and new programs are created. Newly created programs are then scored and stored in the programs database (if correct), thus closing the loop. The user can at any point retrieve the highest-scoring programs discovered so far.
Fig. 1 Overview of FunSearch. The input to FunSearch is a specification of the problem in the form of an ‘evaluate’ function, an initial implementation of the function to evolve, which can be trivial, and potentially a skeleton. At each iteration, FunSearch builds a prompt by combining several programs sampled from the programs database (favouring high-scoring ones). The prompt is then fed to the pretrained LLM and new programs are created. Newly created programs are then scored and stored in the programs database (if correct), thus closing the loop. The user can at any point retrieve the highest-scoring programs discovered so far.CC BY · PubMed Central
Fig. 2 Examples of FunSearch specifications for two problems. The ‘evaluate’ function takes as input a candidate solution to the problem, and returns a score assessing it. The ‘solve’ function contains the algorithm skeleton, which calls the function to evolve that contains the crucial logic. a, Cap set. The function to evolve is called ‘priority’. b, Online bin packing. The function to evolve is called ‘heuristic’. The ‘main’ function implements the evaluation procedure by connecting the pieces together. Specifically, it uses the ‘solve’ function to solve the problem and then scores the resulting solutions using the ‘evaluate’ function. In the simplest cases, ‘main’ just executes ‘solve’ once and uses ‘evaluate’ to score the output, for example, a. In specific settings such as online algorithms, the ‘main’ function implements some more logic, for example, b.
Fig. 2 Examples of FunSearch specifications for two problems. The ‘evaluate’ function takes as input a candidate solution to the problem, and returns a score assessing it. The ‘solve’ function contains the algorithm skeleton, which calls the function to evolve that contains the crucial logic. a, Cap set. The function to evolve is called ‘priority’. b, Online bin packing. The function to evolve is called ‘heuristic’. The ‘main’ function implements the evaluation procedure by connecting the pieces together. Specifically, it uses the ‘solve’ function to solve the problem and then scores the resulting solutions using the ‘evaluate’ function. In the simplest cases, ‘main’ just executes ‘solve’ once and uses ‘evaluate’ to score the output, for example, a. In specific settings such as online algorithms, the ‘main’ function implements some more logic, for example, b.CC BY · PubMed Central
Fig. 3 Diagram of a cap set of size four in Z3². The circles are the elements of Z3² with the ones belonging to the cap set shown in blue. The possible lines in Z3² are also shown (with colours indicating lines that wrap around in arithmetic modulo 3). No three elements of the cap set are in a line.
Fig. 3 Diagram of a cap set of size four in Z3². The circles are the elements of Z3² with the ones belonging to the cap set shown in blue. The possible lines in Z3² are also shown (with colours indicating lines that wrap around in arithmetic modulo 3). No three elements of the cap set are in a line.CC BY · PubMed Central
Fig. 4 Result of applying FunSearch to the cap set problem. a, Size of the largest cap set in Z3ⁿ for different dimensions n. b, The function ‘priority’ : Z3ⁿ→R discovered by FunSearch that results in a cap set of size 512 in n = 8 dimensions. One feature to note is that the priority is affected by whether the same entry appears in positions i and −i (−i denotes the ith position counting from the end). This motivates the notion of reflections, used in c. c, An explicit construction of this new 512-cap, which we were able to manually construct thanks to having discovered the cap set by searching in function space. See Supplementary Information Appendix E.2 for more details and for relation to Hill cap.
Fig. 4 Result of applying FunSearch to the cap set problem. a, Size of the largest cap set in Z3ⁿ for different dimensions n. b, The function ‘priority’ : Z3ⁿ→R discovered by FunSearch that results in a cap set of size 512 in n = 8 dimensions. One feature to note is that the priority is affected by whether the same entry appears in positions i and −i (−i denotes the ith position counting from the end). This motivates the notion of reflections, used in c. c, An explicit construction of this new 512-cap, which we were able to manually construct thanks to having discovered the cap set by searching in function space. See Supplementary Information Appendix E.2 for more details and for relation to Hill cap.CC BY · PubMed Central
Fig. 5 Results on the cap set problem through admissible sets. a, Summary of lower bounds on the cap set capacity C. b, The ‘priority’ function ({0,1,2})ⁿ→R discovered by FunSearch that results in an I(12,7) admissible set. The source code shows that when n = 12, the function treats the four triples of coordinates {0, 4, 8}, {1, 5, 9}, {2, 6, 10} and {3, 7, 11} together. We then checked that the admissible set is in fact symmetric under independent cyclic permutations of coordinates within each of these four triples. See Supplementary Information Appendices D and E.3 for more details.
Fig. 5 Results on the cap set problem through admissible sets. a, Summary of lower bounds on the cap set capacity C. b, The ‘priority’ function ({0,1,2})ⁿ→R discovered by FunSearch that results in an I(12,7) admissible set. The source code shows that when n = 12, the function treats the four triples of coordinates {0, 4, 8}, {1, 5, 9}, {2, 6, 10} and {3, 7, 11} together. We then checked that the admissible set is in fact symmetric under independent cyclic permutations of coordinates within each of these four triples. See Supplementary Information Appendices D and E.3 for more details.CC BY · PubMed Central
Fig. 6 Example of a short online bin packing heuristic discovered by FunSearch for the OR dataset. This example illustrates frequently observed behaviour: instead of always packing items into the best fit bin, the heuristic encourages packing the item only if the fit is tight. Comments in the code were manually added. See Supplementary Information Appendix C for more discovered heuristics.
Fig. 6 Example of a short online bin packing heuristic discovered by FunSearch for the OR dataset. This example illustrates frequently observed behaviour: instead of always packing items into the best fit bin, the heuristic encourages packing the item only if the fit is tight. Comments in the code were manually added. See Supplementary Information Appendix C for more discovered heuristics.CC BY · PubMed Central
Extended Data Fig. 1 Example of best-shot prompting, based on the skeleton from Fig. 2a. The prompt includes k = 2 implementations sampled from the programs database, with higher-scoring implementations being more likely to be included.
Extended Data Fig. 1 Example of best-shot prompting, based on the skeleton from Fig. 2a. The prompt includes k = 2 implementations sampled from the programs database, with higher-scoring implementations being more likely to be included.CC BY · PubMed Central
Extended Data Fig. 2 Evolutionary method. The initial programs are separated into islands and each of them is evolved separately. After a number of iterations, the islands with the worst score are wiped and the best program from the islands with the best score are placed in the empty islands. Evolution then proceeds separately again until the next reset. This process is repeated until termination.
Extended Data Fig. 2 Evolutionary method. The initial programs are separated into islands and each of them is evolved separately. After a number of iterations, the islands with the worst score are wiped and the best program from the islands with the best score are placed in the empty islands. Evolution then proceeds separately again until the next reset. This process is repeated until termination.CC BY · PubMed Central
Extended Data Fig. 3 Program clusters within islands. Within each island, programs are grouped into clusters based on their signature (i.e., their scores on several inputs). We first sample clusters, favoring the ones with higher score. Within the chosen clusters, we sample a program, favoring shorter programs. The sampled programs are used to prompt the LLM which generates a new program. If the new program is correct, it is added to the island, either in an existing cluster or a new one if its signature was not yet present.
Extended Data Fig. 3 Program clusters within islands. Within each island, programs are grouped into clusters based on their signature (i.e., their scores on several inputs). We first sample clusters, favoring the ones with higher score. Within the chosen clusters, we sample a program, favoring shorter programs. The sampled programs are used to prompt the LLM which generates a new program. If the new program is correct, it is added to the island, either in an existing cluster or a new one if its signature was not yet present.CC BY · PubMed Central

Verification

Claims the paper makes

8 Valid · 1 Not valid · 11 Not checked · 67 Own results and interpretations

41 more claims

Create a free account to see all 87 claims and to verify the 2 references still open.

See all claims — free account
  • Probably not a substantial claim. 18
  • It may state two separate claims as one. 27
  • The quote only partly states this claim. 1

Create a free account to see these claims.

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?

4 more claims about this paper

Create a free account to see every claim other papers make about this one.

See all claims — free account

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.

1 of 1

Citations

Cites

1 retracted

Show all 94 references

Research works printed but not linked: 9

  1. Tanese, R. Distributed Genetic Algorithms for Function Optimization. PhD thesis, Univ. Michigan (1989).
  2. Cantú-Paz, E. A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systemes Repartis 10, 141–171 (1998).
  3. Hill, R. On the largest size of cap in S5,3. Rend Lincei. Sci. Fis. Mat. Nat. 54, 378–384 (1973).
  4. 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).
  5. Yao, S. et al. ReAct: dynergizing reasoning and acting in language models. In Proc. International Conference on Learning Representations (2023).
  6. 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).
  7. Langdon, W. B. & Poli, R. Foundations of Genetic Programming (Springer Science & Business Media, 2013).
  8. Burke, E. et al. in Handbook of Metaheuristics (eds Glover, F. & Kochenberger, G. A.) 457–474 (Springer, 2003).
  9. 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

See all 544

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
Venue
Nature
Published
2023-12-14
Volume
625
Issue
7995
Pages
468-475
ISSN
  • 0028-0836 (ISSN-L)
  • 1476-4687
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
Licence
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.