1 of 18

Jaewon Chu, Seunghun Lee and Hyunwoo J. Kim

PRESTO: Preimage-Informed Instruction Optimization

for Prompting Black-Box LLMs

Machine Learning and Vision Lab

Korea University, KAIST

1

2

1

2

1

Korea University & KAIST

MLV Lab

NeurIPS 2025

2 of 18

Instruction Optimization

Black-Box LLM

?

GT Answer

Input: NeurIPS 2025

Instruction:�?

Goal: Find optimal instruction that guide black-box LLM to generate the correct response.

MLV Lab

NeurIPS 2025

Korea University & KAIST

3 of 18

Instruction Optimization

Input: NeurIPS 2024

Output: Vancouver

The instruction was to?

Soft Prompt

Instruction:�?

White-Box LLM

Black-Box LLM

?

GT Answer

Input: NeurIPS 2025

Instruction:�?

Goal: Find optimal instruction that guide black-box LLM to generate the correct response.

Search over discrete instruction sequence is challenging: Leverage a white-box LLM!

MLV Lab

NeurIPS 2025

Korea University & KAIST

4 of 18

Instruction Optimization

Black-box optimization

Input: NeurIPS 2024

Output: Vancouver

The instruction was to?

Soft Prompt

Instruction:�Output the host city of the given conference.

White-Box LLM

Black-Box LLM

San Diego �&�Mexico City

GT Answer

Score

Input: NeurIPS 2025

Instruction:�Output the host city of the given conference.

:Observed data

:Next query

Goal: Find optimal instruction that guide black-box LLM to generate the correct response.

Search over discrete instruction sequence is challenging: Leverage a white-box LLM!

Search optimal soft prompt via black-box optimization to generate optimal instruction.

Soft prompt space

MLV Lab

NeurIPS 2025

Korea University & KAIST

5 of 18

Instruction Optimization

Black-box optimization

Input: NeurIPS 2024

Output: Vancouver

The instruction was to?

Soft Prompt

Instruction:�Output the host city of the given conference.

White-Box LLM

Black-Box LLM

San Diego �&�Mexico City

GT Answer

Score

Input: NeurIPS 2025

Instruction:�Output the host city of the given conference.

:Observed data

:Next query

Soft prompt space

Step : Train the score predictor via MSE Loss

Step : Select the next query (soft prompt) with trained score predictor

MLV Lab

NeurIPS 2025

Korea University & KAIST

6 of 18

Motivation

Many-to-one mapping

between soft prompts and instructions

Soft prompts

Instructions

White-Box LLM

: Preimage of

MLV Lab

NeurIPS 2025

Korea University & KAIST

7 of 18

Motivation

Preimage statistics

Count

# soft prompts

# instructions

66%

51%

31%

Preimage index

Preimage size

MLV Lab

NeurIPS 2025

Korea University & KAIST

8 of 18

Motivation

Previous works: Many-to-one mapping hinders the efficient optimization

PRESTO (Ours): Many-to-one mapping accelerates the efficient optimization

MLV Lab

NeurIPS 2025

Korea University & KAIST

9 of 18

Method – Score Sharing [A]

We share the score of observed soft prompt to others in the same preimage.

MLV Lab

NeurIPS 2025

Korea University & KAIST

10 of 18

Method – Score Sharing [A]

Scored data

(Previous works)

{ , 0.4}

{ , 0.3}

{ , 0.4}

Scored data

(Ours)

Score Sharing

{ , 0.3}

We share the score of observed soft prompt to others in the same preimage.
It effectively enlarges the amount of scored data without additional calls to the black-box LLM.

MLV Lab

NeurIPS 2025

Korea University & KAIST

11 of 18

Method – Preimage-based Initialization [B]

Goal: Select preimages for initialization that maximally cover the search space

Search space

: Soft prompt of preimage 1

: Soft prompt of preimage 2

: Soft prompt of preimage 3

MLV Lab

NeurIPS 2025

Korea University & KAIST

12 of 18

Method – Preimage-based Initialization [B]

Goal: Select preimages for initialization that maximally cover the search space

Search space

: Soft prompt of preimage 1

: Soft prompt of preimage 2

: Soft prompt of preimage 3

Search space

Max coverage

Low coverage

MLV Lab

NeurIPS 2025

Korea University & KAIST

13 of 18

Method – Score Consistency Regularization [C]

Train score predictor by:

: Predict the score (supervised loss)

: Ensure consistent predictions within same preimage (unsupervised loss)

: Coefficient of consistency regularization

MLV Lab

NeurIPS 2025

Korea University & KAIST

14 of 18

Experiment: Main Table

MLV Lab

NeurIPS 2025

Korea University & KAIST

15 of 18

X 14

Analysis – Score Sharing [A]

Number of scored data

After optimization process end, we measure the number of scored data under the same budget.
PRESTO yields 14 times more scored data than all previous methods.

Budget

MLV Lab

NeurIPS 2025

Korea University & KAIST

16 of 18

Analysis – Preimage-based Initialization [B]

Visualization of the initial data distribution

Random init. (Previous)

Preimage-based init. (Ours)

We plot entire candidate data (gray dots) and the initial data (red dots).
PRESTO effectively selects the initial data points that densely and evenly cover the search space.

MLV Lab

NeurIPS 2025

Korea University & KAIST

17 of 18

Analysis – Score Consistency Regularization [C]

Score predictor performance

We measure the RMSE of the score predictor after applying our proposed methods.
Compared to the vanilla model, applying both score sharing and score consistency regularization reduced the RMSE by 43.6%.

MLV Lab

NeurIPS 2025

Korea University & KAIST

18 of 18

PRESTO: Preimage-Informed Instruction Optimization

for Prompting Black-Box LLMs

Paper

18

Korea University & KAIST

MLV Lab

NeurIPS 2025