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 loos 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.
"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.