POLCA: Stochastic Generative Optimization with LLM

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.

Modern AI systems—from chatbots that answer customer questions to programs that generate code—need to be carefully tuned to perform well. This tuning is usually done by hand: experts repeatedly tweak instructions or code, see what works, and try again. Recent research has shown this process can be automated by treating a large language model (LLM) itself as the "optimizer": it proposes changes, observes how well they work, and tries again. The problem is that this process is noisy. The same instruction can succeed on one task and fail on a similar one, or receive different scores from different graders. As a result, the LLM optimizer often gets misled by a lucky or unlucky example, discards promising ideas too early, and keeps producing slight variations of the same idea—wasting both time and computation. We propose POLCA, which tackles these issues with three ideas. First, instead of keeping only the single best candidate so far, POLCA maintains a ranked memory of many candidates and re-evaluates the most promising ones, so that lucky or unlucky scores get averaged out. Second, when the LLM proposes a new candidate, POLCA checks whether it is meaningfully different from what is already in memory, using a numerical signature (an "embedding") of the candidate's text, and discards near-duplicates—preventing the search from drowning in repetitive variants. Third, POLCA periodically summarizes the history of successes and failures into high-level guidance, helping the optimizer learn from the entire search rather than just the most recent attempt. We prove mathematically that POLCA converges to near-optimal solutions even when feedback is noisy, and we test it on four very different problems: tuning a customer-service agent, tuning a question-answering prompt, translating Python programs into formally verified Lean 4 code, and writing fast GPU code. Across all four, POLCA finds better solutions faster than existing approaches. The result is a more reliable, automatic way to improve AI systems, reducing the manual effort needed to deploy them in real applications.