PaperlayerView exact revision on arXiv

Source-linked AI summary

POLCA: Stochastic Generative Optimization with LLM

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

arXiv:2603.14769v1cs.LGcs.AI

TL;DR

Complex-system optimization requires repeated LLM-guided program revision despite noisy feedback, sampled evaluations, and stochastic program behavior. POLCA addresses this setting with prioritized memory, semantic ε-Net filtering, and historical summarization, and it reports consistent improvements across stochastic and deterministic benchmarks with near-optimal convergence guarantees under stated assumptions.

  • Problem

    Complex-system optimization lacks an efficient alternative to manual iteration when feedback, sampling, and program behavior are stochastic and the parameter space can grow without bound.

  • Method

    POLCA combines a priority-queue memory, ε-Net novelty filtering, and summarized historical context to guide LLM-generated candidates under stochastic evaluation.

  • Results

    POLCA significantly outperforms existing baselines on τ-bench, HotpotQA, VeriBench, and KernelBench across stochastic and deterministic domains.

  • Takeaways & Limitations

    POLCA provides a robust and scalable framework for generative optimization that bounds candidate growth while retaining diverse programs under noisy evaluations.

  • Takeaways & Limitations

    The theoretical guarantee relies on knowing reward stochasticity and assuming the optimizer can achieve strict improvement, while empirical observations may be benchmark- and model-dependent.

Abstract

from arXiv · show

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.

1 Introduction

Generative optimization replaces manual iteration over complex programs with LLM-guided proposal and feedback, but stochastic evaluations and expanding parameter spaces make reliable search difficult. POLCA addresses these challenges with persistent semantic memory, bounded candidate diversity, and prioritized exploration, achieving strong results across stochastic and deterministic benchmarks.

  • Motivation: Generative optimization treats prompts, code generators, and multi-turn agents as parameterized programs that an LLM repeatedly modifies using numerical or textual feedback.The feedback may include scores, critiques, error messages, or other signals used to guide subsequent revisions.
  • Motivation: Stochastic minibatches, evaluator randomness, and stochastic agent behavior can make performance estimates noisy and limit the information available for improvement.Agent optimization may require evaluating only task subsets, while feedback and execution can each introduce additional randomness.
  • POLCA: POLCA uses an embedding-based ε-Net with accept/reject filtering to avoid premature candidate loss, redundant evaluations, and unbounded growth of the program space.The user-controlled ε parameter trades off parameter-space coverage against evaluation cost.
  • POLCA: POLCA combines persistent memory with prioritized search and summarization to manage stochastic evaluations while providing historical context for new candidate generation.The framework maintains evaluation histories and compresses them into context for later optimization cycles.
  • Theory: Under an optimizer-improvement assumption, the UCB-based analysis proves convergence to near-optimal candidates under stochasticity, with rates governed by optimizer efficiency and evaluation stochasticity.Optimizer capability affects proposal iterations, whereas evaluation stochasticity affects the samples needed to estimate rewards.
  • Results: Across τ-bench, HotpotQA, VeriBench, and KernelBench, POLCA outperforms GEPA and OpenEvolve in convergence speed and final performance across stochastic and deterministic settings.The benchmarks cover agent prompt optimization, code translation, and CUDA kernel generation.

2 Problem Setup

The paper formulates stochastic generative optimization as searching over parameters of a program whose data, execution, guide, optimizer, and algorithm are all potentially stochastic. The objective is to maximize expected reward under a computational budget while balancing novelty against reliable evaluation.

  • Problem Formulation: Stochastic generative optimization changes a parameterized program P_θ, whose parameters may be numbers, text, code, or mixtures, to maximize expected reward.The formulation targets automated optimization of prompts and code while addressing stochastic sampling, evaluation, and program behavior.
  • Problem Formulation: A guide maps program outcomes and inputs to a numerical score and feedback, while an LLM optimizer proposes new parameters from the current state, feedback, and context.The optimizer is not assumed to improve every proposal because information and optimizer randomness can prevent improvement.
  • Objective: The algorithm must coordinate data sampling, guide feedback, program execution, and optimizer behavior to identify the best parameter within a resource budget.The objective explicitly accounts for joint stochasticity from the data, program, guide, optimizer, and search algorithm.
  • Expansive Search Space: The parameter space may be exponentially large, discrete, and unordered, and it is accessed only through proposals from the LLM optimizer rather than enumerated in advance.Effective search also requires selecting useful parameters and data and curating context that steers future proposals.

3 Algorithm

POLCA combines a continually updated priority-queue memory, minibatch evaluation, summarized historical context, and semantic ε-Net filtering. These components reduce the effects of stochastic evaluation while controlling candidate growth and preserving promising diversity.

  • Priority Queue Memory: POLCA maintains a priority queue initialized with θ0 and updates candidate statistics continuously to select programs for further improvement.The queue serves as the algorithm’s memory and is reordered using updated exploration priorities.
  • Minibatch Evaluation: Minibatch sampling estimates candidate performance when full evaluation is too costly, with stochasticity arising from sampling, execution, and guide evaluation.The same minibatch is used for explored and newly proposed candidates to reduce task-specific comparison bias.
  • Priority Queue Memory: The queue’s dynamic priorities allow high-performing programs to be evaluated repeatedly, while candidates with temporarily low empirical means can be revisited as variance averages out.The exploration priority eventually approaches the true expected reward as additional observations reduce variance.
  • Generative Parameter Space Growth: A Summarizer aggregates historical successes and failures into context that is combined with each candidate’s local minibatch feedback before proposing new parameters.The resulting global and local context is used to generate candidate parameters from the optimizer’s proposal distribution.
  • Priority Queue Memory: POLCA’s empirical-mean priorities can be modified to UCB scores to obtain a theoretically guaranteed search strategy.The paper notes that alternative priority functions can support other search strategies.
  • Semantic Filtering based on ε-Net: Semantic filtering embeds parameters and uses their distances to prevent the priority queue from growing linearly with iterations and to preserve a diverse search space.The filter addresses the sample-complexity and evaluation-cost consequences of indiscriminately storing every generated program.

4 Theoretical Analysis

POLCA’s theoretical analysis models stochastic program evaluation and uses UCB prioritization with ε-Net filtering to control exploration and candidate growth. Under a strict-improvement assumption, it converges to near-optimal programs, with rates governed by optimizer uncertainty and evaluation stochasticity.

  • Analysis setup: POLCA analyzes a UCB-prioritized variant that selects one program for observation and proposes one new program per iteration.This simplified theoretical version uses optimistic exploration rather than the implementation’s empirical-mean selection.
  • Stochastic model: The analysis assumes reward observations are σ^2-sub-Gaussian around each program’s mean reward and uses ε-Net filtering to bound the number of distinct evaluated programs.The bound is denoted N_ε and depends on the program space Θ and ε.
  • Assumptions: POLCA is guaranteed to improve programs below B − γ with positive probability, but no improvement guarantee applies once rewards enter (B − γ, B].This strict-improvement assumption defines the near-optimality threshold reached by the theorem.
  • Convergence: Theorem 1 bounds the expected selections of programs with rewards in [0, B − γ], implying convergence toward programs with rewards in [B − γ, B].The theorem identifies the latter interval as the region where the optimizer need not be guaranteed to improve further.
  • Rates: The convergence bound combines optimizer uncertainty with the samples needed to estimate stochastic rewards, while the stochastic term vanishes when σ = 0.In deterministic evaluation, one sample determines each program’s reward and the bound depends only on the reward space and optimization oracle.
  • Scalability: The ε-Net semantic filter rejects redundant candidates, preventing the memory buffer from growing linearly and keeping historical search records scalable.This mechanism maintains a comprehensive record while limiting semantically redundant entries.
  • Deterministic comparison: Compared with sequential updating, POLCA uses the historical best program, preserving a non-decreasing reward baseline and requiring B/(γδ0) expected steps in the stated deterministic comparison.Sequential updating requires O(1/δB/γ) expected steps under the corresponding theorem statement.

5 Experiments

POLCA is evaluated across stochastic and deterministic optimization settings, including LLM agents, code translation, and CUDA kernel generation. It consistently outperforms baselines in convergence speed and final performance, while its ε-Net and summarization components improve efficiency and robustness.

  • Experimental setup: POLCA is implemented in the Trace workflow optimization pipeline and compared with DSPy, GEPA, and OpenEvolve under matched metric-call budgets.An evaluation step counts parallelized metric calls and serves as a proxy for sequential wall-clock operations.
  • Stochasticity from program execution and minibatch sampling: In τ-bench, POLCA outperforms GEPA and OpenEvolve in a stochastic environment where one-shot evaluations are sensitive to execution randomness.The benchmark uses sampled tasks and stochastic agent behavior, while POLCA continuously updates evaluation statistics.
  • Stochasticity from program execution and minibatch sampling: 13% improvement over the base prompt is achieved by POLCA on τ-bench retail Pass@1 across 115 tasks, despite training prompts on only the first 10 tasks.The generated prompt is reported as best on both the training set and the complete retail-domain dataset.
  • Stochasticity from the evaluator: On HotpotQA, POLCA outperforms all baselines within the same time budget by repeatedly updating empirical scores under evaluator stochasticity.Repeated evaluations also provide diverse feedback for promising programs, whereas some baselines retain static performance values.
  • Deterministic domains: 95.2% compilation pass rate (133/140) is reached by the best POLCA algorithm on VeriBench with 50 metric calls per task.Parallelized POLCA exceeds DSPy, OpenEvolve, and GEPA, including comparisons with fully sequential baselines.
  • Ablation study: Both the ε-Net and Summarizer significantly improve vanilla POLCA, while ε = 0 yields the worst learning performance.Large ε values can improve initial learning speed but degrade asymptotic performance through coarser-discretization approximation error; reasonable ε improves speed with negligible approximation error.
  • Ablation study: Regression-based selection fails to outperform empirical-mean selection because the surrogate struggles to generalize program scores without explicit problem-instance information.The comparison uses ensembles of logistic regressors over semantic embeddings and evaluates programs across varying training-set sizes.

6 Related Work

Related work distinguishes generative optimization methods by optimizer design, search strategy, and candidate curation, with search strategies balancing exploration and exploitation. Candidate curation addresses redundant proposals and computational scaling through filtering, clustering, and novelty mechanisms.

  • Overview: Existing algorithms differ in how they invoke LLMs, orchestrate optimization, and filter generated candidates.These dimensions are optimizer design, search strategy, and candidate curation.
  • Optimizer Design: Optimizer designs range from few-shot prompting and sequential revision to history summarization for using broader global knowledge.Methods may use rewards, textual feedback, execution traces, or summarized history.
  • Search Strategies: Search strategies balance exploration and exploitation by proposing improved programs while reducing uncertainty about accessible candidates.Program memory supports this tradeoff alongside repeated generation, refinement, task-merging, beam search, and other strategies.
  • Search Strategies: Single-task verifier settings can make Pareto-frontier search degenerate, motivating evolutionary alternatives such as MAP-Elites and island-based models.Subsequent approaches combine evolutionary search with test-time reinforcement learning or rejection sampling.
  • Candidate Curation: Candidate curation combats semantically redundant proposals through clustering and filtering that preserve diversity, assess novelty, and reduce evaluation needs.AlphaCode, for example, combines test-based rejection with execution-behavior clustering.

7 Conclusion

The paper formalizes stochastic generative optimization and introduces POLCA to manage evaluation variance and unbounded program-space growth. Theory supports near-optimal convergence, while experiments span stochastic and deterministic benchmarks; the authors also identify assumptions and scope limitations.

  • Contributions: POLCA addresses stochasticity in optimization and unconstrained program-space growth through prioritized memory and semantic filtering.Its memory buffer averages evaluation variance, while ε-Net filtering removes redundant candidates and preserves search diversity.
  • Contributions: Theoretical analysis shows that POLCA can converge efficiently to near-optimal candidates under its stated framework.The conclusion summarizes the theoretical guarantee without specifying a quantitative rate.
  • Empirical Results: Evaluations on τ-bench, HotpotQA, VeriBench, and KernelBench show significant outperformance over existing baselines across stochastic and deterministic domains.The reported stochasticity includes minibatch sampling, program execution, and evaluation.
  • Limitations: The UCB analysis depends on knowing reward stochasticity and assuming an optimizer capable of strict improvement, while empirical-mean priorities and embedding distance are not uniquely optimal.The authors also note that more advanced selection and function-approximation strategies may exist.
  • Limitations: POLCA’s empirical findings may be limited to the benchmarks and models tested, despite efforts to make them representative.The authors explicitly state this as a limitation of the experimental observations.

A Full Proof of Section 4

The proof partitions the reward range into intervals, tracks interval exploration and per-program additional selections, and bounds those selections to establish the main theorem.

  • Reward Partition: The reward range [0, B] is partitioned into intervals of width γ/2.The analysis assumes B is divisible by γ/2 and uses these intervals as the proof’s exploration units.
  • Interval Exploration: For each interval I_k, the stopping time τ_k occurs when the interval has been selected u_interval = 2 log(n)/δ_0 times.This interval-level exploration threshold is used to show that a better program can be proposed.
  • Additional Selections: After τ_k, the proof isolates additional selections of an individual program beyond the interval’s initial exploration count.This decomposition separates interval exploration from repeated selection of a particular candidate.
  • Selection Bound: Theorem 3 bounds the expected number of additional selections for any program in an explored interval.The surrounding proof identifies this bound as the critical component used to control candidate selection.

A.2 Proof of Theorem 3

Theorem 3 bounds repeated selection of a program by combining a better-program proposal event, UCB concentration, and interval exploration. The resulting bound supports control of total selections across accepted candidates.

  • Good Event: The proof defines a good event combining concentration, proposal of a strictly better program, and UCB validity.These events ensure that the better candidate is proposed and its UCB remains above its true mean.
  • Selection Control: After a strictly better program is proposed, UCB ordering implies the lower-reward program is no longer selected.This contradicts any assumption that its additional selections exceed the designated threshold.
  • Probability Bounds: The proof combines concentration and failure bounds to control additional selections for each candidate.The stated probability bounds are independent of the stopping-time value used in the conditioning argument.
  • Improvement Event: The probability of failing to propose a program above the next reward interval is analyzed over u_interval consecutive trials using the optimizer’s improvement assumption.The argument links interval-level exploration to the probability of generating a γ-strictly better candidate.
  • Final Bound: Theorem 3 supplies the per-candidate bound needed for the final argument, whose total candidate contribution is controlled by the ε-Net cardinality.The proof explicitly invokes the bound together with the fact that |Θ_n| is at most N_ε.

A.4 Proof of Theorem 2

The proof compares POLCA with sequential updating under stochastic improvements and shows that cumulative improvements suffice for near-optimality without requiring consecutive successes. Its expected time remains bounded even when reward distributions lack a lower bound.

  • Sequential Updates: Sequential updating may require N := B/γ consecutive improvements to reach a near-optimal reward.The proof defines τ1 as the first time such a consecutive streak occurs.
  • POLCA: POLCA instead reaches near-optimal reward after N cumulative improvements because each proposal conditions on the best observation so far.Therefore, the stopping time for POLCA satisfies τ ≤ τ2.
  • POLCA: E[τ] ≤ B/(γδ0), because the time between improvements is modeled as an independent geometric random variable with mean 1/δ0.The bound follows after substituting N = B/γ.
  • Discussion: Without a lower bound on μ, POLCA retains O(N/δ0) complexity, whereas sequential updating may fail to converge.A single sufficiently bad proposal can force sequential updating to recover through many subsequent improvements.

B Implementation Details of POLCA

POLCA combines asynchronous evaluation, local rollout context, historical summarization, and semantic filtering to generate and evaluate diverse program candidates efficiently. Its proposal pipeline uses both recent evidence and population-level patterns while pruning semantically redundant programs.

  • Program Execution and Evaluation: POLCA asynchronously evaluates candidate programs on task minibatches, generating rollout tuples from program outputs, rewards, and feedback.Program-task interactions are dispatched and executed in parallel before aggregation.
  • Context Construction and Program Proposal: The optimizer combines local rollouts with a summarized global history to construct proposal contexts for new program parameters.New parameters are sampled from a proposal distribution conditioned on these contexts.
  • Context Construction and Program Proposal: The Summarizer partitions historical trajectories into successes and failures, then distills contrastive patterns into natural-language meta-gradients.Representative successful and failed trajectories are supplied alongside program parameters to respect context limits.
  • Semantic Filter based on ε-Net Design: SemanticFilter uses farthest-first traversal to construct an ε-net that retains candidates at least ε apart in semantic distance.The filter terminates when remaining candidates are semantically redundant.

C Instantiating Classical Search Algorithms

POLCA can reproduce several classical search strategies by changing only its priority function, while retaining a common optimization framework. The section instantiates sequential refinement, beam search, and UCB-style exploration across benchmark settings.

  • General Framework: Changing p_explore(·) lets POLCA mimic multiple classical search paradigms without altering the rest of the algorithm.This makes different search designs interchangeable on the same problem instance.
  • Sequential search (Iterative refinement): Sequential refinement uses LIFO ordering with k = 1, selecting only the newest program for further evaluation and refinement.This collapses the framework into a depth-first local search process.
  • Beam search: Beam search maintains k active beams and retains only the top-k newly validated candidates based on their initial scores.In POLCA, old programs receive priority −∞ while newly proposed programs are prioritized by current-iteration average reward.
  • Upper Confidence Bound (UCB): UCB adds an uncertainty bonus that prioritizes under-sampled programs and helps prevent premature convergence.The bonus increases when a program has few reward observations, balancing exploration and exploitation.
  • Benchmark Instantiations: POLCA’s framework is evaluated across agent, code-translation, and CUDA-kernel settings, including τ-bench, HotpotQA, VeriBench, and KernelBench metrics.The reported configurations include held-out τ-bench tasks, 140 VeriBench compilation tasks, and fastp evaluation relative to a PyTorch baseline.

D.3 Evaluation Metrics

The evaluation compares POLCA across multiple computational and temporal budgets, reflecting different bottlenecks in stochastic and inexpensive optimization settings. Across the reported benchmarks, POLCA is strongest under time-oriented, parallelized evaluation and proposal budgets, while sequential methods can be stronger early under total computational budgets.

  • Evaluation dimensions: Evaluation steps measure sequential operations when constituent metrics run in parallel, serving as a proxy for wall-clock time.The framework also evaluates total metric calls as a computational budget.
  • Evaluation dimensions: Proposal steps count sequential generation operations under a shared maximum number of parallel proposals per step.Number of proposals separately fixes the generative budget to assess candidate-generation efficiency.
  • Results: POLCA consistently outperforms baselines in proposal and evaluation steps because of its parallelized batch update design.With total metric calls and proposals fixed, it maintains strong final performance but may lag behind sequential methods early in search.
  • Results: On VeriBench, POLCA outperforms all parallelized baselines in total metric calls but initially remains slightly below sequential DSPy.Batch methods use less cumulative information per step than sequential updates, trading search depth for lower latency.
  • Results: On KernelBench, POLCA consistently outperforms baselines in evaluation and proposal steps and final performance, while sequential methods can be better early under metric-call or proposal budgets.The same trade-off reflects POLCA’s emphasis on minimizing wall-clock time through parallel execution.

D.6 More Ablation Results

The ablation and auxiliary analyses examine ε-Net, the Summarizer, ε sensitivity, reward modeling, token use, and representative optimized programs. The supplied results indicate that empirical-mean selection can outperform regression-based criteria in this setting, while the ablation figures compare ε choices across τ-bench and VeriBench.

  • Ablations: Figure 10 ablates POLCA’s ε-Net and Summarizer features, while Figure 11 studies ε values across τ-bench and VeriBench.Figure 11 uses average highest-score curves and standard-error shading across 3 independent seeds.
  • Reward modeling: A reward model maps program embeddings to expected rewards so that observations across programs can inform estimates for sparsely observed candidates.The described model uses logistic regression with regularization, while an ensemble of five regressors is trained on randomly sampled data subsets.
  • Reward modeling: Empirical-mean selection consistently outperforms all regressor-based criteria across the evaluated training-set sizes and metrics.The reported external testing suggests the regression model does not generalize reliably enough to surpass simple empirical estimation in this setting.
  • Token usage: Token accounting covers search-pipeline calls but excludes LLM calls made inside the optimized programs.A single 100-iteration τ-bench run totals 31,202,710 tokens, while HotpotQA totals 6,540,293 tokens; the reported VeriBench single-task 10-iteration run totals 634,045 tokens.
  • Examples: The representative examples span τ-bench prompt optimization, VeriBench Lean 4 translation, and KernelBench CUDA-kernel optimization.These examples illustrate optimized solutions across agentic reasoning, formal verification, and hardware-level performance tuning.

E.3 Veribench

The VeriBench example translates a Python square-function program into Lean 4 and checks its behavior through specifications, theorems, tests, and an imperative implementation. The broader benchmark task asks generative optimization algorithms to refine Lean 4 programs until they satisfy verification requirements.

  • VeriBench: VeriBench translates Python programs into verifiable Lean 4 programs and directly optimizes the formal code against verification requirements.The supplied example centers on a square function.
  • Formal verification: The formal specification includes non-negativity, zero, one, and multiplication properties combined into a post-condition.A correctness theorem states that the pre-condition implies this post-condition.
  • Implementation equivalence: The example also defines an imperative square implementation and states theorems for its tests and equivalence with the functional implementation.The equivalence theorem asserts square n = squareImp n.
  • Related optimization setting: KernelBench provides a separate optimization setting in which custom CUDA operators replace PyTorch operators, including opportunities for operator fusion and algorithmic changes.The supplied KernelBench passages describe this as custom-kernel optimization rather than VeriBench translation.
Loading 2603.14769v1…