5 ms·

Large Language Models as Optimizers. +50% on Big Bench Hard

95 points by famouswaffles 3y ago

terataiijo 3y ago
What's the difference between text-bison and PaLM 2-L? I thought they were the same model?
edot 3y ago
I find this paper "neat", but struggle to understand why (beyond academic curiosity) one would use LLMs to solve optimization problems. The authors note: "We would like to note that OPRO is designed for neither outperforming the state- of-the-art gradient-based optimization algorithms for continuous mathematical optimization, nor surpassing the performance of specialized solvers for classical combinatorial optimization problems such as TSP. Instead, the goal is to demonstrate that LLMs are able to optimize different kinds of objective functions simply through prompting, and reach the global optimum for some small- scale problems." I would also add that, unlike gradient-based optimization algorithms and (many) specialized solvers for combinatorial optimization problems, I don't think it can be proven that an LLM will reach the global optimum. Proving global optimality is kind of the whole point of optimization (or at least, reliably finding what you believe to be darn close). Another note: the paper seems most interested in the number of steps needed to solve a given problem, and even says that "Interestingly, on small-scale traveling salesman problems, OPRO performs on par with some hand-crafted heuristic algorithms." I would like to understand which metric they are using to say that it performs on par. I will guarantee that it is not seconds. Rather, it seems like they are focused on the number of steps, which is great, but an LLM's language-based step surely takes longer to compute than a math-based step in a traditional solver. 100 steps at 10 seconds/step is much worse than 100 steps at 0.1 seconds/step. Still, fun to explore! I think the next big step in this arena is fine tuning an LLM to take business logic objective and constraint prompts, formulate them with a traditional modeling language, hook up to a data feed, and solve using Gurobi or similar (as in, don't use the LLM to actually solve). Reliably doing this costs a few hundred thousand dollars from most consultancies.
- gct 3y ago
  Likely the goal would be to find new optimizations that were previously overlooked, then codify those like usual.
  - sfcarrot 3y ago
    Maybe having LLM providing insights on more math proving techniques (which is the soul of optimization) is more meaningful than having it directly solve the optimization. The ROI of having a effective proof vs. brutal forcely search for a solution is simply day and night.
- PartiallyTyped 3y ago
  Proving that LLMs __will__ (not can) reach a global optimum for a general instantiation in P time (i.e. without EXP number of prompts) would imply P=NP :D Proving that they __could__ reach an optimal solution for some instantiations of the problem is trivial; an LLM can reduce to random search, and random search is essentially a family of algorithms for which there exists some seed (ie instantiation of the algo) and an input, such that it produces an optimal solution.
- nostrademons 3y ago
  There is a drive within certain Big Tech companies to express as many machine-learning problems (really, computational problems) as suitably-prompted LLMs, and then deploy one uber-LLM model where all the other product tasks are specific prompts for the LLM. The goal is MBA-style synergy. If everything is an LLM, then you can optimize your TPU hardware for inferencing LLMs; you can put all your research dollars into LLM research; you have a common framework and common skillset for all engineering across the company; you have a common serving infrastructure when it comes to productionizing these models and deploying them on real traffic; and you have a centralized point where you can research & mitigate security attacks on LLMs. It kinda makes sense, but it's up to the market to say whether this is ultimately a winning strategy. When it works it looks like the Wintel monopoly of the 80s/90s, where standardizing the whole world on an instruction set and OS (even if they were a bad instruction set and bad OS) freed up lots of capital to invest in the physical aspects of making chips fast, and so Intel ate all the specialized hardware manufacturers like Symbolics/Tandem/IBM/Cray/Sun because their higher sales volumes let them invest more capital into pouring more transistors on the chip, and eventually even the crappy 8086 architecture started to have better price/performance than a Cray. When it doesn't work it looks like lambda calculus & Church numerals: just because you can express everything in two simple primitives doesn't mean that you should, or that it's economically viable. If it doesn't work the 2020s are going to be open-season for startups to start eating away at Big Tech monopolies.
sfcarrot 3y ago
- The general idea of providing guiding prompt + scoring for better objective values is interesting. Though I doubt how this scale since it requires a lot of guiding/customization towards different/bigger problem, but I’d love to think further on it. - Maybe let LLM help explain it’s thinking process/logic to help improve existing algorithms (rather than using it as a standalone-optimizer). I once did that for an allocation problem - and it was able to show a basic algorithm for a feasible solution. - A essential topic in optimization is about proving optimality, maybe having AI providing insights on proving could also be cool. - Author compared their algorithm with heuristics on randomly generated TSP problems (why not TSPLIB), the claim is that LLM can do better than heuristics on small problems. They showed an interesting metric on # of success suggesting we might need to sample multiple LLM runs for a good results. - One big question I did not find an answer is how they replicate the runs given the stochastic nature of LLMs. Even with a zero temperature, LLM is only relatively less random. This extends to many LLM-application papers and hence must be papers talking about it.
riku_iki 3y ago
> +50% on Big Bench Hard its +50% on few tasks. It is also +50% not against sota, but some their weak baseline. For example they received large boost on object_counting task where their final result is 86% acc, while current sota from https://arxiv.org/pdf/2210.09261.pdf https://arxiv.org/pdf/2210.09261.pdf is 93%
galaxytachyon 3y ago
You know, the more I read about these things, the more I realize we are literally getting close to "spells" technology. This is literally an entire paper about constructing a specific incantation to create an effect. Neither the author nor the LLM maker can completely deconstruct and trace every steps of the process from the input to the output. They only know how to chant a litany, add a request, chant another litany, then look at the output and hope they didn't summon Satan.
- lawlessone 3y ago
  alternatively "lets work on this step by step" sounds like an adult encouraging a child on how they can solve a big problem by breaking it into smaller problems.
- amelius 3y ago
  Yes, this is the distinction. In the past, we did our best to find guarantees about the things we invented. E.g. in control theory we would analytically find the limits of a system's inputs and performance, in CS we would determine bounds on the worst case performance, etc. But nowadays we just dump everything into a giant black box and call it a day.
- drittich 3y ago
  “Any sufficiently advanced technology is indistinguishable from magic”
  - amelius 3y ago
    > “Any sufficiently advanced technology is indistinguishable from magic” "... even to its creators" -- me
  - gflan 3y ago
    Except Clarke wasn't referring to the black-boxiness of said advanced tech, was he?
    - michaelmior 3y ago
puzzleist 3y ago
Can they solve sudoku?
- coder543 3y ago
  Tree Of Thought can do pretty well at Sudoku, apparently: https://arxiv.org/abs/2305.08291 https://arxiv.org/abs/2305.08291
- data_maan 3y ago
  If you can get the incantation right, they can solve every you want, including proving the Riemann hypothesis, the Goldbach conjecture -- and the Halting Problem ;)
  - puzzleist 3y ago
    In that case someone should figure out how to incant AGI ;)
sshh12 3y ago
For anyone interested I've been working a very similar idea of LLMs for blackbox optimization: https://github.com/sshh12/llm_optimize https://github.com/sshh12/llm_optimize
- lachlan_gray 3y ago
  This is awesome. I was working on something similar (but got distracted) except my strategy was evolutionary. The idea was that the LLM had to figure out what it’s optimizing for itself. I find that as soon as an LLM has an explicit definition of what it’s doing, the exploration/exploitation ratio swerves into exploitation and it gets stuck
- sytelus 3y ago
  This is very nicely done and much more clear to follow than the paper. One question: Does LLM get to evaluate the code using tool or guess the return value of f(x)?
  - sshh12 3y ago
    Thanks! The LLM only sees the result of f(x). So like in the code writing example, the code is actually executed with `eval()`.

95 points by famouswaffles 3y ago

What's the difference between text-bison and PaLM 2-L? I thought they were the same model?

edot 3y ago

I find this paper "neat", but struggle to understand why (beyond academic curiosity) one would use LLMs to solve optimization problems. The authors note: "We would like to note that OPRO is designed for neither outperforming the state- of-the-art gradient-based optimization algorithms for continuous mathematical optimization, nor surpassing the performance of specialized solvers for classical combinatorial optimization problems such as TSP. Instead, the goal is to demonstrate that LLMs are able to optimize different kinds of objective functions simply through prompting, and reach the global optimum for some small- scale problems." I would also add that, unlike gradient-based optimization algorithms and (many) specialized solvers for combinatorial optimization problems, I don't think it can be proven that an LLM will reach the global optimum. Proving global optimality is kind of the whole point of optimization (or at least, reliably finding what you believe to be darn close). Another note: the paper seems most interested in the number of steps needed to solve a given problem, and even says that "Interestingly, on small-scale traveling salesman problems, OPRO performs on par with some hand-crafted heuristic algorithms." I would like to understand which metric they are using to say that it performs on par. I will guarantee that it is not seconds. Rather, it seems like they are focused on the number of steps, which is great, but an LLM's language-based step surely takes longer to compute than a math-based step in a traditional solver. 100 steps at 10 seconds/step is much worse than 100 steps at 0.1 seconds/step. Still, fun to explore! I think the next big step in this arena is fine tuning an LLM to take business logic objective and constraint prompts, formulate them with a traditional modeling language, hook up to a data feed, and solve using Gurobi or similar (as in, don't use the LLM to actually solve). Reliably doing this costs a few hundred thousand dollars from most consultancies.

gct 3y ago
Likely the goal would be to find new optimizations that were previously overlooked, then codify those like usual.
- sfcarrot 3y ago
  Maybe having LLM providing insights on more math proving techniques (which is the soul of optimization) is more meaningful than having it directly solve the optimization. The ROI of having a effective proof vs. brutal forcely search for a solution is simply day and night.
PartiallyTyped 3y ago
Proving that LLMs __will__ (not can) reach a global optimum for a general instantiation in P time (i.e. without EXP number of prompts) would imply P=NP :D Proving that they __could__ reach an optimal solution for some instantiations of the problem is trivial; an LLM can reduce to random search, and random search is essentially a family of algorithms for which there exists some seed (ie instantiation of the algo) and an input, such that it produces an optimal solution.
nostrademons 3y ago
There is a drive within certain Big Tech companies to express as many machine-learning problems (really, computational problems) as suitably-prompted LLMs, and then deploy one uber-LLM model where all the other product tasks are specific prompts for the LLM. The goal is MBA-style synergy. If everything is an LLM, then you can optimize your TPU hardware for inferencing LLMs; you can put all your research dollars into LLM research; you have a common framework and common skillset for all engineering across the company; you have a common serving infrastructure when it comes to productionizing these models and deploying them on real traffic; and you have a centralized point where you can research & mitigate security attacks on LLMs. It kinda makes sense, but it's up to the market to say whether this is ultimately a winning strategy. When it works it looks like the Wintel monopoly of the 80s/90s, where standardizing the whole world on an instruction set and OS (even if they were a bad instruction set and bad OS) freed up lots of capital to invest in the physical aspects of making chips fast, and so Intel ate all the specialized hardware manufacturers like Symbolics/Tandem/IBM/Cray/Sun because their higher sales volumes let them invest more capital into pouring more transistors on the chip, and eventually even the crappy 8086 architecture started to have better price/performance than a Cray. When it doesn't work it looks like lambda calculus & Church numerals: just because you can express everything in two simple primitives doesn't mean that you should, or that it's economically viable. If it doesn't work the 2020s are going to be open-season for startups to start eating away at Big Tech monopolies.

sfcarrot 3y ago

- The general idea of providing guiding prompt + scoring for better objective values is interesting. Though I doubt how this scale since it requires a lot of guiding/customization towards different/bigger problem, but I’d love to think further on it. - Maybe let LLM help explain it’s thinking process/logic to help improve existing algorithms (rather than using it as a standalone-optimizer). I once did that for an allocation problem - and it was able to show a basic algorithm for a feasible solution. - A essential topic in optimization is about proving optimality, maybe having AI providing insights on proving could also be cool. - Author compared their algorithm with heuristics on randomly generated TSP problems (why not TSPLIB), the claim is that LLM can do better than heuristics on small problems. They showed an interesting metric on # of success suggesting we might need to sample multiple LLM runs for a good results. - One big question I did not find an answer is how they replicate the runs given the stochastic nature of LLMs. Even with a zero temperature, LLM is only relatively less random. This extends to many LLM-application papers and hence must be papers talking about it.

riku_iki 3y ago

> +50% on Big Bench Hard its +50% on few tasks. It is also +50% not against sota, but some their weak baseline. For example they received large boost on object_counting task where their final result is 86% acc, while current sota from https://arxiv.org/pdf/2210.09261.pdf https://arxiv.org/pdf/2210.09261.pdf is 93%

galaxytachyon 3y ago

You know, the more I read about these things, the more I realize we are literally getting close to "spells" technology. This is literally an entire paper about constructing a specific incantation to create an effect. Neither the author nor the LLM maker can completely deconstruct and trace every steps of the process from the input to the output. They only know how to chant a litany, add a request, chant another litany, then look at the output and hope they didn't summon Satan.

lawlessone 3y ago
alternatively "lets work on this step by step" sounds like an adult encouraging a child on how they can solve a big problem by breaking it into smaller problems.
amelius 3y ago
Yes, this is the distinction. In the past, we did our best to find guarantees about the things we invented. E.g. in control theory we would analytically find the limits of a system's inputs and performance, in CS we would determine bounds on the worst case performance, etc. But nowadays we just dump everything into a giant black box and call it a day.
drittich 3y ago
“Any sufficiently advanced technology is indistinguishable from magic”
- amelius 3y ago
  > “Any sufficiently advanced technology is indistinguishable from magic” "... even to its creators" -- me
- gflan 3y ago
  Except Clarke wasn't referring to the black-boxiness of said advanced tech, was he?
  - michaelmior 3y ago

puzzleist 3y ago

Can they solve sudoku?

coder543 3y ago
Tree Of Thought can do pretty well at Sudoku, apparently: https://arxiv.org/abs/2305.08291 https://arxiv.org/abs/2305.08291
data_maan 3y ago
If you can get the incantation right, they can solve every you want, including proving the Riemann hypothesis, the Goldbach conjecture -- and the Halting Problem ;)
- puzzleist 3y ago
  In that case someone should figure out how to incant AGI ;)

sshh12 3y ago

For anyone interested I've been working a very similar idea of LLMs for blackbox optimization: https://github.com/sshh12/llm_optimize https://github.com/sshh12/llm_optimize

lachlan_gray 3y ago
This is awesome. I was working on something similar (but got distracted) except my strategy was evolutionary. The idea was that the LLM had to figure out what it’s optimizing for itself. I find that as soon as an LLM has an explicit definition of what it’s doing, the exploration/exploitation ratio swerves into exploitation and it gets stuck
sytelus 3y ago
This is very nicely done and much more clear to follow than the paper. One question: Does LLM get to evaluate the code using tool or guess the return value of f(x)?
- sshh12 3y ago
  Thanks! The LLM only sees the result of f(x). So like in the code writing example, the code is actually executed with `eval()`.