Re:Large Language Models as Optimizers
by PartiallyTyped on Friday September 08, 2023 @11:53AM
(#37435268)
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.
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.