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

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.

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%

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