Skip to content
The methodOpen data
Back to the collection

Mathematical discoveries from program search with large language models

Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov

Show all 12 authors

Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi

2023 · Nature

Language modelsMathematicsScience & research
Read the paper
HN score
0
Mentions
8
Readers
8
Months
4
What’s in a score?

From the 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.

Metadata: Crossref. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

8 selected excerpts · 8 total mentions

geraneum
Neutral mention · rule
This has become a common recurrence recently. Have a problem with clear definition and evaluation function. Let LLM reduce the size of solution space. LLMs are very good at pattern reconstruction, and if the solution has a similar pattern to what was known before, it can work very well. In this case the problem is a specific type of security vulnerability and the evaluator is the expert. This is similar in spirit to other recent endeavors where LLMs are used in genetic optimization; on a different scale. Here’s an interesting read on “Mathematical discoveries from program search with large language models” which was I believe was also featured in HN the past: https://www.nature.com/articles/s41586-023-06924-6 One small note, concluding that the LLM is “reasoning” about code just _based on this experiment_ is bit of a stretch IMHO.
Original comment I used o3 to find a remote zeroday in the Linux SMB implementation
dimatura
Neutral mention · rule
Note that genetic programming is a specific subset of genetic algorithms that focuses on searching for "programs" (hence the name), typically encoded in the form of a tree structure similar to an AST, though other representations exist. In theory, you could use GP for almost any situation where you'd want to synthesize a mathematical expression or piece of code for which you have a criteria to optimize (i.e. "fitness"). In practice, since GPs are basically just semi-randomly searching a huge combinatorial space, they tend to work best in low-dimensional problems, ideally with a fitness function that is cheap to evaluate. They can work nicely for finding nonlinear symbolic…
Read the full comment
formulas for regression, for example. But there's also some other cool results over the years - Hod Lipson has published several cool results in robotics with them. Until a few years ago, the popular deep learning methods like CNNs weren't great at that kind of thing, but LLMs definitely changed that - it's safe to say that by drawing on huge amounts of data LLMs are much better at most practical programming tasks. They're not necessarily a complete replacement though, there's definitely space for hybrid approaches, eg https://arxiv.org/abs/2401.07102 or https://www.nature.com/articles/s41586-023-06924-6.
Original comment Baby Steps into Genetic Programming
guyomes
Neutral mention · rule
> OpenAI is betting heavily on code as a way to improve LLM reasoning for AGI. And researchers from Google Deepmind, University of Wisconsin-Madison and Laboratoire de l’Informatique du Parallélisme, University of Lyon, actually publish some of their results in that direction [1,2]. [1]: https://deepmind.google/discover/blog/funsearch-making-new-d... [2]: https://www.nature.com/articles/s41586-023-06924-6
Original comment Codestral: Mistral's Code Model
t_mann
Neutral mention · rule
It's from May, pity, it would have been really interesting if the author had discussed DeepMind's recent FunSearch paper as well: https://www.nature.com/articles/s41586-023-06924-6 But it goes to show just how fast we are currently progressing.
Original comment How is AI impacting science?
nicklecompte
Neutral mention · rule
Really worth going to the actual paper[1] instead of this rather shameful press release - the second sentence in particular deflates the optimistic mood: "The effectiveness of FunSearch in discovering new knowledge for hard problems might seem intriguing. We believe that the LLM used within FunSearch does not use much context about the problem; the LLM should instead be seen as a source of diverse (syntactically correct) programs with occasionally interesting ideas. When further constrained to operate on the crucial part of the algorithm with a program skeleton, the LLM provides suggestions that marginally improve over existing ones in the population, which ultimately…
Read the full comment
results in discovering new knowledge on open problems when combined with the evolutionary algorithm. Another crucial component of the effectiveness of FunSearch is that it operates in the space of programs: rather than directly searching for constructions (which is typically an enormous list of numbers), FunSearch searches for programs generating those constructions. Because most problems we care about are structured (highly non-random), we hypothesize that solutions are described more concisely with a computer program, compared to other representations." It is perhaps unfair to say that DeepMind has brute-forced generating programs rather than brute-forcing a single program that generates an answer - but effectively that's what they did, and it's a very cool idea! They did the same with "DeepTensor" or whatever their program for finding matrix multiplication algorithms was called. I am not denying that this is a useful direction for computational mathematics research - I have personally spent a lot of time blindly fiddling with SAGE hoping the computer will spit out a nicer answer. Having this process automated seems useful. But saying that this tech "outdoes human mathematicians" is pure dishonesty, very much like saying MATLAB "outdoes human physicists" at understanding fluid mechanics. FunSearch doesn't understand what a set is (or even what a number is), any more than MATLAB understands what viscosity is. LLMs are still much worse at actual quantitative reasoning than pigeons or mice, let alone humans. [1] https://www.nature.com/articles/s41586-023-06924-6
Original comment DeepMind AI outdoes human mathematicians on unsolved problem
westurner
Neutral mention · rule
"Mathematical discoveries from program search with large language models" (2023) https://www.nature.com/articles/s41586-023-06924-6 "DeepMind AI outdoes human mathematicians on unsolved problem" (2023) https://www.nature.com/articles/d41586-023-04043-w : > Large language model improves on efforts to solve combinatorics problems inspired by the card game Set.
Original comment DeepMind AI outdoes human mathematicians on unsolved problem

Keep following the thread.

More in Language models

More from the same topics.

1994arXiv

On proof and progress in mathematics

William P. Thurston

In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.

Mathematics
29 mentions21 months
9HN score