5 ms·

To 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 thing

To 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 ago
The 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 ago
  I 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?
  - resource0x 3y ago
    They need to show something to keep the excitement around Google's upcoming AI alive. Expect a slew of (non-)discoveries to continue unabated going forward.
janalsncm 3y ago
> it should be possible to generate random, correct python functions conforming to a given type signature without an LLM The state space of viable programs is far, far larger than useful ones. You need more than monkeys and typewriters. The point of using Palm2 here is that you don’t want your candidates to be random, you want them to be plausible so you’re not wasting time on nonsensical programs. Further, a genetic algorithm with random program generation will have a massive cold start problem. You’re not going to make any progress in the beginning, and probably ever, if the fitness of all of your candidates is zero.
- jcgrillo 3y ago
  That's an interesting hypothesis, but the work under discussion here didn't make an attempt to test it. You make two claims: (1) That using an LLM (Palm2) somehow "saved time" by avoiding "nonsensical programs" (2) That there exists a "cold start problem" (which, presumably, the LLM somehow solves). Yet not the paper, nor the blog post, nor the code on github support these.
  - famouswaffles 3y ago
    What paper are you reading exactly ? There's a clear comparison https://imgur.com/a/xerOOLn https://imgur.com/a/xerOOLn
    - jcgrillo 3y ago
      Same paper you are. This is comparing apples to oranges. Their "random" strategy is only capable of assembling very constrained python programs whereas the LLM is coming up with things that look like the sort of stuff a person might write, utilizing the whole language (modulo hallucinatory nonsense). So it's not a reasonable comparison at all. Instead, for the purpose of making something resembling a reasonable comparison, it would make a lot more sense to train an LLM on programs written in the same language they allow their "random" strategy to use. I wouldn't recommend trying this in python, as it's way too big a language. Something smaller and more fit for purpose would likely be much more tractable. There are multiple examples from the literature to choose from. EDIT: To be clear--it's obvious the LLM solution outperformed the hand-rolled solution. By a large margin. What would actually be an interesting scientific question, though, is to what extent is the success attributable to the LLM? That's not possible to answer given the results, because the hand rolled-solution and the LLM solution are literally speaking different languages.
nopinsight 3y ago
Genetic algorithms, even with programmed constraints, will come up with many non-sensical programs, although they could be mostly syntactically correct (given sufficient effort). The difference LLMs make here is to limit the space of possible mutations to largely semantically plausible programs. The above should answer your 1) and 2). On 3), a trained LLM is useful for many, many purposes, so the cost of training it from scratch after amortization wouldn't be significant. It may cost additionally to fine-tune an LLM to work in the FunSearch framework but fine-tuning cost is quite minimal. Using it in the framework is likely a win over genetic programming alone.
- jcgrillo 3y ago
  > The difference LLMs make here is to limit the space of possible mutations to largely semantically plausible programs. Yet, sadly, the work under question here didn't make any attempt to show this, AFAICT. It's an interesting hypothesis, but as yet untested. > a trained LLM is useful for many, many purposes, so the cost of training it from scratch after amortization wouldn't be significant. It may cost additionally to fine-tune an LLM to work in the FunSearch framework but fine-tuning cost is quite minimal. Using it in the framework is likely a win over genetic programming alone. Again, an interesting hypothesis that probably could be investigated with the experimental apparatus described in the paper. But it wasn't. Have you?
  - nopinsight 3y ago
    >> The difference LLMs make here is to limit the space of possible mutations to largely semantically plausible programs. > Yet, sadly, the work under question here didn't make any attempt to show this, AFAICT. It's an interesting hypothesis, but as yet untested. It would be ideal to do that. But given the way LLMs work, it is almost a given. This could be the reason it didn't occur to the researchers who are very familiar with LLMs. >> a trained LLM is useful for many, many purposes, so the cost of training it from scratch after amortization wouldn't be significant. It may cost additionally to fine-tune an LLM to work in the FunSearch framework but fine-tuning cost is quite minimal. Using it in the framework is likely a win over genetic programming alone. > Again, an interesting hypothesis that probably could be investigated with the experimental apparatus described in the paper. But it wasn't. Have you? Perhaps it's quite evident to people in the trench, as the hypothesis seems very plausible to me. A numerical confirmation would be ideal as you suggested. Given my management experience, I'd say it's smart of them to focus their limited resources on something more innovative in this exploratory work. Details can be left for future work or worked out by other teams.
deleted 3y ago
[deleted]
mejutoco 3y ago
> (1) What's the value add of the LLM here? Does it substantially reduce the number of evaluations necessary to converge? If so, how? I thought that stochastic (random) gradient descent and LLM were converging much quicker than genetic programming. Definitely much quicker than random search.
anonzzzies 3y ago
Inductive program synthesis stood still for decades because the space is far too large to get anything beyond absolutely trivial programs; LLMs vastly trim (in many wrong ways too of course) the search space and then you can apply ips to finetune and test. You cannot do this (not in any way we know of) without LLMs because it just tests billions of programs that make absolutely no sense even for trivial cases.
- YeGoblynQueenne 3y ago
  Quantify "vastly trim" for me please. All I see is a firehose of compute that spams and spams millions of samples until it hits a lucky guess. That's not trimming anything, it's the computing equivalent of the human wave attack. But, please quantify "vastly trim". Edit: the subject of my PhD research was an inductive program synthesis approach and while I agree with the bit about the size of program search spaces, LLMs are very clearly not a solution to that. Deepmind's "solution" is instead their massive computational capacity which makes it possible to search deeper and wider in the search space of Python programs. FunSearch is like one of those rocket cars that people make once in a while to break land speed records. Extremely expensive, extremely impractical and terminally over-specialised to do one thing, and do that thing only. And, ultimately, a bit of a show.
  - anonzzzies 3y ago
    Well the approach we use (and has been used at MS research before gpt was a thing) is to ask the llm to provide guesses for instructions to get to a (sub) solution and then let ips (in prolog in our case) do the rest. It seems to work for what we are doing. Disclaimer: did my dissertation on ips (with genetic programming), but in the 90s when we basically had no computer power. The results were horrible outside trivialities, now they aren't anymore.
    - deleted 3y ago
      [deleted]
    - deleted 3y ago
      [deleted]

nybsjytm 3y ago

The 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 ago
I 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?
- resource0x 3y ago
  They need to show something to keep the excitement around Google's upcoming AI alive. Expect a slew of (non-)discoveries to continue unabated going forward.

janalsncm 3y ago

> it should be possible to generate random, correct python functions conforming to a given type signature without an LLM The state space of viable programs is far, far larger than useful ones. You need more than monkeys and typewriters. The point of using Palm2 here is that you don’t want your candidates to be random, you want them to be plausible so you’re not wasting time on nonsensical programs. Further, a genetic algorithm with random program generation will have a massive cold start problem. You’re not going to make any progress in the beginning, and probably ever, if the fitness of all of your candidates is zero.

jcgrillo 3y ago
That's an interesting hypothesis, but the work under discussion here didn't make an attempt to test it. You make two claims: (1) That using an LLM (Palm2) somehow "saved time" by avoiding "nonsensical programs" (2) That there exists a "cold start problem" (which, presumably, the LLM somehow solves). Yet not the paper, nor the blog post, nor the code on github support these.
- famouswaffles 3y ago
  What paper are you reading exactly ? There's a clear comparison https://imgur.com/a/xerOOLn https://imgur.com/a/xerOOLn
  - jcgrillo 3y ago
    Same paper you are. This is comparing apples to oranges. Their "random" strategy is only capable of assembling very constrained python programs whereas the LLM is coming up with things that look like the sort of stuff a person might write, utilizing the whole language (modulo hallucinatory nonsense). So it's not a reasonable comparison at all. Instead, for the purpose of making something resembling a reasonable comparison, it would make a lot more sense to train an LLM on programs written in the same language they allow their "random" strategy to use. I wouldn't recommend trying this in python, as it's way too big a language. Something smaller and more fit for purpose would likely be much more tractable. There are multiple examples from the literature to choose from. EDIT: To be clear--it's obvious the LLM solution outperformed the hand-rolled solution. By a large margin. What would actually be an interesting scientific question, though, is to what extent is the success attributable to the LLM? That's not possible to answer given the results, because the hand rolled-solution and the LLM solution are literally speaking different languages.

nopinsight 3y ago

Genetic algorithms, even with programmed constraints, will come up with many non-sensical programs, although they could be mostly syntactically correct (given sufficient effort). The difference LLMs make here is to limit the space of possible mutations to largely semantically plausible programs. The above should answer your 1) and 2). On 3), a trained LLM is useful for many, many purposes, so the cost of training it from scratch after amortization wouldn't be significant. It may cost additionally to fine-tune an LLM to work in the FunSearch framework but fine-tuning cost is quite minimal. Using it in the framework is likely a win over genetic programming alone.

jcgrillo 3y ago
> The difference LLMs make here is to limit the space of possible mutations to largely semantically plausible programs. Yet, sadly, the work under question here didn't make any attempt to show this, AFAICT. It's an interesting hypothesis, but as yet untested. > a trained LLM is useful for many, many purposes, so the cost of training it from scratch after amortization wouldn't be significant. It may cost additionally to fine-tune an LLM to work in the FunSearch framework but fine-tuning cost is quite minimal. Using it in the framework is likely a win over genetic programming alone. Again, an interesting hypothesis that probably could be investigated with the experimental apparatus described in the paper. But it wasn't. Have you?
- nopinsight 3y ago
  >> The difference LLMs make here is to limit the space of possible mutations to largely semantically plausible programs. > Yet, sadly, the work under question here didn't make any attempt to show this, AFAICT. It's an interesting hypothesis, but as yet untested. It would be ideal to do that. But given the way LLMs work, it is almost a given. This could be the reason it didn't occur to the researchers who are very familiar with LLMs. >> a trained LLM is useful for many, many purposes, so the cost of training it from scratch after amortization wouldn't be significant. It may cost additionally to fine-tune an LLM to work in the FunSearch framework but fine-tuning cost is quite minimal. Using it in the framework is likely a win over genetic programming alone. > Again, an interesting hypothesis that probably could be investigated with the experimental apparatus described in the paper. But it wasn't. Have you? Perhaps it's quite evident to people in the trench, as the hypothesis seems very plausible to me. A numerical confirmation would be ideal as you suggested. Given my management experience, I'd say it's smart of them to focus their limited resources on something more innovative in this exploratory work. Details can be left for future work or worked out by other teams.

deleted 3y ago

[deleted]

mejutoco 3y ago

> (1) What's the value add of the LLM here? Does it substantially reduce the number of evaluations necessary to converge? If so, how? I thought that stochastic (random) gradient descent and LLM were converging much quicker than genetic programming. Definitely much quicker than random search.

anonzzzies 3y ago

Inductive program synthesis stood still for decades because the space is far too large to get anything beyond absolutely trivial programs; LLMs vastly trim (in many wrong ways too of course) the search space and then you can apply ips to finetune and test. You cannot do this (not in any way we know of) without LLMs because it just tests billions of programs that make absolutely no sense even for trivial cases.

YeGoblynQueenne 3y ago
Quantify "vastly trim" for me please. All I see is a firehose of compute that spams and spams millions of samples until it hits a lucky guess. That's not trimming anything, it's the computing equivalent of the human wave attack. But, please quantify "vastly trim". Edit: the subject of my PhD research was an inductive program synthesis approach and while I agree with the bit about the size of program search spaces, LLMs are very clearly not a solution to that. Deepmind's "solution" is instead their massive computational capacity which makes it possible to search deeper and wider in the search space of Python programs. FunSearch is like one of those rocket cars that people make once in a while to break land speed records. Extremely expensive, extremely impractical and terminally over-specialised to do one thing, and do that thing only. And, ultimately, a bit of a show.
- anonzzzies 3y ago
  Well the approach we use (and has been used at MS research before gpt was a thing) is to ask the llm to provide guesses for instructions to get to a (sub) solution and then let ips (in prolog in our case) do the rest. It seems to work for what we are doing. Disclaimer: did my dissertation on ips (with genetic programming), but in the 90s when we basically had no computer power. The results were horrible outside trivialities, now they aren't anymore.
  - deleted 3y ago
    [deleted]
  - deleted 3y ago
    [deleted]