3 ms·

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 syst

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.

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.