POLCA: Stochastic Generative Optimization with LLM

ArXiv: 2603.14769

🎯 Pitch

Generative optimization fails catastrophically when feedback is noisy, but POLCA fixes this by forcing the LLM to maintain a diverse, persistent memory of past ideas. This simple change consistently outperforms existing algorithms across four benchmarks, proving that remembering what not to repeat is just as crucial as knowing what to improve.

---

1. Executive Summary

This paper introduces Prioritized Optimization with Local Contextual Aggregation (POLCA), a scalable framework for stochastic generative optimization where an LLM acts as the optimizer, guided by numerical rewards and text feedback to discover optimal program parameters (e.g., system prompts, CUDA kernels, Lean 4 code). POLCA maintains a priority queue memory buffer with an ε-Net semantic filtering mechanism (rejecting new candidates whose embedding distance to any existing program falls below a diversity threshold ε) and an LLM Summarizer for meta-learning across historical trials, evaluated on τ-bench, HotpotQA, VeriBench, and KernelBench using models including Gemini 2.0 Flash, Claude 3.5 Sonnet, and Claude 3.7 Sonnet. Across all benchmarks, POLCA consistently outperforms baseline algorithms—achieving a 13% improvement over the base prompt on τ-bench retail-domain pass@1 and a 95.2% compilation pass rate on VeriBench versus 88.8% for the next-best method—while proving theoretically that the UCB variant converges to near-optimal candidates under stochastic evaluations, establishing that a persistent, diversity-aware memory is critical for robust generative optimization in the face of noisy feedback, minibatch sampling, and stochastic program execution.

2. Context and Motivation

The Core Problem: Generative Optimization Breaks When Evaluations Are Noisy

This paper addresses a fundamental gap in the rapidly growing field of generative optimization—the practice of using LLMs as optimizers that iteratively refine program parameters (prompts, code, agent instructions) based on feedback from evaluation. The problem is deceptively simple to state: when the feedback signal is stochastic—due to noisy evaluations, random minibatch sampling, or inherently stochastic program behavior—existing generative optimization algorithms become unreliable, inefficient, or both.

The paper formalizes this as a stochastic generative optimization problem (Section 2), where the goal is to maximize the expected reward µ(θ) = E[reward of program P_θ] given a finite computational budget, but where the algorithm only ever observes noisy estimates of that reward. The challenge is not merely theoretical: it manifests concretely across the landscape of modern LLM applications. When optimizing an LLM agent's system prompt for multi-turn customer service (τ-bench), running the agent even once on a single task takes minutes, so only small minibatches can be used per optimization step. The agent itself is stochastic (LLM sampling introduces variance), the environment is stochastic (different user behaviors), and the evaluation might come from another LLM judge whose scoring is inconsistent. Each of these sources compounds: the optimizer sees a noisy signal, proposes modifications based on that noisy signal, and risks either (a) discarding genuinely good candidates that had unlucky evaluations, or (b) pursuing dead ends that scored well by chance.

The authors identify that this stochasticity is not an edge case—it is increasingly the default setting. As they note (Section 1), "not all tasks are verifiable and LLM-as-a-Judge is getting more common," and "running the program for all inputs is not always practical when problems get more complex." The central tension is that obtaining low-variance performance estimates is expensive (requiring many evaluations per candidate), yet the optimization process needs to evaluate many candidates to find good ones. Without a principled way to handle this tradeoff, optimization becomes either prohibitively expensive or dangerously unreliable.

Why This Matters: The Scaling Wall for Generative Optimization

The importance of this problem extends along three dimensions: practical deployment, theoretical understanding, and the trajectory of the field.

Practical significance. Generative optimization has demonstrated remarkable successes in automating tasks that traditionally required manual expert iteration—scientific discovery (Novikov et al., 2025), code revision (Pryzant et al., 2023; Chen et al., 2024), end-to-end system optimization (Cheng et al., 2024), and prompt engineering (Agrawal et al., 2025). However, the paper argues that these successes have largely been demonstrated in near-deterministic settings where evaluations are cheap and reliable. As the field pushes toward more complex, realistic problems—optimizing multi-turn agents, learning from human or LLM-judge feedback, scaling to large task distributions where full-batch evaluation is impossible—the stochasticity problem becomes a hard barrier. Without addressing it, generative optimization risks being confined to toy settings or requiring unrealistic amounts of computation.

Moreover, the paper points out a pernicious failure mode that compounds the problem over long optimization horizons: semantic redundancy. When an LLM optimizer receives noisy feedback, it tends to propose many semantically similar candidates—parameters that differ in superficial ways but encode essentially the same program logic. As stated in Section 1, "the search space grows linearly while semantically useful information does not." This means the optimizer burns through its evaluation budget re-discovering (and re-evaluating) essentially the same ideas, rather than genuinely exploring the parameter space. The cost is not just inefficiency—it is a failure mode where the optimization process stalls entirely because it cannot distinguish between "this direction hasn't worked" and "this direction hasn't been tried enough times yet under enough conditions to know if it works."

Theoretical significance. The paper frames stochastic generative optimization as a distinct problem class that does not cleanly map onto existing theoretical frameworks. Unlike standard finite-arm bandits (where the action set is known upfront), the parameter space Θ in generative optimization is "exponentially large and discrete without a natural ordering" and "can only be accessed through querying the LLM optimizer" (Section 2). Unlike standard stochastic optimization (where gradients provide local improvement signals), the LLM optimizer's proposals depend on the rich textual information in feedback and context—and that dependency is itself stochastic (the LLM may produce different proposals from the same input). This creates a unique coupling between exploration (which parameters to evaluate more), exploitation (which parameters to trust as good), and proposal generation (how to use current information to propose better parameters). The paper's theoretical analysis (Section 4) takes a first step toward understanding this coupling by establishing convergence conditions under an assumption about the optimizer's ability to make strict improvements, but the problem class itself is largely uncharted territory.

Trajectory of the field. Perhaps most critically, the paper argues that the field has been building generative optimization systems under an implicit assumption that evaluations are cheap and reliable enough to treat as ground truth. The authors cite examples: evolutionary search methods like AlphaEvolve (Novikov et al., 2025) "primarily address tasks with nearly deterministic verifiers and lack specific mechanisms to handle environments where the evaluation process is stochastic" (Section 6); Pareto-frontier methods like GEPA (Agrawal et al., 2025) are "susceptible to stochastic observations, as it falsely rejects candidates"; and sequential refinement methods like DSPy (Khattab et al., 2023) evaluate each proposed program once and move on, making them "heavily sensitive to the stochastic evaluation" (Section 5.1). The paper positions POLCA as a necessary corrective—a framework that is not another heuristic for deterministic settings, but rather a principled approach explicitly designed for the stochastic regime that increasingly characterizes real-world generative optimization problems.

Where Prior Approaches Fall Short

The paper identifies several distinct classes of prior work and diagnoses specific failure modes for each in the presence of stochasticity.

Iterative refinement (DSPy, TextGrad, Trace/OptoPrime). These methods perform sequential updates: evaluate the current parameter θ on some inputs, use the resulting feedback to propose an improved θ′, evaluate θ′ on (possibly different) inputs, and repeat. The problem, as the paper documents (Section 5.1), is that a single evaluation of a program on a small minibatch—or a single LLM-judge assessment—can be a highly noisy estimate of its true performance. A genuinely good parameter might score poorly in one iteration due to an unlucky minibatch draw, causing the optimizer to "improve" it in a wrong direction (or abandon it entirely). Conversely, a mediocre parameter might score well by chance and serve as the foundation for subsequent proposals that inherit its mediocrity. The sequential nature means there is no mechanism to revisit earlier candidates or average out noise across multiple evaluations—each step is a gamble on a single noisy observation.

The paper's τ-bench experiments make this concrete (Figure 2a, Table 1). OpenEvolve, which evaluates each proposed agent prompt on the 10 training tasks once, achieves a test pass@1 of 0.418—barely above the base prompt's 0.389—despite substantial exploration. The reason is not that OpenEvolve fails to propose good prompts; it is that OpenEvolve cannot reliably identify which of its proposed prompts are good, because it sees only a single noisy evaluation of each.

Evolutionary and population-based methods (AlphaEvolve, OpenEvolve). These methods maintain a population of candidates and use tournament selection, island models, or MAP-Elites to preserve diversity while evolving toward better solutions. The paper acknowledges their strength on deterministic code optimization tasks (Section 5.3, where OpenEvolve performs competitively on KernelBench) but identifies a critical vulnerability: population management decisions (which candidates survive, which are discarded) are based on fitness scores that are assumed to be approximately correct. When those scores are stochastic, the algorithm can "falsely reject candidates" (Section 6) that were unlucky in their evaluation or "falsely promote" candidates that were lucky.

This is not a subtle effect. In the τ-bench experiments (Section 5.1), OpenEvolve uses a single pass over the 10 training tasks to score each candidate. With binary 0/1 rewards per task and only 10 tasks, the variance is enormous—a truly good prompt might score 4/10 in one evaluation and 8/10 in another purely due to the agent's internal stochasticity and task sampling. OpenEvolve's selection mechanism treats the 4/10 score as the ground truth, eliminating candidates that might genuinely be superior.

Pareto-frontier methods (GEPA). GEPA (Agrawal et al., 2025) maintains a Pareto frontier of undominated programs—those that are not worse on any training instance than some other program. This is an elegant approach for deterministic multi-objective optimization, but the paper identifies two failure modes under stochasticity. First, as with evolutionary methods, the Pareto dominance relationship is contaminated by noise: a program that appears dominated on a particular minibatch might actually be superior in expectation. Second, and more subtly, the paper notes (Section 5.2) that for single-task optimization problems, "the Pareto frontier collapses" to a single point—the current best program. GEPA then degenerates into always selecting that single program for further refinement, losing the diversity that makes population-based methods powerful. This is not a bug in GEPA's design; it is a structural consequence of applying a multi-objective Pareto concept to a single-objective stochastic problem, where the "multiple objectives" are just noisy estimates of the same underlying quantity.

Beam search and tree search methods. These methods (Pryzant et al., 2023; Chen et al., 2024; Wang et al., 2023) explore multiple branches of improvement from a given starting point, typically scoring partial or complete solutions to decide which branches to pursue. The paper notes (Section 6) that Chen et al. (2024) attempts to learn a reward model from collected data to guide search, but this reward model itself "may fail in the presence of highly stochastic reward observations"—the regressor overfits to noise just as the search process does.

The broader issue is that these methods assume the scoring function (whether a learned model, an LLM judge, or a direct evaluation) is sufficiently reliable to make branching decisions. When it is not, search amplifies the errors: a good branch pruned early due to a noisy low score is lost forever, while a bad branch pursued due to a noisy high score wastes computation that could have been spent exploring. The paper's theoretical framework (Section 4) formalizes this: without mechanisms to average out noise and revisit candidates, search algorithms can require exponential time to escape from the noise floor.

Candidate curation via clustering/filtering. Several recent works attempt to address the redundancy problem by filtering or clustering candidates based on similarity. AlphaCode (Li et al., 2022) uses test-based rejection and execution-behavior clustering to reduce the pool of programs needing full evaluation. ShinkaEvolve (Lange et al., 2025a) uses embedding-based similarity detection combined with an LLM judge to decide whether new candidates are sufficiently novel to evaluate. Kim et al. (2025) and Wang et al. (2025a) use embedding clustering to collapse redundant reasoning states in tree search.

The paper acknowledges these as steps in the right direction but argues they remain empirically motivated heuristics rather than principled mechanisms: "all previous works rely on multiple heuristic hyper-parameters without clear implications" (Section 6). Specifically, they lack a theoretical connection between the filtering criterion and the underlying optimization objective. An embedding-based filter that rejects candidates "too similar" to existing ones is sensible, but without a theory linking embedding distance to reward difference, the choice of threshold is arbitrary. The paper's ε-Net mechanism is presented as a principled alternative—under mild assumptions about embedding quality (that it captures reward-relevant information), the ε parameter directly controls a coverage-cost tradeoff with formal guarantees (Section 4).

How This Paper Positions Itself

POLCA is positioned not as a new optimizer design or a new search algorithm per se, but as a framework for making any generative optimizer robust to stochasticity through persistent, diversity-aware memory. The key architectural insight is that the two primary challenges—noisy evaluations and semantic redundancy—are coupled and must be addressed together.

Noisy evaluations motivate persistent memory. If evaluations are noisy, you cannot trust a single measurement of a candidate's performance. You need to evaluate promising candidates multiple times, averaging out the noise. This requires a memory—some structure that retains candidates across iterations, tracks their evaluation history, and revisits them as new minibatches become available. The paper's priority queue memory Q serves exactly this role: each program in Q accumulates evaluation data over multiple minibatches, and its priority (empirical mean score) converges to its true expected reward as more data is collected. Critically, this means that a candidate that scored poorly on its first minibatch is not discarded—it stays in memory and can be re-evaluated, potentially revealing its true quality.

Persistent memory motivates semantic filtering. However, persistent memory creates a new problem: if every proposed candidate is added to Q, the memory grows linearly with the number of iterations, and the evaluation budget must be spread increasingly thin across all candidates. This is where the coupling with redundancy becomes critical. Because the LLM optimizer tends to propose semantically similar candidates (driven by similar contexts and noisy feedback), most new proposals are redundant—they encode programs that are essentially the same as ones already in memory. The ε-Net filtering mechanism exploits this: by rejecting candidates whose embedding distance to any existing program in Q is less than ε, it prevents the memory from filling with near-duplicates. This keeps |Q| bounded (theoretically by N_ε, the covering number of the parameter space at resolution ε), ensuring that the evaluation budget is concentrated on genuinely distinct candidates.

The paper explicitly contrasts this with prior filtering approaches by grounding the ε-Net in the optimization objective. Under the theoretical analysis (Section 4), ε controls the granularity of the discretization: candidates within distance ε are treated as effectively identical (their true rewards cannot be distinguished without exceeding the evaluation budget). This provides a principled basis for choosing ε—it is a user-specified tradeoff between approximation error (treating genuinely different programs as the same when ε is too large) and sample complexity (evaluating too many near-duplicates when ε is too small).

The Summarizer as meta-learning. The second key component, the LLM Summarizer, addresses a different coupling: between the quality of proposals and the breadth of information available to the optimizer. In sequential refinement methods, the optimizer sees only the most recent evaluation—a single data point. This is analogous to stochastic gradient descent with a mini-batch of size 1: high variance, slow convergence. The Summarizer distills the entire history stored in Q into a global context c_history that captures patterns across many candidates, many minibatches, and many evaluation outcomes. This provides the optimizer with a "momentum-like" signal (the paper draws an explicit analogy to Momentum-based gradient methods in Section 3) that stabilizes the search direction and prevents the optimizer from overreacting to the noise in any single evaluation.

A unifying framework, not a single algorithm. The paper is careful to present POLCA as a framework rather than a fixed recipe. Section 3 notes that the priority function p_explore(θ) can be modified to instantiate different search strategies—empirical mean (robust default), UCB (theoretically grounded exploration), beam search (greedy selection of recent proposals), or sequential refinement (LIFO ordering). Section C elaborates on these instantiations. This positions POLCA as a meta-algorithm that subsumes many existing approaches while adding the memory and filtering mechanisms that make them robust to stochasticity.

The theoretical analysis (Section 4) reinforces this positioning by proving that even a simplified version of POLCA (single proposal per iteration, UCB priority) converges to near-optimal candidates—specifically, candidates with reward in [B−γ, B] that the optimizer cannot be guaranteed to improve further—with a bound that cleanly separates the contribution of the optimizer's capability (how many proposals are needed to find a good candidate) from the contribution of evaluation noise (how many evaluations are needed to confirm that a candidate is good). This is not a tight practical bound, but it serves as an existence proof: the framework is sound, and the mechanisms (memory, ε-Net filtering, systematic exploration) are sufficient to overcome stochasticity in principle.

Where the paper does not go. The paper is explicit about its boundaries. It does not claim to solve the hardest problems—for the most difficult quintile of τ-bench tasks (bin 5 in the paper's difficulty analysis, implied by the 145-task held-out set), all methods perform near the base rate. It does not combine POLCA's memory mechanisms with PRM-guided tree search or more sophisticated proposal strategies—the optimizer O is assumed to be a black-box LLM that takes feedback and produces proposals, and improving O itself is left to future work. It does not address the cost of the Summarizer's LLM calls, which add to the total token budget (as estimated in Appendix D.8). And its theoretical guarantees rely on an assumption about the optimizer's ability to make strict improvements (Assumption 1) which, as the authors acknowledge, "may not always be realistic." These are not weaknesses per se—they define the scope of the contribution and open clear avenues for follow-up work.

3. Technical Approach

This is primarily a systems + theory paper whose core idea is that stochasticity in generative optimization—arising from noisy evaluations, random minibatch sampling, and stochastic program behavior—can be tamed by maintaining a persistent, diversity-aware memory that continuously updates candidate scores across multiple evaluation batches while using embedding-based filtering to prevent the memory from being overwhelmed by semantically redundant proposals.

3.1 Reader Orientation

POLCA builds a prioritized memory buffer (priority queue) combined with a semantic filtering gate (ε-Net) that sits between an LLM optimizer and the evaluation environment. The system solves the problem of optimizing program parameters (prompts, code, agent instructions) when each evaluation provides only a noisy estimate of true performance: instead of trusting any single evaluation to make irreversible decisions about which candidates to keep or discard, POLCA accumulates evidence over time, re-evaluates promising candidates across multiple minibatches to average out noise, and uses embedding similarity to reject new proposals that are near-duplicates of programs already in memory, thereby bounding the total number of distinct candidates that must be evaluated.

3.2 Big-Picture Architecture (Diagram in Words)

The system has six major components arranged in a loop:

1. Priority Queue Memory Q — a persistent buffer storing all accepted programs θ along with their accumulated evaluation history (multiple (score, feedback) pairs from different minibatches). Each program has a priority score p_explore(θ) (default: empirical mean reward across all evaluations) used to rank candidates. Q is initialized with the base program θ₀.

2. Minibatch Sampler — at each iteration, randomly draws a subset of tasks B ⊂ D with replacement from the full dataset. The same minibatch is used to evaluate both the programs selected for improvement (explore candidates) and newly proposed programs (new candidates), ensuring fair comparison.

3. Program Selector SelectPrograms — extracts the top-k programs from Q by priority score, forming the set Θ_explore that will be evaluated on the current minibatch and then used as seeds for proposing new programs.

4. Evaluator Evaluate — runs each program in Θ_explore (or later Θ_new) on every task in minibatch B, collecting for each (program, task) pair: the program's output y, a numerical reward r from the Guide G, and textual feedback f. All (program, task) evaluations are parallelized asynchronously. Results are stored as rollout tuples s = (θ, ω, x, y, r, f).

5. LLM Optimizer O + Summarizer — for each program in Θ_explore, constructs a context containing (a) the local rollouts from the current minibatch for that specific program, and (b) a global summary c_history produced by an external LLM (the Summarizer) that analyzes patterns across the entire priority queue Q. The optimizer then proposes a new program θ' ~ Π(· | C_θ) designed to improve upon the seed. All proposals happen in parallel, producing Θ_raw.

6. Semantic Filter SemanticFilter — an embedding-based ε-Net gate that accepts a new program θ' only if its embedding distance to every existing program in Q ∪ Θ_new exceeds a threshold ε. This is implemented as a farthest-first greedy traversal: starting from Θ_new = ∅, repeatedly select the candidate in Θ_raw with maximum minimum distance to the current accepted set, and add it if that maximum distance exceeds ε. The surviving set Θ_new is then evaluated on the same minibatch B, its results are merged into Q via UpdateStats, and the loop repeats.

Information flow per iteration: Minibatch B is sampled → top programs from Q are evaluated on B → their updated stats in Q trigger re-ranking → Summarizer produces c_history from Q → Optimizer proposes Θ_raw from local rollouts + c_history → SemanticFilter prunes Θ_raw to Θ_new → Θ_new is evaluated on B → Q is updated → loop.

3.3 Roadmap for the Deep Dive

• First, the formal problem statement (Section 2 formalization) and the core objective: what µ(θ) means, what the optimization budget constrains, and why standard algorithms fail—this grounds all subsequent design choices.
• Second, the minibatch evaluation mechanism and the priority queue memory, because these are the foundational defenses against stochasticity: accumulating evidence across multiple evaluations and multiple minibatches.
• Third, the proposal mechanism (Optimizer + Summarizer), which controls how new candidates are generated from accumulated information—the "learning" component that must work despite the optimizer itself being stochastic.
• Fourth, the semantic filtering mechanism (ε-Net), which is the scalability mechanism that prevents memory explosion while ensuring diversity, and which has theoretical justification.
• Fifth, the evaluation parallelism and program update mechanics (Algorithms 2–4), which are implementation-critical for wall-clock efficiency.
• Sixth, the priority function design space (Section C), showing how POLCA subsumes classical search strategies through a single interface.
• Seventh, the theoretical analysis setup (Section 4 key elements), which provides the formal justification for why persistent memory + UCB exploration + ε-Net filtering is sufficient for convergence.

3.4 Detailed, Sentence-Based Technical Breakdown

The Stochastic Generative Optimization Objective (Section 2 Formalization)

The paper formalizes the optimization problem as finding parameters θ for a program P_θ that maximize expected performance over a data distribution D. The objective is:

$\mu(\theta) = \mathbb{E}_{\omega, x \sim D}\left[\mathbb{E}_{y \sim P_\theta(x)}[G_r(\omega, y, x)]\right]$

where $(x, \omega) \sim D$ means a task input $x$ and side information $\omega$ are sampled from the task distribution; $y \sim P_\theta(x)$ means the program produces an output $y$ given input $x$ (this may be stochastic—LLM sampling, environment randomness); and $G_r(\omega, y, x)$ is the numerical reward returned by the Guide $G$ (which itself may be stochastic—LLM judge noise, human subjectivity).

What it computes: the expected reward of parameter θ, averaging over three independent sources of stochasticity: (1) which task is drawn from the distribution, (2) what output the program produces for that task, and (3) what score the evaluator assigns to that output. The result is a single number in [0, B] that represents the true quality of θ.

Why this form: this three-level expectation captures the full stochasticity the paper addresses. If any of the three were deterministic (e.g., the evaluator always produces the same score for the same output), the problem would simplify. The nesting E_x E_{y|x} E_{r|y} is not just notation—it reflects the actual execution pipeline: sample a task → run the program → evaluate the output. This decomposition matters because it means variance can arise from any level, and POLCA's mechanisms must work regardless of which level dominates.

The optimization goal under a computational budget is:

$\max_{\text{Alg}} \mathbb{E}[\mu(\theta_{\text{best}})]$

where the outer expectation is over the joint stochasticity of data sampling, program execution, Guide evaluation, LLM optimizer randomness, and any internal randomness of the algorithm itself. The algorithm Alg coordinates interactions between the dataset D, the Guide G, and the LLM optimizer O, and must return a single best-found parameter θ_best at budget exhaustion.

Critical property of the parameter space: Θ is "exponentially large and discrete without a natural ordering" (Section 2). This distinguishes generative optimization from standard bandit problems: the algorithm does not have access to the full action set upfront. Parameters can only be discovered by querying the LLM optimizer O, and "the proposal distribution of the LLM optimizer is highly dependent on the specific information in (θ, x, y, r, f, c) provided at each iteration." This means the algorithm cannot simply enumerate and evaluate—it must actively steer the optimizer toward promising regions of parameter space by carefully choosing which seed programs to provide feedback on and what context to include.

Minibatch Evaluation and Priority Queue Memory (Algorithm 1 Core Loop)

The evaluation bottleneck is fundamental: "doing a full evaluation of P_θ in every iteration is computationally out of reach" (Section 3). For τ-bench, evaluating an agent on all training tasks would require running multi-turn conversations for each task—minutes per evaluation. For HotpotQA with 100 tasks, full-batch evaluation would mean 100 LLM calls per candidate. The solution is minibatch sampling with persistent memory.

Minibatch sampling. At each iteration, SampleMinibatch(D) draws B tasks {(ω_i, x_i)}_{i=1}^B randomly with replacement from the dataset. The minibatch size B is a hyperparameter (e.g., batch_size = 2 for τ-bench experiments in Section 5.1). The same minibatch B is used to evaluate both Θ_explore (programs selected for improvement) and Θ_new (newly proposed and filtered programs). The paper states this explicitly: "The same minibatch evaluation is performed for both Θ_explore and the newly proposed Θ_new to ensure a fair comparison, thereby mitigating potential bias arising from task-specific variance."

This is a subtle but important design choice. If Θ_explore and Θ_new were evaluated on different minibatches, a new program that appears to outperform an existing one might simply be benefiting from an easier task draw. By using the same B, any difference in scores between Θ_explore and Θ_new reflects genuine performance differences (modulo the remaining stochasticity from program execution and evaluation, which is averaged out over time).

Priority queue memory. The priority queue Q is the persistent repository of all accepted programs and their evaluation histories. Each entry stores a program θ and its accumulated data: {(θ, ω_n, x_n, y_n, r_n, f_n)}_{n=1}^N, where N grows over time as the program is re-evaluated on different minibatches. The priority (ranking score) for each program is the empirical mean:

$p_{\text{explore}}(\theta) = \frac{1}{N} \sum_{n=1}^{N} r_n$

where $N$ is the total number of reward observations accumulated for program $\theta$ across all minibatches in which it was evaluated, and $r_n$ are the individual reward values $\in [0, B]$.

What it computes: the simple average of all rewards observed for a given program. This is an unbiased estimator of µ(θ) that becomes more accurate as N increases—by the law of large numbers, p_explore(θ) → µ(θ) as N → ∞.

Why this form: the empirical mean is the simplest variance-reduction mechanism. Under sub-Gaussian noise (assumed in Section 4), the estimation error scales as O(σ/√N). By retaining programs across iterations and accumulating observations, POLCA converts the high-variance single-evaluation problem into a lower-variance multiple-evaluation problem. Crucially, the paper does not require p_explore to be the empirical mean—it is the default, chosen for robustness. Section C and Section 4 explore alternatives: UCB score bµ + β√(log n / T) for provable exploration, timestamp-based LIFO ordering for sequential search, and iteration-specific mean for beam search.

The SelectPrograms and UpdateStats operations. At the start of each iteration, SelectPrograms(Q) returns the top-k programs by p_explore, where k is a hyperparameter (e.g., num_candidates = 5 in the τ-bench experiments). These form Θ_explore. After evaluation, UpdateStats(Q, S) integrates new rollout data S into Q for all affected programs, updating their empirical means and re-sorting the queue. The re-sorting is critical: a program that was previously low-ranked may rise as more data reveals its true quality, while a program with a lucky initial evaluation may fall as regression to the mean occurs.

How this addresses the three sources of stochasticity. The paper explicitly states: "This architecture directly addresses the three sources of stochasticity by continuously updating the dynamic priority queue Q." For minibatch sampling noise: evaluating the same program on different minibatches averages out task-specific variance. For program execution noise: evaluating the same program multiple times on the same task (implicitly, through different iterations) averages out sampling variance from the LLM. For evaluation noise: repeated evaluations of the same program-output pair (if the evaluator is stochastic) similarly average out.

The guarantees are asymptotic (more data → better estimates), not finite-sample, but the practical effect is that "promising candidates with temporarily low empirical means can be revisited and refined later, while those with low potential are eventually deprioritized after sufficient sampling."

The Proposal Mechanism: Optimizer + Summarizer (ProposePrograms, Algorithm 3)

Given the seed programs Θ_explore and their current-minibatch evaluations, the system must generate new candidate programs that are likely to improve upon them. This is the role of the LLM Optimizer O, but critically, the optimizer does not see only local information—it also receives a global context summary distilled from the entire priority queue.

Summarizer: generating global context c_history. The Summarizer is an external LLM component that processes the complete trajectory history stored in Q to produce high-level optimization guidance. For each program θ in Q, its history H_θ (all accumulated evaluation tuples) is partitioned into:

• Successes H⁺_θ: evaluation tuples where reward r > τ (for some threshold τ)
• Failures H⁻_θ: evaluation tuples where reward r ≤ τ

The Summarizer receives a contrastive sample—for each program, one representative success trajectory and one representative failure trajectory—along with the program parameters themselves. It is prompted (via the XML-structured template shown in Section 3) to produce:

• <reasoning>: analysis of key patterns and strategies leading to success or failure across the population
• <summary>: concrete, actionable recommendations for improving output quality based on observed patterns

The paper draws an explicit analogy: "utilizing only the current minibatch S_θ is analogous to a standard first-order update in numerical optimization. By incorporating c_history from the Summarizer, the process mirrors Momentum-based methods, leveraging the trajectory of past evaluations to stabilize the search and escape local optima."

Why contrastive sampling? The contrastive design (one success, one failure per program) is not arbitrary. It forces the Summarizer to identify discriminative patterns—what distinguishes programs that work from those that don't—rather than merely describing aggregate statistics. This is fundamentally different from, say, feeding the Summarizer only the top-K programs, which would bias it toward what works without contrasting against failure modes.

Local context construction. For each seed program θ ∈ Θ_explore, the system extracts its current-minibatch rollouts S_θ = {(θ, ω_i, x_i, y_i, r_i, f_i)}_{i=1}^B and augments them with the global summary c_history to form the full context:

$C_\theta = \{(\theta, x_i, y_i, r_i, f_i, c_{\text{history}})\}_{i=1}^B$

The optimizer then samples a new proposal from its distribution conditioned on this context: θ' ∼ Π(· | C_θ). All proposals across all seeds in Θ_explore happen in parallel—the ProposePrograms function queues all contexts and dispatches LLM calls asynchronously.

Why include the seed program in the context? The context explicitly includes the seed program θ itself, not just its evaluations. This allows the optimizer to see what produced the observed outcomes, enabling targeted modifications (e.g., "the instruction about verifying user identity was helpful but too verbose—shorten it while preserving the key steps"). Without the seed program in context, the optimizer would only see abstract feedback without knowing what structural choices led to it.

What makes this different from sequential refinement? In DSPy-style sequential optimization, the optimizer sees a single (program, feedback) pair per iteration and proposes one improvement. POLCA's proposal mechanism differs in three ways: (1) the optimizer sees feedback for multiple seed programs simultaneously (via parallel proposals from Θ_explore), (2) it receives the global summary c_history aggregating patterns across the entire history, not just the most recent step, and (3) multiple proposals are generated in parallel from different seeds, creating a batch of diverse candidates rather than a single sequential chain. This parallel proposal generation is what the paper means by "parallel starting points exploit the stochasticity of the optimizer more effectively than sequential baselines" (Section 5.3).

Semantic Filtering via ε-Net (SemanticFilter, Algorithm 4)

The ε-Net filtering mechanism is the scalability component that prevents the priority queue from growing without bound while ensuring the memory retains semantically diverse programs. Without filtering, the paper warns that "indiscriminately adding all new programs to the memory would cause Q to grow linearly with the number of iterations," leading to "prohibitive sample complexity when attempting to identify the best program."

Why filtering is necessary: the redundancy problem. The key observation is that "LLM-based optimizers tend to propose many semantically similar parameters over time" because "the input context to O often exhibits comparatively low variance." This happens for two reasons: (1) minibatches may overlap or repeat across iterations, so the optimizer sees similar task inputs, and (2) the same high-performing programs are repeatedly selected as seeds from Q (since they stay at the top of the priority ranking), so the optimizer receives similar seed programs. The result: "the growth of useful information in Q does not scale at the same rate as the number of programs." The filter corrects this by admitting only programs that are semantically distinct from everything already stored.

Embedding function. The filter relies on an embedding function ϕ: Θ → R^d that maps program parameters into a dense vector space. The paper uses Google's Gemini embedding models (e.g., gemini/text-embedding-004) and defines semantic distance as Euclidean distance in the embedding space:

$\tilde{d}(\theta, \theta') = \lVert\phi(\theta) - \phi(\theta')\rVert_2$

where $\phi(\theta)$ is the embedding vector for program $\theta$, and $\lVert\cdot\rVert_2$ is the standard Euclidean norm.

What it computes: a scalar distance between two programs in the embedding space. Parameters that encode similar instructions or logic will have small distance; parameters that encode fundamentally different approaches will have large distance.

Why Euclidean distance? The paper implicitly chooses Euclidean distance because it corresponds to the natural geometry of an ε-Net in a normed vector space. In an ε-Net, any two points are at least ε apart in the chosen metric, and the covering number N_ε (the maximum size of an ε-separated set) is bounded by the packing number of the space, which is finite for bounded subsets of R^d. This finiteness is what provides the theoretical bound on |Q|.

The ε-Net acceptance criterion. A new program θ' ∈ Θ_raw is accepted into Θ_new (and subsequently Q) only if:

$\min_{\theta \in Q \cup \Theta_{\text{new}}} \tilde{d}(\theta', \theta) > \varepsilon$

where $\varepsilon > 0$ is a user-specified diversity threshold. In words: the new program must be at least ε away from every program already in the priority queue AND every program already accepted in the current batch.

What it computes: the minimum embedding distance from the candidate to the existing population. If this minimum exceeds ε, the candidate is deemed sufficiently novel; otherwise, it is rejected as redundant.

Why this form: the ε-Net property ensures that for any two programs in Q, their distance is at least ε. This means Q is an ε-packing of the parameter space—a set of points that are all mutually separated by at least ε. The size of any ε-packing is bounded by the covering number N_ε, which depends on the geometry of Θ and the embedding ϕ but is finite for any reasonable embedding of a bounded discrete space. This bound is what prevents unbounded growth: no matter how many iterations POLCA runs, |Q| cannot exceed N_ε.

The farthest-first greedy implementation (Algorithm 4). The filter does not simply test each θ' independently—that would make the outcome depend on the order in which candidates are processed. Instead, it uses farthest-first traversal:

1. Initialize Θ_new = ∅ and Θ_remaining = Θ_raw.
2. While Θ_remaining is non-empty:
   • For each θ ∈ Θ_remaining, compute d(θ) = min_{θ' ∈ Q ∪ Θ_new} d̃(θ, θ').
   • Find θ* = arg max d(θ) with maximum distance d_max = d(θ*).
   • If d_max > ε: transfer θ* from Θ_remaining to Θ_new.
   • Else: terminate (all remaining candidates are within ε of something already accepted).

Why farthest-first? This greedy strategy is a standard 2-approximation for constructing a maximal ε-packing. By always selecting the candidate farthest from the current accepted set, it ensures that the final Θ_new is as diverse as possible given the raw proposals, rather than arbitrarily rejecting later proposals that happen to be similar to earlier ones. The termination condition (when the maximum remaining distance falls below ε) guarantees that every rejected candidate is within ε of something that was accepted, meaning no genuinely novel direction is lost—any rejected program could be approximately represented by an accepted one.

The ε tradeoff. The parameter ε directly controls the granularity of discretization. The paper's ablation study (Figures 3b, 3c) shows:

• ε = 0: no filtering, all candidates accepted → worst performance (memory grows unbounded, evaluation budget spread too thin)
• Small ε (e.g., 0.02 for VeriBench): fine discretization, many distinct candidates → better asymptotic performance but slower initial progress (more candidates to evaluate before any is well-estimated)
• Large ε (e.g., 0.3 for τ-bench): coarse discretization, few candidates → faster initial progress (quickly identifies broad regions of good performance) but potentially worse asymptotic performance (may collapse distinct programs into the same bucket)

The paper concludes: "POLCA's performance is not very sensitive to the exact ε value within a certain range" and "when a reasonable ε value is selected, it improves speed while incurring only negligible approximation error."

Theoretical justification. The ε-Net filtering is not merely a heuristic—it is essential for the convergence proof in Section 4. The bound on |Q| by N_ε enters directly into the sample complexity term: the number of evaluations needed to estimate rewards for all programs scales with N_ε, not with the total number of iterations. Without the ε-Net, N_ε would be replaced by the total number of distinct programs generated, which grows with n and leads to a worse (potentially unbounded) sample complexity.

Embedding quality assumption. The paper implicitly assumes that the embedding ϕ captures reward-relevant information: programs that are close in embedding space should have similar expected rewards. This is a mild assumption given modern embedding models trained on massive text corpora, but it is an assumption nonetheless. If the embedding fails to distinguish programs with genuinely different performance, the ε-Net may either (a) reject truly novel programs because they look similar in the embedding (if ε is too small relative to embedding noise), or (b) accept programs that are effectively identical because they look different in the embedding (if ε is too large). The paper does not systematically characterize embedding quality across domains, leaving this as implicit reliance on the chosen embedding model.

Parallel Evaluation Architecture (Evaluate, Algorithm 2)

The Evaluate function is the workhorse that runs programs on tasks and collects results. Its design prioritizes throughput through full asynchrony.

Algorithm structure. For a set of programs Θ̃ and a minibatch B:

1. Build a global task queue T containing all (program, task) pairs: T = {(θ, x, ω) : θ ∈ Θ̃, (ω, x) ∈ B}.
2. For each (θ, x, ω) ∈ T in parallel:
   • Execute the program: y ~ P_θ(x) (this may involve LLM calls, tool usage, or compilation)
   • Evaluate via the Guide: r ~ G_r(ω, x, y) (numerical score) and f ~ G_f(ω, x, y) (textual feedback)
   • Construct rollout tuple s = (θ, ω, x, y, r, f) and thread-safely append to S
3. Wait for all threads to complete and return S.

Why full parallelism matters. The paper notes that "when program execution or guide evaluation rely heavily on LLM calls, this parallelization becomes significantly more efficient, as the parallelization of LLM API calls can be easily implemented." For τ-bench, with |Θ̃| candidates (say 5) and |B| tasks (say 2), this means 10 parallel LLM-agent runs, each potentially taking minutes, all happening simultaneously rather than sequentially. The evaluation step is the primary bottleneck in most generative optimization pipelines, so parallelization directly translates to wall-clock speedup.

Separation of Θ_explore and Θ_new evaluation. Algorithm 1 calls Evaluate twice per iteration: once for Θ_explore (line 5) and once for Θ_new (line 9), both on the same minibatch B. This ensures that new proposals are scored against exactly the same tasks as the seeds they aim to improve upon, eliminating minibatch selection bias from the comparison. The parallelized evaluation means both calls can fully utilize available compute resources.

Context Construction and Program Proposal Mechanics (Algorithm 3 Detail)

Algorithm 3 fleshes out the ProposePrograms subroutine with specific implementation details.

Summarizer invocation. Before proposing any new programs, the Summarizer processes the priority queue Q to produce c_history. The paper specifies a particular strategy for selecting what to show the Summarizer given context limits:

"To maintain a representative view while adhering to context limits, we employ a Contrastive Sampling strategy, providing the LLM with program parameters alongside paired representative trajectories (one r > τ and one r ≤ τ)."

The Summarizer prompt (reproduced in full in Section 3) uses XML-style tags (<reasoning>, <summary>) to structure the output, separating internal analysis from actionable guidance. This structured format makes the summary parseable and ensures the optimizer receives concrete recommendations rather than vague commentary.

Per-seed proposal generation. For each θ ∈ Θ_explore, the local rollouts S_θ are combined with c_history to form C_θ. Each C_θ is added to a task queue U, and all proposals are generated in parallel: θ' ~ Π(· | C_θ). The set of all generated proposals is Θ_raw.

What the optimizer sees vs. what it doesn't. The optimizer sees (a) the seed program θ that produced the rollouts, (b) the specific inputs x_i it was evaluated on, (c) its outputs y_i for those inputs, (d) the numerical rewards r_i it received, (e) the textual feedback f_i (e.g., error messages, critiques), and (f) the global summary c_history. It does NOT see other seed programs' rollouts directly—cross-program learning happens only through the Summarizer's c_history. This is a deliberate information bottleneck: if the optimizer saw all rollouts from all seeds, the context would be enormous (5 seeds × 2 tasks each = 10 full evaluation trajectories) and the optimizer might struggle to extract a coherent improvement direction. The Summarizer compresses this cross-program information into a concise form.

Priority Function Design Space (Section C, Instantiating Classical Search)

The paper demonstrates POLCA's universality by showing how different priority functions p_explore instantiate classical search paradigms within the same framework.

Sequential search (iterative refinement). Set p_explore(θ) = t_θ (the creation timestamp of θ), restrict k = 1, and use LIFO ordering. This collapses POLCA into a depth-first chain: always select the most recently created program, generate one improvement, add it to memory, and repeat. This is identical to DSPy-style sequential refinement but with the memory buffer still accumulating evaluation history (which DSPy does not do).

Beam search. Allow the optimizer to propose multiple new programs per seed. Set p_explore(θ') = r̄(θ') for newly proposed programs, where r̄ is the average reward from evaluation on the current iteration only. Set p_explore(θ) = -∞ for all older programs. This ensures the priority queue retains only the top-scoring candidates from the most recent generation—classic beam search behavior. The paper notes this "might be efficient in deterministic settings; however, in the presence of stochasticity, discarding historical evaluations and evaluating each program only once may lead to suboptimal results."

Upper Confidence Bound (UCB). This is the theoretically motivated variant analyzed in Section 4. The priority becomes:

$p_{\text{explore}}(\theta) = \hat{\mu}_{\theta, T_\theta(t)} + \beta \sqrt{\frac{\log(n)}{T_\theta(t)}}$

where $\hat{\mu}_{\theta, T_\theta(t)}$ is the empirical mean of program $\theta$ after $T_\theta(t)$ observations at iteration $t$, $n = \sum_{\theta' \in Q} T_{\theta'}(t)$ is the total number of evaluations across all programs, and $\beta > 0$ controls the exploration-exploitation tradeoff.

What it computes: the empirical mean plus an exploration bonus that increases with uncertainty (when T_θ(t) is small) and with the total budget n (ensuring sufficient exploration even as more evaluations accumulate). The second term β√(log n / T) is the standard UCB bonus for sub-Gaussian rewards, derived from Hoeffding's inequality: with probability at least 1 - 1/n², the true mean lies within this radius of the empirical mean.

Why this form: the UCB bonus ensures that every program with a finite number of observations retains some chance of being selected, proportional to how uncertain its reward estimate is. This prevents the algorithm from prematurely converging to a suboptimal program that happened to score well early. The log(n) factor provides a union bound over all iterations, ensuring the confidence intervals hold simultaneously with high probability.

Why the paper defaults to empirical mean. Despite proving convergence for UCB, the experiments (except the theoretical analysis) use empirical mean as the priority. This is pragmatic: UCB requires knowing (or estimating) σ, the sub-Gaussian parameter of the reward noise, which is domain-specific and hard to calibrate. The empirical mean is parameter-free and, in practice, the repeated evaluation of top programs naturally provides exploration because high-ranked programs are evaluated more often, reducing their uncertainty over time, while programs that rise in the ranking get their turn.

The Complete POLCA Algorithm Walkthrough

Putting all components together, here is what happens in a single iteration of Algorithm 1, annotated with the specific mechanics:

Step 1 (Line 3): Sample minibatch. B = SampleMinibatch(D) draws B tasks from the dataset. For τ-bench with batch_size = 2 and num_batches = 1, this means 2 tasks per iteration. For HotpotQA, similarly batch_size = 2. These tasks are fixed for the entire iteration.

Step 2 (Line 4): Select programs for exploration. Θ_explore = SelectPrograms(Q) extracts the top-k programs by priority. For τ-bench, num_candidates = 5, meaning the 5 programs with highest empirical mean score are selected as seeds for this iteration.

Step 3 (Line 5): Evaluate seeds on minibatch. S = Evaluate(Θ_explore, B, G) runs each of the 5 seed programs on each of the 2 tasks (10 evaluations total), all in parallel. Each evaluation produces a reward r and feedback f. The rewards are binary for τ-bench (0 or 1 per task) and HotpotQA (0 or 1), and in [0,1] for VeriBench (composite score) and KernelBench (speedup-based).

Step 4 (Line 6): Update memory with seed results. Q = UpdateStats(Q, S) integrates the new evaluation data into the priority queue. For each seed program, its N increases by |B| (2 observations added), its empirical mean is recomputed, and Q is re-sorted. Programs that consistently score well maintain their high rank; programs that score poorly this iteration may drop.

Step 5 (Line 7): Generate proposals. Θ_raw = ProposePrograms(O, S, Q) invokes the Summarizer to produce c_history from the entire queue, then for each seed in Θ_explore, constructs C_θ from local rollouts + c_history, and calls the optimizer O to propose a new program θ'. With 5 seeds, this produces 5 raw proposals, generated in parallel.

Step 6 (Line 8): Filter proposals. Θ_new = SemanticFilter(Θ_raw, Q) applies the farthest-first ε-Net algorithm to the 5 raw proposals. Starting from Θ_new = ∅, it repeatedly selects the candidate farthest from Q ∪ Θ_new and adds it if that distance exceeds ε. For τ-bench, ε = 0.15 (from the ablation in Figure 3b, the recommended range). Depending on how diverse the proposals are, Θ_new may contain anywhere from 0 to 5 programs. If all 5 proposals are semantically similar to programs already in Q (distance ≤ ε), Θ_new could be empty, and the iteration would skip to the next loop.

Step 7 (Line 9): Evaluate new proposals on same minibatch. S = Evaluate(Θ_new, B, G) runs each accepted new proposal on the same 2 tasks, parallelized. This gives each new program its initial performance estimate on exactly the same tasks as the seeds, enabling direct comparison.

Step 8 (Line 10): Update memory with new results. Q = UpdateStats(Q, S) adds the new programs to the queue with their initial evaluation data (N = 2 observations each) and re-sorts. New programs with high scores may immediately rank near the top; those with low scores start lower but remain in memory for potential future re-evaluation.

Step 9 (Line 2): Budget check. The loop repeats until the total evaluation budget (number of metric calls, e.g., 2000 for HotpotQA, 50 per task for VeriBench) is exhausted.

Step 10 (Line 12): Return best program. θ_best = arg max_{θ ∈ Q} p_explore(θ) returns the program with the highest empirical mean score across all its accumulated evaluations.

Why this order (evaluate seeds → propose → filter → evaluate new)? The sequence is critical: seeds are evaluated before proposals are generated, so the proposals can condition on the most recent feedback (not stale evaluations). But both seeds and new proposals use the same minibatch, so the comparison is fair. Proposals are generated before filtering because filtering requires the full set of raw proposals to perform farthest-first selection—filtering them one at a time as they are generated would be order-dependent and suboptimal. New proposals are evaluated after filtering to avoid wasting evaluation budget on redundant candidates.

4. Key Insights and Innovations

Innovation 1: Generative Optimization Is Fundamentally a Stochastic Problem, Not a Deterministic One

The paper's most foundational conceptual move is to redefine the generative optimization problem class around stochasticity as a first-class concern rather than an edge case. Prior work—spanning evolutionary methods (Novikov et al., 2025; Sharma, 2025), Pareto-frontier search (Agrawal et al., 2025), iterative refinement (Khattab et al., 2023; Cheng et al., 2024), and beam search (Pryzant et al., 2023)—implicitly or explicitly assumes that evaluations provide approximately reliable signals, and that optimization algorithms can safely make irreversible decisions (discarding candidates, pruning branches, selecting for refinement) based on single or few evaluations. The paper's core diagnostic is that this assumption breaks down across all current generative optimization applications, not just niche ones: stochasticity arises from minibatch sampling of large task distributions (cannot evaluate on all tasks every iteration), inherent program stochasticity (LLM agents produce different outputs for the same input), and evaluator noise (LLM-as-a-Judge is increasingly common and inherently non-deterministic). Unlike image classification where a single forward pass gives a deterministic accuracy estimate, evaluating an LLM agent's system prompt on 2 out of 100 tasks—where the agent itself may succeed or fail on the same task across trials—yields a reward signal with enormous variance.

This reframing is significant because it provides a unified explanation for previously conflicting or puzzling results in the literature. The paper demonstrates empirically (Section 5.1, Figure 2a) that algorithms designed for deterministic settings (GEPA, OpenEvolve) degrade substantially under the stochastic conditions of τ-bench, even though they perform competitively on deterministic benchmarks like KernelBench (Section 5.3, Figure 2d). This explains why methods that "work" in code optimization (where compilation tests are deterministic) fail when applied to agent optimization (where everything is stochastic): it is not that the optimizer design is flawed, but that the memory and evaluation architecture is not robust to noise. The paper does not claim to have discovered stochasticity—it claims that treating it as the central design constraint, rather than an afterthought, fundamentally changes what a generative optimization algorithm should look like.

The paper formalizes this diagnosis through the three-level expectation in the objective µ(θ) (Section 2), which explicitly decomposes stochasticity into task sampling, program execution, and evaluator noise. This is not merely notation; it is an argument that these sources are separable in principle and that an algorithm must address all three simultaneously. Prior work typically addressed at most one—for example, minibatch sampling in prompt optimization (Pryzant et al., 2023) without accounting for evaluator noise. The paper's architecture (persistent memory + repeated evaluation + ε-Net filtering) is designed to handle all three through a single mechanism (accumulating noisy observations over time), which is conceptually cleaner than ad-hoc fixes for each source.

Innovation 2: Persistent Memory with Continuous Score Updates Replaces Irreversible Selection Decisions

The dominant paradigm in generative optimization—from DSPy's sequential refinement to AlphaEvolve's tournament selection to GEPA's Pareto dominance—is binary keep/discard: evaluate a candidate, decide whether it is good enough to survive, and irreversibly prune or promote. This is inherited from evolutionary algorithms and beam search where it works well under deterministic fitness evaluations. The paper's key insight is that under stochasticity, this binary decision is fundamentally premature: a genuinely good candidate may score poorly on its first minibatch due to unlucky task draws or LLM sampling variance, and discarding it means losing a potentially optimal solution forever.

POLCA's persistent priority queue memory Q replaces this binary logic with continuous accumulation of evidence. Rather than deciding "keep or discard" after a single evaluation, the memory retains all candidates indefinitely, continuously updates their empirical mean scores as they are evaluated on new minibatches, and allows candidates to rise or fall in the ranking as more data reveals their true quality. This is conceptually analogous to the difference between making a hiring decision after one interview versus maintaining a pool of candidates who are repeatedly assessed over time—the latter is more robust to noise but requires an architecture that supports it.

This is not merely an incremental improvement over prior filtering or caching mechanisms. Existing methods like ShinkaEvolve (Lange et al., 2025a) or GEPA maintain populations but make irreversible pruning decisions based on current fitness estimates. The paper's ablation (Section 5.4, Figure 3a) demonstrates that the continuous-update mechanism (what the paper calls "vanilla POLCA"—the priority queue without ε-Net or Summarizer) already substantially outperforms baselines, confirming that the memory architecture itself is the primary driver of robustness. The empirical evidence is strongest in τ-bench (Figure 2a, Table 1), where OpenEvolve's single-evaluation-per-candidate approach achieves only a 0.418 pass@1 (barely above the base 0.389), while POLCA's continuous accumulation reaches 0.439—the gap comes not from generating better candidates but from more accurately identifying which candidates are good.

The theoretical analysis (Section 4) provides formal grounding for why this matters. Under sub-Gaussian reward noise, distinguishing between two programs with a reward gap of γ requires O(σ²/γ²) evaluations (Lemma 3). A binary keep/discard decision after one evaluation has effectively zero probability of correctly identifying the better program when σ is large relative to γ. The persistent memory converts the problem from "decide correctly once" to "accumulate evidence until confident," which is fundamentally more robust. Theorem 2 further shows that maintaining and improving upon the historical best program (POLCA's approach) achieves O(B/γδ₀) convergence, while sequential updating (DSPy-style) requires exponential time O(1/δ₀^{B/γ}) in the worst case. This is a qualitative difference in scaling, not a constant-factor improvement.

Innovation 3: Semantic Diversity via ε-Net Provides a Principled Solution to the Redundancy-Accuracy Tradeoff

A widely observed but poorly addressed problem in generative optimization is semantic redundancy: LLM optimizers, when given similar contexts (overlapping minibatches, same high-performing seeds), tend to propose many programs that are semantically near-identical—different phrasings of the same instruction, minor code variations, or structurally equivalent approaches. This is not a failure of the optimizer per se; it is a consequence of the optimizer's tendency to make local, incremental improvements rather than radical redesigns, combined with the low variance in input context across iterations. Prior work has attempted to address this through heuristic filtering: AlphaCode (Li et al., 2022) clusters programs by execution behavior, ShinkaEvolve (Lange et al., 2025a) uses embedding similarity with an LLM-based novelty judge, and Kim et al. (2025) collapses redundant reasoning states via embedding clustering. But as the paper notes, these approaches "rely on multiple heuristic hyper-parameters without clear implications" (Section 6)—they work empirically but lack a theoretical connection between the filtering criterion and the underlying optimization objective.

POLCA's ε-Net mechanism provides this missing connection. The conceptual move is to frame filtering as discretization of the parameter space at resolution ε, where ε directly controls a coverage-cost tradeoff with formal guarantees. Under mild assumptions about the embedding function (that programs with small embedding distance have similar expected rewards), the ε-Net ensures that the number of distinct programs in memory is bounded by N_ε (the covering number of the embedding space), and that the approximation error from treating programs within distance ε as identical is controlled by ε times the Lipschitz constant of the reward function. This transforms the filtering problem from "choose arbitrary thresholds for similarity, novelty, and clustering" to "choose ε to trade off between final performance (how finely you can distinguish programs) and sample complexity (how many distinct programs you must evaluate)."

The theoretical significance is that this is not merely a heuristic that happens to work—it is necessary for convergence. In the analysis of Section 4, Theorem 1's sample complexity bound contains a term O(σ²N_ε log(n) / γ²) that depends on N_ε, the maximum number of programs in memory. Without the ε-Net, N_ε would be replaced by the total number of distinct programs generated, which grows with n, potentially unboundedly—the algorithm would need to evaluate every proposed program enough times to estimate its reward, leading to sample complexity that scales with the number of iterations rather than with the intrinsic complexity of the parameter space. The ε-Net converts a worst-case linear dependence on n into a constant N_ε, making the algorithm scalable in principle.

The practical significance is demonstrated in the ablation study (Figure 3a): adding the ε-Net to vanilla POLCA significantly improves performance, particularly under fixed metric-call budgets, because the evaluation budget is concentrated on genuinely distinct candidates rather than spread across near-duplicates. The ε sensitivity analysis (Figures 3b, 3c) further shows that POLCA's performance is not brittle to the exact ε value within a reasonable range, making it practical to deploy without precise tuning. The failure of regression-based alternatives (Section 5.4, Figure 3d) reinforces why this matters: even an ensemble of regressors trained on embeddings cannot reliably predict program performance well enough to replace the simple empirical mean + ε-Net combination, suggesting that the embedding signal, while sufficient for coarse similarity judgments, does not capture enough reward-relevant information for fine-grained prediction.

Innovation 4: Global Context Summarization as Meta-Learning Across the Entire Optimization History

A less obvious but equally important conceptual contribution is the paper's diagnosis of an information bottleneck in how existing generative optimizers use feedback. In DSPy-style sequential refinement, the optimizer sees only the most recent (program, feedback) pair—a single data point. In population-based methods like OpenEvolve or GEPA, the optimizer may see multiple programs, but typically only from the current generation or a small elite subset. The paper identifies that this local, recent-only information is fundamentally insufficient when evaluations are stochastic: the optimizer cannot distinguish between "this modification failed because it's a bad idea" and "this modification failed because the evaluation happened to be noisy this time," because it lacks the statistical context of seeing the same program succeed elsewhere or seeing similar modifications succeed across different seeds.

The Summarizer component addresses this by compressing the entire optimization history into a concise global context c_history that captures patterns across many programs, many minibatches, and many iterations. This is not a simple summary of "what worked"—the contrastive design (showing paired success/failure trajectories for each program) forces the Summarizer to identify discriminative patterns: what structural features distinguish programs that consistently succeed from those that consistently fail, rather than what features happen to be present in the current top candidates.

This is conceptually analogous to momentum in gradient-based optimization: local gradient steps (individual minibatch feedback) are noisy and may point in unproductive directions, but an exponential moving average of past gradients (global historical patterns) stabilizes the direction and filters out noise. The paper makes this analogy explicit (Section 3), and the ablation study (Figure 3a) confirms its practical importance: adding the Summarizer to vanilla POLCA provides a substantial performance boost, particularly in later iterations when local feedback alone would cause the optimizer to oscillate or plateau.

The significance of this innovation extends beyond the specific Summarizer implementation. It establishes that generative optimization requires meta-learning over the optimization trajectory, not just reactive improvement from the most recent feedback. Prior work that used history summarization (Zhang et al., 2025b) did so primarily for context compression, not as a mechanism for learning optimization dynamics. The paper reframes it as an essential component for stochastic robustness, arguing that without it, the optimizer cannot accumulate enough statistical signal to propose genuinely better programs rather than just different ones.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper evaluates on four benchmarks spanning diverse domains and stochasticity sources: (1) τ-bench (Yao et al., 2024)—a multi-turn agent benchmark for tool-use and user interaction in the retail domain, using the first 10 tasks for training and the remaining 145 (for generalization testing in Table 1) or 105 (for the held-out test in Figure 2a) tasks for evaluation; (2) HotpotQA (Yang et al., 2018)—a multi-hop question answering dataset, using the first 100 examples from the distractor validation split; (3) VeriBench (Miranda et al., 2025)—a formal verification benchmark for translating Python programs into Lean 4 code, using either the easy_set (41 tasks) for the 3-step evaluation or all 140 tasks for compilation-only evaluation; and (4) KernelBench (Ouyang et al., 2025)—a CUDA kernel optimization benchmark, using 16 matrix multiplication tasks from level 1. These benchmarks are chosen to cover stochasticity arising from minibatch sampling and program execution (τ-bench, HotpotQA), evaluator noise (VeriBench 3-step), and purely deterministic settings (VeriBench compilation, KernelBench), providing a comprehensive stress test for POLCA's robustness claims.

• Base model(s). The paper uses different backbone LLMs per benchmark: Gemini 2.0 Flash for τ-bench (both agent and optimizer), Gemini 2.5 Flash Lite for HotpotQA (task execution and meta-optimization), Claude 3.5 Sonnet for VeriBench (both code generation and LLM judge), and Claude 3.7 Sonnet for KernelBench (kernel generation). Embedding models are Gemini text-embedding-004 (τ-bench, VeriBench) and Gemini embedding-001 (HotpotQA, KernelBench). These choices are described as "representative of the capabilities of many contemporary LLMs" (Section 5 intro), though no systematic comparison across model families is performed—each benchmark uses a single model configuration, and the results therefore reflect the interaction between POLCA and specific model capabilities rather than model-agnostic optimization behavior.

• Metrics. The primary metric varies by benchmark to match the domain's evaluation standard: (1) τ-bench: pass@1 measured as the fraction of task trials where the agent successfully resolves the user's request, with test scores computed by running 10 trials per task and averaging the pass rate across all tasks and trials (providing a nearly deterministic estimate for external testing); (2) HotpotQA: answer accuracy determined by case-insensitive exact match or substring containment after stripping trailing punctuation, with test scores computed by evaluating each candidate prompt on all 100 tasks with 5 independent repetitions; (3) VeriBench (3-step evaluation): a composite reward r = 0.3 · 1_Compilation + 0.3 · 1_Unit_Tests + 0.4 · r_LLM, where the LLM judge score is normalized to [0,1]; (4) VeriBench (compilation): binary compilation pass rate (1 if compiles, 0 otherwise); and (5) KernelBench: the fast_p score = (1/N) Σ 1(correct_i ∧ speedup_i > p), measuring the fraction of tasks with a correct kernel exceeding speedup threshold p, with p=1.0 or p=0.5 (speedup is computed relative to the PyTorch baseline, with each evaluation result averaged over five repeated executions on an L40S GPU). For all search algorithm comparisons, the paper reports the highest score attained at each step (Figure 2, solid curves) with shaded standard error regions over multiple independent runs, though the number of seeds varies substantially: 6 seeds for τ-bench, 3 for HotpotQA and VeriBench, and only 1 for KernelBench, making the KernelBench comparison essentially a single-run anecdote rather than a statistically reliable comparison.

• Baselines. Three established algorithms are compared: (1) DSPy (Khattab et al., 2023)—a sequential revision search algorithm that uses a dspy.ChainOfThought module to take the current parameter with its score and feedback and propose a new parameter at each step, representing the iterative refinement paradigm; (2) GEPA (Agrawal et al., 2025)—a reflective prompt optimization algorithm maintaining a Pareto frontier of non-dominated solutions across training instances, evaluated against POLCA with two selection variants: "GEPA (Most Frequent)" selecting the candidate appearing most often in the frontier, and "GEPA (Sample by Freq)" performing weighted selection based on frontier frequency; and (3) OpenEvolve (Sharma, 2025)—an open-source implementation of AlphaEvolve (Novikov et al., 2025) using MAP-Elites and island-based evolution with configurable island count, migration intervals, and top/diverse program selection. These baselines span the three main paradigms in generative optimization: sequential refinement (DSPy), Pareto-based population management (GEPA), and evolutionary search (OpenEvolve). Notably absent is any comparison to beam search or MCTS-based methods (Pryzant et al., 2023; Wang et al., 2023), which would provide coverage of the tree search paradigm—the paper's Section C describes how POLCA can instantiate beam search but never empirically compares against it as an external baseline.

• Generation budget / compute accounting. The paper defines two distinct budget metrics to capture different dimensions of computational cost: (1) number of metric calls—the total count of individual program-task evaluations performed, representing actual computation used (e.g., evaluating one agent on one task is one metric call), with maximum budgets of ~1200 for τ-bench, ~2500 for HotpotQA, 50 per task for VeriBench, and ~50 for KernelBench; and (2) evaluation steps—a unit where all constituent metric calls within that step are parallelized, measuring the number of sequential operations as a surrogate for wall-clock time. The main paper's figures (Figures 2, 4–7) use evaluation steps on the x-axis for the primary comparison, with Appendix D.3 providing the complementary metric-calls analysis. This dual accounting is necessary because POLCA's batch-oriented design (parallel evaluation of multiple programs on multiple tasks) achieves lower wall-clock time than sequential methods at the same total computation, but may appear less efficient in the early stages when measured by total metric calls alone. For fairness, all algorithms are constrained to the same maximum parallel evaluation capacity (10 for τ-bench, 5 for VeriBench). Token usage estimates are provided in Appendix D.8 for a single run of POLCA across benchmarks, totaling ~31M tokens for τ-bench, ~6.5M for HotpotQA, ~634K per task for VeriBench, and ~571K per task for KernelBench, though these figures are reported only for POLCA with no baseline token comparisons.

• Cross-validation / statistical protocol. Statistical reliability varies substantially across experiments: τ-bench uses 6 independent random seeds with mean and standard error reported; HotpotQA uses 3 seeds; VeriBench (3-step) uses 3 seeds with per-task optimization repeated across all 41 tasks independently; VeriBench (compilation) uses 3 seeds across all 140 tasks; and KernelBench uses only 1 seed. The paper does not employ cross-validation in the traditional sense—there is no train/validation/test split for hyperparameter selection. Instead, for τ-bench, the first 10 tasks serve as a de facto training set with the remaining 145 held out for generalization testing (Table 1). For all other benchmarks, the optimization is performed per-task (VeriBench, KernelBench) or on the full available set (HotpotQA), and the reported scores are the optimization trajectory curves showing the best-so-far performance at each step. The consistent reporting of standard error where multiple seeds are available is appropriate, but the single-seed KernelBench result provides no statistical evidence whatsoever—it is a single trial that could reflect random initialization luck rather than systematic superiority. The paper acknowledges this limitation only implicitly through the seed count reporting.

Main Quantitative Results

Stochasticity from Program Execution and Minibatch Sampling (τ-bench and HotpotQA)

τ-bench agent prompt optimization. Figure 2(a) and Table 1 present the central evidence for POLCA's robustness to combined minibatch and program-execution stochasticity. On the τ-bench retail domain with 10 training tasks and 145 held-out tasks, POLCA achieves a test pass@1 of 0.575 on the first 10 tasks and 0.425 on the remaining 105 tasks, for an overall pass@1 of 0.439 across all 115 tasks (Table 1). This represents a 13% relative improvement over the base prompt's pass@1 of 0.389 and outperforms the strongest baseline (GEPA at 0.429 overall) by approximately 2.3%.

The evaluation-step efficiency curves in Figure 2(a) reveal the dynamics behind these numbers. The base prompt (not shown directly in the curve, but implied as the starting point near 0.35) provides the floor. GEPA (Most Frequent) climbs to approximately 0.60 by step 200, while GEPA (Sample by Freq) traces a nearly identical trajectory, both stabilizing around step 100–150. OpenEvolve shows the weakest performance among the baselines, reaching only approximately 0.42 at step 200 and demonstrating almost no improvement over the base prompt—evidence that its single-evaluation-per-candidate approach catastrophically fails under stochasticity. POLCA, in contrast, reaches approximately 0.65 by step 250 and continues to improve without the clear plateau visible in the baselines, suggesting that the persistent memory continues to refine estimates and discover better candidates even in late iterations.

The broader generalization results in Table 1 provide critical context. While all methods show a meaningful gap between training-task performance (first 10 tasks) and held-out-task performance (last 105 tasks)—indicating some degree of overfitting to the small training set—POLCA's gap (0.575 → 0.425, a drop of 0.150) is proportionally smaller than GEPA's (0.557 → 0.417, a drop of 0.140) when measured in absolute terms, though the relative degradation is comparable. This suggests that POLCA's advantage is not merely a consequence of better memorization of the training tasks but reflects genuinely better prompt optimization that transfers to unseen tasks.

The specific mechanism behind POLCA's advantage is illuminated by the contrasting behavior of OpenEvolve: OpenEvolve generates many candidate prompts (through island-based evolution) but evaluates each only once on the 10 training tasks. With binary 0/1 rewards per task and only 10 tasks, the variance in the pass rate estimate is enormous—a truly good prompt might score 4/10 in one evaluation and 8/10 in another due to the agent's internal LLM stochasticity and the specific task draw. OpenEvolve's selection mechanism treats the single noisy score as ground truth, discarding candidates that were merely unlucky. POLCA's continuous re-evaluation of promising candidates across multiple minibatches averages out this noise, enabling it to correctly identify good prompts that OpenEvolve would have rejected.

HotpotQA prompt optimization. Figure 2(b) demonstrates POLCA's superiority on a different stochastic domain—multi-hop QA with minibatch sampling. With a budget of approximately 50 evaluation steps, POLCA reaches a test accuracy of nearly 1.00 (exact values are not numerically reported in the text, but the curve asymptotes near the ceiling), while GEPA and OpenEvolve plateau at approximately 0.85–0.90. The curves in Figure 2(b) reveal an interesting pattern: all three methods start from approximately the same point (around step 0, accuracy ~0.75–0.80), but POLCA improves more rapidly and continues to climb while the baselines flatten. GEPA shows a particularly characteristic trajectory—rapid initial improvement followed by early plateau around step 10–15, after which additional evaluations yield minimal gains. This is consistent with GEPA's mechanism: once the Pareto frontier stabilizes around a set of mutually non-dominated prompts, further exploration is driven only by reflection on frontier members, but without re-evaluation of historical candidates, the frontier cannot correct for initial noisy scores that placed mediocre prompts in non-dominated positions.

The Appendix D.3 analysis using alternative budget metrics (Figures 5) tells a more nuanced story. When measured by total number of metric calls (left panel of Figure 5), POLCA's final performance remains superior but its early-stage efficiency is lower than GEPA—at 500 metric calls, GEPA reaches approximately 0.90 while POLCA is at approximately 0.85. This gap closes by 2500 metric calls. The reason is structural: POLCA's batch-oriented design means that early iterations spend evaluation budget on multiple seed programs and multiple new proposals simultaneously, while sequential methods concentrate budget on one improvement chain. The efficiency crossover—where POLCA's investment in broader exploration pays off—occurs between 500 and 1500 metric calls, after which POLCA's better-informed proposals and more accurate candidate scoring drive continued improvement that the baselines cannot match.

Stochasticity from the Evaluator (VeriBench 3-Step Evaluation)

VeriBench with LLM-judge stochasticity. Figure 2(c) presents the optimization curves for the 3-step VeriBench evaluation, where the LLM judge introduces stochasticity into an otherwise deterministic program (the Lean 4 translation). The results show POLCA achieving approximately 0.95 by step 50, compared to DSPy at approximately 0.65, GEPA at approximately 0.40–0.50, and OpenEvolve at approximately 0.45. The performance ordering (POLCA ≫ DSPy ≫ OpenEvolve ≈ GEPA) is different from τ-bench, reflecting the different nature of stochasticity in this domain.

The striking dominance of DSPy over GEPA and OpenEvolve is instructive. In this single-task-per-optimization-run setting, GEPA's Pareto frontier collapses—as the paper notes in Section 5.2, "the Pareto frontier merely represents the current best program," causing GEPA to degenerate into always selecting the single best performer. But because the LLM judge's score is stochastic (a single program might receive scores of 20/30, 25/30, or 15/30 on different evaluations), GEPA's "single best" selection is unreliable—it may promote a program that was merely lucky and discard one that was unlucky, and subsequent proposals inherit from this potentially mediocre foundation. DSPy, despite being sequential, benefits from the fact that its single-improvement-chain design allows it to iterate quickly, and the rich feedback (compilation errors, unit test results, LLM judge critiques) provides more informative guidance even from noisy scores than the population-level statistics available to GEPA.

POLCA's dramatic advantage (~0.95 vs. 0.65 for DSPy) comes from its ability to accumulate multiple evaluations of the same program across iterations. A Lean 4 program that compiles and passes unit tests but receives a low LLM-judge score on one evaluation may be re-evaluated in subsequent iterations (when it is selected as a seed), receiving a higher judge score and rising in the ranking. DSPy, which evaluates each program once and moves on, cannot recover from an unlucky judge score—the program is used as a stepping stone for the next proposal, but its true quality is never revisited. This is particularly important in the VeriBench setting because the LLM judge score, while noisy, contains genuine signal (the judge is comparing the translated program against a ground-truth implementation), and multiple evaluations reveal the consistent quality that a single evaluation might obscure.

The Appendix D.3 analysis (Figure 6) adds important context about the proposal-efficiency tradeoff. When measured by total metric calls (left panel), POLCA still outperforms DSPy (approximately 0.95 vs. 0.65 at 80 metric calls), but the advantage is less dramatic than in evaluation steps because POLCA uses more total evaluations per step. When measured by proposal steps (middle panel), POLCA's advantage is even larger because its parallel proposal generation achieves more improvement per sequential operation.

Deterministic Domains (VeriBench Compilation and KernelBench)

VeriBench compilation pass rate. Table 2 presents the compilation-only results across all 140 VeriBench tasks with a budget of 50 metric calls per task. POLCA achieves a 95.2% pass rate (133/140 tasks), compared to DSPy at 88.8%, OpenEvolve at 73.8%, and GEPA at 69.5%. This is a substantial margin—POLCA compiles approximately 22 more programs than GEPA under the same evaluation budget. The extended results in Appendix D.4 (Figure 8) show that this advantage is consistent across all budget metrics (evaluation steps, metric calls, proposal steps, proposals) and that POLCA's compilation rate climbs to near-ceiling (approx. 0.95) within 10–15 evaluation steps, while the baselines require 30–40 steps to approach their asymptotes.

The authors contextualize this result against prior work: Miranda et al. (2025) used the same model (Claude 3.5 Sonnet) with a sequential search of 5 retries on a subset of 113 tasks and achieved only a 59.3% pass rate (67/113). POLCA's 95.2% on all 140 tasks represents a dramatic improvement, though the comparison is not entirely apples-to-apples (different task subsets, different retry budgets). The key mechanism behind POLCA's advantage in this deterministic setting is identified in Section 5.3: "the use of parallel starting points exploits the stochasticity of the optimizer more effectively than sequential baselines." Even though the evaluation is deterministic (compilation succeeds or fails), the LLM optimizer itself is stochastic—the same prompt can produce different code proposals. By generating multiple proposals from multiple seed programs in parallel (5 seeds × 1 proposal each = 5 new candidates per iteration), POLCA explores a broader set of improvement directions than DSPy's single sequential chain or GEPA's collapsed-frontier single-seed approach. The global context summary further helps by distilling patterns from failed compilations across different code structures, enabling the optimizer to avoid known failure modes even when proposing from different seeds.

KernelBench CUDA kernel optimization. Figure 2(d) presents the fast_1.0 score (fraction of 16 tasks achieving correct kernels with >1× speedup over PyTorch) using Claude 3.7 Sonnet. POLCA reaches approximately 0.75 by step 17.5, compared to GEPA at approximately 0.55, OpenEvolve at approximately 0.30, and DSPy at approximately 0.30. The Appendix D.5 analysis with fast_0.5 (Figure 9) shows a similar ordering with POLCA at approximately 0.90 vs. GEPA at 0.60 vs. DSPy/OpenEvolve at 0.45–0.50.

Several aspects of these results warrant careful interpretation. First, the single-seed reporting means these numbers are single-run observations—there is no estimate of variance, and a different random initialization might produce substantially different outcomes. The paper treats this single run as representative, but without replication, the relative ordering could be an artifact of initialization luck. Second, the evaluation budget for KernelBench is small (approximately 50 metric calls total across 16 tasks), meaning each program receives very few evaluations. In a deterministic domain, this is less problematic (a correct kernel with sufficient speedup is deterministically good), but the small number of proposals limits how much search can be performed.

The performance of GEPA on KernelBench is notably stronger than on the stochastic benchmarks—it achieves 0.55 vs. POLCA's 0.75, a gap of 0.20, compared to its near-zero improvement on τ-bench. This supports the paper's central claim that GEPA's weaknesses are specifically tied to stochasticity: when evaluations are deterministic (kernel correctness and speedup are objective, repeatable measurements), GEPA's Pareto-frontier mechanism functions as designed. POLCA's remaining advantage in this setting comes from the broader exploration enabled by parallel proposals and the global context summarization, not from the memory-based noise-averaging mechanism that is its primary contribution for stochastic domains.

What the KernelBench result does NOT demonstrate. It is important to note what this experiment does not show. The paper explicitly chose "16 matrix multiplication tasks from KernelBench (level 1)" described as "appear simple but remain challenging" because "these tasks are already highly optimized in PyTorch, making it difficult to achieve further speedups." This is a deliberately selected subset—not the full KernelBench benchmark—chosen for its difficulty characteristics. The results therefore demonstrate POLCA's effectiveness on a specific class of hard optimization problems but do not establish general superiority on CUDA kernel optimization across the full range of difficulty levels in KernelBench. A more comprehensive evaluation would include all level 1 tasks or a random sample, rather than a curated set.

Ablation Studies and Robustness Checks

Ablation on ε-Net and Summarizer components. Figure 3(a) decomposes POLCA's performance into the contributions of its two novel components. Starting from "vanilla POLCA" (priority queue memory with empirical mean priority, no ε-Net, no Summarizer) as the baseline, adding the ε-Net alone ("vanilla POLCA + ε-Net") improves the score from approximately 0.52 to approximately 0.58 at 2000 metric calls—a gain that the paper attributes to the ε-Net's ability to concentrate evaluation budget on semantically distinct candidates rather than near-duplicates. Adding the Summarizer alone ("vanilla POLCA + Summarizer") improves performance from 0.52 to approximately 0.60, though the trajectory shows a more interesting pattern: the Summarizer variant initially underperforms vanilla POLCA (steps 0–500 metric calls) before pulling ahead, consistent with the Summarizer requiring sufficient historical data before its global context becomes informative rather than noisy. The full POLCA ("vanilla POLCA + ε-Net + Summarizer") reaches approximately 0.63–0.64, demonstrating that the two components are complementary—the ε-Net ensures the Summarizer sees a diverse, representative set of programs, while the Summarizer ensures the optimizer makes better use of the concentrated evaluation budget that the ε-Net enables. Figure 10 in Appendix D.6 shows these same trends under alternative metrics (evaluation steps, proposal steps, number of proposals), with the qualitative pattern preserved across all views.

The key takeaway from this ablation is that neither component alone captures POLCA's full advantage—their interaction is what drives the substantial gap over baselines. The ε-Net without the Summarizer would filter effectively but leave the optimizer with only local information; the Summarizer without the ε-Net would process an unwieldy population of near-duplicates and potentially overfit its guidance to minor variations rather than genuine structural differences. The complementarity is not just additive but synergistic: the ε-Net gives the Summarizer a higher-quality input, and the Summarizer gives the optimizer better directions, which in turn produce proposals that the ε-Net can more effectively filter for genuine novelty.

Ablation on ε sensitivity. Figures 3(b) and 3(c) sweep the ε parameter across a range of values on τ-bench and VeriBench respectively. On τ-bench (Figure 3b), ε values of 0.0, 0.05, 0.1, 0.15, 0.2, 0.25, and 0.3 are tested. The results confirm the paper's theoretical claims about the ε tradeoff: ε = 0.0 (no filtering) produces the worst performance at all metric-call levels, with the curve stabilizing around 0.42—dramatically worse than any ε > 0 condition, which all cluster between 0.50 and 0.55. This is strong evidence for the necessity of filtering. Among the positive ε values, performance is relatively insensitive in the range 0.1–0.25, with ε = 0.15 appearing near-optimal. At the extreme, ε = 0.3 shows a slight degradation in asymptotic performance (reaching approximately 0.53 vs. 0.55 for ε = 0.15), consistent with the paper's claim that "larger ε values accept more diverse programs into memory, thereby encouraging exploration," but that coarser discretization eventually introduces approximation error that limits final performance.

On VeriBench (Figure 3c), ε values of 0.0, 0.02, 0.05, 0.07, and 0.1 are tested. The pattern is consistent: ε = 0.0 (no filtering) is worst, reaching only approximately 0.4 at 100 metric calls compared to approximately 0.9 for the best ε settings. The optimal ε range appears narrower for VeriBench, with ε = 0.02 performing best and larger values (0.07, 0.1) showing clear degradation—the asymptotic score at ε = 0.1 reaches approximately 0.7 vs. 0.9+ for ε = 0.02–0.05. This domain-specific optimal range reflects the different semantics of the embedding space: in code translation (VeriBench), small textual changes can produce large semantic differences (changing a function signature changes compilation behavior), so a fine ε is needed to preserve genuinely distinct programs; in prompt optimization (τ-bench), the embedding may be coarser-grained, so a larger ε still captures meaningful diversity.

The paper's "within a certain range" qualifier about ε robustness should therefore be understood as domain-conditional—the range of insensitivity is wider for τ-bench (0.1–0.25, a span of 0.15) than for VeriBench (0.02–0.05, a span of 0.03). Practitioners deploying POLCA on a new domain would need to tune ε, and the appropriate range cannot be inferred from the benchmarks studied here without additional investigation.

Why not use regression? Figure 3(d) tests whether a learned reward model (ensemble of logistic regressors on embeddings) could replace POLCA's empirical mean scoring. At 30%, 60%, and 100% data usage, four selection criteria—empirical mean, ensemble highest prediction, ensemble mean prediction, and ensemble lowest prediction—are compared for selecting the best program from the queue. Across all data percentages, the empirical mean consistently outperforms all three regression-based criteria. At 100% data, empirical mean achieves approximately 0.67 vs. 0.52 for mean prediction and approximately 0.35 for lowest prediction.

This is a negative result with significant implications. It demonstrates that even a simple ensemble model cannot learn a reliable mapping from program embeddings to expected rewards in the τ-bench domain, despite the embeddings being sufficient for the coarse similarity judgments used by the ε-Net. The paper speculates that "predicting a program's score accurately is difficult without explicit problem-instance information"—the regression model sees only the program embedding, not the specific tasks it was evaluated on, and therefore cannot distinguish between "this program is genuinely good" and "this program happened to be evaluated on easy tasks." The empirical mean, by explicitly averaging over the actual task instances seen, naturally conditions on the evaluation history in a way that a task-agnostic regression cannot.

This finding validates POLCA's design choice of persisting raw evaluation data (the (θ, x, y, r, f) tuples) rather than attempting to learn a parametric score function from embeddings. It also explains why GEPA's approach (which relies on scoring candidates based on their performance on a fixed validation set, effectively a form of parametric evaluation) underperforms—the fixed validation set does not provide sufficient statistical power to distinguish programs when individual task evaluations are noisy.

Critical Assessment

The central claim—that POLCA's memory + ε-Net architecture provides robustness to stochasticity that existing methods lack—is supported, but with important boundary conditions that the experiments only partially illuminate.

The strongest evidence comes from the τ-bench results (Figure 2a, Table 1), where the stochasticity is most severe (binary rewards, small minibatches, agent stochasticity, and task diversity) and POLCA's advantage is most pronounced. The side-by-side comparison with OpenEvolve—which uses the same optimizer but a different memory architecture—is particularly compelling because it isolates the memory mechanism as the source of improvement: both methods generate proposals from the same LLM, but POLCA's persistent re-evaluation correctly identifies good candidates that OpenEvolve's single-evaluation approach rejects. The HotpotQA results (Figure 2b) provide convergent evidence in a different domain with different types of stochasticity. The VeriBench 3-step results (Figure 2c) demonstrate that POLCA's mechanisms generalize to evaluator-noise-dominated stochasticity rather than just minibatch-noise-dominated stochasticity.

However, several experimental design choices weaken the generality of these conclusions.

First, the baseline comparison set is incomplete. The paper omits comparisons against beam search and MCTS-based generative optimization methods, which are arguably the most natural competitors for search-in-parameter-space approaches. Section C explicitly describes how POLCA can instantiate beam search, but never runs it as an external baseline. This is a meaningful omission because beam search with re-evaluation (where beams are scored on multiple tasks to reduce variance) would be a natural stochasticity-aware extension of standard beam search—essentially a shallower version of POLCA's persistent memory. Without this comparison, it is unclear whether POLCA's advantage comes from the ε-Net filtering specifically or from any mechanism that accumulates evidence over multiple evaluations.

Second, the single-seed KernelBench result is not a valid comparison. A single run with no replication provides zero statistical evidence about relative performance—the observed ordering (POLCA > GEPA > OpenEvolve ≈ DSPy) could reflect initialization luck, and a different random seed might produce any permutation of these methods. The paper's decision to include this as a main result without replication is methodologically weak. The VeriBench compilation results (Table 2, with 3 seeds and error bars) partially compensate but cannot validate the KernelBench-specific claims.

Third, the training/optimization computational cost is not accounted for in the comparisons. POLCA uses an additional LLM (the Summarizer) that is called at each iteration, consuming tokens that are not charged to the evaluation budget. Appendix D.8 reports token usage for POLCA alone but provides no comparable numbers for baselines. If POLCA consumes substantially more optimizer-side compute (LLM calls for summarization) than baselines, the evaluation-budget-matched comparison is misleading—a fairer comparison would match total FLOPs or total API cost, not just evaluation calls. The paper does not discuss this asymmetry.

Fourth, the difficulty of the chosen benchmarks may be systematically biased toward POLCA's strengths. The τ-bench training set of 10 tasks is exceptionally small—optimizing on 10 tasks for generalization to 145 tasks is an extreme few-shot regime where any method's ability to avoid overfitting to spurious patterns is critical. POLCA's explicit diversity mechanism (ε-Net) and global context summarization are well-suited to this regime. On benchmarks with larger training sets (hundreds of tasks), the advantage of diversity preservation may be less pronounced because random sampling of seed programs naturally provides more diversity. The paper does not test this scaling hypothesis by varying the training set size.

Fifth, the ε sensitivity analysis, while informative, reveals that the optimal ε is domain-dependent and must be tuned. The conclusion that "POLCA's performance is not very sensitive to the exact ε value within a certain range" (Section 5.4) is true but conceals the fact that the range itself varies dramatically across domains (0.1–0.25 for τ-bench vs. 0.02–0.05 for VeriBench). A practitioner deploying POLCA on a new domain has no guidance for choosing ε, and the ablation shows that choosing wrong (ε = 0.3 on VeriBench) causes performance to collapse below baselines. This is a practical limitation that the paper does not adequately address.

The regression failure experiment (Figure 3d) is important but incompletely analyzed. The result that an ensemble of logistic regressors on embeddings cannot predict program performance as well as the empirical mean is striking, but the paper does not investigate why. Is it because the embedding space is insufficiently expressive (i.e., programs with very different performance have similar embeddings)? Is it because the training data for the regression is too small? Is it because the binary reward structure in τ-bench makes regression especially difficult? Without diagnostic experiments, the negative result is suggestive but not explanatory, and it is unclear whether the same failure would occur in domains with richer reward signals (continuous scores, more tasks).

The claim that POLCA "consistently outperforms state-of-the-art algorithms in both deterministic and stochastic problems" (Abstract) overstates the evidence in the deterministic case. The KernelBench result is single-seed and on a curated subset of tasks. The VeriBench compilation result is stronger (3 seeds, 140 tasks, substantial margin), but VeriBench compilation is a somewhat unusual deterministic domain—it's a code generation task where the optimizer must propose a complete, compilable program, and the "optimization" is essentially search over program text with binary feedback. This is quite different from, say, optimizing continuous hyperparameters or computational graph structures, where deterministic evaluations are more common. The paper has not demonstrated POLCA's superiority over baselines on a broad class of deterministic optimization problems.

Finally, the theoretical results (Theorem 1, Theorem 2) are validated only in the narrow sense that POLCA works empirically. The paper does not test whether the predicted scaling behavior—the dependence of convergence on the optimizer's improvement probability δ₀, the stochasticity parameter σ², and the ε-Net covering number N_ε—holds in practice. Such tests would require controlled experiments varying σ² (by adding known noise to evaluations) or δ₀ (by degrading the optimizer), which are not performed. The theory thus stands as a plausibility argument rather than a quantitatively validated model of POLCA's behavior.

6. Limitations and Trade-offs

The Difficulty Estimation / Difficulty Awareness Problem Is Not Addressed

The assumption or constraint. POLCA's architecture assumes that the optimizer can propose genuinely better programs given accumulated feedback, but it provides no mechanism to identify when optimization has reached a ceiling—when the remaining programs in memory are all within the [B−γ, B] near-optimal band that the optimizer cannot be guaranteed to improve further (Assumption 1, Section 4). Unlike the referenced paper on compute-optimal test-time scaling, which builds difficulty estimation directly into the allocation policy (using PRM score distributions to bin prompts into quintiles and adaptively select strategies), POLCA treats all optimization problems uniformly. There is no difficulty estimator, no adaptive budget allocation, and no mechanism to stop spending compute on problems where the base model's capability is insufficient.

The paper indirectly acknowledges this in the experimental results: on the hardest τ-bench tasks, all methods perform near the base rate. Table 1 shows that POLCA achieves 0.439 overall pass@1 vs. the base prompt's 0.389, an improvement of only 0.050 in absolute terms across all 115 tasks. On the last 105 (held-out) tasks specifically, POLCA achieves 0.425 vs. the base 0.392, an improvement of 0.033—barely above the noise floor. On VeriBench, even with POLCA's 95.2% compilation pass rate, there remain 7 out of 140 tasks (5%) that fail compilation despite the full 50-call budget. The paper never analyzes which tasks these are, whether they share characteristics that make them fundamentally harder for the base model, or whether additional budget would help or be wasted.

The consequence. In a deployment setting, POLCA has no principled stopping criterion and no mechanism to avoid wasting computation on unsolvable problems. The algorithm continues iterating until the evaluation budget is exhausted, regardless of whether progress has plateaued. For a practitioner with a fixed total budget across many optimization tasks, this means POLCA will spend the same compute on problems where the base model has near-zero pass@1 (and where no amount of test-time optimization can help, as the paper's own theoretical analysis implies through the γ-strict improvement assumption) as on problems where optimization can produce substantial gains. This is economically inefficient: compute that could be reallocated from hopeless problems to promising ones is instead burned uniformly.

The problem is compounded by the lack of difficulty estimation cost in the evaluation budget. If a practitioner wanted to add difficulty estimation to POLCA—for example, by first running a small pilot optimization to gauge whether the problem is in a regime where improvements are possible—that pilot cost would come out of the same evaluation budget, reducing the compute available for actual optimization on the problems that can benefit.

What evidence exists in the paper. The evidence is indirect but consistent across benchmarks. Table 1 shows a training-to-test generalization gap for all methods, with POLCA's training performance (0.575 on first 10 tasks) substantially exceeding its held-out performance (0.425 on last 105 tasks). This gap exists not because POLCA overfits (in fact, POLCA generalizes better than baselines), but because the 10 training tasks are a small, potentially non-representative sample, and many of the 105 held-out tasks may be structurally harder or require capabilities the base Gemini 2.0 Flash model lacks. The paper never stratifies results by task difficulty or analyzes failure cases to determine whether the remaining errors are due to insufficient optimization or fundamental capability limitations. Similarly, the VeriBench compilation results (Table 2) show that 7 tasks remain uncompiled despite 50 metric calls, but there is no analysis of what distinguishes these 7 from the 133 that compiled. Section 5.3 notes that "the hardest questions (difficulty bin 5)" in the reference paper "show near-zero improvement regardless of compute budget," but POLCA's experiments include no analogous difficulty analysis.

Mitigation status. Not addressed. The paper makes no attempt to incorporate difficulty estimation, adaptive budget allocation, or early stopping. The theoretical analysis (Section 4) proves convergence to near-optimal candidates under Assumption 1 but does not bound the number of iterations until plateau, meaning the algorithm may spend many iterations making no progress before budget exhaustion. Section 7 mentions this only implicitly through the assumption's scope: the optimizer is guaranteed to improve programs with reward in [0, B−γ] but not programs in (B−γ, B], yet no mechanism is provided to detect which regime the current best program occupies.

---

The Summarizer Adds Unaccounted Computational Overhead

The assumption or constraint. POLCA invokes an external LLM (the Summarizer) at every iteration to process the priority queue Q and produce the global context c_history. This LLM call consumes input and output tokens that are not included in the evaluation budget on which all comparisons with baselines are based. The paper reports token usage for POLCA in Appendix D.8—for τ-bench, a single 100-iteration run consumes ~31M total tokens (~30.8M input, ~380K output)—but "this estimation is limited to the tokens utilized by the search pipeline and excludes LLM calls invoked within the optimizing programs themselves" (Section D.8). No comparable token numbers are reported for GEPA, OpenEvolve, or DSPy.

The Summarizer's token consumption is not negligible. In a 100-iteration τ-bench run, the Summarizer is called 100 times, each time processing a contrastive sample of programs from Q (one success and one failure trajectory per program, with program parameters included). As Q grows (the ε-Net allows Q to grow up to N_ε programs), the Summarizer's context length grows, increasing token cost per call. At the limit, if N_ε = 100 distinct programs are in memory (a conservative estimate for a diverse prompt optimization run), each Summarizer call must process 100 programs × 2 trajectories each, plus the programs' parameter strings—this could easily reach tens of thousands of input tokens per Summarizer call.

The consequence. The evaluation-budget-matched comparisons (Figures 2, 4–7) are not cost-matched comparisons. A practitioner choosing between POLCA and a baseline must account for total API cost (or total FLOPs, or total wall-clock time including LLM calls), not just the number of program evaluations. If POLCA's Summarizer calls cost, say, 20% of the total token budget, then a 1000-metric-call POLCA run is actually more expensive than a 1000-metric-call GEPA run, and the fair comparison would give GEPA additional metric calls to match the total cost. The paper's reported efficiency advantages (e.g., POLCA reaching 0.65 at step 250 vs. GEPA at 0.60, Figure 2a) may partly reflect POLCA's larger total compute expenditure rather than superior algorithmic efficiency.

This problem is particularly acute for τ-bench and HotpotQA, where the evaluation itself is expensive (each metric call involves an LLM agent interacting with a simulated user for multiple turns, consuming LLM tokens) and the Summarizer overhead might be a small fraction of total cost. For VeriBench compilation, where evaluation is cheap (a compiler call that returns binary success/failure in milliseconds), the Summarizer's LLM calls could dominate the total cost, making the evaluation-budget-matched comparison severely misleading.

What evidence exists in the paper. Appendix D.8 provides token counts for single POLCA runs across all benchmarks but no baseline comparisons. The τ-bench 100-iteration run uses ~31M tokens; if the Summarizer accounts for, say, 20% of these (~6M tokens), and GEPA uses no Summarizer-equivalent component, then a fair comparison would need to account for this asymmetry. The paper does not break down token consumption by component (Summarizer vs. Optimizer vs. evaluation overhead), making it impossible to estimate the Summarizer's marginal cost from the reported numbers. The ablation study (Figure 3a) shows that removing the Summarizer degrades performance, confirming that the Summarizer contributes value, but it does not measure whether that value justifies its cost relative to simply giving a Summarizer-free algorithm more evaluation budget.

Mitigation status. Not addressed. The paper does not propose a cost-aware variant of POLCA, does not provide guidance on trading off Summarizer cost against evaluation budget, and does not compare methods under a total-cost-matching constraint. The limitation is implicitly acknowledged through the mere existence of Appendix D.8 (token reporting), but the implications for fair comparison are not discussed.

---

The ε Sensitivity Is Domain-Dependent and Discovering the Right ε Requires the Search Budget POLCA Is Meant to Save

The assumption or constraint. The ε parameter that controls the ε-Net filtering threshold is a critical hyperparameter with no principled, domain-agnostic method for setting it. The paper's ablation (Figures 3b, 3c) demonstrates that while POLCA is "not very sensitive to the exact ε value within a certain range" (Section 5.4), the range itself varies dramatically across domains: for τ-bench, the robust range is approximately ε ∈ [0.1, 0.25] (a span of 0.15 in embedding distance); for VeriBench, the robust range is approximately ε ∈ [0.02, 0.05] (a span of 0.03). Choosing ε outside the appropriate range causes severe performance degradation: ε = 0.3 on τ-bench (outside the robust range) degrades asymptotic performance by approximately 0.02–0.03; ε = 0.1 on VeriBench (far outside the robust range) causes performance to drop from ~0.95 to ~0.70—worse than DSPy.

The paper provides no guidance on how to choose ε for a new domain without running ablation experiments comparable in scale to the ones in the paper. The theoretical analysis (Section 4) bounds the number of distinct programs by N_ε (the ε-covering number of the parameter space under the embedding), but N_ε is not computable in practice—it depends on the geometry of the embedding space, which is a black-box property of the chosen embedding model. The relationship between ε and the Lipschitz constant of the reward function (which determines how much approximation error is incurred by treating ε-close programs as identical) is also domain-specific and unobservable without extensive evaluation.

The consequence. A practitioner deploying POLCA on a new domain—say, optimizing SQL queries, or tuning robot control policies, or generating hardware description language code—has no a priori way to choose ε. They must either: (a) guess, risking severe performance degradation if the guess is wrong; (b) run an ε-sweep ablation similar to Figure 3b/3c on their domain, consuming a substantial fraction of the total evaluation budget that was meant to be saved by using POLCA in the first place; or (c) transfer ε from the most similar benchmark in the paper (τ-bench for prompt optimization, VeriBench for code generation, etc.), with no guarantee that the embedding model's distance metric behaves similarly on their data.

The narrowness of the VeriBench robust range (0.02–0.05, a factor of 2.5× from minimum to maximum functional ε) is particularly concerning. If a practitioner guesses ε = 0.1 (reasonable-seeming for "coarse filtering"), performance collapses. If they guess ε = 0.01 (reasonable-seeming for "fine-grained filtering"), they are effectively running without filtering (ε = 0), which the ablation shows is the worst setting across all domains. The penalty for mis-specification is asymmetric: too large → moderate degradation; too small → catastrophic degradation (equivalent to no filtering, which the paper demonstrates is dramatically worse).

What evidence exists in the paper. Figures 3(b) and 3(c) provide the primary evidence for domain-dependent ε sensitivity. The τ-bench sweep (Figure 3b) shows that ε ∈ [0.1, 0.25] produces final scores of 0.50–0.55 at 500 metric calls, with a tight cluster; ε = 0.0 collapses to 0.42; ε = 0.3 degrades to ~0.53 asymptotically. The VeriBench sweep (Figure 3c) shows a much steeper sensitivity: ε = 0.02 reaches ~0.95 at 100 metric calls; ε = 0.05 reaches ~0.85; ε = 0.07 reaches ~0.70; ε = 0.1 reaches ~0.70. Additional sweeps in Figure 11 (Appendix D.6) reinforce the pattern of domain-dependence.

The paper also provides negative evidence from the "Why not use regression?" experiment (Figure 3d), which shows that even an ensemble of regressors cannot reliably predict program quality from embeddings. This implies that the embedding space does not have a simple, globally consistent relationship between distance and reward difference—which is precisely the property that would be needed to derive ε from first principles (e.g., by setting ε to the distance at which expected reward difference falls below some threshold).

Mitigation status. Partially addressed through empirical characterization but not resolved. The paper provides ε sensitivity curves for two domains, giving practitioners reference points, and concludes that ε selection is "not very sensitive" within a range—but this reassurance only holds if the practitioner can identify the range, which itself requires experimentation. The paper does not propose an adaptive ε-selection mechanism, a method for estimating the appropriate ε from a small pilot study, or a way to relate ε to observable properties of the domain (e.g., embedding distance between known-good and known-bad programs). Section 7 (Limitations) does not mention this issue.

---

The Theoretical Guarantees Require Assumptions That Are Unverifiable in Practice

The assumption or constraint. The convergence proof (Theorem 1, Section 4) relies on Assumption 1: there exist constants γ > 0 and δ₀ ∈ (0, 1) such that for any θ ∈ Θ with µ(θ) ≤ B−γ, the LLM optimizer O has probability at least δ₀ of proposing a θ' with µ(θ') > µ(θ) + γ. In plain language: the optimizer can, with some non-negligible probability, produce a program that is strictly better by at least γ whenever the current program is not already near-optimal.

This is an extraordinarily strong assumption with no empirical validation in the paper. The constants γ and δ₀ characterize the optimizer's capability: γ is the minimum improvement the optimizer can reliably achieve, and δ₀ is the probability of achieving it. Neither constant is estimated, bounded, or even discussed in the experimental sections. The paper does not measure whether the Gemini 2.0 Flash optimizer used in τ-bench satisfies this assumption, what γ and δ₀ would be for that optimizer on that domain, or whether the assumption holds for some programs but not others (e.g., does the optimizer have a higher δ₀ for easy problems than hard ones?). The theoretical analysis treats γ and δ₀ as given constants, but in practice they are unknown and potentially zero for some problem domains or optimizer configurations.

The bound in Theorem 1 depends critically on these constants: the expected number of iterations spent on non-near-optimal programs is O((B/2γδ₀ + 64σ²N_ε/γ²) log(n)). If δ₀ is very small (the optimizer rarely produces improvements), the first term dominates and convergence is slow. If γ is very small (improvements are tiny), both terms explode. In the worst case—if the optimizer has zero probability of producing strict improvements (δ₀ = 0) for some reward range—the assumption is violated and the theorem provides no guarantee at all. The paper acknowledges this only in passing: "the assumption on the optimizer may not always be realistic" (Section 7, Limitations).

A second unverifiable assumption is that the embedding-based ε-Net filtering preserves the optimization structure—specifically, that programs with embedding distance less than ε have expected rewards that are indistinguishable within the available evaluation budget. This is implicit in the paper's use of ε to control the discretization, but there is no test of whether semantically similar programs (by the Gemini embedding metric) actually have similar expected rewards. The regression failure experiment (Figure 3d) provides suggestive negative evidence: if embeddings captured reward structure well, a regressor trained on them should be able to predict scores. Its failure suggests that the relationship between embedding distance and reward difference is noisy, which would weaken the ε-Net's theoretical justification.

The consequence. The theoretical results do not provide quantitative guidance for practitioners. The bound in Theorem 1 contains the covering number N_ε, the sub-Gaussian parameter σ, the improvement probability δ₀, and the improvement step γ—none of which can be estimated from observable quantities without extensive additional experimentation. A practitioner cannot use the theory to predict how many iterations POLCA needs for their problem, to choose ε optimally, or to decide whether POLCA is likely to converge at all. The theory serves as a qualitative plausibility argument ("persistent memory + UCB exploration + ε-Net filtering is sufficient in principle") but not as a quantitative engineering tool.

More fundamentally, if Assumption 1 is violated in practice—if the LLM optimizer, given feedback on a mediocre program, cannot reliably propose a better one—then POLCA's convergence guarantees evaporate. The paper provides no diagnostic for detecting this condition during optimization. A practitioner who deploys POLCA on a domain where the optimizer is ineffective (e.g., because the feedback signal is too weak, or because the program space is too complex for the LLM to navigate via local modifications) will observe POLCA running for its full budget without making progress, with no indication that the failure is due to assumption violation rather than insufficient budget.

What evidence exists in the paper. None. The paper contains no experiments that estimate γ, δ₀, or σ for any benchmark. There is no ablation where the optimizer's capability is degraded (e.g., by using a smaller LLM, or by providing less informative feedback) to test whether the convergence behavior degrades as predicted by the theory. There is no test of whether the embedding distance correlates with reward difference. The "Limitations" section (Section 7) notes that "the assumption on the optimizer may not always be realistic" and that "more advanced function approximation methods than semantic embedding distance for filtering is possible," but these acknowledgments are generic and do not characterize the severity of the gap between theory and practice.

Mitigation status. Acknowledged but not addressed. The paper's Section 7 states that the UCB analysis "relies on the knowledge of the degree of stochasticity in the reward, and the assumption on the optimizer may not always be realistic." The experiments default to the empirical mean priority rather than UCB, which sidesteps the need to know σ but also means the theoretical guarantees do not apply to the algorithm as deployed. No empirical procedure is proposed for estimating σ, γ, or δ₀ from optimization traces, and no adaptive mechanism is proposed that would switch strategies if the assumption appears violated.

---

Single-Model, Single-Domain Per Benchmark Limits Generalization Claims

The assumption or constraint. Each benchmark in the paper uses a single backbone LLM configuration: Gemini 2.0 Flash for τ-bench, Gemini 2.5 Flash Lite for HotpotQA, Claude 3.5 Sonnet for VeriBench, and Claude 3.7 Sonnet for KernelBench. These choices are not varied within any benchmark, and no experiments test POLCA with multiple model families on the same task. The embedding models similarly vary: Gemini text-embedding-004 for τ-bench and VeriBench, Gemini embedding-001 for HotpotQA and KernelBench. The paper states that these models are "representative of the capabilities of many contemporary LLMs" (Section 5 intro) but provides no evidence for this claim.

This matters because POLCA's mechanisms—particularly the Summarizer (which relies on the LLM's ability to synthesize patterns from historical trajectories) and the ε-Net filtering (which relies on the embedding model's ability to capture semantic program similarity)—may be quality-dependent. A weaker backbone LLM might produce less informative Summarizer outputs, reducing the benefit of the global context. A weaker embedding model might fail to distinguish meaningfully different programs (producing small distances for programs with different behavior), causing the ε-Net to either (a) reject genuinely novel programs because they appear similar in a poor embedding, or (b) accept redundant programs because they appear different when they are not. The paper's theoretical framework assumes the embedding is "good" (captures reward-relevant information with a well-behaved Lipschitz relationship), but this assumption is never tested across embedding models.

The consequence. A practitioner cannot infer from the paper's results how POLCA will perform with their specific model and embedding configuration. If they use a less capable LLM as the optimizer (e.g., an open-source 7B model instead of Gemini 2.0 Flash), the Summarizer's guidance may be less informative, and the δ₀ in Assumption 1 may be lower or zero, causing POLCA to underperform relative to simpler methods that make fewer demands on optimizer quality. If they use a different embedding model (e.g., a lightweight embedding model optimized for retrieval rather than semantic similarity), the ε-Net may filter incorrectly, either admitting too many near-duplicates or rejecting too many novel programs.

The paper's experiments span models from two providers (Google Gemini and Anthropic Claude) across two embedding models from one provider (Google), but each benchmark uses a single fixed configuration. This means the results cannot disentangle "POLCA works well" from "POLCA works well with Gemini 2.0 Flash on τ-bench" or "with Claude 3.5 Sonnet on VeriBench." The observed performance differences between benchmarks (e.g., POLCA's larger advantage over baselines on VeriBench than on KernelBench) confound domain differences with model differences—we cannot tell whether POLCA is more effective on code verification than kernel optimization, or whether POLCA works better with Claude 3.5 Sonnet than with Claude 3.7 Sonnet.

What evidence exists in the paper. The paper provides some indirect evidence of model-dependence through the cross-benchmark patterns. On VeriBench (Claude 3.5 Sonnet), POLCA achieves a 0.952 compilation pass rate vs. 0.888 for DSPy—a gap of 0.064. On KernelBench (Claude 3.7 Sonnet), POLCA achieves ~0.75 fast_1.0 vs. ~0.55 for GEPA—a gap of 0.20. These gaps differ in magnitude, but we cannot attribute the difference to the model vs. the domain. The paper does not include any experiment where the same benchmark is run with two different backbone models, or where the same model is tested with two different embedding models.

The ablation study (Figure 3a) provides the closest thing to a model-dependence analysis: it shows that removing the Summarizer degrades performance, which implies that the Summarizer (and thus the LLM that implements it) contributes value. But this is tested only on τ-bench with Gemini 2.0 Flash—we do not know whether a weaker Summarizer LLM would provide less value, or whether a stronger one would provide more.

Mitigation status. Not addressed. The paper acknowledges in Section 7 that "the observations made in the experimental results may be limited to the benchmarks and models tested here, despite our best efforts to make them representative," but makes no attempt to characterize the scope of this limitation through model ablation, embedding model comparison, or scaling studies. The use of different models across benchmarks is presented as a feature (demonstrating applicability across model families) rather than a confound (preventing controlled comparison), and no discussion addresses how a practitioner should choose among model configurations for POLCA deployment.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper does not introduce a new optimizer architecture or a more sophisticated search algorithm—it introduces a new design constraint for the entire field of generative optimization: stochasticity must be treated as a first-class concern, not an afterthought. This is a methodological reframing rather than a paradigm shift, but it is a reframing with teeth because it invalidates the implicit assumptions under which most prior generative optimization algorithms were designed and evaluated.

The central diagnostic is that existing algorithms—DSPy's iterative refinement, OpenEvolve's evolutionary selection, GEPA's Pareto-frontier maintenance—make irreversible decisions based on single noisy evaluations. In the deterministic or near-deterministic settings where these algorithms were developed (code compilation, scientific discovery with verifiable outcomes), this is acceptable because a single evaluation is approximately ground truth. But the paper demonstrates empirically that when stochasticity enters the picture—through minibatch sampling of large task distributions (τ-bench, HotpotQA), LLM-judge noise (VeriBench 3-step), or inherent program stochasticity (LLM agents)—these irreversible decisions become the primary failure mode. OpenEvolve's single-evaluation-per-candidate approach on τ-bench achieves a pass@1 of 0.418, barely above the base prompt's 0.389, because it cannot distinguish between a genuinely good prompt that was unlucky in its evaluation and a mediocre prompt that was lucky. GEPA's Pareto frontier, elegant in deterministic multi-objective optimization, collapses to a single noisy point in single-task stochastic settings (Section 5.2), degenerating into a random walk.

What makes this reframing significant is that it provides a unified explanation for previously contradictory results. The paper does not claim that DSPy, GEPA, or OpenEvolve are bad algorithms—it claims that they are good algorithms for the wrong problem setting. On deterministic KernelBench (Figure 2d), GEPA achieves a fast_1.0 of approximately 0.55, competitive with POLCA's 0.75 and outperforming DSPy's 0.30. On stochastic τ-bench, the ranking nearly inverts. This is not a contradiction; it is a diagnosis. The community's mixed experience with generative optimization—some papers reporting dramatic successes, others reporting plateaus and instability (Kumar et al., 2024; Chen et al., 2024)—can be understood as a consequence of applying algorithms designed for deterministic evaluation to problems with varying degrees of stochasticity, without recognizing that the transition from deterministic to stochastic evaluation changes the fundamental requirements of the optimization architecture.

This diagnosis reshuffles research priorities in three specific ways:

1. Memory architecture becomes as important as optimizer design. Prior work focused heavily on how the LLM optimizer proposes improvements—beam search strategies, reflection prompts, evolutionary crossover operators. POLCA demonstrates that when evaluations are noisy, the memory architecture (how candidates are stored, scored, and re-evaluated) is at least as important as the proposal mechanism. Adding the ε-Net and persistent memory to vanilla POLCA improves τ-bench performance from 0.52 to 0.64 (Figure 3a), while the optimizer itself is unchanged. This suggests that for stochastic problems, investment in better memory management yields higher returns than investment in more sophisticated proposal generation—a non-obvious allocation of research effort that the paper's ablation makes concrete.

2. Batch-oriented, parallel evaluation architectures become architecturally necessary, not just implementation optimizations. DSPy-style sequential refinement is conceptually simple and easy to implement, but it is structurally incapable of accumulating evidence across multiple evaluations of the same candidate because each candidate is evaluated once and then discarded (or used only as a stepping stone). POLCA's batch design—evaluating multiple seed programs on multiple tasks in parallel, then using the same minibatch to fairly compare new proposals against seeds—is not merely a speed optimization; it is the architectural prerequisite for the persistent memory to function. If evaluations were serial, the time to accumulate enough evidence to distinguish good from lucky would be prohibitive. The paper's dual-budget analysis (evaluation steps vs. metric calls, Appendix D.3) makes this explicit: POLCA dominates on wall-clock time (evaluation steps) because its parallel evaluation amortizes the cost of evidence accumulation, while sequential methods pay the full latency cost for each noisy observation.

3. Evaluation budget stops being a single number and becomes a multidimensional resource. Prior work typically reports "number of evaluations" as a scalar budget. POLCA's design reveals that there are at least three distinct resources being consumed: (a) metric calls (total program-task evaluations), (b) evaluation steps (sequential operations, a proxy for wall-clock time), and (c) optimizer-side compute (LLM calls for the Summarizer and proposal generation). A method that is efficient in one dimension may be wasteful in another. The Appendix D.3 analysis shows that POLCA's early-stage efficiency is lower than GEPA's when measured by metric calls alone (because POLCA spreads its budget across multiple candidates and re-evaluations), but substantially higher when measured by evaluation steps (because parallelization compresses many metric calls into few sequential operations). This multi-dimensional view of the optimization budget is not a POLCA-specific consideration—it applies to any generative optimization algorithm that balances exploration breadth against evaluation depth—and the paper provides the vocabulary and metrics for reasoning about it.

The practical consequence is that the field should stop evaluating generative optimization algorithms solely by their asymptotic best-found performance at a fixed total-evaluation budget. The trajectory matters (how quickly does performance improve?), the wall-clock time matters (are gains from more evaluations offset by serial latency?), and the optimizer-side cost matters (does a method that uses fewer evaluations but more LLM calls actually cost less?). The paper's experimental reporting—with separate curves for evaluation steps, metric calls, proposal steps, and number of proposals across all benchmarks (Figures 4–9)—establishes a reporting standard that future work should adopt.

Follow-Up Research This Work Enables

Adaptive ε selection from a small pilot budget. The paper's ε sensitivity analysis (Figures 3b, 3c) reveals that POLCA works well within a domain-specific ε range, but that the range must be discovered empirically—there is no a priori method for choosing ε. A natural follow-up is to develop an adaptive ε-selection procedure that operates during the early iterations of optimization, before the budget is substantially depleted. The idea: start with a moderate ε, periodically test whether the queue is growing too fast (suggesting ε is too small and near-duplicates are being admitted) or whether too many proposals are being rejected (suggesting ε is too large and genuinely distinct programs are being filtered out), and adjust ε online. This could be operationalized by tracking the acceptance rate of new proposals over a sliding window and maintaining a target acceptance rate (e.g., 30–50% of raw proposals accepted). If POLCA is inherently robust to ε within a range, an adaptive mechanism only needs to find any point in that range, not the optimal point. A strong evaluation would run the same benchmarks as the paper with the adaptive mechanism, compare against the best fixed ε from the full ablation, and measure how much of the budget is consumed by the adaptation process—the key metric is whether the adaptive procedure finds a good ε using less budget than a full sweep would require.

Combining POLCA's memory with process reward model (PRM) guided search. The paper studies POLCA with a black-box LLM optimizer that proposes complete programs given feedback, but the proposal mechanism does not perform step-by-step search or verification. A natural extension—suggested by the paper's Section C, which describes how POLCA can instantiate beam search—is to integrate a PRM that scores partial programs (e.g., individual code blocks, prompt sections, or reasoning steps) and guides the optimizer toward promising partial constructions, while using POLCA's persistent memory to accumulate evidence about which partial constructions lead to good complete programs across multiple evaluations. This would address a limitation of current PRM-guided search methods (Pryzant et al., 2023; Chen et al., 2024): they typically score partial solutions once and prune or expand branches based on those single scores. Under stochastic evaluation, this replicates the same noise-sensitivity problem that POLCA solves for complete programs. The combination would use POLCA's memory to track partial programs, their accumulated scores, and their downstream outcomes, enabling the search to revisit branches that were prematurely pruned due to noisy intermediate scores. A strong experiment would take a benchmark where PRM-guided search has been shown to work (e.g., mathematical reasoning with step-level verification) and add controlled stochasticity to the verifier (e.g., by corrupting step-level scores with noise, or by using an LLM judge with known variance), then compare standard beam search against POLCA-augmented beam search. The prediction is that the advantage of POLCA's memory grows with the noise level of the verifier.

Difficulty-conditioned budget allocation for generative optimization. The paper's experiments allocate a uniform budget to all optimization problems (all τ-bench prompts get the same number of iterations, all VeriBench tasks get 50 metric calls), but the returns to additional optimization are not uniform—some problems are fundamentally outside the base model's capability and no amount of optimization helps (the τ-bench held-out tasks where POLCA achieves only 0.425 vs. baseline 0.392), while others are within reach and benefit substantially. POLCA's architecture provides a natural mechanism for difficulty estimation: the trajectory of a program's empirical mean score as more evaluations accumulate reveals not just its quality but also the variance of its performance. A program whose score oscillates wildly across minibatches is being evaluated under high stochasticity and may need more evaluations to accurately assess; a program whose score is consistently low even after many evaluations is likely just bad; a program whose score plateaus near the maximum after few evaluations is an easy problem. A difficulty-conditioned variant of POLCA could use these within-queue statistics to allocate budget adaptively: problems where no candidate in the queue has achieved a score above some threshold after N evaluations could be terminated early (unlikely to be solvable under this model + optimizer combination), freeing budget for problems where candidates are hovering near the decision boundary and additional evaluations could identify a winner. This is conceptually analogous to the compute-optimal test-time scaling work on MATH problems, but applied to the generative optimization setting. A strong evaluation would take the τ-bench setup with a fixed total budget across many held-out tasks, compare uniform allocation against difficulty-conditioned allocation, and measure the aggregate pass@1—the hypothesis is that shifting budget from near-zero-improvement tasks to near-threshold tasks yields a higher overall score for the same total budget.

Characterizing the relationship between embedding distance and reward difference. The paper's ε-Net mechanism assumes that programs with small embedding distance have similar expected rewards, but this assumption is never directly tested. The regression failure experiment (Figure 3d) provides suggestive negative evidence—an ensemble of regressors on embeddings cannot predict scores well enough to replace empirical means—but this doesn't isolate why. Do embeddings fail to capture reward-relevant structure because (a) the embedding space is too low-dimensional to represent the complexity of program semantics, (b) the embedding model is trained on a different distribution (general web text) that doesn't transfer to the specific semantics of, say, Lean 4 code or CUDA kernels, or (c) reward differences are genuinely not smooth in the embedding space (small lexical changes can have large behavioral consequences)? A systematic investigation would collect a large set of programs from POLCA optimization runs (across τ-bench and VeriBench, where the paper already has data), compute pairwise embedding distances, measure pairwise reward differences (using many evaluations to get near-deterministic estimates of µ(θ)), and plot distance vs. reward difference. This would reveal: (1) whether there exists a distance threshold below which reward differences are small (validating the ε-Net's smoothing assumption), (2) whether this threshold is domain-dependent or embedding-model-dependent, and (3) whether the relationship is monotonic (does larger distance imply larger reward difference on average, or is it scattered?). This experiment does not require new algorithm development—it is purely analytical, using data that can be collected from existing POLCA runs—but it would provide the missing empirical foundation for the ε-Net's theoretical justification and guide the choice of ε in practice.

Scaling laws for generative optimization: how does the benefit of persistent memory change with evaluation budget and problem complexity? The paper demonstrates that POLCA outperforms baselines at the specific budgets tested (50–2500 metric calls, depending on the benchmark), but the relative advantage may depend on budget scale. At very small budgets (e.g., 10 metric calls), sequential methods that focus all evaluations on a single improvement chain may outperform POLCA's broader exploration (as suggested by the early-stage metric-call efficiency results in Appendix D.3, where sequential baselines sometimes lead at low budgets). At very large budgets (e.g., 10,000+ metric calls), all methods may converge to the same asymptote (limited by the optimizer's capability, not the evaluation architecture), and POLCA's advantage disappears. At intermediate budgets—the regime where most practical optimization happens—POLCA's advantage is largest. Characterizing this scaling behavior would involve running POLCA and baselines across a wide range of budgets on a fixed benchmark (τ-bench is natural because it has the most stochasticity), fitting curves of performance vs. budget, and extracting the budget range where POLCA's efficiency advantage (measured as the factor by which baselines need more budget to match POLCA's performance) is maximized. This is the generative optimization analog of scaling-law analyses in pretraining, and it would provide practitioners with guidance on when POLCA is worth the implementation complexity versus when a simpler method suffices.

Negative result: stress-testing POLCA's failure modes to define its applicability boundary. The paper demonstrates where POLCA succeeds but does not systematically characterize where it fails. At least three failure-mode experiments would refine our understanding of POLCA's boundary conditions, each producing a negative result that is as informative as a positive one: (1) Optimizer capability ablation: intentionally degrade the optimizer (by using a smaller LLM, providing truncated feedback, or removing the Summarizer's global context) and measure whether POLCA's advantage over baselines grows (if the persistent memory compensates for a weaker optimizer), stays constant, or shrinks (if the memory's benefit depends on the optimizer being good enough to propose improvements in the first place). The prediction from theory (Theorem 1) is that smaller δ₀ leads to slower convergence, but the practical question is whether the memory mechanism makes POLCA more or less sensitive to optimizer quality than baselines. (2) Embedding model ablation: replace the Gemini embedding model with a weaker embedding model (e.g., a lightweight sentence transformer not fine-tuned for code or instruction semantics) and measure the impact on POLCA's performance. If the ε-Net is robust to embedding quality (because even a weak embedding captures enough coarse semantic structure to filter near-duplicates), this is strong evidence for the practical deployability of POLCA. If performance degrades sharply, it reveals a hidden dependency on embedding quality that practitioners must account for. (3) Task distribution shift: train prompts on the first 10 τ-bench tasks (as in the paper) but test on tasks from a different τ-bench domain (e.g., airline instead of retail) to measure how well POLCA's optimized prompts transfer across domains. This tests whether POLCA's diversity-preserving ε-Net leads to prompts that are more general (because the diverse population covers a broader range of strategies, some of which may transfer) or more domain-specific (because the memory accumulates in-domain evaluation data that biases the population toward retail-specific patterns). The outcome has direct implications for whether POLCA is suitable for few-shot optimization where the training and deployment distributions differ.

Practical Applications and Downstream Use Cases

Optimizing LLM-agent system prompts for production customer-service deployments. The τ-bench experiments (Section 5.1) directly model a real-world scenario: a company deploys an LLM agent to handle customer service queries across a retail domain, but the agent's base prompt (written by an engineer) achieves only 38.9% task resolution. The company has access to a handful of representative training tasks (e.g., 10–20) and wants to optimize the prompt to maximize resolution rate across the full task distribution. POLCA's 13% relative improvement on this benchmark—from 0.389 to 0.439 pass@1 across all 115 tasks—demonstrates that even modest optimization budgets can yield meaningful business impact. The key practical advantage over manual iteration is that POLCA handles the stochasticity inherent in evaluating agent performance (the agent behaves differently on the same task across trials, and the training tasks are only a small sample of the full distribution), producing a prompt that generalizes reliably rather than overfitting to the specific training tasks. For a company handling thousands of customer interactions per day, a 5-percentage-point improvement in resolution rate (the absolute gain POLCA achieves over the base prompt on the 105 held-out tasks, Table 1) translates directly to reduced human escalation costs, faster resolution times, and improved customer satisfaction—all without requiring an engineer to manually analyze failure cases and rewrite prompts. The implementation is straightforward: treat the agent's additional_instructions string as the optimizable parameter, use historical task data (or a small set of representative tasks) as the dataset D, and configure POLCA with the same LLM that powers the agent.

Automated formal verification of LLM-generated code. The VeriBench compilation results (Table 2) demonstrate a compelling use case: translating Python programs into verifiable Lean 4 code with a 95.2% success rate versus 88.8% for the next-best method (DSPy), using the same per-task budget of 50 compiler calls. This has direct implications for software verification pipelines where LLMs generate code that must be formally verified. The critical bottleneck in such pipelines is not generating candidate translations—modern LLMs can produce plausible Lean 4 code—but identifying which of the generated translations actually compile and pass verification. In a deterministic compilation setting, POLCA's advantage comes from parallel exploration of multiple code variants from multiple seed programs, combined with global context summarization that helps the optimizer avoid recurring failure patterns (e.g., type mismatches, syntax errors specific to Lean 4). For a verification engineer, this means: feed the Python specification to POLCA, let it run for 50 compiler calls, and receive a compiled, verified Lean 4 implementation with 95% probability, versus 89% for DSPy's sequential approach. The 6.4-percentage-point gap represents programs that would otherwise require manual debugging of compilation errors—a time-consuming process requiring expertise in both the source and target languages. More broadly, this pattern applies to any code translation task where a compiler or static analyzer provides fast, deterministic feedback: SQL-to-optimized-SQL, Python-to-Rust, or legacy COBOL-to-Java translation, all of which are active areas of industrial LLM deployment.

CUDA kernel optimization for specialized hardware. The KernelBench results (Section 5.3, Figure 2d) suggest POLCA can accelerate the tedious process of hand-optimizing GPU kernels. At fast_1.0 (correct kernels exceeding PyTorch baseline speed), POLCA achieves approximately 75% on the 16 matrix multiplication tasks, versus 55% for GEPA and 30% for DSPy or OpenEvolve. Even at the more forgiving fast_0.5 threshold (kernels reaching half of PyTorch speed), POLCA reaches approximately 90%. For an ML engineer optimizing inference or training pipelines, this means: given a PyTorch reference implementation for a matrix operation, POLCA can automatically discover custom CUDA kernels that are both correct and competitive with (or faster than) the highly-optimized PyTorch baseline, using the Claude 3.7 Sonnet model. The 20-percentage-point gap between POLCA and GEPA at fast_1.0 translates to almost twice as many tasks achieving a speedup—a meaningful productivity gain when optimizing a large model architecture with many distinct operators. The caveat is that these results are single-seed on a curated subset of 16 tasks, so they should be treated as a proof of concept rather than a reliable performance estimate. But the architecture is immediately applicable: an engineer identifies bottleneck operators in their PyTorch model via profiling, feeds each operator's reference implementation to POLCA, and receives optimized CUDA kernels that are correctness-tested and benchmarked against the baseline, all without writing CUDA code manually.

Prompt optimization for retrieval-augmented QA systems. The HotpotQA results (Figure 2b) demonstrate POLCA's applicability to a common enterprise deployment: a RAG (retrieval-augmented generation) system that answers user questions by reasoning over retrieved documents. The base prompt (a simple "Answer the question based on the context") achieves approximately 75–80% accuracy on multi-hop questions, but POLCA-optimized prompts push accuracy near 100% within 50 evaluation steps. For an organization deploying an internal Q&A system over their documentation, this means: collect a representative set of 100 question-answer pairs (with associated context documents), run POLCA overnight to optimize the system prompt, and deploy a prompt that nearly eliminates simple reasoning failures. The specific patterns POLCA discovers—as visible in the optimized prompt case study (Appendix E.2), which includes detailed instructions for multi-hop reasoning decomposition, answer formatting rules, and ambiguity resolution—are the kind of systematic improvements that would take a human prompt engineer days of iterative testing to discover, but which POLCA extracts automatically from the contrastive analysis of successful and failed trajectories across many candidate prompts. The 20-percentage-point improvement over baselines at the same budget (POLCA ≈ 1.00 vs. GEPA ≈ 0.85, Figure 2b) is large enough to justify the implementation effort for any system where answer quality directly impacts user trust or downstream decision-making.

When to Prefer This Method

The paper does not articulate an explicit tradeoff rule or decision framework for choosing POLCA over named alternatives. It does not include experiments where POLCA is compared against baselines under systematically varied conditions (stochasticity level, budget size, optimizer quality) to produce a decision boundary. The ablation studies characterize POLCA's internal mechanisms (ε-Net vs. no ε-Net, Summarizer vs. no Summarizer) but do not position it against external alternatives with clear "prefer POLCA when X, prefer GEPA when Y" guidance. Therefore, a decision matrix cannot be derived from the paper's content without fabricating conditions the authors did not specify. Practitioners should consult the per-benchmark results for domain-specific guidance—POLCA shows the largest advantages on τ-bench (high stochasticity from all three sources) and VeriBench 3-step (evaluator noise), a moderate advantage on HotpotQA and VeriBench compilation, and a promising but unreplicated advantage on KernelBench—but the paper provides no framework for extrapolating these results to new domains.