FunSearch: Making new discoveries in mathematical sciences using LLMs

To what extent is an LLM necessary here? As far as I can tell (and perhaps I haven&#x27;t looked closely enough yet) the purpose of the LLM here is to generate things that look plausibly like python functions conforming to a given type signature.<p>But it should be possible to generate random, correct python functions conforming to a given type signature without an LLM. This would be an exercise like [1], just with a substantially more complex language. But might a restricted language be more ergonomic? Something like PushGP [2]?<p>So I guess my questions would be:<p>(1) What&#x27;s the value add of the LLM here? Does it substantially reduce the number of evaluations necessary to converge? If so, how?<p>(2) Are other genetic programming techniques less competitive on the same problems? Do they produce less fit solutions?<p>(3) If a more &quot;traditional&quot; genetic programming approach can achieve similar fitness, is there a difference in compute cost, including the cost to train the LLM?<p>[1] <a href="http:&#x2F;&#x2F;www.davidmontana.net&#x2F;papers&#x2F;stgp.pdf" rel="nofollow noreferrer">http:&#x2F;&#x2F;www.davidmontana.net&#x2F;papers&#x2F;stgp.pdf</a> [2] <a href="https:&#x2F;&#x2F;faculty.hampshire.edu&#x2F;lspector&#x2F;push.html" rel="nofollow noreferrer">https:&#x2F;&#x2F;faculty.hampshire.edu&#x2F;lspector&#x2F;push.html</a>

Some important context: the discovery is that a certain number in combinatorics is now known to be between 2.2202 and 2.756, not just between 2.218 and 2.756 as discovered last year. The improvement is by finding some particular sequences of numbers which have some special properties, not by a logic-heavy mathematical proof. (That doesn&#x27;t mean it&#x27;s unrigorous.)<p>But it&#x27;s an interesting and possibly useful method of coming up with examples, pretty much a genetic algorithm with LLMs.

Related commentary on &quot;self-play&quot; by Subbarao: <a href="https:&#x2F;&#x2F;twitter.com&#x2F;rao2z&#x2F;status&#x2F;1728121216479949048" rel="nofollow noreferrer">https:&#x2F;&#x2F;twitter.com&#x2F;rao2z&#x2F;status&#x2F;1728121216479949048</a><p>From the article:<p><pre><code> FunSearch uses an evolutionary method powered by LLMs, which promotes and develops the highest scoring ideas. These ideas are expressed as computer programs, so that they can be run and evaluated automatically. The user writes a description of the problem in the form of code. This description comprises a procedure to evaluate programs, and a seed program used to initialize a pool of programs. At each iteration, FunSearch selects some programs from the current pool. The LLM creatively builds upon these, and generates new programs, which are automatically evaluated. The best ones are added back to the pool of existing programs, creating a self-improving loop. </code></pre> For websearch, I (<i>evaluator</i>) use <i>pplx.ai</i> and <i>phind.com</i> in a similar manner. Ask it a question (<i>seed</i>) and see what references it brings up (web links). Refine my question or ask follow-ups (<i>iterate</i>) so it pulls up different or more in-depth references (<i>improve</i>). Works better in unearthing gems than sifting through reddit or Google.<p>Given <i>Tech Twitter</i> has amazing content too, looking forward to using Grok for research, now that it is open to all.

<a href="https:&#x2F;&#x2F;twitter.com&#x2F;gfodor&#x2F;status&#x2F;1735348301812383906" rel="nofollow noreferrer">https:&#x2F;&#x2F;twitter.com&#x2F;gfodor&#x2F;status&#x2F;1735348301812383906</a><p>&gt;If DeepMind just definitively proved neural networks can generate genuinely new knowledge then it’s the most important discovery since fire.<p>If this were actually the case why wouldn&#x27;t everyone be talking about this? I am impressed it was done on Palm 2 given that&#x27;s less advanced than GPT-4 and Gemini. Will be wild to see what the next few generations of models can do utilizing methods like this.

summary: given a program template&#x2F;skeleton and a fitness function (# correct results, shorter programs, etc), generate a population of programs with LLM, use a prompt that generates a new program from k other versions (they found k=2 is good, kinda biological eh), run the programs on inputs and score them with the fitness function, uses the island model for evolution<p>I think the prompt looks in principle something like<p><pre><code> def foo_v1(a, b): ... def foo_v2(a, b): ... # generate me a new function using foo_v1 and foo_v2. You can only change things inside two double curly braces like THIS in {{ THIS }} # idk not a &quot;prompt engineer&quot; def foo(a, b): return a + {{}} </code></pre> They achieved the new results with only ~1e6 LLM calls (I think I&#x27;m reading that right) which seems impressively low. They talk about evaluating&#x2F;scoring taking minutes. Interesting to think about the depth vs breadth tradeoff here which is tied to the latency vs throughput of scoring an individual vs population. What if you memoize across all programs. Can you keep the loss function multidimensional (1d per input or input bucket) so that you might find a population of programs that do well in different areas first and then it can work on combining them.<p>Did we have any prior on how rare the cap set thing is? Had there been previous computational efforts at this to no avail? Cool nonetheless

Paraphrasing a post on Twitter &#x2F; X:<p>Things will only get better from here.<p>i.e.<p>AI capabilities are strictly monotonically increasing (as they have been for decades), and in this case, the capabilities are recursively self-improving: I&#x27;m already seeing personal ~20-30% productivity gains in coding with AI auto-complete, AI-based refactoring, and AI auto-generated code review diffs from comments.<p>I feel like we&#x27;ve hit a Intel-in-the-90s era of AI. To make your code 2x as fast, you just had to wait for the next rev. of Intel CPUs. Now it&#x27;s AI models, once you have parts of a business flow hooked up with a LLM system (e.g. coding, customer support, bug triaging), &quot;improving&quot; the system amounts to swapping out the model name.<p>We can expect a &quot;everything kinda getting magically better&quot; over the next few years, with minimal effort beyond the initial integration.

One of the problems they were approaching was the cap set problem<p><a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Cap_set" rel="nofollow noreferrer">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Cap_set</a><p>&gt; The problem consists of finding the largest set of points (called a cap set) in a high-dimensional grid, where no three points lie on a line. This problem is important because it serves as a model for other problems in extremal combinatorics - the study of how large or small a collection of numbers, graphs or other objects could be. Brute-force computing approaches to this problem don’t work – the number of possibilities to consider quickly becomes greater than the number of atoms in the universe.<p>&gt; FunSearch generated solutions - in the form of programs - that in some settings discovered the largest cap sets ever found. This represents the largest increase in the size of cap sets in the past 20 years. Moreover, FunSearch outperformed state-of-the-art computational solvers, as this problem scales well beyond their current capabilities.

I wonder how someone will integrate symbolic reasoning with LLMs, or if it will be possible.

The recent DeepMind paper on FunSearch highlighted their use of pre-trained large language models (LLMs) for generating code improvements. Interestingly, while the main LLM used was Codey, built on the PaLM2 model family, they also referenced StarCoder, an open-source LLM, in their supplementary information.<p>However, the GitHub repository for FunSearch doesn&#x27;t include implementations for these LLMs. For instance, in `sampler.py`:<p>``` class LLM: &quot;&quot;&quot;Language model that predicts continuation of provided source code.&quot;&quot;&quot;<p><pre><code> def __init__(self, samples_per_prompt: int) -&gt; None: self._samples_per_prompt = samples_per_prompt def _draw_sample(self, prompt: str) -&gt; str: &quot;&quot;&quot;Returns a predicted continuation of `prompt`.&quot;&quot;&quot; raise NotImplementedError(&#x27;Must provide a language model.&#x27;)</code></pre> ```<p>This code suggests the need for an external LLM implementation. Given that they successfully used StarCoder, it&#x27;s surprising that no integration guide or basic implementation for it (or any similar open-source LLM) is provided. Such an inclusion would have significantly enhanced the reproducibility and accessibility of their research.

Regardless of whether this is verifiably new knowledge, it&#x27;s an interesting case study when you consider limiting access to AI based on model size or some other regulatory measure, and the unfair advantage that confers on corporations that do discover new knowledge or laws of nature, and can monetize them without sharing.

I have been wondering recently about a good test for checking whether LLMs can only parrot stochastically or do they manage to indeed learn some higher order concepts inside their weights.<p>What if we would take a bare LLM, train it only on the information (in Maths, physics, etc) that was available to, say, Newton and then try to prompt it to solve the problems that Newton solved? Will it be able to derive the calculus basics and stuff having never seen it before, maybe even with little bit of help from the prompts? Maybe it will be able to come up with something completely different, yet also useful? Or nothing at all...

FunSearch is more along the lines of how I wanted AI to evolve over the last 20 years or so, after reading Genetic Programming III by John Koza:<p><a href="https:&#x2F;&#x2F;www.amazon.com&#x2F;Genetic-Programming-III-Darwinian-Invention&#x2F;dp&#x2F;1558605436" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.amazon.com&#x2F;Genetic-Programming-III-Darwinian-Inv...</a><p>I wanted to use genetic algorithms (GAs) to come up with random programs run against unit tests that specify expected behavior. It sounds like they are doing something similar, finding potential solutions with neural nets (NNs)&#x2F;LLMs and grading them against an &quot;evaluator&quot; (wish they added more details about how it works).<p>What the article didn&#x27;t mention is that above a certain level of complexity, this method begins to pull away from human supervisors to create and verify programs faster than we can review them. When they were playing with Lisp GAs back in the 1990s on Beowulf clusters, they found that the technique works extremely well, but it&#x27;s difficult to tune GA parameters to evolve the best solutions reliably in the fastest time. So volume III was about re-running those experiments multiple times on clusters about 1000 times faster in the 2000s, to find correlations between parameters and outcomes. Something similar was also needed to understand how tuning NN parameters affects outcomes, but I haven&#x27;t seen a good paper on whether that relationship is understood any better today.<p>Also GPU&#x2F;SIMD hardware isn&#x27;t good for GAs, since video cards are designed to run one wide algorithm instead of thousands or millions of narrow ones with subtle differences like on a cluster of CPUs. So I feel that progress on that front has been hindered for about 25 years, since I first started looking at programming FPGAs to run thousands of MIPS cores (probably ARM or RISC-V today). In other words, the perpetual AI winter we&#x27;ve been in for 50 years is more about poor hardware decisions and socioeconomic factors than technical challenges with the algorithms.<p>So I&#x27;m certain now that some combination of these old approaches will deliver AGI within 10 years. I&#x27;m just frustrated with myself that I never got to participate, since I spent all of those years writing CRUD apps or otherwise hustling in the struggle to make rent, with nothing to show for it except a roof over my head. And I&#x27;m disappointed in the wealthy for hoarding their money and not seeing the potential of the countless millions of other people as smart as they are who are trapped in wage slavery. IMHO this is the great problem of our time (explained by the pumping gas scene in Fight Club), although since AGI is the last problem in computer science, we might even see wealth inequality defeated sometime in the 2030s. Either that or we become Borg!

Tl;dr in my words after a skim: this is a method for using LLMs to find new, SOTA (or at least very good?) heuristic algorithms for NP hard combinatorial optimization problems. They achieve this not by making the LLM itself smarter but by finding a way to keep only its best ideas. (Haven&#x27;t had a chance to read carefully yet so caveat lector.)<p>Pretty impressive, but don&#x27;t panic--we&#x27;re not at the singularity yet.

I wonder what would happen if this was applied to alpha code. Instead of generating 1 million codes for each problem during inference, do this kind of iteration during training and then generate less codes for each problem (or generate 1 million but hopefully better ones?).

For me, this is the only right way for LLMs to go. Use them to trim search space for robustly designed <i>logical</i> programs&#x2F;algo&#x27;s we then use to do things. Part of the chain, not the end &#x27;solution&#x27; of the chain.

With the universal approximation theorem, we can use artificial neutral networks with ReLUs to accurately approximate a function. But we just get weights out of it at the end. This approach feels similar, but provides code in the end.

Spitting out some Python is weak sauce. The next version of this I think will spit out Lean, or at the first great version. Then we&#x27;ll be on to something.

Enough talk, has anybody, replicated what Deepmind has done?

Garbage in. Garbage out. It&#x27;s useless unless it can provide a functional mathematical proof of correctness or, at the least, provide a process by with it&#x27;s fictional composition can be proven or disproven.

Wonder where the goalposts will be moved now by the &quot;stochastic parrot&quot; parroters.

Is this the start of Singularity?