PRESTO: Preimage-Informed Instruction Optimization for Prompting Black-Box LLMs

AI summary

Overview

Research area: Machine learning / natural language processing — specifically automatic prompt and instruction optimization for black-box large language models using white-box LLM assistance and black-box optimization.

Technical level: Intermediate. The paper assumes familiarity with soft prompts, embedding spaces, Bayesian optimization-style query selection, and concepts such as Maximum Mean Discrepancy (MMD) and NeuralUCB, though the core idea is intuitive.

Scope: The paper proposes PRESTO, a framework that exploits the "many-to-one" mapping between soft prompts and generated instructions to make instruction optimization for black-box LLMs more query-efficient, evaluated on 33 instruction optimization tasks (30 instruction induction plus 3 arithmetic reasoning).

What This Paper Is About

Optimizing instructions for black-box LLMs (models accessed only through APIs, such as GPT-4.1) is hard because their internal parameters are inaccessible, so optimization relies on costly scored queries. Recent methods use a white-box LLM (such as LLaMA3.1-8B-Instruct) to turn continuous soft prompts into candidate instructions, but many different soft prompts generate the same instruction, producing redundant queries that waste budget.

The paper's goal is to turn that redundancy — the "preimage" structure, i.e., the set of soft prompts that map to a single instruction — from an obstacle into a useful prior that accelerates optimization.

Key Contributions

1. Reinterpreting the many-to-one problem as a resource. The authors reframe the many-to-one mapping between soft prompts and instructions, previously treated as harmful redundancy, as informative structure about the objective function that can be exploited for optimization.

2. PRESTO, a three-component framework. The framework combines (a) score sharing, which propagates one black-box evaluation score to every soft prompt in the same preimage; (b) preimage-based initialization, which greedily selects initial preimages that maximize coverage of the search space; and (c) score consistency regularization, which forces the score predictor to output matching predictions for soft prompts within unscored preimages.

3. State-of-the-art results across 33 tasks. PRESTO reports the best performance on 30 instruction induction tasks and 3 arithmetic reasoning tasks relative to six baselines.

4. Empirical analysis of why it works. Ablations, visualizations of initial data coverage, and score-predictor error analyses quantify the contribution of each component.

Main Findings

• Scale of the redundant structure: In the motivating experiment with LLaMA3.1-8B-Instruct, the white-box model produced approximately 6,500 unique instructions from 10,000 distinct soft prompts, and the largest preimage contained more than 1,000 soft prompts while the 100th largest had around 5.

• Effective data amplification: Under the same query budget, PRESTO achieves the effect of obtaining 14 times more scored data. After optimization, PRESTO assigns scores to over 2,300 soft prompts on average, versus 165 scored data points for previous methods (equal to the query budget in this setting).

• Instruction induction performance: On the 20-task subset reported in the main table, PRESTO achieves the highest accuracy on 12 of 20 tasks, three times more than the second-best method, ZOPO (4 tasks). PRESTO's average rank is 1.90, followed by ZOPO at 3.05, INSTINCT at 3.70, APE at 4.25, EvoPrompt at 4.70, InstructZero at 4.80, and OPRO at 5.20.

• Ablation results: Starting from a vanilla baseline (0 wins, average rank 4.55, average accuracy 51.91), adding score sharing raises accuracy to 59.57 and improves average rank to 3.10; adding score sharing plus consistency regularization gives 61.77 accuracy and 2.65 rank; score sharing plus preimage-based initialization gives 61.82 activity and 2.30 rank; and the full PRESTO model reaches 9 wins, average rank 2.20, and average accuracy 62.91.

• Chain-of-thought prompting: PRESTO obtains the highest accuracy on AQUA-RAT (0.7756), outperforming ZOPO (0.7520), INSTINCT (0.7480), InstructZero (0.7480), and the hand-crafted prompt (0.7402). On SVAMP it ties for best at 0.9400 (matched by InstructZero and ZOPO). On GSM8K it scores 0.9128, compared with ZOPO's best-in-table 0.9143, hand-crafted 0.9121, INSTINCT 0.9098, and InstructZero 0.9083.

• Better score prediction: On the objective counting task, using 100 randomly selected soft prompts for training and another 100 for testing, root mean squared error (RMSE) dropped from approximately 0.27 for the vanilla setting to around 0.23 when either score sharing or score consistency regularization was applied, and to approximately 0.15 when both were used together.

• Better search-space coverage: t-SNE visualizations on the objective counting task show that random initialization gives the sparsest coverage, score sharing enlarges the initial dataset without extra black-box queries, initialization with only the representativeness score improves coverage, and the full coverage score produces the densest coverage.

Methodology in Plain English

The researchers start by sampling a large candidate set of 10,000 soft prompts using a quasi-random method (a scrambled Sobol sequence mapped through a fixed random projection), and they precompute the white-box LLM embeddings of these prompts once at the start.

Because a white-box LLM is deterministic, they can group soft prompts by the instruction each one generates. Every group of soft prompts mapping to the same instruction is called the preimage of that instruction. This grouping is done before optimization begins.

During optimization, when a black-box model (GPT-4.1) returns a score for one instruction, PRESTO copies that score to every soft prompt in that instruction's preimage — no additional black-box calls are needed. This is the score-sharing step, and it is what inflates 165 real queries into over 2,300 scored data points on average.

For initialization, instead of picking soft prompts at random, PRESTO greedily picks whole preimages. A coverage score combines a representativeness score (measured with squared Maximum Mean Discrepancy, checking how closely the selected set matches the full candidate embedding distribution) and a size score (relative preimage size). Preimages are added one at a time until the initial count is reached.

For the score predictor (an MLP trained over the white-box embeddings via NeuralUCB-style optimization), PRESTO adds a consistency loss that penalizes different predictions for soft prompts in the same unscored preimage. The total loss is the mean squared error on scored preimages plus a weight γ times the consistency loss, with γ ramped linearly from 0 up to its maximum over a warm-up period T. A toy example with a two-layer linear model illustrates that this regularization lets the model transfer information to unscored regions.

All components assume both the white-box and black-box LLMs are deterministic, and the exemplars used to generate instructions are fixed per task.

Why This Matters

Impact on research: This work reframes a widely known inefficiency in white-box-assisted prompt optimization as a source of free supervision. It suggests that the internal redundancy of LLM generation can serve as a prior, which may influence how future black-box optimization methods for LLMs are designed — and it directly challenges the prior strategy of INSTINCT (sampling well-separated soft prompts) and ZOPO (discarding duplicates).

Real-world applications (implications, not claims tested in the paper):

• Reducing the API cost of prompt engineering pipelines that repeatedly query commercial LLMs such as GPT-4.1.
• Improving chain-of-thought style instructions for math and reasoning assistants, given the reported gains on AQUA-RAT and competitive results on GSM8K and SVAMP.
• Enabling smaller, budget-constrained research groups to run instruction optimization, since the paper states its goal is to reduce the cost of experimentation and improve accessibility for researchers with limited resources.
• Building task-specific instruction optimizers for domains where labeled validation data is scarce and each black-box evaluation is expensive.

Industry relevance: Query budgets translate directly into API spend. A method that extracts roughly 14 times more scored data from the same 165 queries is directly relevant to companies that tune prompts against proprietary models they cannot fine-tune. The paper also notes overlapping risks: improved optimization could be used in ways that reinforce biases or generate harmful content, requiring careful deployment and alignment with responsible AI principles.

Future Directions

• Scaling behavior: The authors state that PRESTO's benefits are more pronounced when applied to a large candidate set, since score sharing is most effective when many soft prompts map to the same instruction. How it behaves with smaller candidate sets is left open.
• Computational overhead: The paper acknowledges that preimage-based score sharing incurs mild computational overhead compared to simpler baselines; reducing or amortizing this cost is a natural next step.
• Transfer across white-box models: The preimage structure depends on the specific white-box LLM used to generate instructions. Whether preimage information transfers or can be reused across different white-box LLMs is not addressed.
• Combining with other optimizers: The method is built on INSTINCT's NeuralUCB and score-predictor setup. Whether the same preimage-based sharing and regularization help other search algorithms (for example Bayesian optimization or zeroth-order methods such as ZOPO) is an open question.

Target Audience

This paper is most useful for machine learning researchers and practitioners working on prompt engineering, black-box optimization, and LLM instruction tuning — particularly those who build pipelines on top of API-accessed models and care about query efficiency. It is also relevant to researchers studying soft-prompt optimization and the generative behavior of white-box models, and to engineers who need to squeeze more performance out of a fixed evaluation budget. Readers without background in embeddings or black-box optimization will need to consult the cited prior work (InstructZero, INSTINCT, ZOPO) for context.

Authors’ abstract

Large language models (LLMs) have achieved remarkable success across diverse domains, due to their strong instruction-following capabilities. This has led to increasing interest in optimizing instructions for black-box LLMs, whose internal 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 a structure that hinders optimization efficiency, we reinterpret it as a useful prior knowledge that can accelerate the optimization. To this end, we introduce PREimage-informed inSTruction Optimization (PRESTO), a 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 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. By leveraging preimages, PRESTO achieves the effect of effectively obtaining 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. Code is available at https://github.com/mlvlab/PRESTO