5 ms·
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 w
by 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 agoLikely the goal would be to find new optimizations that were previously overlooked, then codify those like usual.
- sfcarrot 3y agoMaybe 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 agoProving 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 agoThere 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.
- benlivengood 3y agoMy 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.