5 ms·

> 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

> 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.
    - janalsncm 3y ago
      The purpose of the ablation is to demonstrate the value-add of using an LLM. Comparing to another type of candidate generator wouldn’t be ablation anymore, it would just be another study. As I have mentioned previously, using an LLM addresses the cold start problem by immediately generating plausible-looking programs. The reason random token selection is limited to constrained programs is that valid programs are statistically unlikely to occur. And the ablation directly demonstrates that the LLM is better than random.
- janalsncm 3y ago
  The fact that LLMs generate text which is better than random is not something the authors need to spell out. Reducing the cross entropy between predicted and target distributions is the entire purpose of training. Put another way: a flat probability distribution from an untrained network is equivalent to the random decoding you’re skeptical an LLM is better than. That’s not a criticism the authors’ peers would likely put forward.
  - YeGoblynQueenne 3y ago
    >> Reducing the cross entropy between predicted and target distributions is the entire purpose of training. Nope. Test distribution. Not target distribution.
    - janalsncm 3y ago
      I’m not sure why you felt the need to correct me. Target is the correct terminology. As a sanity check I even looked up the PyTorch doc which explicitly uses “target” in their example. https://pytorch.org/docs/stable/generated/torch.nn.CrossEntropyLoss.html https://pytorch.org/docs/stable/generated/torch.nn.CrossEntr...
      - YeGoblynQueenne 3y ago
        Because the target distribution is not known, whatever PyTorch docs say. The test distribution is known and nobody knows what's its relation to the target distribution except a hope and a prayer.
YeGoblynQueenne 3y ago
Genetic programming algorithms don't start cold just as FunSearch doesn't start cold. It starts with a partial Python program with "missing" lines that the system has to fill-in. That's pretty much schema-guided program synthesis, to a t, down to the generate-and-test approach. Unfortunately you won't find any references to that kind of earlier work in DeepMind's paper (as in most of their papers), so here's a paper I found on the internets with six second search that explains what that is: Intuitively, a program schema is an abstraction of a class of actual programs, in the sense that it represents their data-flow and control-flow, but neither con- tains all their actual computations nor all their actual data structures. Program schemas have been shown to be useful in a variety of applications. In synthesis, the main idea is to simplify the proof obligations by taking the difficult ones offline, so that they are proven once and for all at schema design time. Also, the reuse of existing programs is made the main synthesis mechanism https://ethz.ch/content/dam/ethz/special-interest/infk/inst-infsec/information-security-group-dam/research/publications/pub2004/Synthesis.pdf https://ethz.ch/content/dam/ethz/special-interest/infk/inst-... See section 4, "Schema-guided synthesis" page 41.
- janalsncm 3y ago
  The original question was “why would they use an LLM here”. Whether candidates are an entire program or just a portion of the program is immaterial to that question. In fact, it is an example of a situation where random decoding is especially poorly matched against an autoregressive model, since there’s already context to use. Anyways, you can see there is a cold start issue in the ablation study since the random strategy didn’t even begin to register until about halfway through the test.
  - YeGoblynQueenne 3y ago
    Of course if you start without any inductive biases (i.e. a program schema in the case of the FunSearch approach) there will be a "cold start" problem, but FunSearch doesn't start cold, as genetic programming doesn't start cold. The question is the "cold start issue". That's what I'm addressing. Maybe you're not used to being corrected? Get used to it.

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.
  - janalsncm 3y ago
    The purpose of the ablation is to demonstrate the value-add of using an LLM. Comparing to another type of candidate generator wouldn’t be ablation anymore, it would just be another study. As I have mentioned previously, using an LLM addresses the cold start problem by immediately generating plausible-looking programs. The reason random token selection is limited to constrained programs is that valid programs are statistically unlikely to occur. And the ablation directly demonstrates that the LLM is better than random.
janalsncm 3y ago
The fact that LLMs generate text which is better than random is not something the authors need to spell out. Reducing the cross entropy between predicted and target distributions is the entire purpose of training. Put another way: a flat probability distribution from an untrained network is equivalent to the random decoding you’re skeptical an LLM is better than. That’s not a criticism the authors’ peers would likely put forward.
- YeGoblynQueenne 3y ago
  >> Reducing the cross entropy between predicted and target distributions is the entire purpose of training. Nope. Test distribution. Not target distribution.
  - janalsncm 3y ago
    I’m not sure why you felt the need to correct me. Target is the correct terminology. As a sanity check I even looked up the PyTorch doc which explicitly uses “target” in their example. https://pytorch.org/docs/stable/generated/torch.nn.CrossEntropyLoss.html https://pytorch.org/docs/stable/generated/torch.nn.CrossEntr...
    - YeGoblynQueenne 3y ago
      Because the target distribution is not known, whatever PyTorch docs say. The test distribution is known and nobody knows what's its relation to the target distribution except a hope and a prayer.

YeGoblynQueenne 3y ago

Genetic programming algorithms don't start cold just as FunSearch doesn't start cold. It starts with a partial Python program with "missing" lines that the system has to fill-in. That's pretty much schema-guided program synthesis, to a t, down to the generate-and-test approach. Unfortunately you won't find any references to that kind of earlier work in DeepMind's paper (as in most of their papers), so here's a paper I found on the internets with six second search that explains what that is: Intuitively, a program schema is an abstraction of a class of actual programs, in the sense that it represents their data-flow and control-flow, but neither con- tains all their actual computations nor all their actual data structures. Program schemas have been shown to be useful in a variety of applications. In synthesis, the main idea is to simplify the proof obligations by taking the difficult ones offline, so that they are proven once and for all at schema design time. Also, the reuse of existing programs is made the main synthesis mechanism https://ethz.ch/content/dam/ethz/special-interest/infk/inst-infsec/information-security-group-dam/research/publications/pub2004/Synthesis.pdf https://ethz.ch/content/dam/ethz/special-interest/infk/inst-... See section 4, "Schema-guided synthesis" page 41.

janalsncm 3y ago
The original question was “why would they use an LLM here”. Whether candidates are an entire program or just a portion of the program is immaterial to that question. In fact, it is an example of a situation where random decoding is especially poorly matched against an autoregressive model, since there’s already context to use. Anyways, you can see there is a cold start issue in the ablation study since the random strategy didn’t even begin to register until about halfway through the test.
- YeGoblynQueenne 3y ago
  Of course if you start without any inductive biases (i.e. a program schema in the case of the FunSearch approach) there will be a "cold start" problem, but FunSearch doesn't start cold, as genetic programming doesn't start cold. The question is the "cold start issue". That's what I'm addressing. Maybe you're not used to being corrected? Get used to it.