adu2021 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:
- Input: Current candidate solution + numerical reward + textual feedback
- Process: LLM proposes improved candidates by reasoning about past attempts
- Output: Diverse set of candidate solutions ranked by potential improvement
- 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.
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.
# 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.
# 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