5 ms·

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

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]
  - YeGoblynQueenne 3y ago
    Well, if you're willing to use Prolog I commend you, but then you don't need an LLM because you don't need to do a dumb search of a large space. You can instead use second-order Resolution for induction. Here's how it's done (a.k.a. shameless plug of my PhD work): https://github.com/stassa/louise/blob/master/data/examples/ackermann.pl https://github.com/stassa/louise/blob/master/data/examples/a... >> 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. But that's because the training data and the model parameters keep increasing. Performance keeps increasing but not because capabilities improve, only because there's more and more resources spent on the same old problems. There's better ways than that. All the classical AI problems, planning, verification, SAT, now have fast solutions thanks to better heuristics, not thanks to more data (that are useless to them anyway). That's a real advance. I still would like a quantification of the "vast trim" btw. Numbers, or it didn't happen.
    - anonzzzies 3y ago
      > but then you don't need an LLM because you don't need to do a dumb search of a large space we do, because we use our prolog ips library, but it's doing this for another language (a subset of python) > I still would like a quantification of the "vast trim" btw. Numbers, or it didn't happen. Agreed, I will get numbers and until then it didn't happen.
      - YeGoblynQueenne 3y ago
        Interesting. Do you have a transpiler from Prolog to Python-subset? I would have preferred to use the LLM to do the translation, instead, and let the Prolog-based IPS (is it based on bottom clause construction?) do what it does best.
    - optimalsolver 3y ago
      Sorry, for those of us unfamiliar with Prolog, can you explain in layman terms how you do program synthesis without a large search of program space? I’m also curious if this scales to real world problems.
samth 3y ago
This is not correct about the current state of the art in program synthesis, which is a field that's made a lot of progress recently. Unfortunately people coming from the AI world tend to ignore that work entirely and imagine they're the only people with new ideas since the 80s.

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]
- YeGoblynQueenne 3y ago
  Well, if you're willing to use Prolog I commend you, but then you don't need an LLM because you don't need to do a dumb search of a large space. You can instead use second-order Resolution for induction. Here's how it's done (a.k.a. shameless plug of my PhD work): https://github.com/stassa/louise/blob/master/data/examples/ackermann.pl https://github.com/stassa/louise/blob/master/data/examples/a... >> 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. But that's because the training data and the model parameters keep increasing. Performance keeps increasing but not because capabilities improve, only because there's more and more resources spent on the same old problems. There's better ways than that. All the classical AI problems, planning, verification, SAT, now have fast solutions thanks to better heuristics, not thanks to more data (that are useless to them anyway). That's a real advance. I still would like a quantification of the "vast trim" btw. Numbers, or it didn't happen.
  - anonzzzies 3y ago
    > but then you don't need an LLM because you don't need to do a dumb search of a large space we do, because we use our prolog ips library, but it's doing this for another language (a subset of python) > I still would like a quantification of the "vast trim" btw. Numbers, or it didn't happen. Agreed, I will get numbers and until then it didn't happen.
    - YeGoblynQueenne 3y ago
      Interesting. Do you have a transpiler from Prolog to Python-subset? I would have preferred to use the LLM to do the translation, instead, and let the Prolog-based IPS (is it based on bottom clause construction?) do what it does best.
  - optimalsolver 3y ago
    Sorry, for those of us unfamiliar with Prolog, can you explain in layman terms how you do program synthesis without a large search of program space? I’m also curious if this scales to real world problems.

samth 3y ago

This is not correct about the current state of the art in program synthesis, which is a field that's made a lot of progress recently. Unfortunately people coming from the AI world tend to ignore that work entirely and imagine they're the only people with new ideas since the 80s.