# STEVE: Stabilizing Textual Gradient-Based Prompt Optimization via Error-Driven Refinement and Regularized Verification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 49 references that are in the map.
- First posted on arXiv 20 Sep 2026.

## Builds on (most cited first, 30 of 34)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [LIMA: Less Is More for Alignment](https://mlsanity.com/paper/2305.11206/) (2023)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Training Region-based Object Detectors with Online Hard Example Mining](https://mlsanity.com/paper/1604.03540/) (2016)
- [DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation](https://mlsanity.com/paper/2211.11501/) (2022)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Solving General Arithmetic Word Problems](https://mlsanity.com/paper/1608.01413/) (2016)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Language Model Cascades](https://mlsanity.com/paper/2207.10342/) (2022)
- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/2507.10485/) (2025)
- [RATT: A Thought Structure for Coherent and Correct LLM Reasoning](https://mlsanity.com/paper/2406.02746/) (2024)
- [Prompt Optimization via Adversarial In-Context Learning](https://mlsanity.com/paper/2312.02614/) (2023)
- [Fine-Grained Preference Optimization Improves Spatial Reasoning in VLMs](https://mlsanity.com/paper/2506.21656/) (2025)
- [SPRIG: Improving Large Language Model Performance by System Prompt Optimization](https://mlsanity.com/paper/2410.14826/) (2024)
- [REVOLVE: Optimizing AI Systems by Tracking Response Evolution in Textual Optimization](https://mlsanity.com/paper/2412.03092/) (2024)
- [Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning](https://mlsanity.com/paper/2310.12774/) (2023)
- [Towards Adversarially Robust Dataset Distillation by Curvature Regularization](https://mlsanity.com/paper/2403.10045/) (2024)
- [An Information-Theoretic Framework for Unifying Active Learning Problems](https://mlsanity.com/paper/2012.10695/) (2020)
- [Unveiling the Lexical Sensitivity of LLMs: Combinatorial Optimization for Prompt Enhancement](https://mlsanity.com/paper/2405.20701/) (2024)

## Abstract (arXiv)

Textual-gradient methods automate prompt optimization through natural-language feedback, but their iterative updates can be unstable. We identify two sources of this instability: noisy gradients produced from already-correct examples and over-specialization to hard cases that degrades performance on simpler inputs. We introduce STEVE, a stabilization framework with two coupled mechanisms. Error-Driven Refinement generates gradients only from incorrectly handled examples, concentrating updates on informative failures. Regularized Verification treats every update as provisional and accepts it only when improvement on hard cases does not cause unacceptable regression on a preservation set. Across ten reasoning benchmarks, three evaluator/optimizer models, and established prompt-optimization baselines, STEVE reduces degradation and produces more robust prompts. Additional evaluations with gpt-5.4-mini/gpt-5.4 on symbolic reasoning, GSM8K-Platinum, and DS-1000 show that these gains persist with newer models and larger test sets. STEVE therefore provides a practical way to improve the stability and effectiveness of textual-gradient prompt optimization.