# SAGE: Stochastic Prompt Optimization via Agent-Guided Exploration

arXiv: https://arxiv.org/abs/2606.18902 · HTML: https://mlsanity.com/paper/2606.18902/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 17 Jun 2026.

## Builds on (most cited first, 16 of 16)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [Quantifying Language Models' Sensitivity to Spurious Features in Prompt Design or: How I learned to start worrying about prompt formatting](https://mlsanity.com/paper/2310.11324/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents](https://mlsanity.com/paper/2407.18901/) (2024)
- [Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs](https://mlsanity.com/paper/2406.11695/) (2024)
- [Dynamic Cheatsheet: Test-Time Learning with Adaptive Memory](https://mlsanity.com/paper/2504.07952/) (2025)
- [A Systematic Survey of Automatic Prompt Optimization Techniques](https://mlsanity.com/paper/2502.16923/) (2025)
- [Meta Context Engineering via Agentic Skill Evolution](https://mlsanity.com/paper/2601.21557/) (2026)
- [Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimization](https://mlsanity.com/paper/2406.15708/) (2024)
- [Shrinkage Estimators in Online Experiments](https://mlsanity.com/paper/1904.12918/) (2019)
- [Textual Gradients are a Flawed Metaphor for Automatic Prompt Optimization](https://mlsanity.com/paper/2512.13598/) (2025)
- [Engagement Phenotypes for a Sample of 102,684 AI Mental Health Chatbot Users and Dose-Response Associations with Clinical Outcomes](https://mlsanity.com/paper/2605.00275/) (2026)
- [Fine-tuning LLMs for Passive Depression Severity Estimation from AI Mental Health Dialogue](https://mlsanity.com/paper/2606.17973/) (2026)

## Abstract (arXiv)

Context engineering has emerged as a primary lever for improving AI systems without parameter updates. Recent work showing that textual gradients do not function as real gradients motivates treating automatic prompt optimization (APO) as black-box search. We introduce SPO (Stochastic Prompt Optimization), a framework for stochastic search over prompt space, and compare three strategies of increasing sophistication: error-informed random search, a genetic algorithm with evolutionary operators, and SAGE (SPO via Agent-Guided Exploration), a multi-agent pipeline with diagnostic code execution. Across three benchmarks, no single strategy dominates; effectiveness depends on the interaction of landscape structure with error type. We further deploy SAGE on a mental-health chatbot under a continuous optimization paradigm, where it compounds eight cycles of individually-noisy A/B tests into a statistically robust gain in next-day retention. We argue that coupling qualitative diagnosis with quantitative validation is what makes agentic optimization effective for open-ended task-oriented dialogue.