POLCA: Stochastic Generative Optimization with LLM

Xuanfei Ren; Allen Nie; Tengyang Xie; Ching-An Cheng

cs.LGMar 16, 2026

POLCA: Stochastic Generative Optimization with LLM

Authors: Xuanfei Ren, Allen Nie, Tengyang Xie, Ching-An Cheng

Organizations: University of Wisconsin-Madison, Madison, WI · Google DeepMind, Mountain View, CA · Google Research, Kirkland, WA

Abstract

Optimizing complex systems, ranging from LLM prompts to multi-turn agents, traditionally requires labor-intensive manual iteration. We formalize this challenge as a stochastic generative optimization problem where a generative language model acts as the optimizer, guided by numerical rewards and text feedback to discover the best system. We introduce Prioritized Optimization with Local Contextual Aggregation (POLCA), a scalable framework designed to handle stochasticity in optimization -- such as noisy feedback, sampling minibatches, and stochastic system behaviors -- while effectively managing the unconstrained expansion of solution space. POLCA maintains a priority queue to manage the exploration-exploitation tradeoff, systematically 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 $τ$ -bench, HotpotQA (agent optimization), VeriBench (code translation) and KernelBench (CUDA kernel generation). 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.

Figures & tables

Panel of Figure 1 — Figure 1: Left : The POLCA framework for generative optimization. POLCA maintains a memory buffer as an $\varepsilon$ -Net to ensure diverse program storage. In each iteration, it selects promising parameter candidates from the $\varepsilon$ -Net, evaluates them against a sampled minibatch, and generates new candidate parameters based on the feedback. These candidates undergo a semantic Filtering stage; accepted parameters are evaluated on the minibatch and integrated into the $\varepsilon$ -Net. Finally, a Summarize step compresses the memory to provide concise global context $C$ for the next optimization cycle. Right : Normalized performance averaged across benchmarks ( $\tau$ -Bench, HotpotQA, VeriBench, and KernelBench). The solid curve represents the mean, while the shaded region indicates the standard error across all benchmarks. Results are aggregated by standardizing scores and computational budgets to a scale of $[0,1]$ .

Panel of Figure 2 — Figure 2: Search efficiency across four benchmarks. Solid curves represent the average highest score attained at each step, while the shaded regions denote the standard error across multiple independent runs (6 seeds for $\tau$ -bench, 3 for HotpotQA and VeriBench (3-step evaluation), and 1 for KernelBench). Higher curves indicate superior efficiency.

Table 3

Panel of Figure 3 — Figure 3: In (a–c), solid curves show the mean highest score achieved at each step, with shaded areas representing the standard error over independent runs (6 seeds for (a); 3 seeds for (b, c)). In (d), bar heights denote test scores for programs selected via different criteria across varying training data percentages. Results are averaged over 3 runs, with error bars indicating the standard error. See Section D.7 for details.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: $\tau$ -bench: performance vs. number of samples (left), proposal steps (middle), and number of proposals (right). Solid curves represent the average highest score attained at each step, while the shaded regions denote the standard error across multiple independent runs (6 seeds).

Panel of Figure 5 — Figure 5: HotpotQA: performance vs. number of samples (left), proposal steps (middle), and number of proposals (right). Solid curves represent the average highest score attained at each step, while the shaded regions denote the standard error across multiple independent runs (3 seeds).

Panel of Figure 6 — Figure 6: VeriBench: performance vs. number of samples (left), proposal steps (middle), and number of proposals (right). Solid curves represent the average highest score attained at each step, while the shaded regions denote the standard error across multiple independent runs (3 seeds).

Panel of Figure 7 — Figure 7: KernelBench: performance vs. number of samples (left), proposal steps (middle), and number of proposals (right). Solid curves represent the average highest score attained at each step (1 seed).

Panel of Figure 8 — Figure 8: VeriBench (Compilation) results: Plots show the compilation rate over $140$ tasks relative to number of evaluation steps, metric calls, proposal steps and proposals, respectively. Solid curves represent the average highest score attained at each step, while the shaded regions denote the standard error across multiple independent runs (3 seeds).

Panel of Figure 9 — Figure 9: Performance comparison across 16 kernel optimization tasks. Plots show the fast 0.5 score relative to number of evaluation steps, metric calls, proposal steps, and proposals, respectively. Solid curves represent the average highest score attained at each step (1 seed).

Panel of Figure 10 — Figure 10: Ablation on $\varepsilon$ -Net and Summarizer. Solid curves represent the average highest score attained at each step, while the shaded regions denote the standard error across multiple independent runs (6 seeds).

Panel of Figure 11 — Figure 11: Ablation study on $\varepsilon$ -values (first two panels for $\tau$ -bench; last panel for VeriBench). Solid curves represent the average highest score attained at each step, while shaded regions denote the standard error across 3 independent seeds.

Large Language Model-Guided Optimization

Large Language Model-Guided Optimization uses language models to propose, steer, and refine solutions to hard search and design problems.

See all 605 papers

RLMOpt: Adaptive Prompt Optimization via Recursive Language Models
Aug 11, 2026Subhash Bangalore Satheesha, Nirvik Pande, Deepthi Duddempudi +1Large Language Model-Guided Optimization LLM Agents
Autonomize AI · Carnegie Mellon University
SAGE: Stochastic Prompt Optimization via Agent-Guided Exploration
Jun 17, 2026Ziyi Zhu, Luka Smyth, Saki Shinoda +1Large Language Model-Guided Optimization Mental Health Conversational Agents
1Slingshot AI · Department of Engineering, University of Cambridge
optimize_anything: A Universal API for Optimizing any Text Parameter
May 19, 2026Lakshya A Agrawal, Donghyun Lee, Shangyin Tan +11Black-Box Optimization Large Language Model-Guided Optimization
UC Berkeley USA · MIT USA

Aug 11, 2026J/K move · Enter open · S save

RLMOpt: Adaptive Prompt Optimization via Recursive Language Models

Subhash Bangalore Satheesha, Nirvik Pande, Deepthi Duddempudi, Bharath Dandala

Autonomize AI · Carnegie Mellon University

Large Language Model-Guided Optimization LLM Agents Prompt Optimization Recursive Language Models LLM Input Optimization

Open paper AskPDF arXiv

Prompt optimizers automate the search for prompts that improve language-model performance, but existing methods rely on a predefined optimization procedure: the algorithm determines which candidates to explore and how the search progresses, while the language model generates or refines prompt proposals. We introduce RLMOpt, a prompt optimizer that makes the search policy itself language-model-driven through a recursive language model (RLM). The RLM agent operates over a tool-based environment, inspecting task information, analyzing failures, generating candidates, allocating evaluation budget, and deciding when to stop. A deterministic harness complements the agent by enforcing objective scoring, Pareto-based selection, and regression constraints. We evaluate RLMOpt across four benchmarks spanning structured clinical information extraction (Chia), multi-hop question answering (HotpotQA), verifiable instruction following (IFBench-2025), and multi-turn tool-calling agents (BFCL). In a matched comparison at a single seed, RLMOpt obtains the best held-out score on all four benchmarks and leads the four-task mean (0.610 against 0.589 for GEPA). Repeating each benchmark across seeds yields 11 matched benchmark-seed comparisons, in which RLMOpt outperforms GEPA in 9 cases. Across all 11 runs, it never produced a prompt that underperformed its seed, whereas GEPA fell below its starting point twice. It is also more efficient, achieving these results with fewer search rollouts while producing prompts that are 27-79% the size of those produced by GEPA. Our results further show that optimization gains are determined primarily by the headroom available in the seed prompt, rather than by the search budget. Efficient optimization therefore depends on reaching the available headroom reliably and with minimal search

Abstract

Large Language Model-Guided Optimization

Explore similar work

RLMOpt: Adaptive Prompt Optimization via Recursive Language Models

SAGE: Stochastic Prompt Optimization via Agent-Guided Exploration

optimize_anything: A Universal API for Optimizing any Text Parameter