10 ms·
FunSearch: Making new discoveries in mathematical sciences using LLMs
- mejutoco 3y agoI wonder how someone will integrate symbolic reasoning with LLMs, or if it will be possible.
- ignoramous 3y agoRelated commentary on "self-play" by Subbarao: https://twitter.com/rao2z/status/1728121216479949048 https://twitter.com/rao2z/status/1728121216479949048 From the article: 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. For websearch, I (evaluator) use pplx.ai and phind.com in a similar manner. Ask it a question (seed) and see what references it brings up (web links). Refine my question or ask follow-ups (iterate) so it pulls up different or more in-depth references (improve). Works better in unearthing gems than sifting through reddit or Google. Given Tech Twitter has amazing content too, looking forward to using Grok for research, now that it is open to all.
- alphabetting 3y agohttps://twitter.com/gfodor/status/1735348301812383906 https://twitter.com/gfodor/status/1735348301812383906 >If DeepMind just definitively proved neural networks can generate genuinely new knowledge then it’s the most important discovery since fire. If this were actually the case why wouldn't everyone be talking about this? I am impressed it was done on Palm 2 given that'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.
- dougmwne 3y agoI said “WOW!” out loud. An LLM can discover a new solution in high dimensional geometry that hasn’t advanced in 20 years!? That goes way beyond glueing little bits of plagiarized training data together in a plausible way. This suggest that there are hidden depths to LLMs’ capabilities if we can just figure out how to prompt and evaluate them correctly. This significantly broke my expectations. Who knows what discovery could be hiding behind the next prompt and random seed.
- bendergarcia 3y agoIt’s kind of like humans: seed of two people and a random interest to pursue, what could they do?!? It makes poverty and children dying unnecessarily even more depressing.
- riku_iki 3y ago> An LLM can discover a new solution in high dimensional geometry that hasn’t advanced in 20 years!? LLM + brute force coded by humans.
- dougmwne 3y agoAnd that not only created a human interpretable method, but beat out 20 years of mathematicians working on a high profile open question. Who’s to say our brains themselves aren’t brute force solution searchers?
- karencarits 3y agoOne of the problems they were approaching was the cap set problem https://en.m.wikipedia.org/wiki/Cap_set https://en.m.wikipedia.org/wiki/Cap_set > 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. > 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.
- aconz2 3y agosummary: given a program template/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 I think the prompt looks in principle something like 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 "prompt engineer" def foo(a, b): return a + {{}} They achieved the new results with only ~1e6 LLM calls (I think I'm reading that right) which seems impressively low. They talk about evaluating/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. 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
- stevenhuang 3y agoWonder where the goalposts will be moved now by the "stochastic parrot" parroters.
- lgessler 3y agoIdk if this work really bears on that argument. I can imagine Bender reacting to this by observing that this is a clever way of finding the needle (a good heuristic algorithm for an NP hard problem) in a haystack (millions of other heuristic algorithms that are bad, very bad, or maybe not even syntactically well-formed), and then saying that the fact that the model still produced so much garbage is proof that the LLM still doesn't really know how to reason or access meaning. And I think that'd be a good argument. OTOH, this system is not just an LLM, but an LLM and a bunch of additional components on top of it, and there might be different things to say about this system considered as a whole.
- airstrike 3y agoWe don't need LLMs to reason or to access meaning for them to be useful
- lgessler 3y agoSure, but I don't think even Bender or Marcus would deny their potential for practical utility, right? I think they mean to say that LLMs are not exactly as miraculous as they might seem, and very capable of misbehavior.
- cbb330 3y agoyour mind also conjectures many unreasonable and illogical solutions to things. then separately your mind has an "evaluator" to deduce a set of solutions down to things that make sense. Is anyone saying LLMs in isolation and without contextual tooling are miraculous? Even the text box for chatGPT is a form of wrapping LLM in a UX that is incrementally more miraculous.
- janalsncm 3y ago
- zackmorris 3y agoFunSearch 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: https://www.amazon.com/Genetic-Programming-III-Darwinian-Invention/dp/1558605436 https://www.amazon.com/Genetic-Programming-III-Darwinian-Inv... 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)/LLMs and grading them against an "evaluator" (wish they added more details about how it works). What the article didn'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'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't seen a good paper on whether that relationship is understood any better today. Also GPU/SIMD hardware isn'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've been in for 50 years is more about poor hardware decisions and socioeconomic factors than technical challenges with the algorithms. So I'm certain now that some combination of these old approaches will deliver AGI within 10 years. I'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'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!
- wolverine876 3y ago
- lgessler 3y agoTl;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't had a chance to read carefully yet so caveat lector.) Pretty impressive, but don't panic--we're not at the singularity yet.
- nybsjytm 3y agoSome 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't mean it's unrigorous.) But it's an interesting and possibly useful method of coming up with examples, pretty much a genetic algorithm with LLMs.
- mmaunder 3y agoRegardless of whether this is verifiably new knowledge, it'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.
- wait_a_minute 3y agoIs this the start of Singularity?
- rhosseinzadeh 3y agoI 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?).
- jcgrillo 3y agoTo what extent is an LLM necessary here? As far as I can tell (and perhaps I haven'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. 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]? So I guess my questions would be: (1) What's the value add of the LLM here? Does it substantially reduce the number of evaluations necessary to converge? If so, how? (2) Are other genetic programming techniques less competitive on the same problems? Do they produce less fit solutions? (3) If a more "traditional" genetic programming approach can achieve similar fitness, is there a difference in compute cost, including the cost to train the LLM? [1] http://www.davidmontana.net/papers/stgp.pdf http://www.davidmontana.net/papers/stgp.pdf [2] https://faculty.hampshire.edu/lspector/push.html https://faculty.hampshire.edu/lspector/push.html
- nybsjytm 3y agoThe found function is in here: https://github.com/google-deepmind/funsearch/blob/main/cap_set/cap_set.ipynb https://github.com/google-deepmind/funsearch/blob/main/cap_s.... I'm not very familiar with genetic algorithms but it's pretty hard for me to imagine that they couldn't come up with this. I'd be surprised if too many people (if any) have tried. On the other hand, as observed in Appendix A.2 of this paper, the non-LLM genetic approach would have to be engineered by hand more than the LLM approach.
- jcgrillo 3y agoI guess what I'm really trying to get at is this seems like a huge missed opportunity to show their LLM is actually doing something cool. Like if it somehow significantly outperforms established genetic programming update strategies that should be pretty easy to demonstrate given their experimental setup, but no attempt was made. That's kinda bizarre... like, in what sense is this an advancement of the field?
- 3y ago
- brotchie 3y agoParaphrasing a post on Twitter / X: Things will only get better from here. i.e. AI capabilities are strictly monotonically increasing (as they have been for decades), and in this case, the capabilities are recursively self-improving: I'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. I feel like we'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's AI models, once you have parts of a business flow hooked up with a LLM system (e.g. coding, customer support, bug triaging), "improving" the system amounts to swapping out the model name. We can expect a "everything kinda getting magically better" over the next few years, with minimal effort beyond the initial integration.
- jcgrillo 3y agoAFAICT neither the blog post nor the linked paper showed anything like this. Specifically, they didn't make any comparison between results obtained _with_ an LLM vs results obtained _without_ one. IIUC, this paper showed results obtained by genetic programming using an LLM to generate a python kernel function conforming (maybe) to a given type signature. You don't _need_ an LLM to do this. So the question of whether the LLM in particular does anything special here is still wide open.
- knicholes 3y agoWith 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.
- mnemotronic 3y agoGarbage in. Garbage out. It's useless unless it can provide a functional mathematical proof of correctness or, at the least, provide a process by with it's fictional composition can be proven or disproven.
- anonzzzies 3y agoFor me, this is the only right way for LLMs to go. Use them to trim search space for robustly designed logical programs/algo's we then use to do things. Part of the chain, not the end 'solution' of the chain.
- arkadiytehgraet 3y agoI 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. 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...
- Ericson2314 3y agoSpitting 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'll be on to something.
- JoelJacobson 3y agoThe 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. However, the GitHub repository for FunSearch doesn't include implementations for these LLMs. For instance, in `sampler.py`: ``` class LLM: """Language model that predicts continuation of provided source code.""" def __init__(self, samples_per_prompt: int) -> None: self._samples_per_prompt = samples_per_prompt def _draw_sample(self, prompt: str) -> str: """Returns a predicted continuation of `prompt`.""" raise NotImplementedError('Must provide a language model.') ``` This code suggests the need for an external LLM implementation. Given that they successfully used StarCoder, it'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.
- chengdujin 3y agoEnough talk, has anybody, replicated what Deepmind has done?