Technical Summary: SAGE (Stochastic Prompt Optimization via Agent-Guided Exploration)

Problem Statement

The paper addresses the challenge of Automatic Prompt Optimization (APO), specifically within the domain of Context Engineering—the optimization of the informational context surrounding Large Language Model (LLM) queries without updating model parameters.

The authors argue that the field lacks a unifying theoretical perspective. While recent work (Melcer et al., 2025) established that APO is fundamentally a black-box search problem (as textual gradients do not function as real gradients), existing approaches suffer from two primary limitations:

1. Myopic Search: Per-sample methods process one training example at a time, greedily accumulating edits. This is computationally expensive and prone to local optima.
2. Shallow Analysis: Most methods constrain optimization to LLM-only reasoning. Even multi-agent approaches that utilize code tools often use them for procedural artifact construction rather than diagnostic analysis of error patterns.

The prompt landscape is characterized as a noisy, black-box optimization problem with expensive evaluations, low effective dimensionality, and rich local structure. The effectiveness of an optimization strategy depends on the interaction between the landscape's structure (ruggedness) and the specific type of errors present.

Methodology: SPO Framework

The authors introduce SPO (Stochastic Prompt Optimization), a framework formalizing APO as stochastic hill climbing over a structured prompt space. The core loop generates $Q$ candidate prompts per iteration and adopts the best one only if it strictly improves upon the incumbent (monotonic selection).

The paper compares three strategies of increasing sophistication within this framework:

1. SPO-RS (Residual Search)

• Mechanism: Generates $Q$ candidates via high-temperature ($\tau=0.9$) LLM sampling.
• Input: Conditioned on the current best prompt and a summary of its errors.
• Nature: Mirrors error-informed refinement but relies on stochastic perturbation rather than structured operators.

2. SPO-GA (Genetic Algorithm)

• Mechanism: Applies evolutionary operators (crossover and mutation) to a population of top-$P$ prompts.
• Input: Crossover combines two parents and their error summaries; mutation targets improvements on a single parent.
• Nature: Follows the "LLM-as-evolutionary-operator" paradigm, trading some diversity for targeted improvement (lower temperature $\tau=0.7$).

3. SAGE (Agent-Guided Exploration)

• Mechanism: A multi-agent pipeline where agents write and execute diagnostic code to inform prompt edits.
• Workflow:
  1. Analyzer: Runs scripts on evaluation results to surface $H$ evidence-backed hypotheses about error patterns.
  2. Orchestrator: Triages hypotheses into $I$ investigation directions.
  3. Investigators: Deep-dive in parallel to verify hypotheses with exact counts and trace analysis, returning implementation-ready fixes.
  4. Generators: Produce revised prompts based on investigation reports.
• Key Distinction: Unlike prior work where code constructs artifacts, SAGE uses code execution for statistical diagnosis (clustering errors, running statistical tests, identifying overrepresented failure patterns) within a fixed procedure.

Experimental Setup

The framework was evaluated on three benchmarks and one production deployment:

• XBRL Formula: Financial reasoning (500 train / 200 test).
• FiNER: Financial Named Entity Recognition (1,000 train / 441 test).
• AppWorld: Autonomous agent tasks involving API understanding and code generation.
• Production Deployment: "Ash," a mental-health chatbot by Slingshot AI, optimized under a continuous optimization paradigm.

Baselines: The methods were compared against Base LLM, In-Context Learning (ICL), MIPROv2, GEPA, Dynamic Cheatsheet, and ACE offline. The target LLM was DeepSeek-V3.1; the meta-model proposing edits was Claude Sonnet 4.6.

Key Results

Benchmark Performance

No single strategy dominated across all tasks; effectiveness depended on the interaction of landscape structure and error type:

• Formula (Rugged, Cascading Errors): SAGE led, as its analytical depth was rewarded for diagnosing cascading reasoning errors.
• FiNER (Smooth Landscape): SAGE achieved the highest training accuracy, but simpler strategies (SPO-GA) generalized better to the test set. The landscape was smooth (correlated over large distances), making deep analysis less critical for generalization.
• AppWorld (Rugged, Procedural Errors): All SPO variants beat baselines. SAGE achieved the highest training accuracy, but validation accuracy oscillated due to the small evaluation set. SPO-GA achieved the highest test accuracy, suggesting that for procedural, per-task errors, simpler search is sufficient.

Landscape Analysis

Using semivariograms from geostatistics, the authors quantified landscape ruggedness:

• Formula and AppWorld: Decorrelated within small semantic neighborhoods (rugged).
• FiNER: Stayed correlated over $\sim4\times$ the distance (smooth).
• Finding: Ruggedness alone does not predict the winning strategy. The decisive factor is error structure: cascading reasoning errors benefit from SAGE's root-cause analysis, while procedural errors yield to simpler search.

Production Deployment (Mental Health Chatbot)

SAGE was deployed on the "Ash" chatbot for eight continuous optimization cycles.

• Process: Each cycle involved deploying the best prompt, running SAGE on collected conversations, A/B testing candidates, and promoting the winner.
• Outcome: Seven of eight cycles produced a positive winning arm. While individual cycles were often statistically insignificant (noisy), chaining the per-cycle deltas resulted in a cumulative +29.4% relative improvement in next-day (D1) retention with nonparametric significance.
• Significance: This demonstrates that individually noisy A/B tests can compound into a statistically robust gain when coupled with continuous optimization.

Contributions and Significance

The paper claims three primary contributions:

1. Black-box Optimization Framework: SPO formalizes APO as noisy black-box search over a structured landscape, providing a controlled ablation to isolate the value of analytical depth and exploration diversity.
2. Diagnostic Code Execution: SAGE is the first APO framework where code execution serves statistical diagnosis (analyzing error patterns) rather than procedural artifact construction or LLM-only reasoning.
3. Production Deployment: The paper introduces a continuous optimization paradigm for open-ended dialogue. It demonstrates that coupling qualitative diagnosis (via agents) with quantitative validation (via A/B testing) allows for effective optimization in domains lacking crisp correctness signals (like mental health), where traditional benchmarks fail.

The authors argue that this "mixed qualitative–quantitative agentic optimization" is the key to improving open-ended task-oriented dialogue systems where correctness cannot be defined in advance. They note limitations, including the reliance on automated evaluation functions, potential distribution shifts in continuous optimization, and the bounded novelty of agent-driven refinement (which refines existing behaviors rather than inventing entirely new ones without external direction).