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.
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.
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.
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.
My guess on "why optimization problems?": You can do self-play like AlphaZero against NP hard problems; easy to generate problems, easy to verify solutions, and they will be probably be feeding the best meta-prompts and best solutions back into the fine-tuning once it's genericized enough to not be fine-tuning directly on the non-public benchmarks themselves.
They also are trying to figure out what properties of prompts actually yield performance improvement/capabilities since that's still an open question. So far it's been highly subjective and qualitative and they've begun to systematize (via ablation) the effect of prompt structure.
My guess is that the ultimate goal for this project is another meta-level or two that can lead directly to relatively stable goal-oriented self-improvement when the LLMs reach human-level ML engineering ability.
- 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.
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 is 93%
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.
Not explicitly, I think no. But in some sense, yes. Arguably any tech which we don't really understand is a black box. I think the lack of understanding how something works is a large part of the "magical" effect.
Could you explain what you mean here? To the best of my knowledge, there hasn't been much success in successfully explaining how LLMs actually work? Of course we know all the low level mathematical details, we built them. But my understanding is that we don't really know much about the structure of LLM parameters and how they relate to the concepts the model is supposedly learning.
Nice, one would expect so. Though if you think more deeply about it, I think not. The language itself is the manifestation of capabilities, but the process exhibiting them is the underlying system, eg. neural nets or human brain.
Still, there's a deeper analogy here. Very much in the "enshittification" vein, today's tech companies are about making something cool, getting folks to use it, and then monetizing while gradually turning said cool thing into a bad parody of itself.
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.
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.
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 ;)
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)?
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
33 comments
[ 3.8 ms ] story [ 101 ms ] thread"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.
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.
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.
They also are trying to figure out what properties of prompts actually yield performance improvement/capabilities since that's still an open question. So far it's been highly subjective and qualitative and they've begun to systematize (via ablation) the effect of prompt structure.
My guess is that the ultimate goal for this project is another meta-level or two that can lead directly to relatively stable goal-oriented self-improvement when the LLMs reach human-level ML engineering ability.
- 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.
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 is 93%
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.
Could you explain what you mean here? To the best of my knowledge, there hasn't been much success in successfully explaining how LLMs actually work? Of course we know all the low level mathematical details, we built them. But my understanding is that we don't really know much about the structure of LLM parameters and how they relate to the concepts the model is supposedly learning.
"... even to its creators"
-- me
Still, there's a deeper analogy here. Very much in the "enshittification" vein, today's tech companies are about making something cool, getting folks to use it, and then monetizing while gradually turning said cool thing into a bad parody of itself.
-- someone wise
https://news.ycombinator.com/item?id=37438398
Sure you can, that's how my brother learned to be a mechanic.
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