FunSearch

What FunSearch is

FunSearch is a method for getting a large language model to contribute to hard mathematical and computational problems. The name stands for "searching in the function space," which points at its central choice: instead of asking a model for a solution, it asks for a program that describes how to solve the problem.^[1] It was introduced in a paper published in Nature on 14 December 2023, in volume 625, pages 468 to 475.^[1] The first author is Bernardino Romera-Paredes; Alexander Novikov and Matej Balog are among the co-authors.^[1]

How it works

FunSearch pairs a pretrained large language model with a systematic evaluator inside an evolutionary loop.^[1] The model proposes candidate programs — small functions that describe a way of attacking the problem — and the evaluator scores each one automatically. High-scoring programs are kept, and the model is asked for variations and combinations of them; the cycle repeats, so the pool of programs improves over successive rounds.

The design is explicitly framed as a way around hallucination, which the authors say has limited the use of large language models in scientific discovery.^[1] Because every proposal is scored by an evaluator that does not depend on the model's own judgment, a confident but wrong program is simply discarded rather than believed. The loop, not the model alone, is what carries the search forward.

The authors also argue that discovered programs tend to be more interpretable than raw solutions, which lets domain experts feed back into the search.^[1] A solution handed over as a finished object — a list of points, a schedule, a number — can be hard to reason about. A program that builds the object can be read, checked, and then modified by a person who knows the problem, and those modifications can go back into the loop.

Results

The paper reports two applications. The first is the cap set problem in extremal combinatorics, which asks for the largest collection of points in a discrete grid with no three of them lying on a straight line. FunSearch found constructions larger than the best known ones, in both finite-dimensional and asymptotic cases.^[1]

The second is online bin packing, an everyday scheduling problem in which items arrive one at a time and must be placed into bins of fixed capacity before the next item — and the future items — are known. There, FunSearch found new heuristics that improve on widely used baselines.^[1]

Why it matters

The paper presents its results as evidence that large language models can make discoveries on established open problems.^[1] That is a narrower and more testable claim than the general hope that such models will automate science: the targets were problems with a long history, a clear scoring rule for any proposed answer, and a recognised best-known result to beat.

The two case studies also show the two halves of the method doing different work. The cap set results show that a program search can reach constructions that people had not written down; the bin packing results show that the same machinery can yield heuristics that are useful in a practical setting and can be compared against widely used baselines. Both rest on the same premise: the model is a source of variation, and the evaluator is the judge.