No Loss, No Gain: Gated Refinement and Adaptive Compression for Prompt Optimization

We thank the reviewer for the encouraging feedback and inspiring questions.

Q1: More Comparative Experiments

We fully agree with your suggestions. In Appendix Table 6, we already report results across different base LLMs. Motivated by your suggestion, we further conduct two additional experiments: (1) evaluating the transferability of optimized prompts across base LLMs, and (2) analyzing the impact of different optimizer LLMs. Both experiments will be included in the appendix of the revised version.

(1) Transferability of Optimized Prompts Across Base LLMs

Our GRACE-optimized prompts exhibit a degree of generalizability but are most effective when applied to the same base LLM.

Since different base LLMs vary in architecture, pretraining data, and instruction tuning, we evaluate whether prompts optimized for one model generalize to others. Specifically, we optimize prompts using DeepSeek-V3-0324 as the target base LLM on five BBH tasks, then evaluate them on Llama-3.3-70B-Instruct and GPT-4.1 without further tuning.

Task (ZS) refers to the task's initial prompt. PromptAgent is a strong automatic prompt optimization bsaeline, and GRACE is our method.

In most cases, GRACE-optimized prompts outperform both the initial prompts and those optimized by PromptAgent, indicating their generalizability. However, the performance gains are highest on the model used for optimization (DeepSeek-V3) and generally smaller when transferred to other models. In a few instances (e.g., Epistemic on GPT-4.1), the optimized prompts even underperform compared to the initial ones. These results suggest that while GRACE prompts exhibit partial transferability, the optimized prompt is most effective when applied to the target base LLM.

(2) Impact of Different Optimizer LLMs

Frontier 'Thinking LLMs' are well-suited as the optimizer LLMs, and models with weaker analytical and reasoning abilities may struggle to effectively optimize prompts on some tasks.

Since the optimizer LLM plays a central role in our method, we assess how its ability affects performance. Besides our default optimizer (DeepSeek-R1), we experiment with another frontier thinking model (o3) and a general-purpose instruction-tuned model (Llama-3.3-70B-Instruct):

We observe three key findings:

1. GRACE consistently outperforms baselines across all settings, demonstrating its robustness and effectiveness regardless of the optimizer model used.

2. DeepSeek-R1 and o3 yield comparable results, suggesting that frontier models with strong reasoning capabilities are both viable and effective as optimizer LLMs.

3. When using Llama-3.3-70B-Instruct as the optimizer, GRACE and PromptAgent achieve performance comparable to that with other optimizers on most tasks. However, on some tasks such as Geometry, its performance is substantially worse, indicating that it fails to sufficiently optimize the prompt.

These results support our recommendation that the optimizer LLM be selected from models with strong analytical and reasoning abilities.

Q2: Integrating Techniques from Neural Network Optimization

Thank you for your insightful suggestions. Your analogy between prompt optimization and neural network training is closely aligned with the motivation behind our GRACE method. It has great potential to stabilize the prompt optimization process, but the practical applicability needs to be verified through empirical experiments.

Our work identifies a key issue in existing reflection-based prompt optimization methods: unregulated updates often lead to instability and convergence to suboptimal prompts. To address this, we draw a parallel between optimizing prompts based on error samples and gradient descent, and introduce three regularization-inspired designs: leveraging correct samples, selectively accepting updates, and adaptive compression. We agree that additional techniques from network training—such as limiting the magnitude of prompt edits (akin to lowering the learning rate), or reintroducing parts of the original prompt (akin to dropout)—may further enhance stability. Intuitively, these strategies could mitigate the issue of overly aggressive updates and help smooth the optimization trajectory. However, their effectiveness in the context of prompt optimization remains an open question and would require empirical validation. In our work, we experimented with several training-inspired strategies (e.g., momentum, adaptive learning rate), but found that only a subset transferred effectively. Many techniques, while conceptually appealing, are difficult to apply in practice due to the discrete nature of prompt space and the non-deterministic behavior of optimizer LLMs, which can instead introduce additional noise and instability. The current design of GRACE reflects the outcome of extensive empirical investigation and tuning.

We greatly appreciate your suggestions and plan to continue explore how optimization theory and techniques from neural network training can be systematically adapted to prompt optimization in future work.

We thank the reviewer for the insightful feedbacks. In the revised version, we will include the following experiments and analysis in the appendix.

Q1: Sensitivity to Meta-Prompt Design

We conduct sensitivity experiments by paraphrasing each key section of the meta-prompts, demonstrating the robustness of our GRACE method to variations in meta-prompt design.

Given the known sensitivity of LLMs to prompts, the design of meta-prompts can affect the effectiveness of prompt optimization. In constructing the meta-prompts, we first clarify the intended role of the optimizer LLM, then express it through clear, modular instructions. To evaluate the robustness of our method to meta-prompts, we paraphrase each key section of the meta-prompts used for optimization in Tabel 11 and compression in Table 12. For each section, we create 5 paraphrased variants and evaluate performance on 5 tasks from the BBH benchmark, reporting the mean and 95% confidence interval per task.

(1) The meta-prompt for optimization consists of the following four components:

• Main Task (MT): Your task is to optimize the current prompt for a language model performing a specific task. The goal is to correct previously failed predictions while preserving the model’s correct behavior on already successful examples.
• Preserve Correctness (PC): Ensure the model, instructed by the optimized prompt, continues to predict correct answers for all successful examples. In addition to prediction correctness, maintain the model’s original correct solutions and response for these cases as much as possible.
• Refine to Fix Errors (FE): For failed examples, attempt to correct them by refining the prompt’s instructions — for example, by adding clearer or more complete guidance. Any new content should integrate naturally with the current prompt and form a coherent task instruction. Avoid special-case logic, examples, or instructions targeted at individual cases.
• Additional Guidelines (AG): - Prompt modifications should always aim to preserve model's correct behavior on successful examples. ...

Performance with paraphrased versions of each component is shown below:

\\begin{array}{l l | c c c c c c} & \text{Method} & \text{Geometry} & \text{Translation} & \text{Snarks} & \text{Movie} & \text{Epistemic} & \text{Avg.} \\\\ \\hline & \\text{GRACE} & 97.00 & 84.29 & 94.74 & 97.14 & 97.50 & 94.13 \\\\ & \\text{MT} & 97.00 (0.71) & 84.29 (1.51) & 94.32 (1.60) & 97.14 (0.51) & 97.45 (0.37) & 94.04 \\\\ & \\text{PC} & 96.40 (1.39) & 84.57 (1.26) & 94.95 (0.47) & 96.86 (0.39) & 97.65 (0.29) & 94.09 \\\\ & \\text{FE} & 97.00 (1.00) & 83.57 (1.34) & 94.95 (1.15) & 96.86 (0.39) & 97.35 (0.60) & 93.95 \\\\ & \\text{AG} & 96.90 (0.74) & 84.00 (1.40) & 94.32 (1.49) & 97.14 (0.51) & 97.25 (0.40) & 93.92 \\\\ \\end{array}

(2) The meta-prompt for compression contains two main components:

• Main Task (MT): The prompt may have accumulated redundant, overly specific, or ineffective wording across previous iterations. Your goal is to ...
• Additional Guidelines (AG): Eliminate instructions that are verbose, ambiguous, or unlikely to generalize ...

Performance with paraphrased compression prompts is shown below:

\\begin{array}{l l | c c c c c c} & \text{Method} & \text{Geometry} & \text{Translation} & \text{Snarks} & \text{Movie} & \text{Epistemic} & \text{Avg.} \\\\ \\hline & \\text{GRACE} & 97.00 & 84.29 & 94.74 & 97.14 & 97.50 & 94.13 \\\\ & \\text{MT} & 97.00 (0.50) & 84.14 (1.28) & 94.53 (1.56) & 97.00 (0.78) & 97.40 (0.52) & 94.01 \\\\ & \\text{AG} & 97.29 (1.64) & 84.00 (0.96) & 94.74 (1.49) & 97.28 (0.32) & 97.55 (0.33) & 94.17 \\\\ \\end{array}

Across all paraphrased variants, performance remains highly stable with minimal variance, demonstrating our method's strong robustness to variations in meta-prompts. In addition, this finding aligns with our observations in search-based prompt optimization methods, where capable LLMs are often insensitive to minor phrasing variations when the core intent is preserved.

Q2: Additional Experimental Tasks

We conduct experiments on two widely-used summarization tasks, where GRACE also demonstrates significant performance improvements over other methods.

Our original experiments demonstrate the effectiveness of our method on complex reasoning, domain-specific, and natural language understanding tasks, which are the most common and standard benchmark tasks for automatic prompt optimization methods. Notably, tasks such as BBH and MedQA can be categorized as question answering, as they involve answering explicit questions based on given options. To further demonstrate the broader applicability of our method, we evaluate it on two summarization tasks: the Reddit TIFU dataset [1] and the Amazon Fine Food Reviews dataset [2]. Task instructions are sourced from Super-NaturalInstructions [3], and performance is measured using Rouge-L.

\\begin{array}{l l | c c c} & \\text{Method} & \\text{Reddit} & \\text{Amazon} & \\text{Avg.} \\\\ \\hline & \\text{Task (ZS)} & 12.21 & 16.78 & 14.50 \\\\ & \\text{Task (FS)} & 12.64 & 18.52 & 15.58 \\\\ \\hline & \\text{EvoPrompt} & 13.24 & 19.24 & 16.24 \\\\ & \\text{OPRO} & 13.13 & 20.35 & 16.74 \\\\ & \\text{APO} & 14.33 & 21.45 & 17.89 \\\\ & \\text{PromptAgent} & 16.29 & 21.29 & 18.79 \\\\ & \\text{GRACE} & **17.60** & **23.76** & **20.68** \\\\ \\end{array}

Task (ZS) is the initial prompt. As shown, GRACE achieves the highest performance across both datasets, demonstrating its effectiveness on summarization tasks and supporting its generalizability beyond classification and reasoning tasks.

[1] Kim et al.; "Abstractive Summarization of Reddit Posts with Multi-level Memory Networks"; NAACL 2019.

[2] https://www.kaggle.com/datasets/snap/amazon-fine-food-reviews

[3] Wang et al.; "Super-NaturalInstructions: Generalization via Declarative Instructions on 1600+ NLP Tasks"; EMNLP 2022.

Thank you for your valuable reviews and suggestions. In the revised version, we will include more ablation studies on hyperparameters and further clarify how the hyperparameters are determined in the appendix. Additionally, we will expand the limitation section to better define the scope of applicability of our method.

Q1: Hyper-Parameter Ablation and Selection

The hyperparameters we select are based on extensive empirical results, balancing efficiency and performance, and are suitable for a wide range of tasks. Our experimental results show that, compared to existing methods, our approach achieves significant performance improvements with much lower overhead.

Our GRACE method involves three key hyper-parameters: (1) the number of correct and incorrect samples used per update, denoted as $\left|S_t'\right|$ and $\left|F_t'\right|$, (2) the maximum number of optimization steps $T$, and (3) the number of consecutive rejections $K$ required to trigger compression.

(1) We choose $\left|S_t'\right| = \left|F_t'\right| = 3$, as it provides the most effective update signal. The comparison experiments and analysis can be found in Figures 5.a and 6.

(2) We choose $T = 80$, which provides optimal performance for most tasks, while achieving a balance between performance and cost. Increasing $T$ generally improves performance, but the gains diminish. Additionally, computational cost and resource requirements grow linearly with $T$. Below is the performance of GRACE with different values of $T$.

\\begin{array}{l l | c c c c c c} & \text{Method} & \text{Geometry} & \text{Translation} & \text{Snarks} & \text{Movie} & \text{Epistemic} & \text{Avg.} \\\\ \\hline & \\text{T=40} & 91.00 & 82.96 & **94.74** & 92.86 & 91.25 & 90.56 \\\\ & \\text{T=60} & 93.50 & 83.71 & **94.74** & 94.29 & 95.70 & 92.39 \\\\ & \\text{T=80} & 97.00 & 84.29 & **94.74** & **97.14** & **97.50** & 94.13 \\\\ & \\text{T=100} & **97.50** & 84.29 & **94.74** & **97.14** & **97.50** & 94.23 \\\\ & \\text{T=120} & **97.50** & **85.00** & **94.74** & **97.14** & **97.50** & **94.38** \\\\ & \\text{T=140} & **97.50** & **85.00** & **94.74** & **97.14** & **97.50** & **94.38** \\\\ \\end{array}

As shown, $T=80$ achieves the best results on 3 tasks and near-optimal performance on the remaining 2. Further increasing $T$ yields minimal improvements but incurs a linear increase in cost. Thus, to balance performance and efficiency, we use $T=80$ as the default. Additionally, we observe that when no improvement is seen over 20 consecutive steps, further iterations rarely help. Therefore, on new tasks, we recommend setting $T = 80$, possibly combined with an early stopping criterion of 20 stagnant steps.

(3) We select $K = 5$, as it provides optimal performance across most tasks.

\\begin{array}{l l | c c c c c c} & \text{Method} & \text{Geometry} & \text{Translation} & \text{Snarks} & \text{Movie} & \text{Epistemic} & \text{Avg.} \\\\ \\hline & \\text{K=3} & 91.50 & 81.43 & 93.68 & 94.29 & 93.00 & 90.78 \\\\ & \\text{K=4} & 97.00 & **84.29** & **94.74** & **97.14** & 96.25 & 93.88 \\\\ & \\text{K=5} & 97.00 & **84.29** & **94.74** & **97.14** & **97.50** & **94.13** \\\\ & \\text{K=6} & **97.50** & 83.57 & **94.74** & 96.43 & 95.50 & 93.55 \\\\ & \\text{K=7} & 94.00 & 84.14 & **94.74** & **97.14** & 91.25 & 92.25 \\\\ \\end{array}

We observe that both smaller and larger values of $K$ lead to decreased performance. A small $K$ may trigger premature compression before sufficient optimization has been explored, destabilizing the optimization process. On the other hand, a large $K$ may provide more optimization opportunities but could also waste resources, reducing the number of effective optimization in a limited number of iterations, leading to lower final performance. Therefore, we suggest set $K = 5$ to achieve a balance between exploration and exploitation in the prompt optimization space.

In summary, GRACE’s hyper-parameters are chosen to ensure strong and stable performance across diverse tasks, and we provide concrete recommendations (e.g., $\left|S_t'\right| = \left|F_t'\right| = 3$, $T=80$, $K=5$) for adapting to new datasets.

Q2: Limitations on Domain-Specialized Tasks

We have demonstrated that GRACE achieves strong performance on complex reasoning, natural language understanding, and domain-specific tasks, significantly surpassing existing methods in both efficiency and effectiveness. However, upon further analysis, we find that the performance gains on tasks requiring specialized domain knowledge are relatively limited. As shown in Table 1, the performance improvement on domain-specific tasks, particularly the MedQA dataset, is modest. Our failure case analysis reveals that certain samples in the MedQA dataset require highly specialized medical knowledge, which both the optimizer and base LLMs lack. This indicates that our method struggles to effectively address such cases. It is important to emphasize that this limitation is not unique to our method but reflects a gap in current automatic prompt optimization approaches, which all rely solely on the capabilities of the optimizer and base LLMs.

Improving the generalizability and practicality of APO methods to better handle domain-specific knowledge is an important direction of our future research. To address this, we are exploring the integration of retrieval-augmented generation (RAG) methods. By enabling the optimizer LLMs to access domain-specific knowledge bases, we can incorporate missing domain knowledge into the prompts.

We thank the reviewer for the encouraging feedback and incisive reviews. In the revised version, we will include the relevant experiments in the appendix.

Q1: Computing Time

The total computing time scales approximately linearly with the number of search size and the reported costs.

The total computing time can be decomposed into two components: (1) the time spent by the optimizer LLM to update prompts, and (2) the time spent by the base LLM to evaluate these prompts. Let $N$ denote the number of search sizes, and $T$ the total computing time. The approximate relationships are:

$T_{EvoPrompt}=N_1 \cdot T_{opt1} + N_1 \cdot T_{base}$

$T_{OPRO}=N_1 \cdot T_{opt2} + N_1 \cdot T_{base}$

$T_{APO}= N_1 \cdot T_{opt2} \cdot 2 + N_1 \cdot T_{base} \cdot \alpha_{UCB}$

$T_{PromptAgent}= N_1 \cdot T_{opt2} \cdot 2 + N_1 \cdot T_{base}$

$T_{GRACE(ours)} =N_2 \cdot T_{opt2} + N_2 \cdot T_{base}$

In the first half of the optimization time, $T_{\text{opt1}}$ refers to the time for lightweight optimization (e.g., paraphrasing), while $T_{\text{opt2}}$ involves more complex optimization using additional context such as failure cases or optimization history. APO and PromptAgent incur twice the optimization time, as they require generating suggestions followed by prompt updates. In contrast, GRACE directly optimizes prompts based on correct and incorrect examples, avoiding this overhead. Notably, the search sizes for GRACE, $N_2 = 80$, are significantly smaller than $N_1 \approx 300$ for other methods.

In the second half of the evaluation time, $T_{\text{base}}$ denotes the time to evaluate a prompt on the validation set, which is nearly identical across methods. APO reduces evaluations by a factor of $\alpha_{\text{UCB}} \approx \frac{1}{3}$ via a UCB algorithm. In practice, we observe that $T_{\text{base}} > T_{\text{opt2}} > T_{\text{opt1}}$, meaning evaluation constitutes the main portion of overall computing time.

Thus, computing time can be directly estimated from the number of search sizes, though the per-step compute varies across methods.

Likewise, total cost $C$ scales approximately linearly with the search size $N$ and follows a similar formulation.

$C_{EvoPrompt}=N_1 \cdot C_{opt1} + N_1 \cdot C_{base1}$

$C_{OPRO}=N_1 \cdot C_{opt2} + N_1 \cdot C_{base1}$

$C_{APO}= N_1 \cdot C_{opt2} \cdot 2 + N_1 \cdot C_{base2} \cdot \alpha_{UCB}$

$C_{PromptAgent}= N_1 \cdot C_{opt2} \cdot 2 + N_1 \cdot C_{base2}$

$C_{GRACE(ours)} =N_2 \cdot C_{opt2} + N_2 \cdot C_{base2}$

Given approximately constant per-call cost and latency, we can estimate computing time as: $T_{method} \approx C_{method} \cdot \frac{T_{opt} + T_{base}}{C_{opt} + C_{base}}$

In summary, although implementation details (e.g., API latency, meta-prompt design, hyperparameters) can affect the exact computing time and cost, the general trends and relationships hold. GRACE consistently achieves lower compute and cost primarily by substantially reducing the number of search sizes.

Q2: Illustrative Examples

To facilitate a clearer comparison, we will include illustrative examples of the prompt optimization process for OPRO (as a representative search-based method) and APO (as a representative reflection-based method).

Below is the process of OPRO on the CB task.

OPRO generates 15 new candidates per step based on top-performing prompts. The prompts shown are the best examples at the selected steps. As observed, the generated candidates preserve the original semantics, resulting in limited diversity and slow improvements.

Below is the process of APO on the CB task.

We highlight the case-specific additions in bold. In the first step, APO primarily adds general guidance with some specific details, resulting in a performance gain. However, later revisions tend to focus solely on narrowly tailored logic or memorized phrasings tied to individual examples, which fail to generalize and can even degrade performance.

We hope these process illustrations will further clarify the optimization behaviors and help highlight how GRACE achieves more efficient and effective improvements.