POLCA: Stochastic Generative Optimization with LLM

Abstract

Optimizing complex systems, ranging from LLM prompts to multi-turn agents, traditionally requires labor-intensive manual iteration. We formalize this as a stochastic generative optimization problem where a language model acts as the optimizer, guided by numerical and text feedback to discover the best system. We introduce **P**rioritized **O**ptimization with **L**ocal **C**ontextual **A**ggregation (POLCA), a scalable framework designed to handle stochasticity in optimization—such as noisy feedback, sampled minibatches, and stochastic system behaviors—while effectively managing the unconstrained expansion of the solution space. POLCA maintains a priority queue to enable exploration–exploitation, tracking candidate solutions and their evaluation histories. To enhance efficiency, we integrate an $\varepsilon$-Net mechanism to maintain parameter diversity and an LLM Summarizer to perform meta-learning across historical trials. We theoretically prove that POLCA converges to near-optimal candidate solutions under stochasticity. We evaluate our framework on diverse benchmarks, including $\tau$-bench, HotpotQA, VeriBench, and KernelBench. Experimental results demonstrate that POLCA achieves robust, sample- and time-efficient performance, consistently outperforming state-of-the-art algorithms in both deterministic and stochastic problems. The codebase for this work is publicly available at https://github.com/rlx-lab/POLCA.