Polca Stochastic Generative Optimization

---
name: polca-stochastic-generative-optimization
title: "POLCA: Stochastic Generative Optimization with LLM"
version: 0.0.2
engine: skillxiv-v0.0.2-claude-opus-4.6
license: MIT
url: "https://arxiv.org/abs/2603.14769"
keywords: [Generative Optimization, LLM as Optimizer, Stochastic Feedback, Priority Queues, Meta-Learning]
description: "Use language models as optimizers to iteratively improve complex systems (prompts, code, agent policies) through noisy feedback and sampling. POLCA maintains a priority queue of candidates, explores with epsilon-nets, and learns meta-insights from trial history."
---

# POLCA: Stochastic Generative Optimization with Language Models

Most optimization of LLM-based systems happens offline through manual iteration. POLCA inverts this by making the language model itself the optimizer, receiving both numerical rewards and textual feedback to propose improved solutions iteratively. This approach handles real-world stochasticity from noisy evaluations, sampling variance, and system non-determinism—enabling continuous improvement of prompts, agents, and code under realistic conditions.

The key technical contribution is combining three mechanisms: priority queue management for exploration-exploitation tradeoff, epsilon-nets for diversity preservation, and an LLM-based summarizer that learns from historical trials. The framework includes theoretical convergence guarantees under stochasticity.

## Core Concept

POLCA treats a generative language model as an optimization algorithm where:

1. **Input**: Current candidate solution + numerical reward + textual feedback
2. **Process**: LLM proposes improved candidates by reasoning about past attempts
3. **Output**: Diverse set of candidate solutions ranked by potential improvement
4. **Feedback Loop**: Evaluate candidates, aggregate insights, feed back to LLM

This setup enables the model to learn meta-patterns across attempts without requiring explicit gradient computation or hand-engineered search strategies.

## Architecture Overview

- **Priority Queue** — Maintains sorted candidate solutions; candidate ordering balances high-score exploitation with under-explored diversity
- **Epsilon-Net Mechanism** — Preserves exploration by tracking which parameter regions have been sufficiently sampled
- **LLM Summarizer** — Generates textual meta-insights from trial history to condition future proposals; learns general improvement patterns
- **Numerical Reward Signal** — Primary feedback for ranking candidates; can be noisy or adversarial
- **Textual Feedback** — Secondary signal that explains why solutions succeeded/failed, enabling meta-learning
- **Stochastic Dynamics** — Explicitly models multiple sources of noise (feedback, sampling, system behavior)

## Implementation Steps

Start by setting up the priority queue and epsilon-net tracking to manage the exploration-exploitation balance.

```python
import heapq
from collections import defaultdict
import numpy as np

class CandidateQueue:
    """Priority queue managing candidates with diversity tracking."""

    def __init__(self, epsilon=0.1, max_size=1000):
        self.epsilon = epsilon  # Min distance for diversity
        self.candidates = []  # Max-heap (negate scores)
        self.explored_regions = set()
        self.max_size = max_size

    def add(self, candidate, score, feedback=""):
        """Add candidate; reject if too close to explored region."""
        # Discretize parameter space for epsilon-net tracking
        region_key = self._discretize(candidate)

        if region_key in self.explored_regions:
            # Only add if score significantly improves
            best_in_region = self._best_in_region(region_key)
            if score <= best_in_region + 0.01:  # Noise margin
                return False

        # Add to priority queue
        heapq.heappush(self.candidates,
                      (-score, len(self.candidates), candidate, feedback))
        self.explored_regions.add(region_key)

        # Maintain max size
        if len(self.candidates) > self.max_size:
            heapq.heappop(self.candidates)

        return True

    def pop_top_k(self, k=5):
        """Return top-k candidates for evaluation."""
        return [candidate for _, _, candidate, _ in self.candidates[:k]]

    def _discretize(self, candidate, bins=10):
        """Convert continuous parameters to discrete regions."""
        return tuple(int(hash(str(c)) % bins) for c in candidate[:3])

    def _best_in_region(self, region_key):
        """Get best score in explored region."""
        return max(((-score, score) for neg_score, _, _, _
                   in self.candidates
                   if self._discretize(_) == region_key),
                  default=(0, 0))[1]
```

Next, implement the LLM summarizer that learns patterns from trial history and generates improvement suggestions.

```python
# LLM-based meta-learner that summarizes trial history
class LLMSummarizer:
    """Extract insights from trial history to guide future optimization."""

    def __init__(self, llm_model):
        self.llm = llm_model
        self.trial_history = []

    def add_trial(self, candidate, score, feedback):
        """Record trial outcome."""
        self.trial_history.append({
            'candidate': candidate,
            'score': score,
            'feedback': feedback
        })

    def summarize_insights(self):
        """Generate meta-insights from trial history."""
        if len(self.trial_history) < 2:
            return "No sufficient data for insights."

        # Format trial summaries
        trial_strings = []
        for trial in self.trial_history[-10:]:  # Use recent trials
            trial_strings.append(
                f"Candidate: {trial['candidate'][:100]}\n"
                f"Score: {trial['score']:.3f}\n"
                f"Feedback: {trial['feedback']}"
            )

        prompt = f"""Analyze these optimization trials and identify patterns:

{chr(10).join(trial_strings)}

What are the key factors driving high vs low scores? What improvements should we try next?"""

        insights = self.llm.generate(prompt, max_tokens=200)
        return insights

    def propose_improvements(self, best_candidate, best_score):
        """Generate candidate improvements based on insights."""
        insights = self.summarize_insights()

        prompt = f"""Current best solution:
{best_candidate}
Score: {best_score:.3f}

Key insights from trials:
{insights}

Generate 3 diverse improvements to this solution that address the identified issues."""

        proposals = self.llm.generate(prompt, max_tokens=300)
        return proposals
```

Finally, implement the main optimization loop that orchestrates candidate generation, evaluation, and learning.

```python
# Main POLCA optimization loop
class POLCAOptimizer:
    """Stochastic generative optimization using LLM."""

    def __init__(self, llm_model, evaluator, initial_solution):
        self.llm = llm_model
        self.evaluator = evaluator
        self.queue = CandidateQueue(epsilon=0.1)
        self.summarizer = LLMSummarizer(llm_model)
        self.best_candidate = initial_solution
        self.best_score = -float('inf')

    def step(self):
        """One optimization step: propose, evaluate, learn."""
        # Generate improvement proposals using LLM
        proposals_text = self.summarizer.propose_improvements(
            self.best_candidate, self.best_score)

        # Parse proposals into candidates
        candidates = self._parse_proposals(proposals_text)

        # Evaluate candidates (may be noisy)
        scores_and_feedback = []
        for candidate in candidates:
            score, feedback = self.evaluator(candidate)
            scores_and_feedback.append((candidate, score, feedback))

            # Update best if improved
            if score > self.best_score:
                self.best_score = score
                self.best_candidate = candidate

            # Add to queue
            self.queue.add(candidate, score, feedback)

            # Record for meta-learning
            self.summarizer.add_trial(candidate, score, feedback)

        return scores_and_feedback

    def optimize(self, num_steps=100):
        """Run optimization for num_steps iterations."""
        best_scores = [self.best_score]

        for step in range(num_steps):
            results = self.step()

            # Exponential moving average of best score
            recent_best = max(score for _, score, _ in results)
            best_scores.append(max(best_scores[-1], recent_best))

            if (step + 1) % 10 == 0:
                improvement = best_scores[-1] - best_scores[0]
                print(f"Step {step+1}: Best Score = {self.best_score:.4f}, "
                      f"Total Improvement = {improvement:.4f}")

            # Check for convergence
            if len(best_scores) > 20:
                recent_improvement = best_scores[-1] - best_scores[-20]
                if recent_improvement < 0.001:
                    print(f"Converged at step {step+1}")
                    break

        return self.best_candidate

    def _parse_proposals(self, proposals_text):
        """Extract structured candidates from LLM text output."""
        # This is application-specific; adapt to your candidate format
        candidates = proposals_text.split('\n\n')
        return candidates[:3]  # Take top 3 proposals
```

## Practical Guidance

**Hyperparameters and When to Use:**
- Epsilon values of 0.05-0.15 work well; smaller values increase exploration overhead, larger values risk premature convergence
- Priority queue size should be 10-100x number of simultaneous evaluations; larger queues enable better diversity but increase storage
- Use when you have reliable but potentially noisy evaluation functions (can tolerate stochastic rewards)
- Ideal for optimizing prompts, hyperparameters, or agent behaviors where manual iteration is expensive

**When NOT to use:**
- If your evaluation function is deterministic and differentiable, use gradient-based optimization instead
- When computational budget is extremely tight; POLCA requires many LLM calls
- For high-dimensional continuous spaces without structure (use Bayesian optimization instead)

**Common Pitfalls:**
- LLM proposals can become stale if diversity isn't maintained; always use epsilon-net mechanism
- Noisy rewards can mislead the optimizer; consider using running averages of scores
- Feedback text should be informative; empty or uninformative feedback degrades meta-learning
- Priority queue management without epsilon-net can lead to repeated proposals of similar candidates

## Reference

Paper: [POLCA: Stochastic Generative Optimization with LLM](https://arxiv.org/abs/2603.14769)