Projection-Free Evolution Strategies for Continuous Prompt Search

Yu Cai; Canxi Huang; Xiaoyu He

cs.CLMar 14, 2026

Projection-Free Evolution Strategies for Continuous Prompt Search

Authors: Yu Cai, Canxi Huang, Xiaoyu He

Organizations: Y. Cai, C. Huang and X. He are with the School of Software Engineering, Sun Yat-sen University, Zhuhai, China

Abstract

Continuous prompt search offers a computationally efficient alternative to conventional parameter tuning in natural language processing tasks. Nevertheless, its practical effectiveness can be significantly hindered by the black-box nature and the inherent high-dimensionality of the objective landscapes. Existing methods typically mitigate these challenges by restricting the search to a randomly projected low-dimensional subspace. However, the effectiveness and underlying motivation of the projection mechanism remain ambiguous. In this paper, we first empirically demonstrate that despite the prompt space possessing a low-dimensional structure, random projections fail to adequately capture this essential structure. Motivated by this finding, we propose a projection-free prompt search method based on evolutionary strategies. By directly optimizing in the full prompt space with an adaptation mechanism calibrated to the intrinsic dimension, our method achieves competitive search capabilities without additional computational overhead. Furthermore, to bridge the generalization gap in few-shot scenarios, we introduce a confidence-based regularization mechanism that systematically enhances the model's confidence in the target verbalizers. Experimental results on seven natural language understanding tasks from the GLUE benchmark demonstrate that our proposed approach significantly outperforms existing baselines.

Figures & tables

Panel of Figure 1 — Fig. 1: Intrinsic dimension estimation on seven GLUE tasks. We report the estimated dimension (y-axis) across continuous prompt lengths $l\in\{5,10,20,40,50,80,100\}$ (x-axis). Different colors correspond to the neighborhood size $k\in\{5,10,20,30,40,50\}$ used in the maximum likelihood estimation.

	$f_{\mathrm{PS}}(x_{*})$	$f_{\mathrm{BBT}}(y_{*})$	$\gamma_{\text{OP}}$	$\gamma_{\text{PI}}$
MRPC	0.0250	0.0413	1.0072	1.4175
MNLI	0.2479	0.2738	0.9919	1.4001
QQP	0.0073	0.0310	0.9665	1.3856
SST-2	0.0051	0.0100	0.9590	1.3843
RTE	0.0611	0.0845	0.9632	1.3864
CoLA	0.0416	0.0698	0.9698	1.3878

TABLE I : Comparison of training loss on the evaluated tasks.

f_{\mathrm{PS}}(x_{*})

denotes the approximate optimal value in the full prompt space, while

f_{\mathrm{BBT}}(y_{*})

corresponds to that in the random subspace.

Panel of Figure 3 — Fig. 2: Median performance on training data over 5 runs with different random seeds. Algorithms include (1+1)-ES, (1+1)-ES-ID, SaES, SaES-ID with projection-free and BBT with subspace projection. The x-axis denotes function evaluations, while the y-axis represents the loss function value.

Algorithm	MRPC	MNLI	QQP	SST-2	RTE	CoLA	QNLI	Time/FE
Algorithm	F1	Acc	F1	Acc	Acc	MCC	Acc	s
ManualPrompt	$77.69\phantom{{}_{0.00}}$	$40.80\phantom{{}_{0.00}}$	$29.37\phantom{{}_{0.00}}$	$78.10\phantom{{}_{0.00}}$	$50.18\phantom{{}_{0.00}}$	$0.79\phantom{{}_{0.00}}$	$48.70\phantom{{}_{0.00}}$	-
ICL	$48.13_{12.0}$	$47.10_{3.14}$	$45.73_{7.01}$	$69.36_{6.22}$	$54.15_{2.79}$	$-0.54_{2.67}$	$52.06_{1.24}$	-
BDPL †	$78.10_{3.70}$	$42.50_{1.80}$	$56.40_{1.90}$	$87.60_{2.10}$	$53.50_{0.90}$	$4.60_{1.20}$	$53.10_{1.10}$	-
RLPrompt †	$68.90_{2.10}$	$42.80_{3.20}$	$53.70_{2.20}$	$88.40_{1.90}$	$51.80_{1.80}$	$5.00_{1.10}$	$52.60_{1.40}$	-
BBT	$77.33_{0.00}$	$46.48_{1.16}$	$51.09_{2.38}$	$88.03_{2.02}$	$54.30_{1.66}$	$3.94_{1.42}$	$54.30_{1.23}$	0.1442

TABLE II : Performance comparison on seven GLUE tasks. For our proposed projection-free methods with the CR term, results are reported using the optimal

\beta

. “Time/FE (s)” represents the average execution time per function evaluation. The results marked with † are cited directly from [ 16 ] . Subscripts denote standard deviations.

Algorithm	MRPC	MNLI	QQP	SST-2	RTE	CoLA	QNLI
(1+1)-ES-ID-CR β=0.01	$77.33_{0.00}$	$46.42_{1.28}$	$38.59_{5.92}$	$86.88_{1.48}$	$54.15_{1.60}$	$-0.73_{1.78}$	$59.80_{2.86}$
(1+1)-ES-ID-CR β=0.1	$77.33_{0.00}$	$46.50_{1.22}$	$40.84_{5.50}$	$88.65_{1.49}$	$53.72_{1.76}$	$0.74_{2.29}$	$58.08_{2.65}$
(1+1)-ES-ID-CR β=1	$77.76_{0.64}$	$49.04_{1.43}$	$53.32_{1.39}$	$89.66_{0.98}$	$56.10_{1.16}$	$8.32_{1.81}$	$53.24_{2.46}$
(1+1)-ES-ID-CR β=10	$81.50_{0.10}$	$48.72_{1.18}$	$54.33_{0.74}$	$79.50_{2.05}$	$54.73_{1.42}$	$6.16_{1.79}$	$52.60_{1.81}$
(1+1)-ES-ID-CR β=100	$79.71_{1.95}$	$48.62_{1.12}$	$54.37_{0.84}$	$78.03_{1.14}$	$53.79_{0.65}$	$5.93_{1.48}$	$51.00_{1.72}$
SaES-ID-CR β=0.01	$77.33_{0.00}$	$46.42_{1.28}$	$48.52_{3.96}$	$88.42_{2.04}$	$54.22_{1.92}$	$2.57_{1.87}$	$59.86_{1.37}$

TABLE III : Sensitivity analysis of the CR coefficient

\beta

. We report the mean and standard deviation of performance over 5 runs.

Panel of Figure 6 — Fig. 3 : Sensitivity analysis of intrinsic dimension $\tilde{d}$ . We report the mean and standard deviation of performance over 5 runs.

Task	BBT	(1+1)-ES-ID-CR	SaES-ID-CR
MRPC	$57.33_{8.04}$	$74.00_{9.47}$	$80.18_{2.26}$
MNLI	$32.92_{1.33}$	$30.70_{1.16}$	$33.54_{2.40}$
QQP	$50.41_{3.28}$	$48.02_{6.55}$	$54.77_{3.22}$
SST-2	$81.22_{3.15}$	$71.88_{3.86}$	$86.17_{1.84}$
RTE	$56.53_{1.75}$	$54.95_{2.78}$	$57.76_{1.66}$
CoLA	$10.30_{0.94}$	$11.42_{4.43}$	$8.40_{0.60}$

TABLE IV : Performance comparison on GLUE tasks using the causal OPT-6.7B model.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Template	Verbalizers
MRPC	$s_{1}$ ? [MASK], $s_{2}$ .	yes / no
MNLI	$s_{1}$ ? [MASK], $s_{2}$ .	yes / maybe / no
QQP	$s_{1}$ [MASK], $s_{2}$ .	yes / no
SST-2	$s_{1}$ . It was [MASK].	great / terrible
RTE	$s_{1}$ ? [MASK], $s_{2}$ .	yes / no
CoLA	$s_{1}$ Correct? [MASK].	yes / no

Appendix

TABLE V : Templates and label descriptions for the mask-filling RoBERTa-Large model.

Dataset	Template	Verbalizers
MRPC	input: sentence one: $s_{1}$ sentence two: $s_{2}$ equivalent? \n output:	yes / no
MNLI	input: sentence one: $s_{1}$ sentence two: $s_{2}$ entailment? \n output:	yes / maybe / no
QQP	input: sentence one: $s_{1}$ sentence two: $s_{2}$ equivalent? \n output:	yes / no
SST-2	input: $s_{1}$ It was \n output:	great / terrible
RTE	input: sentence one: $s_{1}$ sentence two: $s_{2}$ entailment? \n output:	yes / no
CoLA	input: $s_{1}$ correct? \n output:	yes / no

Appendix

TABLE VI : Templates and Label Descriptions for the Causal OPT-6.7B Model

Algorithm	MRPC	MNLI	QQP	SST-2	RTE	CoLA	QNLI
ZOSGD-CR β=0.01	$77.33_{0.00}$	$46.42_{1.28}$	$44.74_{4.27}$	$86.63_{0.40}$	$53.65_{1.24}$	$-0.25_{1.48}$	$58.58_{1.90}$
ZOSGD-CR β=0.1	$77.58_{0.51}$	$46.54_{1.09}$	$48.47_{2.54}$	$87.68_{0.52}$	$54.66_{2.59}$	$1.49_{2.41}$	$59.48_{1.85}$
ZOSGD-CR β=1	$79.37_{1.60}$	$46.42_{1.28}$	$54.04_{1.11}$	$89.29_{1.07}$	$54.30_{0.54}$	$3.68_{2.00}$	$51.66_{1.01}$
ZOSGD-CR β=10	$77.95_{1.23}$	$46.60_{1.38}$	$48.63_{7.77}$	$84.61_{2.17}$	$53.86_{0.27}$	$1.91_{1.64}$	$50.46_{1.38}$
ZOSGD-CR β=100	$77.46_{0.27}$	$46.42_{1.28}$	$48.23_{8.85}$	$82.39_{4.15}$	$53.57_{0.43}$	$3.45_{3.85}$	$51.18_{1.76}$
BDPL (Ours)	$68.63_{4.95}$	$25.76_{1.97}$	$52.40_{1.21}$	$83.85_{1.57}$	$52.78_{2.38}$	$1.95_{4.20}$	$54.35_{1.40}$

Appendix

TABLE VII : Additional experimental results for ZOSGD-CR, BDPL, and RLPrompt. We report the mean and standard deviation over 5 independent runs.

	$f_{\mathrm{PS}}(x_{*})$	$f_{\mathrm{BBT}}(y_{*})$	$\gamma_{\text{OP}}$	$\gamma_{\text{PI}}$
MRPC	0.0250	0.0413	1.0072	1.4175
MNLI	0.2479	0.2738	0.9919	1.4001
QQP	0.0073	0.0310	0.9665	1.3856
SST-2	0.0051	0.0100	0.9590	1.3843
RTE	0.0611	0.0845	0.9632	1.3864
CoLA	0.0416	0.0698	0.9698	1.3878

Appendix

TABLE VIII : Comparison of training loss on the evaluated tasks.

f_{\mathrm{PS}}(x_{*})

denotes the approximate optimal value in the full prompt space, while

f_{\mathrm{BBT}}(y_{*})

corresponds to that in the random subspace.

Task	Algorithm	Metric (%)	$\mathcal{P}$	$\mathcal{R}$
MRPC	SaES-ID	$76.68_{0.00}$	0.0017	302.23
MRPC	SaES-ID-CR	$81.26_{0.11}$	0.4710	16.80
MNLI	SaES-ID	$46.40_{1.64}$	0.0099	221.48
MNLI	SaES-ID-CR	$51.84_{1.37}$	0.0496	19.50
QQP	SaES-ID	$49.51_{3.21}$	0.0017	203.45
QQP	SaES-ID-CR	$53.28_{2.93}$	0.3021	3.25

Appendix

TABLE IX : Impact of Confidence Regularization on task performance and diagnostic metrics.

Automatic Prompt Optimization

Automatic prompt optimization uses model or task feedback to revise instructions for stronger, more reliable language-model performance.

See all 103 papers

Feb 3, 2026

GFlowPO: Generative Flow Network as a Language Model Prompt Optimizer

Finding effective prompts for language models (LMs) is critical yet notoriously difficult: the prompt space is combinatorially large, rewards are sparse due to expensive target-LM evaluation. Yet, existing RL-based prompt optimizers often rely on on-policy updates and a meta-prompt sampled from a fixed distribution, leading to poor sample efficiency. We propose GFlowPO, a probabilistic prompt optimization framework that casts prompt search as a posterior inference problem over latent prompts regularized by a meta-prompted reference-LM prior. In the first step, we fine-tune a lightweight prompt-LM with an off-policy Generative Flow Network (GFlowNet) objective, using a replay-based training policy that reuses past prompt evaluations to enable sample-efficient exploration. In the second step, we introduce Dynamic Memory Update (DMU), a training-free mechanism that updates the meta-prompt by injecting both (i) diverse prompts from a replay buffer and (ii) top-performing prompts from a small priority queue, thereby progressively concentrating the search process on high-reward regions. Across few-shot text classification, instruction induction benchmarks, and question answering tasks, GFlowPO consistently outperforms recent discrete prompt optimization baselines.

Junmo Cho, Suhan Kim, Sangjune An +5

Korea Advanced Institute of Science and Technology (KAIST) · Korea University · Mila – Québec AI Institute

LLM Input Optimization

Ask PDF

Apr 12, 2024

Budgeted Prompt-Set Expansion and Refinement for Language Models via Simulation Optimization

A prompt is an instruction or description provided by the user to guide a generative language model toward outputs that meet application requirements. When these requirements change, existing prompts may need to be adapted and improved. Evaluating candidate prompts requires time and computational resources. We therefore study how to expand and refine an initial set of prompts under a limited evaluation budget through simulation optimization, aiming to maximize a pre-defined task score for a fixed language model. Specifically, we propose a two-stage framework. In the first stage, we expand the initial set of prompts into a finite candidate set, where each prompt is represented by a moderate-dimensional vector. In the subsequent stage of evaluation and selection, we construct a surrogate model of the score for moderate-dimensional vectors representing the prompts. We propose sequentially selecting prompts for evaluation using the constructed surrogate model. We prove the consistency of the sequential evaluation procedure in our framework. We further introduce a refinement procedure that uses the collected scores to search beyond the initial candidate set. We also conduct numerical experiments to demonstrate the advantages of our method over baseline prompt selection methods, with higher prompt scores, especially when the budget for calling language models to evaluate prompts is limited.

Haoting Zhang, Jinghai He, Rhonda Righter +1

Department of Industrial Engineering and Operations Research, University of California Berkeley

Prompt Optimization LLM Prompting LLM Input Optimization Surrogate-Assisted Optimization Stochastic Optimization

Ask PDF

Jun 9, 2026

APEX: Automated Prompt Engineering eXpert with Dynamic Data Selection

Large Language Models are highly sensitive to prompt formulation, necessitating automatic prompt optimization to unlock their full potential. While evolutionary algorithms have emerged as the dominant paradigm, they suffer from a critical bottleneck: data efficiency. Current methods treat the development dataset as a static benchmark, wasting significant compute budget on uninformative data. In this work, we introduce APEX (Automatic Prompt Engineering eXpert), a novel framework that optimizes the data usage alongside the prompt search. APEX dynamically stratifies the dataset into Easy, Hard, and Mixed tiers based on the optimization lineage. By prioritizing the Mixed tier, which identifies the data where the LLM has mixed performance, we identify two high-leverage subsets: the addressable frontier for generating informative mutations and the rank-sensitive frontier for distinguishing candidate quality. We evaluate APEX across three diverse benchmarks: IFBench, SimpleQA Verified, and FACTS Grounding. Under a fixed budget of 5,000 evaluation calls, due to its data efficiency, APEX outperforms the initial prompt by an average of 11.2% on Gemini 2.5 Flash and 6.8% on Gemma 3 27B, demonstrating that a data-centric approach is key to efficient and effective prompt optimization.

Fei Wang, Si Si, Cho-Jui Hsieh +1

Google · UCLA

Evolutionary Optimization LLM Prompting Automatic Prompt Optimization Prompt Optimization

Ask PDF

Abstract

Automatic Prompt Optimization

Explore similar work

GFlowPO: Generative Flow Network as a Language Model Prompt Optimizer

Budgeted Prompt-Set Expansion and Refinement for Language Models via Simulation Optimization

APEX: Automated Prompt Engineering eXpert with Dynamic Data Selection