PRESTO: Preimage-Informed Instruction Optimization for Prompting Black-Box LLMs
Authors: Jaewon Chu
Seunghun Lee
Hyunwoo J. Kim
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
Instruction Optimization
Primary area: deep_learning
TL;DR: Facilitate instruction optimization for black-box LLM by leveraging the preimage structure over the soft prompts and instructions.

Abstract: Large language models (LLMs) have achieved remarkable success across diverse domains, due to their strong instruction-following capabilities. This raised interest in optimizing instructions for black-box LLMs, whose internal parameters are inaccessible but popular for their strong performance and ease of use. Recent approaches leverage white-box LLMs to assist instruction optimization for black-box LLMs by generating instructions from soft prompts. However, white-box LLMs often map different soft prompts to the same instruction, leading to redundant queries to the black-box model. While previous studies regarded this many-to-one mapping as a redundancy to be avoided, we reinterpret it as useful prior knowledge that can enhance the optimization performance. To this end, we introduce PREimage-informed inSTruction Optimization (PRESTO), a novel framework that leverages the preimage structure of soft prompts to improve query efficiency. PRESTO consists of three key components: (1) score sharing, which shares the evaluation score with all soft prompts in a preimage; (2) preimage-based initialization, which select initial data points that maximize search space coverage using preimage information; and (3) score consistency regularization, which enforces prediction consistency within each preimage. By leveraging preimages, PRESTO observes 14 times more scored data under the same query budget, resulting in more efficient optimization. Experimental results on 33 instruction optimization tasks demonstrate the superior performance of PRESTO.

PRESTO: Preimage-Informed Instruction Optimization for Prompting Black-Box LLMs
Jaewon Chu
Seunghun Lee²*
Hyunwoo Kim
Korea University, ²KAIST
allonsy07@korea. ac. kr (11sshh319, hyunsoojkimm @kaist ac kr
Abstract
Large language models (LLMs) have achieved remarkable success across diverse domains, due to their strong instruction-followinn capabilities. This has led to increasing interest in optimizing instructions for black-box LLMs, whose inter- nal parameters are inaccessible but widely used due to their strong performance. To optimize instructions for black-box LLMs, recent methods employ white-box LLMs to generate candidate instructions from optimized soft prompts. However, white-box LLMs often map different soft prompts to the same instruction, leading to redundant queries. While previous studies regarded this many-to-one mapping as structure that hinders optimization efficiency, we reinterpret as a useful prior knowledge that can accelerate the optimization. To this end, we introduce PREimage-informet inSTruction Optimization (PRESTO), novel framework that leverages the preimage structure of soft prompts for efficient optimization. PRESTO consists of three key components: (1) score sharing, which shares the evaluation score with all soft prompts in preimage; (2) preimage-based initializa- tion, which selects initial data points that maximize search space coverage using preimage information; and (3) score consistency regularization, which enforces prediction consistency within each preimage. By leveraging preimages, PRESTO achieves the effect of effectively obtaining 14 times same query budget, resulting in more efficient optimization. Experimental re- sults 33 instruction optimization tasks demonstrate the superior performance of PRESTO. Code is available at httpp://gihub..om///laaaaaa
scored data under the
1
Introduction
Large language models (LLMs)) have demonstrated strong performance across a wide range do- mains [+5) This success is largely attributed to their impressive instruction-folloiing capabilities, which have led to growing interest discovering effective instructions enhance their perfor- mance 6 7. In particular, LLMs provided through APIs (i.e., black-box LLMs), such as GPT-4 (2), are widely used and show exceptionally strong performance. However, optimizing instructions for the black-box LLMs is challenging problem, since their internal parameters inaccessible. To tackle this challenge, recent studies have explored various strategies for optimizing instructions for black-box LLMs, without access to internal model parameters 13]
Recently, some studies [4 have leveraged open- LLMs (i.e., white-box LLMs) to assist instruction optimization for black-box L.Mss, demonstrating promising results and attracting growing interest. Specifically, these methods optimize soft prompt, which is taken as input to the white-box LLM. The optimization is performed using black-box optimization algorithms such as Bayesian Optimization
20 or Neural Bandits [1 22]. guided by a score predictor
WWrk done while Korca University. Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

10k
1000
9k
Preimage size
Count
200
6k
4.87
5K
0
20
40
60
80 100
soft prompts
instructions
Preimage index
(a)
(b)
Figure 1: Motivating observations illustrating the many-to-one mapping from soft prompts to
instructions in white-box LLM (LLaMA3.1-8) 1-8....88-Inssruee []]. Figure [ shows that the white-
LLM produces approximately 6,500 unique instructions from 10,000 distinct soft prompts. Figure presents the distribution of preimage sizes, displaying the top 100 largest preimages. 'he largest preimage contains more than 1,000 soft prompts, while the 100th largest has around 5. Both figures report the average experimental results over the instruction induction tasks used in Table
regression model, allowing the white-box LLM to generate effective instructions for black-box LLMs. However, as shown in Figure Ta white-box LLMs often generate identical instructions from distinct soft prompts. It leads to repeatedly querying soft prompts that yield the same outputs during the optimization process, which ultimately hinders the optimization process by reducing query efficiency, To avoid redundant queries, previous studies either sample soft prompts that are well-separated in the soft prompt space [16] or filter soft prompts that generate distinct instructions [15].
While previous studies have treated the generation of identical instructions from different soft prompts (i.e., many-to-one structure) as a redundancy that hinders optimization, we reinterpret this as a valuable structure that can facilitate the optimization process. Specifically, the set of soft prompts that generate the same instruction forms the preimage of that instruction under the white-box LLM. This preimage imposes a strong inductive bias over the search space: all soft prompts within preimage share the same objective function value. Since we follow previous settings [16] 15] that sample sufficiently large set of N soft prompts and search for the optimal solution within them, we not observe the full preimage, but only a subset of We refer to such subsets as preimages throughout the paper, and provide the size distribution of these preimages in Figure
Building this insight, we propose PRESTO, novel instruction optimization framework that explicitly leverages the many-to-one structure to facilitate instruction optimization for black-box LLMs. PRESTO consists of three components. First, we present the score-sharing method, where once the score is evaluated through the black-box LLM, it is shared with all soft prompts within a preimage. This effectively enlarges the amount of scored data without additional calls to the black-box LLM. Second, we introduce preimage-basee based initialization, where we select the initial soft prompts regarding the preimage information so that they cover the search space maximally, Finally, we propose score consistency regularization, which adds a regularization term to encourage the score predictor to predict identical scores for soft prompts within the same preimage. We evaluate the instruction optimization performance of PRESTO on 30 instruction induction tasks and three arithmetic reasoning tasks, and achieve state-of-the-art performance compared existing baselines.
The main contributions of our work are:
We reinterpret the many-to-one structure between the soft prompts and instruction, previously viewed as a challenge, as a rich informative structure that facilitates instruction optimization for black-box LLMs.
Leveraging this insight, introduce PRESTO, novel framework that consists of score sharing, preimage-base initialization, and score consistency regularization.
PRESTO achieves state-of-the-art performance across 30 instruction induction and arith- metic reasoning tasks.

---

2 Related Works
Instruction Optimization for Black-box LLMs Instruction optimization has been widely explored as way to improve the performance of large language models (LLMs) on downstream tasks [23 24] In particular, when using black-box LLMs such as GPT-4 (2] where access to model parameters is restricted, optimization methods rely on model outputs to guide the search for better instructions. Under this setting, various approaches have been proposed, including evolutionary algorithms [I LLM-driven vetaaoppimizztion [8] . and bandit-style or heuristic search methods [1312] These works demonstrate that instruction quality can be improved even without access to gradients or internal representations by querying the black-box model efficiently.
More recently, some methods [4H16] incorporate open-source white-box LLMs [1 18 25
to assist the optimization process. Rather than optimizing instruction texts directly, they optimize soft prompts, which are continuous embeddings that the white-box model maps into instructions. InstructZero [4] leveraged Bayesian Optimization (26-28] to search for the optimal soft prompts for black-box LLM. INSTINCT [6] leveraged NeuralUCB [2 with an LLM-based score predictor, which was the first to point out the many-to- too-ee schema and approached it indirectly by sampling soft prompts to be well sell-sepratee. And ZOPO [55] proposed zeroth-order optimization algorithm [29] for local search, which addresses this redundancy by simply discarding all but one soft prompt that produces the same instruction. In contrast, we retain all soft prompts by introducing preimages and facilitate the optimization.
3 Preliminaries
Problem Formulation Instruction optimization aims to find an instruction e that guides a language model to perform given task effectively. To be specifie, the goal is to find the instruction that maximizes the task-specific score function by guiding a black-box LLM fo to generate the correct answer y, which is formally given as:
o" arg max BLe.)eDD. v)), BEN
(1)
where Deal = (..,,,))) y: is a validation set, and Ω denotes the search space of instructions,
typically discrete sequence domain (e.g., natural language prompts token sequences). However, directly searching over discrete instruction sequences is challenging, as it constitutes a combinatorial optimization problem over the space of token configurations. To address this, InstructZero [14 reformulates the discrete instruction search as a continuous optimization problem by leveraging a white-box LLM fw. Specifically. optimizes a soft prompt 2 E NR,,, where N₂ is the number of tokens and d is the embedding dimension, to generate the optimal instruction v*. The soft prompt is concatenated with the token embeddings of input-output exemplars E = { M1) = and fed into the white-box LLM fw, which then generates an instruction (2, E). Formally, the instruction optimization problem is defined as:
arg max (aayen [h(f6lfu22 E), 2E2
where Z is the soft prompt space. In this formulation, we optimize = to find the optimal instruction o that maximizes the expected value of the score function h. Once the optimal soft prompt 2" is obtained, the corresponding instruction 8* is generated by the white-box LLM fw. i.e., v* = (2", E) and subsequently evaluated on held-out test set Dust- Since the exemplars E are fixed for each task, omit them from the notation in the rest of our paper. Following previous works [6), we assume that both the white-box LLM fw and the black-box LLM fo are deterministic.
LLM- Score Predictor for Instruction Optimization. Our method builds upon IN- STINCT [16), which employs frozen white-box L.MM as a feature extractor to predict the score of soft prompt, and uses a NeuralUCB (21) for instruction optimization. Given a soft prompt z, the white-box LLM produces an embedding g(2), the last token representation of the final transformer layer. This embedding is then passed to a score predictor m(g(z);0 0) (e.g., ., an MLP), which predicts the performance of the instruction generated from 2, i.e., m(g(z);0) = E(z.)) Eh (f(f)(f((2)) v)]. At each optimization step, the score predictor mn(: 0) is trained on previously evaluated soft prompts and their corresponding scores, and selects the next query that maximizes the upper confidence bound. We provide further details of NeuralUCB in the supplement. Since computing 9(2) requires full
3

---

Initialization
Initial Group Selection by Preimage Based Enitialisation
S G2.
Random Sampling
E1
Score Sharing
White Box LEM
22
0.4
G2
1/2
Black Box LIM
044
2/2
Soft Prompt
E2g
Gg
1/3
fb
0.3
0.3
E {[r sullii
Soft Promupt Embedding
Instruction
Preimages of Instractions
Score
Exemplar
(()))
Initial Data
Optimization
Soft Prumpt Embeddiig
Instruction
Scure
Scored
G
U1
0.72
0.72
Update Scored Dataset
Predicted Score
0.60:0.20
C2
1/2
7??
0.60:0.10
X
Soft Prompt
0.60s0.21
Nest Query
Scure
Embedding
G3
1/3
0.80g0.28
0.80:0.30
155
0.82
0.02
3 Train Predictor with Leous
Select
Next Query
UCB
Lart:
Figure 2: The overall process of our proposed PRESTO framework. It consists of two main stages: initialization and optimization. In the initialization stage, our method performs preimage- -based score sharing (Section 4.1 and @ preimage-bass initialization to improve search space coverage (Section 4.2 For the optimization stage, we train the score predictor with @ score consistency regularization (Section 4.3) and apply @ preimage-buan baased score sharing share scores of newly observed data within the same preimage.
forward pass through the LLM, INSTINCT mitigates this cost by precomputing the embeddings of candidate soft prompt set = { at the beginning of the optimization, which is sampled using quasi-random method. To this end, the instruction optimization task is reduced to searching for the best solution within the precomputed embedding set, as the white-box LLM frozen during the optimization process.
Method
In this section, we propose PREimage-infone informmedd inSTruction Optimization (PRESTO) which is a novel instruction optimization framework that leverages the many-to-one mapping between soft prompts 2 E Z Z and instructions v e Q (or the preimages of instructions, which is defined in Section 4.11 prior knowledge to facilitate sharing method that shares the score value of one soft prompt with all other soft prompts in the same preimage, effectively enlarging the scored data without additional evaluations of black-box LLM fb- Next, we present a preimage-based initialization method designed to maximize coverage of the search space under score sharing. Finally, we propose a score consistency regularization that leverages preimage information as prior knowledge to encourage the score predictor to predict identical scores for soft prompts belonging the same preimage. We provide the overall framework of our PRESTO in Figure
efficient optimization. We first introduce score
4.1 Preimage-Based Score Sharing
During the instruction optimization, we observe that the white-box LLM fw often generates identical instructions from distinct soft prompts, i.e., fw( = (=(),, leading the same score value. This redundancy leads to unnecessary queries during optimization, hindering the efficiency of instruction

---

optimization. While previous works treated this redundancy as an obstacle to efficient optimization, we instead leverage this information as prior knowledge about the objective function to facilitate optimization. To this end, we propose simple score sharing scheme that associates a large number of soft prompts with a score value without the additional evaluations of black-box L.LM fb-
Our goal is to share the score of an evaluated soft prompt 2 with other soft prompts that generate the same instruction. To enable this score sharing, we first define the preimage of each instruction which consists of all soft prompts that map to the same instruction under the white-box model fw. Establishing this preimage structure requires two steps. First, we sample a soft prompt set Z = { N fi=1 using a quasi- quasi-random method [30 311, which is widely adopted method to sample the data points that evenly cover the soft prompt space [5). Assuming that the soft prompt set size N is large enough to represent the soft prompt space 2, the original optimization problem defined in Eq. (2) reduces to searching for the best solution among the set of N data points, denoted by Z C 2.
Next, for each soft prompts 2j Z, we generate the set of instructions V JM using the white-box LLM fw:
V = (u.) =
(3)
Since the different soft prompts often generate the identical instruction (i.e., many-to-one mapping), the number of instructions M = [V| smaller than or equal to N. The construction of Z and V is performed only once before the optimization process begins.
With the soft prompt set Z and the corresponding instruction set V, now define the preimage of each instruction. The preimage of an instruction v is the set of soft prompts in Z that generate v under the white-box model fw:
(v) {2 Z fz) = v).
(4)
This preimage contains all soft prompts in Z that generate v, and will serve the basis for score sharing. Once the preimages fm (w) for all v E V are established, we apply score sharing across soft prompts that belong to the same preimage during the optimization. Specifically, after querying the black-box model fo with an instruction v E V, we obtain a score of the instruction. This score is then shared to all soft prompts in the preimage Sw (w). By sharing scores in this manner, we effectively enlarge the training data for the score predictor m (=(())); 0) without additional calls to the black-box LLMs. Moreover, score sharing avoids redundant evaluations of soft prompts that lead to the same instruction and improves optimization efficiency.
4.2 Preimage-Base Based Initialization for Maximizing Search Space Coverage
Here, we introduce a preimage-based initialization method that selects initial data points based on the preimage information defined in Section 4.1 At the beginning of the optimization, the score predictor m(g(z); ()) (Section 3) is trained on the initial dataset, and its predictions are used to select the next data points to query the black-box LLM fo. In black-box optimization, it is well known that broadly covering the search space at initialization is crucial for effective optimization 32 Our score sharing method introduced in Section 4. expands the initial dataset without additional queries the black-bor box LLM fb. enabling a more sample-efficiee efficient initialization. To further enhance the search space coverage, propose a preimage- based initialization method that complements score sharing by promoting a broader initial data distribution.
To this end, we design coverage score S.o to guide the selection of an initial preimage set Ginit that maximally covers the entire set of soft prompt embeddings Grotal = [g(2) 2 E Z). We conduct initialization in the embedding space rather than the soft prompt space, since the optimization operates over the soft prompt embeddings. These embeddings are precomputed and remain fixed throughout the optimization, as described in Section 3 For each instruction U, we
define its corresponding preimage group in the embedding space as G, = {g() 2 E (v:)).
Since finding the optimal combination of Nma preimages that maximizes the coverage score Seov a computationally intractable combinatorial optimization problem, we adopt greedy algorithm to iteratively select one preimage at time. Specifically, the coverage score Scxv consists of two components: the representativeness score Seep and the size score Size. The representativeness score Step encourages the selection of a preimage group G3 that, when combined with already selected
5

---

w/o Consistency Loss
w/ Consistency Loss
True function
Model prediction
Train Data
Gı,y = - 0.5
G2.y =
Gs.y 0.5 Group consistency
X
(a)
Train with LaSE only.
(b) Train with CMSE + f
Figure 3: Toy example comparing models trained w/o and w/ our consistency loss Ceons in Eq. (8)
preimage groups Ginit most closely matches the distribution of the candidate set Grotal, defined as:
MMD (G, U Giiit GGotal)
Step (Ge; Giuit Glotal) max, MMD MMD U U Cuosaa)
where the MMD is the squared Maximum Mean Discrepancy. MMD is widely used metric estimate the similarity between two sets, which is defined as:
MMD2 (X, Ex (Kx,, x')] + Ey,y'> [k(y, y')l X [k v)]
(6)
where k(-,-) is positive definite kernel. To densely cover the search space, we propose the size score Ssize, which is defined as relative preimage size: Ssize / max, |Gyl. Combining the two scores, we define the coverage score for the G₁;;
Sene (G;; Ginit
G
Ssize (Gi) + Seep ( G G
Starting from an empty set Ginit we iteratively select the preimage with the highest coverage score Sewv and add it to Ginit until the number of initial preimages reaches Nmn- This initialization maximizes the coverage the candidate set Gotal We provide the visualization to demonstrate the effectiveness
of our initialization method in Section 6.3
4.3 Score consistency regularization for score predictor
Here, we propose score consistency regularization that encourages the score predictor m(g(=); to produce the same prediction for all soft prompts in preimages that have not been evaluated by the black-box function. During the optimization, the score predictor is trained with the scored data to predict the score of each soft prompt in the candidate set Z and estimate its uncertainty for selecting the next query to evaluate. Leveraging the score sharing method defined in Section 4.1 informs the score predictor that data points within the same preimage share identical scores in a supervised manner. However, since the score predictor lacks information about score consistency within unscored preimages, it is unable to make consistent predictions for data points in these unscored preimages. It often hinders the score predictor from predicting the ground truth score and selecting high-scored data.
To ensure consistent predictions within each unscored preimage, we propose score consistency regularization term Ccons. which is defined as:
Ccons
Epe Varaen
E E. (()) (m(g(2):))
(8)
where Vunseen CV denotes the set of instructions that has not been evaluated by the black-box LLM ft- We note that Loons is an unsupervised loss. While the consistency regularization includes pairwise terms per preimage group, each unscored preimage size is not excessively large in practice, so the computation remains tractable. The final loss for training the score predictor model is given by:
L LASE Looms:
where LMSE is the mean squared error loss computed over the scored preimages, and is hyperpa- rameter controlling the strength of the regularization. To avoid premature convergence to incorrect predictions, employ simple linear scheduling strategy 7(t) Tmax min (1, (L,//T), where t

---

Table 1: Performance instruction induction tasks. Bolded numbers (blue) indicate the best methods for each task. Scores show the average accuracy with standard error over three runs.
Tasks
APE
InstructZero
INSTINCT
EvoPrompt
ZOPO
OPRO
PRESTO
untonyms
80.67 a0772
75.33 3.22
83,33 a35
82.00 +0.4
82.67 1/6
80.33 2:33
83.33 1
auto_ categorization
26.00
27.67 2
18.67 =072
29.33
31.67 #3.41
30.33
31.67
auto, debugging
8,33 1.000
12.50 1.800
10.00 14711
16.67 1680
13.33 17220
8,33 6.80
20.83 1:440
cause Landd effect
92.00 1.89
74.67 4.75
76.00=2.5
72.00 20:00
93.33 2
38.67 4.35
94.67 2.88
common_comsee concepp
22.36 2:34
15.53 1.111
20.21 1.19
17.99
21.86 7.16
20.08 6:70
22.86
3:27
diff
18.33 687
53.00 30.17
81.67 15
7.00 5.75
88.33 5M9
64.33 23
98.00
0887
informal, formal
57.59
51.53
48.93 3.46
42.87
58.93
50.02 2:263
52.77 5.46
letters list negation
99.00 0.82
99.00 0.41
97.67 1.52
73.67 9
98.67 1
99.00 10:47
99,33
0.544
83.33 = 1.19
81.67 333
76.67 4.77
71.67 1.199
77.33 4.6
73.33 4.23
84,00 2.1.6
object counting odd one out
37.33 5..90
46,00 1.72
48.67
28.67
34,00 14088
31,00 3.66
45.67 1.4.5
51.33 19.43
46.67 1.76
60.00) 7.17
68.00 1
58.67 7
47.33 10.39
70.00 1194
orthogruphy_starn Satrrpphy_ttrrt__yye seayy_sttrsswtttt with
=
35.00
54.67
42,00
54.67
22.33
57.33
rhymes
69.33 16.41
81.67 10,69
9%.67 0.72
93.67 1996
83.33 6.87
77.00 15:05
85.00 7:41
second word letter
72.67 = 10.85
40.67 5399
48.00=22
33,00 7M
68.00 17.75
=4.70
77.00 =21.57
simiaacesimilarity sum
29.00
17.33 4..5
11.33
29,00
4,33 1.3323.5 3.54
6.67 25.44
21.67 8.49
24.00 14.03
55.00 23.92
99.33 1154
66.67 27.12
100.,00 1:00
91.33 3:77
94.67 4:35
synonyms
10.00
22.67
25 23.00
25,33
24.33 2
12.67
18.33
taxonomy aanimal
43.67 a 15.96
44.33 a 17.72
92.00=3.m
34,00 : 15:08
69.00 : 24.10
73.67 8.00
99.67 a.0:2
word_ sorting
54.00 = 15
39.67 12.11
=.37
71.00 4.50
54.00 15.06
36.33 11.49
53,33 8.38
word unscrambling
4.77
38.00
42.33
23.00 2957
52,00 2.79
43,00
48.00
best-performing tasks
0
3
3
4
0
12
Average
4.25
4.80
3.70
4.70
3.05
5,20
1.90
represents the current epoch and 1" is a warm-up duration. This schedule allows the score predictor m(g(z); () to learn accurate patterns from the scored data and gradually incorporate the score equality constraint of unscored data.
Figure 3 shows a toy example illustrating the effect of the proposed consistency loss. We use simple model with two linear layers. In Figure Bal the model is trained only with the LMSE on the scored data, while in Figure 3b Leens is additionally applied to unscored data. We assume there are three unscored preimages, each represented by a different marker shape. Although the model is only given the information that data points within each preimage share the same score, the Leons allows it to make more accurate predictions on the unscored data.
5 Experiments
5.1
Experimental settings
We evaluate our proposed method, PRESTO, on 30 instruction induction tasks [36], benchmark widely used to assess instruction optimization performance, and 3 arithmetic reasoning tasks [37-- 39.
We compare PRESTO with six competitive instruction optimization baselines: APE (8) InstructZero 14], INSTINCT [6]. EvoPrompt 10) ZOPO 15), and OPRO (. We use I.L.M3.11-
8n-Instt 1 as the white-box LLM fw to generate candidate instructions, and GPT-4.1 as the black-box model fo- Following previous works [14]66), we set the total query budget 165, initialize with 40 soft prompts, and evaluate all methods over three different random seeds. To ensure a fair comparison, we follow the hyperparameter tuning procedure [66.. Detailed hyperparameter configurations and experimental settings are provided in the supplement.
5.2 Instruction induction results
Here we provide the results of our proposed method, PRESTO, compared with six strong baselines on instruction induction tasks. To enhance readability, we report results on a subset of 20 following previous works [6 15). The full results for all 30 tasks are provided in the appendix. Table shows that PRESTO achieves the highest accuracy on 12 out of the 20 tasks, which is three times more than the second- best method, ZOPO. In addition, PRESTO attains the best average rank of 1.90, outperforming all baselines by clear margin; the next best, ZOPO, has an average rank of 3.05, followed by INSTINCT at 3.70. These results highlight the strong performance of PRESTO on individual tasks and its robustness across wide range of instruction induction tasks. In the full set of 30 tasks, PRESTO also consistently outperforms other haselines with large margin in the number of best best-performing tasks and average rank.
7

---

Table Performance of different CoT prompts on three math reasoning datasets. The best result for each dataset is in bold, and the second best is underlined.
Method
Dataset
Best instruction
Accuracy
Hand-crafted
GSM8K
Let's think step
0.9121
InstruciZero
GSM8K
Let's think step by step to solve the math problem
0.9083
INSTINCT
GSM8K
Let's break down and solve the problem
0,9098
ZOPO
GSM8K
Let's break down and find solution
0.9143
PRESTO (Ours)
GSM8K
Let's break it down together
0.9128
Hand-crafted
AQUA-RAT
Let's think step step.
0.7402
InstructZero
AQUA-RAT
Let's break it down and find the solution Let's break it down step by step. am ready to solve the problem.
0.7480
INSTINCT
AQUA-RAT
0.7480
ZOPO
AQUA-RAT
Let's break it down mathematically.
0.7520
PRESTO (Ours)
AQUA-RAT
Let's solve together.
0.7756
Hand-crafted
SVAMP
Let's think step by step.
0.9375
InstructZero
SVAMP
Let's crack codc!
0,9400
INSTINCT
SVAMP
Let's break down step by step
0.9375
ZOPO
SVAMP
see what you'se 're doing there
0.9400
PRESTO (Ours)
SVAMP
Let's use the formula
0.9400
Table Ablation study of PRESTO. We incrementally add score sharing (SS, Sec. 4.1 preimage-
based initialization (Init, Sec. 4.2). and consistency regularization (Reg, Sec. 4.3
to vanilla baseline.
Model
SS
Reg
Init
Wins
Avg. Rank
Avg. acc.
Vanilla
X
X
X
0
4.55
51.91
SS
X
X
3
3.10
59.57
Reg
2.65
61.77
+ + Init
X
V
4
2.30
61.82
+ SS Init Reg (Ours)
V
9
2.20
62.91
5.3 Chain-of-Thoughh Prompting Results
We evaluate the quality of the optimized instructions by measuring their effectiveness chain- of-thought (CoTT) (40] prompts on three math reasoning benchmarks: GSM8K (37), AQUA-
RAT 38,, and SVAMP (39. We compare method with three baselines that soft prompts (InstructZero 14), INSTINCT [6]., and 7OPO (15),, as well as a standard hand-crafted prompt (41). Table demoostrates that our PRESTO outperforms or matches the best-performing baselines across all datasets. In particular, it achieves the highest accuracy on AQUA-RAT (0.7756) and ties for the best result SVAMP (0.9400), while remaining competitive GSM8K. These results indicate that the instructions optimized by our method are also effective when used as CoT prompts.
Analysis
6.1 Ablation Study
We perform an ablation study to analyze the contribution of each component in our method over the 20 instruction induction tasks used Table over random seeds. Starting from a vanilla baseline without our techniques, we incrementally add: (1) score sharing method (Section 4.1 (2)
preimage-based initialization (Section 4.2), and (3) score consistency regularization (Section 4.3)
The full model with all components combined corresponds our proposed method, PRESTO. As shown 3 each component contributes to performance improvement. particular, introducing score sharing significantly boosts accuracy from 51.91 to 59.57 (+7.66) and improves average rank from 4.55 to 30 (-1.45), indicating its strong impact. Our PRESTO achieves the best results overall, with the highest number of wins and the lowest average rank across tasks.
6.2 Impact of score sharing method
We report the average number of soft prompts with assigned scores after the optimization process, comparing our method with baselines across all 30 tasks. The reported count includes soft prompts that were scored either directly through black-box evaluation or indirectly via score sharing. As shown in Figure 4 our method assigns scores to over 2,300 soft prompts average, 14x more than

---

Score predictor performance
3000
0.3
2500
0.25
RMSE
Scooed
1500
0.15
500
165
0.1
All previous
PRESTO
Vanilla
Reg
-88
-88, Reg
method
(Ouns)
Figure 4: Average number of scored soft prompts after optimization across all tasks.
Figure 5: Performance of score predictor trained with diverse methods.
Random init. (Previous)
Random init Score Sharing
Preimage-besed init. (Stup)
Preinage-based init. (Scov)
(b)
(c)
(d)
Figure 6: Visualization of the initial data distribution under different initialization. We plot the entire soft prompt embedding candidate set Grotal using t-SNE, and highlight the selected initial data red.
previous methods, which yield only 165 scored data points, equal to the query budget in our setting, The large amount of scored data enables the score predictor to learn the objective function more effectively, which in turn facilitates more successful optimization. This analysis demonstrates that our soore-sharing method can significantly increase the amount of scored data without requiring additional black-box queries.
6.3 Visualization of Preimage-Based Initialization
We present a qualitative analysis of how score sharing and preimage-based initialization influence the distribution of initial soft prompts. Figure visualizes the distribution of initial soft prompts under four settings: (1) random initialization, (2) random initialization with score sharing (Section 4.1. (3) preimage-based initialization using Stop only, and (4) Seov Step + Ssize (Section 4.2) in "objective counting" task. To visualize the spatial distribution of soft prompt embeddings, we employ t-SNE. Compared random initialization in prior works, score sharing enlarges the size of the initial dataset without additional black-box queries. Furthermore, selecting initial data using Srep leads to better coverage of the soft prompt space than naive score sharing. Finally, our proposed preimage- based initialization method that utilizes Scwv achieves the densest and comprehensive coverage of the search space. shows that our preimage-based initialization method effectively selects the initial data points that densely and evenly cover the search space.
6.4 Score Predictor Performance Enhancement
To analyze how score sharing (Section 4.1) and score consistency regularization (Section 4.3 influence the quality of the score predictor, evaluate its prediction performance under different training configurations. Figure rreports the root mean squared error (RMSE), where lower values indicate higher prediction accuracy. We use 100 randomly selected soft prompts as training data and another 100 as test data for the objective counting task. As shown in Figure [] applying either score sharing or score consistency regularization improves the score predictor's 's performance, reducing the RMSE from approximately 0.27 (vanilla) to around 0.23. When both techniques are applied together, the RMSE further decreases to approximately 0.15, indicating a strong complementary effect. The results demonstrate that expanding the training set without requiring additional black-box queries

---

through score sharing and incorporating the preimage structure a prior via score consistency regularization are both crucial for enhancing the score predictor's performance.
7 Conclusion
We propose PRESTO, a preimage-informed instruction optimization framework that explicitly lever- ages this many-to-one structure via preimage. PRESTO consists of three components that leverage the preimage structure: score sharing to propagate labels within each preimage, preimage-basee initial- ization to improve search space coverage, and consistency regularization to align predictions within unscored preimages. PRESTO achieves state-of-the-an performance on 33 instruction optimization tasks, and our comprehensive analysis supports its effectiveness and robustness.
Limitations and broader impacts
Our method introduces preimage- wreimage-based based score sharing to enlarge the number of data, which incurs mild computational overhead compared to simpler baselines. Moreover, its benefits are more pronounced when applied to a large candidate set, as score sharing is most effective when many soft prompts map to the same instruction.
In terms of broader impact, this work aims to make black-box LLM optimization more data-efficient, which can reduce the cost of experimentation and improve accessibility for researchers with limited resources. However, as with any optimization technique for LLMs, there is risk that improved performance could be applied in ways that reinforce biases or generate harmful content. Careful deployment and alignment with responsible AI principles are necessary.
Acknowledgement
This research was supported by the ASTRA Project through the National Research Foundation (NRF) funded by the Ministry of Science and ICT (No. RS-2024-00439619).
References
[1] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama
3 herd of models. arXiv, 2024.
[2] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv, 2023.
[3] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning, arXiv preprini arXiv:2501.129445 2025.
[4] Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting, Large language models in medicine. Nature medicine, 2023.
[5] Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saced Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian. A comprehensive overview of large language models. arXiv preprint arXiv:2307.06433. 2023.
[6] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
[7] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM computing surveys, 2023.
[8] Yongehao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. In ICLR, 2022.
10

---

[9] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen, Large language models as optimizers. In ICLR, 2024.
[10] Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In ICLR, 2024.
[11] Chrisantha Fernando, Dylan Sunil Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. Promptbreeder: Self-referential self-improvement via prompt evolution. In International Conference on Machine Learning, 2024.
[12] Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng, Automatic prompt optimization with" gradient descent" and beam search. In EMNLP, 2023.
[13] Chengshuai Shi, Kun Yang, Zihan Chen, Jundong Li, Jing Yang, and Cong Shen. Ef- ficient prompt optimization through the lens of best arm identification. arXiv preprint N.NV::2002.09223. 2024.
[14] Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. Instructzero: Efficient instruction optimization for black-box large language models. In ICMI., 2024.
[15] Wenyang Hu, Yao Shu, Zongmin Yu, Zhaoxuan Wu, Xiaoqiang Lin, Zhongxiang Dai, See- Kiong Ng, and Bryan Kian Hsiang Low. Localized zeroth- orderr prompt optimization. NeurIPS, 2024.
[16] Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng. Patrick Jaillet, and Bryan Kian Hsiang Low. Use your instinct: Instruction optimization for Ilms using neural bandits coupled with transformers. ICML, 2024.
[17] Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. Mixtral of experts. arXiv preprint S.kiv:2401.040055 2024.
[18] An Yang. Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15113 2024.
[19] Peter Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv: 1807.028/1 2018.
[20] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: review of bayesian optimization. Proceedings of the IEEE, 2015.
[21] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In ICML, 2020.
[22] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:20/0.00822 2020.
[23] Krista Opsahl-Ong, Michael Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. Optimizing instructions and demonstrations for multi-stage language model programs. In EMNLP, 2024.
[24] Xiaoqiang Lin. Zhongxiang Dai, Arun Verma, See-Kiong Ng. Patrick Jaillet, and Bryan Kian Hsiang Low. Prompt optimization with human feedback. arXiv preprint arXiv:2405. 17346, 2024.
[25] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux. Pierre Stock, Teven Le Scao. Thibaut Lavri Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b. arXiv, 2023.
[26] Seunghun Lee, Jaewon Chu, Sihyeon Kim, Juyeon Ko, and Hyunwoo J Kim. Advancing bayesian optimization via learning correlated latent space. Advances Neural Information Processing Systems, 2023.
11

---

[27] Jaewon Chu, Jinyoung Park, Seunghun Lee, and Hyunwoo Kim. Inversion based latent bayesian optimization. The Thirty-eightt Annual Conference on Neural Information Process- ing Systems, 2024.
[28] Seunghun Lee, Jinyoung Park, Jaewon Chu, Minseo Yoon, and Hyunwoo J Kim. Latent bayesian optimization via autoregressive normalizing flows. In The Thirteenth International Conference Learning Representations, 2025.
[29] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26,
2017.
[30] William J Morokoff and Russel E Caflisch. Quasi-random sequences and their discrepancies. SIAM Journal on Scientific Computing, 15()):1251-1279 1994.
[31] Marissa Renardy, Louis R Joslyn, Jess A Millar, and Denise Kirschner. To sobol or not to sobol? the effects of sampling schemes in systems biology applications. Mathematical biosciences, 337:108593, 2021.
[32] Donald R Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455 1998.
[33] David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
[34] Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hypervolume improvement for parallel multi-objective bayesian optimization. Advances in Neural Information Processing Systems, 33:9851-9988 19664, 2020.
[35] Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Parallel bayesian optimization of multiple noisy objectives with expected hypervolume improvement. Advances in Neural Information Processing Systems, 34:2187-2200 2200, 2021.
[36] Or Honovich, Uri Shaham, Samuel R Bowman, and Omer Levy. Instruction induction: From few examples to natural language task descriptions. In 61 Annual Meeting of the Association for Computational Linguistics, ACL 2023, pages 1935-1952, 2023.
[37] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 141668 2021.
[38] Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by ratio- nale generation: Learning to solve and explain algebraic word problems. arXiv preprint arXiv:1705.0411
2017.
[39] Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are nlp models really able to solve simple math word problems? arXiv preprint arXiv:2103.07199, 2021.
[40] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
[41] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199. 18:22199-2202 22211,, 2022.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly state the main claims (Section D 4b
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses limitations after Section
13

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification: The paper does not present formal theoretical proofs, focusing instead on algorithmic design and empirical validation.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 5.1 provides full experimental settings, and additional details are available the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibilityy which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes)
Justification: The paper states that detailed configurations and implementation details are provided in Section 5.1 and the supplement, and the authors intend to release code and data after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g.. for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 7/nips. wwwpcccccccc/.....c....co..eetle
wwtppppgguidese//ppppppppopppaep guwdee/eee/eeee CooeeSumisssii sssssnooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The paper describes test splits, model usage, total budget, search space construction, and optimization strategies.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The tables report averages with standard errors three random seeds, and all comparisons to baselines include this variance (see Tables [T.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The supplementary materials include detailed specifications, including hard- ware type.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The work conforms to NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses broader impacts after Section
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The method does not release any high-risk models datasets.
17

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper appropriately cites existing models and datasets with references including model names and publications.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pacerswithcode thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new dataset, model, or tool is released. The method is built on existing
assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
18

---

Answer: [NA]
Justification:
The research does not involve any human subjects or crowdsoureing experi- ments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subject research is conducted, hence IRB approval is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [Yes]
Justification: The method leverages both white-box and black-box LLMs part of its optimization framework.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non ntn-standard components.
Please refer to LLM policy httppp////errrpecoccco/ooerreeep for what should or should not be described.
19


Reviews:
[{"review_id": "IzJzlElpWC", "reviewer": "Reviewer_uyym", "summary": "This paper tackles the problem of automatically optimizing instructions for black-box LLMs by leveraging an auxiliary white-box LLM. Prior work generates soft prompts that are fed into a white-box model to propose candidate instructions, but often different soft prompts map to the same instruction. Rather than regarding this redundancy as wasteful, the authors introduce PRESTO, which exploits the preimage structure to amplify the effective data and guide search. There are 3 major components in the proposed method: (1) score sharing, which shares the evaluation score with all soft prompts in a preimage; (2) preimage-based initialization, which selects initial data points that maximize search space coverage using preimage information; and (3) score consistency regularization, which enforces prediction consistency within each preimage. Empirically, PRESTO uses the same query budget but effectively learns from 14× more “virtual” data points, yielding superior performance on 33 instruction-induction tasks and three arithmetic reasoning benchmarks, outperforming strong baselines.", "questions": "How will the cost of MMD scale with the candidate set size?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n1. The idea of reinterpreting the many-to-one mapping as useful prior knowledge to enhance the optimization performance is novel. \n\n2. The experimental results on a variety of datasets show the effectiveness of the proposed method over the compared baselines.\n\nWeakness:\n\nIn general I think the paper is good. However, I have one concern - though the method is designed to improve the data efficiency, I am curious about the overall computational efficiency of the proposed method. For example, how will the cost of MMD scale with the candidate set size? A more detailed comparison of the algorithm efficiency with the baseline method is desired.", "was_revised": false, "final_justification": "", "rebuttal": "- **[W1, Q1] Computational Analysis of MMD**\n    \n    \n    | Candidate set size | 1k | 5k | 10k (Current) | 20k | 30k |\n    | --- | --- | --- | --- | --- | --- |\n    | MMD computation time (sec.) | 7.18 $\\pm$ 1.39 | 11.13 $\\pm$ 1.77 | 27.67 $\\pm$ 3.75  | 79.92 $\\pm$ 5.32 | 94.31 $\\pm$ 8.83 |\n    \n    Thank you for the suggestion. We conducted a computational analysis of the MMD with respect to the size of the candidate set (1k, 5k, 10k, 20k, 30k). As expected, the computation time increases with the size of the candidate set. Notably, even the largest setting (30k) remains computationally feasible, taking approximately 1 minute and 30 seconds.\n        \n- **[W1] Efficiency Comparison with Baselines**\n    \n    \n    |  | InstructZero [1] | INSTINCT [2] | ZOPO [3] | PRESTO (Ours) |\n    | --- | --- | --- | --- | --- |\n    | Preprocess (min.) | - | 2.02 $\\pm$ 0.38 | 5.07 $\\pm$ 0.48 | 6.81 $\\pm$ 0.51 |\n    | Optimization (min.) | 11.17 $\\pm$ 1.04 | 13.21 $\\pm$ 1.79 | 9.53 $\\pm$ 1.19 | 10.63 $\\pm$ 1.36 |\n    | Average accuracy | 61.67 | 67.92 | 69.79 | **72.76** |\n    \n    We conducted a wall-clock time comparison with baselines. During preprocessing, which is performed before the optimization process begins, PRESTO generates both LLM embeddings and instructions of candidate soft prompts, whereas INSTINCT generates only the embeddings. Despite involving more components, PRESTO achieves a lower overall optimization time than INSTINCT. This is because PRESTO pre-generates candidate instructions in batch during preprocessing, while INSTINCT queries the LLM at every optimization step. As shown above, PRESTO incurs only marginal preprocessing overhead, yet achieves superior optimization performance.\n    \n    - Reference\n        \n        [1] Chen, Lichang, et al. \"Instructzero: Efficient instruction optimization for black-box large language models.\" ICML (2024).\n        \n        [2] Lin, Xiaoqiang, et al. \"Use your instinct: Instruction optimization for llms using neural bandits coupled with transformers.\" ICML (2024).\n        \n        [3] Hu, Wenyang, et al. \"Localized zeroth-order prompt optimization.\" NeurIPS (2024)."}, {"review_id": "3K17ajYo9t", "reviewer": "Reviewer_BKWA", "summary": "This paper introduces PRESTO, a novel framework for optimizing instructions for black-box large language models (LLMs) by leveraging the preimage structure—the many-to-one mapping from soft prompts to instructions produced by a white-box LLM. Unlike previous work, which treats this redundancy as a nuisance, PRESTO exploits it to improve sample efficiency and optimization performance. The framework consists of three main components: (1) score sharing across soft prompts in the same preimage, (2) preimage-based initialization to increase search space coverage, and (3) score consistency regularization for the score predictor. Experiments on 33 instruction optimization tasks show that PRESTO outperforms strong baselines.", "questions": "Ablation Studies:\nThe paper would be improved by including ablations isolating the impact of each PRESTO component (score sharing, initialization, regularization) to better understand their individual contributions.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- Novelty. The key insight—interpreting the many-to-one mapping from soft prompts to instructions as a source of prior knowledge rather than redundancy—is both original and well-motivated. This perspective enables PRESTO to achieve significant improvements in query efficiency and optimization performance\n\n- Empirical Results. The method is evaluated on a broad set of 33 instruction optimization tasks (30 induction, 3 arithmetic reasoning), achieving state-of-the-art performance compared to strong baselines such as INSTINCT and ZOPO. PRESTO shows the effect of observing up to 14 times more scored data under the same query budget.\nClarity. The paper is well-organized, with clear motivation, background, and methodological exposition. The figures (e.g., distribution of preimage sizes) effectively illustrate the core concepts. \n\n## Weaknesses\n\n- Assumptions about Preimage Structure: PRESTO assumes that the preimage structure (i.e., which soft prompts map to which instructions) can be efficiently established by sampling a large set of soft prompts and mapping them through the white-box LLM. The scalability of this approach to very large prompt spaces or more complex instruction sets is not fully discussed.\n- Dependence on White-Box LLMs: The framework relies on access to a white-box LLM to generate instructions from soft prompts and to extract embeddings for the score predictor. This may limit applicability in scenarios where only black-box LLMs are available, or where the white-box model's behavior diverges from the black-box model.\n- Evaluation Scope: While the paper reports strong results on 33 tasks, it is unclear how PRESTO performs on tasks with fundamentally different instruction distributions or in settings where the preimage sizes are much smaller (i.e., less redundancy to exploit). Additional ablations or analysis on such edge cases would strengthen the empirical claims.\n- Computational Overhead: The need to precompute and store large sets of soft prompts, instructions, and preimage mappings may incur significant computational and memory overhead, especially as the candidate set grows. The paper would benefit from a more detailed discussion of these practical considerations.", "was_revised": true, "final_justification": "The authors' response clarified several of my concerns, particularly regarding scalability, computational overhead, and the empirical contributions of each PRESTO component. The added analyses and ablations strengthen the paper’s technical grounding and confirm its effectiveness.\n\nHowever, two core limitations remain: (1) the dependence on access to white-box LLMs, and (2) assumptions about the feasibility of constructing preimage structures in broader settings. These restrict general applicability beyond the evaluated scenarios.\n\nOverall, I find the work well-executed and valuable within its scope. My score remains unchanged, reflecting my assessment of the work.", "rebuttal": "- **[W1] Scalability analysis of preimage construction**\n    \n    \n    | # Soft prompt tokens | 3 | 5 | 10 | 50 | 100 |\n    | --- | --- | --- | --- | --- | --- |\n    | Preimage construction (min.) | 6.72 $\\pm$ 0.39 | 6.87 $\\pm$ 0.44 | 7.08 $\\pm$ 0.45 | 8.66 $\\pm$ 0.62 | 10.52 $\\pm$ 0.70 |\n    \n    Thank you for the suggestion. We provide a scalability analysis of preimage construction with respect to the size of the soft prompt space, which is defined as (number of tokens $\\times$ dimension). Since the dimension is fixed (it depends on the white-box LLM), we focus on the number of soft prompt tokens: 3, 5, 10, 50, and 100. The table above shows that the proposed method has good scalability. With a large number of soft prompts (50 and 100), the preimage construction remains computationally feasible. In our experiments, we used 3 to 10 soft prompt tokens.\n    \n- **[W2] Availability of and dependency on white-box LLM**\n    \n    Scenarios where only black-box LLMs are available are relatively uncommon, since various open-source white-box LLMs are already publicly available. Several prior studies have leveraged white-box LLMs to facilitate instruction optimization for black-box LLMs [1,2,3]. Additionally, as already shown in Tables 4 and 5 of the supplementary material, PRESTO consistently achieves strong performance across diverse white-box and black-box LLM combinations.\n    \n    - Reference\n        \n        [1] Chen, Lichang, et al. \"Instructzero: Efficient instruction optimization for black-box large language models.\" ICML (2024).\n        \n        [2] Lin, Xiaoqiang, et al. \"Use your instinct: Instruction optimization for llms using neural bandits coupled with transformers.\" ICML (2024).\n        \n        [3] Hu, Wenyang, et al. \"Localized zeroth-order prompt optimization.\" NeurIPS (2024).\n        \n- **[W3] Analysis of the effect of preimage size**\n    \n    \n    | Preimage size (%) | \\- (Vanilla) | 1 | 10 | 50 | 100 (Current) |\n    | --- | --- | --- | --- | --- | --- |\n    | Average accuracy | 51.91 | 59.95 | 60.67 | 61.89 | 62.91  |\n    \n    As suggested, we analyzed the effect of preimage size by varying the proportion of soft prompts included in each preimage (1%, 10%, 50%, and 100%). We also included experimental results for the vanilla model, which does not utilize the preimage structure. The results show that larger preimage sizes lead to higher average accuracy, indicating that richer information in the preimage facilitates more successful optimization. This highlights the critical role of the preimage structure in instruction optimization.\n    \n- **[W4] Computational analysis of preimage construction**\n    \n    \n    | Candidate set size | 1k | 5k | 10k (Current) | 20k | 30k |\n    | --- | --- | --- | --- | --- | --- |\n    | Preimage construction (min.) | 0.66 $\\pm$ 0.04 | 3.31 $\\pm$ 0.20 | 6.72 $\\pm$ 0.39 | 13.36 $\\pm$ 0.80 | 19.82 $\\pm$ 1.02 |\n    | Memory (MB) | 47.47 | 237.46 | 474.96 | 950.10 | 1425.63 |\n    \n    We provide an efficiency analysis of the preimage construction process with respect to the candidate set size. The results show that construction time and total memory usage increase approximately linearly with the size of the candidate set, while the overall cost remains modest.\n    \n- **[Q1] Additional ablation studies**\n    \n    \n    | Model | Vanilla | + Init | + Reg | + SS |\n    | --- | --- | --- | --- | --- |\n    | Avg. acc. | 51.91 | 52.41 (+0.5) | 53.49 (+1.58)  | 59.57 (+7.66) |\n    \n    We have conducted additional ablation studies that apply score consistency regularization (Reg) and preimage-based initialization (Init) to the vanilla model. Preimage-based initialization shows relatively smaller performance gain since this method assumes the presence of score sharing. As shown in Table 3 of the main paper, adding preimage-based initialization to score sharing results in a further performance improvement (+2.25)."}, {"review_id": "j9GF2OgWzj", "reviewer": "Reviewer_cs11", "summary": "This paper tackles inefficient instruction optimization for black-box LLMs, a problem arising when different \"soft prompts\" generate the same instruction. The authors reframe this many-to-one mapping as a useful \"pre-image\" structure and introduce PRESTO, a framework that leverages it for efficient optimization. PRESTO employs three techniques: score sharing, which propagates a single evaluated score to all soft prompts within its preimage; preimage-based initialization, which improves initial data selection to maximize search space coverage; as well as score consistency regularization, which enforces consistent predictions for prompts within the same preimage. Over dozens of different tasks, PRESTO can achieve comparably or better performance on instruction optimization tasks compared with baselines.", "questions": "Please kindly refer to my comments above", "limitations": "There is a limitations section after Section 7", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Positive:\n\n1. The manuscript is generally well-structured and easy to follow. Figure 2 also provides a clear high-level illustration and narrative of the overall pipeline. Augmenting the data to provide abundant learning signals without additionally querying the expensive API is intuitive.\n\n2. The method's robustness is validated through extensive experiments across various combinations of white-box (LLaMA, Qwen, Mistral) and black-box (GPT-4.1, Gemini-2.0-Flash) language models. Statistical significance results are also reported via standard deviation. The extensive experiments are the main contribution of this work.\n\n3. Code implementation is provided for reproducing the results.\n\n\nNegative:\n\n1.\tThe method is an extension of the existing INSTINCT framework, using the related NeuralUCB algorithm and codebase, leading to limited algorithmic contributions and limited novelty. The core techniques are based on well-established machine learning concepts, including distribution matching with MMD for initialization, and consistency regularization for training. \n\n2.\tThe training pipeline still needs further justifications since it is purely heuristic rather than theoretically justified by the authors. For instance, what is the motivation and justification of designing the coverage score as Eq (7) other than simple heuristics? The toy example along is also not sufficient since it is merely a toy example with a small network of two layers as suggested by the authors.\n\n3.\tWhile an efficiency analysis is provided, the paper lacks an explicit wall-clock time comparison with the baselines, which can better demonstrate the computational overhead of the new components, especially with the newly added soft prompt augmentation techniques.\n\n4.\tWhile the experiments cover over 30 tasks, most of them are simple induction tasks. Although additional evaluations on three math reasoning tasks are included in Table 2, there are no significant insights derived from these empirical results, as the best instructions across methods are very similar and notably short. The authors also provide no further analysis or justification for the advantages of the generated instructions produced by their method, other than good performance (248-255). Given the small performance gaps and the highly similar instructions, it is difficult to justify the superiority of the proposed approach over baselines, on the other tasks beyond simple instruction induction.", "was_revised": true, "final_justification": "I appreciate the new wall-clock time comparison, which helps address my questions about overhead.\n\nI still believe that the work can be enhanced with deeper theoretical justification for its heuristic design choices. Furthermore, a qualitative analysis is still needed to explain why the method's instructions are more effective on complex tasks. This would provide valuable insight that the dry accuracy metrics alone do not capture.\n\nAs mentioned in my initial review, I will maintain my positive rating given the paper's strong empirical contributions.", "rebuttal": "- **[W1] Contributions and novelty of PRESTO**\n    \n    Our main contribution is that we reinterpret many-to-one mapping between soft prompts and instructions—typically, previous works considered it as a challenge of white-box LLM-based instruction optimization for black-LLMs—as useful prior knowledge for optimization by leveraging the preimage structure. To our knowledge, this is the first work to leverage the preimage structure in instruction optimization. Also, both reviewers uyym and BKWA highlighted the novelty as a strength of our PRESTO, stating that \"The idea of reinterpreting the many-to-one mapping as useful prior knowledge is novel\" and \"The key insight is both original and well-motivated.\", respectively.\n\n- **[W2] Justification of the coverage score and consistency regularization**\n\n    While PRESTO does not rely on a formal theoretical proof, its design is grounded in widely accepted principles in black-box optimization and machine learning.\n\n    - **Preimage-based initialization:** In black-box optimization, it is important to select initial data that broadly covers the search space [1]. Since coverage increases when the data distribution is closer to that of the search space and when the number of data points is larger, we designed Eq. 7 to measure the coverage.\n    - **Consistency regularization:** We encourage the regression model to predict identical predictions for soft prompts within the same preimage to impose the preimage structure as a prior. Such regularization is a well-established technique across various areas of machine learning.\n\n    Theoretical justification for PRESTO is a highly intriguing direction, and we also have a deep interest in exploring it further.\n\n    - Reference\n\n        [1] Jones, Donald R., Matthias Schonlau, and William J. Welch. \"Efficient global optimization of expensive black-box functions.\" *Journal of Global optimization* (1998).\n\n- **[W3] Wall-clock time comparison**\n    \n    \n    |  | InstructZero [1] | INSTINCT [2] | ZOPO [3] | PRESTO (Ours) |\n    | --- | --- | --- | --- | --- |\n    | Preprocess (min.) | - | 2.02 $\\pm$ 0.38 | 5.07 $\\pm$ 0.48 | 6.81 $\\pm$ 0.51 |\n    | Optimization (min.) | 11.17 $\\pm$ 1.04 | 13.21 $\\pm$ 1.79 | 9.53 $\\pm$ 1.19 | 10.63 $\\pm$ 1.36 |\n    | Average accuracy | 61.67 | 67.92 | 69.79 | **72.76** |\n    \n    We conducted a wall-clock time comparison with baselines. During preprocessing, which is performed before the optimization process begins, PRESTO generates both LLM embeddings and instructions, whereas INSTINCT generates only the embeddings. Despite involving more components, PRESTO achieves a lower overall optimization time than INSTINCT. This is because PRESTO pre-generates instructions in batch during preprocessing, while INSTINCT queries the LLM at every optimization step. As shown above, PRESTO incurs only marginal preprocessing overhead, yet achieves superior optimization performance.\n    \n    - Reference\n        \n        [1] Chen, Lichang, et al. \"Instructzero: Efficient instruction optimization for black-box large language models.\" ICML (2024).\n        \n        [2] Lin, Xiaoqiang, et al. \"Use your instinct: Instruction optimization for llms using neural bandits coupled with transformers.\" ICML (2024).\n        \n        [3] Hu, Wenyang, et al. \"Localized zeroth-order prompt optimization.\" NeurIPS (2024).\n\n- **[W4] Performance of PRESTO on complicated tasks**\n\n    PRESTO demonstrates strong performance on both simple and complex tasks. Interestingly, even when the task is more complex or challenging, the proposed method still boosts performance, while the baselines are NOT effective in optimizing prompts. For instance, on a math reasoning task, AQUA-RAT, which is a relatively challenging task, INSTINCT provides only a marginal improvement (0.78%) over hand-crafted instruction. However, our method achieves a significant performance gain of 3.54% over hand-crafted instruction. Although we cannot provide more results at the moment due to limited resources, we will include more challenging tasks in the final version."}]

Author rebuttal:

Meta-review: This paper introduces PRESTO. The key contribution is to reinterpret the many-to-one mapping from soft prompts to discrete instructions, a phenomenon previously seen as a redundancy, as a useful structure called a "preimage". The paper's primary strengths, as noted by the reviewers, include the  novelty of its core insight and its strong, extensive empirical results across 33 tasks and multiple LLMs. Weaknesses raised during the review process include a  dependency on access to white-box LLMs, a  lack of formal theoretical justification for some heuristic design choices , and initial concerns about computational overhead (the last of which were effectively addressed during rebuttal).

During the rebuttal period, the authors effectively addressed most of the reviewers' concerns. They provided a detailed wall-clock time comparison and scalability analysis, demonstrating that the computational overhead is manageable and competitive with baselines. They also provided requested ablation studies that clarified the contribution of each of PRESTO's components. Overall, a majority of reviewers acknowledge the novelty of the work, and there is consensus on its strong empirical results, both in terms of the margin of gain and the extensiveness of the evaluation. The rebuttal cleared most of the issues raised. The remaining weaknesses concern the lack of deep theoretical justification (which is a valid point but is arguably what the entire field is lacking) and the reliance on white-box LLMs (again, this is a setup shared across all methods based on soft prompt tuning). All reviewers ultimately recommended acceptance. Hence, the AC recommends acceptance of this paper.
Decision: Accept (poster)